張元鳴,葉成龍,黃浪游,陸佳煒,徐 俊,肖 剛

1(浙江工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,杭州 310023) 2(浙江工業(yè)大學(xué) 機械工程博士后流動站,杭州 310023)

1 引 言

隨著服務(wù)計算技術(shù)的快速發(fā)展,不僅軟件以服務(wù)的方式被發(fā)布在互聯(lián)網(wǎng)上,稱為Web服務(wù),而且數(shù)據(jù)也以服務(wù)的方式發(fā)布在互聯(lián)網(wǎng)上,稱為數(shù)據(jù)服務(wù)(Data Service,DS)[1,2].數(shù)據(jù)服務(wù)通過一組數(shù)據(jù)資源訪問接口,屏蔽了底層數(shù)據(jù)多源、異構(gòu)等特征,為數(shù)據(jù)集成和數(shù)據(jù)共享提供了一種統(tǒng)一的數(shù)據(jù)模型.通過組合已發(fā)布的數(shù)據(jù)服務(wù),可以有效滿足跨域業(yè)務(wù)處理系統(tǒng)的處理需求和數(shù)據(jù)分析需求.

然而,如何快速自動組合數(shù)據(jù)服務(wù)并生成數(shù)據(jù)視圖是數(shù)據(jù)服務(wù)需要解決的一個挑戰(zhàn)性問題.與Web服務(wù)組合問題不同的是,數(shù)據(jù)服務(wù)間不存在接口依賴關(guān)系,不能根據(jù)接口關(guān)系生成數(shù)據(jù)視圖,現(xiàn)有的數(shù)據(jù)服務(wù)組合方法與工具,如Aqualogic[3]、Damia[4]、Iviewer[5]等,為用戶提供了可視化的方式來自定義數(shù)據(jù)服務(wù)組合,由用戶根據(jù)需求手動地生成數(shù)據(jù)視圖.然而,當(dāng)數(shù)據(jù)服務(wù)的數(shù)量超過一定規(guī)模時,數(shù)據(jù)服務(wù)之間的關(guān)系也變得非常復(fù)雜,用戶將難以高效地選擇數(shù)據(jù)服務(wù),這給組合出用戶需要的數(shù)據(jù)視圖帶來很大挑戰(zhàn).

針對該問題,本文提出一種數(shù)據(jù)服務(wù)依賴圖模型,并在該模型基礎(chǔ)上實現(xiàn)了數(shù)據(jù)服務(wù)的自動組合.該方法根據(jù)內(nèi)在的數(shù)據(jù)依賴關(guān)系,將數(shù)據(jù)服務(wù)組織為能夠描述全局邏輯結(jié)構(gòu)的數(shù)據(jù)服務(wù)依賴圖,將數(shù)據(jù)組合問題建模為基于依賴圖模型的數(shù)據(jù)服務(wù)搜索問題:以用戶數(shù)據(jù)需求為輸入,根據(jù)需求約束,在依賴圖上搜索能夠滿足需求的數(shù)據(jù)服務(wù)依賴子圖,然后執(zhí)行組合后的復(fù)合數(shù)據(jù)服務(wù)生成可視化數(shù)據(jù)視圖.

2 相關(guān)研究

BEA公司最早在2005年提出以服務(wù)的形式封裝數(shù)據(jù)并提供各種數(shù)據(jù)服務(wù)給用戶或系統(tǒng)[6],它以類似于Web服務(wù)的形式,將數(shù)據(jù)資源作為一種軟件服務(wù),通過其所提供的接口進(jìn)行訪問,并輸出一個確定數(shù)據(jù)模式結(jié)果的數(shù)據(jù)集.數(shù)據(jù)服務(wù)為數(shù)據(jù)集成和共享提供了一種新的有效手段,是當(dāng)前服務(wù)計算領(lǐng)域研究的一個熱點.

在數(shù)據(jù)服務(wù)的封裝、訪問和應(yīng)用方面,蔡海尼等[6]驗證了數(shù)據(jù)服務(wù)不僅能夠直接訪問數(shù)據(jù)源,并且能通過標(biāo)準(zhǔn)的接口集成到SOA中,不需要依賴已有應(yīng)用程序,能夠訪問跨平臺的數(shù)據(jù)資源,彌補了傳統(tǒng)SOA在數(shù)據(jù)訪問中的缺陷與不足;Liu等[7]為現(xiàn)代企業(yè)信息系統(tǒng)設(shè)計了數(shù)據(jù)服務(wù)架構(gòu),用來解決數(shù)據(jù)的語義集成和數(shù)據(jù)服務(wù)的適應(yīng)性,使各種企業(yè)信息系統(tǒng)能獲取和共享數(shù)據(jù);謝興生等[8]提出了一種基于數(shù)據(jù)服務(wù)匹配的數(shù)據(jù)集成方法,該方法主要基于數(shù)據(jù)服務(wù)發(fā)布、注冊和檢索的方式,利用數(shù)據(jù)形式語義進(jìn)行數(shù)據(jù)集成,并增強與語義Web和描述邏輯推理等智能技術(shù)的融合,具有良好的性能和可伸縮性;謝軍等[9]提出一種基于虛擬視圖的多源數(shù)據(jù)集成方法,該方法利用分類包裝器對底層物理數(shù)據(jù)進(jìn)行包裝和轉(zhuǎn)換,統(tǒng)一異構(gòu)數(shù)據(jù)源訪問接口,把底層的數(shù)據(jù)轉(zhuǎn)換為統(tǒng)一的數(shù)據(jù)模型,有效地實現(xiàn)了多源異構(gòu)數(shù)據(jù)的集成;王桂玲等[10]提出了基于云計算的流數(shù)據(jù)集成與服務(wù),歸納了大規(guī)模流數(shù)據(jù)的集成與服務(wù)研究面臨的挑戰(zhàn),探討了云計算環(huán)境下求解相關(guān)問題的思路;Zorrilla M等[11]描述了基于SaaS的數(shù)據(jù)挖掘服務(wù)架構(gòu),它遵循面向服務(wù)的架構(gòu)設(shè)計,可與其他數(shù)據(jù)挖掘算法和可視化工具非常容易地集成,為沒有數(shù)據(jù)挖掘知識的用戶提供服務(wù).

