Benchmarking Approximate Consistent Query Answering

Abstract

Consistent query answering (CQA) aims to deliver meaningful answers when queries are evaluated over inconsistent databases. Such answers must be certainly true in all repairs, which are consistent databases whose diference from the inconsistent one is somehow minimal. A more informative notion is the percentage of repairs in which a candidate answer is true, called relative frequency. Computing this percentage is intractable in general, but for the relevant setting of conjunctive queries and primary keys, data-eficient randomized approximation schemes exist. Our goal is to perform a thorough experimental evaluation and comparison of those approximation schemes and provide new insights on which technique is indicated depending on key characteristics of the input.

1. Introduction

A database is inconsistent if it does not conform to its specifications given in the form of constraints. There is a consensus that inconsistency is a real-life phenomenon that arises due to many reasons such as integration of conflicting sources. With the aim of obtaining conceptually meaningful answers to queries posed over inconsistent databases, Arenas, Bertossi, and Chomicki introduced in the late 1990s the notion of Consistent Query Answering (CQA) [ 1 ]. The key elements underlying CQA are (1) the notion of repair of an inconsistent database , that is, a consistent database that difers somehow minimally from the original database , and (2) the notion of query answering based on certain answers, i.e., answers that are entailed by every repair. Here is a simple example taken from [ 2 ]: Example 1. Consider the single relation Employee(id, name, dept) where the attribute id is the key of the relation Employee. Consider also the database consisting of the tuples: (1, Bob, HR) (1, Bob, IT) (2, Alice, IT) (2, Tim, IT).

Observe that the above database is inconsistent w.r.t. the key constraint since we are uncertain about Bob’s department, and the name of the employee with id 2. In this case, to devise a repair, we only need to keep one of the two atoms that are in a conflict. In this way, we obtain a ⊆ -maximal subset of that is consistent. Consider now the Boolean query that asks whether employees 1 and 2 work in the same department. This query is true only in two repairs, thus, according to certain answers, is not entailed.

CQA has been extensively studied both in theory (see, e.g., [ 3, 4, 5 ]), and in practice (see, e.g., [ 6, 7 ]). Nevertheless, the CQA approach comes with a conceptual limitation. The notion of certain answers only says that a candidate answer is entailed by all repairs, or is not entailed by at least one repair. But, as it has been frequently observed (e.g., see [ 2, 8, 9 ]), the former is too strict, while the latter is not very useful in a practical context.

A Refined Approach. A simple step in obtaining more information for a candidate answer is to consider its relative frequency, i.e., the percentage of repairs that entail the answer [ 2 ]. In Example 1, the relative frequency of the empty tuple (i.e., the only candidate answer for Boolean queries) is 50% since, out of four repairs in total, only two satisfy the query. However, computing this simple measure is #P-hard, even in data complexity, i.e., when the query and the constraints are fixed, and even if we focus on conjunctive queries and primary keys [ 10 ]. Hence, the way to proceed is to give up exact solutions, and target approximations. Data-eficient Approximations. Approximation algorithms have been crucial for tackling intractable problems in diferent areas of Data Management. Examples are in the context of approximating certain answers over incomplete databases, where diferent approximation algorithms have been devised and experimentally evaluated [ 11, 12, 13 ]. In the case of inconsistent databases, data-eficient randomized algorithms exist, in the relevant setting of conjunctive queries and primary keys, that approximate the relative frequency of a candidate answer within a desired error, with high probability [ 2 ]. These rely on techniques that have been originally proposed to approximate the number of satisfying assignments of DNF Boolean formulas [ 14 ]. However, no corresponding infrastructure for experimentally evaluating such techniques exists. Main Objective. The main objective of this work is to provide a benchmark for these randomized approximation schemes, when considering primary keys and conjunctive queries, covering a wide range of scenarios, and exploit this benchmark to asses how the performance of the approximation schemes is afected by key parameters of the input. 1

2. Preliminaries

