基于约束求解和描述逻辑的Web服务组合方法

技术领域

本发明属于计算机技术领域，尤其是软件技术领域。本发明提供了一种结合约束求解和描述逻辑的Web服务组合方法，用于Web服务的重用和增值。

背景技术

面向服务的软件体系结构SOA具有异构、系统互操作、松耦合等特性，得到了业界的普遍接受。作为SOA的具体实现，基于Web服务的软件开发也成为常见的软件开发方法，其中，服务组合是生成新服务与构建应用的重要方式。基于语义的服务组合，能够更加快速、准确、有效地定位所需要组合在一起的服务，涉及到领域本体、OWL语言等技术。

领域本体，是专业性的本体，描述的是特定领域中的概念和概念之间的关系，提供了某个专业学科领域中概念的词表以及概念间的关系。它是对学科概念的一种描述，包括学科中的概念、概念的属性、概念间的关系和关系的属性。由于知识具有显著的领域特性，所以领域本体能够更为合理而有效地进行知识的表示。“领域”是根据本体构建者的需求来确定的，可以是一个学科领域，可以是某几个领域的一种结合，也可以是一个领域中的一个小范围。

OWL，即网络本体语言，旨在提供一种可用于描述网络文档和应用之中固有的那些类及其之间关系的语言，用于编撰本体的知识表达，使得基于此技术的网络应用更加人性化和智能化，节省用户自身搜索资源的时间。

描述逻辑是用于知识表示的逻辑语言和以其为对象的推理方法，主要用于描述概念分类及其概念之间的关系，是一阶谓词逻辑的一个可判定子集。描述逻辑的重要特征是具有很强的表达能力和可判定性，能保证推理算法总能停止并返回正确的结果。可满足性问题是描述逻辑推理中的核心问题，因为许多其它问题(如包含检测、一致性问题等)都可转化为可满足性问题。可满足性问题的核心是基于描述逻辑ALC的Tableau算法。

Web服务组合是将基本Web服务有机地组织起来，以形成粒度更大、功能更强的增值服务或者系统的过程。根据Web服务组合方法所依赖的技术基础，可将其归纳为基于过程的组合方法和基于语义的组合方法。

基于过程的组合方法：利用Web服务组合与过程模型的相似性，使用较成熟的过程建模工具和语言对业务过程进行建模，采用“替代”法将过程模型中的相关组件最终替换成为具体的Web服务，从而获得有效的、可执行的Web服务组合方案。根据具体的建模工具和实现技术，过程驱动的Web服务组合又可分为基于工作流模型、基于状态演算和基于进程代数的Web服务组合。由于服务组合具有不确定性，因此传统的基于工作流的算法往往难以满足Web服务组合的需要。基于状态演算的算法要通过公理和证明实现服务组合，包含了复杂的形式化规约与转换，难以面向最终的业务用户。而基于进程代数的Web服务组合为服务组合的形式化描述和验证提供工具和方法，但对于同义异构的服务不能很好地处理，在实用性和通用性方面还有待提高。

基于语义的组合方法：语义驱动的Web服务组合强调Web服务的自描述，其基本思想是为Web服务描述和服务请求描述添加能被计算机系统所理解的语义，使Web服务组合方案通过推理自动生成。现有工作虽然能够准确地找到所需组合的服务，但是存在业务逻辑关系不严谨的情况。

发明内容

在现有工作的基础上，本发明要解决的问题是：克服Web服务组合过程中存在的组合不确定性、服务的动态变化性以及同义异构服务等问题，有效保障服务组合的质量。

本发明的技术方案为：基于约束求解和描述逻辑的Web服务组合方法，其特征是基于领域本体知识库的目标任务分解，设计各细粒度任务的优化目标，并提取任务接口的约束条件，然后通过约束求解得到细粒度任务的组合，再运用描述逻辑检测组合的有效性、合理性，避免流程冲突。

本发明具体包括以下步骤：

1)根据领域本体知识库，划分目标任务为可直接实现的细粒度任务；

2)基于各细粒度任务关联的服务获取所需的接口参数；

