形式語(yǔ)言與自動(dòng)機(jī)：第11講-服務(wù)組合1

1、形式語(yǔ)言與自動(dòng)機(jī)Formal Languages and Automata Theorey 在Web服務(wù)組合中的應(yīng)用 Web服務(wù)簡(jiǎn)介 面向服務(wù)的體系結(jié)構(gòu)（Service-oriented Architecture） Web服務(wù)組合方法基于自動(dòng)機(jī)模型的服務(wù)組合 有限自動(dòng)機(jī) guarded 有限自動(dòng)機(jī) 交替自動(dòng)機(jī)內(nèi)容提要 早在1996年，Gartner就首次提出了SOA（Service-Oriented Architecture，即面向服務(wù)的架構(gòu)）的概念，并預(yù)言SOA將成為下一代軟件的革命性技術(shù) 但因?yàn)楫?dāng)時(shí)缺乏實(shí)現(xiàn)SOA的技術(shù)基礎(chǔ)，SOA并沒(méi)有立即引起企業(yè)用戶(hù)和IT公司的重視 直到后來(lái)XML、SO

2、AP、WSDL、UDDI等Web服務(wù)標(biāo)準(zhǔn)逐漸成熟，SOA才真正成長(zhǎng)為可部署的技術(shù)、產(chǎn)品和下一代應(yīng)用系統(tǒng)的方法論，開(kāi)始被業(yè)界廣泛接受，進(jìn)入了部署期 面向服務(wù)的體系結(jié)構(gòu) 2000年，Web服務(wù)標(biāo)準(zhǔn)出臺(tái)，推動(dòng)SOA實(shí)踐軟件即服務(wù)，跨Internet的互操作面向服務(wù)的體系結(jié)構(gòu)SOAWeb服務(wù)的產(chǎn)生及發(fā)展Web服務(wù)協(xié)議棧7Web服務(wù)現(xiàn)狀互聯(lián)網(wǎng)上存在豐富的軟件（服務(wù)）資源大量公司提供了可調(diào)用的應(yīng)用服務(wù). .各大標(biāo)準(zhǔn)組織、公司提出Web服務(wù)標(biāo)準(zhǔn)與工業(yè)產(chǎn)品傳統(tǒng)軟件開(kāi)發(fā)：自頂向下圖書(shū)館管理系統(tǒng)圖書(shū)出入庫(kù)管理子系統(tǒng)圖書(shū)入庫(kù)管理模塊圖書(shū)出庫(kù)管理模塊讀者借閱管理子系統(tǒng)圖書(shū)借出歸還管理模塊圖書(shū)預(yù)訂管理模塊圖書(shū)超期/損毀

3、/遺失管理模塊圖書(shū)類(lèi)庫(kù)存類(lèi)入庫(kù)類(lèi)權(quán)限類(lèi)出庫(kù)類(lèi)借書(shū)類(lèi)還書(shū)類(lèi)預(yù)訂類(lèi)超期類(lèi)損毀類(lèi)遺失類(lèi)通知類(lèi) 有限狀態(tài)自動(dòng)機(jī)(finite state automata) 確定型有限狀態(tài)機(jī) 非確定有限自動(dòng)機(jī)Web服務(wù)組合中的自動(dòng)機(jī)模型 Web服務(wù)組合中的自動(dòng)機(jī)模型 有限自動(dòng)機(jī) Guarded 自動(dòng)機(jī) 交替自動(dòng)機(jī)（Alternating automata） Web服務(wù)簡(jiǎn)介 面向服務(wù)的體系結(jié)構(gòu)（Service-oriented Architecture） Web服務(wù)組合方法 基于自動(dòng)機(jī)模型的服務(wù)組合有限自動(dòng)機(jī) Guarded automata 交替自動(dòng)機(jī)（Alternating automata內(nèi)容提要（1）確定型自動(dòng)

4、機(jī)模型 initsearchlistencartbuybuyinitsearchcartsearchMusic storelistencartsearchsearch用戶(hù)音樂(lè)網(wǎng)站27search“UDDI+”: Available servicesinitsearchsearchWeb storecartlistenJukebuyBankinitsearchlistencartbuybuyinitsearchcartsearchMusic store (front-end)listencartsearchsearchDesiredServiceJuly 13, 2005Web Services

