機率資料庫查詢處理關鍵技術研究

《機率資料庫查詢處理關鍵技術研究》是依託中國人民大學，由覃飆擔任項目負責人的面上項目。

基本介紹

• 中文名：機率資料庫查詢處理關鍵技術研究
• 項目類別：面上項目
• 項目負責人：覃飆
• 依託單位：中國人民大學

項目摘要

由於測量精度限制、網路延遲以及採樣誤差等因素導致不確定數據在現實生活中無處不在，我們用機率資料庫來管理這些不確定數據。當機率資料庫採用元組關聯模型時，我們擬用圖模型來表達它們，並用一階機率圖模型來描述其結果元組的推理過程；還要研究查詢語句安全的充要條件，並提出生成安全外延執行計畫的算法。當機率資料庫採用元組獨立模型時，本項目擬根據結果元組世系圖的特點，從圖論提出判斷結果元組為唯讀一次範式的理論，並導出元組機率的推理算法。本項目擬研究查詢語句與貝葉斯網路推理方法之間的映射關係，並在此基礎上生成最佳化的安全計畫或高效的內涵查詢策略。本項目還將研究協同內涵和外延兩種基本策略來高效地執行非安全查詢語句的技術，並通過索引和物化視圖來提高系統的性能。最後，研發一個機率資料庫原型系統，對我們提出的理論和算法進行驗證和分析。本項目的工作不僅對機率資料庫查詢處理有直接的意義，而且對其存儲管理等方面有理論指導。

結題摘要

數據的不確定性在很多領域都有，比如感測器網路和RFID網路，我們用機率資料庫來管理這些不確定數據。本項目研究塊分離概論資料庫上的安全執行計畫，該問題是概論資料庫的一個基本問題。我們提出了兩種新的數據模型，關聯表和擴展的關聯表；接著我們提出了一種混合的投影，它的原子操作包括首先執行不相交投影然後執行獨立投影在BID表上；此外，我們提出了一種高效的算法來在BID中找到安全的執行計畫。本項目還研究了元組獨立的機率資料庫中不等式查詢，這類查詢分為路徑類型、樹類型和圖類型，並提出了高效的查詢處理策略來計算不等式查詢的機率。 經典的數據挖掘算法需要修改和擴充來挖掘不確定數據對象，否則挖掘的精度將由於數據的不確定性而大大降低。我們為不確定的數值屬性和字元屬性定義了不確定數據模型，在此基礎上提出新的EMU算法來聚類不確定數據對象。該算法經過精心設計基於不確定數據對象發現分散式參數以便最大化模型的質量，因此能夠正確的區分不同的類。我們的聚類算法能夠處理數值和字元數據，在實驗中我們採用合成的和真實數據來評估我們算法的高效性和健壯性。 貝葉斯網路能夠推導出事件的機率，是典型的不確定推理套用。微分和干預分別是貝葉斯網路和因果網的基本操作，我們揭示了這兩種操作的聯繫，我們首先提出了一個新的表示模型部分干預表（PIT）來編碼因果網中對一個結點的多干預。利用PIT，我們引入了聯合樹算法來求因果網中所有變數的全乾預。我們接著發現經典算法只有當微分結點能夠到達證據結點時才能夠正確計算貝葉斯網路的微分。如果該條件不能滿足，經典算法將不能正確計算微分。基於此，我們發現干預的微分語義。 連線查詢語句的結果元組在世系的責任問題，我們把一類IQ查詢的世系分為路徑世系和複合世系。我們首先把路徑世系編輯為世系圖，然後把世系圖轉換為矩陣。接著我們把計算路徑世系責任的問題歸約為最小路徑問題，該問題能夠把動態規划算法在PTIME時間內求解。本項目進一步證明複合世系的責任能夠分解為路徑世系的責任求解。因此，本項目的第一個主要結論是IQ查詢世系的責任能夠在PTIME時間內求解。我們把先前的求解世系責任在等值連線查詢推廣到不等值連線查詢。當把複合世系分解為路徑世系後，進行責任計算的數據量降低了超過一個數量級。因此我們的算法能夠高效地計算複合世系的責任。最後，本項目提出了一個貪婪算法，它把計算一般世系的責任歸約為集合覆蓋問題。