江 彤

(湖南人文科技學(xué)院計算機科學(xué)技術(shù)系，婁底，417000)

穩(wěn)態(tài)的概率數(shù)據(jù)庫探討

江 彤

(湖南人文科技學(xué)院計算機科學(xué)技術(shù)系，婁底，417000)

現(xiàn)實世界中存在著大量不確定性信息，傳統(tǒng)關(guān)系數(shù)據(jù)庫都視他們?yōu)榭罩??；跀U展傳統(tǒng)關(guān)系數(shù)據(jù)庫模型處理概率數(shù)據(jù)方面的不確定性，可建立一種處理概率關(guān)系數(shù)據(jù)庫查詢方法——穩(wěn)態(tài)處理方法。該方法通過在關(guān)系模式中，為每條記錄指定適當(dāng)?shù)母怕?，表示不確定性信息，同時依據(jù)事物之間的聯(lián)系，確立事件的條件關(guān)系概率，其中最大條件關(guān)系概率值即為所查詢事件的穩(wěn)態(tài)。該方法對于處理大量不確定性信息，預(yù)測其最大可能性，具有重要意義。

不確定信息;條件關(guān)系概率;穩(wěn)態(tài)

在數(shù)據(jù)庫的基本研究中，數(shù)據(jù)分為確定性數(shù)據(jù)與不確定性數(shù)據(jù)。傳統(tǒng)關(guān)系數(shù)據(jù)庫的相關(guān)規(guī)則是建立在精確的數(shù)據(jù)之上，而不確定性數(shù)據(jù)充斥著整個世界，大致可分為模糊型和概率型兩種，其中對模糊數(shù)據(jù)的研究在國內(nèi)外已取得許多成果[1-3]。概率數(shù)據(jù)(probabilistic database)是指某一事件發(fā)生的可能性，文獻[4-6]都是國外關(guān)于概率數(shù)據(jù)庫研究的主要成果，大都表現(xiàn)在概率關(guān)系的定義上。2006年，Prithviraj Sen 和Amol Deshpande錯誤！未找到引用源。研究了概率數(shù)據(jù)庫元組的描述和查詢相互關(guān)聯(lián)的元組，認(rèn)為概率數(shù)據(jù)庫的發(fā)展主要受到兩個方面的限制：(1)當(dāng)前的概率數(shù)據(jù)庫對所舉的事例過于簡單，例如元組是相互完全獨立的，這就使得在實際的應(yīng)用中出現(xiàn)相互關(guān)聯(lián)的數(shù)據(jù)時，不能夠有效的計算。(2)大多數(shù)概率數(shù)據(jù)庫只能解決用傳統(tǒng)查詢語句描述的限制了的查詢語句。隨著計算機網(wǎng)絡(luò)的飛速發(fā)展和信息化的推進，概率數(shù)據(jù)庫這種處理不確定性問題的數(shù)據(jù)庫模型逐漸引起了人們的關(guān)注，但以前出現(xiàn)的概率數(shù)據(jù)庫研究，認(rèn)為元組在數(shù)據(jù)庫中的存在具有不確定性、屬性值具有不確定性、查詢應(yīng)答也具有不確定性。這使得人們在面對不確定問題時往往采取忽略的態(tài)度，在關(guān)系數(shù)據(jù)庫中視他們?yōu)榭罩怠Ｈ欢鉀Q不確定性問題、處理概率性數(shù)據(jù)的重大價值，使我們不得不重新定義概率數(shù)據(jù)模型。

本文為了處理概率數(shù)據(jù)方面的不確定性，建立了一種處理概率關(guān)系數(shù)據(jù)庫查詢的方法——穩(wěn)態(tài)處理方法，通過在關(guān)系模式中，為每條記錄指定適當(dāng)?shù)母怕剩硎静淮_定性信息，同時依據(jù)事物之間的聯(lián)系，確立事件的條件關(guān)系概率，其中最大條件關(guān)系概率值最大即為所查詢事件的穩(wěn)態(tài)。

1 相關(guān)工作

由于世界是動態(tài)的，對象或事物存在與否本身具有一定的可能性，對于大量不確定的信息，在前人工作的基礎(chǔ)上，我們繼續(xù)用一個概率值表示事物發(fā)生的可能性。通常大家把事件發(fā)生與否看成隨機事件，即事件存在n種可能時，每種可能發(fā)生的概率為1/n。隨著人們遇到問題的復(fù)雜程度的增加，特別是對于同一事件，可以從不同的可能性角度算出不同的概率。另一方面，隨著經(jīng)驗的積累，人們逐漸認(rèn)識到，在做大量重復(fù)試驗時，隨著試驗次數(shù)的增加，一個事件出現(xiàn)的頻率，總在一個固定數(shù)的附近擺動，顯示一定的穩(wěn)定性。R.von米澤斯把這個固定數(shù)定義為該事件的概率，即概率的頻率定義。

