王 艷，樂(lè)嘉錦，姜久雷，張 云

1.東華大學(xué) 旭日工商管理學(xué)院，上海 200061

2.上海海洋大學(xué) 信息學(xué)院，上海 201306

3.東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620

多維不確定性XML數(shù)據(jù)模型的研究

王 艷1，2，樂(lè)嘉錦3，姜久雷1，張 云2

1.東華大學(xué) 旭日工商管理學(xué)院，上海 200061

2.上海海洋大學(xué) 信息學(xué)院，上海 201306

3.東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620

1 引言

近年來(lái)，大量技術(shù)被應(yīng)用于海量數(shù)據(jù)的存儲(chǔ)和記錄，但是在很多情況下，數(shù)據(jù)本身存在錯(cuò)誤或者不完整性，同時(shí)數(shù)據(jù)的源事件也是存在大量不確定性。

在數(shù)據(jù)庫(kù)領(lǐng)域?qū)τ诓淮_定信息而言，最早是文獻(xiàn)[1]提出一種概率關(guān)系數(shù)據(jù)模型PRM及其關(guān)系代數(shù)，并在研究中用系統(tǒng)的觀點(diǎn)闡述了概率數(shù)據(jù)庫(kù)的有關(guān)理論，奠定了在數(shù)據(jù)庫(kù)中應(yīng)用概率論來(lái)處理不確定信息的基礎(chǔ)。

后來(lái)，不確定的數(shù)據(jù)模型也被擴(kuò)展到半結(jié)構(gòu)化的XML數(shù)據(jù)。XML概率模型具備XML的靈活性，可以很自然地表示多個(gè)粒度的概率信息，乃至嵌套的概率信息；另外XML以其自描述性好與可擴(kuò)展性高的優(yōu)點(diǎn)，特別適用于信息抽取與數(shù)據(jù)集成等可能產(chǎn)生大量不確定信息的應(yīng)用。

文獻(xiàn)[2]提出的P文檔模型（ProDB）是最早的概率XML數(shù)據(jù)模型，該模型描述節(jié)點(diǎn)的概率以父節(jié)點(diǎn)存在為前提，提出兄弟節(jié)點(diǎn)之間關(guān)系為相對(duì)獨(dú)立（ind）和相互排斥（mux）。文獻(xiàn)[3]和文獻(xiàn)[4]均擴(kuò)展了P文檔模型，其中文獻(xiàn)[4]對(duì)原有的P文檔模型的邊增加了外部約束條件，利用約束條件來(lái)限制節(jié)點(diǎn)出現(xiàn)概率。文獻(xiàn)[5]對(duì)P文檔模型給出了高效的查詢算法。文獻(xiàn)[6]提出了一種XML概率樹(shù)模型，該模型給各節(jié)點(diǎn)附加一系列事件變量，由外部事件的發(fā)生的概率決定節(jié)點(diǎn)的存在性，增加了數(shù)據(jù)表示的靈活度。文獻(xiàn)[7]對(duì)概率樹(shù)模型進(jìn)一步分析了查詢復(fù)雜度。文獻(xiàn)[8]提出了PXML模型，該模型是以有向圖為基礎(chǔ)的概率半結(jié)構(gòu)數(shù)據(jù)模型，把概率實(shí)例定義為半結(jié)構(gòu)實(shí)例及其對(duì)應(yīng)的概率值。文獻(xiàn)[9]提出了以概率區(qū)間值表示PXML的數(shù)據(jù)模型。文獻(xiàn)[10]提出的概率樹(shù)模型以及文獻(xiàn)[11]提出的PrXML模型等對(duì)概率模型進(jìn)行了進(jìn)一步的擴(kuò)充。

現(xiàn)有的XML概率模型在表達(dá)方式和表達(dá)效率上不斷演進(jìn)，但是由于一直在單維空間進(jìn)行表述，所以在描述復(fù)雜事件時(shí)依然存在一定缺陷。本文在目前已有的XML概率模型的基礎(chǔ)上，以建立描述多維復(fù)雜事件的概率數(shù)據(jù)模型為目標(biāo)，建立一種新的關(guān)聯(lián)事件概率模型，并且提出了多維不確定概率模型空間的概念，從而使系統(tǒng)能對(duì)多個(gè)概率模型進(jìn)行統(tǒng)一建模，并把單維XML概率節(jié)點(diǎn)引申到多維空間，進(jìn)而定義了統(tǒng)一的空間查詢方式，從而優(yōu)化了復(fù)雜事件的概率數(shù)據(jù)建模和查詢方法。

