概率XM L數(shù)據(jù)模型的綜述

殷麗鳳，金 花，田 宏

（大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116028）

在許多應(yīng)用中，如傳感器網(wǎng)絡(luò)[1]、無線射頻識別技術(shù)[2]、數(shù)據(jù)集成[3]、基于位置的服務(wù)[4]等領(lǐng)域都涉及不確定數(shù)據(jù)。不確定數(shù)據(jù)普遍存在，傳統(tǒng)的數(shù)據(jù)管理技術(shù)無法有效管理不確定性數(shù)據(jù)，不確定數(shù)據(jù)的管理技術(shù)成為新的研究領(lǐng)域。針對不確定數(shù)據(jù)的研究工作已有幾十年的歷史，自二十世紀(jì)八十年代末開始，針對概率數(shù)據(jù)庫的研究工作從未間斷，研究者把概率信息引入關(guān)系數(shù)據(jù)模型中（稱為概率關(guān)系數(shù)據(jù)庫），對其概率關(guān)系數(shù)據(jù)模型、概率關(guān)系代數(shù)、查詢技術(shù)、查詢優(yōu)化、集成技術(shù)等領(lǐng)域進行了研究[5-10]，如今該類數(shù)據(jù)庫的管理技術(shù)取得了很大進展。

隨著網(wǎng)絡(luò)應(yīng)用的快速發(fā)展，可擴展標(biāo)識語言XML（eXtensible Markup Language）已成為Internet上信息表示和數(shù)據(jù)交換的標(biāo)準(zhǔn)，在網(wǎng)絡(luò)服務(wù)、電子商務(wù)、電子數(shù)據(jù)交換、科學(xué)數(shù)據(jù)表示、數(shù)據(jù)建模與分析、智能體和搜索引擎等領(lǐng)域得到了廣泛的應(yīng)用，XML技術(shù)也日益受到更廣泛的關(guān)注，XML數(shù)據(jù)庫的管理技術(shù)也不斷得到成熟和完善。由于不確定數(shù)據(jù)的普遍存在性，通常不確定信息以概率信息的形式在XML中表示，因此，研究表示和處理概率XML數(shù)據(jù)成為一個新的研究領(lǐng)域。XML的半結(jié)構(gòu)化、自描述性好及可擴展性高等優(yōu)點使其在概率數(shù)據(jù)表示上比概率關(guān)系模型占優(yōu)勢。因此，近些年概率XML數(shù)據(jù)管理技術(shù)成為研究熱點。文中綜述了概率XML數(shù)據(jù)、概率XML數(shù)據(jù)模型以及不同模型之間的轉(zhuǎn)換關(guān)系等方面的工作，討論目前存在的主要問題和進一步的研究方向。

1 概率XM L數(shù)據(jù)

XML數(shù)據(jù)通?？梢杂梦臋n樹來描述，概率XML數(shù)據(jù)是把概率信息加入到文檔樹中，稱為概率XML文檔樹。在概率XML文檔樹中，包含兩種類型的節(jié)點，一種為普通節(jié)點，描述實際的數(shù)據(jù)；一種為分布節(jié)點，描述概率數(shù)據(jù)。為了描述不同離散類型和連續(xù)類型的概率分布，分布節(jié)點分為以下6種類型。

1）獨立類型節(jié)點ind[11-12]，ind節(jié)點的孩子節(jié)點在概率XML文檔樹中的出現(xiàn)是獨立的，不受其他節(jié)點影響。若ind節(jié)點v選擇孩子w的概率為p（w），則v選擇孩子的子集C的概率為，表示v的孩子不在C中的節(jié)點集合。

2）互斥類型節(jié)點mux[11-12]，mux節(jié)點的孩子節(jié)點只能出現(xiàn)一個，或者全不出現(xiàn)。若mux節(jié)點v的孩子w1，…，wn的概率分別為 p（w1），…，p（wn），滿足（wi）≤1。 節(jié)點 v 的孩子全不出現(xiàn)的概率為1-（wi）。

3）事件驅(qū)動類型節(jié)點cie[13-14]，cie節(jié)點的存在是由獨立的外部事件變量e1，…，em決定的，外部事件變量e1，…，em的發(fā)生與否決定cie節(jié)點的存在性。

4）組合類型節(jié)點exp[15-16]，exp節(jié)點有多個孩子節(jié)點，可以選擇不同的孩子節(jié)點組成exp的孩子節(jié)點的集合，若exp的孩子節(jié)點的不同子集 c1，c2，…，cn的概率分別為 p（c1），p（c2），…，p（cn），要求