5、 Composition28A Roman Compositioninitsearchlistencartbuy能否由下面的原子服務(wù)生成所需的功能？initsearchsearchWeb storecartlistenJukebuyBanksearch?buyinitsearchcartsearchDelegatorfor music storelistencartWebWebWebJukeWebBanksearchsearchWebWebWeb 服務(wù)：有限狀態(tài)機(jī) ( finite state machine)Roman-模型在線(xiàn)音樂(lè)服務(wù)強(qiáng)調(diào)動(dòng)作序列每次運(yùn)行是一個(gè)序列 服務(wù)：有限狀態(tài)機(jī) ( f

6、inite state machine)Roman-模型目標(biāo)服務(wù)：服務(wù)1：目標(biāo)服務(wù)S0能否由服務(wù)1與服務(wù)2組合？ (1) S0的執(zhí)行樹(shù)上的每個(gè)動(dòng)作都可以分配給S1或S2的一個(gè)動(dòng)作完成； (2) S0的執(zhí)行樹(shù)上的動(dòng)作序列對(duì)應(yīng)到S1或S2的動(dòng)作執(zhí)行序列的交錯(cuò)連接服務(wù)2：轉(zhuǎn)化為確定型命題動(dòng)態(tài)邏輯公式的可滿(mǎn)足性問(wèn)題 給定一個(gè)目標(biāo)服務(wù)G和一個(gè)服務(wù)集合S 是否存在S中的服務(wù)能組合成G？ 如果存在一個(gè)組合，是否可以由有限自動(dòng)機(jī)表示？ 如果存在，如何找到這個(gè)組合？問(wèn)題 把組合問(wèn)題轉(zhuǎn)化為命題動(dòng)態(tài)邏輯（DPPL）的可滿(mǎn)足性問(wèn)題 DPDL的可滿(mǎn)足性問(wèn)題（EXPTIME-complete） 可以：DPDL的小模型性質(zhì)

7、 計(jì)算DPDL公式的模型確定型命題動(dòng)態(tài)邏輯DPDL建模所有服務(wù)的初始狀態(tài)目標(biāo)服務(wù)n個(gè)組件服務(wù)領(lǐng)域無(wú)關(guān)的條件這些DPPL公式的大小關(guān)于目標(biāo)服務(wù)或組件服務(wù)的大小是多項(xiàng)式的 目標(biāo)服務(wù)確定型命題動(dòng)態(tài)邏輯DPPL建模狀態(tài)是兩兩不相同的刻畫(huà)狀態(tài)轉(zhuǎn)移在狀態(tài)s上不能執(zhí)行動(dòng)作a終止?fàn)顟B(tài) 組件服務(wù)確定型命題動(dòng)態(tài)邏輯DPPL建模狀態(tài)是兩兩不相同的刻畫(huà)狀態(tài)轉(zhuǎn)移當(dāng)動(dòng)作a要被執(zhí)行，而服務(wù)Si不能執(zhí)行a終止?fàn)顟B(tài)如果Si執(zhí)行a則到新?tīng)顟B(tài)s, 否則狀態(tài)保持不變 其他條件確定型命題動(dòng)態(tài)邏輯DPPL建模 初始狀態(tài)對(duì)于動(dòng)作a，至少有一個(gè)服務(wù)執(zhí)行a當(dāng)目標(biāo)服務(wù)到達(dá)終止?fàn)顟B(tài)時(shí)，所有組件服務(wù)都到達(dá)終止?fàn)顟B(tài)目標(biāo)服務(wù)和所有組件服務(wù)都處于初始狀態(tài)

8、 目標(biāo)服務(wù)例子 組件服務(wù)s10s11s20s21抽取FSA極小化FSADFA 把服務(wù)的一個(gè)功能建模為自動(dòng)機(jī)的一個(gè)動(dòng)作 未考慮 服務(wù)之間的消息交互服務(wù)功能實(shí)現(xiàn)的條件 Summary點(diǎn)擊聽(tīng)取音樂(lè)音樂(lè)名稱(chēng)找到音樂(lè)音樂(lè)名稱(chēng)音樂(lè)名稱(chēng)音樂(lè)不存在點(diǎn)擊聽(tīng)取音樂(lè)找到音樂(lè)（2）Guarded 自動(dòng)機(jī)41StoreWare-HouseBank服務(wù)組合場(chǎng)景Client(human or machine)服務(wù)之間的消息傳輸每個(gè)服務(wù)都有本地?cái)?shù)據(jù)庫(kù)每個(gè)服務(wù)有內(nèi)部流程codeavailablewarehousepriceHP15TNGW5HS72FSW1042guarded automata?requestOrder(pay

9、By,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 / requestShip(wh,addr; oid,date,status)approved = F /! replyOrder(“fail”)paym

10、entOK = F /! replyOrder(“fail”)! shipStatus(oid,date,status)approved = T /requestShip( wh,addr; oid,date,status)？：輸入消息！：輸出消息! shipStatus(oid,date,status)三類(lèi)動(dòng)作：原子流程輸出消息輸入消息對(duì)輸入消息的參數(shù)值和本地存儲(chǔ)的數(shù)值定義了條件付款方式卡號(hào)地址價(jià)格原子流程（atomic process）September 1, 2005Automatic Composition of Semantic Web Services, VLDB 200544組合

11、模式一：Choreography Synthesis S = ( C , F = S1,Sn , L )客戶(hù)（client）：發(fā)送、接收消息服務(wù)集合連接通道(Linkage):服務(wù)之間消息傳輸?shù)耐ǖ繡S1S3S2服務(wù)通過(guò)原子流程對(duì)數(shù)據(jù)庫(kù)進(jìn)行查詢(xún)與修改客戶(hù)、服務(wù)之間的消息傳輸September 1, 2005Automatic Composition of Semantic Web Services, VLDB 200545Each edge satisfies , and labeled by “trace”, which records ground message sent/receive

