Enumerating the answers to a query: beyond conjunctive queries

Abstract

Conjunctive Queries (CQs) are one of the most fundamental classes of database queries. As such, the enumeration problem for CQs - that is, given a query and a database, to output all answers of the query over the database in an efficient wayis well understood. However, it is not clear how or even if results on the enumeration complexity do extend to query languages that are natural generalizations of CQs. In this thesis, we aim to evaluate the enumeration complexity of CQs that are extended in three different directions: CQs in the presence of Functional Dependencies (FDs), Unions of Conjunctive Queries (UCQs), and Well-designed pattern trees (wdPTs), which extend CQs by allowing partial matching. For CQs in the presence of FDs as well as for UCQs, our focus is on the ability to list output tuples with a constant delay in between, following a linear-time preprocessing. For wdPTs, we show that even some of the simplest queries can not be enumerated within such bounds. Therefore, we consider the task of enumerating the answers to wdPTs with a polynomial delay between answers. In a seminal paper by Bagan et al., a dichotomy is shown which classifies the acyclic self-join-free CQs into those that admit enumeration with a constant delay. The class of such queries coincides with the class of free-connex CQs. However, this classification no longer holds in the common case where the database exhibits dependencies among attributes: There exist queries that are classified as hard, but their answers can in fact be enumerated with a constant delay, if dependencies are accounted for. We establish a generalization of the dichotomy to accommodate FDs. In addition, we generalize a hardness result for cyclic CQs to accommodate unary FDs, leading to a dichotomy for enumeration with linear delay. Next, we extend the notion of free-connexity from CQs to UCQs, thus showing that some unions containing intractable CQs are, in fact, tractable. Interestingly, some unions consisting of only intractable CQs are tractable too. The question of finding a full characterization of the tractability of UCQs remains open. Nevertheless, we prove that for several classes of queries, free-connexity fully captures the tractable UCQs. For wdPTs, several computational problems have been studied in recent years, such as the evaluation problem under structural restrictions. We show that the parameterized complexity of the evaluation problems is in fact strongly connected to enumeration. Thus extending the existing structural restrictions, we identify several tractable and intractable cases of this problem both from a classical complexity point of view and from a parameterized complexity point of view.