溫 彥, 仇麗青， 陳 欣， 張 峰

(山東科技大學(xué) 信息科學(xué)與工程學(xué)院 山東 青島 266590)

?

一種支持?jǐn)?shù)據(jù)源動(dòng)態(tài)加入的交互式數(shù)據(jù)集成方法

溫 彥, 仇麗青， 陳 欣， 張 峰

(山東科技大學(xué) 信息科學(xué)與工程學(xué)院 山東 青島 266590)

提出了一種支持?jǐn)?shù)據(jù)源動(dòng)態(tài)加入的交互式數(shù)據(jù)集成方法.該方法利用基于可視化嵌套表格提供所見即所得的即時(shí)集成環(huán)境，利用語義映射工具提供半自動(dòng)化的支持，漸進(jìn)式地向用戶推薦可能的集成結(jié)果和方式，屏蔽集成過程的復(fù)雜性，并保證任意的數(shù)據(jù)源引入順序條件下集成結(jié)果的正確性.采用增量式的方法計(jì)算新數(shù)據(jù)源加入時(shí)的最優(yōu)集成方案，利用用戶反饋有效地進(jìn)行剪枝，優(yōu)化集成過程.通過實(shí)驗(yàn)驗(yàn)證了此方法的有效性.

數(shù)據(jù)集成； 交互式； 按需集成； 數(shù)據(jù)源動(dòng)態(tài)加入

0 引言

互聯(lián)網(wǎng)正在演變?yōu)槠袢祟愖畲蟮膮f(xié)同計(jì)算平臺(tái)，其上的數(shù)據(jù)規(guī)模呈指數(shù)級增長，其中結(jié)構(gòu)化數(shù)據(jù)顯著增加，且用戶對結(jié)構(gòu)化對象的查詢占據(jù)了所有Web檢索的一半以上并呈現(xiàn)出跨領(lǐng)域、綜合性的特點(diǎn)[1].此外，用戶的個(gè)性化數(shù)據(jù)需求愈發(fā)明顯，具有即時(shí)性、不可重復(fù)等特點(diǎn).因此如何支持最終用戶快速按需集成互聯(lián)網(wǎng)數(shù)據(jù)，成為亟待解決的問題.解決該問題需要克服前所未有的新的挑戰(zhàn)，使得傳統(tǒng)的重量級集成方法不再適用：數(shù)據(jù)規(guī)模大、動(dòng)態(tài)性強(qiáng)，難以建立和維護(hù)統(tǒng)一的中間模式，且需要應(yīng)對數(shù)據(jù)源的動(dòng)態(tài)加入和退出[2]；數(shù)據(jù)內(nèi)容高度自治，缺乏足夠的語義信息和統(tǒng)一的語義規(guī)范，給集成帶來較大困難；即時(shí)、個(gè)性化的集成需求使得方法必須易于使用.

已有一些工作針對互聯(lián)網(wǎng)環(huán)境下的跨域數(shù)據(jù)集成，然而這些方法對用戶而言是困難的，主要表現(xiàn)在：1) 用戶理解并實(shí)現(xiàn)復(fù)雜的集成邏輯是困難的，包括各類數(shù)據(jù)處理和控制邏輯操作，且需要按照正確的順序來引入數(shù)據(jù)源、執(zhí)行集成操作.2) 跨域數(shù)據(jù)普遍存在語義層面的異構(gòu)性，用戶正確指定數(shù)據(jù)的語義映射關(guān)系并進(jìn)行可視化表示是困難的.3) 面對新數(shù)據(jù)源動(dòng)態(tài)加入和退出，用戶需要即時(shí)修正集成邏輯并保證集成結(jié)果的正確性，對用戶而言也是困難的.

