HAL - INRIA :: [inria-00135678, version 1] Polynomial Time Fragments of XPath with Variables

inria-00135678, version 1

Polynomial Time Fragments of XPath with Variables

Emmanuel Filiot ¹, Joachim Niehren () ^1, 2, Jean-Marc Talbot ³, Sophie Tison ^1, 2

26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (2007) 205-214

Résumé : 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.

1 : MOSTRARE (INRIA Futurs)
INRIA – CNRS : UMR8022 – Université des Sciences et Technologies de Lille - Lille I : EA3588 – Université Charles de Gaulle - Lille III
2 : Laboratoire d'Informatique Fondamentale de Lille (LIFL)
CNRS : UMR8022 – INRIA – IRCICA – Université des Sciences et Technologies de Lille - Lille I
3 : Laboratoire d'informatique Fondamentale de Marseille (LIF)
CNRS : UMR6166 – Université de la Méditerranée - Aix-Marseille II – Université de Provence - Aix-Marseille I

inria-00135678, version 1
http://hal.inria.fr/inria-00135678
oai:hal.inria.fr:inria-00135678
Contributeur : Joachim Niehren <>
Soumis le : Mercredi 21 Mars 2007, 16:08:35
Dernière modification le : Jeudi 13 Mai 2010, 01:01:39

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="inria-00135678"><analytic>
<author><persName><forename>Emmanuel</forename><surname>Filiot</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Futurs</orgName>
<orgName type="team">MOSTRARE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université des Sciences et Technologies de Lille - Lille I : EA3588</orgName>
<orgName type="institution">Université Charles de Gaulle - Lille III</orgName>
</affiliation>
</author>
<author><persName><forename>Joachim</forename><surname>Niehren</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Futurs</orgName>
<orgName type="team">MOSTRARE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université des Sciences et Technologies de Lille - Lille I : EA3588</orgName>
<orgName type="institution">Université Charles de Gaulle - Lille III</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIFL</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale de Lille</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">IRCICA</orgName>
<orgName type="institution">Université des Sciences et Technologies de Lille - Lille I</orgName>
</affiliation>
</author>
<author><persName><forename>Jean-Marc</forename><surname>Talbot</surname></persName>
<affiliation>
<orgName type="laboratory">LIF</orgName>
<orgName type="team">Laboratoire d'informatique Fondamentale de Marseille</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6166</orgName>
<orgName type="institution">Université de la Méditerranée - Aix-Marseille II</orgName>
<orgName type="institution">Université de Provence - Aix-Marseille I</orgName>
</affiliation>
</author>
<author><persName><forename>Sophie</forename><surname>Tison</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Futurs</orgName>
<orgName type="team">MOSTRARE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université des Sciences et Technologies de Lille - Lille I : EA3588</orgName>
<orgName type="institution">Université Charles de Gaulle - Lille III</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIFL</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale de Lille</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">IRCICA</orgName>
<orgName type="institution">Université des Sciences et Technologies de Lille - Lille I</orgName>
</affiliation>
</author>
<title type="main" level="a">Polynomial Time Fragments of XPath with Variables</title></analytic><monogr><meeting>26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems</meeting><imprint><pubPlace><settlement>Beijing</settlement><country>Chine</country></pubPlace><biblScope type="publicationDate">2007-00-00</biblScope><biblScope type="pp">205-214</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00135678</idno><idno type="HALFile">http://hal.inria.fr/inria-00135678/PDF/0.pdf</idno></biblStruct>
</listBibl>
</listBibl>