形式語言與自動機(jī)-2014-第11講-服務(wù)組合1

1、胡春明、趙永望、鄧婷u Web服務(wù)簡介p 面向服務(wù)的體系結(jié)構(gòu)（Service-oriented Architecture）p Web服務(wù)組合方法u基于自動機(jī)模型的服務(wù)組合p 有限自動機(jī)p guarded 有限自動機(jī)p 交替自動機(jī)u 早在1996年，Gartner就首次提出了SOA（Service-Oriented Architecture，即面向服務(wù)的架構(gòu)）的概念，并預(yù)言SOA將成為下一代軟件的革命性技術(shù) u但因?yàn)楫?dāng)時缺乏實(shí)現(xiàn)SOA的技術(shù)基礎(chǔ)，SOA并沒有立即引起企業(yè)用戶和IT公司的重視 u直到后來XML、SOAP、WSDL、UDDI等Web服務(wù)標(biāo)準(zhǔn)逐漸成熟，SOA才真正成長為可部署的技術(shù)、產(chǎn)

2、品和下一代應(yīng)用系統(tǒng)的方法論，開始被業(yè)界廣泛接受，進(jìn)入了部署期 u 2000年，Web服務(wù)標(biāo)準(zhǔn)出臺，推動SOA實(shí)踐p軟件即服務(wù)，跨Internet的互操作7u互聯(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)圖書出入庫管理子系統(tǒng)圖書入庫管理模塊圖書出庫管理模塊讀者借閱管理子系統(tǒng)圖書借出歸還管理模塊圖書預(yù)訂管理模塊圖書超期/損毀/遺失管理模塊圖書類庫存類入庫類權(quán)限類出庫類借書類還書類預(yù)訂類超期類損毀類遺失類通知類u 有限狀態(tài)自動機(jī)(finite state automata)p 確定型有限狀態(tài)機(jī)p 非確定有限自動機(jī)u

3、Web服務(wù)組合中的自動機(jī)模型u 有限自動機(jī)u Guarded 自動機(jī)u 交替自動機(jī)（Alternating automata）u Web服務(wù)簡介p 面向服務(wù)的體系結(jié)構(gòu)（Service-oriented Architecture）p Web服務(wù)組合方法u 基于自動機(jī)模型的服務(wù)組合u有限自動機(jī)u Guarded automatau 交替自動機(jī)（Alternating automatainitsearchlistencartbuybuyinitsearchcartsearchMusic storelistencartsearchsearch用戶音樂網(wǎng)站27search“UDDI+”: Availab

4、le servicesinitsearchsearchWeb storecartlistenJukebuyBankinitsearchlistencartbuybuyinitsearchcartsearchMusic store (front-end)listencartsearchsearchDesiredServiceJuly 13, 2005Web Services Composition28initsearchlistencartbuy能否由下面的原子服務(wù)生成所需的功能？initsearchsearchWeb storecartlistenJukebuyBanksearch?buyin

5、itsearchcartsearchDelegatorfor music storelistencartWebWebWebJukeWebBanksearchsearchWebWebWebu 服務(wù)：有限狀態(tài)機(jī) ( finite state machine)在線音樂服務(wù)強(qiáng)調(diào)動作序列每次運(yùn)行是一個序列u 服務(wù)：有限狀態(tài)機(jī) ( finite state machine)目標(biāo)服務(wù)：服務(wù)1：目標(biāo)服務(wù)S0能否由服務(wù)1與服務(wù)2組合？ (1) S0的執(zhí)行樹上的每個動作都可以分配給S1或S2的一個動作完成； (2) S0的執(zhí)行樹上的動作序列對應(yīng)到S1或S2的動作執(zhí)行序列的交錯連接服務(wù)2：轉(zhuǎn)化為確定型命題動態(tài)邏輯公

6、式的可滿足性問題u 給定一個目標(biāo)服務(wù)G和一個服務(wù)集合Sp 是否存在S中的服務(wù)能組合成G？p 如果存在一個組合，是否可以由有限自動機(jī)表示？p 如果存在，如何找到這個組合？u 把組合問題轉(zhuǎn)化為命題動態(tài)邏輯（DPPL）的可滿足性問題p DPDL的可滿足性問題（EXPTIME-complete）p 可以：DPDL的小模型性質(zhì)p 計算DPDL公式的模型所有服務(wù)的初始狀態(tài)目標(biāo)服務(wù)n個組件服務(wù)領(lǐng)域無關(guān)的條件這些DPPL公式的大小關(guān)于目標(biāo)服務(wù)或組件服務(wù)的大小是多項(xiàng)式的u 目標(biāo)服務(wù)狀態(tài)是兩兩不相同的刻畫狀態(tài)轉(zhuǎn)移在狀態(tài)s上不能執(zhí)行動作a終止?fàn)顟B(tài)u 組件服務(wù)狀態(tài)是兩兩不相同的刻畫狀態(tài)轉(zhuǎn)移當(dāng)動作a要被執(zhí)行，而服務(wù)Si