為了克服上述困難，本文基于已有數(shù)據(jù)服務(wù)的模型和其上定義的聚合操作[3]，以及嵌套表格提供的所見即所得的集成環(huán)境和語義映射工具提供的匹配方法，提供一種漸進(jìn)式的交互式集成過程向用戶推薦可能的集成結(jié)果，屏蔽語義映射和集成操作的復(fù)雜性，同時(shí)保證在任意的數(shù)據(jù)源引入順序條件下(即數(shù)據(jù)源動(dòng)態(tài)加入過程)集成結(jié)果的正確性.集成過程采用增量式的方法計(jì)算新資源加入時(shí)的最優(yōu)集成方案，并利用用戶反饋有效地進(jìn)行剪枝，優(yōu)化集成過程，改進(jìn)用戶體驗(yàn).

1 基本概念

我們在之前的工作中提出了數(shù)據(jù)服務(wù)模型[3]，它基于嵌套關(guān)系定義，能夠表達(dá)互聯(lián)網(wǎng)上常見的結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)，且具有良好的可視化形式，嵌套關(guān)系和數(shù)據(jù)服務(wù)的定義如下.

定義1 (嵌套關(guān)系) 一個(gè)嵌套關(guān)系包含模式和實(shí)例.令A(yù)是屬性名稱全集，嵌套關(guān)系模式R(S)被定義為：R(S)=(A1,A2,…,Am)，其中：R∈A.R是關(guān)系模式的名稱，S是屬性名稱列表.Ai是原子屬性或者形如Ri(Si)的子關(guān)系屬性.模式R(S)的一個(gè)實(shí)例是形如(a1,a2,…,am)的有序元組集合，若Ai是原子屬性，則ai是基礎(chǔ)數(shù)據(jù)值；若Ai是關(guān)系模式，則ai是Ai的實(shí)例.

定義2(數(shù)據(jù)服務(wù)) 數(shù)據(jù)服務(wù)是如下五元組：ds=，uri是其web可訪問位置以及其全局標(biāo)識(shí)，name是其名稱，params是其輸入?yún)?shù)，schema是服務(wù)所暴露數(shù)據(jù)的模式，表示為嵌套關(guān)系模式，instance是該服務(wù)運(yùn)行時(shí)數(shù)據(jù)實(shí)例，表示為嵌套關(guān)系實(shí)例.

在數(shù)據(jù)服務(wù)上定義了基于映射關(guān)系的服務(wù)輸出輸入連接(connect)、服務(wù)輸出連接(join)和合并(union)等操作.基于嵌套關(guān)系代數(shù)的理論基礎(chǔ)，這些操作滿足廣義交換律、結(jié)合律和分配律.

2 集成典型案例

本節(jié)通過一個(gè)典型案例來說明本文所提方法的基本效果.該案例的目標(biāo)為獲得滿足火災(zāi)救援需求的設(shè)備儲(chǔ)備信息視圖.假設(shè)涉及的數(shù)據(jù)服務(wù)模式如表1～表4中的S1～S4所示，它們均不包含輸入?yún)?shù).

表1 物資需求(S1)Tab.1 Material reserves(S1)

表2 醫(yī)療設(shè)備儲(chǔ)備(S2)Tab.2 Medical equipment storage(S2)

表3 滅火設(shè)備型號登記(S3)Tab.3 Fire extinguishing equipment models registration(S3)

表4 設(shè)備庫存(S4)
Tab.4 Equipment storage(S4)

設(shè)備型號各倉庫存量倉庫庫存量MTZ?5S1500S3300MTZ?20S3200MTZ?50S1400S3300

3 目標(biāo)模式生成

本文的集成過程分為集成目標(biāo)模式生成和增量式集成方式發(fā)現(xiàn)兩個(gè)階段.生成結(jié)果的數(shù)據(jù)模式稱為目標(biāo)模式.該階段關(guān)注新引入服務(wù)(設(shè)為S)與當(dāng)前目標(biāo)模式(設(shè)為T)的屬性合并、擴(kuò)展(增加新屬性)和層次結(jié)構(gòu)的改變.基本思路為，首先根據(jù)S與T之間的原子屬性上的基本映射關(guān)系形成新的目標(biāo)模式T′.而后根據(jù)S的嵌套結(jié)構(gòu)所反映的數(shù)據(jù)依賴關(guān)系來確定T′的層次結(jié)構(gòu).

