自適應貪婪算法在Web服務查詢優化上的應用

孫茂榮，劉呈則，張 益，王曉翔

（國核電站運行服務技術有限公司，上海200233）

0 引 言

采用非自適應的貪婪算法［1］雖然能幫助 Web服務使用者縮短Web服務的響應時間、提高執行效率，但由于Web服務背后數據的分布性，信息處理的動態性以及流數據的出現，原始的貪婪算法已經無法滿足Web服務在查詢優化上的需要。隨著 AQP （adaptive query processing）［2］即自適應查詢處理技術的出現，基于Eddy和CQP（corrective query processing）等自適應技術的系統也逐漸被廣泛應用。若在Web服務上的查詢優化上采用自適應技術，將會影響正在執行的查詢計劃或者已經排定的操作，這將可能提高本地DBMS查詢性能，有效地處理分布式情況和解決流數據問題。

本文給出了基本AQP概念，并針對自適應查詢優化的Web服務給出一個 WSPRC模型。在介紹了自適應貪婪算法［2－3］的基礎上，將A－Greedy算法與 Web服務上的查詢優化相結合，并詳細闡述查詢優化執行的過程。最后，對采用了A－Greedy算法的 Web服務上的查詢優化的執行性能進行了評估。

1 AQP

1.1 AQP的定義

AQP即自適應查詢處理，它是指在查詢優化過程中，根據查詢反饋的結果而動態的調整查詢計劃的執行，它是自主數據庫管理系統的基礎，主要針對數據庫查詢處理的交叉問題以及Web上應用。

1.2 AQP與Web服務查詢優化

Web服務［4－5］（web service，WS）采用了面向服務的體系架構 （SOA），解決了分布式和異構環境下系統集成的問題。當客戶在查詢中需要調用多個Web服務時，通常會涉及到訪問Web服務的先后順序及Web服務的響應時間等優化處理問題。而AQP技術不僅能適合Web服務的這種數據的地域分布性及復雜的查詢過程，還能提高查詢效率。本文正是將Web服務查詢優化與AQP技術相結合來彌補其不足。

2 WSPRC

下面首先給出采用了AQP技術的WSPRC模型結構，然后對其具體的處理流程進行描述。

2.1 WSPRC模型

WSPRC （web service profiler－reoptimizer－cache） 模 型的主要思想是：當客戶端提出查詢Web服務的請求時，該模型對所需查詢的Web服務進行查找和分析，然后交由再優化器進行查詢優化處理并制定出一個查詢計劃，同時將所制定的查詢計劃存入緩存單元，最后按照該查詢計劃來調用Web服務。圖1給出了WSPRC模型圖。

圖1 Web Service Profiler－Reoptimizer－Cache

2.2 WSPRC模型的處理流程

根據上節所闡述的WSPRC模型的主要思想，本節首先給出一個Web服務的查詢示例：假設一個企業需要給工齡超過10年的員工的社保卡發放額外的醫療補貼。首先，企業需要根據員工號來查找員工的身份證號碼，然后根據員工身份證號碼去勞動保障部門查找工齡超過10年的員工，同時查找員工的社保卡號碼和與社保卡所關聯的銀行卡號，最后，對符合條件的員工的銀行卡上發放補貼。

下面給出完成這個查詢所需涉及到的4個Web服務：①WS1：Employee ID （EID） → （Identity Card Number（IDN）；②WS2：Identity Card Number（IDN）→ （Working Age（WA）；③WS3：Identity Card Number（IDN）→ （Social Security Number（SSN）；④WS4：Social Security Number（SSN）→ （Credit Card Numbers（CCN）。

其中，根據員工號找到對應身份證號的WS1是其余WSi，i∈ （1，4］的優先約束，即WS1必須首先完成。同樣WS3也是WS4的優先約束，而WS2與WS3則可同時執行。分別給出Linear執行和Parallel執行的2條查詢Web服務的訪問計劃，如圖2所示。

圖2 WS Query Plan（Parallel ＆ Linear）

這里將采用偽代碼的方式描述WSPRC模型的處理流程，首先給出以下相關定義：①WSi表示序號為i的Web Service；②Aj表示需要投影的屬性 （Attribute）；③Pj（Aj）表示在屬性上運用謂 詞 （predicate）；④ITQ表示輸入的元組隊列 （Input Tuple Queue）；⑤A－Greedy表示自適應貪婪算法；⑥RC表示緩存模塊。

