面向數據融合的半環溯源計算方法

薛見新 申德榮 寇 月 聶鐵錚 于 戈

（東北大學信息科學與工程學院 沈陽 110819）（xuejianxin＠research．neu．edu．cn）

面向數據融合的半環溯源計算方法

薛見新 申德榮 寇 月 聶鐵錚 于 戈

（東北大學信息科學與工程學院 沈陽 110819）
（xuejianxin＠research．neu．edu．cn）

數據融合是集成數據的質量保證和分析挖掘的前提條件；然而，數據融合作為一個整體對于用戶來講是一個黑盒過程，使得當前數據融合過程缺乏可解釋性和可調試性．為了便于數據融合過程中有效的沖突檢測和調試，需要利用數據溯源技術建立數據融合的可回溯機制．數據溯源描述了數據產生并隨著時間推移而演變的整個過程，半環溯源模型作為一種經典的數據溯源表示形式，不僅能表示結果數據是由哪些數據派生的，而且還能夠描述這些數據以什么方式進行派生．主要研究用于數據融合的半環溯源的計算問題．用于數據融合的半環溯源計算是一個pay as you go的模式，計算數據的溯源信息是一個非常耗時的過程．首先，提出一種基于Kleene序列的近似迭代方法，并證明了該方法與半環溯源的派生樹定義的關系，從而證明了該方法的正確性．然后，提出了一種類牛頓序列，這種方法比Kleene序列有更好的收斂性．由于遞歸的引入可能會導致這2種迭代算法無法終止，通過分析結果元組的半環多項式溯源的特點，證明這2種近似算法最壞可在n次迭代后終止．最后，通過實驗說明了本文提出的方法是可行和有效的．

數據融合；半環溯源；多項式系統；派生樹；遞歸查詢

隨著網絡的飛速發展，Web技術以其廣泛性、交互性、快捷性和開放性等特點迅速風靡全球，并且已經滲入到社會的各個領域，網站及網頁數量正以指數級飛速增長．如何準確、有效地集成海量高價值的Web信息，對于諸如市場情報分析、輿情分析、商業智能等分析型應用尤為重要，具有非常重要的應用價值和現實意義．

但是，由于Web信息發布的隨意性以及信息發布者的水平差異，使得Web中存在大量不完整、過時、甚至錯誤、虛假的信息，為了保證集成的準確性，數據融合需要對多數據源的數據進行沖突解決．Web數據融合作為一個整體對用戶來講是一個黑盒過程，這使得當前數據融合過程缺乏可解釋性和可調試性．因此，為了使用戶能夠了解數據來源及演化過程，同時，追蹤沖突數據來源以便有效地解決沖突，需要研究一種基于數據溯源的可回溯的數據融合方法．

數據溯源（data provenance）是指數據的產生、并隨著時間推移而演化的整個過程的信息，可以為數據融合提供可回溯機制．但是，用于解決數據融合中數據沖突的數據溯源是一種細粒度的pay as you go模型，而當前細粒度的數據溯源方法要么是根據Data lineage［1］的方法計算數據起源，要么是預先計算所有數據的溯源形式［2］．這些方法都不能滿足數據融合可回溯機制的要求．

針對現在數據融合過程中透明化、融合階段比較孤立的特點，同時為了使融合結果具備可解釋性、融合過程具備可調試性，需要一種數據溯源方法來實現數據融合可回溯機制，該數據溯源方法應該：

1）是一種細粒度的數據溯源方法，不僅能夠表示數據的起源，而且還能夠描述數據的生成過程．

2）是一種快速的溯源計算方法，由于數據融合中沖突的解決是一種pay as you go模式，數據融合對溯源計算的實時性要求較高．

很顯然基于Datalog查詢的半環溯源模型是數據融合可回溯機制的選擇．