Relational Databases. A schema S is a finite set of relation symbols (or predicates) with associated arity. A database over a schema S is a set of facts of the form (̄), where ∈ S, and ̄ = 1, . . . , is a tuple of terms that are drawn from a countably infinite set C of constants. We write dom() for the active domain of , that is, the set of constants occurring in . Primary Key Constraints. A key constraint (or key) over a schema S is an expression key() = {1, . . . , }, where ∈ S has arity , and ≤ ; we also call it an -key. A database satisfies if, for every (̄), ()̄ ∈ , ̄[] = [̄ ] for each ∈ {1, . . . , } implies ̄ = ̄. We say that is consistent w.r.t. a set Σ of keys, written |= Σ , if satisfies each key in Σ ; otherwise, it is inconsistent. A set of primary keys Σ is a set of keys such that, for each predicate , Σ has at most one -key. For = (1, . . . , ), the key value of 1An extended version of this paper has been accepted to PODS 2021, and can be found at https://tinyurl.com/ f8sev5pj. Source code and test scenarios can be found at https://gitlab.com/mcalautti/cqabench. w.r.t. Σ , denoted keyΣ ( ), is defined as ⟨, ⟨1, . . . , ⟩⟩, if key() = {1, . . . , } ∈ Σ , and ⟨, ⟨1, . . . , ⟩⟩ otherwise. Let blockΣ (, ) = { ∈ | keyΣ ( ) = keyΣ ( )}, and blockΣ () = {blockΣ (, ) | ∈ }. A repair of w.r.t. Σ is a database obtained by choosing one fact from each ∈ blockΣ (). We denote the set of repairs of w.r.t Σ as rep(, Σ) . Conjunctive Queries. A conjunctive query (̄) over a schema S is a first-order expression of the form ∃̄ (︀ 1(̄1) ∧ · · · ∧

(̄)︀) that mentions only atoms over S, and has free variables ̄.

For a tuple ̄ ∈ C|̄|, (̄) denotes after replacing the -th variable in ̄ with the -th constant in ̄. A homomorphism from to a database is a function ℎ from the set of variables and constants in to dom() that is the identity over C such that (ℎ(̄)) ∈ for every ∈ []. We use →ℎ to say that ℎ is a homomorphism from to . The answer to (̄) over a database , denoted (), is the set of tuples {ℎ(̄) ∈ dom()|̄| | (̄) →ℎ }.

R,Σ ,(̄) = |{′ ∈ rep(, Σ)

| ̄ ∈ (′)}|/|rep(, Σ) |. Our main problem is: Consistent Query Answering. Consider a database , a set Σ of primary keys, and a CQ (̄) . The relative frequency of a tuple ̄ ∈ dom()|̄| w.r.t. , Σ and is the ratio

PROBLEM : INPUT : OUTPUT :

CQA

A database , a set Σ of primary keys, and a CQ (̄) .

The set {︀ (̄, R,Σ ,(̄)) | ̄ ∈ dom()|̄| and R,Σ ,(̄) > 0}︀ .

That is, output, for each candidate answer tuple ̄, its relative frequency, when this is not zero. We dub the problem of computing R,Σ ,(̄), given , Σ , , ̄, RelativeFreq. We know that RelativeFreq is #P-hard, in data complexity. Clearly, having an eficient way of approximating the relative frequency of a tuple will immediately provide an algorithm for approximately solving CQA. Hence, in the rest, we focus on RelativeFreq.

Pr (| − R,Σ ,(̄)| ≤ · R,Σ ,(̄)) ≥ 1

− .

Approximate CQA. A (data-eficient) randomized approximation scheme for the problem RelativeFreq is a randomized algorithm A that takes a database , a set Σ of primary keys, a CQ (̄) , a tuple ̄ ∈ dom()|̄|, and numbers > mial time in |||| + ||̄||,2 1/ and log(1/ ), and produces a random variable such that 0 and 0 < <

1, runs in polyno

3. Approximation Schemes

In principle, an approximation scheme for RelativeFreq would require to access the input database . However, doing this naively is prohibitive in practice since, in general, is very large. However, an approximation scheme for RelativeFreq only needs a small part of the database, which we call synopsis. In what follows, let , Σ , (̄) , ̄ be a database, a set of primary keys, a CQ and a tuple in dom()|̄|, respectively.

