XPath evaluation in linear time with polynomial combined complexity.

Published in: PODS (2009)

Keyphrases

transitive closure
query evaluation
data complexity
combined complexity
query language
first order logic
xml documents
expressive power
conjunctive queries
lower complexity
knowledge base
database systems
relational databases