=Paper= {{Paper |id=Vol-2994/paper21 |storemode=property |title=Benchmarking Approximate Consistent Query Answering (Discussion Paper) |pdfUrl=https://ceur-ws.org/Vol-2994/paper21.pdf |volume=Vol-2994 |authors=Marco Calautti,Marco Console,Andreas Pieris |dblpUrl=https://dblp.org/rec/conf/sebd/CalauttiCP21 }} ==Benchmarking Approximate Consistent Query Answering (Discussion Paper)== https://ceur-ws.org/Vol-2994/paper21.pdf
Benchmarking Approximate Consistent Query
Answering
(Discussion Paper)

Marco Calautti1 , Marco Console2 and Andreas Pieris3
1
  DISI, University of Trento, Italy
2
  Sapienza, University of Rome, Italy
3
  University of Edinburgh, UK

                                         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 difference 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-efficient 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 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)
                                       © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073       CEUR Workshop Proceedings (CEUR-WS.org)
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 algo-
rithms 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 random-
ized 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


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
    1
     An 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(𝐷)|𝑥̄| | 𝑄(𝑥
                                                                       ̄ ) → 𝐷}.
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
R𝐷,Σ,𝑄 (𝑡̄) = |{𝐷′ ∈ 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 polyno-
mial time in ||𝐷|| + ||𝑡̄||,2 1/𝜖 and log(1/𝛿), and produces a random variable 𝒜 such that
Pr (|𝒜 − R𝐷,Σ,𝑄 (𝑡̄)| ≤ 𝜖 · R𝐷,Σ,𝑄 (𝑡̄)) ≥ 1 − 𝛿.


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
   2
       As 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 ℬ. Fi-
nally, R(ℋ,ℬ) = |{𝐼 ∈ db(ℬ) | 𝐻 ⊆ 𝐼 for some 𝐻 ∈ ℋ}||db(ℬ)|.3
  We 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 ℋ = ∅.


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-efficient
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, other-
wise 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 sam-
pling space, called symbolic, by exploiting ideas from [14]. Let 𝐻1 , . . . , 𝐻𝑛 be an arbitrary order-
    3
    In case ℋ = ∅, we let R(ℋ,ℬ) = 0.
    4
    In a data-efficient 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 different 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 self-
                                                                                      𝑖

adjusting 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 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 gener-
ated 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,
                         | 𝑛𝑖=1 ℋ𝑖 |
which is given by                       . 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 different 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
             (a) Noise[0, 3]     (b) Noise[0.5, 3]   (c) Balance[0.2, 3]   (d) Balance[0.4, 3]
Figure 1: Noise and balance scenarios - Noise[balance, joins], and Balance[noise, joins]


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


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
project “HOPE” (prot. 2017MMJJRE), and by the EU under the H2020-EU.2.1.1 project TAILOR,
grant id. 952215. Pieris was supported by the EPSRC grant EP/S003800/1 “EQUID”.


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 incon-
     sistent 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: Efficient 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.