WSPRC模型處理流程如下：

2.3 WSPRC模型的分析

（1）Result Cache：在 WSPRC模型中引入 Result Cache組件，即對已經調用過的 Web服務的查詢結果［6］進行緩存，其緩存的內容包括兩個部分：Web服務的查詢結果和 Web服務的查詢方案。

（2）Profile：在一些 Web服務相關的系統中 （如WSMS［7］）Profile也是存在的，它的作用是：對所需的Web服務的響應時間和相關的一些統計數據進行分析。本文提出的WSPRC模型中Profile除了上述的2個共同的作用外，還持續對網絡上注冊發布的Web服務進行查找分析，同時將搜尋到得結果發送給Reoptimizer。

（3）Reoptimizer：這是 WSPRC模型中一個核心的組件。Reoptimizer將采用A－Greedy算法對從Profile處得到的Web服務相關信息進行分析，并根據Web服務有無優先約束的特點［8］，結合當前信息流及 Web服務自身的情況，選擇出一條最佳的Web服務查詢訪問方案。

上面所說的3個組件是本文提出的WSPRC模型的核心部分，這3個組件協同工作，在一定程度上提高了Web服務的查詢效率，節省了用戶查詢Web服務的成本。

3 影響Web服務查詢的相關因素

WSPRC在執行查詢優化過程中需要考慮一些影響查詢訪問的因素，下面將分別進行簡單介紹。

（1）Precedence Constraints［9－10］即優先約束，在示例1中需要首先通過查詢WS3得到相關的社保卡號，才可以調用WS4來查詢與社保卡號相關聯的銀行卡號，所以WS3是WS4的優先約束。

（2）Linear與Parallel［11］：即需要根據 Web服務間的具體情況來決定采用哪種方案。WSPRC模型需要根據Web服務間的具體情況來決定采用Linear還是Parallel方案。通常在無優先約束，但Web服務間存在謂詞條件的情況時，則優先考慮采用Linear方案，而Parallel方案則可用于無謂詞過濾，并且Web服務間無直接關系的場合。

（3）過濾性：在文獻 ［2］中，采用選擇性來表示 WSi在接收到一個元組輸入后應用相關謂詞選擇而得到的最終結果。本文中將使用過濾性 （Filter）來衡量WS對輸入元組的過濾能力，過濾性高的WS可考慮將其排列在查詢計劃較前的位置。這里假定Web服務的選擇性小于1，即過濾后輸出元組數目小于輸入元組數目。

（4）元組處理時間［12］：從 WS接收一個元組開始，到應用相關謂詞進行過濾，最后返回結果的這段時間稱為元組處理時間，文中將用時間成本 （cost time，CT）來表示元組處理時間。

本文提出的A－Greedy算法將持續的監控CT的變化，并對實時反饋信息的分析，制定出新的查詢訪問計劃，彌補了固定元組處理時間的不足。

4 A－Greedy查詢優化

4.1 Pipelined Filters問題

關于Pipelined Filters問題的研究較多［13－14］，即用一系列過濾器來處理連續輸入的流元組信息，它在流數據應用及多路流連接方面是最為通用的。在Web服務的查詢訪問中流信息的輸入也日益增多，如何很好地解決流處理的問題即Pipelined Filters問題，也是Web服務面臨的挑戰之一。本文采用的A－Greedy針對流和過濾器 （即根據WS的過濾性）的特性來動態的調整WS的調用順序，減少了調用Web服務的成本。

4.2 Adaptivity Loop

自適應循環框架［15］貫穿AQP技術，它包括：評測、分析、制定計劃及執行這4個主要部分，他們循環執行。A－Greedy正是遵循這樣的框架來對Web服務的調用過程進行度量，分析及改進的。

4.3 A－Greedy的主要思想

為了闡述A－Greedy主要思想，先給出如下相關定義：

（1）Fi：表示第i個的過濾器 （Filter），即WSi對輸入元組的過濾能力，其中1≤i≤n；

