數(shù)據(jù)服務依賴圖模型及自動組合方法研究

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

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

1 引 言

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

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

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

2 相關研究

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

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

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

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

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

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

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

3.1 基本概念

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

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

根據(jù)函數(shù)依賴的定義,可以推導出完全函數(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

來源部門關系模式名稱屬性集設計部門電梯基本信息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：電梯標識；l：電梯名稱；m：使用單位；n：安裝位置；(5) o：維修標識；p：報修故障；q：報修時間；r：維修時間；(6) s：維修部件；t：維修價格

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

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

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

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

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

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

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

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

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

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

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

· Id是ADS的唯一標識;

· Name是ADS的名稱;

· Fields是ADS的屬性列表;

· Description是ADS的語義描述;

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

· Output是ADS的輸出,可以是一個關系;

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

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

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

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

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ù)依賴圖進行原子數(shù)據(jù)服務劃分,得到的原子數(shù)據(jù)服務如表2所示.根據(jù)定義4,原子數(shù)據(jù)服務可以表示為一個八元組,包括輸入和輸出,以ADS1和ADS2為例予以說明:

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

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

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

表2 屬性集劃分得到的部分原子數(shù)據(jù)服務
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ù)服務自動組合

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

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

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

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

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

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

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

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

證明:略.

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

證明:略.

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

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

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

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

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

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

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

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

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

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

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

· Id是CDS的唯一標識;

· Name是CDS的名稱;

· Sub-DSDG是DSDG的子圖;

· Description是ADS的語義描述;

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

· Output是CDS的輸出,可以是一個關系;

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

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

數(shù)據(jù)服務組合過程是在用戶數(shù)據(jù)需求驅(qū)動下進行的,數(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ù)服務自動組合算法,該算法的輸入是DSDG和DR,輸出是復合數(shù)據(jù)服務.首先在DSDG上檢索出包含Requires屬性列表和Conditions屬性列表的所有ADS;通過深度搜索策略尋求能夠聯(lián)通這些ADS的通路;如果存在多個通路,則表示存在多個組合方案;將包括ADS數(shù)量最少以及包括的屬性個數(shù)最少的通路作為最終輸出,得到最優(yōu)的數(shù)據(jù)服務組合結果,該結果即是需要的CDS.

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

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

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

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

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ù)服務組合的結果,執(zhí)行CDS將能夠生成數(shù)據(jù)視圖,其定義如下:

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

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

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

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

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

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

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

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

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

5 實驗分析與評價

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

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

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

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

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

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

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

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

5.1 組合效率

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

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

5.2 組合質(zhì)量

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

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

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

5.3 組合準確性

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

6 結束語

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

附中文參考文獻：

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

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

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

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

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

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