包含完整性約束的概率關(guān)系數(shù)據(jù)庫更新和查詢優(yōu)化方法研究.pdf

1、隨著數(shù)據(jù)清洗、傳感器網(wǎng)絡(luò)、追蹤移動物體等應用對不確定數(shù)據(jù)的管理要求越來越高，概率關(guān)系數(shù)據(jù)模型作為一個對不確定數(shù)據(jù)進行有效管理的重要模型，自2003年開始引起學術(shù)界和工業(yè)界開始高度關(guān)注。從形式上說，一個概率關(guān)系數(shù)據(jù)庫是一組傳統(tǒng)關(guān)系數(shù)據(jù)庫上（可能世界）的概率分布，而完整性約束是關(guān)系數(shù)據(jù)上的重要信息，因此，提出一個包含完整性約束的概率關(guān)系數(shù)據(jù)庫模型，并研究該模型上的更新與查詢方法具有重要意義。
　　針對目前大部分的不確定數(shù)據(jù)模型研究著重

2、于描述具體數(shù)據(jù)之間的約束關(guān)系，而沒有考慮模式級別的約束關(guān)系的問題，提出了一個包含完整性約束的概率關(guān)系數(shù)據(jù)庫模型。不確定數(shù)據(jù)模式級別的完整性約束信息能捕捉動態(tài)更新下的數(shù)據(jù)間的關(guān)聯(lián)關(guān)系，因此，利用基于約束的概率關(guān)系數(shù)據(jù)庫更新，自動更新數(shù)據(jù)間的關(guān)聯(lián)關(guān)系，有效防止了概率關(guān)系數(shù)據(jù)庫包含不合理的可能世界的發(fā)生。由于現(xiàn)有將不確定數(shù)據(jù)從可能世界集合表示方式轉(zhuǎn)化為基于變量的表示方式的數(shù)據(jù)模型轉(zhuǎn)化方法導致元組表達式十分冗長，通過分析元組表達式的生成規(guī)則，提

3、出了一個高效的數(shù)據(jù)模型轉(zhuǎn)化方法。該轉(zhuǎn)化方法基于一個消除表達式中重復變量的公式，減少了后續(xù)查詢在處理元組表達式的計算開銷。實驗表明該數(shù)據(jù)模型轉(zhuǎn)化方法在沒有增加額外時間開銷的前提下，大大簡化了元組表達式，且提高了后續(xù)查詢的處理效率。
　　為了解決目前基于約束的概率關(guān)系數(shù)據(jù)庫更新方法枚舉概率關(guān)系數(shù)據(jù)庫中元組的表達式里出現(xiàn)的所有變量的取值，而導致的高時間復雜度的問題，提出了一個高效的更新方法。該方法只需考慮在約束中出現(xiàn)的變量取值，且采用變

4、量替換機制更新元組的表達式，避免了概率關(guān)系數(shù)據(jù)庫中其他變量的參與。實驗表明該方法在各種參數(shù)配置下，都優(yōu)于現(xiàn)有的更新方法。
　　針對目前基于約束的概率關(guān)系數(shù)據(jù)庫更新方法，在獲取相關(guān)變量滿足約束的取值集合這個十分耗時的重要步驟中，沒有考慮針對常見的函數(shù)依賴約束的特征進行優(yōu)化的問題，提出了兩種更新優(yōu)化策略。剪枝策略將相關(guān)元組的表達式單獨遍歷，避免了遍歷一個由各相關(guān)元組表達式組合而成的復雜表達式，減少了遍歷到的變量數(shù)量，從而減少了獲取相關(guān)

5、變量滿足約束的取值集合的時間。在剪枝策略的基礎(chǔ)上，變量消除策略合并多個滿足約束且對應相同可能世界的變量取值來最小化新生成的變量數(shù)目，利于后續(xù)的查詢處理。實驗結(jié)果表明剪枝策略能進一步提高基于約束的概率關(guān)系數(shù)據(jù)庫更新方法的效率，而變量消除策略能在不帶來額外開銷的情況下減少新生成的變量數(shù)量。
　　針對目前大部分的概率關(guān)系數(shù)據(jù)庫上的一般查詢優(yōu)化方法著重于研究加速查詢結(jié)果世系邏輯表達式，而沒有考慮在查詢處理過程中生成簡化的結(jié)果世系表達式的問

6、題，提出了一個利用模式級別的約束信息來簡化查詢結(jié)果世系數(shù)據(jù)表達式的優(yōu)化方法。分別利用函數(shù)依賴約束和引用完整性約束這兩種模式級別的信息對兩種關(guān)系操作的世系數(shù)據(jù)給出了簡化的生成方式。假設(shè)查詢對于概率關(guān)系數(shù)據(jù)庫有重要應用價值。為了避免目前基于生成新數(shù)據(jù)庫版本通用處理方法會帶來額外更新開銷的問題，提出了一種利用條件概率來處理假設(shè)查詢的優(yōu)化方法。該方法通過計算結(jié)果在假設(shè)條件下的條件概率，避免了不必要的概率關(guān)系數(shù)據(jù)庫更新。實驗結(jié)果驗證了一般查詢優(yōu)化