Computer Science ›› 2016, Vol. 43 ›› Issue (11): 284-290.doi: 10.11896/j.issn.1002-137X.2016.11.055

Previous Articles     Next Articles

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: 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

[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 25th 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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!