3)分析输入接口参数，确定每个参数可能的约束及相应的约束条件；

4)考虑用户对各细粒度任务的选择性偏好以及对应的本体类关系之间隐含的业务逻辑关系，再结合每个原子服务的输入接口参数约束条件，分析其它服务的输出接口参数，代入一个或者多个参数，进行约束条件求解，得到各个可行解，组成一个可行解序列，每一个可行解序列对应一个服务组合方案；

5)基于描述逻辑的推理和可满足性理论判断可行解序列是否有效、合理，去除不合理的可行解序列，得到最终的组合Web服务。

步骤1)中，可以使用已有的领域本体知识库，或者使用Protégé来构建知识库。在知识库中找到与目标任务相一致的本体类，根据领域本体中的本体类及其个体，以及本体类之间的父类、子类、祖先类、后代类以及兄弟类等类关系，还有本体类之间存在的对象属性关系，把目标任务划分为领域本体中已存在的本体类所对应的细粒度任务：

设A是目标任务，K为领域本体知识库，其中a_i表示领域本体中的本体类，b_j[b_k......]表示a_i对应的细粒度任务，1≤i≤n，1≤j＜k≤m，“[]”内的任务表示a_i需要b_j和其它细粒度任务组合完成，并且任务序列，即任务序列(b₁，......，b_m)能够实现任务A。

步骤2)中，根据前面得到的细粒度任务以及领域知识库的本体类，关联对应的服务，即WSDL文件，加上语义标注转化为OWLS文件以及关联的本体文件，再通过Jena本体操作语言得到(b₁，......，b_m)任务的输入输出接口。

步骤3)中，分析输入接口参数的特征，主要包括参数类型、参数的取值范围、参数名称，得到参数类型约束、参数取值范围约束以及语义相似度阈值约束，结合这些约束组合成一个输入接口的约束条件：

参数类型约束：一个任务输出接口中的参数类型type1必须是对应的另一个任务输入接口参数类型type2所接受的类型，即type1∈Accepted(type2)。

参数取值范围约束：一个任务输出接口中的参数值value1必须是对应的另一个任务输入接口参数值value2所接受的取值范围，即value1∈Range(value2)

语义相似度阈值约束：概念语义相似度包括结构相似度和层级相似度。

其中l为c₁，c₂在领域本体中的最短路径，α为调整因子，其值由经验值确定。这是一个单调递减函数，随着距离的增加，相似度减少。

其中h为c₁，c₂的最近公共祖先节点到本体根结点的路径长度，β为调整因子，其值由经验值确定。这是一个单调递增函数，随着深度的增加，相似度增大。

SemanticSim(c₁，c₂)＝w₁*SimStructure(c₁，c₂)+w₂*SimLevel(c₁，c₂)，其中w₁和w₂是由经验值确定的权重因子，当且仅当SemanticSim(c₁，c₂)≥λ(λ＝0.75，由经验值确定)时，才可满足语义相似度阈值约束。

因此，对于一个任务的输出接口参数<type1，value1，name1>和另一个任务的输入接口参数<type2，value2，name2>，name1对应的概念为c₁，name2对应的概念为c₂，必须满足接口约束条件

(type1∈Accepted(type2))∩(value1∈Range(value))∩(SemanticSim(c₁，c₂)≥λ)。

步骤4)中，任务的选择性偏好由用户个人信息建模所得，用户个人信息可包括性别、年龄、职业、地理位置、兴趣爱好标签等。用户的每一个属性可设定一个或者多个属性值，例如性别有男和女、年龄可以划分若干区间。对于用户的属性att₁，......，att_n，表示属性att_i第j个属性值，表示某类服务WS_j中的原子服务。提取每个属性中的一个属性值组合成一个条件，提取一个作为结果。基于用户的选择记录，运用Apriori算法进行关联分析，得出置信度大于经验阈值的<条件-结果>组合，这称为一条偏好规则，可表示为