Datalog查詢是合取查詢在遞歸上的一種擴展．近幾年Datalog再次成為研究熱點，例如基于Datalog的邏輯的表述式語言的大量應用、Internet協議與服務的設計、程序語言的分析與查詢、本體的推理與查詢等．Datalog查詢儼然成為數據交換和數據集成中的一種更具有表達能力的語言．然而，面向Datalog查詢的數據溯源的研究還處于起步階段．其中主要的研究工作是賓夕法尼亞大學提出的半環多項式溯源模型［2］．

半環溯源作為一種典型的細粒度溯源方法，不僅能夠追蹤結果元組是由哪些數據派生得到的，還能夠表示這些數據以什么方式結合派生出結果元組．結果元組的半環多項式溯源信息主要通過結果元組的派生樹定義［2］計算得到．這種計算本質上是一種查詢的逆操作，需要大量的訪問原數據庫，尤其是在分布式環境下，計代價很大．然而溯源計算是數據融合可回溯機制的前提，當前的溯源計算方法無法滿足數據融合對數據溯源的需求．

本文主要研究面向數據融合的半環溯源計算問題．首先，提出一種近似序列Kleene序列，Kleene序列的第i個值ki等于結果元組的所有高度不高于i的派生樹收益．因此，Kleene序列就相當于按派生樹的高度對結果元組的派生樹進行劃分．根據半環溯源模型的派生樹定義，結果元組的半環溯源計算可以轉換成求解Kleene序列．這種代數方法通過把派生樹的構建轉化成對相應方程組的近似求解來減少對原數據庫的訪問，從而大大提高了半環溯源的計算效率．

針對Kleene序列收斂速度較慢的問題，提出了類牛頓序列vi．通過擴展函數在半環域內的可導的語義給出一種類牛頓的方法．由證明可以看出類牛頓序列有比Kleene更好的收斂速度．

然而Kleene序列和類牛頓序列都是一種近似迭代方法，當Datalog查詢出現遞歸時，可能會無限迭代下去．通過分析派生樹的結構特性，引入Kleene星操作，最多派生樹的高度為n后迭代終止，n表示結果元組的數目．

1 相關工作

數據融合的概念最初來源于多傳感器數據融合［3］，是指對來自多個傳感器的數據進行多級別、多方面、多層次的處理，從而產生新的有意義的信息．由于需要整合來自不同數據源的異構數據，數據集成很自然地需要進行數據融合的研究．但是對于數據融合的解釋還沒有一個統一的標準，其中普遍認可的是Dong等人在文獻［4］中的解釋：數據融合是指將來自不同數據源的表示同一實體的不同表象融合成一種單一的表象，并解決可能存在的數據沖突的過程．

Dong等人［5－8］在數據集成的數據融合方面做了很多具有代表性的工作，他們借助Web網站的拷貝現象，通過建立數據源之間的依賴關系，進而有效地融合多數據源的數據，并設計一個原型系統SOLOMON［9］，以展示數據源之間依賴關系及數據融合過程．

數據溯源是數據管理的重要內容，特別是在Web數據集成中，由于數據源的自由性以及集成過程的多階段性，更需要追蹤數據的起源及其演化過程，以確保集成數據的質量的可解釋性和可調試性．

關于數據溯源已經有了大量的研究工作．在傳統的異構數據集成方法中，通常使用模式級的數據溯源方法來追蹤數據在不同模式間的演化過程．由于數據融合過程中的沖突檢查處理的對象是數據，因此，細粒度的數據溯源方法是本文的研究對象．元組溯源是當前數據溯源研究的熱點，它在關系表上額外增加一個屬性來表示標注信息，用來對元組的元數據進行管理，這些標注信息可以是概率、置信度、布爾變量等．Cui等人提出的lineage溯源［1］方法用來標注哪些元組對結果元組的生成做了貢獻．Buneman等人提出的where［10］溯源方法用來表示哪些元組在一起共同構成結果元組．Green等人提出了一種更一般的標注模型——半環溯源（howprovenance［2］）．

