The close relationship between Conjunctive Queries (CQs) and Constraint Satisfaction Problems (CSPs) has long been known. Nevertheless, apart from decomposition methods, research on efficient query evaluation or constraint solving algorithms has developed rather independently. In this article, we illustrate how search algorithms originating from the CSP community can be fruitfully applied to query evaluation - either by further developing the original search algorithms or by combining them with query decomposition methods. It turns out that the resulting approaches may indeed lead to lower time and/or space complexity than previous query evaluation methods.

In the last decade, various works have used statistics on relations to improve both the theory and practice of conjunctive query execution. Starting with the AGM bound which took advantage of relation sizes, later works incorporated statistics like functional dependencies and degree constraints. Each new statistic prompted work along two lines; bounding the size of conjunctive query outputs and worst-case optimal join algorithms. In this work, we continue in this vein by introducing a new statistic called a partition constraint. This statistic captures latent structure within relations by partitioning them into sub-relations which each have much tighter degree constraints. We show that this approach can both refine existing cardinality bounds and improve existing worst-case optimal join algorithms.

Fuzzy relation equations (FRE) are a useful formalism with a broad number of applications in different computer science areas. Testing if a solution exists and, if so, computing the unique greatest solution is straightforward. In contrast, the computation of minimal solutions is more complex. In particular, even in FRE with a very simple structure, the number of minimal solutions can increase exponentially. However, minimal solutions are immensely useful since, under mild conditions, they (together with the greatest solution) allow one to describe the entire space of solutions to an FRE. The main result of this work is a new method for enumerating the set of minimal solutions. It works by establishing a relationship between coverings of FRE and maximal independent elements of (hyper-)boxes. We can thus make efficient enumeration methods for maximal independent elements of (hyper-)boxes applicable also to our setting of FRE, where the operator considered in the composition of fuzzy relations only needs to preserve suprema of arbitrary subsets and infima of non-empty subsets. More specifically, we thus show that the enumeration of the minimal solutions of an FRE can be done with incremental quasi-polynomial delay.

When query evaluation produces too many tuples, a new approach in query answering is to retrieve a diverse subset of them. The standard approach for measuring the diversity of a set of tuples is to use a distance function between tuples, which measures the dissimilarity between them, to then aggregate the pairwise distances of the set into a score (e.g., by using sum or min aggregation). However, as we will point out in this work, the resulting diversity measures may display some unintuitive behavior. Moreover, even in very simple settings, finding a maximally diverse subset of the answers of fixed size is, in general, intractable and little is known about approximations apart from some hand-picked distance-aggregator pairs. In this work, we introduce a novel approach for computing the diversity of tuples based on volume instead of distance. We present a framework for defining volume-based diversity functions and provide several examples of these measures applied to relational data. Although query answering of conjunctive queries (CQ) under this setting is intractable in general, we show that one can always compute a (1-1/e)-approximation for any volume-based diversity function. Furthermore, in terms of combined complexity, we connect the evaluation of CQs under volume-based diversity functions with the ranked enumeration of solutions, finding general conditions under which a (1-1/e)-approximation can be computed in polynomial time.

While extensive research on query evaluation has achieved consistent improvements in the time complexity of algorithms, the space complexity of query evaluation has been largely ignored. This is a particular challenge in settings with strict pre-defined space constraints. In this paper, we examine the combined space-time complexity of conjunctive queries (CQs) and, more generally, of sum-product queries (SPQs). We propose several classes of space-efficient algorithms for evaluating SPQs, and we show that the optimal time complexity is almost always achievable with asymptotically lower space complexity than traditional approaches.

The set of answers to a query may be very large, potentially overwhelming users when presented with the entire set. In such cases, presenting only a small subset of the answers to the user may be preferable. A natural requirement for this subset is that it should be as diverse as possible to reflect the variety of the entire population. To achieve this, the diversity of a subset is measured using a metric that determines how different two solutions are and a diversity function that extends this metric from pairs to sets. In the past, several studies have shown that finding a diverse subset from an explicitly given set is intractable even for simple metrics (like Hamming distance) and simple diversity functions (like summing all pairwise distances). This complexity barrier becomes even more challenging when trying to output a diverse subset from a set that is only implicitly given (such as the query answers for a given query and a database). Until now, tractable cases have been found only for restricted problems and particular diversity functions. To overcome these limitations, we focus in this work on the notion of ultrametrics, which have been widely studied and used in many applications. Starting from any ultrametric d and a diversity function δ extending d , we provide sufficient conditions over δ for having polynomial-time algorithms to construct diverse answers. To the best of our knowledge, these conditions are satisfied by all the diversity functions considered in the literature. Moreover, we complement these results with lower bounds that show specific cases when these conditions are not satisfied and finding diverse subsets becomes intractable. We conclude by applying these results to the evaluation of conjunctive queries, demonstrating efficient algorithms for finding a diverse subset of solutions for acyclic conjunctive queries when the attribute order is used to measure diversity.

Enumeration problems aim at outputting, without repetition, the set of solutions to a given problem instance. However, outputting the entire solution set may be prohibitively expensive if it is too big. In this case, outputting a small, sufficiently diverse subset of the solutions would be preferable. This leads to the Diverse-version of the original enumeration problem, where the goal is to achieve a certain level d of diversity by selecting k solutions. In this paper, we look at the Diverse-version of the query answering problem for Conjunctive Queries and extensions thereof. That is, we study the problem if it is possible to achieve a certain level d of diversity by selecting k answers to the given query and, in the positive case, to actually compute such k answers.