步骤4)中，本体类之间的业务逻辑关系具体为：本体类之间的业务逻辑关系主要包括分支、循环、并发，根据类之间的父子、兄弟、祖孙等类关系以及对象属性所连接的类之间其它关系，提取细粒度任务之间的逻辑关系约束，形式化表示为Rel(t_i，t_j)，即细粒度任务t_i，t_j必须满足关系Rel(t_i，t_j)，若t_i，t_j存在多个业务逻辑关系，则t_i，t_j必须满足Rel₁(t_i，t_j)∩，......，∩Rel_n(t_i，t_j)。

步骤4)中，基于约束求解和描述逻辑的Web服务组合方法包括三类约束条件，即：对于每一个细粒度任务t_i的接口参数约束；用户对候选细粒度任务的选择性偏好约束；本体知识库中导出的业务逻辑关系约束。如果一个细粒度任务t_j的输出接口的参数t_jO或者多个t_j，t_k，......的输出接口参数t_jO，t_kO，......结合的结果能够满足细粒度任务t_i的输入接口参数t_iI的所有约束条件，就称t_jt_i或者(t_jt_k......)t_i组成一个衔接序列；若存在[t₁，......，t_n]使得能够满足整个目标任务，则称[t₁，......，t_n]是一个可行解序列。其中整个目标任务的输入接口参数能够满足t₁输入接口参数约束条件，t_n的输出接口参数满足整个目标任务的输出接口参数。

步骤5)中，描述逻辑是一阶逻辑的一个可判定子集，能够提供可判定的推理服务，并且具有语义特征。描述逻辑建立在概念(concept)和角色(role，即二元关系)之上，由构造算子(constructor)从简单概念和角色中构造出复杂概念和角色。描述逻辑主要包括三大组件：ABox，TBox以及TBox和ABox上的推理机制。其中：ABox是关于个体的断言，如Student(A)即表示A是一个学生；TBox是关于概念术语的断言，比如Father(A，B)即表示A是B的父亲。

一般而言，所有的推理问题都可以归结为一致性检测(或称为可满足性检测)。通过Tableau判定算法可以得到：当且仅当是不可满足的。

基于描述逻辑理论以及构建的领域本体库，使用Protégé以及基于描述逻辑的推理机Racer，对得到的可行解序列进行可满足性检测，对于不满足检测要求的，去除这个序列。

通过采用以上技术方案，本发明具有以下优点：

1.服务组合的有效性提升：本发明使用基于语义的技术，能够区分同形异义词以及同义异形词，组合服务结果的召回率都能够得到提升。

2.服务组合的准确性显著提升：传统的服务组合存在组合过程不确定性的问题，本发明中使用约束求解组合接口约束条件、选择性偏好约束以及业务逻辑约束，有效考虑了多种约束条件，能够充分解决组合过程的不确定性问题，使组合结果准确性得到显著提升。

3.服务组合的逻辑正确性有保障：本发明使用描述逻辑验证组合结果的可满足性，基于描述逻辑推理理论和Tableau算法具有严密的逻辑推理，使服务组合更加合理有效。

附图说明

图1为本发明的结构流程图。

图2为Travel领域知识本体库结构简略图

图3为TravelScheduling组合服务的具体流程。

具体实施方式

本发明方法首先对目标任务进行事件分析，接着基于领域本体知识库分解目标任务；再通过WSDL描述关联对应的Web服务；接着依据Web服务接口参数、用户选择性偏好和业务逻辑关系提取任务约束条件；然后借助约束求解器得到目标任务的可行解序列；最后结合工具Protégé，应用描述逻辑检测可行解序列的可满足性和一致性，得到最终合理、有效的服务组合。

本发明的流程如图1所示，具体包括如下四个步骤。

第一步：利用目标任务的事件分析和领域本体知识库对目标任务进行分解，得到若干细粒度任务。分析事件所需涉及的领域本体知识库的本体类及相关的属性，关联WSDL文档描述的原子Web服务w₁，w₂，......，W_n。

第二步：通过提取Web服务接口参数、用户选择性偏好和业务逻辑关系，得到任务约束条件。

(1)Web服务接口参数