5）確定類型節(jié)點det，det節(jié)點的孩子節(jié)點必須全部出現(xiàn)。它是上面4種類型節(jié)點的特例。

6）連續(xù)概率分布節(jié)點cont[17]，cont節(jié)點描述了此節(jié)點服從的連續(xù)概率分布，如二項分布，泊松分布，高斯分布，正態(tài)分布等。

以上前5種類型節(jié)點描述了離散類型的不同概率分布，第6種類型節(jié)點描述了連續(xù)概率分布。根據(jù)解決問題的實際需要，研究者采用這6種類型節(jié)點進行組合，提出了不同的概率XML數(shù)據(jù)模型。

2 概率XM L數(shù)據(jù)模型

為了解決不同問題的實際需要，研究者提出包含不同類型分布節(jié)點的概率 XML 數(shù)據(jù)模型，我們用 PrXML{type1，type2，…}表示此通用模型，type1，type2分別表示上面六種分布節(jié)點類型中的任一種類型。例如PrXML{ind，mux}表示只包含獨立節(jié)點和分布節(jié)點的概率XML數(shù)據(jù)模型。

在概率XML數(shù)據(jù)模型PrXML{ind，mux}[11-12]中，各節(jié)點的概率依賴于其父親節(jié)點的概率，節(jié)點之間的關(guān)系可以是互斥關(guān)系（mux）或相互獨立（ind）關(guān)系。圖1描述了該模型的一個例子。有5個普通節(jié)點，2個分布節(jié)點，節(jié)點B、C之間相互獨立，概率值分別為0.7和0.8，節(jié)點D、E之間相互互斥，概率值分別為 0.6 和 0.3。 此時僅包含 A、C、D 的子樹概率為（1-0.7）×0.8×0.3=0.072；任意子樹均不能同時包含D和E兩個節(jié)點。

在概率XML數(shù)據(jù)模型PrXML{cie}[13-14]中，它并不在各個節(jié)點或邊上附加概率值來描述不確定性，而是在各個節(jié)點上附加一系列事件變量，節(jié)點的存在性由外部事件是否發(fā)生來決定。圖2描述了一個PrXML{cie}的例子，共有2個外部事件w1和w2，其發(fā)生的概率分別為0.8和0.7。節(jié)點C出現(xiàn)的前提條件是w2發(fā)生，而節(jié)點D出現(xiàn)的前提條件是w1發(fā)生而w2不發(fā)生。節(jié)點C和D的存在條件為互斥，從而不存在同時包含C和D的子樹。包含A、B、D 3個節(jié)點的子樹的概率為：0.8×（1-0.7）=0.24。 可以看出 PrXML{cie}的表達能力比 PrXML{ind，mux}強。

圖1 PrXML{ind， mux}模型Fig.1 Model of PrXML{ind，mux}

圖2 PrXML{cie}模型Fig.2 Model of PrXML{cie}

圖3 PrXML{exp}模型Fig.3 Model of PrXML{exp}

在概率XML數(shù)據(jù)模型PrXML{exp}[15-16]中，每個節(jié)點可以選擇孩子節(jié)點的任意組合。文中對文獻[15]、[16]中的圖約束為樹，把區(qū)間概率變?yōu)辄c概率，給出圖3描述概率XML數(shù)據(jù)模型PrXML{exp}的一個例子。此圖共有6個節(jié)點，節(jié)點A和B1屬于組合類型節(jié)點，節(jié)點A可以選擇孩子節(jié)點B1、B2、B3的組合中{（B1，B2）（B2，B3）、（B1，B3）、（B1，B2，B3）}中的任意一個組合，節(jié)點 B1可以選擇孩子節(jié)點 C1、C2的組合中{（C1）、（C2）、（C1，C2）}中的任意一個組合。若節(jié)點A選擇孩子節(jié)點組合（B1，B3）而節(jié)點B1孩子節(jié)點組合（C2）構(gòu)成的子樹概率為0.1×0.6=0.06。

B Kimelfeld等人[18]提出了包含cie、exp節(jié)點的概率XML數(shù)據(jù)模型 PrXML{cie，exp}。 E Kharlamov 和 S Abiteboul等人[17]對前面介紹的概率XML數(shù)據(jù)模型進行了擴展，允許葉子節(jié)點為cont節(jié)點，表示連續(xù)概率分布，如二項分布，泊松分布，高斯分布，正態(tài)分布等。這樣此模型具有很強的通用性。