對于數據溯源的查詢DBNotes［5，11］系統提出一種類似于SQL查詢的語言pSQL，用來指定where溯源的傳遞規則．Trio［12］系統開發了新查詢語言TriQL，支持不確定性和溯源查詢．Karvounarakis等人［13］提出了一種基于元組、半環溯源的查詢語言ProQL，可以很好地實現對溯源信息的查詢，同時提供一些機制解決存儲和查詢的相關問題．Perm［14］是一種數據溯源原型系統，它采用非標注表示法，用查詢重寫規則來修改SQL查詢．文獻［15－16］主要研究了數據溯源的查詢包含問題．文獻［17］提出一種基于circuit的溯源計算方法，這種方法是面向布爾查詢，主要是利用布爾電路遞歸地計算溯源信息，該方法可以在多項式時間構建多項式大小的溯源信息．

2 半環溯源與問題描述

在這節首先介紹Datalog查詢和半環溯源的一些相關概念．

2．1 Datalog查詢

一個Datalog查詢通常包含一系列如下形式的規則：這里n≥0，P表示這個Datalog規則的頭部，B1，B2，…，Bn的表示Datalog規則的主體．本文假定讀者對Datalog已有足夠的了解，不再贅述．

關系在Datalog規則中由謂詞表示．每個謂詞擁有固定數目的參數，一個謂詞和它的參數一起被稱為原子．實質上，謂詞就是一個返回布爾值的函數名．對于Datalog規則中的謂詞可以分為擴展謂詞（EDB）和內涵謂詞（IDB），擴展謂詞的關系存放在數據庫中，內涵謂詞的關系是由一個或多個Datalog規則計算出來的．

2．2 半環多項式溯源

作為一種一般的抽象溯源模型，半環溯源模型是在不完整數據庫、概率數據庫基礎上抽象出來的，是不同溯源模型應用的一個統一框架．文獻［6］給出了一個統一的數據溯源框架K關系，即提出一個半環溯源表示模型，溯源的傳播是根據關系代數的演算得到的，和查詢的耦合度較高．下面給出K關系的定義．

定義1．假設有一個半環K＝（κ，＋，×，0，1），包含2個演算操作符＋和×以及特異元0，1．U表示關系表上的屬性集．那么U上的K關系是指一個函數R：U．tuple→κ，其中它的支持元組集supp（R）＝｛t｜R（t）≠0｝．

半環溯源模型是用半環多項式來表示結果數據的生成過程．其中溯源多項式中的×操作對應關系代數中的連接操作，＋操作對應關系代數中的union操作．這樣就可以通過多項的結構表示結果數據是由哪些數據通過什么方式生成的．例如一個結果元組t的標注是xy2＋z＋z，其中x，y，z分別表示源數據庫中元組的抽象標注，這個多項式表示元組t是由3種派生路徑生成，一種是通過x標注的元組與y標注的元組做連接操作生成的，別外2種派生路徑是由z標注的元組直接生成．K關系本質是關系半環到標注半環的一個映射關系．

下面給出半環多項式溯源的基于派生樹的定義．

定義2［2］．給出一個可交換半環（κ，＋，×，0，1），一個數據庫實例D，查詢Q∈Datalog≠，Datalog≠表示存在不等式謂詞的Datalog查詢，對于Q（D）中的任意元組t，其多項式溯源可以表示為：

其中A（t，Q，D）是產生t的所有派生樹集合．

定義2不僅僅說明了半環溯源的語義，同時也給出半環溯源的計算方法．

2．3 派生樹

派生樹是本文提出的方法的關鍵，本文中派生樹的概念來源于上下文無關文法．

下面介紹一個在ω－連續半環域內的關于冪級數向量f的派生樹，如果沒有特殊說明，本文中的半環都是指ω－連續半環．派生樹中每一個結點都標注為（X，j）的形式，其中X∈χ表示f中的變量，j表示該結點依賴冪級數哪個項進行派生，它本質上表示一種項的索引．如果一個派生樹t的結點是（X，j），映射λ（t）（X，j）表示該派生樹與根結點的映射，λv（t）X表示根節點的變量，λm（t）j表示該結點按冪級數中的哪個項派生．