這里我們依照概率的頻率定義，把A(張三，教授)的概率設(shè)為0.6，B(張三，教務(wù)主任)的概率設(shè)為0.4，具體設(shè)置如(表1，表2)所示，對于同一個對象依照離散的隨機變量的分布情況，滿足0≤ps≤1，且∑p(ps)=1的屬性。張三的職務(wù)在教授和教務(wù)主任兩種可能，同時教授和教務(wù)的工資也是個動態(tài)量。依照一般的查詢處理，無法準(zhǔn)確得出張三，李四的具體身份及工資情況。為了使概率數(shù)據(jù)模型適合關(guān)系數(shù)據(jù)模型的查詢方法，我們以穩(wěn)態(tài)來反映不確定事件在動態(tài)世界的常態(tài)，通過查詢事件的穩(wěn)態(tài)，從條件概率關(guān)系的分布式中取得事件的穩(wěn)定狀態(tài)。

概率關(guān)系模式上的一個元組由對象屬性、動態(tài)屬性、概率屬性等組成, 它描述的不是傳統(tǒng)關(guān)系數(shù)據(jù)模型中的簡單對象, 而是動態(tài)對象( 包括動態(tài)的對象本身和對象的動態(tài)屬性) 的一個事件連同該事件發(fā)生的概率。形式上它類似傳統(tǒng)關(guān)系模式,實際是描述某事件發(fā)生的概率。所以不同的行描述的是不同的事件及其概率,同一事件不允許出現(xiàn)在同一關(guān)系之中。

表1 ZW表

表2 GZ表

2 方法概述

定義1 概率數(shù)據(jù)模式：我們擴展了文獻[1]的有關(guān)概率的定義即事物隨機試驗的每一種可能為一個樣本，它是最基本的元素。所有的樣本構(gòu)成事物的樣本空間，且其樣本空間滿足p(Ω)=1 的特性。設(shè)r是數(shù)據(jù)庫M的有一個實例，對于r事件發(fā)生的每一個可能，為一個樣本點，r滿足0≤p(r)≤，r事件發(fā)生的所有可能之和總為1的情況，由跟r類似的數(shù)據(jù)構(gòu)成就是概率數(shù)據(jù)庫。

張三是一個對象，其身份存在教授和教務(wù)主任兩種可能，滿足0.6+0.4=1的條件，其職務(wù)和工資的可能性也符合 0.3+0.3+0.28+0.12=1，李四跟張三的情形類似，都處于動態(tài)的關(guān)系中，由張三，李四構(gòu)成的數(shù)據(jù)表就是一個關(guān)于表1動態(tài)變概率數(shù)據(jù)表。表中數(shù)據(jù)的概率屬性是一個不確定性數(shù)據(jù)，是一個在有限的次數(shù)中積累的一個數(shù)據(jù)頻率。

定義2 由概率的性質(zhì)我們知道事件發(fā)生的概率之和滿足等于1的條件。然而對于動態(tài)世界中的動態(tài)事件永遠(yuǎn)處于一種不確定的條件下，我們不可能對事件發(fā)生的各種可能做出有效的判斷，這種不可能令數(shù)據(jù)庫處于一種非穩(wěn)定狀態(tài)。

例如在已知的有限條件下，我們對動態(tài)對象M的概率化處理得到P(M(A))=0.6 (M(A)表示M發(fā)生事件A)，P(M(B))=0.4 (M(B)表示M發(fā)生事件B)，其滿足P(M(A))+P(M(B))=1。這時，當(dāng)出現(xiàn)M(C)時，顯然無論P(M(C))多大，只要它發(fā)生，其和就大于1。

根據(jù)概率的頻率定義，在事件無限次發(fā)生的條件下，P(i)將為一個固定值，即動態(tài)事務(wù)對象產(chǎn)生各種可能性的概率值的比值為一個穩(wěn)定值。當(dāng)事件存在的有限種可能性中，設(shè)其概率P(i)(i≥1)，在滿足(1)式的情況下，P(0);P(1):…:P(i)=M:N:…:Z，當(dāng)i增加1或減少1時，滿足仍然滿足關(guān)系P(0);P(1):…:P(i)=M:N:…:Z不變。P(i+1)的值則通過如下求得：

