answers. 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, suficiently 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.
Answering database queries is one of the most fundamental tasks in computer science and
has thus been the topic of countless theoretical analyses from numerous diferent perspectives.
Classically, the focus of complexity studies by the database theory community has been on
decision problems such as deciding if the query result is non-empty or if a given tuple is
contained in the query result. In recent times, the enumeration problem (i.e., outputting all
answers to a query) has played a prominent role on the research agenda, see e.g1., 2[
It is well known that even seemingly simple problems, such as answering an acyclic Conjunctive Query, can have a huge number of solutions. Consequently, specific notions of tractability were introduced right from the beginning of research on enumeration proble m4]st[o separate the computational intricacy of a problem from the mere size of the solution space. However, even with these refined notions of tractability, the usefulness of flooding the user with tons of solutions (many of them possibly difering only minimally) may be questionable. If the solution space gets too big, it would be more useful to provide an overview by outputting a “meaningful” subset of the solutions.
For instance, consider a variation of the car dealership example from5][. Suppose that models the preferences of a customer and( )
are all cars that match these restrictions. Now, nEvelop-O in a large dealership, presenting all cars in ( ) to the customer would be infeasible. Instead, it would be better to go through a rather small list of cars that are significantly diferent from each other. With this, the customer can point at those cars which the further discussion with the clerk should concentrate on.
This example suggests that we should focus on finding a smalldiverse set of answers to database queries. Due to the inherent hardness of computing maximally diverse solutio5n],s [ the database community – apart from limited exception6]s –[ mostly focused on heuristic and approximation methods to find diverse answers (see 7[] for an extensive survey). The present work takes a step forward to fill this void, broadening our understanding of the theoretical boundaries of diverse query answering while developing complementary exact algorithms. More specifically, we analyze diversity problems related to answering Conjunctive Queries (CQs) and extensions thereof.
Problem statement. To formalize the problems, we roughly follow the approach from 8[] by defining the diversity of a set of answers (tuples) to be their aggregated pairwise distances. Furthermore, in the spirit of classical relational database theory, we consider the data untyped and use the Hamming distancΔe( , ′) as the measure of distance between two answer tuples , ′. As far as the choice of an aggregator is concerned, we impose the general restriction that it must be computable in polynomial time. Formally, for a cl assof queries we study the following problem Diverse- :
Diverse- Instance: A database instance, query ∈ , and integer s and .
Question: Do there exist pairwise distinct answe r1s, … , ∈ ( ) (diversity
set) such that ((Δ( , ))1≤<≤ ) ≥ ?
That is, we ask if a certain leve l of diversity can be achieved by choosin g pairwise distinct answers to a given query over the database instan ce.Since we are intuitively looking fosrmall diversity sets, we usually conside r to be a problem parameter in the sense of parameterized complexity.
For proving upper bounds on the complexity in terms of membership, we aim for the most general setting, i.e., the most general class of aggregatorasnd the biggest query class . On the other hand, for lower bounds in terms of hardness proofs, we aim for the most restrictive, i.e., a concrete (but natural) aggregatorand the smallest query class . In particular, the natural aggregators minimum and sum will be used to prove lower bounds while, for the upper bound, we either impose no further restriction onor require them to be monotone in addition, i.e.,(( , )1≤<≤ ) ≤ (( ,′ )1≤<≤ ) whenever , ≤ ,′ holds for every 1 ≤ < ≤ . The corresponding diversity problems are denoted bDyiversemin- , Diversesum- , and Diversemon- , respectively.
As for the query classes , we start our analysis with the clasCsQ of Conjunctive Queries and
then extend our studies to the classUeCsQ and CQ¬ of unions of CQs and CQs with negation.
As the most general query class, we will also look at the claFssO of all first-order queries. Recall
that, even the question if an answer tuple exists at aNllPis-complete for CQs [
a labeling ∶ ( ) → 2
() defined as follows: Queries. Formally, we can consider our various query classes as fragments of first-order logic with the corresponding database being a matching finite first-order structure and answers being assignments on the free variables. CQs are formulae solely using the connectiv{∃e,s∧}, while UCQs additionally allow{∨} as a top-level connective and CQ¬sadditionally allow negated atoms. ∶ ( ) → 2 ( ) Acyclicity and widths. (Generalized hyper-)tree decompositions and their corresponding widths are staple tools to express the acyclicity of CQs (with negation) and define large tractable query classes. A tree decompositions of a CQ¬ is a tuple ⟨ , ⟩ such that is a tree and ()
. Furthermore, for each atom , all its variables have to appear in some together, and for each variable, the vertice s where appears in ( ) have to induce a connected subtree in. A generalized hypertree decomposition extends a tree decomposition by such that, for every nod e in , every variable of ( ) appears in some atom of( ) . Then the treewidth of and the generalized hypertree width ofare tw() = min max | ( )| − 1, ⟨ ,⟩ ghw() = ⟨ ,,⟩ min max |( )|.
CQs are called acyclic (ACQs) if ghw() = 1 and UCQs = ∨ are called acyclic (UACQs) if all conjunctions are acyclic.
Parameterized Complexity. An instance of aparameterized problem is given as a pair (, ) , where is the actual problem instance andis a parameter. A problem is inFPT (fixed-parameter tractable), if it can be solved in time( () ⋅ || and inXP, if it can be solved in time(||
) (for some computable functio n and constant)
() ). Furthermore, there is a classW[
The main novel lower bounds of our work are the following hardness results: Theorem 1. On queries of bounded tw, the problems
Diversesum-CQ
and
Diversemin-CQ are [
The theorem follows by reduction from the (parameterizeIdn)dependent Set problem. In the
case where arbitrarily large, albeit almost acyclic, queries are allowed, the reduction preserves
the parameter and impliesW[
Somewhat surprisingly, dealing with UCQs is significantly harder than dealing with CQs. Theorem 2. On UACQs and when the size of the sought-after diversity set is at most two, the problems Diversesum-UCQ and Diversemin-UCQ remain -hard.
Intuitively, this comes down to the fact that even if all conjuncts of a query are acyclic, the interconnectedness of two or more conjuncts can be arbitrarily cyclic. Furthermore, when searching for diverse answers to UCQs, it is not suficient to solve the conjuncts independently.
Complementing theW[
This runtime can be achieved by dynamic programming algorithms which maintain data structures storing all possible-tuples of partial solutions together with all possible pairwise Hamming distances. This data structure is then propagated along the (generalized hyper-)tree decompositions. In the end, a witnessing diversity set can be extracted from the root. Crucially, the size of the data structure is exponential onl y i(nand the (generalized hyper-)tree width).
For queries of bounded size, an even faster algorithm is developed.
Theorem 4. On queries of bounded size, the problem Diversemon- is in .
Such a runtime is achieved by a kernelization algorithm. Essentially, first, all (polynomially many) query answers are computed. Then, the answers are grouped by all possible subsets of the columns, and whenever a group exceeds a certain threshold, insuficiently diverse members of the group are discarded.
Table 1 summarizes the discussed results.
Query class bounded ghw CQ bounded tw CQ¬
UACQ bounded size FO
Lower Bound
W[
W[
NP*
Upper Bound
XP XP FPT
In this work, we took a fresh look at thDeiversity problem of query answering. Looking at
diferent classes of queries from CQs to FO queries, we provide a fairly complete picture of
complexity results. Nevertheless, numerous directions for future work exist, including:
Restricting the database. We primarily focused on restrictions on the queries. However,
restricting the database is also a viable option with far-reaching implications in related areas. Our full
paper contains some preliminary results1[
Further parameterization. Exploring further parameterizations besides the size of the diversity
set seems interesting. For instance, choosing the diversity thresh oleldad to intriguing results
in [
Alternative distance measure. The Hamming distance might not a suitable distance measure in all situation. It might thus be interesting to consider replacing it by more specific distance measures derived from domain specific metrics.
This work has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT2201, 10.47379/VRG18013, 10.47379/NXT22018]; and the Christian Doppler Research Association (CDG) JRC LIVE.