2 關(guān)聯(lián)事件概率模型

2.1 兩種經(jīng)典概率模型

半結(jié)構(gòu)化數(shù)據(jù)模型的出現(xiàn)，解決了不確定數(shù)據(jù)在無(wú)嚴(yán)格模式結(jié)構(gòu)情況下的描述問(wèn)題。在管理概率半結(jié)構(gòu)化數(shù)據(jù)的方法基礎(chǔ)上，出現(xiàn)了直接以文檔樹(shù)形式描述的p-文檔模型[2]。如圖1所示，p-文檔模型以文檔樹(shù)的邊作為概率屬性的載體，各個(gè)節(jié)點(diǎn)的概率依附于上一級(jí)的概率，同時(shí)對(duì)于同層次節(jié)點(diǎn)之間，使用互斥或者獨(dú)立關(guān)系作為描述。節(jié)點(diǎn)和邊的數(shù)目決定了計(jì)算概率的工作量。

圖1 p-文檔模型結(jié)構(gòu)圖

在計(jì)算節(jié)點(diǎn)概率的時(shí)候，按照下式：

得到C節(jié)點(diǎn)的概率，同樣D節(jié)點(diǎn)的概率也可由公式（1）得到：

其中等式右邊的值可以從原XML文檔得到。所以計(jì)算某個(gè)元素e∈A，A為某個(gè)定義的子圖，只需要計(jì)算公式（2）：

其中n為從e節(jié)點(diǎn)到root節(jié)點(diǎn)r的所有路徑上的節(jié)點(diǎn)數(shù)目。

考慮了事件驅(qū)動(dòng)后的概率樹(shù)模型[6]在各節(jié)點(diǎn)附加一系列外部事件變量，由外部事件的發(fā)生與關(guān)聯(lián)決定節(jié)點(diǎn)的存在性。按照概率樹(shù)的定義，數(shù)據(jù)樹(shù)t是一個(gè)4元組t=(A，E，r，φ)，A是一個(gè)節(jié)點(diǎn)有限級(jí)，E?A2，是以rootr∈A為起點(diǎn)的數(shù)據(jù)樹(shù)。φ作為字符串組對(duì)應(yīng)的節(jié)點(diǎn)label標(biāo)示。假設(shè)t=(A，E，r，φ)，t′=(A′，E′，r′，φ′)。可以說(shuō)t和t′同構(gòu)。假設(shè)有W作為有限事件變量級(jí)，存在概率條件為w或者-w， w∈W 。對(duì)于概率樹(shù)的定義T為4元組(t，W，π，Y)，t=(A，E，r，φ)是數(shù)據(jù)樹(shù)，π以W 的某種概率分布，Y分配概率條件到節(jié)點(diǎn)A-{r}。圖2是一個(gè)具體的概率樹(shù)模型結(jié)構(gòu)圖，概率樹(shù)模型作為事件驅(qū)動(dòng)的模型，它并不在各節(jié)點(diǎn)邊上附加概率值來(lái)描述不確定性，而是由事件的發(fā)生與否決定節(jié)點(diǎn)的存在性。

圖2 概率樹(shù)模型結(jié)構(gòu)圖

圖2共有2個(gè)外部事件w1和w2，其發(fā)生概率分別為0.7和0.8。節(jié)點(diǎn)B出現(xiàn)的前提條件是事件w1發(fā)生且事件w2不發(fā)生；節(jié)點(diǎn)E存在的前提條件是事件w2發(fā)生。由于節(jié)點(diǎn)B與E的存在條件互斥，不存在同時(shí)包含節(jié)點(diǎn)B、E的子圖。包含且僅包含 A、C、D 3個(gè)節(jié)點(diǎn)的子圖的概率為：(1-0.8)×(1-0.7)-0.06，前提是w1、w2均不發(fā)生。

2.2 關(guān)聯(lián)事件有向圖概率模型定義

