概率XM L數據模型的綜述

殷麗鳳，金 花，田 宏

（大連交通大學 軟件學院，遼寧 大連 116028）

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

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

1 概率XM L數據

XML數據通常可以用文檔樹來描述，概率XML數據是把概率信息加入到文檔樹中，稱為概率XML文檔樹。在概率XML文檔樹中，包含兩種類型的節點，一種為普通節點，描述實際的數據；一種為分布節點，描述概率數據。為了描述不同離散類型和連續類型的概率分布，分布節點分為以下6種類型。

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

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

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

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

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

6）連續概率分布節點cont[17]，cont節點描述了此節點服從的連續概率分布，如二項分布，泊松分布，高斯分布，正態分布等。

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

2 概率XM L數據模型

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

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

在概率XML數據模型PrXML{cie}[13-14]中，它并不在各個節點或邊上附加概率值來描述不確定性，而是在各個節點上附加一系列事件變量，節點的存在性由外部事件是否發生來決定。圖2描述了一個PrXML{cie}的例子，共有2個外部事件w1和w2，其發生的概率分別為0.8和0.7。節點C出現的前提條件是w2發生，而節點D出現的前提條件是w1發生而w2不發生。節點C和D的存在條件為互斥，從而不存在同時包含C和D的子樹。包含A、B、D 3個節點的子樹的概率為：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數據模型PrXML{exp}[15-16]中，每個節點可以選擇孩子節點的任意組合。文中對文獻[15]、[16]中的圖約束為樹，把區間概率變為點概率，給出圖3描述概率XML數據模型PrXML{exp}的一個例子。此圖共有6個節點，節點A和B1屬于組合類型節點，節點A可以選擇孩子節點B1、B2、B3的組合中{（B1，B2）（B2，B3）、（B1，B3）、（B1，B2，B3）}中的任意一個組合，節點 B1可以選擇孩子節點 C1、C2的組合中{（C1）、（C2）、（C1，C2）}中的任意一個組合。若節點A選擇孩子節點組合（B1，B3）而節點B1孩子節點組合（C2）構成的子樹概率為0.1×0.6=0.06。

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

3 概率XM L數據模型的轉換

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

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

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

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

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

圖4 PrXML模型轉換的有效圖Fig.4 PrXML effective model transformation diagram

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

圖5 擴展的PrXML模型轉換有效圖Fig.5 Extended PrXML effective model transformation diagram

4 結束語

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

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

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

在概率XML數據庫管理領域仍有很多工作有待完成。

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

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

3）概率 XML數據的約束[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不確定數據管理技術[J].計算機科學與探索，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.