The (Σ , )-synopsis of for ̄ is the pair (ℋ, ℬ), where ℋ = {ℎ() | (̄) , and ℎ() |= Σ } and ℬ = {blockΣ (, ) | ∈ ∪∈ℋ}. That is, the (Σ , )-synopsis of for ̄ collects all the consistent homomorphic images of (̄) in (the set ℋ), and the blocks of the atoms occurring in a consistent homomorphic image of (̄) in (the ℎ → 2As usual, for a syntactic object , we write |||| for its size. set ℬ). We also let db(ℬ) = {{ 1, . . . , } | ⟨ 1, . . . , ⟩ ∈ × ∈ℬ}, i.e., the set of databases that can be formed by keeping exactly one atom from each member of ℬ. Finally, R(ℋ,ℬ) = |{ ∈ db(ℬ) | ⊆ for some ∈ ℋ}||db(ℬ)|.3

We show that the (Σ , )-synopsis of a database for a tuple ̄ can be eficiently constructed, and it contains enough information that allows us to compute the relative frequency of ̄. Lemma 2. If (ℋ, ℬ) is the (Σ , )-synopsis of for ̄, then :1) (ℋ, ℬ) can be computed in polynomial time in |||| + ||̄||; 2) R,Σ ,(̄) = R(ℋ,ℬ); 3) R,Σ ,(̄) = 0 if ℋ = ∅.

3.1. Monte Carlo Approach

Let (ℋ, ℬ) be the (, Σ) -synopsis of some tuple ̄ and let Sample be a randomized procedure that with input (ℋ, ℬ), computes a random number in [ 0, 1 ]. Being randomized, its output is determined by the underlying sampling space obtained from (ℋ, ℬ). Sample(ℋ, ℬ) produces a random variable, and a crucial problem for us is computing its expected value E[Sample(ℋ, ℬ)].

E[Sample(ℋ, ℬ)] can be approximated by performing the following: (1) := 0, (2) for times do the following: := + Sample(ℋ, ℬ), and finally (3) return / .

It is clear that as long as we increase the number of iterations in the above procedure, the ratio / is a better approximation of E[Sample(ℋ, ℬ)]. From [ 15 ], we know that we can compute the minimum number (up to constant factors) of iterations such that the above algorithm approximates E[Sample(ℋ, ℬ)] within a given error , and with probability at least 1 − , for some given 0 < < 1. By exploiting this approach in the algorithm discussed above, we obtain the algorithm MonteCarlo[Sample], which is parametrized with a randomized procedure Sample. Let ||ℋ, ℬ|| = |ℋ| + max∈ℋ{||||} + ||ℬ||. From [ 15 ], we know that: (*) If Sample runs in polynomial time in ||ℋ, ℬ|| and E[Sample(ℋ, ℬ)] > 1/pol(||ℋ, ℬ||), when E[Sample(ℋ, ℬ)] > 0, for some polynomial pol, then MonteCarlo[Sample] is a data-eficient randomized approximation scheme for computing E[Sample(ℋ, ℬ)].4

By combining the above property and Lemma 2, an approximation scheme for RelativeFreq can be obtained by devising the right sampling procedure Sample.

Natural Sampling Space. The first sampler, which we call SampleNatural, takes as input (ℋ, ℬ), and has E[SampleNatural(ℋ, ℬ)] = R(ℋ,ℬ), i.e., its expected value precisely coincides with the relative frequency. This sampler simply performs the following: 1) sample a database ∈ db(ℬ) uniformly at random (u.a.r.); 2) if ⊆ , for some ∈ ℋ, output 1, otherwise output 0. We can prove that SampleNatural enjoys (*) and E[SampleNatural(ℋ, ℬ)] = R(ℋ,ℬ). By Lemma 2, the algorithm that constructs the (, Σ) -synopsis (ℋ, ℬ) of ̄, and runs MonteCarlo[SampleNatural] with input (ℋ, ℬ), is an approximation scheme for RelativeFreq. This algorithm is called Natural.

Symbolic Sampling Space. An alternative sampler is one whose expected value, on input (ℋ, ℬ), is a number from which R(ℋ,ℬ) can be derived. We devise a slightly more complex sampling space, called symbolic, by exploiting ideas from [ 14 ]. Let 1, . . . , be an arbitrary order3In case ℋ = ∅, we let R(ℋ,ℬ) = 0.