Web服务的接口参数包括参数类型约束TypeConstraint，参数取值范围约束RangeConstraint，语义相似度阈值约束ThresholdConstraint，Web服务接口参数的约束可以表达为TypeConstraint∩RangeConstraint∩ThresholdConstraint。其中：

TypeConstraint：一个任务输出接口中的参数类型type1必须是对应的另一个任务输入接口参数类型type2所接受的类型，则type1∈Accepted(type2)，即TypeConstraint＝type1∈Accepted(type2)。

RangeConstraint：一个任务输出接口中的参数值value1必须是对应的另一个任务输入接口参数值value2所接受的取值范围，则value1∈Range(value2)，即RangeConstraint＝value1∈Range(value2)。

语义相似度阈值约束：概念语义相似度包括结构相似度和层级相似度。

其中l为c₁，c₂在领域本体中的最短路径，α为调整因子，其值由经验值确定。这是一个单调递减函数，随着距离的增加，相似度减少。

其中h为c₁，c₂的最近公共祖先节点到本体根结点的路径长度，β为调整因子，其值由经验值确定，这是一个单调递增函数，随着深度的增加，相似度增大。

SemanticSim(c₁，c₂)＝w₁*SimStructure(c₁，c₂)+w₂*SimLevel(c₁，c₂)，其中w₁和w₂是由经验值确定的权重因子，当且仅当SemanticSim(c₁，c₂)≥λ(λ＝0.75，由经验值确定)时，才可满足语义相似度阈值约束。

即ThresholdConstraint＝SemanticSim(c₁，c₂)≥λ。

(2)用户选择性偏好

定义1：表征用户选择性偏好决定目标属性的选择，称为一条规则Rule。

设Att₁，Att₂，.......，Att_n表示用户个人信息的属性，例如性别、年龄、职业、收入、兴趣爱好等，对于每一个属性Att_i，存在一个或者多个不同的属性值，设表示属性Att_i的一个属性值，不同的属性，属性值的个数可能不同。表示目标任务中的某类服务WS_i中包含的原子服务。

上述规则表示提取所有属性中每个属性的一个值组成规则的前提条件，运用Apriori算法进行关联规则分析，得出置信度大于经验阈值的<条件-结果>组合作为偏好规则，即提取目标任务中的某类服务WS_j中包含的一个原子服务，作为偏好选择项。

关联规则是形如X→Y的蕴涵式，表示通过X可以推导“得到”Y，其中X和Y分别称为关联规则的先导和后继。关联规则A→B的支持度support＝P(AB)，指的是事件A和事件B同时发生的概率。置信度confidence＝P(B|A)＝P(AB)/P(A)，指的是发生事件A的基础上发生事件B的概率。同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。如果事件A中包含k个元素，那么称这个事件A为k项集，并且事件A满足最小支持度阈值的事件称为频繁k项集。Apriori算法用来找到所有的频繁项集。

A中全部属性的所有属性值和B中的原子服务作为项组成一个项集。利用Apriori算法找到所有频繁项集，计算满足支持度和置信度阈值且表达形式为A→B的规则，作为偏好规则。

(3)业务逻辑关系

定义2：Rel(t_i，t_j)表征t_i，t_j之间存在的逻辑关系。

本体类之间的关系主要包括父子、兄弟、祖孙等类关系以及对象属性所连接的类之间的其它关系，而细粒度任务之间存在分支、循环、并发等业务逻辑关系，本体类之间的关系隐含一些不可违反的逻辑关系。

设class₁，class₂表示两个本体类，Rel_i(class₁，class₂)存在某种关系，可以是父子关系，即class₁是class₂的直接父类，或者Rel_i(class₂，class₁)，即class₂是class₁的直接父类；同理也可以表示兄弟关系、祖孙类关系以及两个类之间的对象属性关系。

设t_i，t_j表示两个细粒度任务，c_i，c_j分别为t_i，t_j对应的本体类，若在本体库中存在关系，使得t_i，t_j必须满足顺序关系或者合并关系<t_it_j>或者分支关系t_i∪t_j等关系，都可以转化为顺序关系和分支关系，则在目标任务实现中，t_i，t_j必须满足