(P(0)-P(i+1)*M/(M+N+…+Z)):(P(i+1)*N(M+N+…+Z))=M:N…:Z

圖1 概率變化

圖1可以清楚的反映當(dāng)原概率滿足1的情況下，隨著對象事件發(fā)生次數(shù)的增加出現(xiàn)新可能的變化，圖中(ps表示概率，n表示事件發(fā)生的次數(shù))。

如(表1)中，當(dāng)在添加一個元組C(張三，系統(tǒng)分析師)時，其概率滿足如下關(guān)系：A.ps ：B.ps ：C.ps=2/5 ： 4/15 ： 1/3 。這也反映了目前由于條件的限制，動態(tài)事件的各種可能性的記錄結(jié)果處于一種不確定不穩(wěn)定狀態(tài)，其主要特點就是目前我們收集數(shù)據(jù)源的數(shù)據(jù)是不確定的，并且數(shù)據(jù)處理過程也會產(chǎn)生一些不確定的結(jié)果。

定義3 條件關(guān)系概率(Conditions probability)：我們在已有的條件概率定義的基礎(chǔ)上再定義，設(shè)A，B?M，m為M上的關(guān)系。如果x，y∈m，x≠y，?c∈B，有x(A)=y(A)x(C)y(C)，?A稱為B前提事件，則元組x的可能值可看成在A事件發(fā)生的前提下B事件同時發(fā)生的可能性，即條件關(guān)系概率。令x是模式A的一個元組，x發(fā)生的概率用p(x)表示，y是模式B的一個元組， 概率是p(y)，則p(x×y)=A??B 。

如通過對表1、表2做笛卡爾積計算，得到條件關(guān)系概率值。通常情況下，關(guān)系數(shù)據(jù)庫一個元組唯一表示一個對象(實體/聯(lián)系)。而在概率數(shù)據(jù)模式中，每個元組不能唯一的表示一個對象，只能表示該對象的一種可能性分布。因而，依靠事件之間的關(guān)系雖然不能精確反映事物屬性，卻使事件的動態(tài)屬性與傳統(tǒng)的關(guān)系數(shù)據(jù)模式的靜態(tài)屬性轉(zhuǎn)化，為預(yù)測和查詢事件的最大可能奠定基礎(chǔ)。

由于世界是動態(tài)的，對象或事件存在與否本身具有一定的可能性。在存在的前提下，事件的發(fā)生也具有一定可能性。因此，對于查詢這些動態(tài)的數(shù)據(jù)的確定性記錄很能夠難實現(xiàn)，而只能依照事件發(fā)生的概率，來反映事件發(fā)生的穩(wěn)定狀態(tài)。

概率數(shù)據(jù)庫中，元組本身描述的是動態(tài)的對象事件，每一個元組表示某一個對象事件，一個對象可能出現(xiàn)幾個不同的事件，有幾個元組描述。令所有的可能事件為一個集合，某一個事件發(fā)生的可能性，即為其發(fā)生概率。概率數(shù)據(jù)模式形象的反映了事件發(fā)生的概率情況。然而，這些動態(tài)生成的數(shù)據(jù)往往是對研究動態(tài)世界中的穩(wěn)態(tài)產(chǎn)生干擾。如在(表三)中(李四，職務(wù)，工資，概率)關(guān)系里，其存在的四種可能使得我們無法對李四的身份得出精確的記錄。

當(dāng)遇到了不確定性問題，傳統(tǒng)研究方式往往采取的“去除不確定性”方法避開對不確定數(shù)據(jù)的管理。這里我們必須承認(rèn)數(shù)據(jù)中的不確定性問題，保留并處理不確定的中間結(jié)果，而不是通過種種確定化的手段去除不確定性，只有這樣才能真正解決概率數(shù)據(jù)模式中的不確定問題。這里我們采取數(shù)據(jù)查詢求取穩(wěn)態(tài)的方法處理這種不確定性問題。

方法1 查詢優(yōu)化一：設(shè)概率關(guān)系模式{P1，P2，…，Pn}上i元組的概率值為Pi(0≤Pi≤1)，對于該關(guān)系模式的查詢結(jié)果按照Pi的大小排序，以MAX(Pi)--最大概率值反映事件的穩(wěn)定狀態(tài)。MAX(Pi)即為穩(wěn)態(tài)。

