Constant Delay Enumeration for Acyclic Conjunctive Queries over X-Doublebar Structures

Guillaume Bagan 1, 2, * Joachim Niehren 2, 1
* Auteur correspondant
2 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We present an efficient answer enumeration algorithm for a fragment of Conditional XPath with variables, which is a first-order complete query language for unranked trees of bounded depth. Our algorithm requires linear precomputation time and constant delay for fixed queries, while depending linearly on the size of the query. It is based on a new enumeration algorithm for disjunctions of acyclic conjunctive queries on so called X-doublebar-structures that we introduce.

Keywords: Logic, databases, enumeration, XML

http://www.grappa.univ-lille3.fr/~niehren/Papers/X-doublebar/0.pdf

Type de document :
Rapport
[Research Report] 2011
Liste complète des métadonnées

https://hal.inria.fr/inria-00609719
Contributeur : Joachim Niehren <>
Soumis le : mardi 19 juillet 2011 - 19:23:48
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

  • HAL Id : inria-00609719, version 1

Collections

Citation

Guillaume Bagan, Joachim Niehren. Constant Delay Enumeration for Acyclic Conjunctive Queries over X-Doublebar Structures. [Research Report] 2011. 〈inria-00609719〉

Partager

Métriques

Consultations de la notice

121