基于標(biāo)記的不一致數(shù)據(jù)查詢處理框架

吳愛華

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

0 引言

盡管完整性約束用于防止不一致已有多年，不一致關(guān)系數(shù)據(jù)仍普遍存在于多類現(xiàn)實(shí)應(yīng)用中，涵蓋系統(tǒng)集成與數(shù)據(jù)整合［1］、數(shù)據(jù)交換、Web 信息抽取、信息檢索［2］、科學(xué)數(shù)據(jù)管理和傳感器網(wǎng)絡(luò)等多個(gè)應(yīng)用領(lǐng)域.不一致數(shù)據(jù)蘊(yùn)含著錯(cuò)誤信息，在這樣的數(shù)據(jù)庫上回答用戶查詢，得到的結(jié)果也可能是錯(cuò)誤的.而錯(cuò)誤數(shù)據(jù)對企事業(yè)單位的日常工作、經(jīng)營管理、決策等的不良影響和經(jīng)濟(jì)損害不言而喻.因此，怎樣回答不一致數(shù)據(jù)庫上的查詢，如何保證查詢回答準(zhǔn)確可信，就成為亟待解決的實(shí)際問題.

但不一致數(shù)據(jù)上的查詢處理比傳統(tǒng)關(guān)系數(shù)據(jù)的查詢處理復(fù)雜得多，哪怕只有互相矛盾的記錄存在.首先，從理論模型上看，這是一個(gè)全、準(zhǔn)、復(fù)雜度難以權(quán)衡的難題.如果在計(jì)算查詢回答時(shí)排除所有不一致記錄，雖返回給用戶的結(jié)果確定可信，卻不可避免地丟失不一致記錄中的確定部分［3］.而若要把所有可能的確定回答都返給用戶，則其計(jì)算復(fù)雜度非常高.有研究［4］表明，不一致數(shù)據(jù)庫對應(yīng)的全部確定數(shù)據(jù)庫的求解是NP 完全問題.其次，給出好的理論模型，還要尋找高效的查詢處理算法，以便能在不影響一致數(shù)據(jù)管理和商用RDBMS 使用的基礎(chǔ)上，實(shí)現(xiàn)不一致數(shù)據(jù)的管理和查詢，使用戶仍能從不一致數(shù)據(jù)中獲得有價(jià)值的查詢結(jié)果.最后，盡管用戶希望能從不一致數(shù)據(jù)庫上得到唯一可信的查詢回答，但其概率本質(zhì)使得這樣的查詢結(jié)果不存在，須從語義上重新思考查詢結(jié)果的可信性及其價(jià)值.

標(biāo)記描述常被用于協(xié)同數(shù)據(jù)處理領(lǐng)域，如基因序列識別、蛋白質(zhì)數(shù)據(jù)管理、天文數(shù)據(jù)處理、多樣性物種歸類和協(xié)同文檔處理.這類應(yīng)用要求多用戶參與同一數(shù)據(jù)的收集、修改和處理，為了分享觀點(diǎn)，標(biāo)記常被用來解釋和糾正數(shù)據(jù)，或否定其他用戶的觀點(diǎn).不一致數(shù)據(jù)正是典型的有爭議共享數(shù)據(jù)，只是標(biāo)記對象不是協(xié)同文件或分子結(jié)構(gòu)，而是一組組不一致數(shù)據(jù).

文獻(xiàn)［5］和［6］針對違反函數(shù)依賴且主碼可信的不一致關(guān)系數(shù)據(jù)，提出一種基于標(biāo)記的查詢回答的研究方案(簡稱AQA)，通過區(qū)分查詢回答中一致和不一致的部分，給用戶可靠且信息量最大的查詢回答.在AQA中，不一致性是數(shù)據(jù)的屬性，可用標(biāo)記加以描述;關(guān)系中的每個(gè)單元值都可附加0 至多個(gè)標(biāo)記，有標(biāo)記的單元值不一致，反之一致.且標(biāo)記能隨著查詢計(jì)算從源數(shù)據(jù)庫正確地遷徙到查詢回答中.通過標(biāo)記的使用，原數(shù)據(jù)庫和查詢回答中的不一致信息都不會被過濾掉，可避免信息丟失.文獻(xiàn)［5］證明該方案的有效性和完備性.