3.1 屬性映射關(guān)系的計(jì)算和推薦

定義3 模式匹配擴(kuò)展圖.嵌套模式R1和R2的所有原子屬性集合分別為T和S，在T中為S中的每個(gè)元素s構(gòu)建附加節(jié)點(diǎn)s′構(gòu)成Ts′={s′}，并令T′=T∪Ts′，在S中為T中的每個(gè)元素t構(gòu)建附加節(jié)點(diǎn)t′構(gòu)成St′={t′}，并令S′=S∪St′.構(gòu)造二部圖G=為T和S的模式匹配擴(kuò)展圖，其中：N=T′∪S′，e∈E，e=，a∈T′，b∈S′，w的計(jì)算方法包括如下3種情況：

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()))/2.

根據(jù)上述定義，可直接得到性質(zhì)1.

性質(zhì)1 所有擴(kuò)展節(jié)點(diǎn)上只有一條邊，連接其源節(jié)點(diǎn).

定義3的2)和3)中除以2的含義為：使得連接兩個(gè)屬性的邊通過擴(kuò)展節(jié)點(diǎn)提供的兩條擴(kuò)展邊的權(quán)值和不大于原匹配屬性對的權(quán)值.根據(jù)性質(zhì)1，擴(kuò)展圖中的附加節(jié)點(diǎn)s′與其源節(jié)點(diǎn)s構(gòu)成的邊表示源節(jié)點(diǎn)s不與T中的所有節(jié)點(diǎn)匹配，即為擴(kuò)展屬性.可在模式匹配擴(kuò)展圖中使用KM算法獲得最大匹配.圖1為示例.假設(shè)兩模式原子屬性間的匹配及其置信度如圖1(a)所示，擴(kuò)展后如圖1(b)，兩圖的帶權(quán)最大二分匹配為加粗黑線，左圖的質(zhì)量為1.62，右圖為1.895，t1、s1為擴(kuò)展屬性.

圖1 模式擴(kuò)展圖的最大二部匹配示例Fig.1 Maximum bipartite graph mappings for schema extending graph

3.2 擴(kuò)展屬性位置的計(jì)算和推薦

盡管嵌套和解嵌套操作可形成多種合理的層次結(jié)構(gòu)，不存在唯一最優(yōu)結(jié)構(gòu)，然而合并過程應(yīng)當(dāng)盡量保持原嵌套層次表示的數(shù)據(jù)依賴關(guān)系.因此可根據(jù)此依賴關(guān)系來預(yù)測并推薦擴(kuò)展屬性的位置.

定義4 嵌套關(guān)系屬性的層次關(guān)系.嵌套關(guān)系模式中的屬性(原子、子關(guān)系屬性)間在嵌套結(jié)構(gòu)上的關(guān)系分為4種：上層、下層、平級、無關(guān).屬性A為B的上層屬性當(dāng)且僅當(dāng)A所在的嵌套關(guān)系R1可遞歸包含B所在的嵌套關(guān)系R2，此時(shí)稱B為A的下層屬性，R1為B、R2的祖先關(guān)系，B、R2為R1的子孫關(guān)系/屬性，若A和B為同一個(gè)嵌套關(guān)系的屬性，則A、B互為彼此的平級屬性，若A、B不滿足3種關(guān)系，則稱A、B無關(guān).A的所有祖先關(guān)系與B的所有祖先關(guān)系中相交的部分稱為A和B的公共上層關(guān)系，其中嵌套層次最深的子關(guān)系稱為A、B的最近公共祖先關(guān)系.A、B的距離是指A、B到兩者的最近公共祖先關(guān)系的嵌套路徑長度之和.如嵌套模式A,F>中，B為D、E、G、H的上層屬性，D與E、G與H互為平級屬性，D-G、D-H、E-G、E-H、C-F均為無關(guān)屬性，它們的最近公共祖先關(guān)系均為A，D-H的距離為4，C-F的距離為2.

