非一致性數據庫關鍵詞 非聚集約束查詢與性能分析

摘要:在分析非一致性數據庫一致性查詢方法的基礎上，結合非聚集約束條件，以關鍵詞為元數據，利用B樹與二叉樹的原理，提出一種新的針對非一致性數據庫的查詢方法#65377;通過節點分組訪問#65380;分層迭代查詢的方法，不僅解決非一致性數據庫約束條件難寫的問題，而且容易組合選擇查詢條件，有助于提高查詢的靈活性與準確性#65377;

關鍵詞:非一致性數據庫;完整性約束;修改;一致性查詢;非聚集約束

中圖分類號:TP311文獻標志碼:A

文章編號:1001-3695(2007)10-0107-03



數據庫信息技術經歷了幾十年的發展過程，已提出了許多經典的數據庫操作實現方法#65377;然而這些方法所研究的主要對象是滿足一定約束條件的數據庫系統，畢竟一直以來數據庫設計都要求滿足數據庫的數據完整性，如實體完整性#65380;域完整性#65380;引用完整性和用戶定義完整性，這些約束有效地保證了數據的完整性和有效性，使數據符合現實世界的實體規則，有利于數據的生成與查詢#65377;但隨著互聯網的飛速發展，網絡迅速成為一種重要的信息傳播和交換手段#65377;尤其是在Web 上，有著極其豐富的數據來源，這些大量產生的數據并不總能維持數據庫的一致性#65377;如表1所示，同一個員工編號卻有兩份不同的工資，顯然違背了數據庫的完整性#65377;所以如何對非一致性數據庫進行有效操作成為當前研究的課題之一#65377;非一致性數據庫就是違背數據完整性約束的數據庫，其中含有違背完整性約束的數據#65377;那么怎樣對一個非一致性數據庫進行有效管理?能否通過簡單強加一組約束條件或者靠清理掉其中的非一致性數據來恢復整個數據庫的一致性?怎樣從非一致性數據庫中準確有效地查找數據?本文將結合非一致性數據庫的研究成果分析這些問題#65377;

1相關工作

首先是什么原因形成了非一致性數據庫?在給定了約束條件，數據庫為什么變成非一致性數據庫?主要有以下幾種情況:

a)當數據從多個數據源被集成，每個數據源可以滿足約束(如鍵約束)，但當移植到一起時，可能就不能滿足約束(如每個數據源有相同的鍵值)#65377;更普遍的情況是，當數據是被兩個獨立的具有不同約束的數據源交換時，這個被交換的數據是不會滿足完整性約束的#65377;

b)新的約束條件被強加給一個已經存在的數據庫時#65377;

c)軟約束或用戶約束只有當查詢得到答案后才會被考慮，但這些約束并沒有得到系統的強化#65377;

d)在一般情況下，檢測約束的一致性代價是非常昂貴的，特別是在帶有更新頻繁的負載事務系統中#65377;

e)數據庫管理系統(DBMS)自己本身并沒有一個保持完整性約束的機制#65377;

以上幾種情況只是造成數據庫不一致的重要原因之一，隨著數據庫應用領域的不斷擴大，完整性約束不能很好地維持數據庫一致性的問題日益突出，不可能為了保持數據的一致性而人為地對數據庫中的非一致性數據進行修改或刪除，這樣會造成處理代價昂貴;當數據庫很大時，這種處理也是不現實的，而且還可能會導致有用的數據丟失，或者不清楚怎么存儲一致性數據#65377;所以，在很多情況下必須保持數據庫的非一致性，在不能合理地恢復數據庫一致性的前提下，對非一致性數據庫進行有效管理方面的研究就顯得非常必要#65377;

針對非一致性數據庫的研究，國外的研究比國內的要多，也比國內起步早，如Pontificia Universidad Cat’olica de Chile計算機學院的M. Arenas等人[1]在1999年就提出了數據清理#65377;認為非一致性數據庫管理的一個策略就是數據清洗，識別和糾正數據中的錯誤，恢復數據庫到一致性狀態#65377;然而清除數據庫中的非一致性數據可能會造成某些有用信息的丟失，這是用戶不希望發生的#65377;現在對非一致性數據庫的研究主要方法有修改#65380;一致性查詢#65380;查詢重寫[1~4]和關鍵詞搜索方法[5~7]#65377;