4In a data-eficient randomized approximation scheme for EV[Sample] the output to be approximated is E[Sample((ℋ, ℬ))], and the running time must be polynomial in ||ℋ, ℬ|| (and 1/ and log(1/ )), as these are the parameters of a synopsis that depend on the database. ing (e.g., lexicographical) among the databases of ℋ. For each ∈ [], ℐℋ,ℬ is set of all ∈ db(ℬ) such that ⊆ . Our sampling space is defined as ℋ∙,ℬ = {︁(, ) | ∈ [] and ∈ ℐℋ,ℬ}︁.

Our second sampler, called SampleKL, performs the following: 1) sample (, ) ∈ ℋ∙,ℬ u.a.r., 2) if there is no < s.t. (, ) ∈ ℋ∙,ℬ, then output 1, otherwise output 0. We can prove that SampleKL enjoys (*) and that its expected value is /|ℋ∙,ℬ|, where is the numerator of R(ℋ,ℬ). Hence, we consider the algorithm KL, that constructs the (, Σ) -synopsis (ℋ, ℬ) of ̄, runs the algorithm MonteCarlo[SampleKL] with input (ℋ, ℬ), and multiplies its output by |ℋ∙,ℬ|/|db(ℬ)|. By Lemma 2, KL is an approximation scheme for RelativeFreq.

One can devise a slightly diferent sampler, called SampleKLM, that has a lower variance in general w.r.t. SampleKL. Using SampleKLM in place of SampleKL, as discussed above, we obtain the approximation scheme for RelativeFreq called KLM.

3.2. Union of Sets Approach

An approximation scheme, called self-adjusting coverage algorithm was presented in [ 14 ] for the union of sets problem, which takes a description of ≥ 1 sets 1, . . . , , and the output is | ⋃︀∈[] |. For space reasons, we do not present this algorithm, but only show how RelativeFreq reduces to this problem. We first construct the (Σ , )-synopsis of for ̄, (ℋ, ℬ). Then, since ⋃︀ ℐℋ,ℬ is the numerator of the ratio R(ℋ,ℬ), we approximate the value | ⋃︀ ℐℋ,ℬ| via the selfadjusting coverage algorithm of [ 14 ], by seeing (ℋ, ℬ) as the description of the sets ℐℋ,ℬ, for each . Then, dividing the result by |db(ℬ)| will give an approximation of R(ℋ,ℬ). This, together with Lemma 2, provides an approximation scheme for RelativeFreq, which we dub Cover.

4. The Benchmark

Implementation. Note that to compute the approximate relative frequency of each candidate tuple ̄, the corresponding synopsis must be computed first, regardless of the chosen algorithm. We show we can construct the set synΣ ,() of all pairs (̄, ), with the (, Σ) -synopsis of ̄ ∈ dom()|̄|, with R,Σ ,(̄) > 0, via a single SQL query, obtained by a careful rewriting of the original query . We call this initial precomputation of synΣ ,() the preprocessing step. For implementing the approximation schemes, we extended the framework of [ 16 ] of approximation algorithms for the number of satisfying assignments of DNF formulas. Experimental Setting. To efectively evaluate our algorithms, our test scenarios must expose how the running time of the approximation schemes is afected by key input parameters like the inconsistency of the database, and the number of joins in the query.

Data Generator. We generate databases using the dbgen tool of the TPC-H benchmark. Databases of varied size can be generated by providing a scale factor as input. Since the generated databases are consistent w.r.t. the underlying constraints we will later inject inconsistency via a noise generator that we developed.

Query-aware Noise Generator. General-purpose noise generators exist in the literature; see, e.g., [ 17 ]. However, all such tools are query-oblivious, i.e., do not take into account any query: if we generate noise by randomly adding facts to the database, considering only the primary keys, it is likely that we will not afect the evaluation of the query (and hence the synopses), as in general, databases are much larger than the actual synopses.

Given , Σ , (̄) , a percentage 0 < < 1 and an integer interval [, ], our noise generator constructs the set synΣ ,(), and for each (̄, (ℋ, ℬ)), randomly chooses ℓ = ⌈ · |ℬ|⌉ blocks 1, . . . , ℓ, and for each , adds to a random number ∈ [, ] of tuples having the same key value as the one of . These tuples are constructed by reusing existing tuples from , and by changing their key value. This ensures that the new tuples preserve the join patterns of . Query Generator. To generate our stress test queries we exploit a recent query generator [ 18 ], which we call static query generator (SQG) since it can control static query parameters, such as the number of joins, and the number of free variables (i.e., output variables). As we also want to precisely control the size of the synopsis, we also consider some dynamic query parameters.

