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.
展开▼