7、不能執(zhí)行a終止?fàn)顟B(tài)如果Si執(zhí)行a則到新狀態(tài)s, 否則狀態(tài)保持不變u 其他條件u 初始狀態(tài)對于動作a，至少有一個服務(wù)執(zhí)行a當(dāng)目標(biāo)服務(wù)到達(dá)終止?fàn)顟B(tài)時，所有組件服務(wù)都到達(dá)終止?fàn)顟B(tài)目標(biāo)服務(wù)和所有組件服務(wù)都處于初始狀態(tài)u 目標(biāo)服務(wù)u 組件服務(wù)s10s11s20s21抽取FSA極小化FSADFAu 把服務(wù)的一個功能建模為自動機(jī)的一個動作u 未考慮p 服務(wù)之間的消息交互p服務(wù)功能實(shí)現(xiàn)的條件 點(diǎn)擊聽取音樂音樂名稱找到音樂音樂名稱音樂名稱音樂不存在點(diǎn)擊聽取音樂找到音樂41StoreWare-HouseBankClient(human or machine)服務(wù)之間的消息傳輸每個服務(wù)都有本地數(shù)據(jù)庫每個服務(wù)有內(nèi)部流

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. 輸入消息對輸入消息的參數(shù)值和本地存儲的數(shù)值定義了條件付款方式卡號地址價格September 1, 2005Automat

10、ic Composition of Semantic Web Services, VLDB 200544S = ( C , F = S1,Sn , L )客戶（client）：發(fā)送、接收消息服務(wù)集合連接通道(Linkage):服務(wù)之間消息傳輸?shù)耐ǖ繡S1S3S2服務(wù)通過原子流程對數(shù)據(jù)庫進(jìn)行查詢與修改客戶、服務(wù)之間的消息傳輸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之間的消息交互 原子流程(委托給服務(wù)完成)組件服務(wù)：銀行、商

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

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

18、狀態(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)=1NFA A (k個狀態(tài))DFA A (2k 個狀態(tài))AFA A (k個狀態(tài))NFA A (2k個狀態(tài))DFA A (22k 個狀態(tài))u DFA, NFA 與 AFA 接受的語言都為正則語言u 一個提供到奧蘭多迪斯尼樂園游玩的旅游預(yù)定p 機(jī)票p 旅館p 迪斯尼門票或有折扣的出租車預(yù)訂輸入消息：機(jī)票日期、入住天數(shù)、價格預(yù)算等輸入消息：旅游日期、租車時間段等自頂向下服務(wù)運(yùn)行自底向上生成服務(wù)運(yùn)行成果簡化： X1=1: 機(jī)票

19、成功預(yù)訂 X2=1: 旅館成功預(yù)訂 Y1=1: 門票成功預(yù)訂 Y2=1: 出租車成功預(yù)訂 guarded服務(wù)u 給定一個目標(biāo)服務(wù)和一個服務(wù)集合，是否存在一個協(xié)調(diào)者，使得協(xié)調(diào)者與目標(biāo)服務(wù)有相同的輸出？80n旅游代理提供兩種迪斯尼樂園旅行的預(yù)訂方式pself-booking：用戶分別預(yù)定機(jī)票、旅館和參加的活動pcruise：用戶直接預(yù)定旅游套餐n用戶希望預(yù)訂到最便宜的旅行安排startself-bookingcruisepackagelodgingreservinghotel activityflight服務(wù)庫出發(fā)城市:北京旅行時間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動時間:

20、8.23, 10:00- 14:00自由活動: 最便宜的旅行安排價格81u服務(wù)質(zhì)量感知的服務(wù)選擇與組合pQoS屬性定義、計算方式pQoS感知的服務(wù)選擇、組合算法問題p 考慮的QoS屬性主要是與系統(tǒng)相關(guān)的屬性，如服務(wù)響應(yīng)時間、可靠性、可用性、信任度與帶寬等p 最優(yōu)聚合問題考慮的是極大化（或極小化）用戶真正感興趣的值，如價格、效益等，而且這些值被服務(wù)作為其輸出消息中的參數(shù)p 最優(yōu)聚合問題的復(fù)雜度主要來源于數(shù)據(jù)流依賴關(guān)系，而服務(wù)質(zhì)量感知的服務(wù)組合不考慮數(shù)據(jù)流依賴。82出發(fā)城市: string旅行時間: date機(jī)票張數(shù): integer自由活動時間: list / free time slots自由

