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 differs 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 SEBD 2021: The 29th Italian Symposium on Advanced Database Systems, September 5-9, 2021, Pizzo Calabro (VV), Italy marco.calautti@unitn (M. Calautti); console@diag.uniroma1.it (M. Console); apieris@inf.ed.ac.uk (A. Pieris)

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-efficient Approximations. Approximation algorithms have been crucial for tackling intractable problems in different areas of Data Management. Examples are in the context of approximating certain answers over incomplete databases, where different approximation algorithms have been devised and experimentally evaluated [11,12,13]. In the case of inconsistent databases, data-efficient 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 affected by key parameters of the input. 1

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 KeyR 𝐷,Σ,𝑄 (𝑡 ̄) = |{𝐷 ′ ∈ rep(𝐷, Σ) | 𝑡 ̄∈ 𝑄(𝐷 ′ )}|/|rep(𝐷, Σ)|.

Our main problem is:

PROBLEM : CQA INPUT :

A database 𝐷, a set Σ of primary keys, and a CQ 𝑄(𝑥 ̄). OUTPUT :

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 efficient 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.

Approximate CQA. A (data-efficient) 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 𝜖 > 0 and 0 < 𝛿 < 1, runs in polynomial time in ||𝐷|| + ||𝑡 ̄||, 2 1/𝜖 and log(1/𝛿), and produces a random variable 𝒜 such that

Pr (|𝒜 − R 𝐷,Σ,𝑄 (𝑡 ̄)| ≤ 𝜖 • R 𝐷,Σ,𝑄 (𝑡 ̄)) ≥ 1 − 𝛿.

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 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(ℬ)|. 3We show that the (Σ, 𝑄)-synopsis of a database 𝐷 for a tuple 𝑡 ̄can be efficiently 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 iff ℋ = ∅.

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-efficient randomized approximation scheme for computing E[Sample(ℋ, ℬ)]. 4By 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 order-ing (e.g., lexicographical) among the databases of ℋ. For each 𝑖 ∈ [𝑛], ℐ 𝑖 ℋ,ℬ is set of all 𝐼 ∈ db(ℬ) such that 𝐻 𝑖 ⊆ 𝐼. Our sampling space is defined as 𝒮

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.

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 effectively evaluate our algorithms, our test scenarios must expose how the running time of the approximation schemes is affected 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 affect 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 affect any (𝐷, Σ)-synopsis in syn Σ,𝑄 (𝐷). Since synopses in syn Σ,𝑄 (𝐷) can have different sizes, it is natural to consider the average size of a (Σ, 𝑄)-synopsis in syn Σ,𝑄 (𝐷) as a key parameter, which is given by

| ⋃︀ 𝑛 𝑖=1 ℋ 𝑖 | |syn Σ,𝑄 (𝐷)|

. We normalize the above to a number in the interval (0, 1) by 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 S H , and the set Σ H of primary keys over S H 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 S H , using scale factor 1GB. The database contains roughly 9M tuples. ( 2

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).

Take-home Messages

Our analysis reveals a striking difference 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.