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

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

面向數(shù)據(jù)融合的半環(huán)溯源計(jì)算方法

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

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

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

數(shù)據(jù)融合；半環(huán)溯源；多項(xiàng)式系統(tǒng)；派生樹；遞歸查詢

隨著網(wǎng)絡(luò)的飛速發(fā)展，Web技術(shù)以其廣泛性、交互性、快捷性和開放性等特點(diǎn)迅速風(fēng)靡全球，并且已經(jīng)滲入到社會(huì)的各個(gè)領(lǐng)域，網(wǎng)站及網(wǎng)頁數(shù)量正以指數(shù)級(jí)飛速增長(zhǎng)．如何準(zhǔn)確、有效地集成海量高價(jià)值的Web信息，對(duì)于諸如市場(chǎng)情報(bào)分析、輿情分析、商業(yè)智能等分析型應(yīng)用尤為重要，具有非常重要的應(yīng)用價(jià)值和現(xiàn)實(shí)意義．

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

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

針對(duì)現(xiàn)在數(shù)據(jù)融合過程中透明化、融合階段比較孤立的特點(diǎn)，同時(shí)為了使融合結(jié)果具備可解釋性、融合過程具備可調(diào)試性，需要一種數(shù)據(jù)溯源方法來實(shí)現(xiàn)數(shù)據(jù)融合可回溯機(jī)制，該數(shù)據(jù)溯源方法應(yīng)該：

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

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

很顯然基于Datalog查詢的半環(huán)溯源模型是數(shù)據(jù)融合可回溯機(jī)制的選擇．

Datalog查詢是合取查詢?cè)谶f歸上的一種擴(kuò)展．近幾年Datalog再次成為研究熱點(diǎn)，例如基于Datalog的邏輯的表述式語言的大量應(yīng)用、Internet協(xié)議與服務(wù)的設(shè)計(jì)、程序語言的分析與查詢、本體的推理與查詢等．Datalog查詢儼然成為數(shù)據(jù)交換和數(shù)據(jù)集成中的一種更具有表達(dá)能力的語言．然而，面向Datalog查詢的數(shù)據(jù)溯源的研究還處于起步階段．其中主要的研究工作是賓夕法尼亞大學(xué)提出的半環(huán)多項(xiàng)式溯源模型［2］．

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

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

針對(duì)Kleene序列收斂速度較慢的問題，提出了類牛頓序列vi．通過擴(kuò)展函數(shù)在半環(huán)域內(nèi)的可導(dǎo)的語義給出一種類牛頓的方法．由證明可以看出類牛頓序列有比Kleene更好的收斂速度．

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

1 相關(guān)工作

數(shù)據(jù)融合的概念最初來源于多傳感器數(shù)據(jù)融合［3］，是指對(duì)來自多個(gè)傳感器的數(shù)據(jù)進(jìn)行多級(jí)別、多方面、多層次的處理，從而產(chǎn)生新的有意義的信息．由于需要整合來自不同數(shù)據(jù)源的異構(gòu)數(shù)據(jù)，數(shù)據(jù)集成很自然地需要進(jìn)行數(shù)據(jù)融合的研究．但是對(duì)于數(shù)據(jù)融合的解釋還沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)，其中普遍認(rèn)可的是Dong等人在文獻(xiàn)［4］中的解釋：數(shù)據(jù)融合是指將來自不同數(shù)據(jù)源的表示同一實(shí)體的不同表象融合成一種單一的表象，并解決可能存在的數(shù)據(jù)沖突的過程．

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

數(shù)據(jù)溯源是數(shù)據(jù)管理的重要內(nèi)容，特別是在Web數(shù)據(jù)集成中，由于數(shù)據(jù)源的自由性以及集成過程的多階段性，更需要追蹤數(shù)據(jù)的起源及其演化過程，以確保集成數(shù)據(jù)的質(zhì)量的可解釋性和可調(diào)試性．

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

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

2 半環(huán)溯源與問題描述

在這節(jié)首先介紹Datalog查詢和半環(huán)溯源的一些相關(guān)概念．

2．1 Datalog查詢

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