21、活動 list / activitiesval: Q Q / the domain of rational number服務(wù)的輸入/輸出可被服務(wù)更新出發(fā)城市: Beijing旅行時間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動時間: 8. 23, 10:00- 14:00 8. 23, 16:00-20:00自由活動: val: 機(jī)票總價格機(jī)票總價格出發(fā)城市: 北京旅行時間: 8.22-8. 24, 2010機(jī)票張數(shù): 2自由活動時間: 8.23, 10:00- 14:00 8.23, 16:00-20:00自由活動 : val: flight用于存儲聚合值本地數(shù)據(jù)庫業(yè)務(wù)對象模

22、板83n業(yè)務(wù)對象模板 RA上的組合服務(wù)模板定義為M=(Q,q0)pQ 是有限狀態(tài)集合；pq0 是初始狀態(tài)；p 是狀態(tài)變遷規(guī)則集合；p 是聚合規(guī)則集合。組合服務(wù)模板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服務(wù)庫實(shí)現(xiàn)實(shí)現(xiàn)初始輸入業(yè)務(wù)對象自頂向下控制組合服務(wù)的執(zhí)行，生成執(zhí)行樹自底向上生成聚合值84(t)=trueq21kq1q2qk.11( ):( , )( ,),.

23、,(,)kkqqqq業(yè)務(wù)對象t t服務(wù)庫業(yè)務(wù)對象 t t1 1業(yè)務(wù)對象t t2 2業(yè)務(wù)對象tk.組件服務(wù)模板后繼狀態(tài)前提條件：定義在業(yè)務(wù)對象模板RA上的多項(xiàng)式時間可計算的謂詞 組合服務(wù)模板根據(jù)狀態(tài)變遷規(guī)則和初始輸入業(yè)務(wù)對象生成一棵執(zhí)行樹85(,)(,),(,),(,)sffhhaaq trueqqqhotel出發(fā)城市: 北京旅行時間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動時間:8. 23, 10:00- 14:00自由活動: val: 旅館總價格旅館總價格出發(fā)城市:北京旅行時間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動時間:8.23, 10:00- 14:

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

25、 fqtrue qfqh終止?fàn)顟B(tài)(,)(,),(,) ( is .)aaaaridalqqqtT qa自由時間列表不為空a=false執(zhí)行樹停止生成新的節(jié)點(diǎn)執(zhí)行樹停止生成新的節(jié)點(diǎn) 碰到終止?fàn)顟B(tài)碰到終止?fàn)顟B(tài) 前提條件不滿足前提條件不滿足86q21kq1q2qk.1( ):val( )(val(),.,val()qkqqFqqval(q1)val(q2)val(qk)Fq (val(q1),.,val(qk)val(q)聚合函數(shù):多項(xiàng)式時間內(nèi)可計算的函數(shù)（ min, max, sum.)狀態(tài) q 對應(yīng)的聚合值87startself-bookingcruisepackagelodgingreserv

26、ingflighthotel activityqfqaqhqsval(qs) val(qf)+val(qh)+val(qa)qs出發(fā)城市: 北京旅行時間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動時間:8. 23, 10:00- 14:00自由活動: val: 旅館總價格旅館總價格出發(fā)城市: 北京旅行時間: 8.22-8.24, 2010機(jī)票張數(shù): 2自由活動時間: 8.23, 10:00- 14:00自由活動: val: 機(jī)票總價格機(jī)票總價格出發(fā)城市: 北京旅行時間: 8. 22-8. 24, 2010機(jī)票張數(shù): 2自由活動時間:8. 23, 10:00- 14:00自由活動: 潛水潛水val: 潛水總價格潛水總價格val( qs)val( qf)val( qa)val( qs)=機(jī)票總價格+旅館總價格+潛水總價格88u輸入p定義在業(yè)務(wù)對象模板RA上的組合服務(wù)模板Mp由RA 規(guī)范的業(yè)務(wù)對象 tp服務(wù)庫 Lp實(shí)現(xiàn)約束 對應(yīng)的決策問題:是否存在一個關(guān)于實(shí)現(xiàn)約束有效的實(shí)現(xiàn)使得 M(t) （ ）B 問題: 是否存在一個實(shí)現(xiàn)使得關(guān)于實(shí)現(xiàn)約束有效并能極小化（或極大化）輸出M(t)（聚合值）RA包含了所有服務(wù)的輸入/輸出參數(shù) ( ( ) )為可實(shí)現(xiàn)組件模板 的功能的服務(wù)集合89u組合服務(wù)模板M=(Q,