On the Diversity and Space-Time Complexity of Query Answering: Algorithms and Structural Foundations

Abstract

Conjunctive queries (CQs) form the theoretical and practical backbone of modern database systems. They correspond to the part of SQL responsible for expressing joins, selections, and projections – the most frequent and performance critical operations in relational databases. This thesis advances the study of conjunctive queries by developing new algorithms and frameworks that improve the efficiency of query evaluation. A first line of contributions focuses on computing diverse query answering, addressing situations where a query yields too many results and the system is expected to return a meaningful subset of them. To that end, we study two complementary approaches to compute a diverse subset of query answers. The first provides diversity answers through ultrametric-based diversity measures, which endow query answers with a hierarchical structure that allows computing optimally diverse subsets efficiently. The second introduces a volume-based framework for computing diverse query answers that guarantees an (1 − 1/e)-approximation factor by employing agreedy algorithm. In this framework, we interpret diversity geometrically as the volume occupied by answers in some feature space. A second line of work targets the efficient computation of all query results withdata-dependent worst-case optimal join runtime guarantees. To that end, we propose partition constraints (PCs) as a novel generalization of degree constraints (DCs) to capture skew common in practical datasets. PCs allow us to more tightly bound the worst-case number of answers to a query and we show how existing worst-case optimal join algorithms developed for DCs can be extended to leverage PCs for improved performance. Finally, we study the space-time complexity of query processing. Building upontechniques from both database theory and probabilistic graphical models (PGMs),we show how pseudo-tree (PT) based algorithms developed for PGMs can be lifted toquery evaluation algorithms via generic join style loops. By construction, these algorithms are space-optimal, using only constant additional space. We then investigate controlled space-time trade-offs through caching strategies and tree decompositions, culminating in the novel structure termed recursive pseudo-trees. We show that optimal time complexity is often achievable with asymptotically lower space complexity than traditional approaches.