本文定義了一種概率有向圖模型，同時(shí)兼顧了前面描述的兩種經(jīng)典模型的優(yōu)點(diǎn)，并且擴(kuò)展了表述概率事件的復(fù)雜度，從而提高了模型的表述能力。

定義1數(shù)據(jù)有向圖 f是一個(gè)4元組，表述為 f=(S，E，p，φ)，其中S是節(jié)點(diǎn)的有限集合，E?S2，作為節(jié)點(diǎn)有向圖，概率關(guān)系矩陣 p定義了所有節(jié)點(diǎn)的關(guān)系，φ標(biāo)示了有限節(jié)點(diǎn)集合的字符串。

對(duì)于概率矩陣 p的定義為 pij=(ei-＞ej)節(jié)點(diǎn)i指向節(jié)點(diǎn)j的關(guān)聯(lián)概率，如果有A、B、C、D四個(gè)節(jié)點(diǎn)，形成的概率關(guān)系矩陣如公式（3）所示：

如果其中存在不相關(guān)的節(jié)點(diǎn)對(duì)，使用0表示。

對(duì)于某個(gè)節(jié)點(diǎn)B的概率Prob(B)，可以看作與之關(guān)聯(lián)的有向標(biāo)識(shí)的集。

圖2的概率樹(shù)模型變換為如下關(guān)聯(lián)事件圖3，對(duì)于 A出現(xiàn)，B必然出現(xiàn)的節(jié)點(diǎn)關(guān)系，使用單向箭頭表示，把依存概率作為邊，對(duì)于C出現(xiàn)，B不出現(xiàn)，概率為 -1，箭頭的方向表示作用關(guān)系。不同節(jié)點(diǎn)通過(guò)外部事件關(guān)聯(lián)，如圖3所示。

計(jì)算節(jié)點(diǎn)B的概率，先確定有向標(biāo)示的起點(diǎn)概率和標(biāo)示概率的極性，然后計(jì)算。圖4中B節(jié)點(diǎn)的概率為：

其中前面的Prob(A)，(1-Prob(C))，Prob(D)組成關(guān)聯(lián)概率，Prob(Wb)是內(nèi)在節(jié)點(diǎn)事務(wù)驅(qū)動(dòng)概率。

圖3 關(guān)聯(lián)事件概率模型結(jié)構(gòu)圖

圖4 B節(jié)點(diǎn)的關(guān)聯(lián)事概率拓?fù)?/p>

所以，任何一個(gè)節(jié)點(diǎn)概率e可以由公式（4）計(jì)算為：

對(duì)于關(guān)聯(lián)事件有向圖概率模型，很明顯每個(gè)節(jié)點(diǎn)的關(guān)系從樹(shù)變成網(wǎng)，同時(shí)保留了外部驅(qū)動(dòng)事件的影響。所以表述能力得到了提升，可以對(duì)更加復(fù)雜的概率數(shù)據(jù)進(jìn)行描述。

3 多維XML概率模型空間定義與查詢

關(guān)聯(lián)事件的概率模型和其他概率模型均可以在多維平面展開(kāi)，形成對(duì)于多維事件驅(qū)動(dòng)的概率表述，從而極大地?cái)U(kuò)展了其復(fù)雜性。

定義2對(duì)任何一個(gè)節(jié)點(diǎn)的概率，有一個(gè)n維概率坐標(biāo)表示，(P1，P2，…，Pn)，其中對(duì)于每一個(gè)坐標(biāo)，表示在某一個(gè)該節(jié)點(diǎn)所在概率空間的概率坐標(biāo)。對(duì)于該節(jié)點(diǎn)的概率，可以看作是在n維概率空間的某個(gè)點(diǎn)。

如果O(i)表示某個(gè)節(jié)點(diǎn)的概率坐標(biāo)的維度。如果i點(diǎn)有4個(gè)坐標(biāo)點(diǎn)，表示坐標(biāo)維度為4，如果4維坐標(biāo)的其中一個(gè)坐標(biāo)值為1，O(i)=O(i-1)，出現(xiàn)降維事件。

