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

江 彤

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

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

江 彤

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

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

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

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

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

1 相關(guān)工作

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

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

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

表1 ZW表

表2 GZ表

2 方法概述

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

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

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

例如在已知的有限條件下，我們對(duì)動(dòng)態(tài)對(duì)象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。這時(shí)，當(dāng)出現(xiàn)M(C)時(shí)，顯然無(wú)論P(yáng)(M(C))多大，只要它發(fā)生，其和就大于1。

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

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

圖1 概率變化

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

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

定義3 條件關(guān)系概率(Conditions probability)：我們?cè)谝延械臈l件概率定義的基礎(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事件同時(shí)發(fā)生的可能性，即條件關(guān)系概率。令x是模式A的一個(gè)元組，x發(fā)生的概率用p(x)表示，y是模式B的一個(gè)元組， 概率是p(y)，則p(x×y)=A??B 。

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

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

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

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

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

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

3 查詢操作

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

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

根據(jù)3.1根據(jù)定義1和定義2，對(duì)(表1,表2)查詢。這里根據(jù)事件之間的條件概率關(guān)系，先對(duì)其做其做笛卡爾處理，然后進(jìn)行查詢。這里產(chǎn)生(張三，教授，4500，0.3)，(張三，教授，5000，0.3)兩條MAX記錄，顯然我們只能對(duì)其進(jìn)行第二種優(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)系的分布式反映(格式不對(duì))

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

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

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

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

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

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

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

所得結(jié)果的概率值最大，反映了其在動(dòng)態(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 效果

若存在條件概率相等的情況則輸出工資期望(職位對(duì)應(yīng)的概率與職位對(duì)應(yīng)的的薪資的概率及薪資的乘積) 相對(duì)較高的記錄所對(duì)應(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ù)庫(kù)查詢的方法——穩(wěn)態(tài)處理方法，主要通過(guò)分析了動(dòng)態(tài)世界中大量不確定事件的內(nèi)在聯(lián)系，對(duì)事件發(fā)生的可能性進(jìn)行了概率化，將產(chǎn)生事件之間的條件關(guān)系概率，作為事件發(fā)生的參考依據(jù)，同時(shí)把事件發(fā)生的最大條件關(guān)系概率作為事件的準(zhǔn)確性，其中最大條件關(guān)系概率值最大即為所查詢事件的穩(wěn)態(tài)，以反映事件的動(dòng)態(tài)屬性。

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

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

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

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

[5]王潔,鞠實(shí)兒.數(shù)據(jù)庫(kù)中不完善信息的邏輯描述[J].華南理工大學(xué)學(xué)報(bào)，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é)研究項(xiàng)目(11C0699)。

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

TP311.123

A

1673-0712(2011)05-0116-04