溫 彥, 仇麗青, 陳 欣, 張 峰
(山東科技大學 信息科學與工程學院 山東 青島 266590)
?
一種支持數據源動態(tài)加入的交互式數據集成方法
溫 彥, 仇麗青, 陳 欣, 張 峰
(山東科技大學 信息科學與工程學院 山東 青島 266590)
提出了一種支持數據源動態(tài)加入的交互式數據集成方法.該方法利用基于可視化嵌套表格提供所見即所得的即時集成環(huán)境,利用語義映射工具提供半自動化的支持,漸進式地向用戶推薦可能的集成結果和方式,屏蔽集成過程的復雜性,并保證任意的數據源引入順序條件下集成結果的正確性.采用增量式的方法計算新數據源加入時的最優(yōu)集成方案,利用用戶反饋有效地進行剪枝,優(yōu)化集成過程.通過實驗驗證了此方法的有效性.
數據集成; 交互式; 按需集成; 數據源動態(tài)加入
互聯(lián)網正在演變?yōu)槠袢祟愖畲蟮膮f(xié)同計算平臺,其上的數據規(guī)模呈指數級增長,其中結構化數據顯著增加,且用戶對結構化對象的查詢占據了所有Web檢索的一半以上并呈現出跨領域、綜合性的特點[1].此外,用戶的個性化數據需求愈發(fā)明顯,具有即時性、不可重復等特點.因此如何支持最終用戶快速按需集成互聯(lián)網數據,成為亟待解決的問題.解決該問題需要克服前所未有的新的挑戰(zhàn),使得傳統(tǒng)的重量級集成方法不再適用:數據規(guī)模大、動態(tài)性強,難以建立和維護統(tǒng)一的中間模式,且需要應對數據源的動態(tài)加入和退出[2];數據內容高度自治,缺乏足夠的語義信息和統(tǒng)一的語義規(guī)范,給集成帶來較大困難;即時、個性化的集成需求使得方法必須易于使用.
已有一些工作針對互聯(lián)網環(huán)境下的跨域數據集成,然而這些方法對用戶而言是困難的,主要表現在:1) 用戶理解并實現復雜的集成邏輯是困難的,包括各類數據處理和控制邏輯操作,且需要按照正確的順序來引入數據源、執(zhí)行集成操作.2) 跨域數據普遍存在語義層面的異構性,用戶正確指定數據的語義映射關系并進行可視化表示是困難的.3) 面對新數據源動態(tài)加入和退出,用戶需要即時修正集成邏輯并保證集成結果的正確性,對用戶而言也是困難的.
為了克服上述困難,本文基于已有數據服務的模型和其上定義的聚合操作[3],以及嵌套表格提供的所見即所得的集成環(huán)境和語義映射工具提供的匹配方法,提供一種漸進式的交互式集成過程向用戶推薦可能的集成結果,屏蔽語義映射和集成操作的復雜性,同時保證在任意的數據源引入順序條件下(即數據源動態(tài)加入過程)集成結果的正確性.集成過程采用增量式的方法計算新資源加入時的最優(yōu)集成方案,并利用用戶反饋有效地進行剪枝,優(yōu)化集成過程,改進用戶體驗.
我們在之前的工作中提出了數據服務模型[3],它基于嵌套關系定義,能夠表達互聯(lián)網上常見的結構化和半結構化數據,且具有良好的可視化形式,嵌套關系和數據服務的定義如下.
定義1 (嵌套關系) 一個嵌套關系包含模式和實例.令A是屬性名稱全集,嵌套關系模式R(S)被定義為:R(S)=(A1,A2,…,Am),其中:R∈A.R是關系模式的名稱,S是屬性名稱列表.Ai是原子屬性或者形如Ri(Si)的子關系屬性.模式R(S)的一個實例是形如(a1,a2,…,am)的有序元組集合,若Ai是原子屬性,則ai是基礎數據值;若Ai是關系模式,則ai是Ai的實例.
定義2(數據服務) 數據服務是如下五元組:ds=
在數據服務上定義了基于映射關系的服務輸出輸入連接(connect)、服務輸出連接(join)和合并(union)等操作.基于嵌套關系代數的理論基礎,這些操作滿足廣義交換律、結合律和分配律.
本節(jié)通過一個典型案例來說明本文所提方法的基本效果.該案例的目標為獲得滿足火災救援需求的設備儲備信息視圖.假設涉及的數據服務模式如表1~表4中的S1~S4所示,它們均不包含輸入參數.
表1 物資需求(S1)Tab.1 Material reserves(S1)
表2 醫(yī)療設備儲備(S2)Tab.2 Medical equipment storage(S2)
表3 滅火設備型號登記(S3)Tab.3 Fire extinguishing equipment models registration(S3)
表4 設備庫存(S4)
Tab.4 Equipment storage(S4)
設備型號各倉庫存量倉庫庫存量MTZ?5S1500S3300MTZ?20S3200MTZ?50S1400S3300
本文的集成過程分為集成目標模式生成和增量式集成方式發(fā)現兩個階段.生成結果的數據模式稱為目標模式.該階段關注新引入服務(設為S)與當前目標模式(設為T)的屬性合并、擴展(增加新屬性)和層次結構的改變.基本思路為,首先根據S與T之間的原子屬性上的基本映射關系形成新的目標模式T′.而后根據S的嵌套結構所反映的數據依賴關系來確定T′的層次結構.
3.1 屬性映射關系的計算和推薦
定義3 模式匹配擴展圖.嵌套模式R1和R2的所有原子屬性集合分別為T和S,在T中為S中的每個元素s構建附加節(jié)點s′構成Ts′={s′},并令T′=T∪Ts′,在S中為T中的每個元素t構建附加節(jié)點t′構成St′={t′},并令S′=S∪St′.構造二部圖G=
1) 若a∈T,b∈S,則w=c(
2) 若a∈T,b=e1,則w=(1-maxbi∈S(c()))/2;
3) 若b∈S,a=e2,則w=(1-maxaj∈T(c(
根據上述定義,可直接得到性質1.
性質1 所有擴展節(jié)點上只有一條邊,連接其源節(jié)點.
定義3的2)和3)中除以2的含義為:使得連接兩個屬性的邊通過擴展節(jié)點提供的兩條擴展邊的權值和不大于原匹配屬性對的權值.根據性質1,擴展圖中的附加節(jié)點s′與其源節(jié)點s構成的邊表示源節(jié)點s不與T中的所有節(jié)點匹配,即為擴展屬性.可在模式匹配擴展圖中使用KM算法獲得最大匹配.圖1為示例.假設兩模式原子屬性間的匹配及其置信度如圖1(a)所示,擴展后如圖1(b),兩圖的帶權最大二分匹配為加粗黑線,左圖的質量為1.62,右圖為1.895,t1、s1為擴展屬性.
圖1 模式擴展圖的最大二部匹配示例Fig.1 Maximum bipartite graph mappings for schema extending graph
3.2 擴展屬性位置的計算和推薦
盡管嵌套和解嵌套操作可形成多種合理的層次結構,不存在唯一最優(yōu)結構,然而合并過程應當盡量保持原嵌套層次表示的數據依賴關系.因此可根據此依賴關系來預測并推薦擴展屬性的位置.
定義4 嵌套關系屬性的層次關系.嵌套關系模式中的屬性(原子、子關系屬性)間在嵌套結構上的關系分為4種:上層、下層、平級、無關.屬性A為B的上層屬性當且僅當A所在的嵌套關系R1可遞歸包含B所在的嵌套關系R2,此時稱B為A的下層屬性,R1為B、R2的祖先關系,B、R2為R1的子孫關系/屬性,若A和B為同一個嵌套關系的屬性,則A、B互為彼此的平級屬性,若A、B不滿足3種關系,則稱A、B無關.A的所有祖先關系與B的所有祖先關系中相交的部分稱為A和B的公共上層關系,其中嵌套層次最深的子關系稱為A、B的最近公共祖先關系.A、B的距離是指A、B到兩者的最近公共祖先關系的嵌套路徑長度之和.如嵌套模式A,F
可根據嵌套結構的形態(tài)描述嵌套關系整體及其子結構的數據依賴關系特征,包含全局依賴和局部依賴[5],前者表示在整個嵌套結構上的依賴關系,后者表示僅在某個子關系內部成立的依賴關系.兩者主鍵只包含原子屬性.例如S4中“(設備型號,倉庫)→庫存量”為全局依賴,“倉庫→庫存量”為局部依賴,可以看出,全局依賴的主鍵分布在不同的嵌套層次中,形成了局部依賴.
定義5 嵌套關系的全局依賴關系.對于嵌套關系模式R,其上的全局依賴關系的形式為:(A1,A2,…,An)→GB,其中Ai∈R.TAttr,i=1,2,…,n,B為R中某嵌套層次內的原子屬性或子關系屬性,表示(A1,A2,…,An)的值能夠唯一確定B的取值(B為原子屬性時,表示簡單值,B為子關系屬性時,表示B上的元組集合),并將{A1,A2,…,An}稱為B的依賴屬性集.假設B所有祖先關系的原子屬性集合為A,則A→GB被稱為B上的平凡全局依賴關系,并將A稱為B的平凡依賴屬性集.
定義6 嵌套關系的局部依賴關系.對于嵌套關系模式R,其上的局部依賴關系的形式為:(L1,L2,…,Lm)→LB成立當且僅當存在R上的全局依賴關系(A1,A2,…,An)→GB,使得{L1,L2,…,Lm}?{A1,A2,…,An},且(L1,L2,…,Lm)與B在同一子關系內.
根據上述對嵌套結構及其依賴關系的分析,擴展屬性位置的推薦原則為維護屬性間的數據依賴關系并盡量保持它們在原數據模式中的位置關系,使得相同屬性對間的距離在數據服務中和在目標模式中的變化較小.某些全局依賴關系可能不包含在所有的平凡全局依賴關系集合內,但在缺乏明確定義的依賴關系的情況下,推薦均基于平凡依賴關系.根據定義4~6,得到引理1.
引理1 假設在嵌套關系模式R中,存在(A1,A2,…,An)→GB,A1,A2,…,An中不存在不相關的屬性對,Rj為(A1,A2,…,An)中嵌套層次最深的屬性Aj所在的關系,則若通過嵌套操作使得Rj的某個子關系包含B,則該子關系中所有元組在B上的取值全部相同.
引理2 在關系R的非主鍵屬性上的嵌套操作不會改變數據實例結構.
結合引理1和引理2,設新引入服務模式S中的屬性Ri形成了目標模式T中的擴展屬性,Ri的所有祖先關系的集合為RS,對于每個關系Rj∈RS,設Rj的原子屬性集合為Aj,Aj在T中對應的屬性集合為map(Aj),則Ri在目標模式T中的位置可能存在于T內各個Aj的map(Aj)中的屬性所在的嵌套層次最深的關系中.此外,對于S中映射屬性所依賴的嵌套結構,不同映射屬性的最近公共祖先關系構成了它們共同依賴的內容,可以作為共同的上層嵌套結構在T中擴展,而由于下層的屬性平凡依賴于上層屬性,因此在S中以自頂向下的方式逐步確定擴展屬性的位置.算法1如下所示.
算法1擴展屬性推薦列表構建算法輸入:嵌套關系S,目標模式T,S與T的基本映射關系M輸出:推薦列表begin//S的最近公共祖先SCR←S.closestAncestor(S.TAttr∩M.Left)//T的最近公共祖先TCR←T.closestAncestor(M.map(S.TAttr∩M.Left))Head←S?SCR//S中不包含于SCR的嵌套結構addRecommend(“Head包含TCR”)//共同的上層嵌套結構//遞歸時,添加當前子關系對所有上層屬性的依賴關系loopforeachRi∈Head.Attr loopforeachrelationRj∈Head.ancestorRelations addRecommend(“Ri與Rj.AAttr中最低層屬性同層”);loopforeachRi∈SCR.RAttr∧Ri.TAttr∩M.Left≠? constructRecommendPositionList(Ri,T,M);//遞歸 endloopendloop //若最近公共祖先內存在映射屬性 if?Ai∈SCR.AAttr∧Ai∈M.Left loopforeachRj∈SCR.Attr∧(Rj?M.Left∨(Rj.TAttr∩M.Left=?))//非映射屬性和子關系 //這些屬性依賴于Aj addRecommend(“Rj與Ai位于同一關系”); endloopendif//對SCR中各個包含映射屬性的子關系 endloopend
以本文的典型案例為例,若S1為當前目標模式,S2為新引入服務的模式,那么在原子映射關系{類型,/醫(yī)療設備名稱>}之上,擴展屬性為S2中的“儲備量”.基于S2中的平凡依賴關系“(醫(yī)療設備名稱,儲備量)→儲備量”,則可確定擴展屬性“儲備量與類型”位于同一關系,最終形成新的目標模式:“物資需求<類型,數量,儲備量>”.
本節(jié)主要說明如何在新的目標模式確定后發(fā)現新引入服務與已集成服務的正確集成操作序列.
4.1 基本思路及正確性驗證
一般來說,任意數據服務的二元集成過程均可通過”連接+合并”的方式實現,連接是指多個服務通過連接類操作(join、connect)形成全部或部分目標模式,合并是指將多個能覆蓋目標模式的連接結果通過集合類操作合并到一起(union).
定理1 (正確性)多個數據服務{S}由任意的join、connect、union操作序列構成的集成形式能夠等價變換為由{S}的子集形成的多個連接運算之上的集合運算的集成形式.
證明思路:利用數學歸納法和連接、合并操作的分配律可以得證.此處略.
通過此定理,新引入服務可先與部分已引入服務進行連接,再將多個連接結果合并即可.這種“連接+合并”的表達方式借鑒了傳統(tǒng)的查詢發(fā)現方法[6],是本節(jié)方法的依據.
4.2 實現算法
首先規(guī)定幾個基本定義,對于T上的某一個原子屬性Ri,將模式中包含與Ri實現映射的屬性的服務集合稱為Ri的映射服務集合,將映射到Ri上的服務模式中的屬性集合稱為Ri的映射屬性集合.集成方式的發(fā)現方法通過以下3個步驟實現,具體包括:
1) 計算全部和部分覆蓋目標模式的服務集合及其覆蓋率;
該步驟主要發(fā)現可能通過連接操作形成全部或部分目標模式的服務集合,稱為候選服務集合.
定義7 候選服務集合.候選服務集合為目標模式各個原子屬性的映射服務集合的笛卡爾積.假設目標模式為T,數據服務的模式為S,S與T形成的原子屬性間的映射關系為MS,T,對于每個ti∈T.TAttr,令C(ti)={c?u∈c.TAttr,∈Mc,T}∪{ε},則候選服務集合L={cc=set(u),u=C(t1)×C(t2)×…×C(tn)}.其中:C(ti)表示目標模式T中的原子屬性ti的映射服務集合,ε表示空元素,set(u)表示將有序數據列表u變?yōu)闊o序的數據集合的函數.
上述笛卡爾積包含所有可能的服務連接方式,正確的連接序列為其子集.其中的空元素使得集合能夠僅覆蓋部分目標模式,表示某些屬性取值可為null,或者表示尚未完成連接的候選服務集合.計算過程中也要考慮同一候選服務集合中的不同服務的屬性與目標模式的映射關系存在包含的情況.例如服務A和服務B的屬性分別與目標模式中的t1及t2均具有映射關系,B包含A.將所有連接方式集合中存在包含關系的被包含的候選服務集刪除,將這一過程稱為候選服務集合的約減.
每個候選服務集合形成了對目標模式一定程度的覆蓋,反映了能夠通過連接形成目標模式的完整程度,是候選服務集合排序和選擇的重要指標.此外,集合內服務在相同屬性上的映射反映了它們的連接條件.
定義8 候選服務集合的覆蓋率.假設目標模式為T,其全部原子屬性集合為T.TAttr,目標模式上的映射關系集合為M,候選服務集合為L,則將L對T的覆蓋率CoverRate定義為T中與L中的服務有映射關系的原子屬性占T中所有原子屬性的比例.
2) 增量式的集成方式發(fā)現方法
增量式集成方法旨在發(fā)現新引入服務并與已有集成的結果直接集成.基本原則為盡量選擇覆蓋程度較低的候選服務集合進行擴展,表明尚有空間在該集合中添加新服務以增加覆蓋率.
假設S和T的原子屬性集合分別為SA和TA,集成S前T上的候選服務集的集合為L0,其中CoverRate=1的集合為L1,新候選服務集合L和模式T’的計算方法如表5所示.
聚合操作的廣義交換律、結合律和分配律保障了上述過程的正確性,實現了任意的服務引入順序均不影響最終集成結果的正確性,系統(tǒng)能夠即時處理數據源的動態(tài)加入,用戶不必拘泥于嚴格的服務引入和聚合操作的順序,并免除了需要多次引入同一服務和存儲臨時服務等繁瑣細節(jié).
表5 增量式集成策略Tab.5 Incremental integration rules
3) 用戶反饋的學習和集成過程優(yōu)化
系統(tǒng)計算出新的目標模式和集成方式后,可直接在嵌套表格中呈現,體現為模式變更和數據內容變化.用戶對系統(tǒng)推薦的集成操作可提供接受(隱式)或者拒絕(顯式)的反饋,并可用于對后續(xù)集成方案的優(yōu)化,實際上是對搜索空間的剪枝,具體策略如表6所示.
表6 基于用戶反饋的集成過程調整方法Tab.6 Integration process adjustment based on user-feedbacks
本文選擇一組具有代表性的數據集成需求,如表7所示.數據主要來自于互聯(lián)網的Deep Web數據和公開的API.實驗中,采用包含字符串、WordNet等多個匹配器的混合匹配計算工具.
表7 實驗中用戶的集成需求列表Tab.7 Integration needs in the experiments
本文所提出的交互式集成過程的效率可從如下兩方面評價:1) 推薦的操作數,反映了用戶需要提供的反饋的數量,實際中由于正確推薦是隱式的,因此采用拒絕的推薦數作為評價指標.包括:屬性合并、屬性擴展、位置確定、服務連接等操作.2) 推薦的正確率,反映了用戶的體驗效果.
由于本文的方法中包含了增量式和用戶反饋的機制,通過組合這兩種機制,形成下面3種實現方法:有用戶反饋非增量式方法、無用戶反饋增量式方法以及有用戶反饋的增量式方法.
實驗結果如圖2和3所示.在拒絕數上,基于有用戶反饋的增量式方法比有反饋非增量式和無反饋增量式的實現方法分別減少了52.5%和88.4%.在正確率上,基于有用戶反饋的增量式機制的正確率比無用戶反饋的增量式實現方法提高了0.52倍,與有用戶反饋非增量式的方法的正確率基本持平.
對結果分析如下:無反饋的方法無法糾正錯誤的映射關系,從而無法優(yōu)化后續(xù)服務連接方式,因此需要推薦的操作數相當多,正確率也較低.無增量式的方法需重復執(zhí)行已確認的步驟,錯誤的操作數多,但對錯誤率沒有多少影響.但反饋機制會大大減少錯誤的匹配數,因此步驟數沒有劇增.此外,服務數量越多,所需的操作數也就越多.相同方法在不同組別中的差異的原因在于模式的異構性的程度和規(guī)模不同,同時網頁抽取出的模式與Web API相比較為簡單.由上述實驗結果可以看出,本文方法在推薦的操作數和正確率上均有較好的表現,能夠提供良好的用戶體驗.
圖2 不同的機制下的各組實驗中用戶拒絕的推薦數Fig.2 Number of rejections of different groups
圖3 不同的機制下的各組實驗的推薦正確率Fig.3 Recommendation accuracy of different groups
集成邏輯的復雜性和用戶有限的操作能力之間的矛盾是用戶實現多源數據按需集成的主要障礙.解決這一問題可從兩方面考慮,一方面可以向用戶提供簡單的可視化集成操作,另一方面可以利用已有的自動化集成技術,進行人機協(xié)作的集成過程.
前者包括各類數據mashup系統(tǒng),它借鑒了最終用戶編程的思想,向用戶提供各類易于操作的界面級構件和操作方法.Spreadsheet[7]和流程圖[8]是兩種主要形式.對于各類Mashup方法而言,盡管存在多種優(yōu)化方法,它們仍然是由用戶完全主導的,用戶需了解各類操作的含義和用法以及復雜集成邏輯的構造過程,對用戶的技術要求仍然較高.
近年來出現的演化式數據集成方法提供了一種用戶操作更為簡單的數據集成方式.為了應對開放互聯(lián)網環(huán)境下數據源的大規(guī)模、動態(tài)、不確定、缺乏統(tǒng)一規(guī)范等特征,出現了包括數據空間、Pay-as-you-go的漸進式集成方法、不確定性數據集成[4,9]等概念和技術.對于演化式集成方法,盡管能夠大大降低用戶操作的復雜性,但卻在集成結果的正確性和完備性上存在較大的局限性.
本文嘗試尋找兩者平衡,一方面能夠利用自動化集成技術和用戶反饋學習方法降低用戶代價,另一方面也希望能夠提供正確性、表達能力等方面的保障.
本文提出了一種支持數據源動態(tài)加入的交互式數據按需集成方法,該方法在可視化的嵌套表格中實現,利用語義映射工具提供半自動化的支持,漸進式地向用戶推薦可能的集成結果和方式,屏蔽集成邏輯和語義映射關系定義的復雜性.提供了增量式的最優(yōu)集成方案的計算方法,最大程度重用已有集成結果,并且利用用戶反饋有效地進行剪枝,優(yōu)化集成過程.該方法保證任意的數據源引入順序條件下集成結果的正確性,即能夠支持新數據源的動態(tài)加入.通過實驗分析,驗證了本文具有良好的推薦效果和用戶體驗.
[1] CAFARELLA M J, HALEVY A, MADHAVAN J. Structured data on the web[J]. Communications of the ACM, 2011, 54(2): 72-79.
[2] TALUKDAR P P, IVES Z G, PEREIRA F. Automatically incorporating new sources in keyword search-based data integration[C]//Proc of the 2010SIGMOD Int’l Conf on Management of Data. Indianapolis, 2010: 387-398.
[3] 溫彥, 劉晨, 韓燕波. 一種用戶主導的跨組織數據按需集成方法[J]. 西安交通大學學報(自然版). 2013,47(2):116-123
[4] 劉曉光, 謝曉堯. 一種結合遺忘機制與加權二部圖的推薦算法[J].河南科技大學學報(自然科學版),2015, 36(3): 48-53.
[5] HARA C S, DAVIDSON S B. Reasoning about nested functional dependencies[C]//Proc of the 18thACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Philadelphia, 1999: 91-100.
[6] MILLER R J, HAAS L M, Hernandez M A. Schema mapping as query discovery[C]//Proc of the 26thInt’l Conf on Very Large Data Bases. Cairo, 2000: 77-88.
[7] LIU C, WANG J, HAN Y. Mashroom+: an interactive data mashup approach with uncertainty handling[J]. Journal of grid computing, 2014, 12(2): 221-244.
[8] JONES M C, CHURCHILL E F. Conversations in developer communities: a preliminary analysis of the yahoo!Pipes community[C]//Proc of the 4thInt’l Conf on Communities and Technologies. University Park, 2009: 195-204.
[9] BELHAJJAME K, PATON N W, EMBURY S M, et al. Incrementally improving dataspaces based on user feedback[J]. Information systems, 2013, 38(5): 656-687.
(責任編輯:王浩毅)
Interactive Data Integration Method Supporting Dynamic New Source Incorporation
WEN Yan, QIU Liqing, CHEN Xin, ZHANG Feng
(CollegeofInformationandEngineering,ShandongUniversityofScienceand
Technology,Qingdao266590,China)
A method of interactive data integration was proposed, which could support dynamic data sources incorporation. The method used data service model which could provid a visualized inbeded table as the just-in-time integration environment, and used semantic mapping tool to provide semi-automation support. This approach ensured that random data source introducing order would not affect the correctness of the results. An incremental method was provided to generate optimal integrated solutions when new sources were introduced, and user-feedbacks were used to prune and optimize the subsequent integration process. The experimental analysis proved that the proposed method was valid.
data integration; interactive data integration; on-demand data integration; dynamic data source incorporation
2016-07-04
教育部博士點基金(20133718120011);2014青島市博士后研究人員應用研究項目;國家自然科學基金資助項目(61502281).
溫彥(1984—),女,山西晉中人,講師,主要從事數據集成、Web數據管理的研究,E-mail:wenyanxxxy@163.com.
溫彥,仇麗青,陳欣,等.一種支持數據源動態(tài)加入的交互式數據集成方法[J] .鄭州大學學報(理學版),2016,48(4):36-43.
TP312
A
1671-6841(2016)04-0036-08
10.13705/j.issn.1671-6841.2016650