Polynomial time fragments of XPath with variables.

Emmanuel Filiot Joachim Niehren Jean-Marc Talbot Sophie Tison

Published in: PODS (2007)

Keyphrases

querying xml data
xml documents
special case
query language
variable selection
worst case
query evaluation
finite sets
xml fragments
transitive closure
random variables
finite automata
xml data
computational complexity
xpath queries
input variables
regular expressions
approximation algorithms
first order logic