HAL - INRIA :: [inria-00390236, version 2] Earliest Query Answering for Deterministic Nested Word Automata

inria-00390236, version 2

Earliest Query Answering for Deterministic Nested Word Automata

Olivier Gauwin ()^a^, 1, 2, Joachim Niehren () ^1, 2, Sophie Tison ()^b^, 1, 2

17th International Symposium on Fundamentals of Computer Theory 5699 (2009) 121-132

Abstract: Earliest query answering (EQA) is an objective of many recent streaming algorithms for XML query answering, that aim for close to optimal memory management. In this paper, we show that EQA is infeasible even for a small fragment of Forward XPath except if P=NP. We then present an EQA algorithm for queries and schemas defined by deterministic nested word automata (dNWAs) and distinguish a large class of dNWAs for which streaming query answering is feasible in polynomial space and time.

a – INRIA
b – Université des Sciences et Technologies de Lille - Lille I
1: MOSTRARE (INRIA Lille - Nord Europe)
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

inria-00390236, version 2
http://hal.inria.fr/inria-00390236
oai:hal.inria.fr:inria-00390236
From: Joachim Niehren <>
Submitted on: Thursday, 13 August 2009 12:58:45
Updated on: Tuesday, 3 November 2009 16:45:41

See detailed view

Associated documents

PDF :

Export

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>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00390236"><analytic>
<author><persName><forename>Olivier</forename><surname>Gauwin</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</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>Joachim</forename><surname>Niehren</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</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>Sophie</forename><surname>Tison</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</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">Earliest Query Answering for Deterministic Nested Word Automata</title></analytic><monogr><meeting>17th International Symposium on Fundamentals of Computer Theory</meeting><imprint><publisher>SV</publisher><pubPlace><settlement>Wraclaw</settlement><country>Poland</country></pubPlace><biblScope type="publicationDate">2009-00-00</biblScope><biblScope type="vol">5699</biblScope><biblScope type="pp">121-132</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00390236</idno><idno type="HALFile">http://hal.inria.fr/inria-00390236/PDF/0.pdf</idno></biblStruct>
</listBibl>
</listBibl>