12、d or atomic process invokedExecution Trees and EquivalenceEssence of an execution tree: Project ontoAtomic process invocationsMessages from/to clientIntuitively: the observables to client, external worldEquivalence of two systems:If essences of execution trees are isomorphic. . . . . . . . . . . . .

13、 . .Each node labeled (id, I )S = ( C , F = S1,Sn , L )September 1, 2005Automatic Composition of Semantic Web Services, VLDB 200546? ? ?S14S8S2Mediator-centric CompositionSelect from UDDI, construct mediator and linkageInteraction with C, and with “real world”, should copy GCCGS1S2S3. . .“UDDI”MSept

14、ember 1, 2005Automatic Composition of Semantic Web Services, VLDB 200547Composition Synthesis ResultGoal system: S = ( C , G = G , L )“Goal” G has atomic processes and messages to CProblem: Given Goal system and UDDI directory,Select S1,Sn from UDDI Build mediator MBuild linkage Lso that ( C , S = M

15、, S1,Sn , L ) is equivalent to the goal systemThm: Can determine existence of (and build) a (p,q)-bounded mediator in doubly exptimeRestrict to “fully mediated” systems: Client communicates only with mediator; mediator has no atomic processes目標(biāo)服務(wù)兩類(lèi)動(dòng)作： 與client之間的消息交互 原子流程(委托給服務(wù)完成)組件服務(wù)：銀行、商店組件服務(wù)：倉(cāng)庫(kù)SW組

16、件服務(wù)：倉(cāng)庫(kù)NGW(warehouse=NGW) (payBy=cc) (price10)!requestOrder(“cc”, cartNum, addr, price) to NGWMediator (部分)52?requestPurchase(code, payBy)from client!requestCheckItem(code) to Storefrontavail = F ! responsePurchase(“fail”)to clientavail = T! responsePurchase(“provide cart number”)to client?msgCartNum

17、_msgIN(cartNum)to client(warehouse=SW) (payBy=cc)!requestOrder(cartNum, addr, price) to SW動(dòng)作： 與client和服務(wù)的消息交互三、交替自動(dòng)機(jī)（Finite Alternating automata） 一個(gè)提供到奧蘭多迪斯尼樂(lè)園游玩的旅游預(yù)定 機(jī)票 旅館 迪斯尼門(mén)票或有折扣的出租車(chē)預(yù)訂例： 旅游代理自動(dòng)機(jī)模型交替自動(dòng)機(jī)模型邏輯與邏輯或確定/非確定自動(dòng)無(wú)法刻畫(huà)并發(fā) A=( , S, s0, , F) : 非空有限輸入字符表 S：非空有限狀態(tài)集合 ：S B+(S)，其中，B+(S)是S上一個(gè)布爾公式的集合 F

18、: 非空終止?fàn)顟B(tài)集合交替自動(dòng)機(jī)(s, a)=(s1s2)(s3s4)非確定自動(dòng)機(jī)：(s, a)=s1, s2 =s0ab確定自動(dòng)機(jī)AabL(A) iff s2是終止?fàn)顟B(tài)s0s1s2ab非確定自動(dòng)機(jī)AabL(A) iff s2或s4是終止?fàn)顟B(tài)as3s4bcs1s2cc A=( , S, s0, , F) : 非空有限輸入字符表 S：非空有限狀態(tài)集合S0: 初始狀態(tài) ：S B+(S)，其中，B+(S)是S上一個(gè)布爾公式的集合 F: 非空終止?fàn)顟B(tài)集合交替自動(dòng)機(jī)(s0, a)=(s1s2)(s3s4) 交替自動(dòng)機(jī)A在字符串a(chǎn)1a2an上的運(yùn)行是一棵樹(shù)s0s1s2aaA接受a當(dāng)且僅當(dāng)s1與s2都是終止?fàn)?/p>

