Bounded Delay and Concurrency for Earliest Query Answering
| Autor: | Olivier Gauwin, Joachim Niehren, Sophie Tison |
|---|---|
| Přispěvatelé: | Modeling Tree Structures, Machine Learning, and Information Extraction (MOSTRARE), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), Adrian Horia Dediu and Armand Mihai Ionescu and Carlos Martin-Vide, ANR-07-BLAN-0327,ENUM,Algorithms and Complexity for Answer Enumeration(2007) |
| Jazyk: | angličtina |
| Rok vydání: | 2009 |
| Předmět: |
Theoretical computer science
[INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB] Computer science Concurrency Node (networking) InformationSystems_DATABASEMANAGEMENT Tree Automata 0102 computer and information sciences 02 engineering and technology computer.software_genre Streaming 01 natural sciences [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] Decidability XML database XML Databases 010201 computation theory & mathematics 020204 information systems Bounded function Streaming XML 0202 electrical engineering electronic engineering information engineering Tree automaton Time complexity computer |
| Zdroj: | 3rd International Conference on Language and Automata Theory and Applications 3rd International Conference on Language and Automata Theory and Applications, Apr 2009, Tarragona, Spain. pp.350-361, ⟨10.1007/978-3-642-00982-2⟩ Language and Automata Theory and Applications ISBN: 9783642009815 LATA |
| DOI: | 10.1007/978-3-642-00982-2⟩ |
| Popis: | International audience; Earliest query answering is needed for streaming XML processing with optimal memory management. We study the feasibility of earliest query answering for node selection queries. Tractable queries are distinguished by a bounded number of concurrently alive answer candidates at every time point, and a bounded delay for node selection. We show that both properties are decidable in polynomial time for queries defined by deterministic automata for unranked trees. Our results are obtained by reduction to the bounded valuedness problem for recognizable relations between unranked trees. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|