對(duì)于每個(gè)概率空間，存在某一個(gè)概率模型，表示該節(jié)點(diǎn)的位置。假設(shè)Mi是第i維空間概率坐標(biāo)形成的模型，Mj是第 j維空間概率坐標(biāo)形成的模型，如果Mi∩Mj=0，則稱為 Mi正交于Mj，其中∩操作表示兩個(gè)模型的節(jié)點(diǎn)之間關(guān)系∩，或者說(shuō)兩個(gè)模型非聯(lián)通。如果 Mi非正交于Mj，則稱為節(jié)點(diǎn)i所處的概率空間存在聯(lián)通性。需要通過(guò)聯(lián)通關(guān)系裁剪概率空間，保證正交，或者降低坐標(biāo)維度。

關(guān)聯(lián)事件模型M1和p文檔模型M2對(duì)每個(gè)點(diǎn)的概率模型疊加，如圖5所示。

圖5 多維概率模型疊加結(jié)構(gòu)圖

對(duì)于每一個(gè)節(jié)點(diǎn)的概率坐標(biāo)Pnode=(Pp，Pw)，其中Pp是由P-文檔模型定義的，Pw由概率樹(shù)事件定義。

在引入多維概率模型以后，進(jìn)而描述多維空間的操作運(yùn)算和關(guān)于節(jié)點(diǎn)的概率坐標(biāo)的幾個(gè)延伸，如下定義。

定義3對(duì)某個(gè)節(jié)點(diǎn)的概率坐標(biāo)，形成坐標(biāo)向量Pi，定義坐標(biāo)概率權(quán)重向量：

K'i，Pi作為權(quán)重因子以后的節(jié)點(diǎn)概率坐標(biāo)。對(duì)于正交模型空間的節(jié)點(diǎn) X每個(gè)坐標(biāo) pi，如果存在一個(gè)時(shí)間函數(shù)，在t時(shí)刻，發(fā)生關(guān)系，假設(shè)存在函數(shù) F(t，pi)，在t時(shí)刻，坐標(biāo) pi可以映射到 pj上，則稱為概率模型i和 j在節(jié)點(diǎn)X上存在時(shí)間滑動(dòng)映射關(guān)系，pj=F(t，pi)，其中F為時(shí)間滑動(dòng)概率函數(shù)，對(duì)于實(shí)際世界，不同的概率模型在某個(gè)節(jié)點(diǎn)是存在某種關(guān)聯(lián)的，?t，pj=F(t，pi)，則概率模型空間i和 j是可以一一映射的，同時(shí)O(i)=O(i-1)，存在降維事件。

下面對(duì)于關(guān)聯(lián)事件概率模型與概率模型空間進(jìn)行查詢研究。首先定義查詢類型。對(duì)于關(guān)聯(lián)事件概率模型，作為網(wǎng)狀關(guān)聯(lián)模型，需要給出并且評(píng)估有效的查詢方法。為了定義一種查詢方式，首先定義子關(guān)聯(lián)圖的概念：

定義4有 f=(S，E，p，φ)和 f′=(S′，E′，p′，φ′)兩個(gè)關(guān)聯(lián)事件圖，如果有：

對(duì)于一個(gè)查詢節(jié)點(diǎn)e的操作，定義為Q(e|f)，對(duì)于Q(e′|f′)= Q(e|f)∩Sub(f′)，定義Prob(e|f)=Prob(e|fmin)，其中fmin=sub(f)，fmin是元素最少的sub(f)，則稱 fmin是e的最簡(jiǎn)子關(guān)聯(lián)圖。

對(duì)于具有多維概率坐標(biāo)的節(jié)點(diǎn)，首先獲得正交概率空間，得到Omin。

對(duì)每個(gè)空間實(shí)施Qi(e)函數(shù)，獲得全部維度的查詢信息。

對(duì)概率世界的查詢可以表示為：

其中S={(ti，pi)}，作為PW集。

在多維概率模型以及概率模型的引申定位，從空間上統(tǒng)一了多種概率模型。對(duì)于節(jié)點(diǎn)的多模型多概率定義創(chuàng)造性地給出了統(tǒng)一建議，使得表述和兼容性在多維度下統(tǒng)一，也就是在兼容性和統(tǒng)一性上有很大改善和提升。

