1、胡春明、赵永望、邓婷u Web服务简介p 面向服务的体系结构（Service-oriented Architecture）p Web服务组合方法u基于自动机模型的服务组合p 有限自动机p guarded 有限自动机p 交替自动机u 早在1996年，Gartner就首次提出了SOA（Service-Oriented Architecture，即面向服务的架构）的概念，并预言SOA将成为下一代软件的革命性技术 u但因为当时缺乏实现SOA的技术基础，SOA并没有立即引起企业用户和IT公司的重视 u直到后来XML、SOAP、WSDL、UDDI等Web服务标准逐渐成熟，SOA才真正成长为可部署的技术、产
2、品和下一代应用系统的方法论，开始被业界广泛接受，进入了部署期 u 2000年，Web服务标准出台，推动SOA实践p软件即服务，跨Internet的互操作7u互联网上存在丰富的软件（服务）资源大量公司提供了可调用的应用服务. .各大标准组织、公司提出Web服务标准与工业产品图书馆管理系统图书出入库管理子系统图书入库管理模块图书出库管理模块读者借阅管理子系统图书借出归还管理模块图书预订管理模块图书超期/损毁/遗失管理模块图书类库存类入库类权限类出库类借书类还书类预订类超期类损毁类遗失类通知类u 有限状态自动机(finite state automata)p 确定型有限状态机p 非确定有限自动机u
3、Web服务组合中的自动机模型u 有限自动机u Guarded 自动机u 交替自动机（Alternating automata）u Web服务简介p 面向服务的体系结构（Service-oriented Architecture）p Web服务组合方法u 基于自动机模型的服务组合u有限自动机u Guarded automatau 交替自动机（Alternating automatainitsearchlistencartbuybuyinitsearchcartsearchMusic storelistencartsearchsearch用户音乐网站27search“UDDI+”: Availab
4、le servicesinitsearchsearchWeb storecartlistenJukebuyBankinitsearchlistencartbuybuyinitsearchcartsearchMusic store (front-end)listencartsearchsearchDesiredServiceJuly 13, 2005Web Services Composition28initsearchlistencartbuy能否由下面的原子服务生成所需的功能？initsearchsearchWeb storecartlistenJukebuyBanksearch?buyin
5、itsearchcartsearchDelegatorfor music storelistencartWebWebWebJukeWebBanksearchsearchWebWebWebu 服务：有限状态机 ( finite state machine)在线音乐服务强调动作序列每次运行是一个序列u 服务：有限状态机 ( finite state machine)目标服务：服务1：目标服务S0能否由服务1与服务2组合？ (1) S0的执行树上的每个动作都可以分配给S1或S2的一个动作完成； (2) S0的执行树上的动作序列对应到S1或S2的动作执行序列的交错连接服务2：转化为确定型命题动态逻辑公
6、式的可满足性问题u 给定一个目标服务G和一个服务集合Sp 是否存在S中的服务能组合成G？p 如果存在一个组合，是否可以由有限自动机表示？p 如果存在，如何找到这个组合？u 把组合问题转化为命题动态逻辑（DPPL）的可满足性问题p DPDL的可满足性问题（EXPTIME-complete）p 可以：DPDL的小模型性质p 计算DPDL公式的模型所有服务的初始状态目标服务n个组件服务领域无关的条件这些DPPL公式的大小关于目标服务或组件服务的大小是多项式的u 目标服务状态是两两不相同的刻画状态转移在状态s上不能执行动作a终止状态u 组件服务状态是两两不相同的刻画状态转移当动作a要被执行，而服务Si
7、不能执行a终止状态如果Si执行a则到新状态s, 否则状态保持不变u 其他条件u 初始状态对于动作a，至少有一个服务执行a当目标服务到达终止状态时，所有组件服务都到达终止状态目标服务和所有组件服务都处于初始状态u 目标服务u 组件服务s10s11s20s21抽取FSA极小化FSADFAu 把服务的一个功能建模为自动机的一个动作u 未考虑p 服务之间的消息交互p服务功能实现的条件 点击听取音乐音乐名称找到音乐音乐名称音乐名称音乐不存在点击听取音乐找到音乐41StoreWare-HouseBankClient(human or machine)服务之间的消息传输每个服务都有本地数据库每个服务有内部流
8、程codeavailablewarehousepriceHP15TNGW5HS72FSW1042?requestOrder(payBy,cartNum,addr,price)(payBy = PREPAID) (price 10) charge(cartNum; paymentOK)(payBy = CC) (price 10) / !requestCCCheck(cartNum)?replyCCCheck( approved)? requestShipStatus(oid)checkShipStatus( oid; date,status)paymentOK = T / requestShi
9、p(wh,addr; oid,date,status)approved = F /! replyOrder(“fail”)paymentOK = F /! replyOrder(“fail”)! shipStatus(oid,date,status)approved = T /requestShip( wh,addr; oid,date,status)？：输入消息！：输出消息! shipStatus(oid,date,status)三类动作：1. 原子流程2. 输出消息3. 输入消息对输入消息的参数值和本地存储的数值定义了条件付款方式卡号地址价格September 1, 2005Automat
10、ic Composition of Semantic Web Services, VLDB 200544S = ( C , F = S1,Sn , L )客户（client）：发送、接收消息服务集合连接通道(Linkage):服务之间消息传输的通道CS1S3S2服务通过原子流程对数据库进行查询与修改客户、服务之间的消息传输September 1, 2005Automatic Composition of Semantic Web Services, VLDB 200545Each edge satisfies , and labeled by “trace”, which records gr
11、ound message sent/received or atomic process invokeduEssenceEssence of an execution tree: Project ontopAtomic process invocationspMessages from/to clientuIntuitively: the observables to client, external worldIntuitively: the observables to client, external worlduEquivalence of two systems:pIf essenc
12、es of execution trees are isomorphic. . . . . . . . . . . . . . .Each node labeled (id, I )S = ( C , F = S1,Sn , L )September 1, 2005Automatic Composition of Semantic Web Services, VLDB 200546? ? ?S14S8S2uSelect from UDDI, construct mediator and linkageuInteraction with C, and with “real world”, sho
13、uld copy GCCGS1S2S3. . .“UDDI”MSeptember 1, 2005Automatic Composition of Semantic Web Services, VLDB 200547uGoal system: S = ( C , G = G , L )p“Goal” G has atomic processes and messages to CuProblem: Given Goal system and UDDI directory,pSelect S1,Sn from UDDI pBuild mediator MpBuild linkage Lso tha
14、t ( C , S = M, S1,Sn , L ) is equivalent to the goal systemuThm: Can determine existence of (and build) a (p,q)-bounded mediator in doubly exptimepRestrict to “fully mediated” systems: Client communicates only with mediator; mediator has no atomic processes两类动作： 与client之间的消息交互 原子流程(委托给服务完成)组件服务：银行、商
15、店组件服务：仓库SW组件服务：仓库NGW(warehouse=NGW) (payBy=cc) (price10)!requestOrder(“cc”, cartNum, addr, price) to NGW52?requestPurchase(code, payBy)from client!requestCheckItem(code) to Storefrontavail = F ! responsePurchase(“fail”)to clientavail = T! responsePurchase(“provide cart number”)to client?msgCartNum_m
16、sgIN(cartNum)to client(warehouse=SW) (payBy=cc)!requestOrder(cartNum, addr, price) to SW动作： 与client和服务的消息交互三、交替自动机（Finite Alternating automata）u 一个提供到奥兰多迪斯尼乐园游玩的旅游预定p 机票p 旅馆p 迪斯尼门票或有折扣的出租车预订自动机模型交替自动机模型逻辑与逻辑或确定/非确定自动无法刻画并发u A=( , S, s0, , F)p : 非空有限输入字符表p S：非空有限状态集合p ：S B+(S)，其中，B+(S)是S上一个布尔公式的集合p F
17、: 非空终止状态集合(s, a)=(s1s2)(s3s4)非确定自动机：(s, a)=s1, s2 =s0ab确定自动机AabL(A) iff s2是终止状态s0s1s2ab非确定自动机AabL(A) iff s2或s4是终止状态as3s4bcs1s212ssccu A=( , S, s0, , F)p : 非空有限输入字符表p S：非空有限状态集合pS0: 初始状态p ：S B+(S)，其中，B+(S)是S上一个布尔公式的集合p F: 非空终止状态集合(s0, a)=(s1s2)(s3s4)u 交替自动机A在字符串a1a2an上的运行是一棵树s0s1s2aaA接受a当且仅当s1与s2都是终止
18、状态，或s3与s4都是终止状态s3as4a定义f(si)=1 如果 si是终止状态；否则f(si)=0自底向上判断：A接受a当且仅当 (f(s1)f(s2)(f(s3)f(s4)=1NFA A (k个状态)DFA A (2k 个状态)AFA A (k个状态)NFA A (2k个状态)DFA A (22k 个状态)u DFA, NFA 与 AFA 接受的语言都为正则语言u 一个提供到奥兰多迪斯尼乐园游玩的旅游预定p 机票p 旅馆p 迪斯尼门票或有折扣的出租车预订输入消息：机票日期、入住天数、价格预算等输入消息：旅游日期、租车时间段等自顶向下服务运行自底向上生成服务运行成果简化： X1=1: 机票
19、成功预订 X2=1: 旅馆成功预订 Y1=1: 门票成功预订 Y2=1: 出租车成功预订 guarded服务u 给定一个目标服务和一个服务集合，是否存在一个协调者，使得协调者与目标服务有相同的输出？80n旅游代理提供两种迪斯尼乐园旅行的预订方式pself-booking：用户分别预定机票、旅馆和参加的活动pcruise：用户直接预定旅游套餐n用户希望预订到最便宜的旅行安排startself-bookingcruisepackagelodgingreservinghotel activityflight服务库出发城市:北京旅行时间: 8. 22-8. 24, 2010机票张数: 2自由活动时间:
20、8.23, 10:00- 14:00自由活动: 最便宜的旅行安排价格81u服务质量感知的服务选择与组合pQoS属性定义、计算方式pQoS感知的服务选择、组合算法问题p 考虑的QoS属性主要是与系统相关的属性，如服务响应时间、可靠性、可用性、信任度与带宽等p 最优聚合问题考虑的是极大化（或极小化）用户真正感兴趣的值，如价格、效益等，而且这些值被服务作为其输出消息中的参数p 最优聚合问题的复杂度主要来源于数据流依赖关系，而服务质量感知的服务组合不考虑数据流依赖。82出发城市: string旅行时间: date机票张数: integer自由活动时间: list / free time slots自由
21、活动 list / activitiesval: Q Q / the domain of rational number服务的输入/输出可被服务更新出发城市: Beijing旅行时间: 8. 22-8. 24, 2010机票张数: 2自由活动时间: 8. 23, 10:00- 14:00 8. 23, 16:00-20:00自由活动: val: 机票总价格机票总价格出发城市: 北京旅行时间: 8.22-8. 24, 2010机票张数: 2自由活动时间: 8.23, 10:00- 14:00 8.23, 16:00-20:00自由活动 : val: flight用于存储聚合值本地数据库业务对象模
22、板83n业务对象模板 RA上的组合服务模板定义为M=(Q,q0)pQ 是有限状态集合；pq0 是初始状态；p 是状态变迁规则集合；p 是聚合规则集合。组合服务模板departure city: Beijingtravel dates: July 22-24, 2010number of tickets: 2TL: July 23, 10:00- 14:00 July 23, 16:00-20:00Al: val: 聚合值 valval服务库实现实现初始输入业务对象自顶向下控制组合服务的执行，生成执行树自底向上生成聚合值84(t)=trueq21kq1q2qk.11( ):( , )( ,),.
23、,(,)kkqqqq业务对象t t服务库业务对象 t t1 1业务对象t t2 2业务对象tk.组件服务模板后继状态前提条件：定义在业务对象模板RA上的多项式时间可计算的谓词 组合服务模板根据状态变迁规则和初始输入业务对象生成一棵执行树85(,)(,),(,),(,)sffhhaaq trueqqqhotel出发城市: 北京旅行时间: 8. 22-8. 24, 2010机票张数: 2自由活动时间:8. 23, 10:00- 14:00自由活动: val: 旅馆总价格旅馆总价格出发城市:北京旅行时间: 8. 22-8. 24, 2010机票张数: 2自由活动时间:8.23, 10:00- 14:
24、00自由活动: val: startself-bookingcruisepackagelodgingreservingflighthotel activityflightactivity服务库出发城市: 北京旅行时间: 8.22-8.24, 2010机票张数: 2自由活动时间: 8.23, 10:00- 14:00自由活动: val: 机票总价格机票总价格出发城市: 北京旅行时间: 8. 22-8. 24, 2010机票张数: 2自由活动时间:8. 23, 10:00- 14:00自由活动: 潜水val: 潜水总价格qshqfqafaqhqstrueqfqhqa(,). hqtrue (,).
25、 fqtrue qfqh终止状态(,)(,),(,) ( is .)aaaaridalqqqtT qa自由时间列表不为空a=false执行树停止生成新的节点执行树停止生成新的节点 碰到终止状态碰到终止状态 前提条件不满足前提条件不满足86q21kq1q2qk.1( ):val( )(val(),.,val()qkqqFqqval(q1)val(q2)val(qk)Fq (val(q1),.,val(qk)val(q)聚合函数:多项式时间内可计算的函数（ min, max, sum.)状态 q 对应的聚合值87startself-bookingcruisepackagelodgingreserv
26、ingflighthotel activityqfqaqhqsval(qs) val(qf)+val(qh)+val(qa)qs出发城市: 北京旅行时间: 8. 22-8. 24, 2010机票张数: 2自由活动时间:8. 23, 10:00- 14:00自由活动: val: 旅馆总价格旅馆总价格出发城市: 北京旅行时间: 8.22-8.24, 2010机票张数: 2自由活动时间: 8.23, 10:00- 14:00自由活动: val: 机票总价格机票总价格出发城市: 北京旅行时间: 8. 22-8. 24, 2010机票张数: 2自由活动时间:8. 23, 10:00- 14:00自由活动
27、: 潜水潜水val: 潜水总价格潜水总价格val( qs)val( qf)val( qa)val( qs)=机票总价格+旅馆总价格+潜水总价格88u输入p定义在业务对象模板RA上的组合服务模板Mp由RA 规范的业务对象 tp服务库 Lp实现约束 对应的决策问题:是否存在一个关于实现约束有效的实现使得 M(t) （ ）B 问题: 是否存在一个实现使得关于实现约束有效并能极小化（或极大化）输出M(t)（聚合值）RA包含了所有服务的输入/输出参数 ( ( ) )为可实现组件模板 的功能的服务集合89u组合服务模板M=(Q,q0)的状态变迁图为有向图GM=(Q, E), 其中(q, q1)是E中一条边
28、当且仅当q1是q的后继状态。 11( ):( , )( ,),.,(,)kkqqqqqq1q2qk.根据状态变迁图的结构分析最优聚合问题的复杂度90组合服务模板 MAGP(M, L,t )固定服务库L图结构有向非循环图结构树结构PSPACE-PSPACE-完全完全PSPACE-PSPACE-完全完全NP-NP-完全完全近似难近似难NP-NP-完全完全近似难近似难不可判定不可判定不可判定不可判定固定 M不可判定不可判定多项式时间多项式时间多项式时间多项式时间u Web服务简介p 面向服务的体系结构（Service-oriented Architecture）p Web服务组合方法u基于自动机模型
29、的服务组合p 有限自动机p guarded 有限自动机p 交替自动机正则语言The Endu 计算复杂度p图灵机（Turing machine）pPTIME、NP、PSPACE、EXPTIME、2EXPTIME . .Decision problemu 图灵机M 接收输入序列 x 当且仅当M 停止在终止状态u 图灵机M 在输入序列 x上的计算时间为M在x上直到达到停机状态的所进行的步骤u 时间复杂度函数u 多项式时间DTM（PTIME）p 若存在一个多项式p(n)，使得对任意的n，有 TM(n) p(n)u 多项式时间复杂度类语言P问题：存在一个多项式时间的算法解决该问题u 非确定型图灵机NP问题：猜测一个解，验证它是该问题的解可以在PTIME时 间内完成PNPP=NP?u PSPACE ： 多项式空间确定图灵机u NPSPACE：多项式空间非确定图灵机u EXPTIME：O(2p(n)时间的确定图灵机u NEXPTIME：O(2p(n)时间的非确定图灵机u EXPSPACE：O(2p(n)空间的确定图灵机u NEXPSPACE：O(2p(n)空间的非确定图灵机 PNPPSPACEEXPTIMENEXPTIMEEXPSPACE=NPSPACE=NEXPSPACEC类完全问题：C类问题中最难的问题