但傳統(tǒng)的關(guān)系代數(shù)運(yùn)算并不支持AQA，已有DBMS 的SQL 查詢處理模塊也不支持不一致標(biāo)記的計(jì)算.為了能把AQA 應(yīng)用到現(xiàn)存各類不一致關(guān)系數(shù)據(jù)庫上，須研究其實(shí)現(xiàn)方法.

對于不確定數(shù)據(jù)的管理和查詢，僅已形成少數(shù)幾個(gè)實(shí)用系統(tǒng)［7-14］.已有系統(tǒng)大多以PostgreSQL 等開源RDBMS為基礎(chǔ)，擴(kuò)展或重新編寫其查詢處理模塊，形成專門的不確定數(shù)據(jù)庫管理系統(tǒng).這類系統(tǒng)不能很好地與Oracle，DB2，Sysbase 等現(xiàn)有商用RDBMS 相融合.但現(xiàn)有商業(yè)RDBMS 穩(wěn)定成熟，新系統(tǒng)即便能同時(shí)管理和查詢確定和不確定數(shù)據(jù)，也難以取代它們.另外，新系統(tǒng)還需定義全新的查詢語言，給用戶帶來一定的負(fù)擔(dān).

本文以文獻(xiàn)［5］和［6］提出的理論模型為依據(jù)，采用查詢重寫的方法實(shí)現(xiàn)一個(gè)不一致數(shù)據(jù)查詢處理系統(tǒng)——AQA 系統(tǒng)，它是RDBMS 與用戶之間的一類中間件，能將任意傳統(tǒng)SQL 查詢翻譯成能返回帶信任標(biāo)記的SQL 查詢集，由已有的RDBMS 響應(yīng).該系統(tǒng)雖效率稍低，但勝在:(1)能內(nèi)嵌到現(xiàn)有數(shù)據(jù)庫應(yīng)用系統(tǒng)中;(2)用戶無須掌握新查詢語言，沒有學(xué)習(xí)負(fù)擔(dān).

此外，本系統(tǒng)還有以下優(yōu)點(diǎn):(1)支持屬性一級的不一致數(shù)據(jù)的檢測和查詢處理;(2)能同時(shí)處理來自不同DBMS 維護(hù)的不一致數(shù)據(jù);(3)除初始標(biāo)記外，該實(shí)現(xiàn)方案無須其他預(yù)處理或后處理，基本遵從關(guān)系數(shù)據(jù)模型，不影響一致數(shù)據(jù)的管理和查詢處理.

1 不一致數(shù)據(jù)帶標(biāo)記的查詢回答

1.1 基本概念

給定一個(gè)數(shù)據(jù)庫D 及其上的完整性約束集合CI，如果?c∈CI，使得D|≠c，那么數(shù)據(jù)庫D 不一致.本文假設(shè)CI中只包含函數(shù)依賴，且主碼確定，那么違反某約束的記錄在被決定因素上的分量就不一致.

所有不一致分量都可附加一個(gè)以上的標(biāo)記，以識別查詢結(jié)果中不可信的部分.雖然初始數(shù)據(jù)庫中分量的不一致性不會在查詢估值中改變，但有些一致分量會因違反蘊(yùn)含約束而在查詢結(jié)果中不一致.為此，本系統(tǒng)采用兩種標(biāo)記:靜態(tài)標(biāo)記和動態(tài)標(biāo)記.前者描述初始數(shù)據(jù)庫中的不一致分量，示以符號“* ”;后者描述僅在查詢結(jié)果中不一致的分量，標(biāo)記符號為導(dǎo)致該分量不一致的決定因素的屬性名.圖1 給出一個(gè)不一致數(shù)據(jù)庫及其標(biāo)記的例子，其中student表上的查詢Q1中，“EE081”班的Teacher 因違反CName→Teacher 而標(biāo)以“* ”，而“EE081”班的Cellphone 則因違反蘊(yùn)含依賴CName→Cellphone，而被附上動態(tài)標(biāo)記“Class.CName”.靜態(tài)標(biāo)記不會變，但動態(tài)標(biāo)記則可能在查詢處理中創(chuàng)建和消亡.

定義2 根據(jù)給定域等和ArmStrong 公理系統(tǒng)，蘊(yùn)含依賴(Derived FD)是那些不屬于給定函數(shù)依賴集F，但屬于F+的函數(shù)依賴.