可根據(jù)嵌套結(jié)構(gòu)的形態(tài)描述嵌套關(guān)系整體及其子結(jié)構(gòu)的數(shù)據(jù)依賴關(guān)系特征，包含全局依賴和局部依賴[5]，前者表示在整個(gè)嵌套結(jié)構(gòu)上的依賴關(guān)系，后者表示僅在某個(gè)子關(guān)系內(nèi)部成立的依賴關(guān)系.兩者主鍵只包含原子屬性.例如S4中“(設(shè)備型號，倉庫)→庫存量”為全局依賴，“倉庫→庫存量”為局部依賴，可以看出，全局依賴的主鍵分布在不同的嵌套層次中，形成了局部依賴.

定義5 嵌套關(guān)系的全局依賴關(guān)系.對于嵌套關(guān)系模式R，其上的全局依賴關(guān)系的形式為：(A1,A2,…,An)→GB，其中Ai∈R.TAttr，i=1,2,…,n，B為R中某嵌套層次內(nèi)的原子屬性或子關(guān)系屬性，表示(A1,A2,…,An)的值能夠唯一確定B的取值(B為原子屬性時(shí)，表示簡單值，B為子關(guān)系屬性時(shí)，表示B上的元組集合)，并將{A1,A2,…,An}稱為B的依賴屬性集.假設(shè)B所有祖先關(guān)系的原子屬性集合為A，則A→GB被稱為B上的平凡全局依賴關(guān)系，并將A稱為B的平凡依賴屬性集.

定義6 嵌套關(guān)系的局部依賴關(guān)系.對于嵌套關(guān)系模式R，其上的局部依賴關(guān)系的形式為：(L1,L2,…,Lm)→LB成立當(dāng)且僅當(dāng)存在R上的全局依賴關(guān)系(A1,A2,…,An)→GB，使得{L1,L2,…,Lm}?{A1,A2,…,An},且(L1,L2,…,Lm)與B在同一子關(guān)系內(nèi).

根據(jù)上述對嵌套結(jié)構(gòu)及其依賴關(guān)系的分析，擴(kuò)展屬性位置的推薦原則為維護(hù)屬性間的數(shù)據(jù)依賴關(guān)系并盡量保持它們在原數(shù)據(jù)模式中的位置關(guān)系，使得相同屬性對間的距離在數(shù)據(jù)服務(wù)中和在目標(biāo)模式中的變化較小.某些全局依賴關(guān)系可能不包含在所有的平凡全局依賴關(guān)系集合內(nèi)，但在缺乏明確定義的依賴關(guān)系的情況下，推薦均基于平凡依賴關(guān)系.根據(jù)定義4～6，得到引理1.

引理1 假設(shè)在嵌套關(guān)系模式R中，存在(A1,A2,…,An)→GB，A1,A2,…,An中不存在不相關(guān)的屬性對，Rj為(A1,A2,…,An)中嵌套層次最深的屬性Aj所在的關(guān)系，則若通過嵌套操作使得Rj的某個(gè)子關(guān)系包含B，則該子關(guān)系中所有元組在B上的取值全部相同.

引理2 在關(guān)系R的非主鍵屬性上的嵌套操作不會(huì)改變數(shù)據(jù)實(shí)例結(jié)構(gòu).

結(jié)合引理1和引理2，設(shè)新引入服務(wù)模式S中的屬性Ri形成了目標(biāo)模式T中的擴(kuò)展屬性，Ri的所有祖先關(guān)系的集合為RS，對于每個(gè)關(guān)系Rj∈RS，設(shè)Rj的原子屬性集合為Aj，Aj在T中對應(yīng)的屬性集合為map(Aj)，則Ri在目標(biāo)模式T中的位置可能存在于T內(nèi)各個(gè)Aj的map(Aj)中的屬性所在的嵌套層次最深的關(guān)系中.此外，對于S中映射屬性所依賴的嵌套結(jié)構(gòu)，不同映射屬性的最近公共祖先關(guān)系構(gòu)成了它們共同依賴的內(nèi)容，可以作為共同的上層嵌套結(jié)構(gòu)在T中擴(kuò)展，而由于下層的屬性平凡依賴于上層屬性，因此在S中以自頂向下的方式逐步確定擴(kuò)展屬性的位置.算法1如下所示.