19、態(tài)，或s3與s4都是終止?fàn)顟B(tài)s3as4a定義f(si)=1 如果 si是終止?fàn)顟B(tài)；否則f(si)=0自底向上判斷：A接受a當(dāng)且僅當(dāng) (f(s1)f(s2)(f(s3)f(s4)=1結(jié)論NFA A (k個(gè)狀態(tài))DFA A (2k 個(gè)狀態(tài))AFA A (k個(gè)狀態(tài))NFA A (2k個(gè)狀態(tài))DFA A (22k 個(gè)狀態(tài)) DFA, NFA 與 AFA 接受的語(yǔ)言都為正則語(yǔ)言組合場(chǎng)景 一個(gè)提供到奧蘭多迪斯尼樂(lè)園游玩的旅游預(yù)定 機(jī)票 旅館 迪斯尼門(mén)票或有折扣的出租車(chē)預(yù)訂輸入消息：機(jī)票日期、入住天數(shù)、價(jià)格預(yù)算等輸入消息：旅游日期、租車(chē)時(shí)間段等自頂向下服務(wù)運(yùn)行自底向上生成服務(wù)運(yùn)行成果簡(jiǎn)化： X1=1: 機(jī)票

20、成功預(yù)訂 X2=1: 旅館成功預(yù)訂 Y1=1: 門(mén)票成功預(yù)訂 Y2=1: 出租車(chē)成功預(yù)訂 基于AFA的服務(wù)組合模型guardedRun of synthesized web serviceRun of synthesized web serviceRun of synthesized web serviceRun of synthesized web serviceRun of synthesized web serviceRun of synthesized web serviceRun of synthesized web serviceRun of synthesized web ser

21、viceRun of synthesized web serviceRun of synthesized web serviceRun of synthesized web serviceRun of synthesized web service基于協(xié)調(diào)者(mediator)的組合方法服務(wù) 給定一個(gè)目標(biāo)服務(wù)和一個(gè)服務(wù)集合，是否存在一個(gè)協(xié)調(diào)者，使得協(xié)調(diào)者與目標(biāo)服務(wù)有相同的輸出？組合問(wèn)題與主要結(jié)果80例：迪斯尼樂(lè)園旅行安排旅游代理提供兩種迪斯尼樂(lè)園旅行的預(yù)訂方式self-booking：用戶(hù)分別預(yù)定機(jī)票、旅館和參加的活動(dòng)cruise：用戶(hù)直接預(yù)定旅游套餐用戶(hù)希望預(yù)訂到最便宜的旅行安排starts

22、elf-bookingcruisepackagelodgingreservinghotelactivityflight服務(wù)庫(kù)出發(fā)城市:北京旅行時(shí)間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間:8.23, 10:00- 14:00自由活動(dòng): 最便宜的旅行安排價(jià)格最優(yōu)聚合問(wèn)題81研究現(xiàn)狀及問(wèn)題服務(wù)質(zhì)量感知的服務(wù)選擇與組合QoS屬性定義、計(jì)算方式QoS感知的服務(wù)選擇、組合算法問(wèn)題考慮的QoS屬性主要是與系統(tǒng)相關(guān)的屬性，如服務(wù)響應(yīng)時(shí)間、可靠性、可用性、信任度與帶寬等最優(yōu)聚合問(wèn)題考慮的是極大化（或極小化）用戶(hù)真正感興趣的值，如價(jià)格、效益等，而且這些值被服務(wù)作為其輸出消息中的參數(shù)最優(yōu)聚

23、合問(wèn)題的復(fù)雜度主要來(lái)源于數(shù)據(jù)流依賴(lài)關(guān)系，而服務(wù)質(zhì)量感知的服務(wù)組合不考慮數(shù)據(jù)流依賴(lài)。82業(yè)務(wù)對(duì)象模板出發(fā)城市: string旅行時(shí)間: date機(jī)票張數(shù): integer自由活動(dòng)時(shí)間: list / free time slots自由活動(dòng) list / activitiesval: Q / the domain of rational number服務(wù)的輸入/輸出可被服務(wù)更新出發(fā)城市: Beijing旅行時(shí)間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間: 8. 23, 10:00- 14:00 8. 23, 16:00-20:00自由活動(dòng): val: 機(jī)票總價(jià)格出發(fā)城市: 北

24、京旅行時(shí)間: 8.22-8. 24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間: 8.23, 10:00- 14:00 8.23, 16:00-20:00自由活動(dòng) : val: flight用于存儲(chǔ)聚合值本地?cái)?shù)據(jù)庫(kù)業(yè)務(wù)對(duì)象模板83業(yè)務(wù)對(duì)象模板 RA上的組合服務(wù)模板定義為M=(Q,q0)Q 是有限狀態(tài)集合；q0 是初始狀態(tài)； 是狀態(tài)變遷規(guī)則集合； 是聚合規(guī)則集合。組合服務(wù)模板組合服務(wù)模板departure city: Beijingtravel dates: July 22-24, 2010number of tickets: 2TL: July 23, 10:00- 14:00 July 23, 1