$>{\mathrm{Rel}}_{{\mathrm{sequence}}_1}(t_i,t_j)\cap ,......,\cap {\mathrm{Rel}}_{{\mathrm{sequence}}_n}(t_a,t_b)\cap {\mathrm{Rel}}_{{\mathrm{branch}}_1}(t_c,t_d)\cap ,......,\cap$>$>{\mathrm{Rel}}_{{\mathrm{branch}}_n}(t_e,t_f),$>即由本体类之间关系反映得出的逻辑关系。

综合以上约束，对于一个Web服务WS₁的输入接口WS_I，另一个Web服务WS₂的输出接口WS_O必须满足约束：TypeConstraint(WS_I，WS_O)∩RangeConstraint(WS_I，WS_O)∩ThresholdConstraint(WS_I，WS_O)∩(Rule₁∪，......，∪Rule_n)∩(Rel₁(WS₂，WS₁)∩，......，∩Rel_m(WS₂，WS₁))＝True。其中细粒度任务对应于Web服务。

第三步：基于第二步中得到的约束条件，对约束条件进行编码，然后代入约束求解器中，得到可行解空间，解空间即为满足约束条件的所有可行解序列。编码过程即将条件表达式转换成求解器可识别的形式，不同的求解器需要的条件表达式形式略有不同。

本发明采用Z3-str求解器。Z3求解器是由微软研究院开发的一款SMT(SatisfiabilityModulo Theories)求解器，可以用来对数值型、布尔型表达式进行约束求解。Z3-str是在Z3的基础上加入String接口使得能够支持String变量的编码和求解。Z3-str支持的类型编码包括int，real，string，bool类型。假设要进行编码的变量为var，则各约束的编码规则示例如下：

参数类型的编码规则：(declare-variable var Real)，即要求var是Real类型。

参数取值范围的编码规则：(assert(＜＝var bigger))(assert＞＝var smaller))，表示var＜＝bigger且＞＝smaller这样的取值范围约束。

语义相似度阈值约束规则：首先基于语义相似度的求解，得到两个原子服务的输入接口与对应的输出接口的语义相似度，再与阈值比较，即可转换为参数取值范围的编码规则。

偏好规则的约束编码方法：e₁ op₁ e₂||op₂ e₃，其中op₁是一个比较操作符，取值范围为{＜，＜＝，＞，＞＝，＝＝，！＝}，e₁和e₂是常量表达式；另外，op₁也可以是{&&，||}中的一个逻辑操作符，此时e₁和e₂均为布尔表达式；op₂为二元逻辑操作符{not}，此时e₃为一个布尔表达式。一条偏好规则可以转换为布尔表达式：

业务逻辑关系的约束编码规则：即把业务逻辑关系转化为布尔表达式。对每一个细粒度任务赋予一个编号，即对于细粒度任务t_i，t_j分别有一个时钟向量编号ID_i和ID_j，若ID_i＜ID_j，则t_i在t_j之前发生，若ID_i＞ID_j，则t_i在t_j之后发生，若ID_i＝ID_j，则t_i和t_j属于并发关系。

编码完成后，把所有编码加入到Z3-str中进行求解，得到可行解序列。

第四步：基于第三步中得到的可行解序列，利用Protégé和描述逻辑，结合领域知识本体库的底层知识，对可行解序列进行可满足性检测。

Protégé是基于Java语言开发的本体编辑和知识获取软件，是本体开发工具，也是基于知识的编辑器，属于开放源代码软件。描述逻辑是一阶逻辑的一个可判定子集，能够提供可判定的推理服务，并且具有语义特征。描述逻辑建立在概念(concept)和角色(role，即二元关系)之上，由构造算子(constructor)从简单概念和角色中构造出复杂概念和角色。描述逻辑主要包括三大组件：ABox、TBox以及TBox和ABox上的推理机制。