多維概率模型對(duì)于查詢的復(fù)雜度并不能降低，而是在于表述能力的提升。需要指出的是在降維操作之后的查詢復(fù)雜度才是最終的可度量查詢復(fù)雜度。對(duì)于復(fù)雜度本身可以同樣適用矩陣和向量表示。

4 多維概率模型實(shí)例分析

以某大學(xué)人事數(shù)據(jù)為例。圖6列出了一個(gè)2維概率模型的實(shí)例?？梢钥吹?，在維1（黑影部分），通過(guò)類似P-文檔模型結(jié)構(gòu)表示了某大學(xué)人事數(shù)據(jù)概率模型各個(gè)節(jié)點(diǎn)的關(guān)系。而對(duì)于維2（灰色部分），是同樣節(jié)點(diǎn)的外部概率事件模型。對(duì)于每個(gè)節(jié)點(diǎn)，存在二維概率值，例如對(duì)于salary value的劃分概率，不只是由工資級(jí)別決定的，同時(shí)與職位存在外部事件關(guān)聯(lián)。

圖6 多維概率模型實(shí)例

在假設(shè)的概率關(guān)系中得到一個(gè)節(jié)點(diǎn)二維矩陣如下：

同時(shí)該二維數(shù)存在W1節(jié)點(diǎn)子集存在維度降低，為1維概率節(jié)點(diǎn)集：

存在W0節(jié)點(diǎn)子集存在更大的維度減低，為0維概率節(jié)點(diǎn)集：

剩余的子集為2維節(jié)點(diǎn)子集W2，由此可以將W形成3類矩陣進(jìn)行計(jì)算，3類矩陣的計(jì)算復(fù)雜度一次增加。

可見(jiàn)同一節(jié)點(diǎn)由于存在多重空間表示，表述性必然增加。但是降維以后的操作和查詢復(fù)雜度是由節(jié)點(diǎn)本身的關(guān)聯(lián)復(fù)雜度導(dǎo)致的。隨后對(duì)二維空間的每個(gè)維度概率節(jié)點(diǎn)，可以實(shí)施前文定義的多維查詢函數(shù)，獲得全部維度的查詢信息。多維查詢函數(shù)是在之前多維模型的同步維度擴(kuò)展，并不作為重點(diǎn)在本文描述。

在本實(shí)例中可見(jiàn)二維查詢函數(shù)存在一個(gè)可優(yōu)化之處。對(duì)于每個(gè)模型通常是既定的，并沒(méi)有考慮正交性，也很難進(jìn)行正交分解，所以在非正交化概率模型間的查詢效率簡(jiǎn)化是值得進(jìn)一步研究的。

5 結(jié)束語(yǔ)

隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的蓬勃發(fā)展，海量的數(shù)據(jù)展現(xiàn)在人們面前，大量的不確定數(shù)據(jù)需要有高效的管理，并且要能為用戶提供方便、有效、真實(shí)的查詢，概率則恰是表示不確定信息的一種常用方式，因此對(duì)概率數(shù)據(jù)模型進(jìn)行研究有著很重要的應(yīng)用價(jià)值。

本文描述了一種XML關(guān)聯(lián)事件概率數(shù)據(jù)模型，能夠描述較為復(fù)雜的概率數(shù)據(jù)模型并提出概率模型空間的概念和查詢，使系統(tǒng)能夠使用多個(gè)概率模型進(jìn)行建模，把每個(gè)XML概率節(jié)點(diǎn)引申到多維空間，進(jìn)而定義了統(tǒng)一的查詢方式，為復(fù)雜概率數(shù)據(jù)建模和查詢優(yōu)化提供了一種新穎的理論方法。

后續(xù)多維概率模型的維度正交化研究以及在非正交性的既定概率模型下的最大查詢簡(jiǎn)化方法研究，是下一步的研究工作。

[1]Dey D，Sarkala S.A probabilistic relational model and algebra[J].ACM Transactions on Database Systems，1996，21（3）：339-369.

[2]Nierman A，Jagadish H V.ProTDB：probabilistic data in XML[C]// Proceedings of 28th International Conference on Very Large Data Bases，2002：646-657.

[3]Kimelfeld B，Sagiv Y.Matching twigs in probabilistic XML[C]// VLDB’07，Vienna，Austria，2007：27-38.