定義3 標(biāo)記過的關(guān)系(annotated relation).對于任意給定關(guān)系r 及其上的函數(shù)依賴集CI，?x→y∈CI，?t1，t2∈r，如 果t1［x］=t2［x］但t1［y］≠t2［y］，t1［y］和t2［y］都被附上標(biāo)記，那么r是一個(gè)依據(jù)CI標(biāo)記過的關(guān)系.

定義4 帶標(biāo)記的查詢回答(annotation-based query answer).對于任意給定關(guān)系r，其上的函數(shù)依賴集CI及查詢Q，設(shè)C'I是CI在Q(r)上的投影，C″I是Q(r)上的蘊(yùn)含依賴集，如果Q(r)依據(jù)C'I和C″I標(biāo)記過，那么Q(r)是一個(gè)帶標(biāo)記的查詢回答.

圖1(c)的表格即是一個(gè)帶標(biāo)記的查詢回答.

1.2 數(shù)據(jù)模型

為了在存儲上區(qū)分一致分量和不一致分量，本文擴(kuò)展傳統(tǒng)的關(guān)系數(shù)據(jù)模型，對每一個(gè)字段C，增加字段CA，用于存儲記錄在C 上分量的信任標(biāo)記.如果t［C］不一致，那么t［CA］是由一個(gè)或多個(gè)標(biāo)記組成的字符串，否則為空值.新增字段只能由系統(tǒng)更新.

此外，因大多RDBMS 只支持主碼和外碼，本文還在數(shù)據(jù)庫中增加一些描述原始約束和蘊(yùn)含約束的系統(tǒng)表，以存儲數(shù)據(jù)庫上的函數(shù)依賴集.

2 AQA 系統(tǒng)框架

AQA 系統(tǒng)由查詢重寫、初始標(biāo)記、初始標(biāo)記維護(hù)和蘊(yùn)含約束計(jì)算等4個(gè)模塊組成，見圖2.

圖2 AQA 的系統(tǒng)框架

蘊(yùn)含約束計(jì)算模塊根據(jù)給定函數(shù)依賴和域等關(guān)系計(jì)算關(guān)系模式上所有的蘊(yùn)含依賴.查詢結(jié)果上成立的蘊(yùn)含函數(shù)依賴是源關(guān)系模式上成立的蘊(yùn)含依賴在其上的投影.源關(guān)系模式不變，其蘊(yùn)含函數(shù)依賴就不變.查詢處理時(shí)僅需求解其在查詢結(jié)果上的投影.此處一次計(jì)算可用于任意查詢處理中，效率提高.

初始標(biāo)記模塊在數(shù)據(jù)載入時(shí)運(yùn)行，該模塊依據(jù)給定函數(shù)依賴集(不包括蘊(yùn)含依賴)給不一致分量附加靜態(tài)標(biāo)記.

數(shù)據(jù)日常維護(hù)后，初始標(biāo)記可能無法正確表示其語義，另外，約束改變時(shí)不一致性也需重新計(jì)算.初始標(biāo)記維護(hù)模塊包括全維護(hù)和增量維護(hù)兩個(gè)子模塊，全維護(hù)模塊根據(jù)最新函數(shù)依賴集重新檢測數(shù)據(jù)的不一致性，用于約束集合改變時(shí)的標(biāo)記維護(hù)，增量維護(hù)模塊在記錄值改變時(shí)根據(jù)當(dāng)前函數(shù)依賴重新計(jì)算其不一致性，它們均以觸發(fā)器的形式實(shí)現(xiàn).

查詢重寫模塊在整個(gè)系統(tǒng)中最重要.對用戶提交的常用SQL 語句，該模塊會將其翻譯成一系列可得到帶標(biāo)記查詢結(jié)果的SQL 語句，這組SQL 語句計(jì)算蘊(yùn)含依賴在查詢結(jié)果上的投影、并依據(jù)每個(gè)蘊(yùn)含依賴計(jì)算查詢結(jié)果中的動態(tài)標(biāo)記.

另外，為了測試性能，本系統(tǒng)還包括一個(gè)數(shù)據(jù)產(chǎn)生器，依據(jù)圖1 所示的數(shù)據(jù)庫模式及其函數(shù)依賴產(chǎn)生給定大小和臟數(shù)據(jù)比例的人工數(shù)據(jù).

