文章基本信息

标题：TJP: A Modified Twig Join Algorithm Based on the Pri-order Labeling Scheme
本地全文：下载
作者：Ren JiaDong, Yue LiWen
期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2006
卷号：6
期号：7A
页码：144-151
出版社：International Journal of Computer Science and Network Security
摘要：XML exploits a tree-structured data model for representing data, and XML queries specify patterns of selection predicates on multiple elements related by a tree structure. Finding all occurrences of such a twig pattern in an XML database is a core operation for XML query processing. A lot of algorithms have been proposed to process to XML twig pattern query based-on region labeling scheme, which can not support the updating of XML documents. In this paper, a new twig join algorithm TJP is proposed, for matching an XML query twig pattern, it is modification of TwigStackList based on a new labeling scheme. This labeling scheme is optimal to determine the relationships between nodes and can support efficiently dynamic updating of documents. TJP uses a list to cache some elements in input data streams; the length of list is not longer than that of the longest path in the XML documents. It is important technique for lists of branching nodes; we preserve the elements in list only when they contribute to the final query results. The algorithm is I/O and CPU optimal for queries with ancestor-descendant edge. When the twig pattern contains parent-child relationships below branching nodes, the algorithm TJP will get a much smaller set of intermediate results than previous join algorithms.
关键词：XML, twig pattern, labeling scheme, join algorithm