TP+Output: Modeling complex output information in XML twig pattern query

Abstract

Twig pattern is considered a core pattern for XML queries. However, due to the limited expressivity of twig pattern expressions, many queries that aim to find complex output information under one object cannot be expressed in a single twig pattern. Instead, they have to be expressed as XQuery expression, which is transformed into several twig patterns linked by joins. To process such an XQuery query, we need to match multiple twig patterns to the XML document, even though they are all centered on the same object. In this paper we analyze the characteristics of each query node, i.e. the purpose, optionality and occurrence, and define four types of nodes in a twig pattern query to express output information, namely, output node, optional-output node, predicated-output node, and optional-predicated-output node. Then we propose the TP+Output expression to extend twig pattern queries, to model complex output information based on the semantics of different node types. With TP+Output, queries with the four output types can be expressed in one TP+Output expression and processed more efficiently. We extend our previously proposed twig pattern query processing algorithm, VERT, to process the TP+Output query, and demonstrate the performance improvement of using TP+Output to represent queries. © 2010 Springer-Verlag.