在數(shù)據(jù)服務(wù)組合和數(shù)據(jù)視圖生成方面,溫彥等[5]提出了跨組織業(yè)務(wù)數(shù)據(jù)視圖的動態(tài)生成方法iViewer,通過可視化和易用的數(shù)據(jù)服務(wù)組合操作來動態(tài)構(gòu)建數(shù)據(jù)視圖;Gu等[12]提出了服務(wù)數(shù)據(jù)鏈接模型,描述數(shù)據(jù)服務(wù)的輸入和輸出屬性之間的數(shù)據(jù)映射,并實現(xiàn)了數(shù)據(jù)驅(qū)動在自動服務(wù)組合領(lǐng)域的應(yīng)用;Amdouni等[13]提出了一種用于對不確定數(shù)據(jù)服務(wù)建模的概率方法,計算組合輸出概率的組合代數(shù),并提出了一種算法來找到組合的正確執(zhí)行計劃;Chen等[14]開發(fā)了一種名為HS3的新穎的分布式認(rèn)證代碼,針對多維數(shù)據(jù)的各種查詢認(rèn)證方案,確保集成數(shù)據(jù)的完整性和查詢結(jié)果的正確性;Abdelhamid等[17]對非確定語義描述的數(shù)據(jù)服務(wù)組合問題進(jìn)行了研究,通過“可能性”將非確定的語義描述進(jìn)行了量化,并在組合過程中考慮可能的組合方案;Zhou等[18]提出了擴展的IOPE模型,能夠基于本體描述語言O(shè)WL-S對數(shù)據(jù)服務(wù)進(jìn)行語義描述和建模,為數(shù)據(jù)服務(wù)自動組合提供了語義信息.

在數(shù)據(jù)服務(wù)視圖更新及優(yōu)化方面,張鵬等[15]提出了一種基于數(shù)據(jù)服務(wù)的嵌套視圖動態(tài)更新方法,利用指針為嵌套視圖中的元組建立嵌套任意層次的數(shù)據(jù)服務(wù)的引用,同時給出了一種記錄數(shù)據(jù)服務(wù)更新的日志以及在該日志上的嵌套視圖增量更新算法,提高了嵌套視圖的數(shù)據(jù)新鮮度;此外,該課題組還對數(shù)據(jù)組合視圖的優(yōu)化更新方法進(jìn)行了研究,通過數(shù)據(jù)緩存的方法減少數(shù)據(jù)視圖更新的時間[16].

分析現(xiàn)有的關(guān)于數(shù)據(jù)服務(wù)組合的研究可知,還沒有給出有效的數(shù)據(jù)服務(wù)自動組合方法.例如,文獻(xiàn)[5]提出的基于嵌套視圖的組合方法屬于手動的組合方法,難以適應(yīng)數(shù)據(jù)服務(wù)數(shù)量較大的情況;文獻(xiàn)[12]提出的基于輸入輸出依賴關(guān)系的數(shù)據(jù)服務(wù)組合方法借鑒了傳統(tǒng)的Web服務(wù)組合方法,無法利用數(shù)據(jù)服務(wù)自身的特征對組合進(jìn)行建模;文獻(xiàn)[17]給出了數(shù)據(jù)服務(wù)的語義描述方法,還沒有具體的組合算法;文獻(xiàn)[18]僅對數(shù)據(jù)服務(wù)的模糊語義進(jìn)行了建模,也沒有提出可行的自動組合方法.與以上這些方法相比,本文將數(shù)據(jù)服務(wù)組合問題建模為基于依賴圖模型的數(shù)據(jù)服務(wù)搜索問題,實現(xiàn)了數(shù)據(jù)服務(wù)的自動組合:以用戶數(shù)據(jù)需求為輸入,根據(jù)需求約束,在依賴圖上搜索能夠滿足需求的數(shù)據(jù)依賴子圖,然后執(zhí)行組合后的復(fù)合數(shù)據(jù)服務(wù)生成可視化數(shù)據(jù)視圖,實現(xiàn)了數(shù)據(jù)服務(wù)的自動化組合和視圖生成.

3 數(shù)據(jù)服務(wù)依賴圖模型

本節(jié)先給出數(shù)據(jù)依賴、數(shù)據(jù)依賴圖、原子數(shù)據(jù)服務(wù)的基本概念,并說明這些基本概念之間的關(guān)系.

3.1 基本概念

屬性是客觀事物特征或性質(zhì)的抽象描述,數(shù)據(jù)則是屬性的具體取值,而數(shù)據(jù)依賴則是客觀事物屬性間取值的約束關(guān)系.借鑒關(guān)系數(shù)據(jù)模型中的函數(shù)依賴和連接依賴的相關(guān)概念,對數(shù)據(jù)服務(wù)之間的關(guān)系進(jìn)行建模.

定義1.(函數(shù)依賴)設(shè)X,Y是關(guān)系模式R(U)的兩個屬性集合,當(dāng)R的任意關(guān)系的任意兩個元組的X值相同時,則它們的Y值也相同,則稱Y函數(shù)依賴于X,記為X→Y.

根據(jù)函數(shù)依賴的定義,可以推導(dǎo)出完全函數(shù)依賴、部分函數(shù)依賴、相互函數(shù)依賴,定義如下:

推論3.如果X→Y且Y→X,則X與Y之間為相互函數(shù)依賴,記為X?Y.

表1 電梯企業(yè)信息系統(tǒng)數(shù)據(jù)集
Table 1 Data set of elevator enterprise information system

來源部門關(guān)系模式名稱屬性集設(shè)計部門電梯基本信息a；b；c；d；電梯客戶信息e；f；g；h；電梯訂單信息a；e；i；j；維修部門電梯基本信息k；l；m；n；電梯維修記錄o；p；q；r；電梯維修信息k；o；s；t；數(shù)據(jù)項定義：(1) a：電梯編號；b：電梯名稱；c：規(guī)格型號；d：安裝位置；(2) e：客戶編號；f：客戶名稱；g：客戶地址；h：聯(lián)系方式；(3) i：電梯價格；j：安裝日期；(4) k：電梯標(biāo)識；l：電梯名稱；m：使用單位；n：安裝位置；(5) o：維修標(biāo)識；p：報修故障；q：報修時間；r：維修時間；(6) s：維修部件；t：維修價格

