《一种基于泛化-特化关系模式的业务服务实例化方法.docx》由会员分享，可在线阅读，更多相关《一种基于泛化-特化关系模式的业务服务实例化方法.docx（13页珍藏版）》请在三一办公上搜索。
1、一种基于泛化-特化关系模式的业务服务实例化方法 本课题得到国家自然科学基金项目(60573117)和山东泰山学者项目资助。 作者简历: 张鹏 (1984- ), 男, 硕士研究生, zhangpeng, 主要研究领域为面向服务的计算; 王菁 (1978-),女, 博士,助理研究员, wangjing，主要研究领域为面向服务的计算，服务组合。赵小伟(1984- )，男，硕士研究生，主要研究领域为服务网格，工作流技术。张鹏1 王菁2 赵小伟1（1 山东科技大学信息科学与工程学院 青岛266510）（2 中国科学院计算技术研究所 网格与服务计算研究中心 北京 100190） 摘 要 业务服务作为业务
2、活动具体实现的一种抽象表示，在业务层上解决了业务用户可用及领域可复用的问题，但是，业务服务在落实到具体的物理服务时缺少一种规范化的实例化方法，因此，本文提出了一种基于泛化-特化关系模式的业务服务实例化方法。通过泛化-特化关系的判定，最终用户定制的表达个性化需求的业务服务能够发现它的邻近上界业务服务，并且基于泛化-特化关系模式的应用，业务服务只需要在它的邻近上界业务服务的公共实例集合中去匹配。实验表明，这种实例化方法能够很好的减少业务服务实例化中的冗余匹配，提高业务服务实例化的效率。关键词 业务服务；泛化-特化关系模式；实例化；邻近上界中图法分类号 TP311Business Services
3、Instantiation on the Basis of the Generalization-Specification Patterns ZHANG Peng1 WANG Jing2 ZHAO Xiao-Wei11（College of Information Science and Engineering. Shandong University of Science and Technology,QingDao 266510,China）2 (Research Center for Grid and Service Computing, Institute of Computing
4、Technology, CAS, Beijing 100190, China)Abstract Business Service, as an abstraction of concrete realization of a business activity, helps to relieve the complexity in end-user-oriented service assembly and reuse. However, there lacks a standard instantiation method for realizing business services on
5、 top of concrete software services. The paper proposes an instantiation method for business services on the basis of the generalization-specification patterns. By examining and summarizing generalization-specification relations and the patterns thereof, the customized business services that are adap
6、ted to end-user requirements only need to match to the software services that fall into the category of the patterns. Experiments indicate that the instantiation method can help to reduce the matching redundancy and to improve the instantiation efficiency.Key words Business Service; Generalization-S
7、pecification Patterns; Instantiation; Adjacent Upper Bound1. 引言网络技术的发展对科学研究活动正在产生着深远的影响，并且使得共享网络资源和进行跨时间和空间的科研协作成为可能。e-Science概念的提出意味着科学家能够方便地共享广域分布的大规模计算能力、存储能力和科学仪器，能够方便地获得和使用大量的科学数据以及与世界各地的科学研究人员进行交流协作。目前，Internet内已有大量的信息资源，也开始涌现出越来越多的可供使用的网络服务资源，例如仅在生物信息领域可统计到的Web服务数量就超过30001，并且还在不断增长。针对无序成长、高度自
8、治和复杂多样的网络资源，如何提供面向网络资源共享和集成的“资源在逻辑上一体、物理上独立自治”的虚拟计算环境，以支持最终用户方便高效的使用，已经成为当前网络计算技术领域的热点研究问题。业务服务2作为业务活动具体实现的一种抽象表示，在业务层上满足了最终用户对服务的可理解、可构造的需求，然而，业务服务只有落实到具体的物理服务，才能让最终用户真正的使用。由于业务服务和物理服务分属于问题域和解空间，因此需要通过一种跨所属域的资源实例化方法来实现两者之间的映射。我们把业务服务与物理服务通过跨所属域的匹配方法建立映射的过程称为业务服务实例化。首先通过一个实际场景，说明本文拟解决的问题。Jerry是某化学所的
9、科研人员，对生物信息领域的软件操作不是很熟悉。现在，Jerry接到一个任务：要尽快完成家蚕的化学实验，该实验流程中包括家蚕的核苷酸序列相似性查找。目前，网络上已经有很多实现序列相似性查找业务功能的Web服务，但是Jerry并不了解，也不会使用这些Web服务。Jerry现在只有整个实验的流程图，并且可以根据这个流程图构建家蚕的核苷酸序列相似性查找的业务服务，但是，这个业务服务并不是真正的计算资源，不能够返回Jerry需要的实验结果。为了解决Jerry遇到的问题，业务服务需要一种实例化方法能够保证其正确、快速的落实到对应的物理服务，实现具体的业务功能。目前，业务服务实例化方法主要有两种，一种是文献
10、2提出的业务服务实例化方法，该方法虽然能够保证业务服务正确的落实到物理服务，但是没有给出物理服务复用的具体解决办法，当物理服务数量较多时，业务服务在实例化过程中会产生很多冗余匹配，影响业务服务实现具体业务功能的效率。 图1 定制复用的业务服务实例化方法定制是对可复用资源进行修改以适应某一特定需求的过程3。文献4沿用了自上而下的需求细化和自下而上的已有服务资源复用的思想，提出了定制复用的业务服务实例化方法。如图1所示，最终用户通过对业务层上的业务服务A进行定制，可得到满足个性化需求的业务服务B。在业务服务B实例化时，由于可以复用软件层上的业务服务A的实例，所以只需要在业务服务A的实例集合中进行匹
11、配，从而缩小了匹配范围，但是，在哪个业务服务上进行定制，不同用户会有不同的做法。例如，一个用户可能通过对业务服务B进行定制得到业务服务C，如图1(a)所示，而另一个用户可能会通过对业务服务A进行定制来得到业务服务C，如图1(b)所示。由于业务服务A的实例数多于业务服务B的实例数，所以相同的业务服务C在与软件层的物理服务进行匹配时，匹配范围会不同，由此而产生冗余匹配，影响业务服务实现具体业务功能的效率。本文在分析和借鉴了服务聚合和服务匹配相关工作的基础上，提出了基于泛化-特化关系模式的业务服务实例化方法。与前两种方法相比，此方法可以通过发现邻近上界业务服务来确定业务服务的复用层次，并且基于泛化-
12、特化关系模式的应用，业务服务在实例化时可以减少冗余匹配，能够正确、快速地落实到对应的物理服务，实现具体的业务功能。文章的组织结构如下：第二章是泛化-特化关系模式，是本文的核心，主要给出了模式中的元素、元素之间的关系以及关系之间的映射三个方面的形式化定义，为基于泛化-特化关系模式的业务服务实例化方法提供了基础；第三章是基于泛化-特化关系模式的业务服务实例化方法；第四章是应用及评价；第五章对相关工作进行了比较分析；最后是全文总结。2. 泛化-特化关系模式模式是对某种环境中不断出现的问题给出的解决方案的核心，是解决问题的指导。下面给出泛化-特化关系模式解决业务服务落实到对应的物理服务问题的基本原理以
13、及具体的解释。2.1泛化-特化关系模式的基本原理对于如何将业务服务落实到对应的物理服务，使业务服务真正拥有业务能力的这个问题，泛化-特化关系模式给出了相应的解决方案。其基本原理是：在业务层上，业务服务之间建立泛化-特化关系，同时，在软件层上，这些业务服务对应的物理服务的集合之间建立包含-被包含关系。业务层和软件层通过实例化搭建沟通的桥梁。下图是泛化-特化关系模式的结构。图2泛化-特化关系模式的结构图2所示的结构中包括元素、元素之间的关系以及关系之间的映射三个方面，下面给出它们形式化的定义。2.2模式中的元素 模式中的元素包括业务服务和物理服务，其中业务服务通过引入特征模型体现了领域业务活动的共
14、性和变化性。特征模型由概念的特征及其特征间关系组成，通常以特征树形式描述，用于描述领域内系统的业务属性。特征树的一个配置是指根据特征树中定义的变化性约束选取得到的特征集合5。从特征树中得到一个特征树的配置的过程被称为配置过程。业务服务的特征模型描述了业务服务的输入参数、输出参数和服务质量属性，从而可以和具有特征模型描述的共性，以及特征模型允许的变化性范围内的物理服务进行匹配。物理服务是与业务服务具有匹配能力的语义Web服务操作，为了表述方便，后面简称语义Web服务。下面我们给出业务服务、业务服务特征树（输入参数/输出参数/服务质量特征树）和语义Web服务的定义。定义1. 业务服务：BS:=，其
15、中Action是业务服务的动作概念，Entity是业务服务的客体概念，InputFT/OutputFT/QosFT分别是业务服务输入/输出/服务质量特征树。定义2. 特征树：FT:=，其中F表示特征节点的集合，EFFFS为特征节点之间的有向边的集合，FS=Man,Opt,Xor,Or分别对应于必选、可选、异或、或四种特征类型。集合F和E构成了以rF为根节点的树结构。定义3. 语义Web服务：SWS:=其中Function是语义Web服务的功能语义，InputPara/OutputPara/QosPara是语义Web服务Input/Output/Qos标注语义的参数集合。2.3模式中元素之间的关
16、系“泛化特化”关系是概念间常见的一对关系。当在较低层上抽象表达了与之联系的较高层上抽象的特殊情况时，称较高层上抽象是较低层上抽象的“泛化”，而较低层上抽象是较高层上抽象的“特化”。对于业务服务来说，业务服务具有输入、输出、服务质量特征属性，表达了所对应的领域内业务活动的共性和变化性，因此可以通过业务服务的特征树之间的关系来刻画业务服务之间的泛化和特化关系6。“包含-被包含”关系是集合之间常见的一对关系，当集合A的元素都在集合B中，则称集合A被集合B包含，集合B包含集合A。下面给出这两种关系的形式化定义。定义4. 概念匹配：conceptA和conceptB是两个本体概念，如果conceptA等
17、价于conceptB，则称conceptA与conceptB概念匹配，cm(conceptA,conceptB)=true。定义5. 概念细化：conceptA和conceptB是两个本体概念，如果conceptA等价于conceptB或者conceptA是conceptB的子概念，则称conceptA是conceptB的细化，记为conceptA c conceptB。定义6. 业务服务特征树的配置：对于业务服务（输入参数/输出参数/服务质量）特征树FT=，如果存在语义Web服务的标注语义的参数（输入参数/输出参数/服务质量）集合P，以及存在FT的特征的子集FsF，Fs是FT的一个配置，并且
18、对于每个Fs中的特征f，存在P中的一个参数p，使得cm(p,f)=true，对于P中的每个参数p，存在Fs中的一个特征，使得cm(p,f)=true，则可称此语义Web服务的参数集P是业务服务特征树FT的一个配置，记为isConfiguration(P,FT)=true。定义7. 业务服务特征树的“泛化-特化”关系：对于两个业务服务特征树FT1，FT2，如果对于FT1的每一个配置P，同时也是FT2的一个配置，则可称FT1是FT2的特化，FT2是FT1的泛化，记为FT1 f FT2。定义8. 业务服务的“泛化-特化”关系：对于两个业务服务bs1和bs2，如果对于bs1的每一个输入、输出、服务质量
19、特征树FT1，bs2中都存在相应的特征树FT2 满足FT1 f FT2，并且bs1.Entityc bs2.Entity，bs1.Actionc bs2.Action，则可称bs1是bs2的特化，bs2是bs1的泛化，记为bs1 bs bs2。定义9. 语义Web服务集合的“包含-被包含”关系：对于两个语义Web服务集合SwsSet1、SwsSet2，如果swsSwsSet1，有swsSwsSet2，则称SwsSet1被SwsSet2包含，SwsSet2包含SwsSet1，记为SwsSet1 SwsSet2。2.4模式中关系之间的映射业务服务实例化建立了模式中元素之间的映射，同时也是实现模式中
20、关系之间映射的前提，下面给出业务服务实例的定义以及模式中关系之间映射的形式化表示。定义10. 业务服务实例：对于一个业务服务bs，如果存在一个语义Web服务sws，满足sws.InputPara是bs.InputFT的一个配置，sws.OutputPara是bs.OutputFT的一个配置，sws.QosPara是bs.QosFT的一个配置，并且sws.Function c bs.Action+bs.Entity，其中“+”表示组合（例如：序列+查找表示序列查找这个业务活动概念），则称此语义Web服务是业务服务的一个实例，记为instance(sws,bs)=true。业务服务的泛化-特化关系
21、与物理服务集合的包含-被包含关系之间映射的形式化表示如下：bs1 bs bs2 SwsSet1SwsSet2其中bs1 、bs2是业务服务，SwsSet1是bs1的实例集合，SwsSet2是bs2的实例集合。内涵包括：定理1. 如果两个业务服务具有泛化-特化关系，则它们对应的物理服务集合具有包含-被包含关系。证明：语义Web服务sws，业务服务bs1、bs2，其中bs1 bs bs2，instance(sws,bs1)=true，则根据定义7，sws.InputPara是bs1.InputFT的一个配置，sws.OutputPara是bs1.OutputFT的一个配置，sws.QosPara是
22、bs1.QosFT的一个配置，并且sws.Function c bs1.Action+ bs1.Entity，根据定义8，sws.InputPara是bs2.InputFT的一个配置，sws.OutputPara是bs2.OutputFT的一个配置，sws.QosPara是bs2.QosFT的一个配置，并且sws.Function c bs2.Action+ bs2.Entity，根据定义10，instance(sws,bs2)=true，根据定义9，得证。定理2. 如果两个业务服务对应的物理服务集合是包含-被包含关系，则这两个业务服务是泛化-特化关系。证明： sws，swsSwsSet1，根
23、据定义7，sws.InputPara是bs1.InputFT的一个配置，sws.OutputPara是bs1.OutputFT的一个配置，sws.QosPara是bs1.QosFT的一个配置，并且sws.Function c bs1.Action+bs1.Entity， 由于SwsSet1 SwsSet2，所以sws.InputPara是bs2.InputFT的一个配置，sws.OutputPara是bs2.OutputFT的一个配置，sws.QosPara是bs2.QosFT的一个配置，并且sws.Function c bs2.Action+bs2.Entity。反证法，如果存在bs1的输入
24、、输出、服务质量特征树FT1与bs2相应的特征树FT2不满足定义7中的泛化-特化关系，则FT1必然存在一个配置p，满足pFT1， pFT2，与开始证明的结论矛盾。因此，根据定义7，对于每一个bs1的输入、输出、服务质量特征树FT1，bs2中都存在相应特征树FT2，满足FT1 f FT2。根据定义8，得证。该模式针对业务服务如何落实到对应的物理服务给出了相应的解决方案和指导，具体有以下三个特点：一是模式中元素以及元素之间的关系有明确的定义；二是模式中元素之间以及元素关系之间建立了映射；三是来自较高层上的元素之间具有层次化的结构，有利于较高层上元素的使用和维护。3. 基于泛化-特化关系模式的业务服
25、务实例化方法基于泛化-特化关系模式的业务服务实例化方法分为两个过程，一个是发现邻近上界业务服务的过程，另一个是业务服务与物理服务的匹配过程。下面给出这个方法的基本原理和具体的做法。3.1方法的基本原理基于泛化-特化关系模式的业务服务实例化方法的基本原理是：业务服务之间的泛化-特化关系映射到软件层中表现为对应的物理服务集合之间的包含-被包含关系；物理服务集合之间的包含-被包含关系，映射到业务层中表现为对应的业务服务之间的泛化-特化关系。根据这个原理，业务服务从构造到实例化的整个过程如图3所示。图3 基于泛化-特化关系模式的业务服务实例化方法在业务服务构造上，首先，领域专家根据领域存在内聚性(领域
26、知识逻辑上的紧密相关性)和稳定性(在一定时间内，领域知识不会发生剧烈的变化)的特点2，按照领域分析原理，对领域内相似的业务活动根据其共性和变化性进行抽象，构造表示领域内相似业务活动的领域业务服务，方法是通过组合动作概念和客体概念来表示业务活动的概念，通过输入、输入、服务质量三个方面的特征建模完成业务活动的共性和变化性的特征的表示。其次，最终用户通过业务服务的特化操作进行个性化定制。在业务服务实例化上，首先，通过发现业务服务的邻近上界业务服务，确定其复用层次。这样一方面可以屏蔽不同的定制选择导致的业务服务匹配范围的不同，另一方面可以减少业务服务的冗余匹配。然后，业务服务在其邻近上界业务服务的公共
27、实例集合中进行匹配，建立与对应物理服务的映射，使业务服务真正拥有其业务能力。下面是邻近上界业务服务的形式化定义：定义11. 邻近上界业务服务：bs1、bs2是业务服务，如果bs2与bs1满足泛化-特化关系，即bs1 bs bs2，并且不存在业务服务bs，满足bs bsbs2且bs1bs bs。则称bs2是bs1的邻近上界业务服务。对于如何确定新的业务服务与它的邻近上界业务服务下原有的特化业务服务之间的关系，本文是利用了6中研究的业务服务融合的结果，在这里不做详细阐述。3.2邻近上界业务服务的发现发现邻近上界业务服务需要判定业务服务之间的泛化-特化关系，其中主要是判定业务服务特征树之间的泛化-特
28、化关系。定义7给出了通过业务服务特征树的配置集合之间的包含-被包含关系来判定业务服务特征树之间的泛化-特化关系的方法，但是，如图4所示的特征树，特征 f下有n个特征f1,f2,.,fn，它们与f通过“或”特征类型构成特征树的边，该特征树的配置个数是2n-1，在多项式时间内不能够发现它的所有配置，并且文献7也将特征树模型所有配置的发现归为NP完全问题，定义7的方法不能够在多项式时间内实现。因此，本文提出了另一个判定业务服务之间的泛化-特化关系的方法，这种方法首先是找到业务服务特征树的完备的特化操作集合OP，基于OP，判定业务服务特征树的泛化-特化关系转化为判定业务服务特征树的改变操作是否属于OP
29、中的特化操作集合，与定义7的方法相比，该方法能够在多项式时间内判定业务服务之间的泛化-特化关系。下面给出相关的定义和具体的实现方法。图4“或”特征类型的特征树3.2.1业务服务的特化操作业务服务的特化操作具体包括业务服务动作概念和客体概念的细化操作(选取特征表示的概念及其子概念的操作)和业务服务输入、输出、服务质量特征树的特化操作。其中业务服务特征树的特化操作包括12种基本的原子操作，下面给出这12种基本的原子操作。定义12. 业务服务特征树的原子操作：如果业务服务特征树的建模操作op不能通过其他操作及其组合来表示，则称op为业务服务特征树的原子操作。定义13. 业务服务特征树的特化操作：业务
30、服务bs1经过操作op得到业务服务bs2，如果bs1 bs bs2，则op是业务服务特征树的特化操作。以下列出满足特化操作定义的12种原子操作： 1）“可选”特征类型的特征改变为“必选”特征类型的特征； 2）“可选”特征类型的特征改变为“异或”特征类型的特征； 3）“可选”特征类型的特征改变为“或”特征类型的特征； 4）当同一个父特征下的“必选”特征类型的子特征只有一个时，“必选”特征类型的子特征改变为“异或”特征类型的子特征； 5）当同一个父特征下的“必选”特征类型的子特征只有一个时，“必选”特征类型的子特征改变为“或”特征类型的子特征； 6）当同一个父特征下的“异或”特征类型的子特征只有一
31、个时，“异或”特征类型的子特征改变为“必选”特征类型的子特征； 7）当同一个父特征下的“异或”特征类型的子特征只有一个时，“异或”特征类型的子特征改变为 “或”特征类型的子特征； 8）当同一个父特征下的“或”特征类型的子特征只有一个特征时，“或”特征类型的特征改变为“异或”特征类型的特征； 9）当同一个父特征下的“或”特征类型的子特征只有一个特征时，“或”特征类型的特征改变为“必选”特征类型的特征； 10）删除“可选”特征类型的特征； 11）当同一个父特征下的“异或”特征类型的子特征不只有一个时，删除“异或”特征类型的特征； 12）当同一个父特征下的“或”特征类型的子特征不只有一个时，删除“或
32、”特征类型的特征。3.2.2特化操作集合的完备性下面我们给出业务服务特征树的完备的特化操作集合的定义，并且证明上述12种原子操作组成的集合是业务服务特征树的完备的特化操作集合。定义14. 业务服务特征树的完备的特化操作集合OP：如果任何一个与业务服务特征树FT1满足泛化-特化关系的业务服务特征树FT2都能够在业务服务特征树FT1下通过OP中的特化操作实现，那么称OP是业务服务特征树的完备的特化操作集合。由于任何业务服务特征树的操作可以分解为一组原子操作，因此，如果从所有原子操作中找到的特化操作集合是完备的，则它对于业务服务特征树的操作也是完备的。因此，我们只需要通过证明所有业务服务建模的原子操
33、作是否是特化操作来找到完备的特化操作集合。下面我们将所有业务服务建模的原子操作分为增加特征、改变特征类型、删除特征三种情况。n 增加特征1）增加“可选”、“必选”、“异或”、“或”特征类型的特征不是特化操作证明: FT1表示特征树，FT2表示FT1增加了“可选”特征类型的特征f的特征树(“必选”、“异或”、“或”证明类似)。P，P是FT2的配置，P包含特征f，由于FT1中没有特征f，P不是FT1的配置，根据定义7，FT2不是FT1的特化，得证。n 改变特征类型1）“可选”特征类型的特征改变为“必选”特征类型的特征是特化操作证明: FT1表示包含“可选”特征类型的特征f的特征树，FT2表示FT1
34、中的特征f改变为“必选”特征类型特征的特征树。P， P是FT2的配置，则P满足特征树FT2配置的约束条件，由于“可选”特征类型没有作用特征树配置约束条件，所以 P一定满足特征树FT1配置的约束条件，P是FT1的配置，根据定义7，FT2 f FT1，得证。2）“可选”特征类型的特征改变为“异或”特征类型的特征以及“可选”特征类型的特征改变为“或”特征类型的特征是特化操作（证明同上面类似）3）当同一个父特征下的“必选”特征类型的子特征只有一个时，“必选”特征类型的子特征改变为“异或”或“或”特征类型的子特征是特化操作(在相同条件下，“异或”特征类型、“或”特征类型的证明类似)证明: FT1表示包含
35、“必选”特征类型的特征f的特征树，并且f的父特征在这个“必选”特征类型下只有一个子特征，FT2表示FT1中的特征f改变为“异或”或“或”特征类型特征的特征树。P， P是FT2的配置，则P满足特征树FT2配置的约束条件，由于在父特征只有一个子特征情况下，“必选”、“异或”、“或”特征类型作用于特征树配置的约束条件等价，所以 P一定满足特征树FT1配置的约束条件，P是FT1的配置，根据定义7，FT2 f FT1，得证。4）当同一个父特征下的“必选”特征类型的子特征不只有一个时，“必选”特征类型的子特征改变为“异或”或“或”特征类型的子特征不是特化操作(在相同条件下，“异或”特征类型、“或”特征类型
36、的证明类似)证明: FT1表示包含“必选”特征类型的特征f的特征树，并且f的父特征在这个“必选”特征类型下不只有一个子特征，FT2表示FT1的特征f改变为“异或”或“或”特征类型特征的特征树。由于“异或”、“或”、“必选”这三种特征类型作用于特征树配置的约束条件的定义不同，并且，在这种情况下它们作用于特征树配置的约束条件也不等价，因此，P，P满足特征树FT2配置的约束条件，是FT2的配置，但是P不满足特征树FT1配置的约束条件，P不是FT1的配置，根据定义7，FT2不是FT1的特化，得证。5）“必选”、“异或”、“或”特征类型的特征改变为“可选”特征类型的特征不是特化操作证明: FT1表示包含
37、“必选”特征类型的特征f的特征树(“异或”、“或”证明类似)，FT2表示FT1中的特征f改变为“可选”特征类型特征的特征树。由于“必选”特征类型对特征树配置作用了约束条件，因此，P，P不包含“可选”特征类型的特征f，P满足特征树FT2配置的约束条件，是FT2的配置，但P不满足特征树FT1中“必选”特征类型对特征树配置作用的约束条件，P不是FT1的配置，根据定义7，FT2不是FT1的特化，得证。n 删除特征1）删除“可选”特征类型的特征是特化操作证明: FT1表示包含“可选”特征类型的特征f的特征树，FT2表示FT1删除特征f的特征树。P， P是FT2的配置，则P满足特征树FT2配置的约束条件，
38、由于“可选”特征类型没有对特征树配置作用约束条件，因此P一定满足特征树FT1配置的约束条件，P是FT1的配置，根据定义7，FT2 f FT1，得证。2）当同一个父特征下的“异或”特征类型的子特征不只有一个时，删除“异或”特征类型的子特征是特化操作(在相同条件下“或”特征类型的证明类似)证明: FT1 表示包含“异或”特征类型的特征f1的特征树，并且f1的父特征在这个“异或”特征类型下还有其他子特征如特征f2，FT2表示FT1中删除f1或f2的特征树。P， P是FT2的配置，则P满足特征树FT2配置的约束条件，如果P不包含f1的父特征，“异或”特征类型没有对 P属于FT1的配置作用约束条件，则P
39、是FT1的配置。如果P包含f1的父特征，那么P必然包含f1或f2，因此，P满足FT1下“异或”特征类型作用特征树配置的约束条件，P是FT1的配置，根据定义7，FT2 f FT1。3）当同一个父特征下的“异或”特征类型的子特征只有一个时，删除“异或”特征类型的子特征不是特化操作(在相同条件下“或”特征类型的证明类似)证明: FT1 表示包含“异或”特征类型的子特征f1的特征树，并且f1的父特征在这个“异或”特征类型下只有f1子特征，FT2表示FT1中删除f1得到的特征树。P， P是包含f1的父特征但是不包含特征f1的FT2的配置，P满足特征树FT2配置的约束条件，但是P不满足FT1下“异或”特征
40、类型作用特征树配置的约束条件，P不是FT1的配置，根据定义7，FT2不是FT1的特化，得证。 4）删除“必选”特征类型的特征不是特化操作证明: FT1表示包含“必选”特征类型的特征f的特征树，FT2表示FT1删除f得到的特征树。P，P是FT2的配置，P不包含特征f，P满足特征树FT2配置的约束条件，但是P不满足FT1下“必选”特征类型作用特征树配置的约束条件，P不是FT1的配置，根据定义7，FT2不是FT1的特化。上述通过对业务服务所有原子操作是否是特化操作的证明，我们找到了12种满足业务服务特化操作定义的原子操作，这12种操作组成了业务服务特征树的完备的特化操作集合，这为业务服务泛化-特化关
41、系的判定提供了新的方法。3.2.3业务服务特化-泛化关系的判定算法该算法通过业务服务表示的业务活动概念的细化关系和业务服务输入、输出、服务质量特征树的泛化-特化关系来判定业务服务的泛化-特化关系。算法1. 泛化-特化关系判定算法GSS(bs1, bs2)输入: bs1, bs2;/ bs1,bs2表示业务服务输出:boolean;/返回bs1是否是bs2的特化过程:(1) if (bs1.Action+ bs1.Entity cbs2.Action+ bs2.Entity)(2) for ft bs2.InputFT, bs2.OutputFT, bs2.QosFT (3) for(int i
42、=0;ift.depth;i+)(4) selectedFeatureSet =selectedFeature(ft,i);(5) for(int j=0;jselectedFeatureSet.size;j+)(6) f=selectedFeatureSet.get(j);(7) ft=bs1.getFeatureTree(ft.getFTName();/根据bs2的特征树得到bs1相应的特征树(8) if(!isModify(f,ft) continue; /如果特征f没变化，则继续(9) operation= getModifyOperation(f,ft); /得到特征的变化操作(10
43、) if(!isSpecificationOperation(operation) /判断是否是属于完备的特化操作集合的特化操作(11) return false;(12) (13) return true;(14) else return false I通过分析，该算法最坏时间复杂度是O(h*t)，其中t是业务服务的特征树中特征最多的一层的特征个数，h是业务服务的特征树中最深的特征树的深度。3.2.4邻近上界业务服务发现算法该算法从领域业务服务开始，根据深度优先遍历的原则，判断每个业务服务下的特化业务服务与输入业务服务的泛化-特化关系。如果业务服务下的特化业务服务中存在输入业务服务的泛化业务
44、服务，进入下一层；如果业务服务下的特化业务服务中没有输入业务服务的泛化业务服务，则将该业务服务加入邻近上界业务服务集合中，并且对它的特化业务服务进行剪枝。具体算法如下：算法2. 邻近上界业务服务发现算法AUS(bs1, bs2)输入: bs1, bs2;/ bs1是业务服务，bs2是领域业务服务输出: bsSet;/ bs1的邻近上界业务服务集合过程:(1) bsSet,bsSet1= bs2.getsubbs();(2) boolean sign=true;/剪枝标记(3) for(int i=0;ibsSet1.size();i+) /遍历业务服务bs2下一层所有的业务服务(4) bs=b
45、sSet1.get(i);(5) if (GSS(bs,bs)(6) sign=false;(7) bsSet=bsSet.add(AUS(bs1,bs);(8) (9) if(sign) bsSet.add(bs2);(10) return bsSet;通过分析，邻近上界业务服务发现算法的最坏时间复杂度是O(p*h*t) ，其中p是领域业务服务下所有业务服务的个数，h是领域业务服务下所有业务服务的特征树中最深的特征树的深度，t是领域业务服务下所有业务服务的特征树中特征最多一层的特征个数。3.3业务服务实例化业务服务与它的邻近上界业务服务满足泛化-特化关系，因此，我们可以应用泛化-特化关系模式
46、。基于这个模式，我们得到了推论1 ，下面我们给出这个推论和利用这个推论的实例化算法。推论1：如果业务服务存在邻近上界业务服务，则该业务服务的实例在它的邻近上界业务服务的公共实例集合中。证明：bs，bsSet是bs的邻近上界业务服务集合，bsSet，则bsbsSet，bs bs bs，根据定理1，sws，instance(sws,bs)=true，则instance(sws, bs)=true，所以ws属于bsSet的公共实例集合。业务服务实例化可以建立业务服务与物理服务之间跨所属域的映射，这里是通过业务服务与语义Web服务进行能力信息的匹配来实现。这种匹配方法一方面可以基于服务能力信息以实现精
47、确匹配，另一方面允许匹配的一方(业务服务)的能力信息有一定的变化性，匹配的另一方(语义Web服务)只需与业务服务能力信息变化范围内的某一合法能力信息匹配即可，并且，需要匹配的语义Web服务集合缩小为邻近上界业务服务的公共实例集合。下面给出具体算法：算法3. 利用邻近上界业务服务的公共实例集合的业务服务实例化算法BSIA(bs1, bs2)输入: bs1, bs2, paraSet;/ bs1是输入业务服务, bs2是领域业 务服务, paraSet是参数集合输出: resultSet;/ bs1的实例集合过程:(1) 根据算法2得到bs1的邻近上界业务服务集合bsSet;(2) 取得邻近上界业务服务的公共实例集合wsSet;(3) for each swsdo(4) if(cm(sws.Function,bs1.Action+ bs1.Entity)(5) for ft b