（2）CP（i，j）：表示條件概率，即對于輸入的元組信息，前面F1，F2，…，Fj個未過濾成功而被Fi成功過濾的概率，其中1≤i≤n，j＝i–1；

（3）CTi：即上節中介紹的元組處理時間，其中1≤i≤n。

（4）O：在對文獻 ［3］的修改上給出了如下代價公式

（5）GI：貪婪不變式［3，16］，在GI中分子是該 WS過濾元組的概率，分母是該WS處理該元組的時間，通過權衡WS的過濾元組的能力和處理元組的時間來比較Web服務的訪問代價，代價較小的Web服務將優先得到調用，具體公式如下

但公式GI并不適用于下列情況：

（1）相關Web服務的調用順序存在著優先約束關系（如示例1中的WS3和 WS4）。

（2）無優先約束也無相關謂詞條件的Parallel關系 （如示例1中的WS4和 WS5）。

A－Greedy的主要思想就是持續的監控當前需要查詢訪問的Web服務的代價O，根據代價的由小到大的順序建立最優的Pipelined查詢訪問方案，并實時針對當前輸入元組信息的變化及Web服務的反饋信息調整方案，使得Web服務的查詢能夠自適應。

4.4 A－Greedy的優化過程

A－Greedy的執行過程可以分為兩個階段：建立初始方案和方案優化。下面將分別進行介紹：

（1）構建初始的Web服務查詢圖。如示例1中，按照調用的先后順序，擬定初步的查詢計劃，通常為圖2中的Parallel方案。

（2）對示例1進行修改，增加一個WS5負責查找符合條件的員工的社保所屬的地區名稱：WS5：Social Security Number（SSN）→District Name（DN），對 Web服務進行分級，采用式 （1）和 （2）分析各 Web服務的查詢代價。等級劃分如圖3所示。

1）根級別與優先約束。如圖3中兩個查詢方案的級別1的服務為根級別，第1個查詢方案中的WS3是WS4的優先約束，第2個查詢方案WS3是WS4和WS5的優先約束，由于這些服務之間存著指定的關系，所以A－Greedy將忽略對根級別及優先約束的優化。

圖3 對查詢方案進行等級劃分

2）無優先約束但有相關謂詞條件的。在圖3的第1個查詢訪問方案的級別2中WS2與WS3間雖無優先約束關系可并發執行，但WS2含有謂詞條件WA＞10，在運用式（2）計算可知，將WS2前置將會使輸入的員工信息大量過濾，若此時再將過濾后的元組交由WS3處理，則可以減少冗余數據的產生，提高執行效率。因而A－Greedy將會調整WS2與WS3的位置，最終效果如圖2的Linear方案。

3）無優先約束無相關謂詞條件的。在圖3的第2個查詢方案中，WS4與WS5之間即無優先約束也不存在相關聯的謂詞，即WS4與 WS5調用后的結果相互獨立。此時A－Greedy將會采用Parallel方案來調用 WS4與 WS5，這樣將會提高Web服務的并發性，縮短了執行時間，提高執行效率。

（3）反復執行步驟 （2）直到所需調用的 Web服務都已經優化排列完成，然后將最終Web服務的查詢返回結果和優化訪問方案保存到Result Cache中。

其次，由于Web服務處理的信息是動態變化的，這就使得原始的查詢優化方案可能不再合適，需要進行再次優化，其具體的再優化過程如下：

（4）由輸入信息變化導致的再優化。自適應循環框架中的評測部分將對一段時間輸入Web服務的信息元組進行度量，分析遵從Result Cache中存儲的Web服務查詢優化方案所返回結果的變化，若發現查詢成本上升，則需調整Web服務的查詢計劃，然后執行步驟 （6）。如示例1中的Linear方案為 最初確定的Web服務查詢計劃，假設員工信息的處理過程中，隨著員工號的增大，工齡大于10年 （即age＞10）的員工數量也逐漸增多即每個工號較大的員工的工齡都超過10年，則此時WS2的謂詞條件過濾能力大大降低，A－Greedy算法將修改 WS2與 WS3的順序，并發執行 WS2與 WS3，提高了 WS2與 WS3的并發處理能力，將Web服務的查詢訪問方案修改為圖2中的Parallel。

