Polynomial Time Fragments of XPath with Variables

Abstract : Variables are the distiguishing new feature of XPath 2.0 which permits to select n-tuples of nodes in trees. It is known that the Core of XPath 2.0 captures n-ary first-order (FO) queries modulo linear time transformations. In this paper, we distinguish a fragment of Core XPath 2.0 that remains FO-complete with respect to n-ary queries while enjoying polynomial-time query answering.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00135678
Contributor : Joachim Niehren <>
Submitted on : Wednesday, March 21, 2007 - 4:08:35 PM
Last modification on : Thursday, July 25, 2019 - 8:50:07 AM
Long-term archiving on : Friday, September 21, 2012 - 12:40:46 PM

File

0.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00135678, version 1

Collections

Citation

Emmanuel Filiot, Joachim Niehren, Jean-Marc Talbot, Sophie Tison. Polynomial Time Fragments of XPath with Variables. 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Jun 2007, Beijing, China. pp.205-214. ⟨inria-00135678⟩

Share

Metrics

Record views

522

Files downloads

339