[4]Cohen S，Kimelfeld B，Sagiv Y.Incorporating constraints in probabilistic XML[C]//Proceedings of the 27th ACM SIGMODSIGACT-SIGART Symposium on PrinciplesofDatabase Systems，Vancouver，2008：109-118.

[5]Souihli A，Senellart P.Efficient query evaluation over probabilistic XML with long-distance dependencies[C]//Proceedings of the 2011 Joint EDBT/ICDT Ph.D.Workshop，Sweden，2011：32-37.

[6]Abiteboul S，Senellart P.Querying and updating probabilistic information in XML[C]//10th InternationalConference on Extending DatabaseTechnology，Munich，Germany，2006：1059-1068.

[7]Senellart P，Abiteboul S.On the complexity of managing probabilistic XML data[C]//Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems，Beijing，2007：283-292.

[8]Hung E，Getoor L，Subrahmanian V S.PXML：a probabilistic semistructured data modeland algebra[C]//Proceedingsof the 19th International Conference on Data Engineering（ICDE），2003：467-478.

[9]Hung E，Getoor L，Subrahmanian V S.Probabilistic interval XML[J].ACM Transactions on Computational Logic，2007，8（4）.

[10]van Keulen M，de Keijzer A，Alink W.A probabilistic XML approach to data integration[C]//Proceedings ofthe 2lst IEEE International Conference on Data Engineering，Tokyo，2005：459-470.

[11]Kimelfeld B，Kosharovsky Y，Sagiv Y.Query efficiency in probabilistic XML models[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data，Vancouver，2008：701-714.

WANG Yan1，2,LE Jiajin3,JIANG Jiulei1,ZHANG Yun2

1.Glorious Sun School of Business and Management,Donghua University,Shanghai 200061,China
2.College of Information Technology,Shanghai Ocean University,Shanghai 201306,China
3.School of Computer Science and Technology,Donghua University,Shanghai 201620,China

Uncertainty of mass data storage and recording and the extensive application of XML in the extension make that the XML association event probability data model has become a hot topic.Based on the existent probability models,this article describes the complex event probabilistic data model,and puts forward the conception of multidimensional uncertainty probability model space.Furthermore,the paper unifies modeling of multiple probability models,and extends the single dimension XML probability node to multidimensional space,and then defines the uniform spatial query,provides a new theory method of modeling and query optimization of complex probabilistic data model.

Extensive Markup Language（XML）;uncertainty;multi-dimensional space;probability model;related events

不確定海量數(shù)據(jù)存儲(chǔ)與記錄的廣泛應(yīng)用及其在XML上的擴(kuò)展，使XML的關(guān)聯(lián)事件概率的數(shù)據(jù)模型研究成為研究熱點(diǎn)，以描述復(fù)雜事件的概率數(shù)據(jù)模型為目標(biāo)，在當(dāng)前已有概率模型的基礎(chǔ)上，提出了多維不確定概率模型空間的概念，基于多個(gè)概率模型進(jìn)行統(tǒng)一建模，并把單維XML概率節(jié)點(diǎn)引申到多維空間，進(jìn)而定義了統(tǒng)一的空間查詢方式，為復(fù)雜概率數(shù)據(jù)建模和查詢優(yōu)化提供了一種新穎的理論方法。

可擴(kuò)展標(biāo)示語(yǔ)言（XML）；不確定性；多維空間；概率模型；關(guān)聯(lián)事件

A

TP309.2

10.3778/j.issn.1002-8331.1203-0174

WANG Yan,LE Jiajin,JIANG Jiulei,et al.Research on multi-dimensional uncertainty data model based on XML.Computer Engineering and Applications,2013,49（23）：91-94.

上海市科學(xué)技術(shù)委員會(huì)專項(xiàng)基金資助項(xiàng)目（No.11510501300）。

王艷（1978—），女，博士研究生，講師，主要研究方向：信息管理與信息系統(tǒng)、數(shù)據(jù)挖掘等。E-mail：yanwang@shou.edu.cn

2012-03-07

2012-05-21

1002-8331（2013）23-0091-04

CNKI出版日期：2012-07-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120716.1501.040.html