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

Pattern Matching Algorithms for Graph Structured Fuzzy XML Documents

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

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,agroup 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 matching 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.