數據服務依賴圖模型及自動組合方法研究

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

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

1 引 言

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

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

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

2 相關研究

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

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

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

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

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

3 數據服務依賴圖模型

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

3.1 基本概念

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

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

根據函數依賴的定義,可以推導出完全函數依賴、部分函數依賴、相互函數依賴,定義如下:

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

表1 電梯企業信息系統數據集
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；數據項定義：(1) a：電梯編號；b：電梯名稱；c：規格型號；d：安裝位置；(2) e：客戶編號；f：客戶名稱；g：客戶地址；h：聯系方式；(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.

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

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

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

圖1 屬性間的數據依賴關系圖Fig.1 Data dependency graph among attributes

3.2 原子數據服務

數據服務的粒度會對數據服務的可用性和可組合性產生直接影響:

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

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

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

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

· Id是ADS的唯一標識;

· Name是ADS的名稱;

· Fields是ADS的屬性列表;

· Description是ADS的語義描述;

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

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

· Operations是ADS可執行的操作;

· Publisher是ADS的發布者.

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

算法1.原子數據服務劃分算法

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

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

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

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

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

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

4 數據服務自動組合

4.1 數據服務依賴圖模型

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

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

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

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

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

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

性質1.數據服務依賴具有傳遞性,即若ADSi→ADSj且ADSj→ADSk,則ADSi→ADSk.

證明:略.

性質2.數據服務依賴具有對稱性,即若ADSi?ADSj,則ADSi→ADSj且ADSj→ADSi.

證明:略.

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

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

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

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

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

圖3 數據服務依賴圖Fig.3 Data service dependence graph

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

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

4.2 數據服務自動組合算法

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

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

· Id是CDS的唯一標識;

· Name是CDS的名稱;

· Sub-DSDG是DSDG的子圖;

· Description是ADS的語義描述;

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

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

· Operations是對ADS可執行的操作;

· Publisher是ADS的發布者.

數據服務組合過程是在用戶數據需求驅動下進行的,數據需求(Data Requirements,DR)的定義如下:

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

· Requires表示數據需求的屬性列表;

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

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

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

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

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

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

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

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

算法2.數據服務自動組合算法

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 數據組合視圖生成

根據數據服務組合的結果,執行CDS將能夠生成數據視圖,其定義如下:

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

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

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

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

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

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

第5步.對得到的多個數據子集執行并操作.

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

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

5 實驗分析與評價

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

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

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

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

表3 實驗數據集
Table 3 Experimental data set

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

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

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

5.1 組合效率

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

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

5.2 組合質量

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

表4 組合質量的統計結果
Table 4 Experimental results of composition quality

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

5.3 組合準確性

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

6 結束語

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

[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:利用數據服務即時生成跨域數據視圖[J].計算機科學與探索,2012,6(3):221-236.

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

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

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

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

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