張美茹

（常州鐵道高等職業(yè)技術(shù)學(xué)校 軌道交通系，江蘇 常州 213011）

概率數(shù)據(jù)庫中元組間關(guān)系的表示

張美茹

（常州鐵道高等職業(yè)技術(shù)學(xué)校 軌道交通系，江蘇 常州 213011）

文章從介紹概率數(shù)據(jù)庫的概念入手，分析了在實(shí)際應(yīng)用中為了更靈活地操作關(guān)系中的元組，在原來的概率數(shù)據(jù)庫基礎(chǔ)上增加對(duì)元組之間存在的關(guān)系操作的必要性。文章提出在概率數(shù)據(jù)庫中表示元組間存在的各種關(guān)系的方法，并且對(duì)這種改進(jìn)進(jìn)行了可行性分析。

概率數(shù)據(jù)庫；元組；關(guān)系表示；模型

1 概率數(shù)據(jù)庫的概念

傳統(tǒng)的關(guān)系數(shù)據(jù)庫處理的是確定的精確的數(shù)據(jù)，對(duì)不確定的非精確數(shù)據(jù)無能為力，描述的是靜態(tài)的世界。然而，現(xiàn)實(shí)世界中的事物都是不斷變化的，為了在數(shù)據(jù)庫中描述對(duì)象的動(dòng)態(tài)性，文章引入了概率數(shù)據(jù)庫，它除了描述靜態(tài)的對(duì)象外，而且通過給對(duì)象增加一個(gè)概率屬性來描述動(dòng)態(tài)對(duì)象或?qū)ο蟮膭?dòng)態(tài)方面。

1996年Dey和Sarkar提出了一種概率關(guān)系數(shù)據(jù)模型—PRM模型（Probabilistic Relational Model），該模型所描述的數(shù)據(jù)庫結(jié)構(gòu)模式稱為概率關(guān)系數(shù)據(jù)庫模式簡(jiǎn)稱為概率關(guān)系模式，是在數(shù)據(jù)庫的每個(gè)元組中引入概率標(biāo)記Sp（probabilistic sign）屬性表示該元組的不確定性。概率關(guān)系模式R為屬性名的集合{A1，A2，…，An}，其中屬性之一為概率屬性，用符號(hào)Sp表示，對(duì)應(yīng)于每個(gè)屬性Ai（i=1，2，…，n）有一個(gè)值域Di。若Ai為Sp，則Di（0，1］。積集D=｛D1，D2，…，Dn｝稱為R的值域。r是R上一個(gè)關(guān)系，r的每個(gè)元組x是R到D的一個(gè)函數(shù)，表示某一對(duì)象的各屬性的綜合可信度或者說是某一事物發(fā)生的可能程度。

2 在原有的概率數(shù)據(jù)庫模型基礎(chǔ)上增加元組間關(guān)系處理功的必要性

許多應(yīng)用領(lǐng)域中產(chǎn)生了彼此間存在一定關(guān)系的數(shù)據(jù)，數(shù)據(jù)的合并導(dǎo)致關(guān)系中出現(xiàn)了同一個(gè)對(duì)象的重復(fù)元組。因此必須將這些元組間的關(guān)系定義為互斥的。由網(wǎng)絡(luò)傳感器產(chǎn)生的數(shù)據(jù)在時(shí)空上都是高度相關(guān)的。因此要求概率數(shù)據(jù)庫有處理元組間關(guān)系的功能。

然而原有的概率數(shù)據(jù)庫都是基于元組間相互獨(dú)立的假設(shè)的。但是即使假設(shè)初始數(shù)據(jù)元組間相互獨(dú)立在對(duì)關(guān)系數(shù)據(jù)庫進(jìn)行操作（如連接操作）過程中產(chǎn)生的中間元組間也存在一定的關(guān)系。此外在對(duì)原來的概率數(shù)據(jù)庫進(jìn)行查詢操作時(shí)只能得到用傳統(tǒng)查詢語言表示時(shí)的查詢結(jié)果的一個(gè)子集。針對(duì)上面的問題，有不少學(xué)者對(duì)這個(gè)模型進(jìn)行了改進(jìn)，主要是通過限制查詢集合的范圍或者是限制元組間允許存在的關(guān)系。但是這不能滿足實(shí)際應(yīng)用的需求?；谏厦娴睦碛?，文章在下一節(jié)中提出了一種表示元組間關(guān)系的方法。

3 概率數(shù)據(jù)庫中元組間關(guān)系的表示以及概率的計(jì)算

首先看一個(gè)在假設(shè)元組間相互獨(dú)立時(shí)的查詢過程的例子。文章分別列出了兩個(gè)概率關(guān)系Sp，Tp，表示兩個(gè)關(guān)系中元組所有可能的組合及各種組合出現(xiàn)的概率（為了直觀、精確地描述查詢過程而引入）；進(jìn)行操作后得到的結(jié)果；計(jì)算結(jié)果元組的概率。

概率是將各元組在查詢結(jié)果中出現(xiàn)或不出現(xiàn)的概率相乘得到的。可以看到執(zhí)行操作后只有3種組合會(huì)出現(xiàn)在結(jié)果關(guān)系中，然后將重復(fù)出現(xiàn)的元組的概率相加后用一個(gè)元組來表示。

現(xiàn)在假設(shè)基本元組s1，s2，t1之間不是獨(dú)立的，下面來看假設(shè)它們之間存在下列3種關(guān)系時(shí)的情況：（1）（這種關(guān)系用implies表示），即t1和s1，s2不能同時(shí)出現(xiàn)在結(jié)果關(guān)系中；（（用mut.ex表示），即t1和s1互斥；（用nxor表示），即t1與s1存在正相關(guān)關(guān)系。

