Abstract
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 language | English |
---|---|
Title of host publication | Proceedings of the 2023 Computer Science Logic Conference |
Editors | Bartek Klin, Elaine Pimentel |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Number of pages | 20 |
Volume | 252 |
ISBN (Electronic) | 978-3-95977-264-8 |
DOIs | |
Publication status | Published - 1 Feb 2023 |
Event | The 31st EACSL Annual Conference on Computer Science Logic, 2023 - Warsaw, Poland Duration: 13 Feb 2023 → 16 Feb 2023 Conference number: 31 https://csl2023.mimuw.edu.pl/ |
Publication series
Name | LIPIcs – Leibniz International Proceedings in Informatics |
---|---|
Publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
Volume | 252 |
ISSN (Electronic) | 1868-8969 |
Conference
Conference | The 31st EACSL Annual Conference on Computer Science Logic, 2023 |
---|---|
Abbreviated title | CSL 2023 |
Country/Territory | Poland |
City | Warsaw |
Period | 13/02/23 → 16/02/23 |
Internet address |
Keywords / Materials (for Non-textual outputs)
- acyclic queries
- query evaluation
- enumeration delay