Rewriting XPath queries using materialized XPath views

• Published in: Journal of computer and system sciences 2012-07, Vol.78 (4), p.1006-1025
• Main Author: Ramanan, Prakash
• Format: Article
• Language: English
• Subjects: Algorithms; Equivalence; Fragmentation; Homomorphism; Queries; Query evaluation; Rewriting; Simulation; Trees; Views; XML; XPath
• ISSN: 0022-0000; 1090-2724
• DOI: 10.1016/j.jcss.2011.12.001

Let XP(/,//,[]) be the fragment of XPath 1.0, consisting of queries that involve only the child and descendant axes, and predicates without disjunction or negation (and no wildcard nodetests); these queries can be represented as tree patterns. We consider the problem of rewriting a query Q using a materialized view V, where Q,V∈XP(/,//,[]). We present more efficient algorithms for the following: (1) Determine if an equivalent rewriting of Q using V exists; find the smallest such rewriting, when it exists. A previously-known algorithm runs in O(|Q|2+|Q||V|) time. For the special case when Q is known to be minimal, we present an O(|Q||V|) algorithm. (2) Determine if a (nonempty) contained rewriting of Q using V exists. We present an O(|Q||V|) algorithm, compared to the previous O(|Q||V|2) algorithm. We also present a more efficient algorithm for finding a maximal such rewriting, when it exists. Then we extend this result to a subset of XP(/,//,[],⁎) that allows restricted occurrences of wildcard nodetests. ► Study the problem of rewriting an XPath query using a materialized XPath view. ► Characterize when an equivalent rewriting exists. ► Faster algorithm to determine if a maximal contained rewriting exists. ► Faster algorithm to find a compact representation of all contained rewritings. ► Study the relationship between homomorphisms and simulation.