25、6:00-20:00Al: val: 聚合值 val服務(wù)庫(kù)實(shí)現(xiàn)初始輸入業(yè)務(wù)對(duì)象自頂向下控制組合服務(wù)的執(zhí)行，生成執(zhí)行樹(shù)自底向上生成聚合值84狀態(tài)變遷規(guī)則(t)=trueqq1q2qk.業(yè)務(wù)對(duì)象t服務(wù)庫(kù)業(yè)務(wù)對(duì)象 t1業(yè)務(wù)對(duì)象t2業(yè)務(wù)對(duì)象tk.組件服務(wù)模板后繼狀態(tài)前提條件：定義在業(yè)務(wù)對(duì)象模板RA上的多項(xiàng)式時(shí)間可計(jì)算的謂詞 組合服務(wù)模板根據(jù)狀態(tài)變遷規(guī)則和初始輸入業(yè)務(wù)對(duì)象生成一棵執(zhí)行樹(shù)85hotel出發(fā)城市: 北京旅行時(shí)間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間:8. 23, 10:00- 14:00自由活動(dòng): val: 旅館總價(jià)格 狀態(tài)變遷規(guī)則(續(xù))出發(fā)城市:北京旅行時(shí)間: 8

26、. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間:8.23, 10:00- 14:00自由活動(dòng): val: startself-bookingcruisepackagelodgingreservingflighthotelactivityflightactivity服務(wù)庫(kù)出發(fā)城市: 北京旅行時(shí)間: 8.22-8.24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間: 8.23, 10:00- 14:00自由活動(dòng): val: 機(jī)票總價(jià)格出發(fā)城市: 北京旅行時(shí)間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間:8. 23, 10:00- 14:00自由活動(dòng): 潛水val: 潛水總價(jià)

27、格qsqfqaqhqstrueqfqhqaqfqh終止?fàn)顟B(tài)qa自由時(shí)間列表不為空a=false執(zhí)行樹(shù)停止生成新的節(jié)點(diǎn)碰到終止?fàn)顟B(tài)前提條件不滿(mǎn)足86聚合規(guī)則qq1q2qk.val(q1)val(q2)val(qk)Fq (val(q1),.,val(qk)val(q)聚合函數(shù):多項(xiàng)式時(shí)間內(nèi)可計(jì)算的函數(shù)（ min, max, sum.)狀態(tài) q 對(duì)應(yīng)的聚合值87聚合規(guī)則（續(xù)）startself-bookingcruisepackagelodgingreservingflighthotelactivityqfqaqhqsval(qs) val(qf)+val(qh)+val(qa)qs出發(fā)城市: 北

28、京旅行時(shí)間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間:8. 23, 10:00- 14:00自由活動(dòng): val: 旅館總價(jià)格出發(fā)城市: 北京旅行時(shí)間: 8.22-8.24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間: 8.23, 10:00- 14:00自由活動(dòng): val: 機(jī)票總價(jià)格出發(fā)城市: 北京旅行時(shí)間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動(dòng)時(shí)間:8. 23, 10:00- 14:00自由活動(dòng): 潛水val: 潛水總價(jià)格val( qs)val( qf)val( qa)val( qs)=機(jī)票總價(jià)格+旅館總價(jià)格+潛水總價(jià)格88最優(yōu)聚合問(wèn)題:AGP(M, L, t):輸入定義在業(yè)務(wù)對(duì)象模板RA上的組合服務(wù)模板M由RA 規(guī)范的業(yè)務(wù)對(duì)象 t服務(wù)庫(kù) L實(shí)現(xiàn)約束 對(duì)應(yīng)的決策問(wèn)題:是否存在一個(gè)