算法1擴(kuò)展屬性推薦列表構(gòu)建算法輸入：嵌套關(guān)系S，目標(biāo)模式T，S與T的基本映射關(guān)系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的嵌套結(jié)構(gòu)addRecommend(“Head包含TCR”)//共同的上層嵌套結(jié)構(gòu)//遞歸時(shí)，添加當(dāng)前子關(guān)系對所有上層屬性的依賴關(guān)系loopforeachRi∈Head．Attr loopforeachrelationRj∈Head．a(chǎn)ncestorRelations addRecommend(“Ri與Rj．AAttr中最低層屬性同層”)；loopforeachRi∈SCR．RAttr∧Ri．TAttr∩M．Left≠? constructRecommendPositionList(Ri，T，M)；//遞歸 endloopendloop //若最近公共祖先內(nèi)存在映射屬性 if?Ai∈SCR．AAttr∧Ai∈M．Left loopforeachRj∈SCR．Attr∧(Rj?M．Left∨(Rj．TAttr∩M．Left=?))//非映射屬性和子關(guān)系 //這些屬性依賴于Aj addRecommend(“Rj與Ai位于同一關(guān)系”)； endloopendif//對SCR中各個(gè)包含映射屬性的子關(guān)系 endloopend

以本文的典型案例為例，若S1為當(dāng)前目標(biāo)模式，S2為新引入服務(wù)的模式，那么在原子映射關(guān)系{}之上，擴(kuò)展屬性為S2中的“儲(chǔ)備量”.基于S2中的平凡依賴關(guān)系“(醫(yī)療設(shè)備名稱，儲(chǔ)備量)→儲(chǔ)備量”，則可確定擴(kuò)展屬性“儲(chǔ)備量與類型”位于同一關(guān)系，最終形成新的目標(biāo)模式：“物資需求<類型，數(shù)量，儲(chǔ)備量>”.

4 集成方式的增量式發(fā)現(xiàn)

本節(jié)主要說明如何在新的目標(biāo)模式確定后發(fā)現(xiàn)新引入服務(wù)與已集成服務(wù)的正確集成操作序列.

4.1 基本思路及正確性驗(yàn)證

一般來說，任意數(shù)據(jù)服務(wù)的二元集成過程均可通過”連接+合并”的方式實(shí)現(xiàn)，連接是指多個(gè)服務(wù)通過連接類操作(join、connect)形成全部或部分目標(biāo)模式，合并是指將多個(gè)能覆蓋目標(biāo)模式的連接結(jié)果通過集合類操作合并到一起(union).

定理1 (正確性)多個(gè)數(shù)據(jù)服務(wù){(diào)S}由任意的join、connect、union操作序列構(gòu)成的集成形式能夠等價(jià)變換為由{S}的子集形成的多個(gè)連接運(yùn)算之上的集合運(yùn)算的集成形式.

證明思路：利用數(shù)學(xué)歸納法和連接、合并操作的分配律可以得證.此處略.

通過此定理，新引入服務(wù)可先與部分已引入服務(wù)進(jìn)行連接，再將多個(gè)連接結(jié)果合并即可.這種“連接+合并”的表達(dá)方式借鑒了傳統(tǒng)的查詢發(fā)現(xiàn)方法[6]，是本節(jié)方法的依據(jù).

4.2 實(shí)現(xiàn)算法

首先規(guī)定幾個(gè)基本定義，對于T上的某一個(gè)原子屬性Ri，將模式中包含與Ri實(shí)現(xiàn)映射的屬性的服務(wù)集合稱為Ri的映射服務(wù)集合，將映射到Ri上的服務(wù)模式中的屬性集合稱為Ri的映射屬性集合.集成方式的發(fā)現(xiàn)方法通過以下3個(gè)步驟實(shí)現(xiàn)，具體包括：

