Evaluation Trade-Offs for Acyclic Conjunctive Queries

Ahmet Kara, Milos Nikolic, Dan Olteanu, Haozhe Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We consider the evaluation of acyclic conjunctive queries, where the evaluation time is decomposed into preprocessing time and enumeration delay. In a seminal paper at CSL’07, Bagan, Durand, and Grandjean showed that acyclic queries can be evaluated with linear preprocessing time and linear enumeration delay. If the query is free-connex, the enumeration delay becomes constant. Further prior work showed that constant enumeration delay can be achieved for arbitrary acyclic conjunctive queries at the expense of a preprocessing time that is characterised by the fractional hypertree width. We introduce an approach that exposes a trade-off between preprocessing time and enumeration delay for acyclic conjunctive queries. The aforementioned prior works represent extremes in this trade-off space. Yet our approach also allows for the enumeration delay and the preprocessing time between these extremes, in particular the delay may lie between constant and linear time. Our approach decomposes the given query into subqueries and achieves for each subquery a trade-off that depends on a parameter controlling the times for preprocessing and enumeration. The complexity of the query is given by the Pareto optimal points of a bi-objective optimisation program whose inputs are possible query decompositions and parameter values.
Original languageEnglish
Title of host publicationProceedings of the 2023 Computer Science Logic Conference
EditorsBartek Klin, Elaine Pimentel
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages20
ISBN (Electronic)978-3-95977-264-8
Publication statusPublished - 1 Feb 2023
EventThe 31st EACSL Annual Conference on Computer Science Logic, 2023 - Warsaw, Poland
Duration: 13 Feb 202316 Feb 2023
Conference number: 31

Publication series

NameLIPIcs – Leibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik
ISSN (Electronic)1868-8969


ConferenceThe 31st EACSL Annual Conference on Computer Science Logic, 2023
Abbreviated titleCSL 2023
Internet address

Keywords / Materials (for Non-textual outputs)

  • acyclic queries
  • query evaluation
  • enumeration delay


Dive into the research topics of 'Evaluation Trade-Offs for Acyclic Conjunctive Queries'. Together they form a unique fingerprint.

Cite this