3 概率XM L數(shù)據(jù)模型的轉(zhuǎn)換

可能世界模型是不確定數(shù)據(jù)庫應(yīng)用的最廣泛的模型，上面介紹的概率XML數(shù)據(jù)模型PrXML{type1，type2，…}構(gòu)成了概率XML數(shù)據(jù)庫的可能世界[19]。在該模型中，通過下面兩個步驟可得到一個可能世界的實例，實例的概率值可以通過分布節(jié)點固有的特征計算得到。

1）隨機選擇每個分布節(jié)點的合法孩子節(jié)點，刪除沒有選擇的所有孩子節(jié)點及其后裔。

2）刪除所有的分布節(jié)點。如果普通節(jié)點v沒有父親節(jié)點，選擇離v最近、合適的普通祖先節(jié)點為新的父親節(jié)點。

通過反復(fù)使用上面兩個步驟可以得到可能世界的所有可能世界實例，且滿足所有可能世界實例的概率總和為1。一般情況下，可能世界實例的數(shù)量遠遠高于概率XML數(shù)據(jù)庫的規(guī)模，甚至是后者的指數(shù)倍，這也是概率XML數(shù)據(jù)庫管理技術(shù)所面臨的最大難點。

根據(jù)解決實際問題的需要，根據(jù)上面前五種不同類型分布節(jié)點的不同組合，可以提出不同的概率XML數(shù)據(jù)模型，Benny Kimelfeld等人[20]根據(jù)這些模型表達力研究了這些模型之間的相互轉(zhuǎn)換關(guān)系，如圖4所示。

圖4 PrXML模型轉(zhuǎn)換的有效圖Fig.4 PrXML effective model transformation diagram

從圖4可以看出，模型PrXML{ind}與PrXML{mux}之間不能相互轉(zhuǎn)換，模型PrXML{exp}與PrXML{cie}之間也不能相互轉(zhuǎn)換，但其它所有模型都可以轉(zhuǎn)換為 PrXML{exp，cie}，從而 PrXML{exp，cie}的表達力最強，而PrXML{ind}、PrXML{mux}的表達力最弱。針對前面介紹的六種分布節(jié)點類型，我們可以把cont類型節(jié)點加入到概率 XML 數(shù)據(jù)模型 PrXML{type1，type2，…}中，對概率 XML 數(shù)據(jù)模型之間的轉(zhuǎn)換關(guān)系進行擴展，如圖5所示，從而進一步增強表達能力。

圖5 擴展的PrXML模型轉(zhuǎn)換有效圖Fig.5 Extended PrXML effective model transformation diagram

4 結(jié)束語

人類認知存在的局限性、度量的誤差、數(shù)據(jù)的動態(tài)變化以及信息描述的差異等情況，往往會產(chǎn)生許多不確定的數(shù)據(jù)。不確定數(shù)據(jù)在諸如軍事、經(jīng)濟、物流、電信、金融等領(lǐng)域的具體應(yīng)用中也普遍存在。針對不確定數(shù)據(jù)管理技術(shù)的研究已有40年的歷史，概率關(guān)系數(shù)據(jù)庫管理技術(shù)取得了很大的進展。隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，XML成為Internet上信息表示和交換的標(biāo)準(zhǔn)。XML的半結(jié)構(gòu)化、自描述性好及可擴展性高等優(yōu)點，使其在概率數(shù)據(jù)表示上與概率關(guān)系模型相比較占優(yōu)勢。因此，近些年概率XML數(shù)據(jù)管理技術(shù)成為研究熱點。概率XML數(shù)據(jù)管理技術(shù)與確定性的XML數(shù)據(jù)管理技術(shù)截然不同，這使得前者面臨如下挑戰(zhàn)：

1）龐大的可能世界實例集合。與概率關(guān)系數(shù)據(jù)庫相同，概率XML數(shù)據(jù)管理所面臨的直接挑戰(zhàn)就是其相當(dāng)于XML數(shù)據(jù)庫規(guī)模呈指數(shù)倍的可能世界實例的數(shù)量。因此，在查詢時需要考慮刪除概率值太小的實例后查詢還是直接在所有可能世界實例上查詢之間進行權(quán)衡。

2）概率信息。概率信息在概率XML數(shù)據(jù)管理中具有多重角色。在查詢時，輸入的文檔有概率信息，描述文檔中有不確定信息；輸出的文檔有概率信息，描述查詢結(jié)果的發(fā)生概率；查詢定義可以有概率信息，用于約束查詢結(jié)果。因此，概率信息的出現(xiàn)極大地改變了確定XML數(shù)據(jù)的處理方式，迫切新技術(shù)進行處理。

