毕业设计：有效地处理XML分支模式.doc

滨州学院本科毕业设计（专业外文翻译） PAGE 12 专业外文翻译 题 目Efficient Processing of Ordered XML Twig PatternEfficient Processing of Ordered XML Twig Pattern Jiaheng Lu, Tok Wang Ling, Tian Yu, Changqing Li, Wei Ni School of computing, National University of Singapore Abstract： Finding all the occurrences of a twig pattern in an XML database is a core operation for efficient evaluation of XML queries. Holistic twig join algorithm has showed its superiority over binary decompose based approach due to efficient reducing intermediate results. The existing holistic join algorithms, however, cannot deal with ordered twig queries. A straightforward approach that first matches the unordered twig queries and then prunes away the undesired answers is obviously not optimal in most cases. In this paper, we study a novel holistic-processing algorithm, called OrderedTJ, for ordered twig queries. We show that OrderedTJ can identify a large query class to guarantee the I/O optimality. Finally, our experiments show the effectiveness, scalability and efficiency of our proposed algorithm. 1． Introduction With the rapidly increasing popularity of XML for data representation, there is a lot of interest in query processing over data that conforms to a tree-structured data model([1],[5]). Efficient finding all twig patterns in an XML database is a major concern of XML query processing. Recently, holistic twig join approach has been taken as an efficient way to match twig pattern since this approach can efficiently control the size of intermediate results([1],[2],[3],[4]). We observe that, however, the existing work on holistic twig query matching only considered unordered twig queries. But XPath defines four ordered axes: following-sibling, preceding-sibling, following, preceding. For example, XPath: //book/text/following-sibling::chapter is an ordered query, which finds all chapters in the dataset that are following siblings of text which should be a child of book. We call a twig query which cares