關(guān)系在Datalog規(guī)則中由謂詞表示．每個(gè)謂詞擁有固定數(shù)目的參數(shù)，一個(gè)謂詞和它的參數(shù)一起被稱為原子．實(shí)質(zhì)上，謂詞就是一個(gè)返回布爾值的函數(shù)名．對(duì)于Datalog規(guī)則中的謂詞可以分為擴(kuò)展謂詞（EDB）和內(nèi)涵謂詞（IDB），擴(kuò)展謂詞的關(guān)系存放在數(shù)據(jù)庫中，內(nèi)涵謂詞的關(guān)系是由一個(gè)或多個(gè)Datalog規(guī)則計(jì)算出來的．

2．2 半環(huán)多項(xiàng)式溯源

作為一種一般的抽象溯源模型，半環(huán)溯源模型是在不完整數(shù)據(jù)庫、概率數(shù)據(jù)庫基礎(chǔ)上抽象出來的，是不同溯源模型應(yīng)用的一個(gè)統(tǒng)一框架．文獻(xiàn)［6］給出了一個(gè)統(tǒng)一的數(shù)據(jù)溯源框架K關(guān)系，即提出一個(gè)半環(huán)溯源表示模型，溯源的傳播是根據(jù)關(guān)系代數(shù)的演算得到的，和查詢的耦合度較高．下面給出K關(guān)系的定義．

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

半環(huán)溯源模型是用半環(huán)多項(xiàng)式來表示結(jié)果數(shù)據(jù)的生成過程．其中溯源多項(xiàng)式中的×操作對(duì)應(yīng)關(guān)系代數(shù)中的連接操作，＋操作對(duì)應(yīng)關(guān)系代數(shù)中的union操作．這樣就可以通過多項(xiàng)的結(jié)構(gòu)表示結(jié)果數(shù)據(jù)是由哪些數(shù)據(jù)通過什么方式生成的．例如一個(gè)結(jié)果元組t的標(biāo)注是xy2＋z＋z，其中x，y，z分別表示源數(shù)據(jù)庫中元組的抽象標(biāo)注，這個(gè)多項(xiàng)式表示元組t是由3種派生路徑生成，一種是通過x標(biāo)注的元組與y標(biāo)注的元組做連接操作生成的，別外2種派生路徑是由z標(biāo)注的元組直接生成．K關(guān)系本質(zhì)是關(guān)系半環(huán)到標(biāo)注半環(huán)的一個(gè)映射關(guān)系．

下面給出半環(huán)多項(xiàng)式溯源的基于派生樹的定義．

定義2［2］．給出一個(gè)可交換半環(huán)（κ，＋，×，0，1），一個(gè)數(shù)據(jù)庫實(shí)例D，查詢Q∈Datalog≠，Datalog≠表示存在不等式謂詞的Datalog查詢，對(duì)于Q（D）中的任意元組t，其多項(xiàng)式溯源可以表示為：

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

定義2不僅僅說明了半環(huán)溯源的語義，同時(shí)也給出半環(huán)溯源的計(jì)算方法．

2．3 派生樹

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

下面介紹一個(gè)在ω－連續(xù)半環(huán)域內(nèi)的關(guān)于冪級(jí)數(shù)向量f的派生樹，如果沒有特殊說明，本文中的半環(huán)都是指ω－連續(xù)半環(huán)．派生樹中每一個(gè)結(jié)點(diǎn)都標(biāo)注為（X，j）的形式，其中X∈χ表示f中的變量，j表示該結(jié)點(diǎn)依賴冪級(jí)數(shù)哪個(gè)項(xiàng)進(jìn)行派生，它本質(zhì)上表示一種項(xiàng)的索引．如果一個(gè)派生樹t的結(jié)點(diǎn)是（X，j），映射λ（t）（X，j）表示該派生樹與根結(jié)點(diǎn)的映射，λv（t）X表示根節(jié)點(diǎn)的變量，λm（t）j表示該結(jié)點(diǎn)按冪級(jí)數(shù)中的哪個(gè)項(xiàng)派生．

下面將給出關(guān)于多項(xiàng)式方程組的派生樹定義，并介紹如何定義每個(gè)派生樹的收益．

定義3．冪級(jí)數(shù)向量f的派生樹和派生樹的收益可遞歸地定義為：

如果向量f的任一單項(xiàng)式mx，j中都是常量（終止符），那么派生樹t只包含一個(gè)被標(biāo)記為（X，j）的結(jié)點(diǎn)，同時(shí)派生樹t的收益Y（t）＝mx，j．