定義2.(連接依賴)設(shè)X是兩個關(guān)系模式R1(U1)和R2(U2)的公共屬性集,若X→U2,則稱屬性集U2連接依賴于X.

將連接依賴視為關(guān)系模式間特殊的函數(shù)依賴,這樣函數(shù)依賴定義了關(guān)系模式內(nèi)和關(guān)系模式間的數(shù)據(jù)依賴關(guān)系.任給關(guān)系模式集及在其上定義的屬性集,通過屬性集之間的函數(shù)依賴關(guān)系就可以建立屬性之間的依賴圖,簡稱為數(shù)據(jù)依賴圖(Data dependence graph,DDG),定義如下:

定義3.(數(shù)據(jù)依賴圖)將關(guān)系模式集的屬性間的依賴關(guān)系描述為一個擴展的有向圖,表示為一個二元組DDG=(U,E),其中U={a1,a2,…,an}是單個屬性的集合;E={e1,e2,…,em}是屬性間依賴關(guān)系的集合,如ei=X→aj表示屬性aj完全依賴于屬性集X,X?U.

依據(jù)上述定義中的完全依賴關(guān)系,可以推出屬性間的部分依賴關(guān)系和相互依賴關(guān)系.例如,假設(shè)存在電梯企業(yè)的兩個業(yè)務(wù)信息系統(tǒng),它們包括的關(guān)系模式以及屬性如表1所示.其中的屬性a(電梯編號)和屬性k(電梯標(biāo)識)在兩個信息系統(tǒng)中語義等價,相互依賴,為數(shù)據(jù)集成和共享提供了橋梁作用.

圖1 屬性間的數(shù)據(jù)依賴關(guān)系圖Fig.1 Data dependency graph among attributes

3.2 原子數(shù)據(jù)服務(wù)

數(shù)據(jù)服務(wù)的粒度會對數(shù)據(jù)服務(wù)的可用性和可組合性產(chǎn)生直接影響:

1)如果數(shù)據(jù)服務(wù)粒度太小,則數(shù)據(jù)服務(wù)可能會失去語義信息.例如,若僅將表1中電梯的屬性d作為一個數(shù)據(jù)服務(wù),則對該數(shù)據(jù)服務(wù)的訪問結(jié)果難以表明是屬于哪臺電梯的安裝位置;

2)如果數(shù)據(jù)服務(wù)的粒度太大,則數(shù)據(jù)服務(wù)的組合將失去一定的靈活性,并造成一定的數(shù)據(jù)冗余.例如,若將關(guān)系“電梯基本信息”的所有屬性作為一個數(shù)據(jù)服務(wù),則對該數(shù)據(jù)服務(wù)訪問的結(jié)果包括了較多的數(shù)據(jù),降低組合的靈活性和引起較多的數(shù)據(jù)冗余.

為此,提出原子數(shù)據(jù)服務(wù)(Atomic data service,ADS)的概念,其定義如下:

定義4.(原子數(shù)據(jù)服務(wù))將可獨立訪問且語義不可再分的數(shù)據(jù)服務(wù)稱為原子數(shù)據(jù)服務(wù),可以表示為一個八元組ADS=,其中,

· Id是ADS的唯一標(biāo)識;

· Name是ADS的名稱;

· Fields是ADS的屬性列表;

· Description是ADS的語義描述;

· Input是ADS的輸入,可以有多個;

· Output是ADS的輸出,可以是一個關(guān)系;

· Operations是ADS可執(zhí)行的操作;

· Publisher是ADS的發(fā)布者.

算法1給出了原子數(shù)據(jù)服務(wù)劃分算法,輸入是數(shù)據(jù)依賴圖DDG,輸出是原子數(shù)據(jù)服務(wù)的列表.該算法以DDG的任意結(jié)點v開始訪問,按照廣度優(yōu)先策略查找結(jié)點v的任一鄰接結(jié)點w,若結(jié)點w中存在結(jié)點v的前驅(qū)結(jié)點且存在多個前驅(qū)結(jié)點,則首先把v結(jié)點所有的前驅(qū)結(jié)點封裝為一個ADS,其輸入是v節(jié)點的屬性,輸出也是v節(jié)點的屬性;再把所有的前驅(qū)結(jié)點與v結(jié)點封裝為一個ADS,其輸入是前驅(qū)結(jié)點的屬性集或v結(jié)點的屬性,而輸出則是前驅(qū)結(jié)點的屬性集和v結(jié)點的屬性;若v結(jié)點的前驅(qū)結(jié)點唯一,則把前驅(qū)結(jié)點和v結(jié)點封裝為ADS,其輸入是前驅(qū)結(jié)點的屬性集或v結(jié)點的屬性,輸出是前驅(qū)結(jié)點的屬性集和v結(jié)點的屬性;若v結(jié)點不存在前驅(qū)結(jié)點,則確定v結(jié)點為前驅(qū)結(jié)點,w結(jié)點為后繼結(jié)點,把v結(jié)點和w結(jié)點依次封裝為ADS,其輸入是w結(jié)點的屬性或v結(jié)點的屬性,輸出為w結(jié)點的屬性和v結(jié)點的屬性;若所有結(jié)點都被訪問過,則劃分結(jié)束,輸出原子數(shù)據(jù)服務(wù)集合.

算法1.原子數(shù)據(jù)服務(wù)劃分算法

Input:Data dependence graphDDG=

Output:A set of atomic data services.

