概率數據庫中元組間關系的表示

張美茹

（常州鐵道高等職業技術學校 軌道交通系，江蘇 常州 213011）

概率數據庫中元組間關系的表示

張美茹

（常州鐵道高等職業技術學校 軌道交通系，江蘇 常州 213011）

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

概率數據庫；元組；關系表示；模型

1 概率數據庫的概念

傳統的關系數據庫處理的是確定的精確的數據，對不確定的非精確數據無能為力，描述的是靜態的世界。然而，現實世界中的事物都是不斷變化的，為了在數據庫中描述對象的動態性，文章引入了概率數據庫，它除了描述靜態的對象外，而且通過給對象增加一個概率屬性來描述動態對象或對象的動態方面。

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

2 在原有的概率數據庫模型基礎上增加元組間關系處理功的必要性

許多應用領域中產生了彼此間存在一定關系的數據，數據的合并導致關系中出現了同一個對象的重復元組。因此必須將這些元組間的關系定義為互斥的。由網絡傳感器產生的數據在時空上都是高度相關的。因此要求概率數據庫有處理元組間關系的功能。

然而原有的概率數據庫都是基于元組間相互獨立的假設的。但是即使假設初始數據元組間相互獨立在對關系數據庫進行操作（如連接操作）過程中產生的中間元組間也存在一定的關系。此外在對原來的概率數據庫進行查詢操作時只能得到用傳統查詢語言表示時的查詢結果的一個子集。針對上面的問題，有不少學者對這個模型進行了改進，主要是通過限制查詢集合的范圍或者是限制元組間允許存在的關系。但是這不能滿足實際應用的需求。基于上面的理由，文章在下一節中提出了一種表示元組間關系的方法。

3 概率數據庫中元組間關系的表示以及概率的計算

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

概率是將各元組在查詢結果中出現或不出現的概率相乘得到的。可以看到執行操作后只有3種組合會出現在結果關系中，然后將重復出現的元組的概率相加后用一個元組來表示。

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

概率分別為各種關系下各種組合在結果關系中出現的條件概率。可以看出當基本元組間存在的關系不同時，各種組合在查詢結果中出現的概率不同。執行同樣的操作得到的結果關系中元組的概率也不相同，而且求得的概率也不相同。由此可見，在某些應用場合，基于基本元組間相互獨立假設的條件下建立的概率數據庫并不能精確地表示或操作數據庫中的對象。概率數據庫具有根據處理數據的特征對其進行靈活設置的特點。

描述的數據庫模型同樣有缺點。在各種關系下結果元組的概率是通過一張pwd（Dp）表計算出來的，當基本元組的數目相當大時，pwd（Dp）表中的項就會以指數倍的速度增長，計算所有項在結果關系中出現的條件概率就會變得不可能。針對這個問題，本文提出了如下解決辦法。

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

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

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

4 結語

為了滿足應用的需要，在原來的概率數據庫模型的基礎上增加元組關系處理的功能，這種做法的可行性已經得到了證明。并且具體的實現方法的原型已經研究出來了，目前還有許多學者正在對其進行深入研究和不斷優化。深信在不久的將來這種改進會體現在實際的應用當中。

[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]李啟金，袁鼎榮.概率數據模型的分析研究[J].廣西教育學院學報，2000（5）：47-50.

[3]高紅梅，馬元元，孫志揮.基于概率關系數據庫模型的研究[J].東南大學學報（自然科學版），2000（2）：17-20.

[4]袁鼎榮，嚴小衛，陳宏朝.一個新的概率數據模型[J].廣西教育學院學報，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— ），女，江蘇常州，碩士，副教授；研究方向：數據庫。