Letting synΣ ,() = {(̄, (ℋ, ℬ))}∈[] for some ≥ 1, we consider the homomorphic size of w.r.t. defined as | ⋃︀

=1 ℋ|, which measures how large is the portion of that can afect any (, Σ) -synopsis in synΣ ,(). Since synopses in synΣ ,() can have diferent sizes, it is natural to consider the average size of a (Σ , )-synopsis in synΣ ,() as a key parameter, which is given by | ⋃︀=1 ℋ| . We normalize the above to a number in the interval (0, 1) by |synΣ ,()| considering its inverse. We call this number the balance of w.r.t. . The closer the balance to 1 (resp., 0) is, the smaller (resp., larger) the average size of a (Σ , )-synopsis is.

We developed a query generator, called dynamic, that modifies a query generated by the SQG so that it has a desired balance w.r.t. the given database .

Test Scenarios. For our test scenarios we consider the TPC-H schema, denoted SH, and the set Σ H of primary keys over SH coming with the TPC-H benchmark. We generated a large set of database-query pairs H as follows: (1) First, we generated a (consistent) database H over SH, using scale factor 1GB. The database contains roughly 9M tuples. (2) For each number of joins ∈ [ 5 ], we generated 5 base CQs , with ∈ [ 5 ], having joins, using SQG, producing a set of 25 CQs. Using our query-aware noise generator, for each ∈ , we generated 10 inconsistent databases [], using noise levels ∈ {0.1, 0.2, . . . , 1}, and the same block interval [ 2, 5 ]. (4) Finally, for each ∈ , and for each [], we generated 11 variations of , denoted [], having balance ∈ {0, 0.1, 0, 2, . . . , 1} w.r.t. [], where balance = 0 means the query [] is Boolean. H is then the set of pairs {([], []) | ∈ { },∈[ 5 ], ∈ {0.1, . . . , 1} and ∈ {0, 0.1, . . . , 1}}, containing 2750 database-query pairs.

We considered diferent scenarios (subsets of H) by fixing all parameters but one. Noise scenarios: The sets Noise[, ] of all pairs of H, where the balance level () and the number of joins () are fixed. Join scenarios: The sets Join[, ] of all pairs of H, where the noise level () and the balance level () are fixed. Balance scenarios: The sets Balance[, ] of all pairs of H, where the noise level () and the number of joins () are fixed.

Hardware and execution. For the experiments we used two Desktop PCs each with an Intel(R) Core(TM) i5-8500 CPU@3.00GHz processor, 16GB RAM, 500GB mechanical drive, running Xubuntu 19.04 64-bit. All databases are stored in a PostgreSQL 11.5 instance. The approximation schemes and the preprocessing step are implemented in C++ and SQL, respectively.

We fixed = 0.25 and = 0.1, i.e., 75% confidence and 10% error. We report the time required to execute each algorithm over the synopses of all output tuples, excluding the time of the preprocessing step since it is the same for all the approximation schemes. Each data point in a plot of Fig. 1 is the average runtime over all the CQs for that X-axis value; due to space constraints, here we report only some representative noise and balance scenarios (see Fig. 1).

5. Take-home Messages

Our analysis reveals a striking diference between Boolean and non-Boolean CQs. The Boolean Case. Here, Natural is the best performer, no matter the noise and the number of joins in the query, whereas Cover is the worst. Only in the case of CQs with many joins Cover is comparable to KL(M), but in any case, Natural is the way to go. This is mainly due to the fact that for Boolean queries, the (only) synopsis is very large in general, and thus the relative frequency is very high. Hence, since Natural directly estimates the value of the relative frequency via the natural sampling space, requires less samples to obtain a good estimate. The Non-Boolean Case. In this case, KLM is the way to go in almost all the scenarios, i.e., for any level of noise and for any level of (non-zero) balance of the query. Only for CQs with many joins, and high noise, KL is comparable to KLM. Nevertheless, KL is never going to outperform KLM in practice. The worst algorithms for non-Boolean CQs are Natural and Cover. They perform similarly for low levels of noise, balance and joins, but, in general, Natural is the slowest. The reson for this outcome is that for higher values of balance, the average size of a synopsis is low, which then implies that the relative frequency of the corresponding tuple is usually close to 0, hence, sampling from the symbolic space helps avoiding to perform a large number of samples like Natural does. Moreover, the low-variance sampler of KLM lets the algorithm find the optimal number of samples earlier than KL, on average.

