A key task in the context of consistent query answering is to count the number of repairs that entail the query, with the ultimate goal being a precise data complexity classification. This has been achieved in the case of primary keys and self-join-free conjunctive queries (CQs) via an FP/♯P-complete dichotomy. We lift this result to the more general case of functional dependencies (FDs). Another important task in this context is whenever the counting problem in question is intractable, to classify it as approximable, i.e., the target value can be eficiently approximated with error guarantees via a fully polynomial-time randomized approximation scheme (FPRAS), or as inapproximable. Although for primary keys and CQs (even with self-joins) the problem is always approximable, we prove that this is not the case for FDs. We show, however, that the class of FDs with a left-hand side chain forms an island of approximability. We see these results, apart from being interesting in their own right, as crucial steps towards a complete classification of approximate counting of repairs in the case of FDs and self-join-free CQs.
A database is inconsistent if it does not satisfy its integrity 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) [
Example 1. Consider the relation name Employee(id, name, dept) that comes with the constraint
that the attribute id functionally determines name and dept. Consider also the database
consisting of the tuples: (1, Bob, HR), (1, Bob, IT), (2, Alice, IT), (2, Tim, IT). It is easy to see that
is inconsistent since we are uncertain about Bob’s department, and the name of the employee
with id 2. To devise a repair, we need to keep one tuple from each conflicting pair, which leads to a
maximal subset of that is consistent. Observe now that the query that asks whether employees 1
and 2 work in the same department is true only in two out of four repairs, and thus, not entailed.
Counting Repairs Entailing a Query. A key task in this context is to count the number of
repairs of an inconsistent database w.r.t. a set Σ of constraints that entail a given query ;
for clarity, we base our discussion on Boolean queries. Given a set Σ of constraints and a query
, the problem ♯Repairs(Σ , ) that takes as input a database , and asks for the number of
repairs of w.r.t. Σ that entail , can be tractable or intractable depending on the shape of Σ
and . This leads to the natural question whether we can establish a complete classification,
i.e., for every Σ and , classify ♯Repairs(Σ , ) as tractable or intractable by simply inspecting
Σ and . We already know from [
The closest known result related to Question 1 is for the problem ♯Repairs(Σ) , where Σ is
a set of FDs, that given a database , asks for the number of repairs of w.r.t. Σ (without
considering a query). In particular, we know from [
For a set Σ of primary keys, and a CQ (even with self-joins), ♯Repairs(Σ , ) is always
approximable [
We consider the disjoint countably infinite sets C and V of constants and variables, respectively. For > 0, let [] be the set {1, . . . , }, and for a finite set , let ♯ be the cardinality of . Relational Databases. A schema S is a finite set of relation names with associated arity; we write / to denote that has arity > 0. Each relation name / is associated with a tuple of distinct attribute names (1, . . . , ); we write att() for the set {1, . . . , }. A position of S is a pair (, ), where ∈ S and ∈ att(), that essentially identifies the attribute of . A atom over S is an expression of the form (1, . . . , ), where / ∈ S, and ∈ C ∪ V for each ∈ []. A fact is an atom mentioning only constants; we may say -atom/fact to indicate that the relation name is . For an atom = (1, . . . , ), with (1, . . . , ) being the tuple of attribute names of , we write [] for the term . A database over S is a finite set of facts over S. We write , for ∈ S, for the database {(¯) | (¯) ∈ }. The active domain of , denoted dom(), is the set of constants occurring in .
Functional Dependencies. A functional dependency (FD) over a schema S is an expression of the form : → , where / ∈ S and , ⊆ att(); we say -FD to indicate that the relation name is . We call a key if ∪ = att(). Given a set Σ of FDs over S, we write Σ , for ∈ S, for the set { ∈ Σ | is an -FD}. We call Σ a set of primary keys if it consists only of keys, and |Σ | ≤ 1 for each ∈ S. A database over S satisfies an FD over S, denoted |= , if, for every two -facts , ∈ the following holds: [] = [] for every ∈ implies [] = [] for every ∈ . We say that is consistent w.r.t. a set Σ of FDs, written |= Σ , if |= for every ∈ Σ ; otherwise, is inconsistent w.r.t. Σ . Two sets of FDs Σ , Σ ′ are equivalent if, for every database , |= Σ if |= Σ ′. Conjunctive Queries. A (Boolean) conjunctive query (CQ) over S is an expression of the form ∃¯1, . . . , ∃¯ 1(¯1) ∧ · · · ∧ (¯), where each (¯), for ∈ [], is an atom over S. With abuse of notation we may treat as the set of its atoms. The query is a self-join-free CQ (SJFCQ) if it mentions every relation name of S at most once. Let var() and const() be the set of variables and constants in , respectively. A homomorphism from to a database is a function ℎ : var() ∪ const() → dom(), which is the identity over C, such that (ℎ(¯)) ∈ for ∈ []. We say that entails , and write |= if there exists a homomorphism from to . We point out that in this paper we are only dealing with Boolean queries, but all the presented results can be generalized to non-Boolean CQs. Database Repairs. Given a database and a set Σ of FDs, both over a schema S, a repair of w.r.t. Σ is a maximal subset ′ of such that ′ |= Σ . Let repΣ() be the set of repairs of w.r.t Σ . Given a CQ over S, we write repΣ,() for {′ ∈ repΣ() | ′ |= }. The following is a useful observation that we will exploit later in the paper: Lemma 2. Consider a database , a set Σ of FDs, and a Boolean SJFCQ . We can compute in polynomial time a database ′ such that ♯repΣ() = ♯repΣ,(′).
Problem Definition. For each set Σ of FDs and CQ , we focus on the problem ♯Repairs(Σ , ), which takes as input a database , and asks for the number ♯repΣ,(). The goal is to classify it as tractable (place it in FP) or as intractable (show that is ♯P-complete).
Another important task is whenever ♯Repairs(Σ , ) is intractable to classify it as
approximable via a so-called fully polynomial-time randomized approximation scheme (FPRAS, for
short), or as inapproximable. Formally, an FPRAS for ♯Repairs(Σ , ) is a randomized algorithm
A that takes as input a database , and numbers > 0 and 0 < < 1, runs in
polynomial time in ||||, 1/ and log(1/ ), and produces a random variable A(, , ) such that
Pr (︀ |A(, , ) − ♯repΣ,()| ≤ · ♯repΣ,())︀ ≥ 1 − .
LHS Chain FDs. Consider a set Σ of FDs over S, and a relation name ∈ S. We say that
Σ has a left-hand side chain (LHS chain) if the FDs of Σ can be arranged in a sequence
: 1 → 1, . . . , : → such that 1 ⊆ 2 ⊆ · · · ⊆ [
The goal of this section is to discuss the key ideas behind our main result on exact counting: Theorem 4. For a set Σ of FDs, and an SJFCQ , ♯Repairs(Σ , ) is either in FP or ♯P-complete, and we can decide in polynomial time in ||Σ || + |||| which of the two cases hold.
We observe that for every set Σ of FDs, and an SJFCQ , ♯Repairs(Σ , ) is in ♯P: simply guess
(in polynomial time) a subset ′ of the given database , and verify (again in polynomial time)
that ′ is a repair of w.r.t. Σ that entails . We also note that the non-existence of an LHS
chain (up to equivalence) is a preliminary boundary for the hard side of the target dichotomy,
regardless of the CQ. We know from [
From Proposition 5, and the fact that checking whether a set Σ of FDs has an LHS chain (up
to equivalence) is feasible in polynomial time [
In the rest, we give some hints on the proof of Theorem 6; we first need some new notions.
Canonical Covers. If Σ has an LHS chain (up to equivalence), we know that it has a single
canonical cover1 Σ ′, and Σ ′ has an LHS chain [
Primary FDs and Positions. Consider now an SJFCQ . Let be the -atom in , and let Λ = : 1 → 1, . . . , : → be the LHS chain of Σ . We call an FD : → , for some ∈ [], the primary FD of Σ w.r.t. if ∪ contains an attribute such that at position (, ) in we have a variable, whereas at each position of {(, ) | ∈ ∪ for < } in we have a constant. Note that there is no guarantee that the primary FD of Σ w.r.t. exists. If the primary FD : → of Σ w.r.t. exists, for some ∈ [], then the primarylhs positions of (w.r.t. Σ ) are the positions {(, ) | ∈ }, while the non-primary-lhs positions of (w.r.t. Σ ) are the positions {(, ) | ∈ att() ∖ }. We further call the sequence of FDs : 1 → 1, . . . , : − 1 → − 1 the primary prefix of Σ w.r.t. . If the primary FD of Σ w.r.t. does not exist, then, by convention, the primary-lhs positions of are the positions {(, ) | ∈ att()}, i.e., all the positions in are primary-lhs, which in turn implies that has no non-primary-lhs positions. Moreover, the primary prefix of Σ w.r.t. is defined as the sequence Λ itself. We denote by pvarΣ( ) the set of variables occurring in at primary-lhs positions of .
Query Complex Part. A variable ∈ var() is a liaison variable (of ) if it occurs more than once in . The complex part of w.r.t. Σ , denoted compΣ(), is the set of atoms of in which we have a constant or a liaison variable at a non-primary-lhs position (, ), with being the -atom of , such that, for every FD : → in the primary prefix of Σ w.r.t. , ̸∈ ∪ . We observe that when compΣ() = ∅, the number of repairs of w.r.t. Σ that entail coincides with the number of repairs (without any query) of the subset cΣo,nf of obtained after removing the facts of that are somehow in a conflict with , and thus, they cannot appear in a repair that entails . Since cΣo,nf can be computed in polynomial time in ||||, by Proposition 3 we obtain the following: Proposition 7. Given a database , a set Σ of FDs with an LHS chain, and an SJFCQ with compΣ() = ∅, it holds that rfreq,Σ() is computable in polynomial time in ||||.
We start by defining some properties that, when satisfied by a SJFCQ, allow to restate its relative frequency in terms of the relative frequency of simpler queries.
We write 1 ⊎ 2 for the CQ consisting of the atoms of two non-empty CQs 1, 2 that share no atoms and variables, i.e., 1 ∩ 2 = ∅ and var(1) ∩ var(2) = ∅. We also write ↦→, where ∈ var() and ∈ C, for the CQ obtained from after replacing with . Theorem 8. Consider a set Σ of FDs with an LHS chain, and a SJFCQ . For every database , the following hold: 1. If = 1 ⊎ 2, then rfreq,Σ() = rfreq,Σ(1) × rfreq,Σ(2). 2. If compΣ() ̸= ∅, and there exists a variable ∈ var() such that ∈ pvarΣ( ) for every ∈ compΣ(), then there is * ⊆
, computable in polynomial time in ||||, such that ⎛ ⎝1 −
∏︁ ∈dom()
︀( 1 rfreq,Σ() = − rfreq* ,Σ(↦→) ⎠ × ︀) ⎞ ♯repΣ ︁(
∖ cΣo,nf)︁ ♯repΣ() . 3. If compΣ() ̸= ∅, and there exists an atom = (¯) ∈ compΣ() such that pvarΣ( ) = ∅, and a variable occurs in at a position of {(, ) | ∈ }, where : → is the primary FD of Σ w.r.t. , then rfreq,Σ() = ∑︀ ∈dom() rfreq,Σ(↦→).
Item (1) of Theorem 8 is straightforward, and implies that when = 1 ⊎ 2, one can
compute the relative frequency of in polynomial time, if the same can be done for the relative
frequencies of 1 and 2. Items (2) and (3) are much more involved, and we refer the reader
to the full version of the paper [
For a set Σ of FDs with an LHS chain and an SJFCQ , we say that is Σ -safe if either its complex part is empty, i.e., compΣ() = ∅, or after recursively applying the conditions of items (1)-(3) of Theorem 8 to , we are only left with queries having an empty complex part.2 By definition of Σ -safe queries, and by Proposition 7 and Theorem 8, we obtain the following: Theorem 9. Consider a set Σ of FDs with an LHS chain, and an SJFCQ . If is Σ -safe, then RelFreq(Σ , ) is in FP.
Interestingly, safety exhausts the tractable side of the dichotomy stated in Theorem 6. That establishes the second part of Theorem 6. is, if is not Σ -safe, then RelFreq(Σ , ) is ♯P-hard, as we discuss in the next section. Let us stress that checking whether is Σ -safe is feasible in polynomial time in ||Σ || + ||||, which
We conclude this section by briefly discussing how the intractable side of the dichotomy stated
in Theorem 6 is obtained. We know from [
2We remark that for items (2) and (3), it is enough to recursively apply the conditions of Theorem 8 to ↦→ for
Theorem 10 is shown in two main steps. We first prove that there exists a set Σ * of FDs, and
an SJFCQ * such that RelFreq(Σ * , * ) can be reduced to RelFreq(Σ , ) by means of a set of
rewriting rules that extend the ones of [
We now briefly discuss our results on approximate counting. The main contribution of this
section is the following theorem; BPP is the class of decision problems that are eficiently
solvable via a randomized algorithm with a bounded two-sided error [
Theorem 11. For every set Σ of FDs with an LHS chain (up to equivalence), and a CQ ,
♯Repairs(Σ , ) admits an FPRAS. Moreover, for Σ ℎ = { : 1 → 2, : 3 → 4}, where
att() = { | ∈ [
To prove the approximability result we observe that ♯Repairs(Σ , ) can be seen as an
instantiation of the so-called union of sets problem [
From the above discussion, and the results of [
The proof of the inapproximability of ♯Repairs(Σ ℎ, ), for every SJFCQ , employs a
socalled gap preserving reduction from the promise problem Gap3SAT , for some fixed ∈ (0, 18 ),
i.e., the problem that given a Boolean formula in 3CNF, asks whether is satisfiable. The
promise is that if is unsatisfiable, then every truth assignment makes at most 78 + of the
clauses of true. For every ∈ (0, 81 ), Gap3SAT is NP-complete [
For a fixed ∈ (0, 18 ), the reduction maps each formula to a database db( ) such that the following holds: for any yes instance of Gap3SAT , and any no instance of Gap3SAT , the “gap” (i.e., the ratio) between the numbers ♯repΣℎ,(db( )) and ♯repΣℎ,(db( )) is so large that an FPRAS for ♯Repairs(Σ ℎ, ) could be used, by employing a small enough error , to distinguish between yes and no instances of Gap3SAT with high probability, and thus, placing the NP-complete problem Gap3SAT in BPP.
The Dificulty Underlying a Dichotomy. Despite our eforts, we could not get a complete
approximability/inapproximability classification. However, in the full version of the paper [
The obvious problems that remain open are the following: (1) lift the dichotomy of Theorem 4 for FDs and self-join-free CQs to arbitrary CQs with self-joins, and (2) establish an approximability/inapproximability dichotomy for FDs and SJFCQs.
We point out that approximate versions of CQA have already been considered, both in
the database and ontological setting. In the database setting, to the best of our knowledge
[