1) 計(jì)算全部和部分覆蓋目標(biāo)模式的服務(wù)集合及其覆蓋率；

該步驟主要發(fā)現(xiàn)可能通過連接操作形成全部或部分目標(biāo)模式的服務(wù)集合，稱為候選服務(wù)集合.

定義7 候選服務(wù)集合.候選服務(wù)集合為目標(biāo)模式各個(gè)原子屬性的映射服務(wù)集合的笛卡爾積.假設(shè)目標(biāo)模式為T，數(shù)據(jù)服務(wù)的模式為S，S與T形成的原子屬性間的映射關(guān)系為MS,T，對于每個(gè)ti∈T.TAttr，令C(ti)={c?u∈c.TAttr,∈Mc,T}∪{ε}，則候選服務(wù)集合L={cc=set(u),u=C(t1)×C(t2)×…×C(tn)}.其中:C(ti)表示目標(biāo)模式T中的原子屬性ti的映射服務(wù)集合，ε表示空元素，set(u)表示將有序數(shù)據(jù)列表u變?yōu)闊o序的數(shù)據(jù)集合的函數(shù).

上述笛卡爾積包含所有可能的服務(wù)連接方式，正確的連接序列為其子集.其中的空元素使得集合能夠僅覆蓋部分目標(biāo)模式，表示某些屬性取值可為null，或者表示尚未完成連接的候選服務(wù)集合.計(jì)算過程中也要考慮同一候選服務(wù)集合中的不同服務(wù)的屬性與目標(biāo)模式的映射關(guān)系存在包含的情況.例如服務(wù)A和服務(wù)B的屬性分別與目標(biāo)模式中的t1及t2均具有映射關(guān)系，B包含A.將所有連接方式集合中存在包含關(guān)系的被包含的候選服務(wù)集刪除，將這一過程稱為候選服務(wù)集合的約減.

每個(gè)候選服務(wù)集合形成了對目標(biāo)模式一定程度的覆蓋，反映了能夠通過連接形成目標(biāo)模式的完整程度，是候選服務(wù)集合排序和選擇的重要指標(biāo).此外，集合內(nèi)服務(wù)在相同屬性上的映射反映了它們的連接條件.

定義8 候選服務(wù)集合的覆蓋率.假設(shè)目標(biāo)模式為T，其全部原子屬性集合為T.TAttr，目標(biāo)模式上的映射關(guān)系集合為M，候選服務(wù)集合為L，則將L對T的覆蓋率CoverRate定義為T中與L中的服務(wù)有映射關(guān)系的原子屬性占T中所有原子屬性的比例.

2) 增量式的集成方式發(fā)現(xiàn)方法

增量式集成方法旨在發(fā)現(xiàn)新引入服務(wù)并與已有集成的結(jié)果直接集成.基本原則為盡量選擇覆蓋程度較低的候選服務(wù)集合進(jìn)行擴(kuò)展，表明尚有空間在該集合中添加新服務(wù)以增加覆蓋率.

假設(shè)S和T的原子屬性集合分別為SA和TA，集成S前T上的候選服務(wù)集的集合為L0，其中CoverRate=1的集合為L1，新候選服務(wù)集合L和模式T’的計(jì)算方法如表5所示.

聚合操作的廣義交換律、結(jié)合律和分配律保障了上述過程的正確性，實(shí)現(xiàn)了任意的服務(wù)引入順序均不影響最終集成結(jié)果的正確性，系統(tǒng)能夠即時(shí)處理數(shù)據(jù)源的動(dòng)態(tài)加入，用戶不必拘泥于嚴(yán)格的服務(wù)引入和聚合操作的順序，并免除了需要多次引入同一服務(wù)和存儲(chǔ)臨時(shí)服務(wù)等繁瑣細(xì)節(jié).

表5 增量式集成策略Tab.5 Incremental integration rules