盡管數(shù)據(jù)庫中新增的約束表和每張表的標(biāo)記字段會有一定的硬盤開銷，它們并不改變原始記錄，AQA 仍支持傳統(tǒng)SQL 查詢;從性能上講，現(xiàn)實(shí)應(yīng)用不會經(jīng)常改變數(shù)據(jù)模式，因此系統(tǒng)中的初始標(biāo)記模塊和蘊(yùn)含約束計(jì)算模塊很少執(zhí)行，全維護(hù)模塊也幾乎不運(yùn)行.除查詢重寫和標(biāo)記維護(hù)外，所有模塊都可在數(shù)據(jù)庫不太忙時(shí)運(yùn)行，對用戶影響有限.

3 關(guān)鍵問題

3.1 不一致分量的初始檢查標(biāo)記算法

初始標(biāo)記主要依據(jù)給定的函數(shù)依賴集檢查違反約束的分量.這里假設(shè)待標(biāo)記數(shù)據(jù)庫遵從3NF 且主碼一致.具有相同主碼的記錄可被認(rèn)作同一實(shí)體，其不同屬性值就不一致.另外，由于主碼一致，檢測時(shí)可忽略兩類約束:一是被決定因素是主屬性的函數(shù)依賴，二是決定因素是其他候選碼的函數(shù)依賴.

算法1 首先極小化輸入的函數(shù)依賴集，確保主碼對其他字段的函數(shù)依賴在待處理的函數(shù)依賴集中.剔除上述兩類函數(shù)依賴，對剩余任意函數(shù)依賴x→y，設(shè)數(shù)據(jù)庫中有兩條記錄t1和t2，t1［x］=t2［x］且t1［y］!=t2［y］，則將標(biāo)記“* ”添加到t1［yA］和t2［yA］中.該算法須對每個(gè)函數(shù)依賴掃描一遍數(shù)據(jù)庫，能標(biāo)記所有主碼正確的3NF 數(shù)據(jù)庫.

3.2 標(biāo)記增量維護(hù)

靜態(tài)標(biāo)記在兩種情況下需加以維護(hù):一是日常記錄維護(hù)，二是數(shù)據(jù)庫模式改變(此時(shí)原有標(biāo)記可能無法正確反映數(shù)據(jù)的不一致性).數(shù)據(jù)庫模式改變又可分成:(1)數(shù)據(jù)庫結(jié)構(gòu)改變，如增加新表及其上的約束、刪除表、增加字段、修改字段或刪除字段;(2)約束改變，增加或刪除某些表上的約束.

日常記錄維護(hù)可能使標(biāo)記與其語義不符.記錄增加時(shí)，AQA 采用觸發(fā)器1 檢測該記錄是否與表中的其他記錄矛盾;記錄值修改后，AQA 采用觸發(fā)器2檢測并修改其靜態(tài)標(biāo)記;記錄刪除雖不會帶來新的標(biāo)記，但可能改變其他記錄的不一致性，AQA 采用觸發(fā)器3 檢測并修改靜態(tài)標(biāo)記.

對于模式改變:首先，修改字段并不會影響數(shù)據(jù)和約束，無須任何處理;其次，數(shù)據(jù)庫表或表中字段的刪除，AQA 僅簡單地將標(biāo)記和數(shù)據(jù)一起刪除;再次，由于新增表暫時(shí)無數(shù)據(jù)，靜態(tài)標(biāo)記可延后維護(hù)，同樣采用觸發(fā)器1 在增加記錄時(shí)維護(hù)其靜態(tài)標(biāo)記，類似地，新增字段也可留待修改其值時(shí)維護(hù)標(biāo)記;最后，增加新約束需通過觸發(fā)器4 對整個(gè)表按此約束重新檢測并標(biāo)記不一致分量，刪除約束時(shí)要對違反了該約束的記錄用觸發(fā)器5 檢測并修改標(biāo)記.

觸發(fā)器1 UpdateAnno_Insert

觸發(fā)器2 UpdateAnno_update

觸發(fā)器3 UpdateAnno_Delete

觸發(fā)器4 UpdateAnno_AddFD

觸發(fā)器5 UpdateAnno_DelFD

3.3 查詢重寫方法