下面將給出關于多項式方程組的派生樹定義，并介紹如何定義每個派生樹的收益．

定義3．冪級數向量f的派生樹和派生樹的收益可遞歸地定義為：

如果向量f的任一單項式mx，j中都是常量（終止符），那么派生樹t只包含一個被標記為（X，j）的結點，同時派生樹t的收益Y（t）＝mx，j．

如果單項式mx，j＝a1X1a2X2…akXkak＋1，k≥1，t1，t2，…，tk是f中的一個項，其中λv（ti）Xi；那么以t1，t2，…，tk作為子樹的樹t同樣也是f的派生樹，如果λ（t）（X，j），那么Y（t）＝a1Y（t1）a2Y（t2）…akY（tk）ak＋1．

定義4．派生樹t的高度h（t）表示由根結點到葉子結點的最長的路徑長度．為了表示方便，用根結點表示派生，t＝h表示根結點為t的高度為h的所有派生樹集合，t＜h表示根結點為t的所有高度小于h的派生樹集合．

2．4 問題描述

為了更形象地說明半環溯源計算問題，下面給出實例來詳細說明．

給出Datalog查詢如圖1（a）所示，源數據庫實例抽象標注形式如圖1（b），圖1（c）表示查詢結果實例．通過Datalog查詢，能夠生成如圖1（d）所示的固定點方程組．其中結元組的實例表示變量，源數據實例表示常量．最終求解的結果就是用表示常量的源數據庫實例來表示結果元組的標注．

當前關于半環溯源的一些研究工作［12］是假定已知如圖1（d）所示的等式，這個等式是表示各數據庫元組之間的關聯關系．數據溯源的查詢、傳播與存儲等研究都是建立在這個派生關系的基礎上．生成結果元組與原數據實例之間關系的過程就是計算元組間的派生關系．因此溯源計算過程是半環溯源的研究基礎．相同關系內不同元組的派生路徑并不相同，因此元組的溯源計算過程以元組為處理對象．結果元組的溯源計算是一個復雜而耗時的過程，由于數據融合中對時效性要求較高，因此需要快速而高效的溯源計算方法．

Fig．1 Provenance for result tuples．圖1 結果元組溯源實例

當前Web數據更新與演化比較頻繁．而當數據經過多次演化后，多項式溯源的項會指數倍增加，這將導致溯源信息量過大，使得溯源計算過程更加復雜，而快速的計算溯源信息就成為一種挑戰．

遞歸的引入會使得溯源計算過程更加復雜化．遞歸導致一些元組會重復地派生自身，結果元組的溯源表達式是形式冪級數．面向遞歸查詢的溯源信息計算代價很大，同時溯源信息的存儲將會占用更多空間．解決遞歸查詢引起的無窮溯源問題是半環多項式溯源計算專有的問題．

3 Datalog查詢與多項式方程組

第2節給出了結果元組的半環多項式溯源的定義，顯然這個定義不是一個有效的計算方法．因此，這種半環多項式的派生樹定義只可以用來作為理論證明．從Datalog查詢評估的角度來看，會存在一個固定點理論．正如溯源信息的Datalog查詢一樣，會存在一種與派生樹定義等價的固定點語義，這種定義具有更好的可計算性．

根據Datalog查詢評估的特點，可知結果元組可能會由其他IDB元組派生得到，因此，為了方便表示，對每一個結果元組使用新的變量來表示．因此，通過Datalog規則可以構建結果元組與所有其他元組之間的一個等價關系．

這種等價關系的構建可以在查詢執行時構建．但是，一方面需要重寫查詢機制；另一方面查詢執行過程并不能完全反映結果元組的派生路徑，比如遞歸，因為遞歸查詢的終止條件是兩次的查詢結果相同；而且，數據融合過程中的沖突檢測是一個pay as you go模型，只有需要時才會計算相應數據的溯源信息，這種在查詢過程中預先計算所有數據的溯源信息方法會大大降低查詢的執行效率，也會計算很多不需要的溯源信息并占用大量的存儲空間．本節提出一種查詢逆操作的方程組構建方法．

