孙茂荣，刘呈则，张 益，王晓翔

（国核电站运行服务技术有限公司，上海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.