Universität des Saarlandes
Fachrichtung 6.2 - Informatik
D-66041 Saarbrücken, Germany
Building 36.1, 2nd floor
This talk reports on rewriting XPath-like queries into forward equivalents, i.e., queries without reverse predicates, using the theory of term rewriting systems. We give three such systems and discuss their properties like soundness and completeness, and confluence. We show then how the applications of these rewriting systems shed also light on query language properties like the expressivity of some of its fragments, the query minimization, or the complexity of query evaluation.
Such a rewriting is particularly beneficial in stream contexts, because the evaluation of forward queries, as produced by our rewriting systems, requires only to look forward in the stream and avoids to keep a history of the stream fragments already processed.