概率查詢簡要算法研究

摘 要:現(xiàn)實世界中大量存在著不確定性的信息，但這些信息依然具有很好的使用價值，需要被檢索和利用。本文在總結(jié)前人工作的基礎上，結(jié)合概率數(shù)據(jù)庫理論，提出了一種比較簡單的概率查詢的一種算法。

關鍵詞:概率查詢 概率數(shù)據(jù)庫

中圖分類號:O21\t\t\t文獻標識碼:A\t\t\t文章編號:1672-3791(2011)10(a)-0242-01

隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡迅速成為一種重要的信息傳播和交換的手段，尤其是在Web上，有著極其豐富的數(shù)據(jù)來源，這些數(shù)據(jù)大多數(shù)是變化的，有些是有規(guī)律的變化，有些是無規(guī)律的變化，或者變化的規(guī)律是不確定的，對于有規(guī)律的變化，可以利用關系數(shù)據(jù)庫表示，而對于大量無規(guī)律的數(shù)據(jù)則無法用SQL準確查詢，因為這些 大量產(chǎn)生的無規(guī)律的數(shù)據(jù)并不總能維持關系型數(shù)據(jù)庫的一致性，往往會產(chǎn)生數(shù)據(jù)沖突，但這些信息仍然具有使用價值，不能簡單丟棄。

不確定數(shù)據(jù)通常采用概率數(shù)據(jù)模型的方式進行描述，這種模型對每個元組附加一個概率值來表示該元組的可靠程度。概率數(shù)據(jù)模型[1]不僅可以對關系數(shù)據(jù)模型無法描述的不確定數(shù)據(jù)進行描述，而且可以描述關系數(shù)據(jù)模型所能描述的確定的數(shù)據(jù)。對概率數(shù)據(jù)庫進行的查詢稱為概率查詢。

如圖所示，下圖中有兩個關系表，每一個關系表中都有一個概率屬性，說明了該元祖發(fā)生的概率。

本文嘗試利用概率統(tǒng)計的知識，利用足夠精確的代價計算方法探討這種信息轉(zhuǎn)換過程，并利用正確抽取數(shù)據(jù)元素特征方法減少代價計算成本，希望能有效降低這種轉(zhuǎn)換代價和由此產(chǎn)生的誤差。

1 算法概述

現(xiàn)在假設一個聚類代表一個實體，當這個聚類中的實體的概率為1的時候，該聚類的元組發(fā)生是相互獨立的，該元組發(fā)生的幾率就是必然發(fā)生了;反之若元組的概率為0的話，該元組就是必然不發(fā)生。這兩種情況先不研究。

首先，在這里，我們把一個元組的屬性分成這四種屬性:主屬性，特征屬性，動作屬性，概率屬性。其中，主屬性就是區(qū)分關系表中不同對象的屬性，比如賬號，代號;特征屬性就是伴隨主屬性而唯一確定的屬性，如姓名，表2中的行為屬性，這種屬性由主屬性唯一確定，如11002001對應的唯一姓名屬性就是張三。動作屬性就是該元組對象的不同動態(tài)行為，如存款，取款等，相同的主屬性可以有不同的動態(tài)屬性;概率屬性就是描述該動態(tài)對象在某一時刻、地點的動態(tài)行為。

使用了這種動態(tài)屬性之后，該關系表就不是傳統(tǒng)關系意義上的簡單對象，而是動態(tài)對象(包括動態(tài)對象本身和動態(tài)的對象屬性)的一個事件連同其發(fā)生的概率了。該關系表描述的是一個事件的發(fā)生概率，不同的行為描述的是不同的概率，同一事件不允許出現(xiàn)在同一關系中。

其中，數(shù)據(jù)庫的概率查詢可以分為兩個方面:(1)數(shù)據(jù)庫操作的概率化，根據(jù)相應條件，計算每個元組發(fā)生的概率;(2)查詢語句的概率化，通常需要在數(shù)據(jù)庫查詢過程前增加相應的語義分析，這里主要包含兩類情況，一類是直接含有概率條件的查詢語句，如列出“行為=′存錢′”且選擇概率大于等于0.7的賬號，其SQL語句如下。

賬號 行為=′存錢′∧(概率)=0.7)(Π(賬號，行為，概率)(表1))

那么綜合表1和表2的數(shù)據(jù)，我們可以得知賬號為的張三存款金額為11002001元的概率是0.8×0.6=0.48。

這是一個簡單的例子，但是給了我們一個很好的啟發(fā)，對于一些簡單的概率查詢有了一個一般性的思路。

2 算法實現(xiàn)

根據(jù)概率學上的全概率公式。

P(B)=P(B|A0)P(A0)+P(B|A1)P(A1)+…+P(B|AN)P(AN)，其中P(B|AN)是B在AN下的影響的概率，P(AN)是AN發(fā)生的概率。

我們可以對照前面兩個表進行類似的分析，比如我們要求賬號為11002001，存款金額為5000的元組信息。我們可以從第一個表中得知賬號為11002001存款的概率為0.8。我們記事件A1為“11002001存款”，那么事件B“存款金額為5000”，從而可以得到了11002001存款金額為5000元得概率是0.8×0.6=0.48.

由此，我們可以寫出一個查詢式子。

Select distance賬號，金額，sum(a..概率*b.概率)from表1a，表2b，where a..賬號=b.賬號。

簡單來說，這種算法的思路就在于把符合要求的元組進行簡單連接，然后將相應的概率相乘，然后將符合相同條件的元組相加。

3 結(jié)語

傳統(tǒng)的關系模式已經(jīng)不能很好的適用于對不確定性信息的處理了。本文通過對概率論的基礎知識進行處理，給出了對多表的一種簡單的查詢處理。這種新型的數(shù)據(jù)庫能夠?qū)Υ_定性數(shù)據(jù)和不確定性數(shù)據(jù)進行同時處理。

參考文獻

[1]\t劉波，雷剛躍，楊路明，等.非一致性數(shù)據(jù)概率查詢策略與算法分析[J].

[2]\t袁鼎榮，嚴小衛(wèi)，陳宏朝.一個新的概率數(shù)據(jù)模型[J].計算機應用研究.

[3]\t李石君，譚成予，劉海青，等.一種概率關系數(shù)據(jù)庫系統(tǒng)[J].

[4]\t李俊麗.概率算法及其算法研究[J].

[5]\tBarbara D，Garcla-Molina H，Porter D.The Management of Probabilistic Data[J].

[6]\tP.Barcelo，L.Bertossi．Logic programs for querying inconsistent databases[J].

[7]\tSurajit Chaudhuri，Gautam Das，Vagelis Hristidis etc.Probabilistic Ranking of Database Query Results[J].