一种非归并不确定XML小枝模式查询算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (5): 198-200.

一种非归并不确定XML小枝模式查询算法

刘立新,张晓琳,吕庆,张换香,褚艳华

内蒙古科技大学信息工程学院包头014010;内蒙古科技大学信息工程学院包头014010;内蒙古科技大学信息工程学院包头014010;内蒙古科技大学信息工程学院包头014010;内蒙古科技大学信息工程学院包头014010

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(61163015),内蒙古科技大学创新基金(2011NCL024,2010NC041)资助

Matching Twig Patterns in Uncertain XML without Merging

LIU Li-xin,ZHANG Xiao-lin,LV Qing,ZHANG Huan-xiang and CHU Yan-hua

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 针对目前不确定XML小枝模式查询需要存储大量中间结果和归并中间结果的情况,提出一种非归并不确定XML小枝模式查询算法ProTwigList。该算法查询之前通过Tag+Level流进行剪枝,以减少待处理节点的数目；并扩展了区间编码来对剪枝后剩余的普通节点进行编码,用一定规则对分布节点进行标识；查询时采用公共分布节点路径的方法处理分布结点,最后结合最低公共祖先节点的概率计算查询结果的概率值。理论分析和实验结果证明了ProTwigList算法的查询效率。

关键词: 不确定XML,P-文档,分布节点,区间编码,小枝模式

Abstract: In order to avoid storing large amounts of intermediate results and merging those intermediate results when matching twig patterns in uncertain XML,this paper proposed the algorithm ProTwigList．First,it uses Tag＋Level stream pruning to reduce the number of nodes to be processed．Second,it extends the range encoding to encode the remaining ordinary nodes,and adopts rules to mark distributed nodes．Third,it uses the path of common distributed node to deal with distributed nodes．Finally,it utilizes the probability of the lowest common ancestor node to calculate the probability of every result．The theoretical analysis and experimental results prove the efficiency of ProTwigList.

Key words: Uncertain XML,P-document,Distributed node,Rang encoding,Twig pattern

刘立新,张晓琳,吕庆,张换香,褚艳华. 一种非归并不确定XML小枝模式查询算法[J]. 计算机科学, 2013, 40(5): 198-200. https://doi.org/

LIU Li-xin,ZHANG Xiao-lin,LV Qing,ZHANG Huan-xiang and CHU Yan-hua. Matching Twig Patterns in Uncertain XML without Merging[J]. Computer Science, 2013, 40(5): 198-200. https://doi.org/

参考文献

[1] 周傲英,金澈清,王国仁,等.不确定性数据管理技术研究综述 [J].计算机学报,2009,32(1):1-16
[2] 李文凤,彭智勇,李德毅．不确定性Top-k查询处理[J].软件学报,2012,26(3):1-19
[3] Li Jian,Deshpande A.Ranking Continuous Probabilistic Datasets[C]∥Proceeding of the 36^th International Conference on Very Large Data Bases.Singapore:VLDB Endowment,2010:13-17
[4] Nierman A,Jagadish H V．ProTDB:Probabilistic data in xml[C]∥Proceeding of the 28th Very Large Data Bases．Hong Kong:VLDB Endowment,2002:29-41
[5] Kimelfeld B,Sagiv Y.Matching Twigs in Probabilistic XML[C]∥Proceeding of the 33^th International Conference on Very Large Data Bases.Vienna:VLDB Endowment,2007:23-28
[6] Li Ya-wen,Wang Guo-ren,Xin Juan-chang．Holistically TwigMatching in Probabilistic XML[C]∥Proceedings of the 25th International Conference on Data Engineering.Shanghai:IEEE,2009:1649-1656
[7] Liu Si-qi,Wang Guo-ren.Boosting Twig Joins in ProbabilisticXML[C]∥Proceeding of the 22ed International Conference on Database and Expert Systems Applications．France:Springer-Verlag,2011:51-58
[8] Ning Bo,Liu Cheng-fei,Yu J X,et al.Matching Top-k Answers of Twig Patterns in Probabilistic XML[C]∥Proceeding of the 15th International Conference on Database Systems for Advanced Applications．Tsukuba:Springer-Verlag,2010:125-139
[9] Nierman A,Jagadish H V．Probabilistic data in XML[C]∥Proceeding of the 28th international conference on Very Large Data Bases．Hong Kong:Springer-Verlag,2002:646-657
[10] Lu Jia-heng,Meng Xiao-feng,Ling T W．Indexing and querying XML using extended Dewey labeling scheme[J]．Data & Knowledge Engineering,2011,70(1):35-39

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed