基于標記的不一致數據查詢處理框架

吳愛華

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

0 引言

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

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

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

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

但傳統的關系代數運算并不支持AQA，已有DBMS 的SQL 查詢處理模塊也不支持不一致標記的計算.為了能把AQA 應用到現存各類不一致關系數據庫上，須研究其實現方法.

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

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

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

1 不一致數據帶標記的查詢回答

1.1 基本概念

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

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

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

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

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

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

1.2 數據模型

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

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

2 AQA 系統框架

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

圖2 AQA 的系統框架

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

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

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

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

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

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

3 關鍵問題

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

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

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

3.2 標記增量維護

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

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

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

觸發器1 UpdateAnno_Insert

觸發器2 UpdateAnno_update

觸發器3 UpdateAnno_Delete

觸發器4 UpdateAnno_AddFD

觸發器5 UpdateAnno_DelFD

3.3 查詢重寫方法

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

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

蘊含約束則采用算法2 求得.

算法2:DerivedFD

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

輸出:r 上成立的函數依賴集

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

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

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

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

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

返回最后的函數依賴集.

4 實 驗

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

實驗共使用兩組8個數據庫.第1 組數據庫規模均為1GB 左右，但臟數據比例分別為1%，5%，10%，15%;第2 組數據庫中臟數據比例均為5%，但規模分別為0.13，0.54，1.00和1.50 GB.

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

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

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

5 結束語

不一致數據的查詢與管理是近期的一個難點和熱點問題.本文以前期理論工作為基礎，實現了不一致數據的查詢處理系統.該系統能處理大多數用戶查詢，支持常用謂詞，如NOT，IN，BETWEEN，…，AND，LIKE，EXISTS 等;支持屬性級的不一致數據的檢測和查詢處理;能同時處理不同DBMS 維護的不一致數據;除初始標記之外，無須其他預處理或后處理，基本遵從關系數據模型，不影響一致數據的管理和查詢處理.

［1］ANDRITSOS P，FUXMAN 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］吳愛華，談子敬，汪衛.不一致數據庫上帶信任標記的查詢結果［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.