文献检索报告.doc

支持树模式查询的XQuery系统的研究一、 关键词：中文关键词：树模式，查询, XQuery, XML英文关键词：tree pattern, query, XQuery, XML二、 扩展后的检索词：扩展后的中文检索词：树模式，模式树，小枝查询，整体匹配，XQuery，XML扩展后的英文检索词：tree pattern, pattern tree, generalized tree patterns, twig，holistic match, fast matching, twig pattern, XQuery, XML三、 检索式（1）中文检索式：(模式树 OR 树模式) AND (XML OR XQuery)（2）英文检索式：(tree pattern) OR (pattern tree) OR (generalized tree pattern)AND (twig OR (holistic match*) OR (twig pattern) OR (fast match*)AND (XML OR XQuery)四、 所选择的信息源1、中文全文数据库：CNKI2、文摘数据库：EI3、英文全文数据库：SDOL4、专利数据库：中国国家知识产权局、DII五、 每个数据库或其他信息源的检索结果1、 使用CNKI检索检索描述：检索到57条记录，按照被引频次排序，如下图所示， 其中，比较重要的2篇文献是上图中序号为1的“OreintXA:一种有效的XQuery查询代数”和序号为5的“支持XML信息检索的索引技术”。2、 使用EI检索检索描述如下：共检索到79条记录，整个检索结果如下:通过阅读摘要，比较重要的3篇文献如下图所示（通过EI的View Selections功能删掉了其他无关的文献）：这三篇文献的篇名分别为“TwigList: Make twig pattern matching fast”、“Holistic twig joins: Optimal XML pattern matching”、“Put a tree pattern in your Algebra”。3、 使用SDOL检索检索描述如下：共检索到60篇文献，如下图所示：4、 使用专利数据库检索（1）使用中国国家知识产权局专利数据库以“xquery”作为关键词进行检索，可以得到5条记录，如下图所示：（2）使用DII检索以“xquery” 作为关键词进行检索，结果如下，得到88条记录。六、文献综述随着计算机网络技术的迅猛发展，互联网已经成为了高效地获取、发布信息的重要渠道。越来越多的应用通过网络进行信息的交换。信息交换就需要一种统一的数据格式，供交换双方更加便捷的使用信息。XML（Extensible Markup Language）就是这样一种已被广泛应用于信息共享的数据格式。自1998年由W3C（World Wide Web Consortium）提出后，XML凭借其可扩展性、自描述性等特性，已成为一种公认的跨平台交互数据的形式。XQuery是一种针对XML数据的查询语言，具有灵活而强大的查询功能，能够从XML数据中提取出所需要的片段，重新组织成XML文档结构。在XQuery语言相关的研究中，如何高效地实现XQuery语言，提高查询效率是研究的核心问题之一。为此，2001年，TAX（参见1）中提出了树模式的概念，虽然该树模式并未采用整体的树模式算法进行处理，但将XML查询请求抽象成树模式，为日后的树模式查询算法奠定了基础。XQuery查询请求具有树模式特征，针对这一特征，研究人员提出了多种XQuery实现算法，并取得了显著的成果。为了避免产生大量的中间结果，N.Bruno等人首次提出采用整体匹配的方法进行结构连接的算法：PathStack算法和TwigStack算法（参见2）。PathStack算法即路径模式查询算法，用来处理不包含分支的树模式查询。TwigStack算法将Twig查询分为两个阶段：在第一个阶段中，将树查询中的一些从根到叶的单个路径查询局部匹配结果被计算；在第二个阶段中，这些单个路径查询的局部匹配结果被归并成树模式查询的最终匹配。模式树存在一定的局限性，难以表示XQuery查询中的复杂谓词，嵌套层次等特性。基于上述树模式的局限性，文献3对常见的树模式进行了扩展，并加入了一些反映XQuery特性的信息，如嵌套层次、强弱绑定、分组返回等从而增强了树模式的表达式能力，提出了GTP这个概念，并给出了从XQuery向GTP转化的算法。为了解决过去树查询算法的问题，文献4提出一种新的层次栈编码（hierarchical-stack encoding scheme）结构，用来描述查询的部分结果，并提出采用此结构的Twig2Stack算法。该算法有效地解决了中间结果较多的问题，同时支持基于GTP的树模式查询。Lu Qin提出了TwigList算法（参见5）与Twig2Stack算法类似，TwigList算法同样通过构建算法将XML节点保存在特定的数据结构中，并通过相应的枚举算法得到结果。TwigList由于采用简单高效的线性表数据结构取代了复杂的层次栈结构，从而提高了算法的效率。Jiang Li和Junhu Wang在TwigList算法的基础上，结合标签流，提出了TwigFast算法6，进一步提高了树模式查询的效率。综上，从整体来看，上面所提到的几个算法之间的大体关系如下图所示。本研究的主要研究目的就是要创建一个XQuery查询系统，实现上述的这些算法。参考文献1 Xin Zhang, Elke A. Rundensteiner. XAT: XML Algebra for the Rainbow System. Computer Science Technical Report Series, Department of Computer Science, Worcester Polytechnic Institute, Worcester, MA, 20022 N. Bruno, N. Koudas and D. Srivastava. Holistic Twig Joins: Optimal XML Pattern Matching. Proceedings of 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, June 3-6, 2002. ACM Press, 2002: 310-3213 Z. Chen, H. V. Jagadish, L. V. S. Lakashmanan, et al. From Tree Patterns to Generalized Tree Patterns: On efficient Evaluation of XQuery. Proceedings of 29th International Conference on Very Large Data Bases. Berlin, Germany. September 9-12, 2003. Morgan Kaufmann.2003:237-2484 S. Chen, H. Li, J. Tatemura, et al. Twig2Stack: Bottom-Up Processing of Generalized-Tree-Pattern Queries Over Xml Documents. Proceedings of the 32nd International Conference on Very large Data Bases , Seoul, Korea , 2006. VLDB Endowment. 2006: 283-2945 L. Qin, J. X. Yu and B. Ding. TwigList: Make Twig Pattern Matching Fast. Bangkok, 2008：