Technical Report PHD-2020-09

Title: The Power of Implicit Acyclicity in the Enumeration Complexity of Database Queries
Authors: Nofar Carmeli
Supervisors: Benny Kimelfeld
Abstract: We inspect the fine-grained complexity of answering queries over relational databases. With the ideal guarantees, linear time is required before the first answer to read the input and determine its existence, and then we need to print the answers one by one. Consequently, we wish to identify the queries that can be solved with linear preprocessing time and constant or logarithmic delay between answers. A known dichotomy classifies CQs into those that admit such enumeration and those that do not. The computationally expensive component of query answering is joining tables, which can be done efficiently if and only if the join query is acyclic. However, the join query usually does not appear in a vacuum. For example, it may be part of a larger query, or it may be applied to a database with dependencies. We inspect how the complexity changes in these settings and chart the borders of tractability within. In addition, we consider the task of enumerating query answers with a uniformly random order, and we propose to do so using a random-access structure for representing the set of answers. Our results are accompanied by conditional lower bounds showing that our algorithms capture all tractable cases for some query classes. Among our results, we show that a union of intractable conjunctive queries may be tractable with respect to enumeration, while on the other hand, a union of tractable conjunctive queries may be intractable with respect to random access. To handle cases where we cannot reach efficient enumeration after linear preprocessing time, we also suggest an algorithm for generating tree decompositions. This algorithm can be used to simplify intractable queries by extracting an acyclic structure.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information
DisclaimerRecent theses may have not yet been approved by the Technion Senate, and are provided here for the purpose of fast dissemination of knowledge only. Final approval of the Technion Senate is needed for a thesis to be used for the partial fulfillment of the requirements for the degree of M.Sc. or Ph.D.

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2020
To the main CS technical reports page

Computer science department, Technion