1. Function ADSCreate(DDG& G,const V & v){

2. Dim i,w,n,loc As INTEGER;

3. n=G.NumberOfVertices(); //Take the number of nodes in the graph

4. Dim visited[] As bool; //Record whether the node has been visited

5. for(i=0;i

6. loc=G.getVertexPos(v);

7. G.getValue(loc);//Access the node,making the visited tag

8. QueueQ;Q.EnQueue(loc); //Nodes into the queue,to achieve hierarchical access

9. while(!Q.IsEmpty){

10. Q.DeQueue(loc); //Quit the node(loc)from the queue

11. w = G.getFirstNeighbor(loc);

12. While(w!=-1){

13. if(visited[w] = = false){

14. G.getValue(w);

15. visited[w]=true;

16. if(?loc.П∈w){ // П means predecessor node

17. if(П.length()>=2){

18. for(j=0;j<П.length();j++)

19. Encapsulated П as a data service,

20. input is {П},output is {П};

21. Encapsulated {П,loc} as a data service,

22. input is {П} or {loc},output is {П,loc};

23. }else if(П.length()<2){

24. Encapsulated {П,loc} as a data service,

25. input is {П} or {loc},output is {П,loc};

26. }

27. }else{

28. for(j=0;j

29. Encapsulated {loc,w[j]} as a data service,

30. input is {loc} or {w[j]},output is {loc,w[j]};

31. }

32. Q.EnQueue(w);

33. }

34. w = G.getNextNeighbor(loc,w);

35. }

36. delete [] visited;

37. }

38. };

通過算法1對圖1所示的數(shù)據(jù)依賴圖進(jìn)行原子數(shù)據(jù)服務(wù)劃分,得到的原子數(shù)據(jù)服務(wù)如表2所示.根據(jù)定義4,原子數(shù)據(jù)服務(wù)可以表示為一個八元組,包括輸入和輸出,以ADS1和ADS2為例予以說明:

1)ADS1是僅包含一個屬性的數(shù)據(jù)服務(wù),該數(shù)據(jù)服務(wù)可以提供電梯編號信息,其輸入和輸出都是“電梯編號”.

2)ADS2是一個包括電梯編號和電梯名稱的數(shù)據(jù)服務(wù),該數(shù)據(jù)服務(wù)可以提供電梯編號和電梯名稱信息,其輸入是“電梯編號”或“電梯名稱”,輸出是“電梯編號”和“電梯名稱”.

需要說明的是,ADS2不可以再細(xì)分為兩個服務(wù),因為在電梯名稱可以重復(fù)的情況下,僅電梯名稱(對應(yīng)屬性b)不能明確是哪臺電梯,導(dǎo)致語義丟失,因此不可以獨立封裝為一個原子數(shù)據(jù)服務(wù).

表2 屬性集劃分得到的部分原子數(shù)據(jù)服務(wù)
Table 2 Some atomic data services obtained from data sets

IdNameFieldsDescriptionInputOutputOperations01ADS1{a}查詢電梯編號電梯編號電梯編號get02ADS2{a，b}查詢電梯編號和電梯名稱電梯編號或電梯名稱電梯編號和電梯名稱get03ADS3{a，c}查詢電梯編號和型號規(guī)格電梯編號或型號規(guī)格電梯編號和型號規(guī)格get04ADS4{a，d}查詢電梯編號和額定人數(shù)電梯編號或額定人數(shù)電梯編號和額定人數(shù)get05ADS5{e}查詢客戶編號客戶編號客戶編號get06ADS6{e，f}查詢客戶編號和客戶名稱客戶編號或客戶名稱客戶編號和客戶名稱get07ADS7{e，g}查詢客戶編號和客戶地址客戶編號或客戶地址客戶編號和客戶地址get08ADS8{e，h}查詢客戶編號和聯(lián)系方式客戶編號或聯(lián)系方式客戶編號和聯(lián)系方式get09ADS9{a．e}查詢電梯、客戶編號電梯編號或客戶編號電梯編號和客戶編號get10ADS10{a，e，i}查詢電梯、客戶編號和電梯價格電梯、客戶編號或電梯價格電梯、客戶編號和電梯價格get11ADS11{a，e，j}查詢電梯、客戶編號和安裝日期電梯、客戶編號或安裝日期電梯、客戶編號和安裝日期get

4 數(shù)據(jù)服務(wù)自動組合

4.1 數(shù)據(jù)服務(wù)依賴圖模型

由于原子數(shù)據(jù)服務(wù)是通過封裝關(guān)系模式的屬性得到的,因此原有屬性間的數(shù)據(jù)依賴關(guān)系可以直接轉(zhuǎn)換為數(shù)據(jù)服務(wù)之間的依賴關(guān)系.根據(jù)屬性間的完全函數(shù)依賴、部分函數(shù)依賴和相互函數(shù)依賴可以得到數(shù)據(jù)服務(wù)之間的以下三種依賴關(guān)系:

定義5.(順序依賴)對于兩個原子數(shù)據(jù)服務(wù)ADSi與ADSj,若ADSi的屬性值確定,ADSj上的屬性值也相應(yīng)確定,即ADSi→ADSj,則稱ADSi與ADSj之間為順序依賴.

定義6.(合并依賴)對于原子數(shù)據(jù)服務(wù)ADS1,ADS2,…,ADSm以及ADSj,若 {ADS1∪ADS2∪ADS3∪…∪ADSm}→ADSj,則稱為合并依賴.

定義7.(相互依賴)對于原子數(shù)據(jù)服務(wù)ADSi以及ADSj,若ADSi→ADSj且ADSj→ADSi,則稱為ADSi與ADSj之間為相互依賴.

圖2 原子數(shù)據(jù)服務(wù)間的基本依賴關(guān)系Fig.2 Basic dependency relationship among ADSs

這三種數(shù)據(jù)服務(wù)依賴關(guān)系如圖2所示.根據(jù)以上定義,可以得到數(shù)據(jù)服務(wù)依賴的性質(zhì):

性質(zhì)1.數(shù)據(jù)服務(wù)依賴具有傳遞性,即若ADSi→ADSj且ADSj→ADSk,則ADSi→ADSk.

證明:略.

性質(zhì)2.數(shù)據(jù)服務(wù)依賴具有對稱性,即若ADSi?ADSj,則ADSi→ADSj且ADSj→ADSi.

證明:略.

根據(jù)數(shù)據(jù)服務(wù)依賴關(guān)系,可以得到數(shù)據(jù)服務(wù)依賴圖(Data service dependence graph,DSDG),簡稱服務(wù)依賴圖,定義如下：