3) 用戶反饋的學(xué)習(xí)和集成過程優(yōu)化

系統(tǒng)計(jì)算出新的目標(biāo)模式和集成方式后，可直接在嵌套表格中呈現(xiàn)，體現(xiàn)為模式變更和數(shù)據(jù)內(nèi)容變化.用戶對系統(tǒng)推薦的集成操作可提供接受(隱式)或者拒絕(顯式)的反饋，并可用于對后續(xù)集成方案的優(yōu)化，實(shí)際上是對搜索空間的剪枝，具體策略如表6所示.

表6 基于用戶反饋的集成過程調(diào)整方法Tab.6 Integration process adjustment based on user-feedbacks

5 實(shí)驗(yàn)分析

本文選擇一組具有代表性的數(shù)據(jù)集成需求，如表7所示.數(shù)據(jù)主要來自于互聯(lián)網(wǎng)的Deep Web數(shù)據(jù)和公開的API.實(shí)驗(yàn)中，采用包含字符串、WordNet等多個(gè)匹配器的混合匹配計(jì)算工具.

表7 實(shí)驗(yàn)中用戶的集成需求列表Tab.7 Integration needs in the experiments

本文所提出的交互式集成過程的效率可從如下兩方面評價(jià)：1) 推薦的操作數(shù)，反映了用戶需要提供的反饋的數(shù)量，實(shí)際中由于正確推薦是隱式的，因此采用拒絕的推薦數(shù)作為評價(jià)指標(biāo).包括：屬性合并、屬性擴(kuò)展、位置確定、服務(wù)連接等操作.2) 推薦的正確率，反映了用戶的體驗(yàn)效果.

由于本文的方法中包含了增量式和用戶反饋的機(jī)制，通過組合這兩種機(jī)制，形成下面3種實(shí)現(xiàn)方法：有用戶反饋非增量式方法、無用戶反饋增量式方法以及有用戶反饋的增量式方法.

實(shí)驗(yàn)結(jié)果如圖2和3所示.在拒絕數(shù)上，基于有用戶反饋的增量式方法比有反饋非增量式和無反饋增量式的實(shí)現(xiàn)方法分別減少了52.5%和88.4%.在正確率上，基于有用戶反饋的增量式機(jī)制的正確率比無用戶反饋的增量式實(shí)現(xiàn)方法提高了0.52倍，與有用戶反饋非增量式的方法的正確率基本持平.

對結(jié)果分析如下：無反饋的方法無法糾正錯(cuò)誤的映射關(guān)系，從而無法優(yōu)化后續(xù)服務(wù)連接方式，因此需要推薦的操作數(shù)相當(dāng)多，正確率也較低.無增量式的方法需重復(fù)執(zhí)行已確認(rèn)的步驟，錯(cuò)誤的操作數(shù)多，但對錯(cuò)誤率沒有多少影響.但反饋機(jī)制會(huì)大大減少錯(cuò)誤的匹配數(shù)，因此步驟數(shù)沒有劇增.此外，服務(wù)數(shù)量越多，所需的操作數(shù)也就越多.相同方法在不同組別中的差異的原因在于模式的異構(gòu)性的程度和規(guī)模不同，同時(shí)網(wǎng)頁抽取出的模式與Web API相比較為簡單.由上述實(shí)驗(yàn)結(jié)果可以看出，本文方法在推薦的操作數(shù)和正確率上均有較好的表現(xiàn)，能夠提供良好的用戶體驗(yàn).

圖2 不同的機(jī)制下的各組實(shí)驗(yàn)中用戶拒絕的推薦數(shù)Fig.2 Number of rejections of different groups

圖3 不同的機(jī)制下的各組實(shí)驗(yàn)的推薦正確率Fig.3 Recommendation accuracy of different groups

6 相關(guān)工作

集成邏輯的復(fù)雜性和用戶有限的操作能力之間的矛盾是用戶實(shí)現(xiàn)多源數(shù)據(jù)按需集成的主要障礙.解決這一問題可從兩方面考慮，一方面可以向用戶提供簡單的可視化集成操作，另一方面可以利用已有的自動(dòng)化集成技術(shù)，進(jìn)行人機(jī)協(xié)作的集成過程.