如果單項(xiàng)式mx，j＝a1X1a2X2…akXkak＋1，k≥1，t1，t2，…，tk是f中的一個(gè)項(xiàng)，其中λ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）表示由根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長(zhǎng)的路徑長(zhǎng)度．為了表示方便，用根結(jié)點(diǎn)表示派生，t＝h表示根結(jié)點(diǎn)為t的高度為h的所有派生樹集合，t＜h表示根結(jié)點(diǎn)為t的所有高度小于h的派生樹集合．

2．4 問題描述

為了更形象地說明半環(huán)溯源計(jì)算問題，下面給出實(shí)例來詳細(xì)說明．

給出Datalog查詢?nèi)鐖D1（a）所示，源數(shù)據(jù)庫實(shí)例抽象標(biāo)注形式如圖1（b），圖1（c）表示查詢結(jié)果實(shí)例．通過Datalog查詢，能夠生成如圖1（d）所示的固定點(diǎn)方程組．其中結(jié)元組的實(shí)例表示變量，源數(shù)據(jù)實(shí)例表示常量．最終求解的結(jié)果就是用表示常量的源數(shù)據(jù)庫實(shí)例來表示結(jié)果元組的標(biāo)注．

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

Fig．1 Provenance for result tuples．圖1 結(jié)果元組溯源實(shí)例

當(dāng)前Web數(shù)據(jù)更新與演化比較頻繁．而當(dāng)數(shù)據(jù)經(jīng)過多次演化后，多項(xiàng)式溯源的項(xiàng)會(huì)指數(shù)倍增加，這將導(dǎo)致溯源信息量過大，使得溯源計(jì)算過程更加復(fù)雜，而快速的計(jì)算溯源信息就成為一種挑戰(zhàn)．

遞歸的引入會(huì)使得溯源計(jì)算過程更加復(fù)雜化．遞歸導(dǎo)致一些元組會(huì)重復(fù)地派生自身，結(jié)果元組的溯源表達(dá)式是形式冪級(jí)數(shù)．面向遞歸查詢的溯源信息計(jì)算代價(jià)很大，同時(shí)溯源信息的存儲(chǔ)將會(huì)占用更多空間．解決遞歸查詢引起的無窮溯源問題是半環(huán)多項(xiàng)式溯源計(jì)算專有的問題．

3 Datalog查詢與多項(xiàng)式方程組

第2節(jié)給出了結(jié)果元組的半環(huán)多項(xiàng)式溯源的定義，顯然這個(gè)定義不是一個(gè)有效的計(jì)算方法．因此，這種半環(huán)多項(xiàng)式的派生樹定義只可以用來作為理論證明．從Datalog查詢?cè)u(píng)估的角度來看，會(huì)存在一個(gè)固定點(diǎn)理論．正如溯源信息的Datalog查詢一樣，會(huì)存在一種與派生樹定義等價(jià)的固定點(diǎn)語義，這種定義具有更好的可計(jì)算性．

根據(jù)Datalog查詢?cè)u(píng)估的特點(diǎn)，可知結(jié)果元組可能會(huì)由其他IDB元組派生得到，因此，為了方便表示，對(duì)每一個(gè)結(jié)果元組使用新的變量來表示．因此，通過Datalog規(guī)則可以構(gòu)建結(jié)果元組與所有其他元組之間的一個(gè)等價(jià)關(guān)系．

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

定理1．利用Datalog查詢構(gòu)建結(jié)果元組的多項(xiàng)式方程組是一個(gè)NP－h(huán)ard問題．

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

對(duì)于一個(gè)NP－h(huán)ard問題要從算法的角度優(yōu)化該問題是比較困難的，但是可以從減少輸入的角度來優(yōu)化該問題．

為了簡(jiǎn)化概念，假定只存在一個(gè)EDB謂詞和一個(gè)IDB謂詞．對(duì)于給定的有限的EDB謂詞k－關(guān)系可以按如下方法（算法1）構(gòu)建固定點(diǎn)方程組：

算法1．GenerateEquations．

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

輸出：固定點(diǎn)方程組．

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

4 基于Kleene迭代的半環(huán)溯源計(jì)算方法