Practical Applicability. In most of our experiments, the preprocessing step took less than 30 seconds. Furthermore, for modest scenarios, which is what we expect to face in practice, the running time of the best performing approximation scheme is in the order of seconds. We also considered larger databases, up to 120M tuples (15GBs), for which the overall running time of the preprocessing step is encouraging (considering the weak machines used): it is in the order of minutes, while the best approximation algorithm for each case always performs in the order of seconds. Thus, we believe applying approximate CQA in practice is not an unrealistic goal.

Acknowledgments

Part of Calautti’s and Console’s work was done while they were research associates at the University of Edinburgh. Console has been partially supported by MIUR under the PRIN 2017

References

[1] M. Arenas , L. E. Bertossi , J. Chomicki , Consistent query answers in inconsistent databases , in: PODS , 1999 , pp. 68 - 79 .

[2] M. Calautti , M. Console , A. Pieris , Counting database repairs under primary keys revisited , in: PODS , 2019 , pp. 104 - 118 .

[3] P. Koutris , J. Wijsen , Consistent query answering for primary keys in logspace , in: ICDT, 2019 , pp. 23 : 1 - 23 : 19 .

[4] B. ten Cate , G. Fontaine, P. G. Kolaitis , On the data complexity of consistent query answering , Theory Comput. Syst . 57 ( 2015 ) 843 - 891 .

[5] S. Greco , C. Molinaro , I. Trubitsyna , Computing approximate query answers over inconsistent knowledge bases , in: IJCAI , 2018 , pp. 1838 - 1846 .

[6] A. A. Dixit , P. G. Kolaitis , A sat-based system for consistent query answering , in: SAT , 2019 , pp. 117 - 135 .

[7] A. Fuxman , E. Fazli, R. J. Miller , Conquer: Eficient management of inconsistent databases , in: SIGMOD , 2005 , pp. 155 - 166 .

[8] S. Greco , C. Molinaro , Probabilistic query answering over inconsistent databases , Ann. Math. Artif. Intell. 64 ( 2012 ) 185 - 207 .

[9] M. Calautti , L. Libkin , A. Pieris , An operational approach to consistent query answering , in: PODS , 2018 , pp. 239 - 251 .

[10] D. Maslowski , J. Wijsen , A dichotomy in the complexity of counting database repairs , J. Comput. Syst. Sci . 79 ( 2013 ) 958 - 983 .

[11] N. Fiorentino , S. Greco , C. Molinaro , I. Trubitsyna , ACID: A system for computing approximate certain query answers over incomplete databases , in: SIGMOD , 2018 , pp. 1685 - 1688 .

[12] S. Greco , C. Molinaro , I. Trubitsyna , Approximation algorithms for querying incomplete databases , Inf. Syst . 86 ( 2019 ) 28 - 45 .

[13] M. Console , P. Guagliardo , L. Libkin , E. Toussaint, Coping with incomplete data: Recent advances , in: PODS , 2020 , pp. 33 - 47 .

[14] R. M. Karp , M. Luby , N. Madras , Monte-carlo approximation algorithms for enumeration problems , J. Algorithms 10 ( 1989 ) 429 - 448 .

[15] P. Dagum , R. M. Karp , M. Luby , S. M. Ross , An optimal algorithm for monte carlo estimation , SIAM J. Comput . 29 ( 2000 ) 1484 - 1496 .

[16] K. S. Meel , A. A. Shrotri , M. Y. Vardi , Not all FPRASs are equal: Demystifying FPRASs for DNF-counting , Constraints 24 ( 2019 ) 211 - 233 .

[17] P. C. Arocena , B. Glavic , G. Mecca, R. J. Miller , P. Papotti , D. Santoro , Messing up with BART: Error generation for evaluating data-cleaning algorithms , PVLDB 9 ( 2015 ) 36 - 47 .

[18] M. Benedikt , G. Konstantinidis, G. Mecca , B. Motik , P. Papotti , D. Santoro , E. Tsamoura, Benchmarking the chase , in: PODS , 2017 , pp. 37 - 52 .