图结构模糊XML文档上的模式匹配算法

doi:10.11896/j.issn.1002-137X.2016.11.055

计算机科学 ›› 2016, Vol. 43 ›› Issue (11): 284-290.doi: 10.11896/j.issn.1002-137X.2016.11.055

图结构模糊XML文档上的模式匹配算法

缪丰羽,王宏志

宁德师范学院计算机系宁德352100,哈尔滨工业大学计算机学院哈尔滨150001

出版日期:2018-12-01 发布日期:2018-12-01
基金资助:
本文受国家973计划(2012CB316200),国家自然科学基金项目(61472099,2),国家科技支撑计划项目(2015BAH10F00),宁德师范学院2014年校级青年专项基金(2014Q51)资助

Pattern Matching Algorithms for Graph Structured Fuzzy XML Documents

MIAO Feng-yu and WANG Hong-zhi

Online:2018-12-01 Published:2018-12-01

摘要/Abstract

摘要： 模糊XML文档是指包含不确定信息的XML文档。在模糊XML文档查询方面,现有的研究成果较少,并且都是基于树型结构的XML文档进行的。针对图结构下模糊XML文档的特征,设计了一组高效的图结构模糊XML文档上的模式匹配算法。该算法基于一种适合于图结构文档的索引方式,采用自底向上的结点匹配顺序,大大减少了结点的重复判断操作,也不需要进行局部匹配结果的归并以及针对PC关系设计额外的过滤函数。理论分析以及实验结果证明,提出的模式匹配算法不仅在小枝查询性能上优于现有的相关算法,而且能够较好地实现DAG模式匹配查询。

关键词: 图结构,模糊数据,XML,模式匹配,DAG

Abstract: Fuzzy XML documents are XML documents which contain uncertain information.There are few research achievements of fuzzy XML documents,and all of them are based on tree-structure.According to the characteristics of the graph structured fuzzy XML documents,a group of efficient algorithms were proposed in this paper.These algorithms are based on an indexing scheme which is fit for graph-structured documents,and use the bottom-up search for nodes matchings to reduce the repeat judgements greatly.Such approaches neither need to merge the portions of ma-tching results nor need to design the filter function for PC relations.The theoretical analysis and experimental results show that,the pattern matching algorithms presented in this paper outperform the relevant algorithms in twig query performance,and accomplish the query of DAG pattern matching effectively.

Key words: Graph structure,Fuzzy data,XML,Pattern matching,DAG

缪丰羽,王宏志. 图结构模糊XML文档上的模式匹配算法[J]. 计算机科学, 2016, 43(11): 284-290. https://doi.org/10.11896/j.issn.1002-137X.2016.11.055

MIAO Feng-yu and WANG Hong-zhi. Pattern Matching Algorithms for Graph Structured Fuzzy XML Documents[J]. Computer Science, 2016, 43(11): 284-290. https://doi.org/10.11896/j.issn.1002-137X.2016.11.055

参考文献

[1] Gaurav A,Alhajj R.Incorporating Fuzziness in XML and Mapping Fuzzy Relational Data into Fuzzy XML[C]∥Proceedings of the 2006 ACM Symposium on Applied Computing.Dijon,France,2006:456-460
[2] Li Ya-wen,Wang Guo-ren,Xin Juan-chang.Holistically TwigMatching in Probabilistic XML[C]∥Proceedings of the 25^th International Conference on Data Engineering.Shanghai:IEEE,2009:1649-1656
[3] Liu Si-qi,Wang Guo-ren.Boosting Twig Joins in ProbabilisticXML[C]∥Proceedings of the 22nd International Conference on Database and Expert Systems Applications.France:Springer Verlag,2011:51-58
[4] Ma Zong-ming,Yan Li.Fuzzy XML Data Modeling with TheUML and Relational Data Models[J].Data & Knowledge Engineering,2007,63(3):972-996
[5] Liu Jian,Ma Zong-ming,Yan Li.Efficient Processing of TwigPattern Matching in Fuzzy XML[C]∥Proceedings of the 18th ACM Conference on Information and Knowledge Management.Hong Kong,China,2009:193-204
[6] Yan Li,Liu Jian.Conceptual Design Methodology for FuzzyXML Model[J].Computer Science,2011,8(12):156-161(in Chinese) 严丽,刘健.一种模糊XML模型的概念设计方法[J].计算机科学,2011,8(12):156-161
[7] Ma Zong-ming,Liu Jian,Yan Li.Matching Twigs in Fuzzy XML[J].Information Sciences,2011,181(1):184-200
[8] Liu Jian,Ma Zong-min,Qu Qiu-long.Querying Twigs in Fuzzy XML Documents[J].Chinese Journal of Computers,2014,9(37):1972-1985(in Chinese) 刘健,马宗民,璩秋龙.基于模糊XML的小枝查询处理[J].计算机学报,2014,9(37):1972-1985
[9] Liu Li-xin,Zhang Xiao-lin,Lv qin,et al.Matching Twig Patterns in Uncertain XML without Merging[J].Computer Science,2013,0(5):198-200(in Chinese) 刘立新,张晓琳,吕庆,等.一种非归并不确定XML小枝模式查询算法[J].计算机科学,2013,0(5):198-200
[10] Wang Hong-zhi,Wang Wei.Labeling Scheme and StructuralJoins for Graph-Structured XML Data[J].Lecture Notes in Computer Science,2005,3399:277-289
[11] Zhang C,Naughton J,DeWitt D,et al.On Supporting Containment Queries in Relational Database Management Systems[C]∥Proceedings of the 2001 ACM SIGMOD International Conferen-ce on Management of Data.Santa Barbara,California,United States:ACM Press,2001:425-436
[12] Fu Li-zhen,Meng Xiao-feng.Reachability Indexing for Large-Scale Graphs:Studies and Forecasts[J].Journal of Computer Research and Development,2015,2(1):116-129(in Chinese) 富丽贞,孟小峰.大规模图数据可达性索引技术[J].计算机研究与发展,2015,2(1):116-129
[13] Chen Yang-jun,Chen Yi-bin.An Efficient Algorithm for An-swering Graph Reachability Queries[C]∥Proceedings of IEEE ICDE08.Piscataway,NJ:IEEE,2008:893-902
[14] Wang Hong-zhi,Li Jian-zhong,Luo Ji-zhou,et al.Hash-baseSubgraph Query Processing Method for Graph-structured XML Documents[J].Proceedings of the VLDB Endownment,2008,1(1):478-489
[15] Chen Li,Gupta A.Stack-based Algorithms for Pattern Matching on DAGs[C]∥Proceedings of the 31st International Conference on Very Large Data Bases (VLDB).Trondheim,Norway:VLDB Endownment,2005:493-504
[16] Tril S,Leser U.Fast and Practical Indexing and Querying ofVery Large Graphs[C]∥Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data.Beijing,China:ACM Press,2007:845-856
[17] Jin Ruo-ming,Ruan Ning,Xiang Yang,et al.Path-tree:An Efficient Reachability Indexing Scheme for Large Directed Graphs[J].ACM Trans on Database System,2011,6(1):73-84
[18] Cai Jing,Poon C.Path-hop:Efficiently Indexing Large Graphs for Reachability Queries[C]∥Proc of ACM CIKM’10.New York:ACM,2010:119-128
[19] Kimelfeld B,Kosharovshy Y,Sagiv Y.Query efficiency in proba-bilistic XML models[C]∥Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data.Vancouver,Canada,2008:701-714

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

图结构模糊XML文档上的模式匹配算法

Pattern Matching Algorithms for Graph Structured Fuzzy XML Documents

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0