定義8.(服務(wù)依賴圖)將原子數(shù)據(jù)服務(wù)間的依賴關(guān)系描述為一個擴展的有向圖,表示為一個二元組DSDG=(D,E),其中D={ADS1,ADS2,…,ADSn}是原子數(shù)據(jù)服務(wù)集合;E={e1,e2,…,em}是原子數(shù)據(jù)服務(wù)間依賴關(guān)系集合,如ei=A→ADSj表示原子數(shù)據(jù)服務(wù)ADSj依賴于原子數(shù)據(jù)服務(wù)集合A,A?D.

對于上述定義的數(shù)據(jù)服務(wù)依賴關(guān)系ei=A→ADSj,

1)若A僅包含一個原子數(shù)據(jù)服務(wù),ei是順序依賴關(guān)系;

2)若A至少包含兩個原子數(shù)據(jù)服務(wù),ei是合并依賴關(guān)系.

圖3 數(shù)據(jù)服務(wù)依賴圖Fig.3 Data service dependence graph

根據(jù)圖1的數(shù)據(jù)依賴圖得到原子數(shù)據(jù)服務(wù)依賴圖,如圖3所示,圖中的原子數(shù)據(jù)服務(wù)對應(yīng)表2中的原子數(shù)據(jù)服務(wù).

構(gòu)建服務(wù)依賴圖的意義在于可以方便地根據(jù)數(shù)據(jù)服務(wù)之間的依賴關(guān)系組合成用戶需要的復(fù)合數(shù)據(jù)服務(wù),并進(jìn)一步生成用戶數(shù)據(jù)視圖.例如,假設(shè)有一個數(shù)據(jù)需求是根據(jù)“客戶名稱”查詢“規(guī)格型號”,則根據(jù)服務(wù)依賴圖可以查詢知道,相關(guān)的數(shù)據(jù)服務(wù)集包括{ADS6,ADS5,ADS9,ADS1,ADS3},這些數(shù)據(jù)服務(wù)之間的關(guān)系構(gòu)成了一個子圖,通過分析執(zhí)行子圖可以得到查詢的結(jié)果.

4.2 數(shù)據(jù)服務(wù)自動組合算法

本節(jié)給出一個數(shù)據(jù)服務(wù)自動組合算法,該算法基于服務(wù)依賴圖模型,通過分析原子數(shù)據(jù)服務(wù)之間的依賴關(guān)系,搜索與數(shù)據(jù)需求相關(guān)的數(shù)據(jù)服務(wù),構(gòu)建復(fù)合數(shù)據(jù)服務(wù),通過執(zhí)行復(fù)合數(shù)據(jù)服務(wù)得到用戶視圖,對復(fù)合數(shù)據(jù)服務(wù)(Composite data service,CDS)的定義如下:

定義9.(復(fù)合數(shù)據(jù)服務(wù))由若干原子數(shù)據(jù)服務(wù)組成且可被獨立訪問的數(shù)據(jù)服務(wù)稱為復(fù)合數(shù)據(jù)服務(wù),它可以表示為一個八元組CDS=,其中,

· Id是CDS的唯一標(biāo)識;

· Name是CDS的名稱;

· Sub-DSDG是DSDG的子圖;

· Description是ADS的語義描述;

· Input是CDS的輸入,可以有多個;

· Output是CDS的輸出,可以是一個關(guān)系;

· Operations是對ADS可執(zhí)行的操作;

· Publisher是ADS的發(fā)布者.

數(shù)據(jù)服務(wù)組合過程是在用戶數(shù)據(jù)需求驅(qū)動下進(jìn)行的,數(shù)據(jù)需求(Data Requirements,DR)的定義如下:

定義10.(數(shù)據(jù)需求)用戶所需要的屬性列表、約束條件以及執(zhí)行的操作稱為數(shù)據(jù)需求,可以表示為一個三元組DR=,其中,

· Requires表示數(shù)據(jù)需求的屬性列表;

· Conditions={| Field表示屬性名,Value表示屬性值>}表示數(shù)據(jù)需求的約束條件,可以為Null;

· Operations={get,delete,update}表示需要執(zhí)行的操作.

以查詢客戶名稱為“杭州大廈”的電梯規(guī)格型號為例,其DR可以定義為:

DR=<{客戶名稱,規(guī)格型號},{<客戶名稱,“杭州大廈”>},>.

算法2給出了數(shù)據(jù)服務(wù)自動組合算法,該算法的輸入是DSDG和DR,輸出是復(fù)合數(shù)據(jù)服務(wù).首先在DSDG上檢索出包含Requires屬性列表和Conditions屬性列表的所有ADS;通過深度搜索策略尋求能夠聯(lián)通這些ADS的通路;如果存在多個通路,則表示存在多個組合方案;將包括ADS數(shù)量最少以及包括的屬性個數(shù)最少的通路作為最終輸出,得到最優(yōu)的數(shù)據(jù)服務(wù)組合結(jié)果,該結(jié)果即是需要的CDS.

由于CDS包括的ADS數(shù)量和屬性個數(shù)將影響CDS的執(zhí)行性能,因此算法以此為標(biāo)準(zhǔn)對數(shù)據(jù)服務(wù)組合方案進(jìn)行篩選,得到最優(yōu)的數(shù)據(jù)服務(wù)組合結(jié)果.實際應(yīng)用表明,該方法簡單易用,實際應(yīng)用中往往能得到最優(yōu)的組合解.此外,以上算法假設(shè)DSDG的所有節(jié)點是聯(lián)通的,如果不聯(lián)通,則可以分別對DSDG的所有子圖循環(huán)使用該算法,并輸出每個子圖的CDS.

設(shè)r為數(shù)據(jù)需求屬性列表的個數(shù),n為服務(wù)依賴圖中的節(jié)點總數(shù),e代表鄰接表表示邊的個數(shù),則算法第1行到第6行的時間復(fù)雜度是O(n),第7行到第25行的時間復(fù)雜度是O(n+e),因此算法總的時間復(fù)雜度為O(n+e).

