形式語言與自動機：第11講-服務組合1

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

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

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

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

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

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

7、 計算DPDL公式的模型確定型命題動態(tài)邏輯DPDL建模所有服務的初始狀態(tài)目標服務n個組件服務領域無關的條件這些DPPL公式的大小關于目標服務或組件服務的大小是多項式的 目標服務確定型命題動態(tài)邏輯DPPL建模狀態(tài)是兩兩不相同的刻畫狀態(tài)轉(zhuǎn)移在狀態(tài)s上不能執(zhí)行動作a終止狀態(tài) 組件服務確定型命題動態(tài)邏輯DPPL建模狀態(tài)是兩兩不相同的刻畫狀態(tài)轉(zhuǎn)移當動作a要被執(zhí)行，而服務Si不能執(zhí)行a終止狀態(tài)如果Si執(zhí)行a則到新狀態(tài)s, 否則狀態(tài)保持不變 其他條件確定型命題動態(tài)邏輯DPPL建模 初始狀態(tài)對于動作a，至少有一個服務執(zhí)行a當目標服務到達終止狀態(tài)時，所有組件服務都到達終止狀態(tài)目標服務和所有組件服務都處于初始狀態(tài)

8、 目標服務例子 組件服務s10s11s20s21抽取FSA極小化FSADFA 把服務的一個功能建模為自動機的一個動作 未考慮 服務之間的消息交互服務功能實現(xiàn)的條件 Summary點擊聽取音樂音樂名稱找到音樂音樂名稱音樂名稱音樂不存在點擊聽取音樂找到音樂（2）Guarded 自動機41StoreWare-HouseBank服務組合場景Client(human or machine)服務之間的消息傳輸每個服務都有本地數(shù)據(jù)庫每個服務有內(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)三類動作：原子流程輸出消息輸入消息對輸入消息的參數(shù)值和本地存儲的數(shù)值定義了條件付款方式卡號地址價格原子流程（atomic process）September 1, 2005Automatic Composition of Semantic Web Services, VLDB 200544組合

11、模式一：Choreography Synthesis S = ( C , F = S1,Sn , L )客戶（client）：發(fā)送、接收消息服務集合連接通道(Linkage):服務之間消息傳輸?shù)耐ǖ繡S1S3S2服務通過原子流程對數(shù)據(jù)庫進行查詢與修改客戶、服務之間的消息傳輸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目標服務兩類動作： 與client之間的消息交互 原子流程(委托給服務完成)組件服務：銀行、商店組件服務：倉庫SW組

16、件服務：倉庫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動作： 與client和服務的消息交互三、交替自動機（Finite Alternating automata） 一個提供到奧蘭多迪斯尼樂園游玩的旅游預定 機票 旅館 迪斯尼門票或有折扣的出租車預訂例： 旅游代理自動機模型交替自動機模型邏輯與邏輯或確定/非確定自動無法刻畫并發(fā) A=( , S, s0, , F) : 非空有限輸入字符表 S：非空有限狀態(tài)集合 ：S B+(S)，其中，B+(S)是S上一個布爾公式的集合 F

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

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

20、成功預訂 X2=1: 旅館成功預訂 Y1=1: 門票成功預訂 Y2=1: 出租車成功預訂 基于AFA的服務組合模型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)的組合方法服務 給定一個目標服務和一個服務集合，是否存在一個協(xié)調(diào)者，使得協(xié)調(diào)者與目標服務有相同的輸出？組合問題與主要結(jié)果80例：迪斯尼樂園旅行安排旅游代理提供兩種迪斯尼樂園旅行的預訂方式self-booking：用戶分別預定機票、旅館和參加的活動cruise：用戶直接預定旅游套餐用戶希望預訂到最便宜的旅行安排starts

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

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

24、京旅行時間: 8.22-8. 24, 2010機票張數(shù): 2自由活動時間: 8.23, 10:00- 14:00 8.23, 16:00-20:00自由活動 : val: flight用于存儲聚合值本地數(shù)據(jù)庫業(yè)務對象模板83業(yè)務對象模板 RA上的組合服務模板定義為M=(Q,q0)Q 是有限狀態(tài)集合；q0 是初始狀態(tài)； 是狀態(tài)變遷規(guī)則集合； 是聚合規(guī)則集合。組合服務模板組合服務模板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服務庫實現(xiàn)初始輸入業(yè)務對象自頂向下控制組合服務的執(zhí)行，生成執(zhí)行樹自底向上生成聚合值84狀態(tài)變遷規(guī)則(t)=trueqq1q2qk.業(yè)務對象t服務庫業(yè)務對象 t1業(yè)務對象t2業(yè)務對象tk.組件服務模板后繼狀態(tài)前提條件：定義在業(yè)務對象模板RA上的多項式時間可計算的謂詞 組合服務模板根據(jù)狀態(tài)變遷規(guī)則和初始輸入業(yè)務對象生成一棵執(zhí)行樹85hotel出發(fā)城市: 北京旅行時間: 8. 22-8. 24, 2010機票張數(shù): 2自由活動時間:8. 23, 10:00- 14:00自由活動: val: 旅館總價格 狀態(tài)變遷規(guī)則(續(xù))出發(fā)城市:北京旅行時間: 8

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

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

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