前者包括各類數(shù)據(jù)mashup系統(tǒng)，它借鑒了最終用戶編程的思想，向用戶提供各類易于操作的界面級構(gòu)件和操作方法.Spreadsheet[7]和流程圖[8]是兩種主要形式.對于各類Mashup方法而言，盡管存在多種優(yōu)化方法，它們?nèi)匀皇怯捎脩敉耆鲗?dǎo)的，用戶需了解各類操作的含義和用法以及復(fù)雜集成邏輯的構(gòu)造過程，對用戶的技術(shù)要求仍然較高.

近年來出現(xiàn)的演化式數(shù)據(jù)集成方法提供了一種用戶操作更為簡單的數(shù)據(jù)集成方式.為了應(yīng)對開放互聯(lián)網(wǎng)環(huán)境下數(shù)據(jù)源的大規(guī)模、動(dòng)態(tài)、不確定、缺乏統(tǒng)一規(guī)范等特征，出現(xiàn)了包括數(shù)據(jù)空間、Pay-as-you-go的漸進(jìn)式集成方法、不確定性數(shù)據(jù)集成[4,9]等概念和技術(shù).對于演化式集成方法，盡管能夠大大降低用戶操作的復(fù)雜性，但卻在集成結(jié)果的正確性和完備性上存在較大的局限性.

本文嘗試尋找兩者平衡，一方面能夠利用自動(dòng)化集成技術(shù)和用戶反饋學(xué)習(xí)方法降低用戶代價(jià)，另一方面也希望能夠提供正確性、表達(dá)能力等方面的保障.

7 結(jié)論

本文提出了一種支持?jǐn)?shù)據(jù)源動(dòng)態(tài)加入的交互式數(shù)據(jù)按需集成方法，該方法在可視化的嵌套表格中實(shí)現(xiàn)，利用語義映射工具提供半自動(dòng)化的支持，漸進(jìn)式地向用戶推薦可能的集成結(jié)果和方式，屏蔽集成邏輯和語義映射關(guān)系定義的復(fù)雜性.提供了增量式的最優(yōu)集成方案的計(jì)算方法，最大程度重用已有集成結(jié)果，并且利用用戶反饋有效地進(jìn)行剪枝，優(yōu)化集成過程.該方法保證任意的數(shù)據(jù)源引入順序條件下集成結(jié)果的正確性，即能夠支持新數(shù)據(jù)源的動(dòng)態(tài)加入.通過實(shí)驗(yàn)分析，驗(yàn)證了本文具有良好的推薦效果和用戶體驗(yàn).

[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] 溫彥, 劉晨, 韓燕波. 一種用戶主導(dǎo)的跨組織數(shù)據(jù)按需集成方法[J]. 西安交通大學(xué)學(xué)報(bào)(自然版). 2013,47(2):116-123

[4] 劉曉光, 謝曉堯. 一種結(jié)合遺忘機(jī)制與加權(quán)二部圖的推薦算法[J].河南科技大學(xué)學(xué)報(bào)(自然科學(xué)版),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.

(責(zé)任編輯：王浩毅)

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

教育部博士點(diǎn)基金(20133718120011)；2014青島市博士后研究人員應(yīng)用研究項(xiàng)目；國家自然科學(xué)基金資助項(xiàng)目(61502281).

溫彥(1984—)，女，山西晉中人，講師，主要從事數(shù)據(jù)集成、Web數(shù)據(jù)管理的研究，E-mail:wenyanxxxy@163.com.

溫彥，仇麗青，陳欣,等．一種支持?jǐn)?shù)據(jù)源動(dòng)態(tài)加入的交互式數(shù)據(jù)集成方法[J] ．鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2016，48(4)：36-43．

TP312

A

1671-6841(2016)04-0036-08

10.13705/j.issn.1671-6841.2016650