定理1．利用Datalog查詢構建結果元組的多項式方程組是一個NP－hard問題．

證明．多項式方程組的構建主要利用Datalog查詢找出結果元組與其他元組之間的等價關系，如果Datalog規則是合取式的話，那么這個問題可規約為SAT問題，顯然是一個NP－complete問題．所以，利用Datalog查詢構建結果元組的多項式方程組至少是NP－complete問題．證畢．

對于一個NP－hard問題要從算法的角度優化該問題是比較困難的，但是可以從減少輸入的角度來優化該問題．

為了簡化概念，假定只存在一個EDB謂詞和一個IDB謂詞．對于給定的有限的EDB謂詞k－關系可以按如下方法（算法1）構建固定點方程組：

算法1．GenerateEquations．

輸入：查詢Q，IDB元組I，EDB元組E；

輸出：固定點方程組．

算法1主要致力于通過Datalog查詢規則構建結果元組與其他元組之間的等價關系．首先對于每個EDB元組和IDB元組都賦予一個變量來唯一表示這個元組（行③④）．EDB元組變量在固定點方程中表示常量，而IDB元組變量在固定點方程中表示變量．算法1的關鍵就是找出IDB變量與其他所有變量之間的等價關系．這種等價關系就是根據Datalog查詢找出所有能派生出IDB元組的EDB元組的賦值．由于這個問題超出本文的范圍，在另一篇文章中將有詳細的解決方法．

4 基于Kleene迭代的半環溯源計算方法

第3節介紹了結果元組半環多項式溯源計算到固定點方程組的轉換．那么是不是有可能有一種對方程組的處理方法能夠有效地計算結果元組的半環多項式溯源？對固定點方程組的求解顯然要比根據結果元組的派生樹定義直接構建派生樹要有效得多，因為可以避免大量對原數據庫的訪問．

定理2．給定源數據庫實例S、目標數據庫實例T、Datalog查詢規則q．那么，由算法1構建的固定點方程組的解等于結果元組的半環多項式溯源．

證明．根據Kleene定理可知，在ω－連續半環內求解多項式方程組X＝f（X），存在Kleene近似序列，使得方程組X＝f（X）的解等于這個序列的上確界，而Kleene序列可以迭代地表示為k0＝0，ki＋1＝f（ki）．顯然Kleene序列可以看成是一種迭代的方程組求解方法．為了證明定理，只需要證明Kleene迭代與結果元組的派生樹的關系．證畢．

引理1．固定點方程組的第i個Kleene迭代ki等于高度不大于i的所有變量的派生樹的收益之和．

證明．可以通過歸納法來證明．下面的Hi表示度不高于i的所有派生樹集合．

由于固定點方程組的變量表示的是IDB元組的標注，因此，Kleene序列就相當于按派生樹的高度來構建結果元組的派生樹．根據定義2，可知由算法1生成的于固定點方程組的解就是結果元組的半環多項式溯源信息．

定理2的證明不僅說明了半環多項式溯源的計算可以轉化成一種數學計算，而且還給出了一種近似迭代的半環溯源計算方法．這種方法可以避免大量的訪問數據，因此，能有效地提高半環多項式標注的計算過程．

5 類牛頓迭代的半環溯源計算

由v0開始，按vi＋1＝vi＋Δi迭代地計算，其中Δi是線性固定點方程Df｜vi（X）

盡管Kleene迭代方法是一種通用方法．但是對于遞歸查詢來說可能無法終止，并且收斂速度較慢．

牛頓迭代是數值域內求解非線性方程組的一種經典方法，它本質上是將非線性方程逐步轉換成線性方程來求解，是平方收斂的．那么在半環域內是不是能夠有一種迭代方法能快速地收斂．

把牛頓迭代的思想擴展到半環域內，由算法1得到的固定點方程組的一般形式為：

x1＝f1（x1，x2，…，xn）；

x2＝f2（x2，x2，…，xn）；

xn＝fn（x1，x2，…，xn）．