第3節(jié)介紹了結(jié)果元組半環(huán)多項(xiàng)式溯源計(jì)算到固定點(diǎn)方程組的轉(zhuǎn)換．那么是不是有可能有一種對(duì)方程組的處理方法能夠有效地計(jì)算結(jié)果元組的半環(huán)多項(xiàng)式溯源？對(duì)固定點(diǎn)方程組的求解顯然要比根據(jù)結(jié)果元組的派生樹定義直接構(gòu)建派生樹要有效得多，因?yàn)榭梢员苊獯罅繉?duì)原數(shù)據(jù)庫的訪問．

定理2．給定源數(shù)據(jù)庫實(shí)例S、目標(biāo)數(shù)據(jù)庫實(shí)例T、Datalog查詢規(guī)則q．那么，由算法1構(gòu)建的固定點(diǎn)方程組的解等于結(jié)果元組的半環(huán)多項(xiàng)式溯源．

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

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

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

由于固定點(diǎn)方程組的變量表示的是IDB元組的標(biāo)注，因此，Kleene序列就相當(dāng)于按派生樹的高度來構(gòu)建結(jié)果元組的派生樹．根據(jù)定義2，可知由算法1生成的于固定點(diǎn)方程組的解就是結(jié)果元組的半環(huán)多項(xiàng)式溯源信息．

定理2的證明不僅說明了半環(huán)多項(xiàng)式溯源的計(jì)算可以轉(zhuǎn)化成一種數(shù)學(xué)計(jì)算，而且還給出了一種近似迭代的半環(huán)溯源計(jì)算方法．這種方法可以避免大量的訪問數(shù)據(jù)，因此，能有效地提高半環(huán)多項(xiàng)式標(biāo)注的計(jì)算過程．

5 類牛頓迭代的半環(huán)溯源計(jì)算

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

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

牛頓迭代是數(shù)值域內(nèi)求解非線性方程組的一種經(jīng)典方法，它本質(zhì)上是將非線性方程逐步轉(zhuǎn)換成線性方程來求解，是平方收斂的．那么在半環(huán)域內(nèi)是不是能夠有一種迭代方法能快速地收斂．

把牛頓迭代的思想擴(kuò)展到半環(huán)域內(nèi)，由算法1得到的固定點(diǎn)方程組的一般形式為：

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

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

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

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

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

然而牛頓迭代到半環(huán)域內(nèi)的沒有可導(dǎo)函數(shù)，這里擴(kuò)展了半環(huán)域內(nèi)的函數(shù)的可導(dǎo)性．

定義5．f是半環(huán)域S內(nèi)的形式冪級(jí)數(shù)，其中X∈χ是其中的變量．關(guān)于變量X的在v點(diǎn)的微分函數(shù)DXf｜v（X）：v→S定義如下：

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

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

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

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

引理2．f：V→V是一組形式冪級(jí)數(shù)的向量，其中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）．

證明．對(duì)于由于f一組形式冪級(jí)數(shù)的向量，可以假定ρ表示向量f中的一個(gè)元素，那么ρ一般形式ρ＝g×χ×a，其中，g表示單項(xiàng)式，χ表示變量，a表示常量．

定理3．f是一組形式冪級(jí)數(shù)的向量，那么只會(huì)存在一個(gè)類牛頓近似vi，滿足如下性質(zhì)：

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

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

當(dāng)i＝0時(shí)，結(jié)果顯然是滿足的．那么假定i取任意大于0的整數(shù)時(shí)也滿足，即ki≤vi≤f（vi）．

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

當(dāng)?shù)螖?shù)為0時(shí)，顯然是滿足的，假定當(dāng)?shù)螖?shù)為i時(shí)也滿足：

定理3的證明說明了類牛頓序列比Kleene序列有更好的收斂性，也就是能更快地計(jì)算出半環(huán)多項(xiàng)式溯源．

由于Kleene序列和類牛頓序列都是一種迭代方法，而當(dāng)Datalog查詢出現(xiàn)遞歸時(shí)迭代可能是無法終止的．

定理4．Kleene序列和類牛頓序列最多可經(jīng)過n步終止，其中n表示結(jié)果元組的數(shù)目．

證明．由于第n個(gè)Kleene序列表示所有高度不大于n的派生樹集合．定理就相當(dāng)于證明派生樹的高度不需要大于n就可以計(jì)算出結(jié)果元組的半環(huán)多項(xiàng)式溯源．證畢．

6 實(shí)驗(yàn)結(jié)果與分析