（5）由Web服務自身變化導致的再優化。在查詢訪問Web服務的過程中，自適應循環框架中的評測部分將對所需的調用的Web服務本身進行度量，若Web服務本身的變化導致執行代價的增加 （如Web服務的響應時間變大）或減少則需調整該Web服務的位置，然后執行步驟 （6）。

（6）執行再優化后的 Web服務查詢訪問方案，返回Web服務的執行結果，同時在Result Cache中存儲該方案，若仍有后繼輸入信息流入 Web服務則返回步驟 （4）進行評測和分析，否則Web服務查詢訪問將結束。

以上對A－Greedy優化過程的進行了詳細闡述，AGreedy在采用自適應循環框架后，不僅擁有用原始Greedy算法的優點，而且在調用Web服務中數據或服務發生變化后，通過實時的評測和分析，制定出新的查詢訪問方案，而這些是原始的Greedy算法所無法實現的。

5 實驗設計

上面對A－Greedy優化 Web服務查詢訪問的過程進行了詳細的描述。本節將分別對原始Greedy與本文的A－Greedy在以下3個方面進行 Web服務查詢時的性能評測：①初始Web服務查詢優化方案建立；②輸入的元組信息改變；③Web服務自身發生改變。

首先，給出示例2（在示例1的基礎上進行增補）如下：假設一個企業需要查找工齡超過10年并且已經辦理醫療保險的員工，對符合上述條件的員工的社保卡所關聯的銀行卡上發放醫療補貼并查找這些員工的社保所屬的地區名稱，下面給出完成這個查詢所需涉及到的6個Web服務：①WS1：Employee ID （EID） → （Identity Card Number （IDN）；②WS2：Identity Card Number （IDN） → Working Age（WA）；③WS3：Identity Card Number（IDN）→Medical Insurance（MI）；④WS4：Identity Card Number（IDN）→Social Security Number （SSN）；⑤ WS5：Social Security Number（SSN）→Credit Card Numbers（CCN）；⑥WS6：Social Security Number（SSN）→District Name（DN）。

初始狀態時WS1～WS6處理元組的時間CT如表1所示，表2為WS1～WS6的選擇性即1－CP（過濾性）。

表1 WS1～WS6處理元組的時間CT

表2 WS1～WS6的選擇性

5.1 初始Web服務查詢優化方案建立的評測過程

（1）尋找 Web服務間的優先約束關系，同時遵循Parallel方案優先原則。對示例2進行分析結果如下：

1）存在優先約束的：WS1→WS2，WS1→WS3，WS1→WS4，WS4→WS5，WS4→WS6。

2）可Parallel的 Web服務：WS2，WS3和 WS4以及WS5和WS6這兩組Web服務可以Parallel進行。

（2）構建初始的Web服務查詢優化方案，并對其進行分級，如圖4所示。

圖4 Web服務初始查詢方案

（3）根據式 （1）和 （2）計算WS1～WS6的查詢成本，成本計算如下 （其中I為輸入的信息元組）：

1）級別1的查詢成本：Cost（WS1）＝5.5＊1＊I＝5.5I。

2）級別2的查詢成本：其中WS2，WS3和WS4無優先約束，但存在謂詞條件對WS1返回的元組信息進行選擇，所以Greedy與A－Greedy都會對 WS2，WS3和 WS4應用式（2）（見表3）。

表3 在Level 2上應用GI

根據表3，WS2，WS3和 WS4之間的順序可能為 WS3→WS2→WS4，然后我們計算Level 2上所有可能路徑的查詢代價。原Parallel方案：Cost（WS2，WS3，WS4）＝4.1＊1＊I＋3.3＊1＊I＋3.5＊1＊I＝11.3I；Linear排列方案：①Cost（WS2→WS3→WS4）＝4.1＊1＊I＋3.3＊1＊0.63＊I＋3.5＊1＊0.63＊0.27＊I＝6.77253I；②Cost（WS2→WS4→WS3）＝4.1＊1＊I＋3.5＊1＊0.63＊I＋3.3＊1＊0.63＊0.71＊I＝7.78109I；③Cost（WS3→WS2→WS4）＝3.3＊1＊I＋4.1＊1＊0.27＊I＋3.5＊1＊0.27＊0.63＊I＝5.00235I；④Cost（WS3→WS4→WS2）＝3.3＊1＊I＋3.5＊1＊0.27＊I＋4.1＊1＊0.27＊0.71＊I＝5.03097I；⑤Cost（WS4→WS2→WS3）＝3.5＊1＊I＋4.1＊1＊0.71＊I＋3.3＊1＊0.71＊0.63＊I＝7.88709I；⑥Cost（WS4→WS3→WS2）＝3.5＊1＊I＋3.3 ＊ 1 ＊ 0.71 ＊ I ＋ 4.1 ＊ 1 ＊ 0.71 ＊ 0.27 ＊I＝6.62897I。