對于概率關(guān)系模式{P1，P2，…，Pn}處理海量數(shù)據(jù)過程中，連接查詢是我們解決處于動態(tài)世界中不確定問題的主要手段。然而對于海量數(shù)據(jù)不可避免地會出現(xiàn)按照Pi的大小排序時，出現(xiàn)MAX值相等的兩個值。按方法1處理顯然很容易讓人產(chǎn)生迷惑。這時我們對數(shù)據(jù)進一步優(yōu)化。

3 查詢操作

實驗是在一臺有1G內(nèi)存的AMD Athlon(tm) 64 X2 Dual Core Processor 3600+ 2.01GHz的微機上進行的，操作系統(tǒng)是Windows XP ，利用SQLSERVER2005實現(xiàn)各部分功能。

概率數(shù)據(jù)系統(tǒng)所要面對的數(shù)據(jù)已經(jīng)不再局限于確定性的數(shù)據(jù)，而要處理很多非傳統(tǒng)方式產(chǎn)生的數(shù)據(jù)，這些數(shù)據(jù)往往是不準(zhǔn)確的，具有不確定性的本質(zhì)。我們以(表1 ZW表，表2 GZ表)兩表為例，對其我們無法實行精確查找。換句話說，我們查詢出來的元組不精確。如在(表1)查詢“張三“顯示的將是(張三，教授，0.6)，(張三，教務(wù)主任，0.4)兩條記錄。這里我們對表1查詢的結(jié)果優(yōu)化，即查詢結(jié)果為(張三，教授，0.6)。

根據(jù)3.1根據(jù)定義1和定義2，對(表1,表2)查詢。這里根據(jù)事件之間的條件概率關(guān)系，先對其做其做笛卡爾處理，然后進行查詢。這里產(chǎn)生(張三，教授，4500，0.3)，(張三，教授，5000，0.3)兩條MAX記錄，顯然我們只能對其進行第二種優(yōu)化處理方法。

SELECT ZW.姓名, ZW.職務(wù),ZW.準(zhǔn)確性 as 準(zhǔn)確性1,ZG.準(zhǔn)確性 as 準(zhǔn)確性2,

ZG.工資,ZW.準(zhǔn)確性 * ZG.準(zhǔn)確性 as 條件概率

FROM GZ INNER JOIN

ZW ON ZW.職位 = GZ.職位

WHERE ZW.姓名 = '張三'

表3 條件概率關(guān)系的分布式反映(格式不對)

當(dāng)某事件有n張子表，每張表中有n條記錄，當(dāng)我們對這n張表進行連接查詢時，按照條件概率處理方法其時間復(fù)雜度為O(nn)，很顯然這種方法處理不恰當(dāng)。由于我們需要的是在不確定性問題中反映事件穩(wěn)定狀態(tài)的數(shù)據(jù)，即最大的條件關(guān)系概率值。按照笛卡爾的運算方法，我們可以先對這n張表的每一張表的概率屬性值排序。我們知道排序的時間復(fù)雜度為O(n2)，這樣我們處理查詢的時間消耗明顯減少。全文變量斜體問題

通過對每張表排序在一定程度上解決了查詢的時間消耗問題，但同時產(chǎn)生了連接映射(join matching)不確定性問題，即模式匹配不確定性。

定義3 聯(lián)接匹配(join matching)： 以概率數(shù)據(jù)庫中的所有元組為全集M，每張Table的元組的作為集合T，T∈M，有交集Ri=Ti∩Tm(Ti,Tm∈M)，當(dāng)對數(shù)據(jù)查詢是先求兩表間的交集Ri，再依據(jù)其進行匹配查詢。

如在(表1，表2)中，其交集為職務(wù)。故對‘張三’進行查詢時，表1的MAX值為0.6，對應(yīng)教授職務(wù)，表2的MAX值為0.5，對應(yīng)教授職務(wù)，匹配成功。

依據(jù)前面的研究工作，我們對(表1)各元組發(fā)生的可能概率化，使不確定的動態(tài)信息數(shù)字化，以便使用關(guān)系數(shù)據(jù)的查詢模式。通過以上處理后得到表1、表2概率關(guān)系。

我們依照定義對檢索規(guī)則做如下規(guī)定：

先檢索該人的職位，取職位對應(yīng)的概率的最大值，再依據(jù)檢索出的職位檢索其對應(yīng)的工資及概率的最大值，再檢查是否聯(lián)接匹配，最后依照條件概率的乘法定理，得到其條件概率。