這種方程組可以表示成向量的形式X＝f（X）．計算X＝f（X）的最小解就相當于計算g（X）＝0，其中g（X）＝f（X）－X．

利用牛頓迭代求解方程組，給出可導函數g1，g2，…，gn：Rn→R，求解半環多項式溯源方法就是計算方程組g（X）＝0的解，其中g＝（g1，g2，…，gn）；存在這樣一個序列vi＋1＝vi＋Δi，其中Δi是如下線性方程組的解：最小解．這個序列的極值就是原方程組的解．

然而牛頓迭代到半環域內的沒有可導函數，這里擴展了半環域內的函數的可導性．

定義5．f是半環域S內的形式冪級數，其中X∈χ是其中的變量．關于變量X的在v點的微分函數DXf｜v（X）：v→S定義如下：

其中δi是滿足方程f（vi）＝vi＋δi的取值．

定義6．f是一組形式冪級數的向量，第i個類牛頓近似vi可以被歸納地定義為：

其中Δi是方程Df｜vi（X）＋δi＝X的最小解，δi是滿足方程f（vi）＝vi＋δi的任意取值，序列vi被稱為類牛頓序列．

給出近似迭代方法類牛頓序列，下面給出類牛頓序列與Klenne序列的關系．

引理2．f：V→V是一組形式冪級數的向量，其中u，w∈V，那么Df｜u（X）＋w＝X；的最小解是Df｜＊u（w）．相似地，類牛頓序列可以被定義為w0＝f（0）和wi＋1＝wi＋Df｜＊vi（δi）．

f（u）＋Df｜u（v）≤f（u＋v）≤f（u）＋Df｜u＋v（v）．

證明．對于由于f一組形式冪級數的向量，可以假定ρ表示向量f中的一個元素，那么ρ一般形式ρ＝g×χ×a，其中，g表示單項式，χ表示變量，a表示常量．

定理3．f是一組形式冪級數的向量，那么只會存在一個類牛頓近似vi，滿足如下性質：

ki≤vi≤f（vi）≤vi＋1≤μf＝supkj．

證明．首先證明對于所有的i來說會存在一個δi，滿足ki≤vi≤f（vi）．利用歸納法證明這個結論：

當i＝0時，結果顯然是滿足的．那么假定i取任意大于0的整數時也滿足，即ki≤vi≤f（vi）．

接下來需要證明vi≤μf．

當迭代次數為0時，顯然是滿足的，假定當迭代次數為i時也滿足：

定理3的證明說明了類牛頓序列比Kleene序列有更好的收斂性，也就是能更快地計算出半環多項式溯源．

由于Kleene序列和類牛頓序列都是一種迭代方法，而當Datalog查詢出現遞歸時迭代可能是無法終止的．

定理4．Kleene序列和類牛頓序列最多可經過n步終止，其中n表示結果元組的數目．

證明．由于第n個Kleene序列表示所有高度不大于n的派生樹集合．定理就相當于證明派生樹的高度不需要大于n就可以計算出結果元組的半環多項式溯源．證畢．

6 實驗結果與分析

本節給出了基于Kleene迭代方法和類牛頓迭代方法的結果元組半環多項式溯源計算的性能測試結果，并與基于派生樹構建的半環多項式標注計算方法進行比較．

采用TPC－H Benchmark的數據集來進行測試．TPC－H Benchmark是通過數據庫查詢性能測試的實驗平臺，本文在TPC－H Benchmark測試中選用了查詢結果中不包含聚類操作的查詢Q2，Q11，Q15和Q20．

此次實驗使用的數據庫是sql sever 2008數據庫，開發工具使用vs2010，系統實現的語言為C＃．6．1 不同數據大小的溯源計算比較

首先考慮的是輸入數據大小對各算法的執行時間的影響．選擇查詢Q2，Q11，Q15和Q20來度量面向不同的查詢結果元組的半環多項式溯源計算過程的執行時間．