數據修改的方法就是對數據進行重新組合，讓重復的數據經過組合后只出現一次，如表1所示，重新組合后的結果有(t1，t2，t4)，(t1，t3，t4)#65377;這種方法的結果是每次修改都是一個盡可能與原不一致數據庫接近的一致性數據庫#65377;雖然這種方法不會造成數據丟失，也滿足了數據庫的數據完整性，但須經過多次比較組合，效率較差，而且有時選擇的也許是用戶并不需要的組合#65377;一致性查詢就是查詢語句在一個數據庫上執行后返回的結果是一致性的，對非一致性數據庫也是如此#65377;因為非一致性數據庫是違背完整性約束的，所以常規查詢語句返回的結果可能并不是一致性結果#65377;這就需要對常規查詢語句進行一定的修改，添加一些修改條件，其效率與修改無異，但準確率卻比修改要高#65377;而查詢重寫就是在查詢語句上加一組約束條件，在非一致性數據庫上，對初始查詢返回的結果進行一次篩選，只有滿足約束條件的結果才會最終返回給用戶，所以它是在選擇的基礎上剔除不滿足條件的數據#65377;如下列TSQL語句所示:

select distinct eid from db_roll r where salary>2000 and not exists (select * from db_roll r′where r′.eid=r.eid and r′.salary <=2000)

這種方法很好地利用了TSQL語句的靈活性，也方便操作，能夠選擇符合條件的結果，但需要比較整個數據表單，而且只適合熟悉TSQL語句的人員#65377;

針對關鍵詞搜索方面，國內與國外的研究方法比較多，如文獻[5]中利用聚集約束條件進行查找，但這種方式也有其不足，數據與約束條件不分離，不利于對檢索數據進行動態操作;文獻[6]中基于關鍵詞的查詢方法，把數據庫當做是由數據庫中的元組(頂點)通過主碼—外碼關系(邊)連接而成的圖，當用戶給出一個關鍵詞查詢時，則通過全文索引從圖中找出含全部關鍵詞的最小子圖作為查詢結果;文獻[7]中基于聚集的方法查找數據，利用“加權支持度”概念計算元組和聚類間相似度的方法，保證了計算的合理性，并給出一種新的適合大規模可分類數據的聚類算法#65377;文獻[6，7]效率雖高，但都沒有針對非一致性數據庫進行研究，可這些對研究非一致性數據庫卻提供了好的研究策略#65377;

本文以一致性查詢條件為基礎，以關鍵詞為元數據，采用非聚集約束條件，利用B樹與二叉樹的原理，提出一種新的針對非一致性數據庫的查詢方法，通過對節點分組訪問#65380;分層迭代查詢的方法，不僅解決了約束條件難寫的問題，而且易組合選擇條件，有助于查詢的靈活性與準確性#65377;

從測試結果可以看出，當查詢語句中的非聚集約束條件較多而且數據庫記錄較大時，非聚集約束查詢的效率就會變得明顯，在今天大硬盤的時代，這種利用空間換時間的代價也是可以接受的#65377;

5結束語

本文描述了基于非一致性數據庫關鍵詞非聚集約束查詢的理念與實驗方法，通過對TSQL查詢重寫，使系統能夠更快地響應用戶的查詢，并得到一致性結果#65377;但非一致性數據庫的研究在國內剛剛起步，因此還有很多路要走，在未來的工作中計劃結合UML將操作形式化，同時與設計模式相結合，提出更具體的實現方案，特別是針對分布式系統上的索引技術的具體應用，也希望由此引起國內更多的關注#65377;

參考文獻:

[1]ARENAS M，BERTOSSI L，CHOMICKI J.Consistent query answers in inconsistent databases[C]//Proc of ACM PODS.1999:6879.

[2]BARCELO P，BERTOSSI L.Logic programs for querying inconsistent databases[C]//Proc of PADL.[S.l.]:Springer，2003:208-222.

[3]FUXMAN A，FAZLI E，MILLER R J. ConQuer:efficient management of inconsistent databases[C]//Proc ofthe ACM SIGMOD Int Conf Management of Data.2005:155166.

[4]ARENAS M，BERTOSSI L E，CHOMICKI B J.Specifying and querying database repairs using logic programs with exceptions[C]//Proc of the 4th Int Conf on Flexible Query Answering Systems (FQAS 2000).2000:27-41.

[5]FLESCA S，FURFARO F，PARISI F.Consistent query answers on numerical databases under aggregate constraints[C]//Proc of arXiv:cs. DB/0505059.2005:118.

[6]文繼軍，王珊. SEEKER:基于關鍵詞的關系數據庫信息檢索[J].軟件學報，2005，16(7): 1270 1281.

[7]楊向榮，沈鈞毅，王瑞.一種可分類數據的聚類算法及其應用[J].微電子學與計算機，2002(8):30- 33.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”