所得結(jié)果的概率值最大，反映了其在動態(tài)世界中出現(xiàn)的可能性最大，把它作為其穩(wěn)態(tài)。

SELECT top 1 ZW.姓名, ZW.職務(wù),

ZW.準(zhǔn)確性 as 準(zhǔn)確性1,ZG.準(zhǔn)確性 as 準(zhǔn)確2,ZG.工資,

ZW.準(zhǔn)確性 * ZG.準(zhǔn)確性 as 穩(wěn)態(tài)

FROM ZW INNER JOIN

GZ ON ZW.職務(wù) = CZ.ZW

WHERE ZW.姓名 = '李四'

order by ZW.準(zhǔn)確性 * GZ.準(zhǔn)確性 desc

表4 效果

若存在條件概率相等的情況則輸出工資期望(職位對應(yīng)的概率與職位對應(yīng)的的薪資的概率及薪資的乘積) 相對較高的記錄所對應(yīng)的職務(wù)及工資。

SELECT top 1 ZW.姓名, ZW.職務(wù),

ZW.準(zhǔn)確性 as 準(zhǔn)確性1,ZG.準(zhǔn)確性 as 準(zhǔn)確2,ZG.工資,

ZW.準(zhǔn)確性 * ZG.準(zhǔn)確性 as 穩(wěn)態(tài)

FROM ZW INNER JOIN

GZ ON ZW.職務(wù) = CZ.ZW

WHERE ZW.姓名 = '張三'

order by ZW.準(zhǔn)確性 * GZ.準(zhǔn)確性 * GZ.工資desc

表5 效果

本文建立了一種處理概率關(guān)系數(shù)據(jù)庫查詢的方法——穩(wěn)態(tài)處理方法，主要通過分析了動態(tài)世界中大量不確定事件的內(nèi)在聯(lián)系，對事件發(fā)生的可能性進行了概率化，將產(chǎn)生事件之間的條件關(guān)系概率，作為事件發(fā)生的參考依據(jù)，同時把事件發(fā)生的最大條件關(guān)系概率作為事件的準(zhǔn)確性，其中最大條件關(guān)系概率值最大即為所查詢事件的穩(wěn)態(tài)，以反映事件的動態(tài)屬性。

[1]汪榮貴，張佑生，彭青松.條件概率關(guān)系數(shù)據(jù)庫模型[J].微電子學(xué)與計算機,2002，21(9):7-11.

[2]李石群，鄭鵬，周洞汝.一種靈活的概率關(guān)系數(shù)據(jù)庫模式及代數(shù)[J].計算機工程與應(yīng)用,1999, 35 (11)：23-24.

[3]姬東耀，張軍英.一個概率關(guān)系專家數(shù)據(jù)庫模型[J].計算機工程與應(yīng)用,1999,35(6):75-77.

[4]蔣運承，張師超.一個不確定性數(shù)據(jù)庫模型及其語義[J].計算機科學(xué).1999，6(21)：78-81.

[5]王潔,鞠實兒.數(shù)據(jù)庫中不完善信息的邏輯描述[J].華南理工大學(xué)學(xué)報，2003,3(5):93-96.

[6]FAGIN R, LOTEM A, NAOR M. Optimal aggregation algorithms for middleware[J]. In Proceedings of the twentieth ACM IGMODSIGACT-SIGART symposium on Principles of atabase systems, 2001:102-113.

(責(zé)任編校：光明)

DiscussiononSteady-stateDatabases

JIANGTong

(Department of Computer Science and Technology, Hunan Institute of Humanities, Science and Technology, Loudi 417000, China)

There is a lot of uncertain information in the real world, and traditional relation database only regards it as null. Based on expanding the uncertainty of the traditional relation database model dealing with probability database, we may establish a method which called steady-state approach to deal with the probability of relational database queries. We designate the suitable probability for each record to express uncertainty information. At the same time, based on the links between things, we establish the conditions for the relationship between the probability of events, and the greatest probability is the largest event of inquiries by state. The method for dealing with a large number of uncertainties and forecast the possibility of its largest is very important.

uncertain information; condition relationship probability; steady-state

2011-07-12.

湖南省教育廳科學(xué)研究項目(11C0699)。

江彤(1978— )，女，湖南雙峰人，湖南人文科技學(xué)院計算機科學(xué)技術(shù)系講師，碩士，研究方向：數(shù)據(jù)處理。

TP311.123

A

1673-0712(2011)05-0116-04