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

Guillaume Bagan 1, 2, * Joachim Niehren 2, 1
* Corresponding author
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

Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00609719
Contributor : Joachim Niehren <>
Submitted on : Tuesday, July 19, 2011 - 7:23:48 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM

Identifiers

  • 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⟩

Share

Metrics

Record views

187