Racer是基于描述逻辑系统的知识表达系统，采用Tableau算法，它的核心系统是SHIQ(描述逻辑的一种，主要包含交、并、存在、任意、数量约束等构造算子)。它提供支持多个TBox(术语公理)和ABox(断言事实)的推理功能。Racer具有较强的本体一致性检查功能，在TBox方面推理能力较强，能够对大本体文件提供良好的支持。其中领域知识本体库作为逻辑推理的基础知识，把领域本体文件作为输入加入到Protégé中，把可行解序列作为待检测的目标，借助于描述逻辑提供的可判定的推理服务和推理机Racer，Protégé通过IP地址与Racer连接，启动Protégé的一致性检测功能就能调用Racer进行检测。

基于领域本体知识库之间类与类、属性和属性、类和属性之间的关系，把可行解序列对应的类、类的属性以及关系作为Racer的输入，推理出所有存在的矛盾的关系，只要存在一个矛盾的关系，则去除对应的可行解序列。最终得到一个或多个经严格验证的可行解序列，即为最终的、合理有效的Web服务组合。

下面结合TravelScheduling组合服务流程对本发明作具体实施说明。旅游领域知识本体库架构如图2所示。本发明不仅限适用于该例。

TravelScheduling服务是一个行程安排的服务组合。当它收到用户的服务描述时，解析事件，得出事件发生的时间、地点，当前的时间、地点；输入旅游领域本体库，分析时间地点得出开会需要涉及到本体库中的交通方式、住宿方式；在Web服务集合中，找到交通方式和住宿方式本体类中子类本体相对应的原子服务。提取Web服务的接口参数，比如参数类型、参数取值范围、语义相似度阈值，得到服务接口参数约束；根据用户的基本信息得到关联规则判断用户偏好的交通方式和住宿方式；基于本体中类与类之间的关系得出服务组合时必须满足的业务逻辑关系。把约束放入约束求解器中求解，得到一个或者多个可行解序列。把领域本体知识库和所有可行解序列放入Protégé运用Racer推理机进行可满足性检测，去除不满足不一致性的序列，得到最终合理有效的结果。

对该服务进行服务组合的具体过程如下：

1、事件解析。

分析事件：包括用户个人信息、行程开始时间STime、行程结束时间ETime、行程地址TLocation、当前时间CTime、当前位置CLocation。其中用户个人信息主要包括：姓名、性别、年龄、工作情况、职称、工资水平、兴趣爱好。

计算distance(TLocation，CLocation)，若两地距离distance＞10km，则结合领域本体库，选择交通方式和住宿方式本体类。领域本体库中交通方式包括：火车、飞机、地铁、公交、出租车；住宿方式包括：酒店、宾馆、旅社。分别找到乘坐火车、飞机、地铁、公交、出租车的Web服务以及酒店、宾馆、旅社住宿的Web服务。

2、提取约束条件。

对于交通方式，包含的输入接口参数为：目标地点、乘车地点、票价、出发时间、到达时间、乘坐时间；包含的输出接口参数为：目标地点、到达时间。其中需要满足参数类型约束的参数为：目标地点、乘车地点、票价、出发时间、到达时间、乘坐时间；需要满足参数取值范围约束的参数为：票价、出发时间、到达时间、乘坐时间；需要满足参数语义相似度阈值约束的参数为：目标地点、乘车地点。

对于住宿方式，包含的输入接口参数为：住宿点名称、价格、地理位置、入住时间、退房时间、舒适度；包含的输出接口参数为：地理位置、退房时间。其中需要满足参数类型约束的参数为：住宿点名称、价格、地理位置、入住时间、退房时间；需要满足参数取值范围约束的参数为：价格、入住时间、退房时间；需要满足参数语义相似度阈值约束的参数为：地理位置。