Tradition方法指的是傳統的基于派生樹構建的方法，Kleene是指Kleene近似迭代方法，Newton是指類牛頓迭代方法．

由圖2中可以看出傳統的基于派生樹構建的半環多項式溯源計算方法隨著元組數的增長計算代價增長較快，而Kleene近似方法和類牛頓近似方法的計算代價隨著數據的增長近似線性，可見Kleene近似方法與類牛頓近似方法有很好的計算效率，同時也有很好的可擴展性．

Fig．2 Comparison of semiring provenance with different queries．圖2 不同查詢的半環多項式溯源計算對比

6．2 合取謂詞不同對溯源計算的影響

半環多項式溯源主要是根據Datalog查詢找出滿足查詢的所有元組的組合，本小節測試溯源計算方法面對不同長度的Datalog規則的計算效率．

圖3所示為數據大小為1MB，10MB，100MB， 500MB的情況下合取式大小由2～8的計算代價．

通過圖3可以看出傳統的基于派生樹的構建方法代價要遠遠高于基于Kleene迭代和類牛頓迭代的方法．而隨著合取式數目的增加類牛頓迭代表現了更好的性能．

Fig．3 Comparison of semiring provenance with different size of queries．圖3 不同查詢長度的半環多項式溯源計算對比

6．3 不同演化版本的半環溯源計算分析

針對TPCH數據集構建不同版本的數據，每個版本都可以用實化視圖表示．圖4中對源數據大小為10MB和100MB兩種情況進行了分析比較．半環多項式溯源的計算代價隨著版本的增加快速增加，很顯然傳統的方法增長很快，而隨著版本數的增加，類牛頓迭代表現了很好的計算性能和良好的可擴展性．

Fig．4 Comparison of semiring provenance with different versions．圖4 不同演化版本下的半環多項式溯源比較

7 結束語

針對數據融合過程缺乏可解釋性和可調試性，同時為了便于數據融合過程中有效的沖突檢測和調試，本文提出了一種基于數據融合的可回溯機制．本文方法致力于研究快速的溯源計算方法，以應對數據融合過程的可回溯機制對實時性的要求．首先提出一種基于Kleene序列的近似迭代方法，該方法通過把對數據處理轉換對半環多項式的求解來避免對數據庫的大量訪問；然后提出一種類牛頓迭代方法通過加速收斂來提高溯源計算效率．通過分析，本文提出的2種迭代方法均收斂．實驗結果表明，相對于傳統的基于派生樹的溯源計算方法，本文提出的2種方法有正好的計算效率，同時隨著數據量增長，類牛頓迭代方法有更好的可擴展性．

［1］Cui Y，Widom J，Wiener J L．Tracing the lineage of view data in a warehousing environment［J］．ACM Trans on Database Systems，2000，25（2）：179 227

［2］Green T J，Karvounarakis G，Tannen V．Provenance semirings［C］??Proc of the 27th ACM SIGMOD Int Conf on Management of Data Symp on Principles of Database Systems．New York：ACM，2007：31 40

［3］Llinas J，Hall D L．An introduction to multi－sensor data fusion［C］??Proc of ISCAS 98．Piscataway，NJ：IEEE，1998：537 540

［4］Dong X L，Naumann F．Data fusion—Resolving data conflicts for integration［J］．Proceedings of the VLDB Endowment，2009，2（2）：1654 1655

［5］Dong X L，Gabrilovich E，Heitz G，et al．From data fusion to knowledge fusion［J］．Proceedings of the VLDB Endowment，2014，7（10）：881 892

［6］Dong X L，Berti－Equille L，Srivastava D．Data fusion：Resolving conflicts from mutiple sources［C］??Proc of the WAIM2013．Berlin：Springer，2013：64 76

［7］Li Xian，Dong X L，Lyons K，et al．Scaling up copy detection［C］??Proc of the 31st IEEE Int Conf on Data Engineering．Piscataway，NJ：IEEE，89 100

［8］Xuan Liu，Xin Luna Dong，Beng Chin Ooi，et al．Online data fusion［J］．Proceedings of the VLDB Endowment，2011，4（11）：932 943