采用查詢重寫的方法在標(biāo)記過的關(guān)系數(shù)據(jù)庫上為任意用戶輸入的所有SQL 語句(除了統(tǒng)計(jì)查詢和含相關(guān)子查詢的嵌套查詢之外)，計(jì)算其基于標(biāo)記的查詢回答.除了為初始數(shù)據(jù)庫創(chuàng)建初始標(biāo)記之外，這個(gè)實(shí)現(xiàn)方案不需要其他的預(yù)處理或者后處理，也不會改變現(xiàn)有關(guān)系數(shù)據(jù)庫及其應(yīng)用系統(tǒng).

select-project-join 查詢(SPJ 查詢)可以重寫成包含3 類查詢的一組查詢:第一類查詢只有一個(gè)，創(chuàng)建包含所有可能違反蘊(yùn)含依賴記錄的表;第二類查詢修改上一步所得臨時(shí)表的動態(tài)標(biāo)記，對于每個(gè)蘊(yùn)含依賴，都有一個(gè)這樣的update 查詢;第三類查詢也只有一個(gè)，用于檢索并合并所有可能的查詢結(jié)果及其標(biāo)記.

蘊(yùn)含約束則采用算法2 求得.

算法2:DerivedFD

輸入:數(shù)據(jù)庫模式r，r 上的函數(shù)依賴及其域等屬性集

輸出:r 上成立的函數(shù)依賴集

(1)將所有給定函數(shù)依賴的右邊逐一替換為它的域等屬性(如果存在的話)，然后將得到的函數(shù)依賴加入函數(shù)依賴集.

(2)將所有給定函數(shù)依賴的左邊屬性逐一替換為其域等屬性(如果存在的話)，再將得到的函數(shù)依賴加入函數(shù)依賴集.

(3)若函數(shù)依賴集中存在函數(shù)依賴A→B，C→D，且B域等于C，則將函數(shù)依賴A→C，A→D，B→D 加入函數(shù)依賴集.

(4)重復(fù)第(3)步直到函數(shù)依賴集不再變化為止.

(5)刪除所得函數(shù)依賴集中重復(fù)的和已知的函數(shù)依賴.

返回最后的函數(shù)依賴集.

4 實(shí) 驗(yàn)

完成實(shí)驗(yàn)的配置如下:Intel Celeron 420 2.0 GHZ CPU，1GB 內(nèi)存，Windows XP+SP2，SQL Server 2000，編程語言是C#和VC 6.0.

實(shí)驗(yàn)共使用兩組8個(gè)數(shù)據(jù)庫.第1 組數(shù)據(jù)庫規(guī)模均為1GB 左右，但臟數(shù)據(jù)比例分別為1%，5%，10%，15%;第2 組數(shù)據(jù)庫中臟數(shù)據(jù)比例均為5%，但規(guī)模分別為0.13，0.54，1.00和1.50 GB.

查詢共11個(gè):q1～q6均為單表查詢;q7為嵌套查詢;q8和q9分別是2 張表和3 張表之間的自然連接;q10是并查詢;q11是差查詢.

本組實(shí)驗(yàn)旨在查詢重寫的性能，比較它在大小不同和臟數(shù)據(jù)比例不同的數(shù)據(jù)源上的時(shí)間性能表現(xiàn).

如圖3(a)所示，當(dāng)數(shù)據(jù)庫大小不變，而臟數(shù)據(jù)比例增大時(shí)，非連接查詢的時(shí)間性能變化不大，而連接查詢的時(shí)間消耗對于臟數(shù)據(jù)比例呈線性增長.這是因?yàn)殡S著不一致數(shù)據(jù)的增加，在連接結(jié)果集上需驗(yàn)證的不一致分量隨之增加.另外，當(dāng)臟數(shù)據(jù)比例不變，而數(shù)據(jù)庫大小逐步增大時(shí)(如圖3 (b)所示)，查詢q3，q4，q5，q10和q11變化不大，此時(shí)雖然數(shù)據(jù)庫變大，但符合查詢條件的記錄卻不變，且在查詢條件上建有索引，因此時(shí)間消耗基本不變;查詢q2，q6和q7的時(shí)間隨著數(shù)據(jù)庫的增大而增大，雖然它們也無蘊(yùn)含依賴的驗(yàn)證，但因條件字段上無索引，需全表掃描，時(shí)間消耗自然會增加;查詢q8和q9的時(shí)間消耗會隨著數(shù)據(jù)庫的增大而迅速增加，其主要原因在于蘊(yùn)含依賴檢驗(yàn)所需的時(shí)間隨著數(shù)據(jù)庫的增大而增大;q9的時(shí)間消耗比q8更多，原因是其需驗(yàn)證的蘊(yùn)含依賴更多.