從表3和上述成本計算可知，選擇Linear排列方案中的路徑WS3→WS2→WS4為級別2的較優訪問路徑，其代價最小為5.00235I。

3）級別3的查詢成本：WS5和WS6之間并無優先關系和相關的謂詞條件，所以WS5和WS6采用Parallel方案，且他們總是在最后被調用，執行他們的代價不會影響前面的優化結果，因而可以被看為常量。

（4）構建優化后的Linear方案，如圖5所示。

圖5 優化后的Web服務查詢方案

由于A－Greedy初始建立Web服務查詢訪問方案的優化過程與Greedy相似，所以他們的優化代價基本相同：Cost（WS）＝ Cost（WS1）＋5.00235I＋ Cost（WS5，WS6）。

5.2 對輸入元組信息改變的評測

修改示例2，在Web服務查詢方案確定后，隨著員工號碼逐漸增大，發現輸入的90%的員工都辦理了醫療保險，即WS3的過濾性CP＝0.1，這樣輸入元組的信息影響了正在執行的Web服務優化查詢訪問方案。

（1）Greedy算法無法進行自適應，不能改變目前的執行方案，所以代價仍然為：Cost（WS）Greedy＝5.5I＋3.3＊1＊I＋4.1＊1＊0.9＊I＋3.5＊1＊0.9＊0.63＊I＋ Cost（WS5，WS6）＝ Cost（WS1）＋ 8.9745I＋ Cost（WS5，WS6）。

（2）A－Greedy算法度量到輸入信息的變化，重新對WS2，WS3，WS4的執行代價進行評測，由于WS1，WS5和WS6沒有發生變化，所以可以仍然將他們的成本看成是常量。對級別2的成本重新進行評測。

根據表4，WS2，WS3和 WS4之間可能存在的路徑為WS2→WS4→WS3。然后我們計算Level 2上所有可能路徑的查詢代價。通過計算可知，選擇代價較小的WS2→ WS4→WS3，這樣A－Greedy的整體方案代價為：Cost（WS）A－Greedy＝Cost（WS1）＋ 7.78109I＋ Cost（WS5，WS6），因而Cost（A－Greedy）＜ Cost（Greedy）。

表4 在Level 2上應用GI

5.3 對Web服務自身發生改變的評測

修改示例2，在Web服務查詢方案確定后，WS2由于自身未知原因處理元組能力下降即元組的處理時間加長為CT＝6，這樣由于Web服務自身產生的變化影響了正在執行的Web服務優化查詢訪問方案。

（1）Greedy算法無法進行自適應，所以執行的代價仍然為：Cost（WS）Greedy＝Cost（WS1）＋3.3＊1＊I＋6＊1＊0.27＊I＋ 3.5 ＊ 1 ＊ 0.27 ＊ 0.63 ＊I＋ Cost（WS5，WS6）＝ Cost（WS1）＋ 5.51535I＋ Cost（WS5，WS6）。

（2）A－Greedy算法在執行過程中監測到WS2的處理時間加長，它將立刻重新對WS2，WS3，WS4的執行代價進行評測，同上類似，WS1，WS5和WS6沒有發生變化，所以可以仍然將他們的成本看成是常量。

根據表5，WS2，WS3和 WS4之間可能存在的路徑為WS3→WS4→WS2。然后我們計算Level 2上所有可能路徑的查詢代價。通過計算可知，選擇代價較小的WS3→WS4→WS2，這樣A－Greedy的整體方案代價為：Cost（WS）A－Greedy＝Cost（WS1）＋5.3952I＋ Cost（WS5，WS6）。

表5 在Level 2上應用GI

