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

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

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

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

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

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

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