在概率XML數(shù)據(jù)庫管理領(lǐng)域仍有很多工作有待完成。

1）許多確定性XML數(shù)據(jù)管理領(lǐng)域所遇到的問題在概率XML數(shù)據(jù)管理領(lǐng)域也非常重要，需要為之尋求相應(yīng)的解決方案。

2）由于概率信息的存在，概率XML數(shù)據(jù)管理領(lǐng)域存在一些特有的查詢問題，需要找出這些查詢并給出相應(yīng)的解決方案。

3）概率 XML數(shù)據(jù)的約束[20]、集成、挖掘也有待進一步研究。

[1]Deshpande A，Guestrin C，Madden S，et al.Model-driven data acquisition in sensor networks[C]//Proceedings of the 30th international conference on Very large data bases，2004:588-599.

[2]許嘉，于戈，谷峪，等.RFID不確定數(shù)據(jù)管理技術(shù)[J].計算機科學(xué)與探索，2009， 3（6）:561-576.XU Jia，YU Ge，Gu YU，et al.Uncertain data management technologies in RFID[J].Journal of Frontiers of Computer Science and Technology，2009，3（6）:561-576.

[3]Madhavan J，Cohen S，Xin D，et al.Web-scale data integration:you can afford to pay as you go[C]//Roceedings of the 3rd biennial conference on innovative data systems research，2007:342-350.

[4]LIU Ling.From data privacy to location privacy:models and algorithms （tutorial）[C]//Proceedings of the 33rd international conference on very large data bases，2007:1429-1430.

[5]Cavallo R，Pittarelli M.The theory of probabilistic databases[C]//Proceedings of the 13th International Conference on Very Large Data Bases，1987:71-81.

[6]Barbara D，Garcia-Molina H，Porter D.The management of probabilistic data[J].IEEE Transactions on Knowledge and Data Engineering，1992， 4（5）:487-502.

[7]Fuhr N，Rolleke T.A probabilistic relational algebra for the integration of information retrieval and database systems[J].ACM Transactions on Information Systems，1997，15（1）:32-66.

[8]Zimanyi E.Query evaluation in probabilistic databases[J].Theoretical Computer Science，1997，171（1-2）:179-219.

[9]Dalvi N，Suciu D.Management of probabilistic data foundations and challenges[C]//Proceedings of the 26th ACM SIGMODSIGACT-SIGART symposium on principles of database systems.2007:1-12.

[10]Pei J， Hua M， Tao Y F， Lin X M.Query answering techniques on uncertain and probabilistic data:tutorial summary[C]//Proceedings of 2008 ACM SIGMOD international conference on management of data.2008:1357-1364.

[11]Nierman A，Jagadish H V.ProTDB:Probabilistic data in XML[R].Hong Kong：In Proc of the 28th VLDB conference，2002.

[12]LI Te，SHAO Qi-hong，CHEN Yi.PEPX:A query-friendly probabilistic XML database[C]//Proceeding of the 15th ACM international conference on information and knowledge management.ACM Press，2006:848-849.

[13]Abiteboul S，Senellart P.Querying and updating probabilistic information in XML[C]//Proceedings of the 9th international conference on Extending database technology:Advances in database technology.2006:1059-1068.

[14]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，2007:283-292.

[15]Hung E，Getoor L，Subrahmanian V S.PXML:a probabilistic semistructured data model and algebra[C]//Proceedings of the 19th IEEE international conference on data engineering.bangalore，2003:467-478.

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

[17]Abiteboul S，Chan T-H H，Kharlamov E.Aggregate queries for discrete and continuous probabilistic XML[C]//Proceedings of the 13th international conference on database theory，2010:50-61.

[18]Kimelfeld B， Kosharovsky Y，Sagiv Y.Query evaluation over probabilistic XML[J].VLDB Journal， 2009，18（5）：164-170.

[19]CHANG L J，YU J X，QIN L.Query ranking in probabilistic XML data[C]//In Proc of the 12th EDBT Confer-ence，Saint-Petersburg，Russia，2009:156-167.

[20]Kimelfeld B， Kosharovsky Y，Sagiv Y.Query efficiency in probabilistic XML models[C]//In SIGMOD conference，2008:710-714.

[21]Cochen S，Kimelfeld B，Sagiv Y.Running tree automata on Probabilistic XML[C]//In proc.PODS，RI，2009:227-236.