5 結(jié)束語

不一致數(shù)據(jù)的查詢與管理是近期的一個(gè)難點(diǎn)和熱點(diǎn)問題.本文以前期理論工作為基礎(chǔ)，實(shí)現(xiàn)了不一致數(shù)據(jù)的查詢處理系統(tǒng).該系統(tǒng)能處理大多數(shù)用戶查詢，支持常用謂詞，如NOT，IN，BETWEEN，…，AND，LIKE，EXISTS 等;支持屬性級的不一致數(shù)據(jù)的檢測和查詢處理;能同時(shí)處理不同DBMS 維護(hù)的不一致數(shù)據(jù);除初始標(biāo)記之外，無須其他預(yù)處理或后處理，基本遵從關(guān)系數(shù)據(jù)模型，不影響一致數(shù)據(jù)的管理和查詢處理.

［1］ANDRITSOS P，F(xiàn)UXMAN A，MILLER R J.Clean answers over dirty databases［C］// Proc 22nd Int Conf on Data Eng.Atlanta:IEEE Comput Soc，2006:30.

［2］SEN P，DESHPANDE A.Representing and querying correlated tuples in probabilistic databases［C］// Proc 23rd Int Conf on Data Eng，Istanbul，Turkey:IEEE Comput Soc，2007:596-605.

［3］ARENAS M，BERTOSSI L E，CHOMICKI J.Consistent query answers in inconsistent databases［C］// Proc PODS Conf，Philadelphia:ACM，1999:68-79.

［4］LOPATENKO A，BERTOSSI L.Complexity of consistent query answering in databases under cardinality based and incremental repair semantics［C］// Proc 11th Int Conf of Database Theory.Barcelona:Springer-Verlag，2007:179-193.

［5］WU Aihua，TAN Zijing，WANG Wei.Annotation based query answer over inconsistent database［J］.J Comput Sci ＆ Technol (JCST)，2010，25(3):467-479.

［6］吳愛華，談子敬，汪衛(wèi).不一致數(shù)據(jù)庫上帶信任標(biāo)記的查詢結(jié)果［J］.軟件學(xué)報(bào)，2012，23(5):1167-1182.

［7］HUANG Jiewen，ANTOVA L，KOCH C，et al.MayBMS:a probabilistic database management system proc［C］// Proc.ACM SIGMOD Int Conf on Mana of Data.Rhode Island，USA:ACM，2009:1071-1074.

［8］AGRAWAL P，BENJELLOUN O，DAS SARMA A，et al.Trio:a system for data，uncertainty，and lineage［C］// Proc 32th Conf on Very Large Data Bases，New York:ACM，2006:1151-1154.

［9］JAMPANI R，PEREZ L，WU M，et al.MCDB:a Monte Carlo approach to managing uncertain data［C］// Proc ACM SIGMOD Int Conf on Management of Data，Vancouver，Canada，ACM 2008:687-700.

［10］BOULOS J，DALVI N，MANDHANI B，et al.MYSTIQ:a system for finding more answers by using probabilities［C］// Proc ACM SIGMOD Int Conf on Mana of Data，Baltimore:ACM，2005:891-893.

［11］WANG D Z，MICHELAKIS E，GAROFALAKIS M，et al.BayesStore:Managing Large，Uncertain Data Repositories with Probabilistic Graphical Models［J］// J Proc VLDB Endowment 2008(1):340-351.

［12］SINGH S，MAYFIELD C，MITTAL S，et al:Orion 2.0:native support for uncertain data［C］// Proc ACM SIGMOD Int Conf on Management of Data，Vancouver，Canada，ACM 2008:1239-1242.

［13］SARMA A D，BENJELLOUN O，HALEVY A，et al.Representing uncertain data:models，properties，and algorithms［J］.The VLDB J，2009，18(5):989-1019.

［14］Nilesh Dalvi，Chris Re，Dan Suciu.Probabilistic databases:diamonds in the dirt［J］.Commun of the ACM，2009，52(7)，86-96.