［9］Dong X L，Berti－Equille L，Hu Yifan，et al．Solomon：Seeking the truth via copying detection［J］．Proceedings of the VLDB Endowment，2010，3（12）：3 3

［10］Buneman P，Khanna S，Tan W C．Why and where：A characterization of data provenance［C］??Proc of the 8th Int Conf on Data Theory．Berlin：Springer，2001：316 330

［11］Chiticariu L，Tan W C，Vijayvargiya G．DBNotes：A post－it system for relational databases based on provenance［C］?? Proc of the 24th ACM SIGMOD－SlGACT－SlGART Symp on Principles of Database Systems．New York：ACM，2005：942 944

［12］Widom J Trio．A system for integrated management of data，accuracy，and lineage［C］??Proc of the 2nd Biennial Conf on Innovative Data Systems Research．New York：ACM，2005：262 276

［13］Karvounarakis G，Ives I G，Tannen V．Querying data provenance［C］??Proc of the ACM SIGMOD Int Conf on Management of Data．New York：ACM，2010：951 962

［14］Glavic B，Alonso G Perm．Processing provenance and data on the same data model through query rewriting［C］??Proc of the 25th IEEE Int Conf on Data Engineering．Piscataway，NJ：IEEE，2009：174 185

［15］Green T J．Containment of conjunctive queries on annotated relations［J］．Theory of Computing System，2011，49（2）：429 459

［16］Green T J，Huang S S，Loo B T，et al．Datalog and recursive query［J］．Processing Foundations and Trends in Databases，2013，5（2）：105 195

［17］Deutch D，Milo T，Roy S，et al．Circuits for datalog provenance［C］??Proc of the 17th Int Conf on Data Theory．New York：ACM，2014：201 212

Xue Jianxin，born in 1984．PhD candidate．Student member of China Computer Federation．His research interests include recursive query evaluation and data provenance（xuejianxin＠research．neu．edu．cn）．

Shen Derong，born in 1964．Professor and PhD supervisor of the Northeastern University．Senior member of China Computer Federation．Her main research interests include distributed database，Web data management and Web services．

Kou Yue，born in 1980．Associate professor at Northeastern University，China．Member of China Computer Federation．Her main research interests include Web search，Web mining，and dataspace．

Nie Tiezheng，born in 1980．Associate professor at Northeastern University，China．Member of China Computer Federation．His main research interests include data quality and data integration．

Yu Ge，born in 1962．Professor and PhD supervisor at Northeastern University，China．His main research interests include database theory and technology，distributed and parallel systems，and network information security．

Semiring Provenance for Data Fusion

Xue Jianxin，Shen Derong，Kou Yue，Nie Tiezheng，and Yu Ge
（College of Information Science and Engineering，Northeastern University，Shenyang110819）

As an important part of the Web data integration，Web data fusion is the quality assurance of integrated data and the precondition of accurate analysis and mining．However，being a uniform data fusion is treated as black box，which makes the fusion lack of interpretability and debuggable ability．Therefore，to describe fusion process and origin for solving the conflict，we should construct a provenance mechanism with data provenance．Data provenance describes about how data is generated and evolves with time going on，which can not only show which input tuples contribute to the data but also how they contribute．We study the semiring provenance for data fusion．Firstly，we propose an approximate iterative approach to optimal the computational process of semiring provenance．After，to speed up the convergence，we show a Newton－like approach．Recursion may make the situation complicated，we analysize the characteristic of semiring provenance and show that Kleene sequence and Newton－like sequence can convergent only after n step．And experiments show that the technologies in this paper are highly effective and feasible．

data fusion；semiring provenance；polynomial systems；derive trees；recursive queries

TP391

2015－09－25；

2015－11－23

國家自然科學基金項目（61472070）；國家“九七三”重點基礎研究發展規劃基金項目（2012CB316201）

This work was supported by the National Natural Science Foundation of China（61472070）and the National Basic Research Program of China（973Program）（2012CB316201）．