吳愛華

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

0 引言

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

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

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

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

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

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

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

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

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

1.1 基本概念

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

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

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

定義3 標記過的關(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］都被附上標記，那么r是一個依據(jù)CI標記過的關(guān)系.

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

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

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

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

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

2 AQA 系統(tǒng)框架

AQA 系統(tǒng)由查詢重寫、初始標記、初始標記維護和蘊含約束計算等4個模塊組成，見圖2.

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

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

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

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

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

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

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

3 關(guān)鍵問題

3.1 不一致分量的初始檢查標記算法

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

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

3.2 標記增量維護

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

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

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

觸發(fā)器1 UpdateAnno_Insert

觸發(fā)器2 UpdateAnno_update

觸發(fā)器3 UpdateAnno_Delete

觸發(fā)器4 UpdateAnno_AddFD

觸發(fā)器5 UpdateAnno_DelFD

3.3 查詢重寫方法

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

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

蘊含約束則采用算法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)重復第(3)步直到函數(shù)依賴集不再變化為止.

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

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

4 實 驗

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

實驗共使用兩組8個數(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個:q1～q6均為單表查詢;q7為嵌套查詢;q8和q9分別是2 張表和3 張表之間的自然連接;q10是并查詢;q11是差查詢.

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

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

5 結(jié)束語

不一致數(shù)據(jù)的查詢與管理是近期的一個難點和熱點問題.本文以前期理論工作為基礎(chǔ)，實現(xiàn)了不一致數(shù)據(jù)的查詢處理系統(tǒng).該系統(tǒng)能處理大多數(shù)用戶查詢，支持常用謂詞，如NOT，IN，BETWEEN，…，AND，LIKE，EXISTS 等;支持屬性級的不一致數(shù)據(jù)的檢測和查詢處理;能同時處理不同DBMS 維護的不一致數(shù)據(jù);除初始標記之外，無須其他預處理或后處理，基本遵從關(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ù)庫上帶信任標記的查詢結(jié)果［J］.軟件學報，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.