以查詢客戶名稱為“杭州大廈”的電梯規(guī)格型號的數(shù)據(jù)需求為例予以說明:根據(jù)該算法首先檢索包含“客戶名稱”和“規(guī)格型號”語義的原子數(shù)據(jù)服務(wù),然后尋求能夠聯(lián)通這兩個節(jié)點的通路,所有在該通路上的原子數(shù)據(jù)服務(wù)以及依賴邊組成的子圖即是滿足該用戶數(shù)據(jù)需求的“復(fù)合數(shù)據(jù)服務(wù)”.圖3中ADS1,ADS3,ADS5,ADS6,ADS9的ADS原子數(shù)據(jù)服務(wù)就是組合后的復(fù)合數(shù)據(jù)服務(wù).

算法2.數(shù)據(jù)服務(wù)自動組合算法

Input:DSDG,DR

Output:CDS

1. Function CDSCreate(DSDG=&G,constW&v,DR&r){

2. Dim i,n,w,loc As INTEGER;

3. n=G.NumberOfVertices(); //Take the number of nodes in the graph

4. Dim visited[] As bool; //Record whether the node has been visited

5. for(i=0;i

6. loc=G.getVertexPos(v);

7. getPaths(G,loc,visited[],DR){

8. G.getValue(v); //Access the node,making the visited tag

9. stack.push(v);

10. w=G.getFirstNeighbor(v); //Find the first adjacent node of node v

11. while(w != -1){

12. stack.push(w);

13. if(stack.contains(r)== true){

14. Encapsulated v and visited[w] as a composite data service;

15. return true;

16. }

17. else if(visited[w] == false){

18. getPaths(G,w,visited[],DR); //Recursive access if w has not been accessed

19. stack.pop();

20. }

21. w = G.getNextNeighbor(v,w); //Take the next adjacent node

after w of node v;

22. }

23. delete [] visited;

24. }

25. };

4.3 數(shù)據(jù)組合視圖生成

根據(jù)數(shù)據(jù)服務(wù)組合的結(jié)果,執(zhí)行CDS將能夠生成數(shù)據(jù)視圖,其定義如下:

定義11.(數(shù)據(jù)組合視圖)執(zhí)行復(fù)合數(shù)據(jù)服務(wù)后生成的結(jié)果稱為數(shù)據(jù)組合視圖,其形式上是一張二維表格.

CDS包含了與數(shù)據(jù)需求相關(guān)的原子數(shù)據(jù)服務(wù)及其依賴關(guān)系,以查詢操作為例,給出執(zhí)行CDS的基本步驟:

第1步.分別執(zhí)行CDS的所有ADS,并根據(jù)Conditions條件對ADS的執(zhí)行結(jié)果進(jìn)行篩選;

第2步.對具有服務(wù)依賴關(guān)系的ADS的結(jié)果執(zhí)行連接操作;

第3步.根據(jù)DR中的Requires屬性列表對連接的結(jié)果執(zhí)行投影操作;

第4步.若存在多個CDS,則反復(fù)執(zhí)行步驟1和步驟4,得到多個滿足DR的數(shù)據(jù)子集;

第5步.對得到的多個數(shù)據(jù)子集執(zhí)行并操作.

執(zhí)行復(fù)合數(shù)據(jù)服務(wù)所涉及的操作包括選擇、連接、并和投影,這些操作是關(guān)系數(shù)據(jù)模型中的基本操作,不作為本文論述的重點.

以圖3中灰色原子數(shù)據(jù)服務(wù)組合成的復(fù)合數(shù)據(jù)服務(wù)為例說明執(zhí)行的過程:首先,執(zhí)行原子數(shù)據(jù)服務(wù)ADS6、ADS5、ADS9、ADS1、ADS3,根據(jù)Conditions條件<客戶名稱,“杭州大廈”>對ADS6的執(zhí)行結(jié)果進(jìn)行篩選;第二,對以上五個ADS的結(jié)果執(zhí)行連接操作,得到一個結(jié)果集;第三,根據(jù)DR中的Requires對結(jié)果集執(zhí)行投影操作;第四,由于只有一個復(fù)合數(shù)據(jù)服務(wù),因此跳過;第五,輸出執(zhí)行的結(jié)果,該結(jié)果就是執(zhí)行復(fù)合數(shù)據(jù)服務(wù)后得到的數(shù)據(jù)組合視圖.

5 實驗分析與評價

由于目前還沒有公開的數(shù)據(jù)服務(wù)評價數(shù)據(jù)集,本文結(jié)合電梯企業(yè)各部門信息系統(tǒng)中的數(shù)據(jù)建立數(shù)據(jù)服務(wù),涉及的數(shù)據(jù)類別包括電梯標(biāo)準(zhǔn)數(shù)據(jù)、電梯設(shè)計基本數(shù)據(jù)、電梯銷售基本數(shù)據(jù)、電梯維護(hù)基本數(shù)據(jù)、電梯使用基本數(shù)據(jù)、電梯故障檢測數(shù)據(jù)、電梯使用單位數(shù)據(jù)、電梯制造單位數(shù)據(jù)、電梯維保單位數(shù)據(jù)等.

圖4 跨部門數(shù)據(jù)服務(wù)依賴圖Fig.4 Data service dependency graph of inter-departments

根據(jù)文中提出的原子數(shù)據(jù)服務(wù)劃分方法,得到原子數(shù)據(jù)服務(wù)集合,并根據(jù)原子數(shù)據(jù)服務(wù)之間的服務(wù)依賴關(guān)系,建立數(shù)據(jù)服務(wù)依賴網(wǎng),如圖4所示,圖中每個節(jié)點代表一個原子數(shù)據(jù)服務(wù),每條有向邊代表原子數(shù)據(jù)服務(wù)之間的依賴關(guān)系,原子數(shù)據(jù)服務(wù)總數(shù)為810個,圖中的不同顏色表示數(shù)據(jù)來自多個不同的部門,并通過公共的屬性建立跨部門之間的數(shù)據(jù)聯(lián)系.

由于數(shù)據(jù)服務(wù)的劃分已結(jié)合實例進(jìn)行了詳細(xì)描述.為此, 本實驗主要對數(shù)據(jù)服務(wù)組合算法的效率、 質(zhì)量和成功率三個方面進(jìn)行評價: 組合效率用來評估數(shù)據(jù)服務(wù)組合所花費的時間代價; 組合質(zhì)量用來評價服務(wù)組合的結(jié)果是否為最優(yōu)解; 組合準(zhǔn)確性用來評價復(fù)合數(shù)據(jù)服務(wù)的執(zhí)行結(jié)果能否滿足數(shù)據(jù)需求.

表3 實驗數(shù)據(jù)集
Table 3 Experimental data set

測試數(shù)據(jù)集類型DR．Requires屬性個數(shù)DR．Conditions約束個數(shù)數(shù)據(jù)服務(wù)總數(shù)不同數(shù)據(jù)服務(wù)總數(shù)62100，200，400600，800不同屬性列表2，4，6，8，102800不同約束個數(shù)61，2，4，6800

實驗環(huán)境是在一臺服務(wù)器上搭建完成的,CPU是Inter E5-2430,主頻是2.20GHz,內(nèi)存是4GB.

從原子數(shù)據(jù)服務(wù)的總數(shù)、數(shù)據(jù)需求的屬性個數(shù)和數(shù)據(jù)需求的約束條件個數(shù)對組合算法進(jìn)行評價,包括三組測試數(shù)據(jù):測試數(shù)據(jù)集1保持屬性個數(shù)和約束個數(shù)不變,數(shù)據(jù)服務(wù)總數(shù)分別設(shè)置為100、200、400、600、800;測試數(shù)據(jù)集2保持約束個數(shù)不變,數(shù)據(jù)服務(wù)總數(shù)不變,屬性個數(shù)分別設(shè)置為2,4,6,8,10;測試數(shù)據(jù)集3保持屬性個數(shù)和數(shù)據(jù)服務(wù)總數(shù)不變,約束個數(shù)分別設(shè)置為1,2,4,6.以上所涉及到的屬性都可以在數(shù)據(jù)服務(wù)中進(jìn)行成功匹配.每次測試均按照隨機方式給出屬性個數(shù)、約束個數(shù),并選取10次測試結(jié)果的平均值作為實驗結(jié)果.

5.1 組合效率

本文的數(shù)據(jù)服務(wù)組合算法是根據(jù)數(shù)據(jù)需求的Requires和Conditions,基于服務(wù)依賴圖搜索最優(yōu)的復(fù)合數(shù)據(jù)服務(wù).圖5(a)給出了不同數(shù)據(jù)服務(wù)總數(shù)下的復(fù)合數(shù)據(jù)服務(wù)的組合時間; 圖5(b)給出了不同屬性列表情況下復(fù)合數(shù)據(jù)服務(wù)的組合時間.從圖中可以看出,隨著Requires和數(shù)據(jù)服務(wù)的增加, 復(fù)合數(shù)據(jù)服務(wù)的組合時間也在不斷增加.這是因為Requires影響數(shù)到涉及的原子數(shù)據(jù)服務(wù)的數(shù)量;而數(shù)據(jù)服務(wù)總數(shù)影響到據(jù)服務(wù)的組合范圍;此外,實驗還表明數(shù)據(jù)需求的Conditions也影響著服務(wù)組合的時間,但其影響與Requires類似,Conditions中的條件越多,涉及到的原子數(shù)據(jù)服務(wù)數(shù)量也越多.當(dāng)數(shù)據(jù)服務(wù)為800時,不同屬性列表的平均搜索時間為128ms.

圖5 不同條件下數(shù)據(jù)服務(wù)組合的效率Fig.5 Composition efficiency with different conditions

5.2 組合質(zhì)量

組合質(zhì)量是指組合得到的復(fù)合數(shù)據(jù)服務(wù)所包含的原子數(shù)據(jù)服務(wù)的數(shù)量以及屬性的個數(shù).實驗結(jié)果表明,每組數(shù)據(jù)需求通過組合算法可以得到多個組合方案,但它們的原子數(shù)據(jù)服務(wù)數(shù)和屬性個數(shù)可能不同.由于組合算法以復(fù)合數(shù)據(jù)服務(wù)包括的原子數(shù)據(jù)服務(wù)數(shù)量和屬性個數(shù)作為評價標(biāo)準(zhǔn),復(fù)合數(shù)據(jù)服務(wù)中包括的原子數(shù)據(jù)服務(wù)及其屬性列表的數(shù)量越少,組合方案越好.因此,通過運行本文算法得到的組合結(jié)果即是最優(yōu)組合解,實驗統(tǒng)計結(jié)果如表4 所示.對組合結(jié)果分析發(fā)現(xiàn),當(dāng)原子數(shù)據(jù)服務(wù)數(shù)量為800、屬性列表數(shù)量為4時,存在兩個包含數(shù)據(jù)服務(wù)數(shù)量相同的組合方案6(10)和6(11),其中括號前面的數(shù)值表示原子數(shù)據(jù)服務(wù)的數(shù)量,括號中的數(shù)值表示屬性的個數(shù);此外,實驗還表明隨著數(shù)據(jù)需求中包含的屬性列表數(shù)量的增大,組合結(jié)果逐步趨向唯一解.

表4 組合質(zhì)量的統(tǒng)計結(jié)果
Table 4 Experimental results of composition quality

原子數(shù)據(jù)服務(wù)數(shù)量屬性列表數(shù)量不同的CDS包括的原子數(shù)據(jù)服務(wù)的數(shù)量最優(yōu)CDS包括的原子數(shù)據(jù)服務(wù)數(shù)量80022、4、6、6、8、10280046(10)、6(11)、8、106(10)80066、8、10680088、108800101010

5.3 組合準(zhǔn)確性

實驗只考慮數(shù)據(jù)需求所包含的屬性列表能夠在原子服務(wù)中查找到的情況,對于無法查找到相應(yīng)原子數(shù)據(jù)服務(wù)的情況,則表明無法通過服務(wù)組合滿足數(shù)據(jù)需求,被直接忽略.通過執(zhí)行復(fù)合服務(wù)生成數(shù)據(jù)視圖,仔細(xì)分析后發(fā)現(xiàn):數(shù)據(jù)視圖中包含的屬性列表與數(shù)據(jù)需求中包含的屬性列表相匹配,而且執(zhí)行的數(shù)據(jù)結(jié)果滿足數(shù)據(jù)需求的約束條件,這表明通過執(zhí)行復(fù)合數(shù)據(jù)服務(wù)得到的數(shù)據(jù)視圖能夠準(zhǔn)確地滿足數(shù)據(jù)需求,成功率為100%.

6 結(jié)束語

為了根據(jù)已封裝的數(shù)據(jù)服務(wù)自動組合出能夠滿足用戶數(shù)據(jù)需求的復(fù)合數(shù)據(jù)服務(wù),本文提出了一種基于依賴圖模型的數(shù)據(jù)服務(wù)自動組合方法.該方法將具有跨域異構(gòu)特征屬性集封裝為不可再分的原子數(shù)據(jù)服務(wù),并根據(jù)原子數(shù)據(jù)服務(wù)之間的數(shù)據(jù)依賴關(guān)系建立數(shù)據(jù)服務(wù)依賴圖,由此將數(shù)據(jù)組合問題建模為基于依賴圖模型的搜索問題,得到最優(yōu)的復(fù)合數(shù)據(jù)服務(wù),通過執(zhí)行復(fù)合數(shù)據(jù)服務(wù)生成數(shù)據(jù)視圖.實驗結(jié)果表明,該方法具有較高的組合效率,得到的復(fù)合數(shù)據(jù)服務(wù)包含的原子數(shù)據(jù)服務(wù)數(shù)量最少,能夠準(zhǔn)確滿足用戶的數(shù)據(jù)需求.

[1] Carey M J,Onose N,Petropoulos M.Data services[J].Communications of the ACM,2012,55(6):86-97.

[2] Carey M.Declarative data services:this is your data on SOA[C].Proceedings of the IEEE International Conference on Service-Oriented Computing and Applications(SOCA),IEEE,2007:4-4.

[3] Carey M J.Data delivery in a service-oriented world:the BEA aqua logic data services platform[C].Proceedings of the ACM SIGMOD International Conference on Management of Data,Chicago,Illinois,Usa,June.DBLP,2006:695-705.

[4] Altinel M,Brown P,Cline S,et al.Damia:a data mashup fabric for intranet applications[C].Proceedings of the International Conference on Very Large Data Bases(VLDB),University of Vienna,Austria,September,2007:1370-1373.

[5] Wen Yan,Liu Chen,Han Yan-bo.iViewer:service-based view construction method for just-in-time sharing business data across organizations[J].Journal of Frontiers of Computer Science & Technology,2012,6(3):221-236.

[6] Carey M,Reveliotis P,Thatte S,et al.Data service modeling in the aqualogic data services platform[C].Proceedings of the IEEE Congress on Services(SERVICES),2008:78-80.

[7] Liu X,Hu C,Li Y,et al.The advanced data service architecture for modern enterprise information system[C].Proceedings of the International Conference on Information Science and Applications(ICISA),IEEE,2014:1-4.

[8] Xie Xing-sheng,Zhuang Zhen-quan.Study of data integration method based on data service matching [J].Journal of University of Science & Technology of China,2009,39(5):504-509.

[9] Xie Jun,Xiao Lu.Research on data integration based on virtual view and its application[J].Engineering Journal of Wuhan University,2014,47(2):281-285.

[10] Wang Gui-ling,Han Yan-bo,Zhang Zhong-mei,et al.Cloud-based integration and service of streaming data[J].Chinese Journal of Computers,2017,40(1):107-125.

[11] Zorrilla M,Garc,A-Saiz D.A service oriented architecture to provide data mining services for non-expert data miners [J].Decision Support Systems(DSS),2013,55(1):399-411.

[12] Gu Z,Xu B,Li J.Service data correlation modeling and its application in data-driven service composition[J].IEEE Transactions on Services Computing(TSC),2010,3(4):279-291.

[13] Amdouni S,Barhamgi M,Benslimane D,et al.Handling uncertainty in data services composition[C].IEEE International Conference on Services Computing(SCC),IEEE,2014:653-660.

[14] Chen Q,Hu H,Xu J.Authenticated online data integration services[C].Proceedings of the ACM SIGMOD International Conference,ACM,2015:167-181.

[15] Zhang Peng,Han Yan-bo,Wang Gui-ling.Implementing dynamic nested view update based on data service [J].Chinese Journal of Computers,2013,36(2):226-237.

[16] Zhang Peng,Wang Gui-ling,Ji Guang,et al.Optimization update for data composition view based on data service[J].Chinese Journal of Computers,2011,34(12):2344-2354.

[17] Abdelhamid M,Mahmoud B,Sidi-Mohamed B,et al.Composing data services with uncertain semantics[C].IEEE Transactions on Knowledge and Data Engineering(TKDE),2015,27(4):936-949.

[18] Zhou L,Chen H,Zhang Y,et al.A semantic mapping system for bridging the gap between relational database and semantic Web[C].Proceedings of the AAAI Spring Symposium on Semantic Scientific Knowledge Integration,2008:122-126.

附中文參考文獻(xiàn)：

[5] 溫 彥,劉 晨,韓燕波.iViewer:利用數(shù)據(jù)服務(wù)即時生成跨域數(shù)據(jù)視圖[J].計算機科學(xué)與探索,2012,6(3):221-236.

[8] 謝興生,莊鎮(zhèn)泉.一種基于數(shù)據(jù)服務(wù)匹配的數(shù)據(jù)集成方法研究[J].中國科學(xué)技術(shù)大學(xué)學(xué)報,2009,39(5):504-509.

[9] 謝 軍,肖 路.基于虛擬視圖的數(shù)據(jù)集成方法研究及其應(yīng)用[J].武漢大學(xué)學(xué)報工學(xué)版,2014,47(2):281-285.

[10] 王桂玲,韓燕波,張仲妹,等.基于云計算的流數(shù)據(jù)集成與服務(wù)[J].計算機學(xué)報,2017,40(1):107-125.

[15] 張 鵬,韓燕波,王桂玲.基于數(shù)據(jù)服務(wù)的嵌套視圖動態(tài)更新方法[J].計算機學(xué)報,2013,36(2):226-237.

[16] 張 鵬,王桂玲,季 光,等.基于數(shù)據(jù)服務(wù)的數(shù)據(jù)組合視圖的優(yōu)化更新[J].計算機學(xué)報,2011,34(12):2344-2354.