概率分別為各種關(guān)系下各種組合在結(jié)果關(guān)系中出現(xiàn)的條件概率。可以看出當(dāng)基本元組間存在的關(guān)系不同時(shí)，各種組合在查詢結(jié)果中出現(xiàn)的概率不同。執(zhí)行同樣的操作得到的結(jié)果關(guān)系中元組的概率也不相同，而且求得的概率也不相同。由此可見，在某些應(yīng)用場(chǎng)合，基于基本元組間相互獨(dú)立假設(shè)的條件下建立的概率數(shù)據(jù)庫并不能精確地表示或操作數(shù)據(jù)庫中的對(duì)象。概率數(shù)據(jù)庫具有根據(jù)處理數(shù)據(jù)的特征對(duì)其進(jìn)行靈活設(shè)置的特點(diǎn)。

描述的數(shù)據(jù)庫模型同樣有缺點(diǎn)。在各種關(guān)系下結(jié)果元組的概率是通過一張pwd（Dp）表計(jì)算出來的，當(dāng)基本元組的數(shù)目相當(dāng)大時(shí)，pwd（Dp）表中的項(xiàng)就會(huì)以指數(shù)倍的速度增長(zhǎng)，計(jì)算所有項(xiàng)在結(jié)果關(guān)系中出現(xiàn)的條件概率就會(huì)變得不可能。針對(duì)這個(gè)問題，本文提出了如下解決辦法。

（1）用一個(gè)函數(shù)f(x)來表示元組間的這種關(guān)系。（2）每個(gè)元組都用一個(gè)隨機(jī)變量（Xi）表示（i為元組在集合中出現(xiàn)的位置）。Xi的取值范圍為{0，1}分別表示該元組的不出現(xiàn)和出現(xiàn)。Pr(Xi)表示Xi出現(xiàn)的概率。X是元組的集合可表示為X={X1，…，Xn}。計(jì)算概率的公式為：

上面是一般的求解方法，分別計(jì)算每個(gè)元組的條件概率然后將它們相加。下面按某種關(guān)系將元組分組，對(duì)每個(gè)組分別求其條件概率然后將它們相加。這樣做的好處是可以將一個(gè)大的問題分解成多個(gè)小的問題進(jìn)行解決。而且由于各分組間相互獨(dú)立，所以對(duì)各個(gè)分組的處理可以采用并發(fā)進(jìn)行，這樣可以提高計(jì)算速度，同時(shí)問題的規(guī)模也隨著計(jì)算的進(jìn)行成指數(shù)倍地減少，隨機(jī)變量的減少必然會(huì)降低計(jì)算的難度。從而使問題得到簡(jiǎn)化。此外，如果問題中出現(xiàn)的隨機(jī)變量過多，采用上面的方法計(jì)算時(shí)，由于無法預(yù)先知道下一步計(jì)算要使用的數(shù)據(jù)，必須將所有可能用到的數(shù)據(jù)一次性導(dǎo)入到內(nèi)存中，而內(nèi)存空間是有限的而且通常都很小，所以這種做法是不現(xiàn)實(shí)的。而采用下面的方法的話，問題就解決了。

當(dāng)然在概率數(shù)據(jù)庫模型中增加元組間關(guān)系的處理功能所涉及的問題不僅僅是對(duì)關(guān)系的表示和概率的計(jì)算。對(duì)數(shù)據(jù)庫進(jìn)行各種操作時(shí)也會(huì)出現(xiàn)一些問題，如中間元組的表示、概率計(jì)算等等，還要對(duì)上面的模型作進(jìn)一步詳細(xì)設(shè)計(jì)。如何解決由此帶來的處理效率下降的問題也是學(xué)界面臨的一大難題。目前有許多學(xué)者正在進(jìn)行這方面的研究，而且對(duì)于一些問題已經(jīng)有了理想的解決方法。

4 結(jié)語

為了滿足應(yīng)用的需要，在原來的概率數(shù)據(jù)庫模型的基礎(chǔ)上增加元組關(guān)系處理的功能，這種做法的可行性已經(jīng)得到了證明。并且具體的實(shí)現(xiàn)方法的原型已經(jīng)研究出來了，目前還有許多學(xué)者正在對(duì)其進(jìn)行深入研究和不斷優(yōu)化。深信在不久的將來這種改進(jìn)會(huì)體現(xiàn)在實(shí)際的應(yīng)用當(dāng)中。

[1]PRITHVIRAJ S, AMOL D.Representing and Querying Correlated Tuples in Probabilistic Databases[J].International Council for Open and Distance Education，2007（7）：102-105.

[2]李啟金，袁鼎榮.概率數(shù)據(jù)模型的分析研究[J].廣西教育學(xué)院學(xué)報(bào)，2000（5）：47-50.

[3]高紅梅，馬元元，孫志揮.基于概率關(guān)系數(shù)據(jù)庫模型的研究[J].東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2000（2）：17-20.

[4]袁鼎榮，嚴(yán)小衛(wèi)，陳宏朝.一個(gè)新的概率數(shù)據(jù)模型[J].廣西教育學(xué)院學(xué)報(bào)，2003（10）：65-67.

Representation of tuple relations in a probabilistic databasec

Zhang Meiru
（Road Traffic Department of Changzhou Railway Higher Vocational and Technical School, Changzhou 213011, China）

Starting with the introduction of the concept of probability database, this paper analyzes the necessity to increase operations of relationships existing in the tuples based on the original database for being more flexible to operating the tuples in relationship in practical application. The methods for representing all kinds relationships existing in tuples in probability database have been put forward and feasibility analysis about the improvement was done in this paper.

probabilistic databases; tuples; relational representation; model

張美茹（1978— ），女，江蘇常州，碩士，副教授；研究方向：數(shù)據(jù)庫。