因而Cost（WS）A－Greedy＜ Cost（WS）Greedy，A－Greedy在Web服務自身發生變化的時候，實時評價當前的Web服務的調用情況，選擇出較佳的查詢訪問路徑。

通過從以上3個方面的比較可知，擁有自適應能力的A－Greedy在Web服務查詢訪問方面的表現比Greedy更加出色，能更好的適應外部Web服務和內部信息的變化，通過實時評估和分析，為Web服務查詢訪問選擇較佳的查詢路線。

6 結束語

本文首先為Web服務查詢訪問提出了一個采用AQP技術的WSPRC模型，并對其主要組件進行了分析。實驗評測表明，引入了AQP技術后，A－Greedy相對Greedy能更好的適應Web服務變化的需求，實時地對當前執行的Web服務查詢方案進行評估，制定出更優的查詢方案。本文在解決Web服務查詢優化時也存著一些有待將來解決的問題，如對Web服務的響應時間并未考慮到一些網絡延遲，硬件配置方面的因素，此外，如何控制A－Greedy算法使用范圍，使其不會因為頻繁的變更查詢方案，反而降低了查詢能力等問題。

［1］Couvreur C，Bresle Y.On the optimality of the backward greedy algorithm for the subset selection problem ［J］.Matrix Anal ＆ Appl，2009，21 （3）：797－808.

［2］Deshpande A，Ives Z，Raman V.Adaptive query processing［J］.Foundations and Trends in Databases，2007，1 （1）：1－140.

［3］Babu S，Motwani R，Munagala K，et al.Adaptive ordering of pipelined stream filters［C］.New York，NY，USA：Proceedings of the ACM SIGMOD International Conference on Management of Data，2005：407－418.

［4］Web Services［EB／OL］.http：／／www.w3c.org.

［5］CHOU W，LI L，LIU F.Web service enablement of communication services［C］.Proceedings of IEE International Conference on Web Services，2005：393－400.

［6］YU W D，Aravind D，Supthaweesuk P.Software vulnerability analysis for web services software systems ［C］.Proc of the 11th IEEE International Symposium on Computers and Communications，2006：740－748.

［7］Srivastava U，Munagala K，Widom J，et al.Query optimization over web services［C］.Proceedings of the 32nd International Conference on Very Large Data Bases，2006：355－366.

［8］LI L，CHOU W，LIU F，et al.Semantic modeling and design patterns for asynchronous events in web service interaction［C］.Proceedings of IEEE International Conference on Web Services，2006：223－230.

［9］Burge J，Munagala K，Srivastava U.Ordering pipelined operators with precedence constraints ［EB／OL］. ［2009－05－15］.http：／／infolab.stanford.edu／～usriv／papers／precconst.pdf.

［10］XU Shuhua，JIANG Wen，HUANG Zhigang.A web services query algorithm based on bottlenecks spending［J］.Computer Application，2007，27 （8）：1997－2000 （in Chinese）. ［徐署華，江文，黃志剛.一種基于瓶頸開銷的Web服務查詢算法［J］.計算機應用，2007，27 （8）：1997－2000.］

［11］YAN C，SHEN J，PENG Q.Parallel web prefetching on cluster server［C］.Proc of Canadian Conf on Electrical and Computer Engineering，2007.

［12］ Web service eventing （WS－Eventing） ［EB／OL］.http：／／www.w3.org／Submission／WS－Eventing／，2006.

［13］Condon A，Deshpande A，Hellerstein L，et al.Flow algorithms for two pipelined filter ordering problems ［C］.New York，NY，USA：Proceedings of the Twenty－Fifth ACM SIGMOD－SIGACT－SIGART Symposium on Principles of Database Systems，2006：193－202.

［14］Munagala K，Babu S，Motwani R，et al.The pipelined set cover problem ［C］.Edinburgh，UK：Proceedings of the 10th International Conference，2005：83－98.

［15］XIE Xiaoyuan，XU Baowen，SHI Liang，et al.A dynamic optimization strategy for evolutionary testing ［C］.12th ASIAPACIFIC Software Engineering Conference，2005.

［16］ZHAO Xinchao.A greedy genetic algorithm for unconstrained global optimization ［J］.Journal of Systems Science and Complexity，2008，18 （1）：102－110.