Ph.D Thesis

Ph.D StudentCarmeli Nofar
SubjectThe Power of Implicit Acyclicity in the Enumeration
Complexity of Database Queries
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Benny Kimelfeld
Full Thesis textFull thesis text - English Version


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.