对于用户的选择性偏好，根据用户的个人信息设置规则。首先根据用户属性设置一个或者多个属性值。可以把性别属性值拆分为：年龄属性值拆分为职业情况属性值拆分为职称属性值拆分为工资水平属性值拆分为其中n₁，n₂，n₃，n₄，n₅表示5个属性的属性值个数。设定规则表征用户选择性偏好决定目标原子服务的选择。Att₁，Att₂，.......，Att_n表示用户个人信息的属性，也是共性属性，表示属性Att_i的一个属性值，本例中兴趣爱好可以被看成个性，作为属性Att_n+1，这个属性只有一个值，规则变成表示对住宿方式和交通方式原子服务的选择。考虑到用户实际情况，属性组合是其中表示本例中实际的5个共性的属性值，Att₆表示个性的兴趣爱好。把实际的6个属性值、5种交通方式和3种住宿方式运用Apriori算法用来找到所有频繁项集，然后根据经验值设置支持度为75％，置信度为80％，进行关联规则分析，找到所有的偏好规则。得到的偏好规则中，预测交通方式选择不会选择拥挤颠簸的公交，住宿不会选择不够舒适的旅社。规则的右边可以选择的原子服务可以是Train、Airplane、Taxi、Subway、Grogshop、Guesthouse。这六条规则即是用户选择性偏好。

对于本体类之间的业务逻辑关系，Rel(t_i，t_j)表征t_i，t_j之间存在的逻辑关系，值为True表示t_i，t_j必须满足这种关系。根据领域本体库中的住宿方式和交通方式的类的关系和对象属性的关系，不能存在如下关系：Grogshop-Train，Grogshop-Airplane，Grogshop-Taxi，Grogshop-Subway，Guesthouse-Train，Guesthouse-Airplane，Guesthouse-Taxi，Guesthouse-Subway。

3、约束求解。

根据前一步中的得到的接口约束条件、用户选择性偏好规则以及业务逻辑关系约束条件，运用前文所述的编码规则对约束条件进行编码，然后代入Z3-str约束求解器中，得到可行解空间，解空间即为满足约束条件的所有可行解序列。

约束条件编码如下：

对于Web服务接口参数：

对于用户选择性别偏好：

对于业务逻辑关系：

(TrainID＜GrogshopID)∩(AirplaneID＜GrogshopID)(TaxiID＜GrogshopID)∩(SubwayID＜GrogshopID)∩(TrainID＜GuesthouseID)∩(AirplaneID＜GuesthouseID)∩(TaxiID＜GuesthouseID)∩(SubwayID＜GuesthouseID)。

对以上三大约束条件编码关系取交集，放入求解器中，运行后得到若干可行解序列。

对于行程安排分成四细粒度任务，前三个是交通方式、最后一个是住宿方式：表示为t₁-t₂-t₃-t₄，其中t₁，t₂，t₃都是Train，Airplane，Taxi，Subway中的一种，t₄是Grogshop，Guesthouse中的一种，则可行解序列有4*4*4*2＝128种，限于版面，这里不再一一列出。

4、对可行解序列进行可满足性检测。

利用Protégé和描述逻辑，结合领域知识本体库的底层知识，对可行解序列进行可满足性检测。具体实施为：领域知识本体库作为逻辑推理的基础知识，把领域本体文件作为输入加入到Protégé中，把可行解序列作为待检测的目标，借助于描述逻辑提供的可判定的推理服务和推理机Racer，基于领域本体知识库之间类与类、属性和属性、类和属性之间的关系，推理出所有存在的矛盾的关系，只要一个可行解序列中存在一个矛盾的关系，则去除这一个可行解序列。最终得到一个或多个经严格验证的可行解序列，即为合理有效的Web服务组合。

最终得到的可行解序列有16种，具体如下：

Taxi-Train-Taxi-Grogshop，Taxi-Train-Subway-Grogshop，Taxi-Train-Taxi-Guesthouse，Taxi-Train-Subway-Guesthouse，Taxi-Airplane-Taxi-Grogshop，Taxi-Airplane-Subway-Grogshop，Taxi-Airplane-Taxi-Guesthouse，Taxi-Airplane-Subway-Guesthouse，Subway-Train-Taxi-Grogshop，Subway-Train-Subway-Grogshop，Subway-Train-Taxi-Guesthouse，Subway-Train-Subway-Guesthouse，Subway-Airplane-Taxi-Grogshop，Subway-Airplane-Subway-Grogshop，Subway-Airplane-Taxi-Guesthouse，Subway-Airplane-Subway-Guesthouse。

可见，本发明能够得到高效、合理的组合Web服务。