本節(jié)給出了基于Kleene迭代方法和類牛頓迭代方法的結(jié)果元組半環(huán)多項(xiàng)式溯源計(jì)算的性能測(cè)試結(jié)果，并與基于派生樹構(gòu)建的半環(huán)多項(xiàng)式標(biāo)注計(jì)算方法進(jìn)行比較．

采用TPC－H Benchmark的數(shù)據(jù)集來進(jìn)行測(cè)試．TPC－H Benchmark是通過數(shù)據(jù)庫查詢性能測(cè)試的實(shí)驗(yàn)平臺(tái)，本文在TPC－H Benchmark測(cè)試中選用了查詢結(jié)果中不包含聚類操作的查詢Q2，Q11，Q15和Q20．

此次實(shí)驗(yàn)使用的數(shù)據(jù)庫是sql sever 2008數(shù)據(jù)庫，開發(fā)工具使用vs2010，系統(tǒng)實(shí)現(xiàn)的語言為C＃．6．1 不同數(shù)據(jù)大小的溯源計(jì)算比較

首先考慮的是輸入數(shù)據(jù)大小對(duì)各算法的執(zhí)行時(shí)間的影響．選擇查詢Q2，Q11，Q15和Q20來度量面向不同的查詢結(jié)果元組的半環(huán)多項(xiàng)式溯源計(jì)算過程的執(zhí)行時(shí)間．

Tradition方法指的是傳統(tǒng)的基于派生樹構(gòu)建的方法，Kleene是指Kleene近似迭代方法，Newton是指類牛頓迭代方法．

由圖2中可以看出傳統(tǒng)的基于派生樹構(gòu)建的半環(huán)多項(xiàng)式溯源計(jì)算方法隨著元組數(shù)的增長(zhǎng)計(jì)算代價(jià)增長(zhǎng)較快，而Kleene近似方法和類牛頓近似方法的計(jì)算代價(jià)隨著數(shù)據(jù)的增長(zhǎng)近似線性，可見Kleene近似方法與類牛頓近似方法有很好的計(jì)算效率，同時(shí)也有很好的可擴(kuò)展性．

Fig．2 Comparison of semiring provenance with different queries．圖2 不同查詢的半環(huán)多項(xiàng)式溯源計(jì)算對(duì)比

6．2 合取謂詞不同對(duì)溯源計(jì)算的影響

半環(huán)多項(xiàng)式溯源主要是根據(jù)Datalog查詢找出滿足查詢的所有元組的組合，本小節(jié)測(cè)試溯源計(jì)算方法面對(duì)不同長(zhǎng)度的Datalog規(guī)則的計(jì)算效率．

圖3所示為數(shù)據(jù)大小為1MB，10MB，100MB， 500MB的情況下合取式大小由2～8的計(jì)算代價(jià)．

通過圖3可以看出傳統(tǒng)的基于派生樹的構(gòu)建方法代價(jià)要遠(yuǎn)遠(yuǎn)高于基于Kleene迭代和類牛頓迭代的方法．而隨著合取式數(shù)目的增加類牛頓迭代表現(xiàn)了更好的性能．

Fig．3 Comparison of semiring provenance with different size of queries．圖3 不同查詢長(zhǎng)度的半環(huán)多項(xiàng)式溯源計(jì)算對(duì)比

6．3 不同演化版本的半環(huán)溯源計(jì)算分析

針對(duì)TPCH數(shù)據(jù)集構(gòu)建不同版本的數(shù)據(jù)，每個(gè)版本都可以用實(shí)化視圖表示．圖4中對(duì)源數(shù)據(jù)大小為10MB和100MB兩種情況進(jìn)行了分析比較．半環(huán)多項(xiàng)式溯源的計(jì)算代價(jià)隨著版本的增加快速增加，很顯然傳統(tǒng)的方法增長(zhǎng)很快，而隨著版本數(shù)的增加，類牛頓迭代表現(xiàn)了很好的計(jì)算性能和良好的可擴(kuò)展性．

Fig．4 Comparison of semiring provenance with different versions．圖4 不同演化版本下的半環(huán)多項(xiàng)式溯源比較

7 結(jié)束語

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

［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

國家自然科學(xué)基金項(xiàng)目（61472070）；國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃基金項(xiàng)目（2012CB316201）

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