Twig Patterns: From XML Trees to Graphs.
Benny Kimelfeld, Yehoshua Sagiv · International Workshop on the Web and Databases · 2006
Existing approaches for querying XML (e.g., XPath and twig patterns) assume that the data form a tree. Often, however, XML documents have a graph structure, due to ID references. The common way of adapting known techniques to XML graphs is straightforward, but may result in a huge number of results, where only a small portion of them has valuable information. We propose two mechanisms. Filtering is used for eliminating semantically weak answers. Ranking is used for presenting the remaining answers in the order of decreasing semantic significance. We show how to integrate these features in a language for querying XML graphs. Query evaluation is tractable in the following sense. For a wide range of ranking functions, it is possible to generate answers in ranked order with polynomial delay, under query-and-data complexity. This result holds even if projection is used. Furthermore, it holds for any tractable ranking function for which the top-ranked answer can be found efficiently (assuming that equalities and inequalities involving IDs of XML nodes are permitted in queries).