殷麗鳳，金 花，田 宏

（大連交通大學(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)域進(jìn)行了研究[5-10]，如今該類數(shù)據(jù)庫的管理技術(shù)取得了很大進(jìn)展。

隨著網(wǎng)絡(luò)應(yīng)用的快速發(fā)展，可擴(kuò)展標(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)化、自描述性好及可擴(kuò)展性高等優(yōu)點(diǎn)使其在概率數(shù)據(jù)表示上比概率關(guān)系模型占優(yōu)勢。因此，近些年概率XML數(shù)據(jù)管理技術(shù)成為研究熱點(diǎn)。文中綜述了概率XML數(shù)據(jù)、概率XML數(shù)據(jù)模型以及不同模型之間的轉(zhuǎn)換關(guān)系等方面的工作，討論目前存在的主要問題和進(jìn)一步的研究方向。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)解決實(shí)際問題的需要，根據(jù)上面前五種不同類型分布節(jié)點(diǎn)的不同組合，可以提出不同的概率XML數(shù)據(jù)模型，Benny Kimelfeld等人[20]根據(jù)這些模型表達(dá)力研究了這些模型之間的相互轉(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}的表達(dá)力最強(qiáng)，而PrXML{ind}、PrXML{mux}的表達(dá)力最弱。針對前面介紹的六種分布節(jié)點(diǎn)類型，我們可以把cont類型節(jié)點(diǎn)加入到概率 XML 數(shù)據(jù)模型 PrXML{type1，type2，…}中，對概率 XML 數(shù)據(jù)模型之間的轉(zhuǎn)換關(guān)系進(jìn)行擴(kuò)展，如圖5所示，從而進(jìn)一步增強(qiáng)表達(dá)能力。

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

4 結(jié)束語

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

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

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

在概率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]、集成、挖掘也有待進(jìn)一步研究。

[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].計算機(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.