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

吳愛華

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

0 引言

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

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