# Consistent Query Answering for Primary Keys and Conjunctive Queries with
Counting

Aziz Amezian El Khalfioui Research fellow FNRS. University of Mons, Mons,
Belgium
{aziz.amezianelkhalfioui<EMAIL_ADDRESS>Jef Wijsen  University of
Mons, Mons, Belgium
{aziz.amezianelkhalfioui<EMAIL_ADDRESS>
###### Abstract

The problem of consistent query answering for primary keys and self-join-free
conjunctive queries has been intensively studied in recent years and is by now
well understood. In this paper, we study an extension of this problem with
counting. The queries we consider count how many times each value occurs in a
designated (possibly composite) column of an answer to a full conjunctive
query. In a setting of database repairs, we adopt the semantics of [Arenas et
al., ICDT 2001] which computes tight lower and upper bounds on these counts,
where the bounds are taken over all repairs. Ariel Fuxman defined in his PhD
thesis a syntactic class of queries, called $\mathsf{Cforest}$, for which this
computation can be done by executing two first-order queries (one for lower
bounds, and one for upper bounds) followed by simple counting steps. We use
the term “parsimonious counting” for this computation. A natural question is
whether $\mathsf{Cforest}$ contains all self-join-free conjunctive queries
that admit parsimonious counting. We answer this question negatively. We
define a new syntactic class of queries, called $\mathsf{Cparsimony}$, and
prove that it contains all (and only) self-join-free conjunctive queries that
admit parsimonious counting.

##  1 Introduction

The problem of consistent query answering (CQA) [3, 5, 6, 38] with respect to
primary keys is by now well understood for self-join-free conjunctive queries:
a dichotomy between tractable and intractable queries has been established,
and it is known which queries have a consistent first-order rewriting [29,
32]. It remains a largely open question to extend these complexity results to
queries with aggregation. In this paper, we look at a simple form of
aggregation: counting the number of times each (possibly composite) value
occurs in the answer to a conjunctive query. Although this problem has been
studied since the early years of CQA [19], a fine-grained characterization of
its complexity remains open.

Formally, let $q$ be a full (i.e., quantifier-free) self-join-free conjunctive
query. We define a counting query as follows. We designate a tuple $\vec{z}$
of distinct variables of $q$, called the _grouping variables_ , and let
$\vec{w}$ be a tuple of the variables in $q$ that are not in $\vec{z}$. The
variables of $q$, which are all free, are made explicit by denoting $q$ as
$q(\vec{z},\vec{w})$. We are interested in a query that, on a given database
instance $\mathbf{db}$, returns all tuples $(\vec{c},i)$ with $\vec{c}$ a
tuple of constants, of the same arity as $\vec{z}$, and with $i$ a positive
integer that is the number of distinct tuples $\vec{d}$, of the same arity as
$\vec{w}$, satisfying $(\vec{c},\vec{d})\in q(\mathbf{db})$. This counting
query will be denoted ${\mathbf{cnt}}({q},{\vec{z}})$.

For example, consider the database schema of Fig. 1, which is intended to
store the unique gender and department of each employee, and the unique
building of each department. Ignore for now that the database instance of Fig.
1 is inconsistent (as it stores two departments for Anny, and two buildings
for IT). Let $q_{0}(x,y,z)=E(x,\textnormal{`{F}'},y)\land D(y,z)$, where
$x,y,z$ are variables and ‘F’ denotes a constant. Then, on a consistent
database instance, ${\mathbf{cnt}}({q_{0}},{z})$ would return the number of
female employees working in each building. In SQL,
${\mathbf{cnt}}({q_{0}},{z})$ can be encoded as follows:

>
>     SELECT   Building, COUNT(*) AS CNT
>     FROM     E, D
>     WHERE    E.Dept = D.Dept AND Gender = ’F’
>     GROUP BY Building
>

On the database instance of Fig. 1, this query will return $(A,4)$ and
$(B,3)$. These answers are however not meaningful because they suffer from
double-counting due to inconsistencies. We describe next a more meaningful
semantics that was introduced in [3].

First, following [2], we define a _repair_ of a database instance as a maximal
subinstance that satisfies all primary-key constraints. In this paper, we
consider no other constraints than primary keys. Then, following the approach
of [3], more meaningful answers are obtained by returning, for every value
$\vec{c}$ for the grouping variables $\vec{z}$, tight lower and upper bounds
on the corresponding counts over all repairs. This new query is denoted by
${\mathbf{cqacnt}}({q},{\vec{z}})$. Thus, an answer $(\vec{c},[m,n])$ to this
new query means that on every repair, our original query
${\mathbf{cnt}}({q},{\vec{z}})$ returns a tuple $(\vec{c},i)$ with $m\leq
i\leq n$, and, moreover, these bounds $m$ and $n$ are tight. By tight, we mean
that for every $j\in\\{m,n\\}$, there is a repair on which
${\mathbf{cnt}}({q},{\vec{z}})$ returns $(\vec{c},j)$.

For example, the database instance of Fig. 1 has four repairs, because there
are two choices for Anny’s department, and two choices for the building of the
IT department. Note that in Fig. 1, _blocks_ of conflicting tuples are
separated by dashed lines. The query ${\mathbf{cnt}}({q_{0}},{z})$ returns
different answers on each repair: there are two repairs where the answer is
$\\{(A,3),(B,1)\\}$; there is one repair where the answer is
$\\{(A,1),(B,3)\\}$; and there is one repair where the answer is
$\\{(A,2),(B,2)\\}$. The latter set of answers, for example, is obtained in
the repair that assigns Anny to department HR, and IT to building B. The query
${\mathbf{cqacnt}}({q_{0}},{z})$ would thus return
$\\{(A,[1,3]),(B,[1,3])\\}$.

In this paper, we are concerned about the complexity of computing
${\mathbf{cqacnt}}({q},{\vec{z}})$. In general, there exist self-join-free
conjunctive queries $q$ such that, for some choice of the grouping variables
$\vec{z}$, ${\mathbf{cqacnt}}({q},{\vec{z}})$ cannot be solved in polynomial
time (under standard complexity assumptions). This follows from earlier
research showing that there are self-join-free conjunctive queries
$q^{\prime}(\vec{z})$ for which the following problem is $\coNP$-complete:
given $\vec{c}$ and $\mathbf{db}$, determine whether $q^{\prime}(\vec{c})$ is
true in every repair of $\mathbf{db}$. The latter problem obviously reduces to
counting: $q^{\prime}(\vec{c})$ is true in every repair of $\mathbf{db}$ if
and only if ${\mathbf{cqacnt}}({q},{\vec{z}})$ returns $(\vec{c},[m,n])$ on
$\mathbf{db}$ for some $m\geq 1$, where $q$ is the full query obtained from
$q^{\prime}$ by dropping quantification.

In his PhD thesis [19], Fuxman showed that for some $q$ and $\vec{z}$, the
answer to ${\mathbf{cqacnt}}({q},{\vec{z}})$ can be computed by executing
first-order queries followed by simple counting steps. To illustrate his
approach, consider the following query in SQL:

>
>     SELECT   Building, COUNT(DISTINCT Emp) AS CNT
>     FROM     E, D
>     WHERE    E.Dept = D.Dept AND Gender = ’F’
>     GROUP BY Building
>

On our example database of Fig. 1, this query returns $\\{(A,3),(B,3)\\}$. We
observe that the returned counts match the upper bounds previously found for
${\mathbf{cqacnt}}({q_{0}},{z})$. Importantly, it can be shown that this is
not by accident: on _every_ database instance, the latter SQL query will
return the correct upper bounds for ${\mathbf{cqacnt}}({q_{0}},{z})$. Note
that the latter query uses COUNT(DISTINCT Emp), which means that duplicates
are removed, which is a standard practice in relational algebra.

We now explain how to obtain the lower bounds for our example query. To this
end, consider the following query:

>
>     SELECT Building, Emp
>     FROM   E, D
>     WHERE  E.Dept = D.Dept AND Gender = ’F’
>

Following [2], we define the _consistent answer_ to such a query as the
intersection of the query answers on all repairs. For our example database,
the consistent answer is the following table, which we call $C$:

> $C$ | $\mathit{Emp}$ |  $\mathit{Building}$
> ---|---|---
> | Suzy | A
> | Lucy | B

Note that Anny does not occur in the consistent answer, because (Anny, A) is
false in some repair, and so is (Anny, B). From [29], it follows that
computing the consistent answers to the latter SQL query is in $\FO$ (i.e.,
the class of problems that can be solved by a first-order query), using a
technique known as _consistent first-order rewriting_. The lower bounds
$\\{(A,1),(B,1)\\}$ are now found by executing the following query on $C$
(and, again, this is not by accident):

>
>     SELECT   Building, COUNT(DISTINCT Emp) AS CNT
>     FROM     C
>     GROUP BY Building
>

Since $C$ can be expressed in SQL, we can actually construct a single SQL
query that computes the lower bounds in ${\mathbf{cqacnt}}({q_{0}},{z})$.

In general, if $q(\vec{z},\vec{w})$ is a full self-join-free conjunctive query
for which ${\mathbf{cqacnt}}({q},{\vec{z}})$ can be computed as previously
described, then we will say that the query obtained from $q$ by existentially
binding the variables in $\vec{w}$ (i.e., by binding the variables that are
not grouping variables) admits _parsimonious counting_. Thus, our example
showed that $\exists x\exists y\,E(x,\textnormal{`{F}'},y)\land D(y,z)$ admits
parsimonious counting. A formal definition of parsimonious counting will be
given later on (Definition 4.3). In this introduction, we content ourselves by
saying that parsimonious counting, if possible, computes
${\mathbf{cqacnt}}({q},{\vec{z}})$ by executing two first-order queries (one
for lower bounds, and one for upper bounds), followed by simple counting
steps.

| $E$ | $\underline{\mathit{Emp}}$ | $\mathit{Gender}$ |  $\mathit{Dept}$
---|---|---|---
| Suzy | F | HR
2-4 | Anny | F | HR
| Anny | F | IT
2-4 | Dolores | F | IT
2-4 | Lucy | F | MIS
| $D$ | $\underline{\mathit{Dept}}$ |  $\mathit{Building}$
---|---|---
| HR | A
2-3 | IT | A
| IT | B
2-3 | MIS | B
Figure 1: Example database. Primary keys are underlined.

The main contribution of our paper can now be described. In his doctoral
dissertation [19], Fuxman defined a class of self-join-free conjunctive
queries, called $\mathsf{Cforest}$, and showed the following.

######  Theorem 1.1 ([19]).

Every query in $\mathsf{Cforest}$ admits parsimonious counting.

The class $\mathsf{Cforest}$ has been used in several studies on consistent
query answering, because of its good computational properties. It was an open
question whether $\mathsf{Cforest}$ contains _all_ self-join-free conjunctive
queries that admit parsimonious counting. We will answer this question
negatively in Section 8. More fundamentally, we introduce a new syntactic
class, called $\mathsf{Cparsimony}$, which includes $\mathsf{Cforest}$ and
contains _all_ (and only) self-join-free conjunctive queries that admit
parsimonious counting. That is, we prove the following theorem.

######  Theorem 1.2 (Main theorem).

For every self-join-free conjunctive query $q$, it holds that $q$ admits
parsimonious counting if and only if $q$ is in $\mathsf{Cparsimony}$.

Moreover, a new and simpler proof for Theorem 1.1 will follow in Section 8.

The remainder of this paper is organized as follows. Section 2 discusses
related work. Section 3 introduces preliminary constructs and notations.
Section 4 introduces the semantic notion of parsimonious counting. Section 5
introduces our new syntactic class of queries, called $\mathsf{Cparsimony}$,
which restricts self-join-free conjunctive queries. Section 6 shows that every
query in $\mathsf{Cparsimony}$ admits parsimonious counting, and Section 7
shows that $\mathsf{Cparsimony}$ contains every self-join-free conjunctive
query that admits parsimonious counting. Section 8 shows that
$\mathsf{Cforest}$ is strictly included in $\mathsf{Cparsimony}$, and provides
a new proof for Theorem 1.1. Section 9 concludes the paper. Several helping
lemmas and proofs are in the appendix.

##  2 Related Work

Consistent query answering (CQA) started by a seminal paper in 1999 co-
authored by Arenas, Bertossi, and Chomicki [2], who introduced the notions of
repair and consistent answer. Two years later, the same authors introduced the
_range semantics_ (with lower and upper bounds) for queries with aggregation
[3, 4][5, Chapter 5], which has been commonly adopted ever since. In
particular, it was adopted in the PhD thesis [19] of Fuxman, who provided
Theorem 1.1 (albeit using different terminology) and its proof, and used this
result in the implementation of the ConQuer system [20]. ConQuer aims at
computations in first-order logic with counting (coined “parsimonious
counting” in the current paper), which can be encoded in SQL. This is
different from AggCAvSAT [16], a recent system by Dixit and Kolaitis, which
uses powerful SAT solvers for computing range semantics, and thus can solve
queries that are beyond the computational power of ConQuer. Aggregation
queries were also studied in the context of CQA in [7].

Consistent query answering for self-join-free conjunctive queries $q$ and
primary keys has been intensively studied. Its decision variant, which was
coined $\mathsf{CERTAINTY}({q})$ in 2010 [36], asks whether a Boolean query
$q$ is true in every repair of a given database instance. A systematic study
of its complexity for self-join-free conjunctive queries had started already
in 2005 [22], and was eventually solved in two journal articles by Koutris and
Wijsen [29, 32], as follows: for every self-join-free Boolean conjunctive
query $q$, $\mathsf{CERTAINTY}({q})$ is either in $\FO$, $\L$-complete, or
$\coNP$-complete, and it is decidable, given $q$, which case applies. This
complexity classification extends to non-Boolean queries by treating free
variables as constants. Other extensions beyond this trichotomy deal with
foreign keys [24], more than one key per relation [31], negated atoms [30], or
restricted self-joins [28]. For unions of conjunctive queries $q$, Fontaine
[18] established interesting relationships between $\mathsf{CERTAINTY}({q})$
and Bulatov’s dichotomy theorem for conservative CSP [8].

The counting variant of $\mathsf{CERTAINTY}({q})$, denoted
$\sharp\mathsf{CERTAINTY}({q})$, asks to count the number of repairs that
satisfy some Boolean query $q$. This counting problem is fundamentally
different from the range semantics in the current paper. For self-join-free
conjunctive queries, $\sharp\mathsf{CERTAINTY}({q})$ exhibits a dichotomy
between $\FP$ and $\sharp\P$-complete under polynomial-time Turing reductions
[33]. This dichotomy has been shown to extend to queries with self-joins if
primary keys are singletons [34], and to functional dependencies [12].
Calautti, Console, and Pieris present in [9] a complexity analysis of these
counting problems under weaker reductions, in particular, under many-one
logspace reductions. The same authors have conducted an experimental
evaluation of randomized approximation schemes for approximating the
percentage of repairs that satisfy a given query [10]. Other approaches to
making CQA more meaningful and/or tractable include operational repairs [11,
13] and preferred repairs [26, 35].

Recent overviews of two decades of theoretical research in CQA are [6, 38]. It
is worthwhile to note that theoretical research in $\mathsf{CERTAINTY}({q})$
has stimulated implementations and experiments in prototype systems [21, 20,
27, 15, 25, 17].

##  3 Preliminaries

We assume that every relation name $R$ is associated with an _arity_ , which
is a positive integer. We assume that all _primary-key positions_ precede all
_non-primary-key positions_. We say that $R$ has _signature_ $[{n},{k}]$ if
$R$ has arity $n$ and primary-key positions $1,\dots,k$.

If $R$ has signature $[{n},{k}]$ and $s_{1},\dots,s_{n}$ are variables or
constants, then $R(s_{1},\dots,s_{n})$ is an _$R$ -atom_ (or simply _atom_),
which will often be denoted as
$R(\underline{s_{1},\dots,s_{k}},s_{k+1},\dots,s_{n})$ to distinguish between
primary-key and non-primary-key positions. Two atoms
$R_{1}(\underline{\vec{s}_{1}},\vec{t}_{1})$ and
$R_{2}(\underline{\vec{s}_{2}},\vec{t}_{2})$ are said to be _key-equal_ if
$R_{1}=R_{2}$ and $\vec{s}_{1}=\vec{s}_{2}$. A _fact_ is an atom in which no
variable occurs. A _database instance_ (or simply _database_) is a finite set
of facts. A database instance $\mathbf{db}$ is _consistent_ if it does not
contain two distinct key-equal facts. A _repair_ of $\mathbf{db}$ is a
$\subseteq$-maximal consistent subset of $\mathbf{db}$.

If $\vec{s}$ is a tuple of variables or constants, then $|{\vec{s}}|$ denotes
the arity of $\vec{s}$, and ${\mathsf{vars}}(\vec{s})$ denotes the set of
variables occurring in $\vec{s}$. By an abuse of notation, if we use a tuple
$\vec{z}$ of variables at places where a set of variables is expected, we mean
${\mathsf{vars}}(\vec{z})$. For an atom $F=R(\underline{\vec{s}},\vec{t})$, we
define ${\mathsf{Key}}(F)\vcentcolon={\mathsf{vars}}(\vec{s})$,
${\mathsf{notKey}}(F)\vcentcolon={\mathsf{vars}}(\vec{t})\setminus{\mathsf{vars}}(\vec{s})$,
and
${\mathsf{vars}}(F)\vcentcolon={\mathsf{vars}}(\vec{s})\cup{\mathsf{vars}}(\vec{t})$.
For example, if $F=R(\underline{c,x,x,y},y,z,c)$, then
${\mathsf{Key}}(F)=\\{x,y\\}$ and ${\mathsf{notKey}}(F)=\\{z\\}$, where $c$ is
a constant.

Conjunctive Queries. A conjunctive query $q$ is a first-order formula of the
form:

$\exists\vec{w}\left({R_{1}(\underline{\vec{x}_{1}},\vec{y}_{1})\land\dotsm\land
R_{n}(\underline{\vec{x}_{n}},\vec{y}_{n})}\right),$ (1)

where the variables of $\vec{w}$ are _bound_ , and the other variables are
_free_. Such a query is also denoted by $q(\vec{z})$ with $\vec{z}$ a tuple
composed of the free variables. We write ${\mathsf{vars}}(q)$ for the set of
variables that occur in $q$, and can assume
${\mathsf{vars}}(q)={\mathsf{vars}}(\vec{w})\cup{\mathsf{vars}}(\vec{z})$
without loss of generality. We say that $q$ is _full_ if all variables of
${\mathsf{vars}}(q)$ are free. We say that $q$ is _self-join-free_ if $i\neq
j$ implies $R_{i}\neq R_{j}$. The quantifier-free part
$R_{1}(\underline{\vec{x}_{1}},\vec{y}_{1})\land\dotsm\land
R_{n}(\underline{\vec{x}_{n}},\vec{y}_{n})$ of $q$ is denoted
${\mathsf{body}}(q)$. By slightly overloading notation, we also use
${\mathsf{body}}(q)$ for the set
$\\{R_{1}(\underline{\vec{x}_{1}},\vec{y}_{1}),\ldots,R_{n}(\underline{\vec{x}_{n}},\vec{y}_{n})\\}$.
We write ${\mathsf{free}}(q)$ for the set of free variables in $q$.

If a self-join-free conjunctive query $q$ is understood, and we use a relation
name $R$ at places where an atom is expected, then we mean the unique $R$-atom
of $q$. If $\vec{c}$ is a tuple of constants of arity $|{\vec{z}}|$ and
$\mathbf{db}$ a database instance, then $\mathbf{db}\models q(\vec{c})$
denotes that $q(\vec{c})$ is true in $\mathbf{db}$ using standard first-order
semantics. If $\mathbf{db}\models q(\vec{c})$, we also write $\vec{c}\in
q(\mathbf{db})$, and we say that $\vec{c}$ is an _answer_ to $q$ on
$\mathbf{db}$.

We now introduce operators for turning bound variables into free variables, or
vice versa, and for instantiating free variables.

Making bound variables free.

Let $q$ be a conjunctive query with ${\mathsf{free}}(q)=\vec{z}$. Let
$\vec{x}$ be a tuple of (not necessarily all) bound variables in $q$ (hence
$\vec{x}\cap\vec{z}=\emptyset$). We write $\nexists{\vec{x}}\left[{q}\right]$
for the conjunctive query $q^{\prime}$ such that
${\mathsf{free}}(q^{\prime})=\vec{z}\cup\vec{x}$ and
${\mathsf{body}}(q^{\prime})={\mathsf{body}}(q)$. Informally,
$\nexists{\vec{x}}\left[{q}\right]$ is obtained from $q$ by omitting the
quantification $\exists\vec{x}$. For example, if $q(z)=\exists x\exists
y\,R(x,y)\land R(y,z)$, then $\nexists{x}\left[{q}\right]=\exists
y\,R(x,y)\land R(y,z)$.

Binding free variables.

Let $q$ be a conjunctive query, and $\vec{x}$ a tuple of (not necessarily all)
free variables of $q$. Then $\exists{\vec{x}}\left[{q}\right]$ denotes the
query with the same body as $q$, but whose set of free variables is
${\mathsf{free}}(q)\setminus\vec{x}$.

Instantiating free variables.

Let $q$ be a conjunctive query, and $\vec{z}$ a tuple of distinct free
variables of $q$. Let $\vec{c}$ be a tuple of constants of arity
$|{\vec{z}}|$. Then ${q}_{[{\vec{z}}\rightarrow{\vec{c}}]}$ is the query
obtained from $q$ by replacing, for every $i\in\\{1,2,\ldots,|{\vec{z}}|\\}$,
each occurrence of the $i$th variable in $\vec{z}$ by the $i$th constant in
$\vec{c}$.

Consistent Query Answering. Let $q(\vec{z})$ be a conjunctive query. We write
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$ if for every repair
$\mathbf{r}$ of $\mathbf{db}$, we have $\mathbf{r}\models q(\vec{c})$. If
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$, we also say that
$\vec{c}$ is a _consistent answer_ to $q$ on $\mathbf{db}$. A _consistent
first-order rewriting_ of $q(\vec{z})$ is a first-order formula
$\varphi(\vec{z})$ such that for every database instance $\mathbf{db}$ and
every tuple $\vec{c}$ of constants of arity $|{\vec{z}}|$, we have
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$ if and only if
$\mathbf{db}\models\varphi(\vec{c})$. Note incidentally that the set of
integrity constraints is always implicitly understood to be the primary keys
associated with the relation names that occur in the query.

Query Graph. The _query graph_ of a conjunctive query $q(\vec{z})$ is an
undirected graph whose vertices are the bound variables of $q$. There is an
edge between $x$ and $y$ if $x\neq y$ and $x,y$ occur together in some atom of
${\mathsf{body}}(q)$.

Attack Graph. The following is a straightforward extension of attack graphs
[29] to deal with free variables.

Let $q(\vec{z})$ be a self-join-free conjunctive query. If $S$ is a subset of
${\mathsf{body}}(q)$, then $q\setminus S$ denotes the query obtained from $q$
by removing from $q$ all atoms in $S$. Every variable of $q\setminus S$ that
is free in $q$ remains free in $q\setminus S$; and every variable of
$q\setminus S$ that is bound in $q$ remains bound in $q\setminus S$.

We define $\mathcal{K}(q)$ as the set of functional dependencies that contains
$\emptyset\rightarrow{\mathsf{free}}(q)$ and contains, for every atom $F$ in
$q$, the functional dependency
${\mathsf{Key}}(F)\rightarrow{\mathsf{vars}}(F)$. Note that since
$\mathcal{K}(q)$ contains $\emptyset\rightarrow{\mathsf{free}}(q)$, we have
that $\mathcal{K}(q)\models\emptyset\rightarrow y$ if and only if
$\mathcal{K}(q)\models{\mathsf{free}}(q)\rightarrow y$, for each
$y\in{\mathsf{vars}}(q)$. If $F$ is an atom of $q$, then ${F}^{+,q}$ is the
set that contains every variable $y\in{\mathsf{vars}}(q)$ such that either
$y\in{\mathsf{free}}(q)$ or
$\mathcal{K}(q\setminus\\{F\\})\models{\mathsf{Key}}(F)\rightarrow y$ (or
both).

It is known [29] that in the study of consistent query answering for self-
join-free conjunctive queries, free variables can often be treated as
constants. The addition of functional dependencies
$\emptyset\rightarrow{\mathsf{free}}(q)$ has the same effect as treating
variables in ${\mathsf{free}}(q)$ as constants. In the following example, we
omit curly braces and commas when denoting sets of variables. For example,
$\\{z_{1},z_{2}\\}$ is denoted $z_{1}z_{2}$.

######  Example 3.1.

Let $q=\exists u\exists v\exists x\exists y\,R(\underline{u},x)\land
S(\underline{x,z_{1}},y)\land T(\underline{y},v,z_{2})\land
U(\underline{y},u)$. We have ${\mathsf{free}}(q)=z_{1}z_{2}$. Then,
$q\setminus\\{T\\}$111Recall that we use $T$ as a shorthand for the $T$-atom
of $q$. is the query $\exists u\exists v\exists x\exists
y\,R(\underline{u},x)\land S(\underline{x,z_{1}},y)\land U(\underline{y},u)$,
whose only free variable is $z_{1}$. Note incidentally that since $v$ does not
occur in the latter query, the quantification $\exists v$ can be dropped. We
have $\mathcal{K}(q\setminus\\{T\\})=\\{\emptyset\rightarrow
z_{1},u\rightarrow x,xz_{1}\rightarrow y,y\rightarrow u\\}$. Note that
$\emptyset\rightarrow z_{1}$ belongs to the latter set because $z_{1}$ is free
in $q\setminus\\{T\\}$. The closure of ${\mathsf{Key}}(T)$ with respect to
$\mathcal{K}(q\setminus\\{T\\})$ is $uxyz_{1}$. Finally, we obtain
${T}^{+,q}=uxyz_{1}z_{2}$. Note that the latter set contains the variable
$z_{2}$ that is free in $q$. ∎

We say that an atom $F$ of $q$ _attacks_ a variable $x$ occurring in $q$,
denoted ${F}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{x}$, if there
exists a sequence

$\langle{x_{1},x_{2},\ldots,x_{n}}\rangle$ (2)

of bound variables of $q$ ($n\geq 1$) such that:

  1. 1.

if two variables are adjacent in the sequence, then they occur together in
some atom of $q$;

  2. 2.

$x_{1}\in{\mathsf{notKey}}(F)$ and $x_{n}=x$; and

  3. 3.

for every $\ell\in\\{1,\ldots,n\\}$, $x_{\ell}\not\in{F}^{+,q}$.

The sequence (2) will be called a _witness_ that ${F}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{x}$. We say that an atom $F$ of $q$ attacks another
atom $G$ of $q$, denoted ${F}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{G}$, if $F\neq G$ and $F$ attacks some variable of
${\mathsf{vars}}(G)$. It is now easily verified that if $F$ attacks $G$, then
$F$ also attacks a variable in ${\mathsf{Key}}(G)$. A variable or atom that is
not attacked, is called _unattacked_ (where $q$ is understood from the
context). The _attack graph_ of $q$ is a directed graph whose vertices are the
atoms of $q$; there is a directed edge from $F$ to $G$ if
${F}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{G}$. A directed edge in
the attack graph is called an _attack_.

Koutris and Wijsen [29] showed the following.

######  Theorem 3.1 ([29]).

A self-join-free conjunctive query $q(\vec{z})$ has a consistent first-order
rewriting if and only if its attack graph is acyclic.

An attack from $F$ to $G$ is _weak_ if $\mathcal{K}(q)$ logically implies
${\mathsf{Key}}(F)\rightarrow{\mathsf{Key}}(G)$; otherwise it is strong. By a
_component_ of an attack graph, we always mean a maximal weakly connected
component.

Let $q$ be a self-join-free conjunctive query. Whenever the relationship
$\mathcal{K}(q)\models Z\rightarrow w$ holds true, then there exists a
sequential proof of it, as defined next.

Sequential Proof. Let $q(\vec{z})$ be a self-join-free conjunctive query, and
$Z\subseteq{\mathsf{vars}}(q)$. Let $\langle{F_{1},F_{2},\ldots,F_{n}}\rangle$
be a (possibly empty) sequence of atoms in ${\mathsf{body}}(q)$ such that for
every $i\in\\{1,\ldots,n\\}$,
${\mathsf{Key}}(F_{i})\subseteq{\mathsf{free}}(q)\cup
Z\cup\left({\bigcup_{j=1}^{i-1}{\mathsf{vars}}(F_{j})}\right)$. Such a
sequence is called a _sequential proof_ of $\mathcal{K}(q)\models Z\rightarrow
w$, for every $w\in{\mathsf{free}}(q)\cup
Z\cup\left({\bigcup_{j=1}^{n}{\mathsf{vars}}(F_{j})}\right)$. A sequential
proof of $\mathcal{K}(q)\models Z\rightarrow w$ is called _minimal_ if
$\langle{F_{1},\ldots,F_{n-1}}\rangle$ is not a sequential proof of
$\mathcal{K}(q)\models Z\rightarrow w$.

##  4 Parsimonious Counting

Consider a conjunctive query $q(\vec{z})=\exists\vec{w}\;B$, with $B$ a
quantifier-free conjunction of atoms (called the _body_). We introduce a query
that takes a database instance $\mathbf{db}$ as input and returns, for every
tuple $\vec{c}\in q(\mathbf{db})$, the number of valuations for $\vec{w}$ that
make the query true.

######  Definition 4.1 (${\mathbf{cnt}}({q},{\vec{z}})$).

Let $q(\vec{z},\vec{w})$ be a full conjunctive query, in which notation it is
understood that $\vec{z}$ and $\vec{w}$ are disjoint, duplicate-free tuples of
variables. ${\mathbf{cnt}}({q},{\vec{z}})$ is the query that takes as input a
database instance $\mathbf{db}$ and returns every tuple $(\vec{c},i)$ for
which the following hold:

  1. 1.

$\vec{c}$ a tuple of constants of arity $|{\vec{z}}|$; and

  2. 2.

$i$ is a positive integer such that $i$ is the number of distinct tuples
$\vec{d}$, of arity $|{\vec{w}}|$, satisfying $\mathbf{db}\models
q(\vec{c},\vec{d})$.

A maximal set of answers to $q(\mathbf{db})$ that agree on $\vec{z}$ will also
be called a _$\vec{z}$ -group_ (where $q$ and $\mathbf{db}$ are implicitly
understood). Thus, ${\mathbf{cnt}}({q},{\vec{z}})$ counts the number of tuples
in each $\vec{z}$-group.

The following definition introduces range consistent query answers as
introduced in [3].

######  Definition 4.2 (${\mathbf{cqacnt}}({q},{\vec{z}})$).

Let $q(\vec{z},\vec{w})$ be a full conjunctive query, in which notation it is
understood that $\vec{z}$ and $\vec{w}$ are disjoint, duplicate-free tuples of
variables. ${\mathbf{cqacnt}}({q},{\vec{z}})$ is the query that takes as input
a database instance $\mathbf{db}$ and returns every tuple $(\vec{c},[m,n])$
for which the following hold:

  1. 1.

for every repair $\mathbf{r}$ of $\mathbf{db}$, there exists $\vec{d}$ such
that $\mathbf{r}\models q(\vec{c},\vec{d})$;

  2. 2.

there is a repair of $\mathbf{db}$ on which ${\mathbf{cnt}}({q},{\vec{z}})$
returns $(\vec{c},m)$;

  3. 3.

there is a repair of $\mathbf{db}$ on which ${\mathbf{cnt}}({q},{\vec{z}})$
returns $(\vec{c},n)$; and

  4. 4.

if ${\mathbf{cnt}}({q},{\vec{z}})$ returns $(\vec{c},i)$ on some repair of
$\mathbf{db}$, then $m\leq i\leq n$.

Note that it follows that $m\geq 1$. If $(\vec{c},[m,n])$ is an answer to
${\mathbf{cqacnt}}({q},{\vec{z}})$ on $\mathbf{db}$, then we will say that it
is a _range-consistent answer_.

The following proposition states that computing
${\mathbf{cqacnt}}({q(\vec{z},\vec{w})},{\vec{z}})$ can be $\NP$-hard, even if
the query $\exists{\vec{w}}\left[{q}\right]$ has a consistent first-order
rewriting.

######  Proposition 4.1.

There exists a self-join-free conjunctive query $q(\vec{z})$ that has a
consistent first-order rewriting such that
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{\vec{z}})$ is $\NP$-hard to compute.

###### Proof.

The following problem is $\NP$-complete [23].

3-DIMENSIONAL MATCHING (3DM)

INSTANCE:

A set $M\subseteq A_{1}\times A_{2}\times A_{3}$, where $A_{1}$, $A_{2}$,
$A_{3}$ are disjoint sets having the same number $n$ of elements.

QUESTION:

Does $M$ contain a matching, that is, a subset $M^{\prime}\subseteq M$ such
that $|{M^{\prime}}|=n$ and no two elements of $M^{\prime}$ agree in any
coordinate?

Consider the query

$q(z)=\exists x_{1}\exists x_{2}\exists x_{3}\exists
y\,Z(\underline{z})\land\bigwedge_{i=1}^{3}\left({R_{i}(\underline{x_{i}},y)\land
S_{i}(\underline{x_{i}},y)}\right).$

The edge-set of $q$’s attack graph is empty. Therefore, $q$’s attack graph is
acyclic. By Theorem 3.1, $q(z)$ has a consistent first-order rewriting. Let
$M\subseteq A_{1}\times A_{2}\times A_{3}$ be an instance of 3DM. Let
$\mathbf{db}_{M}$ be the database instance that contains $Z(\underline{c})$
and includes, for every $a_{1}a_{2}a_{3}$ in $M$,
$\bigcup_{i=1}^{3}\\{R_{i}(\underline{a_{i}},a_{1}a_{2}a_{3}),S_{i}(\underline{a_{i}},a_{1}a_{2}a_{3})\\}$.
Moreover, $\mathbf{db}_{M}$ includes
$D\vcentcolon=\bigcup_{i=1}^{3}\\{R_{i}(\underline{\bot_{i}},\top),S_{i}(\underline{\bot_{i}},\top)\\}$,
where $\bot_{1},\bot_{2},\bot_{3},\top$ are fresh constants not in $A_{1}\cup
A_{2}\cup A_{3}$. Clearly, $\mathbf{db}_{M}$ is first-order computable from
$M$.

We show the following: $M$ has a matching if and only if for some $\ell$,
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$ returns $(c,[\ell,n+1])$ on
$\mathbf{db}_{M}$. Before delving into the proof, we provide an example.

######  Example 4.1.

Let $A_{1}=\\{a,b\\}$, $A_{2}=\\{d,e\\}$, $A_{3}=\\{f,g\\}$, and
$M=\\{adf,aeg,beg\\}$. Thus, $n=|{A_{1}}|=2$. Then, we construct relations as
follows.

$\begin{array}[]{cccc}\mathbf{db}_{M}:\begin{array}[]{c|*{1}{c}c}Z&\underline{z}\bigstrut\\\
\cline{2-2}\cr&c&\ast\end{array}&\begin{array}[]{c|*{2}{c}c}R_{1}=S_{1}&\underline{x_{1}}&y\bigstrut\\\
\cline{2-3}\cr&a&adf&\ast\\\ &a&aeg\\\ \cdashline{2-3}&b&beg&\ast\\\
\cdashline{2-3}&\bot_{1}&\top&\ast\end{array}&\begin{array}[]{c|*{2}{c}c}R_{2}=S_{2}&\underline{x_{2}}&y\bigstrut\\\
\cline{2-3}\cr&d&adf&\ast\\\ \cdashline{2-3}&e&aeg\\\ &e&beg&\ast\\\
\cdashline{2-3}&\bot_{2}&\top&\ast\end{array}&\begin{array}[]{c|*{2}{c}c}R_{3}=S_{3}&\underline{x_{3}}&y\bigstrut\\\
\cline{2-3}\cr&f&adf&\ast\\\ \cdashline{2-3}&g&aeg\\\ &g&beg&\ast\\\
\cdashline{2-3}&\bot_{3}&\top&\ast\end{array}\end{array}$

Let $q^{*}(z,x_{1},x_{2},x_{3},y)$ be the full query whose set of atoms is
${\mathsf{body}}(q)$. We have $\mathbf{db}_{M}\models_{\mathsf{\tiny
cqa}}q(c)$ because $(c,\bot_{1},\bot_{2},\bot_{3},\top)$ is in the answer to
$q^{*}$ on every repair. It can be verified that
${\mathbf{cqacnt}}({q^{*}},{z})$ returns $(c,[1,3])$ on $\mathbf{db}_{M}$. The
tuples marked with $\ast$ form a repair $\mathbf{r}$ on which
${\mathbf{cnt}}({q^{*}},{z})$ returns $(c,3)$. In particular,
$q^{*}(\mathbf{r})=\\{(c,\bot_{1},\bot_{2},\bot_{3},\top)$, $(c,a,d,f,adf)$,
$(c,b,e,g,beg)\\}$. This answer corresponds to the 3-dimensional matching
$\\{adf,beg\\}$.

Note that if we remove from $\mathbf{db}_{M}$ one of the facts
$R_{i}(\underline{\bot_{i}},\top)$ or $S_{i}(\underline{\bot_{i}},\top)$, for
some $1\leq i\leq 3$, then $c$ is no longer a consistent answer to $q(z)$,
and, according to Definition 4.2, the answer to
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$ would be empty.

$\implies$ Assume $M^{\prime}$ is a matching of $M$. Let $\mathbf{r}$ be a
database instance that includes $D$ and includes, for every
$a_{1}a_{2}a_{3}\in M^{\prime}$, the set
$\bigcup_{i=1}^{3}\\{R_{i}(\underline{a_{i}},a_{1}a_{2}a_{3})$,
$S_{i}(\underline{a_{i}},a_{1}a_{2}a_{3})\\}$. Since no two elements of
$M^{\prime}$ agree on any coordinate, $\mathbf{r}$ is consistent. Moreover,
since $n=|{M^{\prime}}|=|{A_{1}}|=|{A_{2}}|=|{A_{3}}|$, $\mathbf{r}$ contains
a tuple of every block of $\mathbf{db}_{M}$. Therefore, $\mathbf{r}$ is a
repair of $\mathbf{db}_{M}$. Clearly, ${\mathbf{cnt}}({q},{z})$ returns
$(c,n+1)$ on $\mathbf{r}$. It is also obvious to see that there is no repair
of $\mathbf{db}_{M}$ on which ${\mathbf{cnt}}({{\mathsf{body}}(q)},{z})$
returns $(c,k)$ with $k>n+1$. Moreover, $\mathbf{db}_{M}\models_{\mathsf{\tiny
cqa}}q(c)$ because $D$ is included in every repair of $\mathbf{db}_{M}$.
Therefore, for some $\ell$, ${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$
returns $(c,[\ell,n+1])$ on $\mathbf{db}_{M}$.

$\impliedby$ Assume that for some $\ell$,
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$ returns $(c,[\ell,n+1])$ on
$\mathbf{db}_{M}$. Then, there is a repair $\mathbf{r}$ on which
${\mathbf{cnt}}({{\mathsf{body}}(q)},{z})$ returns $n+1$. Let
$q^{*}(z,x_{1},x_{2},x_{3},y)$ be the full query whose set of atoms is
${\mathsf{body}}(q)$. Let $(c,a_{1},a_{2},a_{3},b_{1}b_{2}b_{3})$, with
$b_{1}b_{2}b_{3}\neq\top$, be a tuple in $q^{*}(\mathbf{r})$. For each
$i\in\\{1,2,3\\}$, since $q^{*}$ contains the atom
$R_{i}(\underline{x_{i}},y)$, $\mathbf{r}$ contains
$R_{i}(\underline{a_{i}},b_{1}b_{2}b_{3})$, and hence $a_{i}=b_{i}$ by our
construction. It follows $b_{1}b_{2}b_{3}=a_{1}a_{2}a_{3}$.

Let $(c,a_{1},a_{2},a_{3},a_{1}a_{2}a_{3})$ and
$(c,b_{1},b_{2},b_{3},b_{1}b_{2}b_{3})$ be two tuples in $q^{*}(\mathbf{r})$.
Since $q^{*}$ contains $R_{i}(\underline{x_{i}},y)$, $\mathbf{r}$ contains
$R_{i}(\underline{a_{i}},a_{1}a_{2}a_{3})$ and
$R_{i}(\underline{b_{i}},b_{1}b_{2}b_{3})$. If $a_{i}=b_{i}$, then, since
$\mathbf{r}$ is consistent, we have $a_{1}a_{2}a_{3}=b_{1}b_{2}b_{3}$.
Consequently, no two distinct answers in $q^{*}(\mathbf{r})$ agree on any
coordinate among $x_{1}$, $x_{2}$, and $x_{3}$. Since
${\mathbf{cnt}}({{\mathsf{body}}(q)},{z})$ returns $n+1$ on $\mathbf{r}$, it
follows that the set $\\{a_{1}a_{2}a_{3}\mid\mathbf{r}\setminus D\models
q^{*}(c,a_{1},a_{2},a_{3},a_{1}a_{2}a_{3})\\}$ is a matching of $M^{\prime}$
of size $n$. This concludes the proof. ∎

Note that the foregoing proof can be easily adapted from 3-DIMENSIONAL
MATCHING to 2-DIMENSIONAL MATCHING. That is, the query $q(z)=\exists
x_{1}\exists x_{2}\exists
y\,Z(\underline{z})\land\bigwedge_{i=1}^{2}\left({R_{i}(\underline{x_{i}},y)\land
S_{i}(\underline{x_{i}},y)}\right)$ has a consistent first-order rewriting,
but computing ${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$ is as hard as
$2$-DIMENSIONAL MATCHING.

The following definition introduces the semantic notion of _parsimonious
counting_ , which was illustrated by the running example in Section 1.
Informally, for a query $q(\vec{z})$ that admits parsimonious counting, it
will be the case that on every database instance $\mathbf{db}$, the answers to
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{\vec{z}})$ can be computed by a
first-order query followed by a simple counting step.

######  Definition 4.3 (Parsimonious counting).

Let $q$ be a conjunctive query with ${\mathsf{free}}(q)=\vec{z}$.222We will
commonly write $q(\vec{z})$ to make explicit that
${\mathsf{free}}(q)=\vec{z}$. Let $\vec{x}$ be a (possibly empty) sequence of
distinct bound variables of $q(\vec{z})$. We say that $q$ _admits parsimonious
counting on $\vec{x}$_ if the following hold (let
$q^{\prime}(\vec{z},\vec{x})=\nexists{\vec{x}}\left[{q}\right]$):

  1. (A)

$q(\vec{z})$ has a consistent first-order rewriting;

  2. (B)

$q^{\prime}(\vec{z},\vec{x})$ has a consistent first-order rewriting (call it
$\varphi(\vec{z},\vec{x})$); and

  3. (C)

for every database instance $\mathbf{db}$, the following conditions (C)(a) and
(C)(b) are equivalent:

    1. (a)

$(\vec{c},[m,n])$ is an answer to
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{\vec{z}})$ on $\mathbf{db}$;

    2. (b)

$m\geq 1$ and both the following hold:

      1. (i)

$m$ is the number of distinct tuples $\vec{d}$, of arity $\vec{x}$, such that
$\mathbf{db}\models\varphi(\vec{c},\vec{d})$; and

      2. (ii)

$n$ is the number of distinct tuples $\vec{d}$ such that $\mathbf{db}\models
q^{\prime}(\vec{c},\vec{d})$.

We say that $q$ _admits parsimonious counting_ if it admits parsimonious
counting on some sequence $\vec{x}$ of bound variables.

Significantly, since Definition 4.3 contains a condition that must hold for
every database instance $\mathbf{db}$, it does not give us an efficient
procedure for deciding whether a given self-join-free query $q(\vec{z})$
admits parsimonious counting.

We now give some examples. From the proof of Proposition 4.1 and the paragraph
after that proof, it follows that under standard complexity assumptions, for
$k\geq 2$,

$q_{k}(z)\vcentcolon=\exists x_{1}\dotsm\exists x_{k}\exists
y\,Z(\underline{z})\land\bigwedge_{i=1}^{k}\left({R_{i}(\underline{x_{i}},y)\land
S_{i}(\underline{x_{i}},y)}\right)$

does not admit parsimonious counting, even though $q_{k}(z)$ has a consistent
first-order rewriting. The following example shows a query $q(z)$ that does
not admit parsimonious counting, but for which
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$ can be computed in first-order
logic with a counting step that is slightly more involved than what is allowed
in parsimonious counting.

######  Example 4.2.

Let $q(z)=\exists x\exists y\,R(\underline{z},x)\land S(\underline{x,y})$ and
$q^{*}(z,x,y)=R(\underline{z},x)\land S(\underline{x,y})$. We first argue that
$q(z)$ does not admit parsimonious counting. Let $\mathbf{db}$ be the
following database instance:

$\begin{array}[]{cc}\begin{array}[]{c|cc}R&\underline{z}&x\\\
\cline{2-3}\cr&c_{1}&a\\\ \cdashline{2-3}&c_{2}&a\\\
&c_{2}&b\end{array}&\begin{array}[]{c|cc}S&\underline{x}&\underline{y}\bigstrut\\\
\cline{2-3}\cr&a&d\\\ \cdashline{2-3}&a&e\\\
\cdashline{2-3}&b&f\end{array}\end{array}$

It can be verified that on this database instance,
${\mathbf{cqacnt}}({q^{*}},{z})$ must return $(c_{1},[2,2])$ and
$(c_{2},[1,2])$. We next show the answer to $q^{*}$ on $\mathbf{db}$:

$\begin{array}[]{c|ccc}q^{*}(\mathbf{db})&z&x&y\\\ \cline{2-4}\cr&c_{1}&a&d\\\
&c_{1}&a&e\\\ &c_{2}&a&d\\\ &c_{2}&a&e\\\ &c_{2}&b&f\end{array}$

The correct upper bound of $2$ in $(c_{2},[1,2])$ could only be obtained by
counting, within the $c_{2}$-group, the number of distinct
$\langle{x}\rangle$-values. However, such a counting would conclude an
incorrect upper bound of $1$ for the $c_{1}$-group. It is now correct to
conclude that $q(z)$ does not admit parsimonious counting.

The lower and upper bounds can be obtained from $q^{*}(\mathbf{db})$ by a
counting step that is only slightly more involved than what is allowed in
parsimonious counting. First, construct the following relation where
$\tilde{R}(\underline{c_{j}},v\mid n)$ means that
${\mathbf{cnt}}({q^{*}},{z})$ returns $(c_{j},n)$ on a repair that contains
$R(\underline{c_{j}},v)$.

$\begin{array}[]{c|cc|c}\tilde{R}&\underline{z}&x\\\
\cline{2-4}\cr&c_{1}&a&2\\\ \cdashline{2-4}&c_{2}&a&2\\\
&c_{2}&b&1\end{array}$

These counts can be obtained from $q^{*}(\mathbf{db})$ by counting the number
of distinct $y$-values within each $zx$-group. Next, the lower and upper
bounds are obtained as the minimal and maximal counts within each $z$-group.

Note incidentally that for $q_{0}(z)\vcentcolon=\exists x\exists
y\,R(\underline{z},x)\land T(\underline{z},x)\land S(\underline{x,y})$, which
is obtained from $q(z)$ by adding $T(\underline{z},x)$, we have that $q_{0}$
admits parsimonious counting. The change occurs because if
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q_{0}(c)$, then there exists a unique
value $a$ such that $\mathbf{db}\models\forall
x\left({R(\underline{c},x)\rightarrow x=a}\right)$ and
$\mathbf{db}\models\forall x\left({T(\underline{c},x)\rightarrow x=a}\right)$.
That is, the only blocks that can contribute to
${\mathbf{cqacnt}}({{\mathsf{body}}(q_{0})},{z})$ have cardinality $1$. This
means that range semantics reduces to counting on a consistent database
instance. ∎

##  5 The Class $\mathsf{Cparsimony}$

The notion of parsimonious counting is a semantic property defined for
conjunctive queries. A natural question is to syntactically characterize the
class of conjunctive queries that admit parsimonious counting. In this paper,
we will answer this question under the restriction that queries are self-join-
free. This is the best we can currently hope for, because consistent query
answering for primary keys and conjunctive queries with self-joins is a
notorious open problem for which no tools are known (e.g., attack graphs are
not helpful in the presence of self-joins). We now define our new syntactic
class $\mathsf{Cparsimony}$, which uses the following notion of _frozen
variable_.

######  Definition 5.1 (Frozen variable).

Let $q(\vec{z})$ be a self-join-free conjunctive query. We say that a bound
variable $y$ of $q(\vec{z})$ is _frozen in $q$_ if there exists a sequential
proof of $\mathcal{K}(q)\models\emptyset\rightarrow y$ such that
${F}\stackrel{{\scriptstyle q}}{{\not\rightsquigarrow}}{y}$ for every atom $F$
that occurs in the sequential proof. We write ${\mathsf{frozen}}(q)$ for the
set of all bound variables of ${\mathsf{vars}}(q)$ that are frozen in $q$. A
bound variable that is not frozen in $q$ is called _nonfrozen in $q$_. ∎

######  Example 5.1.

Let $q(z)=\exists x\,R(\underline{z},x)\land S(\underline{z},x)$. We have
${R}\stackrel{{\scriptstyle q}}{{\not\rightsquigarrow}}{x}$. Therefore,
$\langle{R(\underline{z},x)}\rangle$ is a sequential proof of
$\mathcal{K}(q)\models\emptyset\rightarrow x$ that uses no atom attacking $x$.
Hence, $x$ is frozen. Note here that $z$ is free, hence
$\mathcal{K}(q)\models\emptyset\rightarrow z$ by definition. ∎

######  Definition 5.2 (The class $\mathsf{Cparsimony}$).

We define $\mathsf{Cparsimony}$ as the set of self-join-free conjunctive
queries $q(\vec{z})$ satisfying the following conditions:

  1. (I)

the attack graph of $q(\vec{z})$ is acyclic and contains no strong attacks;
and

  2. (II)

there is a tuple $\vec{x}$ of bound variables of $q(\vec{z})$ such that:

    1. (1)

every component333Whenever we use the term component, we mean a maximal weakly
connected component. of $q(\vec{z})$’s attack graph contains an unattacked
atom $R$ such that $\mathcal{K}(q)\models\vec{x}\rightarrow{\mathsf{Key}}(R)$;
and

    2. (2)

for every atom $R$ in ${\mathsf{body}}(q(\vec{z}))$, every (possibly empty)
path in the query graph of $q(\vec{z})$ between a variable of
${\mathsf{notKey}}(R)$ and a variable of $\vec{x}$ uses a variable in
${\mathsf{Key}}(R)\cup{\mathsf{frozen}}(q)$.

We will say that such an $\vec{x}$ is an _id-set_ for $q(\vec{z})$. We will
say that an id-set $\vec{x}$ is _minimal_ if any sequence obtained from
$\vec{x}$ by omitting one or more variables is no longer an id-set.

Informally, id-sets $\vec{x}$ will play the role of $\vec{x}$ in Definition
4.3: they identify the values that have to be counted within each
$\vec{z}$-group to obtain range-consistent answers.

|
---|---
Figure 2: Attack graph _(left)_ and query graph _(right)_ of $q(z)=\exists
x\exists y_{1}\exists y_{2}\exists y_{3}\exists v\exists
w\,R(\underline{x},y_{1})\land S(\underline{x},y_{2})\land
T(\underline{y_{1},y_{2}},y_{3},z)\land P(\underline{v},w)$.

We now illustrate Definition 5.2 by some examples. Then Proposition 5.1
implies that every query $q(\vec{z})$ in $\mathsf{Cparsimony}$ has a unique
minimal id-set that can be easily constructed from $q(\vec{z})$’s attack
graph.

######  Example 5.2.

In the paragraph following the proof of Proposition 4.1, we introduced the
query $q(z)=\exists x_{1}\exists x_{2}\exists
y\,Z(\underline{z})\land\bigwedge_{i=1}^{2}\left({R_{i}(\underline{x_{i}},y)\land
S_{i}(\underline{x_{i}},y)}\right)$. The edge-set of $q(z)$’s attack graph is
empty. No variable is frozen. According to condition (II)(1) in Definition
5.2, every id-set (if any) must contain $x_{1}$. However, no id-set can
contain $x_{1}$, because for the atom $R_{2}(\underline{x_{2}},y)$, the edge
$\\{y,x_{1}\\}$ in the query graph is a path between a variable of
${\mathsf{notKey}}(R_{2})$ and $x_{1}$ that uses no variable of
${\mathsf{Key}}(R_{2})$. We conclude that $q(z)$ is not in
$\mathsf{Cparsimony}$. ∎

######  Example 5.3.

The query $q(z)=\exists x\exists y\exists v\,R(\underline{x},y)\land
S(\underline{y},v)\land T(\underline{v},y)\land P_{1}(\underline{z},y)\land
P_{2}(\underline{z},y)$ belongs to $\mathsf{Cparsimony}$. The attack graph of
$q(z)$ has a single attack from $S$ to $T$. The query graph of $q(z)$ has two
undirected edges: $\\{x,y\\}$ and $\\{y,v\\}$. The variable $y$ is frozen,
because $\langle{P_{1}(\underline{z},y)}\rangle$ is a sequential proof of
$\mathcal{K}(q)\models\emptyset\rightarrow y$ (note here that $z$ is free),
and ${P_{1}}\stackrel{{\scriptstyle q}}{{\not\rightsquigarrow}}{y}$.

It can be verified that $\langle{x}\rangle$ is an id-set. Note that
$\langle{y,x}\rangle$ is a path in the query graph between
$y\in{\mathsf{notKey}}(T)$ and $x$ that uses no variable of
${\mathsf{Key}}(T)=\\{v\\}$. However, that path uses the frozen variable $y$.
∎

######  Example 5.4.

Let $q(z)=\exists x\exists y_{1}\exists y_{2}\exists y_{3}\exists v\exists
w\,R(\underline{x},y_{1})\land S(\underline{x},y_{2})\land
T(\underline{y_{1},y_{2}},y_{3},z)\land P(\underline{v},w)$. The attack graph
and the query graph of $q(z)$ are shown in Fig. 2. We now argue that $q(z)$ is
in $\mathsf{Cparsimony}$. First, the attack graph of $q$ is acyclic and
contains no strong attacks. We next argue that $xv$ is an id-set for $q$. The
attack graph of $q(z)$ has two components. Condition (II)(1) in Definition 5.2
is obviously satisfied for $\vec{x}=xv$ since $\mathcal{K}(q)\models
xv\rightarrow v$ and $\mathcal{K}(q)\models xv\rightarrow x$. It is easily
verified that condition (II)(2) is also verified. In particular, for the atom
$T(\underline{y_{1},y_{2}},y_{3},z)$, every path between $y_{3}$ and $x$ uses
either $y_{1}$ or $y_{2}$. ∎

######  Example 5.5.

Let $q(z)=\exists x\exists y\,R_{1}(\underline{x},y,z)\land
R_{2}(\underline{x},y)\land S_{1}(\underline{y},x)\land
S_{2}(\underline{y},x)$. The attack graph of $q(z)$ contains no edges and,
thus, is acyclic and has four components. It can be verified that no variable
is frozen. We claim that $q(z)$ is not in $\mathsf{Cparsimony}$, because it
has no id-set. Indeed, from condition (II)(1) in Definition 5.2, it follows
that every id-set must contain either $x$ or $y$ (or both). For the atom
$S_{1}(\underline{y},x)$, the empty path is a path between a variable in
${\mathsf{notKey}}(S_{1})$ to $x$ that uses no variable in
${\mathsf{Key}}(S_{1})$. It follows by condition (II)(2) that no id-set can
contain $x$. From $R_{2}(\underline{x},y)$, by similar reasoning, we conclude
that no id-set can contain $y$. It follows that $q(z)$ has no id-set. ∎

######  Proposition 5.1.

Let $q(\vec{z})$ be a query in $\mathsf{Cparsimony}$, and let $\vec{x}$ be a
minimal id-set for it. Let $N=\bigcup\\{{\mathsf{notKey}}(R)\mid R\in q\\}$.
Let $V$ be a $\subseteq$-minimal subset of ${\mathsf{vars}}(q)$ that includes,
for every unattacked atom $R$ of $q$, every bound variable of
${\mathsf{Key}}(R)\setminus N$. Then,

  1. (A)

$V={\mathsf{vars}}(\vec{x})$; and

  2. (B)

whenever $R,S$ are unattacked atoms that are weakly connected in
$q(\vec{z})$’s attack graph,
${\mathsf{Key}}(R)\cap\vec{x}={\mathsf{Key}}(S)\cap\vec{x}$.

######  Example 5.6.

Let $q(z_{1},z_{2})=\exists x\exists y\,R(\underline{x},y,z_{1})\land
S(\underline{x},y)\land T(\underline{y},z_{2})$. The attack graph of $q$
contains no edges, and hence has three weak components. If we construct $V$ as
in the statement of Proposition 5.1, we first compute $N=\\{y,z_{1},z_{2}\\}$,
and then $V=\\{x\\}$. ∎

######  Example 5.7.

Let $q(z_{3})=\exists x\exists y\exists z_{1}\exists
z_{2}\,R(\underline{x},y,z_{1})\land S(\underline{x,y},z_{2})\land
T(\underline{z_{1},z_{2},z_{3}})\land P(\underline{x},y)$. The attack graph of
$q$ contains two edges: $R(\underline{x},y,z_{1})$ and
$S(\underline{x,y},z_{2})$ both attack $T(\underline{z_{1},z_{2},z_{3}})$.
Thus, the attack graph of $q$ has two weak components. If we construct $V$ as
in the statement of Proposition 5.1, we first compute $N=\\{y,z_{1},z_{2}\\}$,
and then $V=\\{x\\}$. ∎

The following proposition settles the complexity of checking whether a query
belongs to $\mathsf{Cparsimony}$.

######  Proposition 5.2.

The following decision problem is in quadratic time: Given a self-join-free
conjunctive query $q(\vec{z})$, decide whether or not $q(\vec{z})$ belongs to
$\mathsf{Cparsimony}$.

##  6 $\mathsf{Cparsimony}$ Admits Parsimonious Counting

In this section, we show the if-direction of Theorem 1.2, which is the
following theorem.

######  Theorem 6.1.

Every self-join-free conjunctive query in $\mathsf{Cparsimony}$ admits
parsimonious counting.

We use a number of helping lemmas and constructs. The following lemma says
that if $\vec{x}$ is an id-set of a query $q(\vec{z})$ in
$\mathsf{Cparsimony}$, then for a consistent database $\mathbf{db}$, the
answers to ${\mathbf{cnt}}({{\mathsf{body}}(q)},{\vec{z}})$ can be obtained by
counting the number of distinct $\vec{x}$-values within each $\vec{z}$-group,
while variables not in $\vec{x}\cdot\vec{z}$ can be ignored.

######  Lemma 6.1.

Let $q(\vec{z},\vec{x},\vec{w})$ be a full self-join free conjunctive query,
in which notation it is understood that $\vec{z}$, $\vec{x}$ and $\vec{w}$ are
disjoint, duplicate-free tuples of variables. Assume that the query
$\exists{\vec{x}\vec{w}}\left[{q}\right]$ belongs to $\mathsf{Cparsimony}$ and
that $\vec{x}$ is an id-set for it. Let $\mathbf{db}$ be a consistent database
instance. For all tuples $\vec{a}$ and $\vec{b}$ of constants, of arities
$|{\vec{z}}|$ and $|{\vec{x}}|$ respectively, for all tuples $\vec{c_{1}}$ and
$\vec{c_{2}}$ of arity $|{\vec{w}}|$, if $\mathbf{db}\models
q(\vec{a},\vec{b},\vec{c_{1}})$ and $\mathbf{db}\models
q(\vec{a},\vec{b},\vec{c_{2}})$, then $\vec{c}_{1}=\vec{c}_{2}$.

We now present the notion of _optimistic repair_ , which was originally
introduced by Fuxman [19]. Informally, a repair $\mathbf{r}$ of a database
$\mathbf{db}$ is an optimistic repair with respect to a conjunctive query
$q(\vec{z})$ if every tuple that is an answer to $q(\vec{z})$ on $\mathbf{db}$
is also an answer to $q(\vec{z})$ on $\mathbf{r}$. The converse obviously
holds true because conjunctive queries are monotone and repairs are subsets of
the original database instance.

######  Definition 6.1 (Optimistic repair).

Let $q(\vec{x})$ be a conjunctive query. Let $\mathbf{db}$ be a database
instance. We say that a repair $\mathbf{r}$ of $\mathbf{db}$ is an _optimistic
repair_ with respect to $q(\vec{x})$ if for every tuple $\vec{a}$ of
constants, of arity $|{\vec{x}}|$, $\mathbf{db}\models q(\vec{a})$ implies
$\mathbf{r}\models q(\vec{a})$ (the converse implication is obviously true).

The following lemma gives a sufficient condition for the existence of
optimistic repairs.

######  Lemma 6.2.

Let $q(\vec{z})$ be a self-join free conjunctive query in
$\mathsf{Cparsimony}$, and let $\vec{x}$ be a minimal id-set for it. Let
$q^{\prime}(\vec{z},\vec{x})$ be the query
$\nexists{\vec{x}}\left[{q}\right]$. Let $\mathbf{db}$ be a database instance,
and $\vec{c}$ a tuple of constants, of arity $|{\vec{z}}|$, such that
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$. Then, $\mathbf{db}$ has
an optimistic repair with respect to
${q^{\prime}}_{[{\vec{z}}\rightarrow{\vec{c}}]}$.

We now present the notion of _pessimistic repair_ , also borrowed from [19].
Informally, a repair of a database $\mathbf{db}$ is a pessimistic repair with
respect to a conjunctive query $q(\vec{z})$ if every answer to $q(\vec{z})$ on
$\mathbf{r}$ is a consistent answer to $q(\vec{z})$ on $\mathbf{db}$. The
converse trivially holds true.

######  Definition 6.2 (Pessimistic repair).

Let $q(\vec{x})$ be a conjunctive query. Let $\mathbf{db}$ be a database
instance. We say that a repair $\mathbf{r}$ of $\mathbf{db}$ is a pessimistic
repair with respect to $q(\vec{x})$ if for every tuple $\vec{a}$ of constants,
of arity $|{\vec{x}}|$, if $\mathbf{r}\models q(\vec{a})$, then
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{a})$.

The following lemma gives a sufficient condition for the existence of
pessimistic repairs.

######  Lemma 6.3.

Let $q(\vec{z})$ be a self-join free conjunctive query in
$\mathsf{Cparsimony}$, and let $\vec{x}$ be a minimal id-set for it. Let
$\mathbf{db}$ be a database instance, and $\vec{c}$ a tuple of constants, of
arity $|{\vec{z}}|$, such that $\mathbf{db}\models_{\mathsf{\tiny
cqa}}q(\vec{c})$. Then, $\mathbf{db}$ has a pessimistic repair with respect to
${q^{\prime}}_{[{\vec{z}}\rightarrow{\vec{c}}]}$.

The following example illustrates the preceding constructs and lemmas.

######  Example 6.1.

Let $q(z)=\exists x\exists y\exists v\,R(\underline{x},y)\land
S(\underline{y,v},z)\land T(\underline{y},v)$. Let $\mathbf{db}$ be the
following database instance:

| $R$ | $\underline{x}$ | $y$
---|---|---
| $a_{1}$ | $b_{1}$
2-3 | $a_{2}$ | $b_{2}$
2-3 | $a_{3}$ | $b_{2}$
2-3 | $a_{4}$ | $b_{3}$
| $S$ | $\underline{y}$ | $\underline{v}$ |  $z$
---|---|---|---
| $b_{1}$ | $c_{1}$ | $g_{1}$
2-4 | $b_{2}$ | $c_{2}$ | $g_{1}$
| $b_{2}$ | $c_{2}$ | $g_{2}$
2-4 | $b_{3}$ | $c_{3}$ | $g_{2}$
| $T$ | $\underline{y}$ |  $v$
---|---|---
| $b_{1}$ | $c_{1}$
2-3 | $b_{2}$ | $c_{2}$
2-3 | $b_{3}$ | $c_{3}$

Clearly, $\mathbf{db}$ has two repairs, which are
$\mathbf{r}_{1}\vcentcolon=\mathbf{db}\setminus\\{S(\underline{b_{2},b_{2}},g_{2})\\}$
and
$\mathbf{r}_{2}\vcentcolon=\mathbf{db}\setminus\\{S(\underline{b_{2},b_{2}},g_{1})\\}$.

We first determine the answers to
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$ on $\mathbf{db}$ in a naive way
without using parsimonious counting, but by enumerating repairs. To this end,
let $q^{*}(z,x,y,v)=R(\underline{x},y)\land S(\underline{y,v},z)\land
T(\underline{y},v)$. We have:

$\displaystyle q^{*}(\mathbf{r}_{1})$ $\displaystyle=$
$\displaystyle\\{(g_{1},a_{1},b_{1},c_{1}),(g_{1},a_{2},b_{2},c_{2}),(g_{1},a_{3},b_{2},c_{2}),(g_{2},a_{4},b_{3},c_{3})\\}$
$\displaystyle q^{*}(\mathbf{r}_{2})$ $\displaystyle=$
$\displaystyle\\{(g_{1},a_{1},b_{1},c_{1}),(g_{2},a_{2},b_{2},c_{2}),(g_{2},a_{3},b_{2},c_{2}),(g_{2},a_{4},b_{3},c_{3})\\}$

The value $g_{1}$ occurs in $3$ tuples of $q^{*}(\mathbf{r}_{1})$, and in one
tuple of $q^{*}(\mathbf{r}_{2})$. On the other hand, $g_{2}$ occurs in one
tuple of $q^{*}(\mathbf{r}_{1})$, and in $3$ tuples of
$q^{*}(\mathbf{r}_{2})$. It follows that $(g_{1},[1,3])$ and $(g_{2},[1,3])$
are the answers to ${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$ on
$\mathbf{db}$.

It can be verified that $q(z)\in\mathsf{Cparsimony}$ with an id-set
$\vec{x}=\langle{x}\rangle$. We next compute
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$ on $\mathbf{db}$ by means of
parsimonious counting. To this end, let
$q^{\prime}(z,x)=\nexists{x}\left[{q}\right]$, and let $\varphi(z,x)$ be a
consistent first-order rewriting for $q^{\prime}(z,x)$. If we execute these
queries on $\mathbf{db}$, we obtain:444$\varphi(\mathbf{db})$ is a shorthand
for the set of all tuples $(c,d)$ such that $\mathbf{db}\models\varphi(c,d)$.

$\displaystyle q^{\prime}(\mathbf{db})$ $\displaystyle=$
$\displaystyle\\{(g_{1},a_{1}),(g_{1},a_{2}),(g_{1},a_{3}),(g_{2},a_{2}),(g_{2},a_{3}),(g_{2},a_{4})\\}$
$\displaystyle\varphi(\mathbf{db})$ $\displaystyle=$
$\displaystyle\\{(g_{1},a_{1}),(g_{2},a_{4})\\}$

As stated in Theorem 6.1, the set $q^{\prime}(\mathbf{db})$ yields the upper
bound $3$ for $g_{1}$ and $g_{2}$, and the set $\varphi(\mathbf{db})$ yields
the lower bound $1$ for $g_{1}$ and $g_{2}$. It is important to understand
that parsimonious counting obtains these bounds directly on $\mathbf{db}$,
without computing any repair.

We elaborate this example further to illustrate the constructs of optimistic
and pessimistic repairs. We have:

$\displaystyle q^{\prime}(\mathbf{r}_{1})$ $\displaystyle=$
$\displaystyle\\{(g_{1},a_{1}),(g_{1},a_{2}),(g_{1},a_{3}),(g_{2},a_{4})\\}$
$\displaystyle q^{\prime}(\mathbf{r}_{2})$ $\displaystyle=$
$\displaystyle\\{(g_{1},a_{1}),(g_{2},a_{2}),(g_{2},a_{3}),(g_{2},a_{4})\\}$

Note that the consistent answer to $q^{\prime}(z,x)$ on $\mathbf{db}$ (i.e.,
the set $\varphi(\mathbf{db})$ used previously) is equal to
$q^{\prime}(\mathbf{r}_{1})\cap
q^{\prime}(\mathbf{r}_{2})=\\{(g_{1},a_{1}),(g_{2},a_{4})\\}$. We see that
$\mathbf{r}_{1}$ is an optimistic repair with respect to
${q^{\prime}(z,x)}_{[{z}\rightarrow{g_{1}}]}$, and a pessimistic repair with
respect to ${q^{\prime}(z,x)}_{[{z}\rightarrow{g_{2}}]}$. On the other hand,
$\mathbf{r}_{2}$ is an optimistic repair with respect to
${q^{\prime}(z,x)}_{[{z}\rightarrow{g_{2}}]}$, and a pessimistic repair with
respect to ${q^{\prime}(z,x)}_{[{z}\rightarrow{g_{1}}]}$. ∎

We finish this section by a proof of Theorem 6.1.

###### Proof of Theorem 6.1.

Let $q(\vec{z})\in\mathsf{Cparsimony}$. We have to prove that $q(\vec{z})$
admits parsimonious counting. Since $q(\vec{z})\in\mathsf{Cparsimony}$, we can
assume an id-set $\vec{x}$ for $q(\vec{z})$. It suffices to show that
conditions (A), (B), and (C) in Definition 4.3 are satisfied for this choice
of $\vec{x}$. As in Definition 4.3, let
$q^{\prime}(\vec{z},\vec{x})=\nexists{\vec{x}}\left[{q}\right]$.

Since $q(\vec{z})$ is in $\mathsf{Cparsimony}$, it has an acyclic attack
graph. It follows from Theorem 3.1 that $q(\vec{z})$ has a consistent first-
order rewriting. Thus, condition (A) in Definition 4.3 is satisfied. It is
known [29] that the attack graph of $q^{\prime}(\vec{z},\vec{x})$ is a
subgraph of the attack graph of $q(\vec{z})$. Informally, no new attacks are
introduced when bound variables are made free. It follows that
$q^{\prime}(\vec{z},\vec{x})$ has an acyclic attack graph, and therefore, by
Theorem 3.1, a consistent first-order rewriting. Thus, condition (B) in
Definition 4.3 is satisfied. In the remainder of the proof, we show that
condition (C) in Definition 4.3 is satisfied. To this end, let $\mathbf{db}$
be an arbitrary database instance.

Let $\vec{c}$ be a tuple of constants such that
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$. Let $D$ be the active
domain of $\mathbf{db}$. Let $f$ be a function that maps every subset
$\mathbf{s}$ of $\mathbf{db}$ to the cardinality of the set $\\{\vec{a}\in
D^{|{\vec{x}}|}\mid\mathbf{s}\models q^{\prime}(\vec{c},\vec{a})\\}$. Clearly,
for every repair $\mathbf{r}$ of $\mathbf{db}$, we have
$\mathbf{r}\subseteq\mathbf{db}$ and hence, since conjunctive queries are
monotone, $f(\mathbf{r})\leq f(\mathbf{db})$. Moreover, since repairs are
consistent, it follows by Lemma 6.1 that for every repair $\mathbf{r}$ of
$\mathbf{db}$, if $(\vec{c},i)$ is an answer to the query
${\mathbf{cnt}}({{\mathsf{body}}(q)},{\vec{z}})$ on $\mathbf{r}$, then
$i=f(\mathbf{r})$.

By Lemma 6.2, we can assume an optimistic repair $\mathbf{o}$ of $\mathbf{db}$
with respect to
${q^{\prime}(\vec{z},\vec{x})}_{[{\vec{z}}\rightarrow{\vec{c}}]}$. By
Definition 6.1 of optimistic repair, for every tuple $\vec{a}$ of constants,
of arity $|{\vec{x}}|$, we have $\mathbf{o}\models
q^{\prime}(\vec{c},\vec{a})$ if and only if $\mathbf{db}\models
q^{\prime}(\vec{c},\vec{a})$. It follows $f(\mathbf{o})=f(\mathbf{db})$.
Consequently, for every repair $\mathbf{r}$ of $\mathbf{db}$,
$f(\mathbf{r})\leq f(\mathbf{o})$. It follows that for some lower bound $m$,
we have that $(\vec{c},[m,f(\mathbf{db})]$ is an answer to
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{\vec{z}})$ on $\mathbf{db}$.

By Lemma 6.3, we can assume a pessimistic repair $\mathbf{p}$ of $\mathbf{db}$
with respect to
${q^{\prime}(\vec{z},\vec{x})}_{[{\vec{z}}\rightarrow{\vec{c}}]}$. Let
$\varphi(\vec{z},\vec{x})$ be a consistent first-order rewriting of
$q^{\prime}(\vec{z},\vec{x})$. By Definition 6.2 of pessimistic repair, the
following hold:

  * •

$\mathbf{p}\models q(\vec{c},\vec{a})$ if and only if
$\mathbf{db}\models\varphi(\vec{c},\vec{a})$. Therefore, $f(\mathbf{p})$ is
the cardinality of the set $S\vcentcolon=\\{\vec{a}\in
D^{|{\vec{x}}|}\mid\mathbf{db}\models\varphi(\vec{c},\vec{a})\\}$.

  * •

for every repair $\mathbf{r}$ of $\mathbf{db}$, $f(\mathbf{p})\leq
f(\mathbf{r})$.

It follows that for some upper bound $n$, we have that $(\vec{c},[|{S}|,n])$
is an answer to ${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{\vec{z}})$ on
$\mathbf{db}$. Putting everything together, we obtain that
$(\vec{c},[|{S}|,f(\mathbf{db})])$ is an answer to
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{\vec{z}})$ on $\mathbf{db}$. From
this, it is correct to conclude that condition (C) in Definition 4.3 is
satisfied. This concludes the proof. ∎

##  7 Completeness of $\mathsf{Cparsimony}$

In this section, we show the only-if-direction of Theorem 1.2, which is the
following theorem.

######  Theorem 7.1.

Every self-join-free conjunctive query that admits parsimonious counting
belongs to $\mathsf{Cparsimony}$.

The following three lemmas state some properties of queries $q(\vec{z})$ that
admit parsimonious counting on some $\vec{x}$.

######  Lemma 7.1.

Let $q(\vec{z})$ be a self-join-free conjunctive query. If $q(\vec{z})$ admits
parsimonious counting, then the attack graph of $q(\vec{z})$ is acyclic.

###### Proof.

Proof by contraposition. If the attack graph of $q(\vec{z})$ is cyclic, then
by Theorem 3.1, $q(\vec{z})$ has no consistent first-order rewriting, and
therefore does not admit parsimonious counting. ∎

######  Lemma 7.2.

Let $q(\vec{z})$ be a self-join-free conjunctive query. Let $\vec{x}$ be a
(possibly empty) sequence of bound variables of $q(\vec{z})$. If $q(\vec{z})$
admits parsimonious counting on $\vec{x}$, then the attack graph of
$q^{\prime}(\vec{z},\vec{x})$ has no strong attack.

######  Lemma 7.3.

Let $q(\vec{z})$ be self-join-free conjunctive query whose attack graph is
acyclic. Let $\vec{x}$ be a (possibly empty) sequence of bound variables of
$q(\vec{z})$. If $q(\vec{z})$ admits parsimonious counting on $\vec{x}$, then
$\vec{x}$ satisfies condition (II)(1) in Definition 5.2.

The following two lemmas, and their corollary, concern condition (II)(2) in
Definition 5.2.

######  Lemma 7.4.

Let $q(\vec{z})$ be a self-join-free conjunctive query. Let $\vec{x}$ be a
(possibly empty) sequence of bound variables of $q(\vec{z})$, and let
$q^{\prime}(\vec{z},\vec{x})=\nexists{\vec{x}}\left[{q}\right]$. Let $\vec{c}$
a tuple of constants of arity $|{\vec{z}}|$. If $q(\vec{z})$ admits
parsimonious counting on $\vec{x}$, then for every database instance
$\mathbf{db}$, if $\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$, then
$\mathbf{db}$ has an optimistic repair with respect to
${q^{\prime}}_{[{\vec{z}}\rightarrow{\vec{c}}]}$.

###### Proof.

Assume that $q(\vec{z})$ admits parsimonious counting on $\vec{x}$. Let
$\mathbf{db}$ be a database instance such that
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$. Let $(\vec{c},[m,n])$ be
an answer to ${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{\vec{z}})$ on
$\mathbf{db}$. Define

$\mathcal{D}\vcentcolon=\\{\vec{d}\in D^{|{\vec{x}}|}\mid\mathbf{db}\models
q^{\prime}(\vec{c},\vec{d})\\},$ (3)

where $D$ be the active domain of $\mathbf{db}$. By our hypothesis that
$q(\vec{z})$ admits parsimonious counting on $\vec{x}$, it follows by
condition (C) in Definition 4.3 that

$n=|{\mathcal{D}}|.$ (4)

By Definition 4.2, we can assume a repair $\mathbf{r}$ of $\mathbf{db}$ such
that $(\vec{c},n)$ is an answer to
${\mathbf{cnt}}({{\mathsf{body}}(q)},{\vec{z}})$ on $\mathbf{r}$. Since
$\mathbf{r}$ is consistent, we have that $(\vec{c},[n,n])$ is an answer to
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{\vec{z}})$ on $\mathbf{r}$. Define

$\mathcal{R}\vcentcolon=\\{\vec{d}\in D^{|{\vec{x}}|}\mid\mathbf{r}\models
q^{\prime}(\vec{c},\vec{d})\\}.$ (5)

By our hypothesis that $q(\vec{z})$ admits parsimonious counting on $\vec{x}$,
it follows by condition (C) in Definition 4.3 that

$n=|{\mathcal{R}}|.$ (6)

Since conjunctive queries are monotone and $\mathbf{r}\subseteq\mathbf{db}$,
it follows $\mathcal{R}\subseteq\mathcal{D}$. Since
$|{\mathcal{R}}|=|{\mathcal{D}}|$ by (4) and (6), it follows
$\mathcal{R}=\mathcal{D}$. From $\mathcal{D}\subseteq\mathcal{R}$, it follows
that $\mathbf{r}$ is an optimistic repair with respect to
${q^{\prime}(\vec{z},\vec{x})}_{[{\vec{z}}\rightarrow{\vec{c}}]}$. ∎

######  Lemma 7.5.

Let $q(\vec{z})$, $\vec{x}$, $q^{\prime}(\vec{z},\vec{x})$, and $\vec{c}$ be
as in the statement of Lemma 7.4. Assume that $\vec{x}$ violates condition
(II)(2) in Definition 5.2. Then, there exists a database $\mathbf{db}$ such
that $\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$, but $\mathbf{db}$
has no optimistic repair with respect to
${q^{\prime}}_{[{\vec{z}}\rightarrow{\vec{c}}]}$.

######  Corollary 7.1.

Let $q(\vec{z})$ be a self-join-free conjunctive query. Let $\vec{x}$ be a
sequence of distinct bound variables of $q(\vec{z})$, and let
$q^{\prime}(\vec{z},\vec{x})=\nexists{\vec{x}}\left[{q}\right]$. If
$q(\vec{z})$ admits parsimonious counting on $\vec{x}$, then $\vec{x}$
satisfies condition (II)(2) in Definition 5.2.

###### Proof.

Immediately from Lemmas 7.4 and 7.5. ∎

Finally, we need the following result.

######  Lemma 7.6.

Let $q(\vec{z})$ be a self-join-free conjunctive query. Let $\vec{x}$ be a
sequence of distinct bound variables of $q(\vec{z})$. Let
$q^{\prime}(\vec{z},\vec{x})=\nexists{\vec{x}}\left[{q}\right]$. Assume that
$\vec{x}$ satisfies condition (II)(2) in Definition 5.2. If the attack graph
of $q(\vec{z})$ has a strong attack from an atom $R$ to an atom $S$, then the
attack graph of $q^{\prime}(\vec{z},\vec{x})$ has a strong attack from $R$ to
$S$.

Before giving a proof of Theorem 7.1, we illustrate the preceding results with
an example.

######  Example 7.1.

Let $q(z)=\exists x\exists y\,R(\underline{x},z,y)\land
S(\underline{y},x)\land T(\underline{y},x)$. We will argue that $q(z)$ is not
in $\mathsf{Cparsimony}$, and then illustrate that it does not admit
parsimonious counting.

The only edges in the attack graph of $q$ are $(R,S)$ and $(R,T)$. Assume for
the sake of contradiction that $q\in\mathsf{Cparsimony}$. Then, following
Proposition 5.1, the minimal id-set of $q(\vec{z})$ is $\langle{}\rangle$.
However, since $\mathcal{K}(q(z))\equiv\\{x\rightarrow y,y\rightarrow
x,\emptyset\rightarrow z\\}$, condition (II)(1) in Definition 5.2 is violated
for $\vec{x}=\langle{}\rangle$. We conclude by contradiction that
$q\notin\mathsf{Cparsimony}$.

We now argue, without using Theorem 7.1, that $q(z)$ does not admit
parsimonious counting. Conditions (A) and (B) in Definition 4.3 of
parsimonious counting are satisfied for every choice of $\vec{x}$ in
$\\{\langle{}\rangle$, $\langle{x}\rangle$, $\langle{y}\rangle$,
$\langle{x,y}\rangle\\}$. However, we will show that condition (C) is not
satisfied. To this end, let $\vec{x}$ be a sequence of bound variables of
$q(z)$. Let $q^{\prime}(z,\vec{x})=\nexists{\vec{x}}\left[{q}\right]$. First,
suppose that $\vec{x}\in\\{\langle{x}\rangle,\langle{x,y}\rangle\\}$. Consider
the following database instance $\mathbf{db}$:

$\begin{array}[]{ccc}\begin{array}[t]{c|ccc}R&\underline{x}&z&y\\\
\cline{2-4}\cr&a&d&e\\\ \cdashline{2-4}&b&d&e\\\
\cdashline{2-4}&c&d&f\end{array}&\begin{array}[t]{c|cc}S&\underline{y}&x\bigstrut\\\
\cline{2-3}\cr&e&a\\\ &e&b\\\
\cdashline{2-3}&f&c\end{array}&\begin{array}[t]{c|cc}T&\underline{y}&x\bigstrut\\\
\cline{2-3}\cr&e&a\\\ &e&b\\\ \cdashline{2-3}&f&c\end{array}\end{array}$

We have that $(d,[1,2])$ is an answer to
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$, but it can be easily verified
that $|{q^{\prime}(\mathbf{db})}|=3$, which is distinct from the upper bound
$2$.

Assume next that $\vec{x}\in\\{\langle{y}\rangle,\langle{x,y}\rangle\\}$.
Consider the following database instance $\mathbf{db}$:

$\begin{array}[]{ccc}\begin{array}[t]{c|ccc}R&\underline{x}&z&y\\\
\cline{2-4}\cr&a&d&e\\\ &a&d&f\\\
\cdashline{2-4}&b&d&g\end{array}&\begin{array}[t]{c|cc}S&\underline{y}&x\bigstrut\\\
\cline{2-3}\cr&e&a\\\ \cdashline{2-3}&f&a\\\
\cdashline{2-3}&g&b\end{array}&\begin{array}[t]{c|cc}T&\underline{y}&x\bigstrut\\\
\cline{2-3}\cr&e&a\\\ \cdashline{2-3}&f&a\\\
\cdashline{2-3}&g&b\end{array}\end{array}$

Now we have that $(d,[2,2])$ is an answer to
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$, but
$|{q^{\prime}(\mathbf{db})}|=3$.

The only remaining case to be considered is $\vec{x}=\langle{}\rangle$. In
that case $q^{\prime}=q$. Consider the following database instance
$\mathbf{db}$:

$\begin{array}[]{ccc}\begin{array}[t]{c|ccc}R&\underline{x}&z&y\\\
\cline{2-4}\cr&a&d&e\\\
\cdashline{2-4}&b&d&f\end{array}&\begin{array}[t]{c|cc}S&\underline{y}&x\bigstrut\\\
\cline{2-3}\cr&e&a\\\
\cdashline{2-3}&f&b\end{array}&\begin{array}[t]{c|cc}T&\underline{y}&x\bigstrut\\\
\cline{2-3}\cr&e&a\\\ \cdashline{2-3}&f&b\end{array}\end{array}$

Since $\mathbf{db}$ is a consistent database instance, the only repair of
$\mathbf{db}$ is $\mathbf{db}$ itself. We have that $(d,[2,2])$ is an answer
to ${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$ on $\mathbf{db}$. It can be
easily verified that $|{q^{\prime}(\mathbf{db})}|=1$, which is distinct from
the upper bound $2$.

Finally, we claim (without proof) that 2-DIMENSIONAL MATCHING (2DM) can be
first-order reduced to computing
${\mathbf{cqacnt}}({{\mathsf{body}}(q)},{z})$. Therefore, since 2DM is
$\NL$-hard [14], $q(z)$ cannot admit parsimonious counting under standard
complexity assumptions. ∎

We can now give the proof of Theorem 7.1.

###### Proof of Theorem 7.1.

Assume that $q(\vec{z})$ admits parsimonious counting. Then, $q(\vec{z})$ has
a tuple $\vec{x}$ of bound variables such that for the query
$q^{\prime}(\vec{z},\vec{x})\vcentcolon=\nexists{\vec{x}}\left[{q}\right]$,
the conditions (A), (B), and (C) in Definition 4.3 are satisfied. From
conditions (A) and (B), it follows by Theorem 3.1 that $q(\vec{z})$ and
$q^{\prime}(\vec{z},\vec{x})$ have acyclic attack graphs. By Lemma 7.3,
condition (II)(1) in Definition 5.2 is satisfied for $\vec{x}$. By Corollary
7.1, condition (II)(2) in Definition 5.2 is satisfied by $\vec{x}$. By Lemma
7.2, the attack graph of $q^{\prime}(\vec{z},\vec{x})$ has no strong attack.
By Lemma 7.6, it is now correct to conclude that the attack graph of
$q(\vec{z})$ has no strong attack either, and thus condition (I) in Definition
5.2 is satisfied. Since we have shown that $q(\vec{z})$ satisfies all
conditions in Definition 5.2, we conclude $q(\vec{z})\in\mathsf{Cparsimony}$.
∎

##  8 Comparison with $\mathsf{Cforest}$

In this section, we introduce $\mathsf{Cforest}$ and show
$\mathsf{Cforest}\subsetneq\mathsf{Cparsimony}$ without making use of Theorem
1.1. Theorem 1.1 then follows by Theorem 6.1.

######  Definition 8.1 ($\mathsf{Cforest}$).

Let $q(\vec{z})$ be a self-join-free conjunctive query. The _Fuxman graph_ of
$q$ is a directed graph whose vertices are the atoms of $q$. There is a
directed edge from an atom $R$ to an atom $S$ if $R\neq S$ and
${\mathsf{notKey}}(R)$ contains a bound variable that also occurs in $S$. The
class $\mathsf{Cforest}$ contains all (and only) self-join free conjunctive
queries $q(\vec{z})$ whose Fuxman graph is a directed forest satisfying, for
every directed edge from $R$ to $S$,
${\mathsf{Key}}(S)\setminus{\mathsf{free}}(q)\subseteq{\mathsf{notKey}}(R)$.

######  Theorem 8.1.

$\mathsf{Cforest}$ is a strict subset of $\mathsf{Cparsimony}$.

##  9 Conclusion and Future Work

In his PhD thesis, Fuxman [19] defined a syntactically restricted class of
self-join-free conjunctive queries, called $\mathsf{Cforest}$, and showed that
for every query in $\mathsf{Cforest}$, consistent answers are first-order
computable, and range-consistent answers are computable in first-order logic
followed by a simple aggregation step. Our notion of “parsimonious counting”
captures the latter computation for counting. Later, Koutris and Wijsen [29]
syntactically characterized the class of _all_ self-join-free conjunctive
queries with a consistent first-order rewriting, which strictly includes
$\mathsf{Cforest}$. However, it remained an open problem to syntactically
characterize the class of _all_ self-join-free conjunctive queries that admit
parsimonious counting. In this paper, we determined the latter class, named it
$\mathsf{Cparsimony}$, and showed that it strictly includes
$\mathsf{Cforest}$.

We now list some open problems for future research. In Definition 4.3 of
parsimonious counting, we required that $q(\vec{z})$ has a consistent first-
order rewriting. It is known [32] that there are self-join-free conjunctive
queries, without consistent first-order rewriting, that have a consistent
rewriting in Datalog. We could relax Definition 4.3 by requiring the existence
of a consistent rewriting in Datalog, rather than in first-order logic. It is
an open question to syntactically characterize the self-join-free conjunctive
queries that admit parsimonious counting under such a relaxed definition.

Another open question is to characterize the complexity of
${\mathbf{cqacnt}}({q(\vec{z},\vec{w})},{\vec{z}})$ for every full self-join-
free conjunctive query $q$ and choice of free variables $\vec{z}$. It is
easily verified that the complexity of computing the answers to
${\mathbf{cqacnt}}({q(\vec{z},\vec{w})},{\vec{z}})$ is higher than computing
the consistent answers to
$q^{\prime}(\vec{z})\vcentcolon=\exists{\vec{w}}\left[{q}\right]$ (because of
the lower bound in range semantics). It remains an open question to
characterize this complexity if $q^{\prime}(\vec{z})$ is not in
$\mathsf{Cparsimony}$, even if it has a consistent first-order rewriting.

The notion of parsimonious counting does not require conjunctive queries to be
self-join-free. An ambitious open problem is to syntactically characterize the
class of all (i.e., not necessarily self-join-free) conjunctive queries that
admit parsimonious counting. This problem is largely open, because it is
already a notorious open problem to syntactically characterize the class of
conjunctive queries that have a consistent first-order rewriting.

Another open question is to extend the results in the current paper to other
aggregation operators than COUNT, including MAX, MIN, SUM, and AVG.

## References

  * [1] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison-Wesley, 1995.
  * [2] Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki.  Consistent query answers in inconsistent databases.  In PODS, pages 68–79. ACM Press, 1999.
  * [3] Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki.  Scalar aggregation in FD-inconsistent databases.  In ICDT, volume 1973 of Lecture Notes in Computer Science, pages 39–53. Springer, 2001.
  * [4] Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki, Xin He, Vijay Raghavan, and Jeremy P. Spinrad.  Scalar aggregation in inconsistent databases.  Theor. Comput. Sci., 296(3):405–434, 2003.
  * [5] Leopoldo E. Bertossi.  Database Repairing and Consistent Query Answering.  Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.
  * [6] Leopoldo E. Bertossi.  Database repairs and consistent query answering: Origins and further developments.  In PODS, pages 48–58. ACM, 2019.
  * [7] Leopoldo E. Bertossi, Loreto Bravo, Enrico Franconi, and Andrei Lopatenko.  The complexity and approximation of fixing numerical attributes in databases under integrity constraints.  Inf. Syst., 33(4-5):407–434, 2008.
  * [8] Andrei A. Bulatov.  Complexity of conservative constraint satisfaction problems.  ACM Trans. Comput. Log., 12(4):24:1–24:66, 2011.
  * [9] Marco Calautti, Marco Console, and Andreas Pieris.  Counting database repairs under primary keys revisited.  In PODS, pages 104–118. ACM, 2019.
  * [10] Marco Calautti, Marco Console, and Andreas Pieris.  Benchmarking approximate consistent query answering.  In PODS, pages 233–246. ACM, 2021.
  * [11] Marco Calautti, Leonid Libkin, and Andreas Pieris.  An operational approach to consistent query answering.  In PODS, pages 239–251. ACM, 2018.
  * [12] Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider.  Counting database repairs entailing a query: The case of functional dependencies.  In PODS, pages 403–412. ACM, 2022.
  * [13] Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider.  Uniform operational consistent query answering.  In PODS, pages 393–402. ACM, 2022.
  * [14] Ashok K. Chandra, Larry J. Stockmeyer, and Uzi Vishkin.  Constant depth reducibility.  SIAM J. Comput., 13(2):423–439, 1984.
  * [15] Akhil A. Dixit and Phokion G. Kolaitis.  A SAT-based system for consistent query answering.  In SAT, volume 11628 of Lecture Notes in Computer Science, pages 117–135. Springer, 2019.
  * [16] Akhil A. Dixit and Phokion G. Kolaitis.  Consistent answers of aggregation queries via SAT.  In ICDE, pages 924–937. IEEE, 2022.
  * [17] Zhiwei Fan, Paraschos Koutris, Xiating Ouyang, and Jef Wijsen.  LinCQA: Faster consistent query answering with linear time guarantees.  CoRR, abs/2208.12339, 2022.
  * [18] Gaëlle Fontaine.  Why is it hard to obtain a dichotomy for consistent query answering?  ACM Trans. Comput. Log., 16(1):7:1–7:24, 2015.
  * [19] Ariel Fuxman.  Efficient query processing over inconsistent databases. PhD thesis, University of Toronto, 2007.
  * [20] Ariel Fuxman, Elham Fazli, and Renée J. Miller.  ConQuer: Efficient management of inconsistent databases.  In SIGMOD Conference, pages 155–166. ACM, 2005.
  * [21] Ariel Fuxman, Diego Fuxman, and Renée J. Miller.  ConQuer: A system for efficient querying over inconsistent databases.  In VLDB, pages 1354–1357. ACM, 2005.
  * [22] Ariel Fuxman and Renée J. Miller.  First-order query rewriting for inconsistent databases.  In ICDT, volume 3363 of Lecture Notes in Computer Science, pages 337–351. Springer, 2005.
  * [23] M. R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [24] Miika Hannula and Jef Wijsen.  A dichotomy in consistent query answering for primary keys and unary foreign keys.  In PODS, pages 437–449. ACM, 2022.
  * [25] Aziz Amezian El Khalfioui, Jonathan Joertz, Dorian Labeeuw, Gaëtan Staquet, and Jef Wijsen.  Optimization of answer set programs for consistent query answering by means of first-order rewriting.  In CIKM, pages 25–34. ACM, 2020.
  * [26] Benny Kimelfeld, Ester Livshits, and Liat Peterfreund.  Counting and enumerating preferred database repairs.  Theor. Comput. Sci., 837:115–157, 2020.
  * [27] Phokion G. Kolaitis, Enela Pema, and Wang-Chiew Tan.  Efficient querying of inconsistent databases with binary integer programming.  Proc. VLDB Endow., 6(6):397–408, 2013.
  * [28] Paraschos Koutris, Xiating Ouyang, and Jef Wijsen.  Consistent query answering for primary keys on path queries.  In PODS, pages 215–232. ACM, 2021.
  * [29] Paraschos Koutris and Jef Wijsen.  Consistent query answering for self-join-free conjunctive queries under primary key constraints.  ACM Trans. Database Syst., 42(2):9:1–9:45, 2017.
  * [30] Paraschos Koutris and Jef Wijsen.  Consistent query answering for primary keys and conjunctive queries with negated atoms.  In PODS, pages 209–224. ACM, 2018.
  * [31] Paraschos Koutris and Jef Wijsen.  First-order rewritability in consistent query answering with respect to multiple keys.  In PODS, pages 113–129. ACM, 2020.
  * [32] Paraschos Koutris and Jef Wijsen.  Consistent query answering for primary keys in datalog.  Theory Comput. Syst., 65(1):122–178, 2021.
  * [33] Dany Maslowski and Jef Wijsen.  A dichotomy in the complexity of counting database repairs.  J. Comput. Syst. Sci., 79(6):958–983, 2013.
  * [34] Dany Maslowski and Jef Wijsen.  Counting database repairs that satisfy conjunctive queries with self-joins.  In ICDT, pages 155–164. OpenProceedings.org, 2014.
  * [35] Slawek Staworko, Jan Chomicki, and Jerzy Marcinkowski.  Prioritized repairing and consistent query answering in relational databases.  Ann. Math. Artif. Intell., 64(2-3):209–246, 2012.
  * [36] Jef Wijsen.  On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases.  In PODS, pages 179–190. ACM, 2010.
  * [37] Jef Wijsen.  Certain conjunctive query answering in first-order logic.  ACM Trans. Database Syst., 37(2):9:1–9:35, 2012.
  * [38] Jef Wijsen.  Foundations of query answering on inconsistent databases.  SIGMOD Rec., 48(3):6–16, 2019.

##  Appendix A Helping Constructs and Lemmas

We recall some definitions from graph theory. In a directed acyclic graph
(DAG), a vertex with zero indegree is called a _source_. If there is a
directed path from $u$ to $v$ in a DAG, with $u\neq v$, then $v$ is called a
_descendant_ of $u$, and $u$ an _ancestor_ of $v$.

The following lemma states that whenever $R$ and $S$ are distinct sources that
are weakly connected in a DAG, then there is a sequence of sources that starts
with $R$ and ends with $S$, such that every two adjacent vertices in the
sequence have a descendant in common.

######  Lemma A.1 (Sources of a graph are linked by sources).

Let $G=(V,E)$ be a DAG. Let $R,S\in V$ be distinct sources that are weakly
connected. There is a sequence $\langle{H_{1},\ldots,H_{n}}\rangle$ of sources
such that $H_{1}=R$, $H_{n}=S$, and every two adjacent sources in the sequence
have a common descendent.

###### Proof.

Since $R$ and $S$ are weakly connected, there is a sequence
$\langle{F_{1},\ldots,F_{n}}\rangle$ of atoms in $V$ such that $F_{1}=R$,
$F_{n}=S$ and for every $i\in\\{1,\ldots,n-1\\}$, either $(F_{i},F_{i+1})\in
E$ or $(F_{i+1},F_{i})\in E$. We construct a new sequence by repeating the
following step as long as possible: replace some contiguous subsequence
$\langle{I,\ldots,J}\rangle$ with $\langle{I,J}\rangle$ if $I$ is a descendant
or an ancestor of $J$. Let the new sequence be
$\langle{G_{1},\ldots,G_{m}}\rangle$. By construction, for all
$i\in\\{1,\ldots,m-2\\}$,

  * •

if $G_{i}$ is a descendant of $G_{i+1}$, then $G_{i+1}$ is an ancestor of
$G_{i+2}$; and

  * •

if $G_{i}$ is an ancestor of $G_{i+1}$, then $G_{i+1}$ is a descendant of
$G_{i+2}$.

It is easily verified that $G_{1}=R$, $G_{m}=S$, and that $m$ is an odd
number. By construction, for every $i\in\\{1,\dots,m\\}$ such that $i$ is
even, we have that $G_{i}$ is a common descendant of $G_{i-1}$ and $G_{i+1}$.
We now change the sequence $\langle{G_{1},\dots,G_{m}}\rangle$ as follows: for
every $j\in\\{1,\dots,m\\}$ such that $j$ is odd, if $G_{j}$ is not a source,
replace $G_{j}$ by a source that is an ancestor of $G_{j}$ (such a source
obviously exists in a DAG). It is easily verified that if we now omit the
vertices that are not sources (i.e., $G_{2},G_{4},\ldots,G_{m-1}$), we obtain
a sequence of sources in which every two adjacent sources have a descendant in
common. ∎

The following lemma states that sequential proofs provide a sound and complete
characterization of logical implication.

######  Lemma A.2.

Let $q$ be a self-join free conjunctive query. Let
$Z\subseteq{\mathsf{vars}}(q)$ and $w\in{\mathsf{vars}}(q)$. Then the
following are equivalent:

  1. 1.

$\mathcal{K}(q)\models Z\rightarrow w$; and

  2. 2.

there is a sequence $\langle{F_{1},\ldots,F_{n}}\rangle$ of atoms that is a
sequential proof of $\mathcal{K}(q)\models Z\rightarrow w$.

###### Proof.

Sequential proofs mimic a standard algorithm for logical implication of
functional dependencies; see for example [1, Algorithm 8.2.7]. ∎

######  Lemma A.3 (Attacks with same endpoint).

Let $q$ be a self-join-free conjunctive query. Let $R$ and $S$ be two distinct
atoms that both attack a same atom. If ${R}\stackrel{{\scriptstyle
q}}{{\not\rightsquigarrow}}{S}$, then either ${S}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{R}$ or ${\mathsf{Key}}(S)\subseteq{R}^{+,q}$.

###### Proof.

Assume ${R}\stackrel{{\scriptstyle q}}{{\not\rightsquigarrow}}{S}$. There is
$T$ such that ${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{T}$ and
${S}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{T}$. There is a sequence
$\langle{x_{0},x_{1},\ldots,x_{n}}\rangle$ ($n\geqslant 0$) of bound variables
not in ${R}^{+,q}$ such that $x_{0}\in{\mathsf{notKey}}(R)$,
$x_{n}\in{\mathsf{vars}}(T)$, and every two adjacent variables occur together
in some atom of $q$. Likewise, there is a sequence
$\langle{y_{0},y_{1},\ldots,y_{m}}\rangle$ ($m\geqslant 0$) of bound variables
not in ${S}^{+,q}$ such that $y_{0}\in{\mathsf{notKey}}(S)$,
$y_{m}\in{\mathsf{vars}}(T)$, and every two adjacent variables occur together
in some atom of $q$. Clearly, for every $i\in\\{0,1,\ldots,m\\}$,
${S}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{y_{i}}$. In the sequence
$\langle{x_{0},x_{1},\ldots,x_{n},y_{m},y_{m-1},\ldots,y_{0}}\rangle$, it
holds that $x_{0}\in{\mathsf{notKey}}(R)$, $y_{0}\in{\mathsf{notKey}}(S)$, and
every two adjacent variables occur together in some atom of $q$. By our
hypothesis that ${R}\stackrel{{\scriptstyle q}}{{\not\rightsquigarrow}}{S}$,
there is $i\in\\{0,\ldots,m\\}$ such that $y_{i}\in{R}^{+,q}$. By Lemma A.2,
there exists a shortest sequence $\langle{H_{1},H_{2},\ldots,H_{\ell}}\rangle$
that is a sequential proof of
$\mathcal{K}(q\setminus\\{R\\})\models{\mathsf{Key}}(R)\rightarrow y_{i}$. Two
cases are possible.

Case that $\ell=0$.

Then $y_{i}\in{\mathsf{Key}}(R)$. From ${S}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{y_{i}}$, it follows ${S}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{R}$.

Case that $\ell>0$.

If $S\in\\{H_{1},\ldots,H_{\ell}\\}$, then by Lemma A.2 it is correct to
conclude ${\mathsf{Key}}(S)\subseteq{R}^{+,q}$, and the desired result
obtains. So it suffices to show $S\in\\{H_{1},\ldots,H_{\ell}\\}$. Assume for
the sake of contradiction that $S\notin\\{H_{1},\ldots,H_{\ell}\\}$. For
technical reasons, define $H_{0}\vcentcolon=R$. We show that for every
$k\in\\{1,\dots,\ell\\}$, the following holds true:

> _Back Property:_ if ${S}\stackrel{{\scriptstyle
> q}}{{\rightsquigarrow}}{H_{k}}$, then there is $g<k$ such that
> ${S}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{H_{g}}$.

To this end, assume ${S}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{H_{k}}$ with $k\geqslant 1$. By definition of attacks,
there is a bound variable $u\in{\mathsf{Key}}(H_{k})$ such that
${S}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{u}$. If
$u\in{\mathsf{vars}}(R)$, then the desired result obtains because we let
$H_{0}=R$. Assume $u\notin{\mathsf{vars}}(R)$ from here on. Then there exists
$g\in\\{1,2,\ldots,k-1\\}$ such that $u\in{\mathsf{notKey}}(H_{g})$.
Informally, $H_{g}$ is the atom that introduces $u$ in ${R}^{+,q}$. Since
${S}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{u}$ and $H_{g}\neq S$, it
follows ${S}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{H_{g}}$. This
concludes the proof of the _Back Property_.

Since our sequential proof is as short as possible,
$y_{i}\in{\mathsf{notKey}}(H_{\ell})$. From ${S}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{y_{i}}$ and $H_{\ell}\neq S$, it follows
${S}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{H_{\ell}}$. By repeated
application of the _Back Property_ , we obtain ${S}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{H_{0}}$ with $H_{0}=R$, a contradiction. This
concludes the proof.∎

######  Lemma A.4 (Sources determine one another).

Let $q$ be a self-join free conjunctive query such that $q$’s attack graph is
acyclic. Let $R$ and $S$ be unattacked atoms that are weakly connected in
$q$’s attack graph. Then,
$\mathcal{K}(q)\models{\mathsf{Key}}(R)\rightarrow{\mathsf{Key}}(S)$.

###### Proof.

It follows from [29, Lemma 3.5] that if an attack graph is acyclic, then it is
transitive. By Lemma A.1, we can assume a sequence of unattacked atoms
$\langle{H_{1},\ldots,H_{n}}\rangle$ such that $H_{1}=R$, $H_{n}=S$, and every
two adjacent atoms in the sequence attack a same atom. From Lemma A.3, it
follows that for every $i\in\\{1,\ldots,n-1\\}$,
$\mathcal{K}(q)\models{\mathsf{Key}}(H_{i})\rightarrow{\mathsf{Key}}(H_{i+1})$.
By Armstrong’s transitivity axiom,
$\mathcal{K}(q)\models{\mathsf{Key}}(R)\rightarrow{\mathsf{Key}}(S)$. ∎

######  Lemma A.5.

Let $q$ be a self-join free conjunctive query with an acyclic attack graph
containing no strong attacks. For every unattacked atom $R$ in $q$’s attack
graph, if $w$ is a variable that occurs in an atom that is weakly connected to
$R$, then $\mathcal{K}(q)\models{\mathsf{Key}}(R)\rightarrow w$.

###### Proof.

Let $R$ be an unattacked atom in ${\mathsf{body}}(q)$. Let $S$ be a atom in
${\mathsf{body}}(q)$ that is weakly connected to $R$, and
$w\in{\mathsf{vars}}(S)$. Clearly,
$\mathcal{K}(q)\models{\mathsf{Key}}(S)\rightarrow w$. It follows from [29,
Lemma 3.5] that if an attack graph is acyclic, then it is transitive. Since
$q$’s attack graph is acyclic, we can assume an unattacked atom $S^{\prime}$
such that either $S=S^{\prime}$ or ${S^{\prime}}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{S}$. Since the attack graph of $q$ contains no strong
attacks, it follows
$\mathcal{K}(q)\models{\mathsf{Key}}(S^{\prime})\rightarrow{\mathsf{Key}}(S)$.
By Lemma A.4,
$\mathcal{K}(q)\models{\mathsf{Key}}(R)\rightarrow{\mathsf{Key}}(S^{\prime})$.
By Armstrong’s transitivity axiom, we obtain
$\mathcal{K}(q)\models{\mathsf{Key}}(R)\rightarrow w$. ∎

##  Appendix B Proofs for Section 5

We present a number of helping lemmas.

######  Lemma B.1.

Let $q(\vec{z})$ be self-join-free conjunctive query. Let $\vec{x}$ be a
minimal id-set for $q(\vec{z})$. Then, for every variable $v$ in $\vec{x}$, we
have $\mathcal{K}(q)\not\models\emptyset\rightarrow v$. Consequently, a
minimal id-set contains no frozen variables.

###### Proof.

Assume for the sake of contradiction that there is a variable $v$ in $\vec{x}$
such that $\mathcal{K}(q)\models\emptyset\rightarrow v$. It can be easily
verified that $\vec{x}\setminus\\{v\\}$ still satisfies conditions (II)(1) and
(II)(2) in Definition 5.2, contradicting that $\vec{x}$ is minimal. ∎

######  Lemma B.2.

Let $q(\vec{z})$ be a self-join-free conjunctive query. If a variable $v$ of
$q$ is attacked in $q$, then $v\notin{\mathsf{frozen}}(q)$.

###### Proof.

Assume ${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{v}$ for some atom
$R$. Assume for the sake of contradiction that $v\in{\mathsf{frozen}}(q)$.
Then there is a sequential proof of $\mathcal{K}(q)\models\emptyset\rightarrow
v$ such that no atom in the sequential proof attacks $v$. Since
${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{v}$, we have that $R$ is
not used in the sequential proof. Consequently,
$\mathcal{K}(q\setminus\\{R\\})\models\emptyset\rightarrow v$, and hence
$v\in{R}^{+,q}$. Consequently, ${R}\stackrel{{\scriptstyle
q}}{{\not\rightsquigarrow}}{v}$, a contradiction. ∎

######  Lemma B.3.

Let $q(\vec{z})$ be a self-join-free conjunctive query with an acyclic attack
graph. Let $\vec{x}$ be a minimal id-set for $q(\vec{z})$. For every variable
$x$ of $\vec{x}$, the following hold:

  1. (a)

if $x$ occurs in an atom $R$ of $q(\vec{z})$, then $x$ occurs at a primary-key
position of $R$;

  2. (b)

$x$ is unattacked; and

  3. (c)

$x$ occurs at a primary-key position in an unattacked atom of $q$.

###### Proof.

Proof of (a) Assume for the sake of contradiction that for some atom $R$ in
$q(\vec{z})$, $\vec{x}$ contains some variable $x$ of
${\mathsf{notKey}}(R)\setminus\vec{z}$. Since $x$ is a bound variable, the
query graph of $q(\vec{z})$ contains an empty path from $x$ to $x$, which is a
path from a variable in ${\mathsf{notKey}}(R)$ to a variable of $\vec{x}$ that
uses no variable of ${\mathsf{Key}}(R)$. From Lemma B.1, it follows that $x$
is not frozen. It follows that condition (II)(2) in Definition 5.2 is
violated, a contradiction.

Proof of (b) Assume for the sake of contradiction that some variable $x$ of
$\vec{x}$ is attacked. There is an atom $F$ in $q$ that attacks $x$, with a
witness $\langle{x_{1},\ldots,x_{n}}\rangle$ of the form (2) in the definition
of attack graphs, where $x_{n}=x$. It is easily verified that the witness is a
path from $x_{1}$ to $x$ in the query graph of $q(\vec{z})$. Since
${\mathsf{Key}}(F)\subseteq{F}^{+,q}$, no $x_{i}$ in this sequence occurs in
${\mathsf{Key}}(F)$. By Lemma B.2, no $x_{i}$ is frozen. It follows that
condition (II)(2) in Definition 5.2 is violated, a contradiction.

Proof of (c) By item (a), we can assume an atom $R$ such that
$x\in{\mathsf{Key}}(R)$. If $R$ is unattacked, then the desired result
obtains. Assume from here on that $R$ is attacked by an atom $S$ in
${\mathsf{body}}(q)$. By definition of an attack graph, there is a witness
$\langle{v_{1},\ldots,v_{n}}\rangle$ of this attack such that
$v_{1}\in{\mathsf{notKey}}(S)$, $v_{n}\in{\mathsf{Key}}(R)$, and for every
$i\in\\{1,\ldots,n\\}$, $v_{i}\not\in{S}^{+,q}$ and therefore
$v_{i}\not\in{\mathsf{Key}}(S)$. By Lemma B.2, no $v_{i}$ is frozen. From
Lemma B.1, it follows that $x$ is not frozen. If $x\notin{\mathsf{Key}}(S)$,
then $\langle{v_{1},\ldots,v_{n},x}\rangle$ is a (not necessarily simple) path
in the query graph from a variable in ${\mathsf{notKey}}(S)$ to a variable of
$\vec{x}$ that uses no variable of ${\mathsf{Key}}(S)$, contradicting
condition (II)(2) in Definition 5.2. We conclude by contradiction that
$x\in{\mathsf{Key}}(S)$. If $S$ is unattacked, then the desired result
obtains. Otherwise there is an atom $T$ that attacks $S$, and we can repeat
the same reasoning as before. The same reasoning can however not be applied
forever, since the attack graph of $q$ is finite and contains no cycles.
Therefore, at some point we will find an unattacked atom whose primary key
contains $x$. ∎

We can now give the proof of Proposition 5.1.

###### Proof of Proposition 5.1.

$V\subseteq{\mathsf{vars}}(\vec{x})$. Let $v\in V$. By the construction of
$V$, we can assume an unattacked atom $R$ such that $v$ is a bound variable in
${\mathsf{Key}}(R)\setminus N$. By condition (II)(1) in Definition 5.2, there
is an unattacked atom $S$ such that $S$ is weakly connected to $R$ and
$\mathcal{K}(q)\models\vec{x}\rightarrow{\mathsf{Key}}(S)$. By Lemma A.5,
$\mathcal{K}(q)\models{\mathsf{Key}}(S)\rightarrow v$. From
$\mathcal{K}(q)\models\vec{x}\rightarrow{\mathsf{Key}}(S)$ and
$\mathcal{K}(q)\models{\mathsf{Key}}(S)\rightarrow v$, it follows
$\mathcal{K}(q)\models\vec{x}\rightarrow v$. Since $v\not\in N$,
$\mathcal{K}(q)\models\vec{x}\rightarrow v$ implies that $v$ belongs to
$\vec{x}$.

${\mathsf{vars}}(\vec{x})\subseteq V$. Let $x$ be an arbitrary variable in
$\vec{x}$. By item (c) in Lemma B.3, we can assume an unattacked atom $R$ such
that $x\in{\mathsf{Key}}(R)$. By item (a) in Lemma B.3, $x\not\in N$. Then, by
construction of $V$, we have $x\in V$.

Proof of (B). Assume $R,S$ are unattacked atoms that are weakly connected in
$q(\vec{z})$’s attack graph. We show
${\mathsf{Key}}(R)\cap\vec{x}\subseteq{\mathsf{Key}}(S)$. The desired result
then follows by symmetry. By Lemma A.1, there is a sequence of weakly
connected, unattacked atoms $\langle{H_{1},H_{2},\ldots,H_{n}}\rangle$ such
that $H_{1}=R$, $H_{n}=S$, and every two adjacent atoms have a descendant in
common. We will show that
${\mathsf{Key}}(H_{1})\cap\vec{x}\subseteq{\mathsf{Key}}(H_{2})$. We can
assume that $T$ is a descendant shared by $H_{1}$ and $H_{2}$. Since the
attack graph of $q$ is acyclic (because $q\in\mathsf{Cparsimony}$), it is
transitive by [29, Lemma 3.5]. Assume
$x\in{\mathsf{Key}}(H_{1})\cap{\vec{x}}$. Let
$\langle{x_{1},\ldots,x_{n}}\rangle$ be a witness that
${H_{1}}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{T}$. It follows that
$H_{1}$ attacks $x_{i}$ for every $i\in\\{1,\ldots,n\\}$. Let
$\langle{y_{1},\ldots,y_{m}}\rangle$ be a witness that
${H_{2}}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{T}$. We have
$y_{1},\ldots,y_{m}\notin{\mathsf{Key}}(H_{2})$. By Lemma B.2, no variable in
$\\{x_{1},\dots,x_{n},y_{1},\dots,y_{m}\\}$ is frozen. Then
$\langle{x,x_{1},\ldots,x_{n},y_{m},\ldots,y_{1}}\rangle$ is a path in the
query graph of $q$ between $x$ and $y_{1}$. For every $i\in\\{1,\dots,n\\}$,
$x_{i}\notin{\mathsf{Key}}(H_{2})$, or else ${H_{1}}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{H_{2}}$, a contradiction. Assume towards a
contradiction that $x\notin{\mathsf{Key}}(H_{2})$. The reverse path is a path
from the variable $y_{1}\in{\mathsf{notKey}}(H_{2})$ to a variable of
$\vec{x}$ that uses no variable of
${\mathsf{Key}}(H_{2})\cup{\mathsf{frozen}}(q)$. By condition (II)(2) in
Definition 5.2, $\vec{x}$ is not an id-set, a contradiction. We conclude by
contradiction that $x\in{\mathsf{Key}}(H_{2})$.

By repeating the same reasoning, we obtain
${\mathsf{Key}}(H_{2})\cap\vec{x}\subseteq{\mathsf{Key}}(H_{3})$,
${\mathsf{Key}}(H_{3})\cap\vec{x}\subseteq{\mathsf{Key}}(H_{4})$,… It follows
${\mathsf{Key}}(H_{1})\cap\vec{x}\subseteq{\mathsf{Key}}(H_{n})$. ∎

Finally, we give the proof of Proposition 5.2.

###### Proof of Proposition 5.2.

Let $q(\vec{z})$ be a self-join-free conjunctive query. It is possible, in
quadratic time in the size of $q$, to compute the attack graph of $q(\vec{z})$
[37], test whether condition (I) in Definition 5.2 is satisfied, and construct
$V$ as in the statement of Proposition 5.1. By adding to $q(\vec{z})$, for
every variable $x$, a fresh atom $P_{x}(\underline{x})$, the attack graph
allows determining the set $n_{x}$ of all atoms not attacking $x$. Membership
of $x$ in ${\mathsf{frozen}}(q)$ is determined by testing whether
$\mathcal{K}(n_{x})\models\emptyset\rightarrow x$, which is in linear time in
the size of $n_{x}$. If condition (I) is not satisfied, answer “no”; otherwise
proceed as follows. For every atom $R$ in ${\mathsf{body}}(q(\vec{z}))$, test
whether, in $q(\vec{z})$’s query graph, some variable of $V$ is reachable from
some variable in ${\mathsf{notKey}}(R)$ without using variables from
${\mathsf{Key}}(R)\cup{\mathsf{frozen}}(q)$. This can be done in quadratic
time. If any such reachability test succeeds, then it is correct to answer
“no”, because $q(\vec{z})$ has no id-set; otherwise answer “yes”. The
correctness follows from Proposition 5.1: if $q(\vec{z})$ has an id-set, then
$V$ is an id-set. Therefore, if $V$ falsifies condition (II)(2) in Definition
5.2, then $V$ is not an id-set, and hence $q(\vec{z})$ has no id-set. Finally,
we note that, by construction, $V$ will satisfy condition (II)(1) in
Definition 5.2. ∎

##  Appendix C Proofs for Section 6

###### Proof of Lemma 6.1.

Assume $\mathbf{db}\models q(\vec{a},\vec{b},\vec{c}_{1})$ and
$\mathbf{db}\models q(\vec{a},\vec{b},\vec{c}_{2})$.

Let $M$ be a component in the attack graph of $q$. By Definition 5.2, there is
an unattacked atom $R$ in $M$ such that
$\mathcal{K}(q)\models\vec{x}\rightarrow{\mathsf{Key}}(R)$. By Lemma A.5, for
every variable $v$ occurring in $M$,
$\mathcal{K}(q)\models{\mathsf{Key}}(R)\rightarrow v$. It follows that for
every variable $v$ occurring in $M$,
$\mathcal{K}(q)\models\vec{z}\cdot\vec{x}\rightarrow v$. Since $\vec{z}$ and
$\vec{x}$ do not depend on $M$, it follows
$\mathcal{K}(q)\models\vec{z}\cdot\vec{x}\rightarrow\vec{w}$. Since
$\mathbf{db}$ is a consistent database instance, from
$\mathcal{K}(q)\models\vec{z}\cdot\vec{x}\rightarrow\vec{w}$,
$\mathbf{db}\models q(\vec{a},\vec{b},\vec{c}_{1})$, and $\mathbf{db}\models
q(\vec{a},\vec{b},\vec{c}_{2})$, it follows that $\vec{c}_{1}=\vec{c}_{2}$ by
Lemma 4.3 in [37]. ∎

######  Lemma C.1.

Let $q(\vec{z})$ be self-join free conjunctive query in $\mathsf{Cparsimony}$,
and let $\vec{x}$ be an id-set for it. Let $q^{\prime}(\vec{z},\vec{x})$ be
the query $\nexists{\vec{x}}\left[{q}\right]$. Let $\mathbf{db}$ be a database
instance, and $\vec{c}$ a tuple of constants, of size $|{\vec{z}}|$, such that
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$. Let
$\langle{\vec{d}_{1},\ldots,\vec{d}_{n}}\rangle$ be a sequence that contains
all (and only) tuples of constants $\vec{d}_{i}$, of size $|{\vec{x}}|$, such
that $\mathbf{db}\models q^{\prime}(\vec{c},\vec{d}_{i})$. There is a sequence
$\langle{\theta_{1},\ldots,\theta_{n}}\rangle$ of valuations over
${\mathsf{vars}}(q)$ such that for every $i,j\in\\{1,\dots,n\\}$, for every
atom $R\in{\mathsf{body}}(q)$:

  1. (a)

$\theta_{i}(R)\in\mathbf{db}$;

  2. (b)

$\theta_{i}(\vec{z})=\vec{c}$ and $\theta_{i}(\vec{x})=\vec{d}_{i}$; and

  3. (c)

if $\theta_{i}(R)$ and $\theta_{j}(R)$ are key-equal, then they are equal.

###### Proof.

Since $\mathbf{db}\models q^{\prime}(\vec{c},\vec{d_{i}})$ for every
$i\in\\{1,\ldots,n\\}$, there is a sequence
$\langle{\theta_{1},\ldots,\theta_{n}}\rangle$ of valuations over
${\mathsf{vars}}(q)$ such that for every $i\in\\{1,\ldots,n\\}$ and every atom
$R\in{\mathsf{body}}(q)$, conditions (a) and (b) are satisfied. Assume that
condition (c) is violated. Then there are $i,j\in\\{1,\ldots,n\\}$ such that
for some atom $R\in{\mathsf{body}}(q)$, $\theta_{i}(R)$ and $\theta_{j}(R)$
are key-equal but distinct. Let $M$ be the smallest subset of
${\mathsf{body}}(q)$ such that:

  * •

for every atom $R\in{\mathsf{body}}(q)$, if $\theta_{i}(R)$ and
$\theta_{j}(R)$ are key-equal but distinct, then $R\in M$ (hence
$M\neq\emptyset$); and

  * •

_Closure Property:_ if $M$ contains $S$ and $\theta_{i}(v)\neq\theta_{j}(v)$
for some $v\in{\mathsf{vars}}(S)$, then $M$ contains every atom of $q$ in
which $v$ occurs.

We show that $\theta_{i}$ and $\theta_{j}$ agree on every variable of
$\vec{x}$ that occurs in $M$. Assume for the sake of contradiction that some
variable $x$ of $\vec{x}$ satisfies $\theta_{i}(x)\neq\theta_{j}(x)$ and
occurs in some atom $M$. By construction of $M$, there is an atom $R_{0}$ in
${\mathsf{body}}(q)$, and a sequence of variables
$\langle{v_{1},\ldots,v_{n}}\rangle$, with $n\geq 1$, such that:

  * •

$v_{n}=x$;

  * •

for every $k\in\\{1,\ldots,n\\}$, $\theta_{i}(v_{k})\neq\theta_{j}(v_{k})$;

  * •

$\theta_{i}(R_{0})$ and $\theta_{j}(R_{0})$ are key-equal but distinct, and
$v_{1}\in{\mathsf{notKey}}(R_{0})$;

  * •

every two adjacent variables in the sequence occur together in some atom of
$M$.

Note that the sequence may reduce to $\langle{v_{1}}\rangle$ with $v_{1}=x$.
Then $\langle{v_{1},\ldots,v_{n}}\rangle$ is a path in the query graph of $q$
that uses no variable of ${\mathsf{Key}}(R_{0})$.

We show that no variable among $v_{1},\ldots,v_{n}$ is frozen. Assume for the
sake of contradiction that some $v_{k}$ is frozen ($1\leq k\leq n$). Let
$q^{*}(\vec{z},v_{k})\vcentcolon=\nexists{v_{k}}\left[{q}\right]$. Since
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$, it follows from (the
proof of) [32, Lemma 11] that for all constants $f_{1},f_{2},$ if
$\mathbf{db}\models q^{*}(\vec{c},f_{1})$ and $\mathbf{db}\models
q^{*}(\vec{c},f_{2})$, then $f_{1}=f_{2}$. Since $\mathbf{db}\models
q^{*}(\vec{c},\theta_{i}(v_{k}))$ and $\mathbf{db}\models
q^{*}(\vec{c},\theta_{j}(v_{k}))$, it follows
$\theta_{i}(v_{k})=\theta_{j}(v_{k})$, a contradiction. We conclude by
contradiction that no variable among $v_{1},\ldots,v_{n}$ is frozen.

Then $\langle{v_{1},\ldots,v_{n}}\rangle$ is a path in the query graph of $q$
between a variable of ${\mathsf{notKey}}(R_{0})$ and a variable of $\vec{x}$
that uses no variable of ${\mathsf{Key}}(R_{0})\cup{\mathsf{frozen}}(q)$.
Consequently, $\vec{x}$ violates condition (II)(2) in Definition 5.2. Then
$\vec{x}$ is not an id-set, a contradiction. We conclude by contradiction that
$\theta_{i}$ and $\theta_{j}$ agree on every variable of $\vec{x}$ that occurs
in $M$.

Assume $i<j$. Let $\theta_{j}^{*}$ be a valuation over ${\mathsf{vars}}(q)$
such that for every $v\in{\mathsf{vars}}(q)$,

$\theta_{j}^{*}(v)=\begin{cases}\theta_{i}(v)&\textnormal{if $x$ occurs in
some atom of $M$;}\\\ \theta_{j}(v)&\textnormal{otherwise.}\end{cases}$

Since $\theta_{i}$ and $\theta_{j}$ agree on every variable of $\vec{x}$ that
occurs in $M$, it follows $\theta_{j}^{*}(\vec{x})=\theta_{j}(\vec{x})$, and
thus $\theta_{j}^{*}(\vec{x})=\vec{d}_{j}$. We now argue that
$\theta_{j}^{*}(R)\in\mathbf{db}$ for every $R\in{\mathsf{body}}(q)$. We
consider two cases:

Case $R\in M$.

Then $\theta_{j}^{*}(R)=\theta_{i}(R)$, and we have that
$\theta_{i}(R)\in\mathbf{db}$;

Case $R\notin M$.

Then $\theta_{j}^{*}(R)=\theta_{j}(R)$, and we have that
$\theta_{j}(R)\in\mathbf{db}$. Note here that if some variable $u$ of
${\mathsf{vars}}(R)$ occurs in $M$, then $R\not\in M$ implies
$\theta_{i}(u)=\theta_{j}(u)$.

The sequence
$\langle{\theta_{1},\ldots,\theta_{i},\ldots,\theta_{j-1},\theta_{j}^{*},\theta_{j+1},\ldots,\theta_{n}}\rangle$
therefore still satisfies conditions (a) and (b). By our construction, for
every atom $R\in{\mathsf{body}}(q)$, if the facts $\theta_{j}^{*}(R)$ and
$\theta_{i}(R)$ are key-equal, then they are equal. By repeatedly removing
primary-key violations in this way, we eventually obtain a sequence that also
satisfies (c). Note that our procedure will not be trapped in an infinite
loop, because whenever two distinct key-equal facts have to be made equal, say
$\theta_{i}(R)$ and $\theta_{j}(R)$, then only the valuation with the larger
index will be modified. This means that $\theta_{1}$ will never be modified;
$\theta_{2}$ will only be modified with respect to $\theta_{1}$; and so on. ∎

We can now give the proof of Lemma 6.2.

###### Proof of Lemma 6.2.

Let $\langle{\vec{d}_{1},\ldots,\vec{d}_{n}}\rangle$ be a sequence that
contains all (and only) tuples of constants $\vec{d}_{i}$, of size
$|{\vec{x}}|$, such that $\mathbf{db}\models q^{\prime}(\vec{c},\vec{d}_{i})$.

By Lemma C.1, there is a sequence
$\langle{\theta_{1},\ldots,\theta_{n}}\rangle$ of valuations over
${\mathsf{vars}}(q)$ such that for every $i,j\in\\{1,\dots,n\\}$, for every
atom $R\in{\mathsf{body}}(q)$:

  1. (a)

$\theta_{i}(R)\in\mathbf{db}$;

  2. (b)

$\theta_{i}(\vec{z})=\vec{c}$ and $\theta_{i}(\vec{x})=\vec{d}_{i}$; and

  3. (c)

if $\theta_{i}(R)$ and $\theta_{j}(R)$ are key-equal, then
$\theta_{i}(R)=\theta_{j}(R)$.

From the last property, it follows that there is a repair $\mathbf{r}$ of
$\mathbf{db}$ such that for every $i\in\\{1,\ldots,n\\}$, for every atom
$R\in{\mathsf{body}}(q)$, we have $\theta_{i}(R)\in\mathbf{r}$. Since
$\mathbf{r}\models q^{\prime}(\vec{c},\vec{d}_{i})$ for every
$i\in\\{1,\ldots,n\\}$, the repair $\mathbf{r}$ is an optimistic repair of
$\mathbf{db}$ with respect to
${q^{\prime}(\vec{z},\vec{x})}_{[{\vec{z}}\rightarrow{\vec{c}}]}$. ∎

Finally, we show Lemma 6.3.

###### Proof of Lemma 6.3.

From [29], it follows that whenever $\vec{x}$ is a sequence of unattacked
variables of a self-join-free Boolean conjunctive query, then every database
instance $\mathbf{db}$ has a repair $\mathbf{r}$ such that for every sequence
$\vec{d}$ of constants, of arity $|{\vec{x}}|$,
$\mathbf{r}\models{q}_{[{\vec{x}}\rightarrow{\vec{d}}]}$ implies
$\mathbf{db}\models_{\mathsf{\tiny
cqa}}{q}_{[{\vec{x}}\rightarrow{\vec{d}}]}$. The proof is now straightforward
by using that all variables of an id-set are unattacked (by item (b) in Lemma
B.3), and that free variables can be treated as constants. ∎

##  Appendix D Proofs for Section 7

######  Lemma D.1.

Let $q^{*}(\vec{z},\vec{x},\vec{w})$ be a full self-join-free conjunctive
query. Let $q^{\prime}(\vec{z},\vec{x})=\exists{\vec{w}}\left[{q^{*}}\right]$
and $q(\vec{z})=\exists{\vec{x}}\left[{q^{\prime}}\right]$. If there exists a
consistent database instance $\mathbf{db}$ such that $\mathbf{db}\models
q(\vec{a},\vec{b},\vec{c_{1}})$ and $\mathbf{db}\models
q(\vec{a},\vec{b},\vec{c_{2}})$ with $c_{1}\neq c_{2}$, then $q(\vec{z})$ does
not admit parsimonious counting on $\vec{x}$. Here, $\vec{a}$, $\vec{b}$,
$\vec{c}_{1}$, and $\vec{c}_{2}$ are understood to be tuples of constants,
where $\vec{a}$ is of arity $|{\vec{z}}|$, $\vec{b}$ of arity $|{\vec{y}}|$,
and $\vec{c_{i}}$ of arity $|{\vec{z}}|$ for $i\in\\{1,2\\}$.

###### Proof.

Let $\mathbf{db}$ be a consistent database instance such that
$\mathbf{db}\models q(\vec{a},\vec{b},\vec{c_{1}})$ and $\mathbf{db}\models
q(\vec{a},\vec{b},\vec{c_{2}})$ with $c_{1}\neq c_{2}$. Let $D$ be the active
domain of $\mathbf{db}$. Define:

$\displaystyle\mathcal{D}$ $\displaystyle\vcentcolon=$
$\displaystyle\\{\vec{b}\in D^{|{\vec{x}}|}\mid\mathbf{db}\models
q^{\prime}(\vec{a},\vec{b})\\},$ $\displaystyle\mathcal{D}^{*}$
$\displaystyle\vcentcolon=$ $\displaystyle\\{\vec{b}\cdot\vec{c}\in
D^{|{\vec{x}}|}\cdot D^{|{\vec{w}}|}\mid\mathbf{db}\models
q^{*}(\vec{a},\vec{b},\vec{c})\\}.$

Clearly, for every $\vec{b}\in\mathcal{D}$, there exists $\vec{c}\in
D^{|{\vec{w}}|}$ such that $\vec{b}\cdot\vec{c}\in\mathcal{D}^{*}$. Therefore,
$|{\mathcal{D}}|\leq|{\mathcal{D}^{*}}|$. Moreover, from $\mathbf{db}\models
q^{*}(\vec{a},\vec{b},\vec{c}_{1})$ and $\mathbf{db}\models
q^{*}(\vec{a},\vec{b},\vec{c}_{2})$, it follows
$|{\mathcal{D}}|<|{\mathcal{D}^{*}}|$. The query
${\mathbf{cnt}}({q^{*}},{\vec{z}})$ on $\mathbf{db}$ returns
$(\vec{a},|{\mathcal{D}^{*}}|)$. Since $\mathbf{db}$ is consistent, the query
${\mathbf{cqacnt}}({q^{*}},{\vec{z}})$ on $\mathbf{db}$ returns
$(\vec{a},[|{\mathcal{D}^{*}}|,|{\mathcal{D}^{*}}|])$. From
$|{\mathcal{D}}|\neq|{\mathcal{D}^{*}}|$, it is correct to conclude that
$q(\vec{z})$ does not admit parsimonious counting on $\vec{x}$. ∎

###### Proof of Lemma 7.2.

The proof is by contraposition. Assume that the attack graph of
$q^{\prime}(\vec{z},\vec{x})$ has a strong attack. We can assume atoms $R$ and
$S$ such that the attack graph of $q^{\prime}(\vec{z},\vec{x})$ has a strong
attack from $R$ to $S$. Let $\theta,\mu$ be two valuations over
${\mathsf{vars}}(q)$ such that for every variable $u\in{\mathsf{vars}}(q)$,

$\theta(u)=\mu(u)$ if and only if
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\rightarrow u$. (7)

Since $\mathcal{K}(q^{\prime})$ contains
$\emptyset\rightarrow{\mathsf{free}}(q)$ by definition, we have
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\rightarrow{\mathsf{Key}}(R)\cup{\mathsf{free}}(q)$
by Armstrong’s augmentation axiom. Consequently, if
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\cup{\mathsf{free}}(q)\rightarrow
u$, then $\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\rightarrow u$ (the
converse is obvious). Thus,
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\rightarrow u$ if and only if
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\cup{\mathsf{free}}(q)\rightarrow
u$.

Let $\mathbf{db}=\theta({\mathsf{body}}(q))\cup\mu({\mathsf{body}}(q))$. We
show that $\mathbf{db}$ is a consistent database instance, i.e., whenever two
facts in $\mathbf{db}$ are key-equal, then they are equal. Since $q^{\prime}$
is self-join-free, it suffices to consider any atom $F$ in
${\mathsf{body}}(q)$ such that for every $u\in{\mathsf{Key}}(F)$,
$\theta(u)=\mu(u)$. By Eq. (7), it follows
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\rightarrow{\mathsf{Key}}(F)$.
Since $\mathcal{K}(q^{\prime})$ contains
${\mathsf{Key}}(F)\rightarrow{\mathsf{vars}}(F)$, it follows
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\rightarrow{\mathsf{vars}}(F)$
by Armstrong’s transitivity axiom. By Eq. (7), $\theta(F)=\mu(F)$.

Let $\vec{w}$ be a tuple of the bound variables of
$q^{\prime}(\vec{z},\vec{x})$, and let
$q^{*}(\vec{z},\vec{x},\vec{w})=\nexists{\vec{w}}\left[{q^{\prime}}\right]$.
Since
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\rightarrow{\mathsf{free}}(q)$,
we have $\theta(\vec{z})=\mu(\vec{z})$ and $\theta(\vec{x})=\mu(\vec{x})$ by
Eq. (7). Since the attack from $R$ to $S$ is strong, there exists
$v\in{\mathsf{Key}}(S)$ such that
$\mathcal{K}(q^{\prime})\not\models{\mathsf{Key}}(R)\rightarrow v$, and hence
$\theta(v)\neq\mu(v)$ by Eq. (7). Since $v$ is necessarily in $\vec{w}$, we
have $\theta(\vec{w})\neq\mu(\vec{w})$. Let
$\vec{a}=\theta(\vec{z})=\mu(\vec{z})$,
$\vec{b}=\theta(\vec{x})=\mu(\vec{x})$, $\vec{c_{1}}=\theta(\vec{w})$, and
$\vec{c_{2}}=\mu(\vec{w})$. Thus, $\vec{c}_{1}\neq\vec{c}_{2}$. Clearly,
$\mathbf{db}\models q^{*}(\vec{a},\vec{b},\vec{c}_{1})$ and
$\mathbf{db}\models q^{*}(\vec{a},\vec{b},\vec{c}_{2})$. By Lemma D.1, it is
correct to conclude that $q(\vec{z})$ does not admit parsimonious counting on
$\vec{x}$. ∎

###### Proof of Lemma 7.3.

The proof is by contraposition. Assume that $\vec{x}$ does not satisfy
condition (II)(1) in Definition 5.2. We can assume that the attack graph of
$q(\vec{z})$ contains an unattacked atom $S$ such that
$\mathcal{K}(q)\not\models\vec{x}\rightarrow{\mathsf{Key}}(S)$. Let
$\theta,\mu$ be two valuations over ${\mathsf{vars}}(q)$ such that for every
variable $u\in{\mathsf{vars}}(q)$,

$\theta(u)=\mu(u)$ if and only if $\mathcal{K}(q)\models\vec{x}\rightarrow u$.
(8)

Let $\mathbf{db}=\theta({\mathsf{body}}(q))\cup\mu({\mathsf{body}}(q))$. It
can be seen that $\mathbf{db}$ is consistent; the reasoning is similar to that
in the proof of Lemma 7.2.

Let $\vec{w}$ be a tuple of the bound variables of
$q^{\prime}(\vec{z},\vec{x})$, and let
$q^{*}(\vec{z},\vec{x},\vec{w})=\nexists{\vec{w}}\left[{q^{\prime}}\right]$.
Since $\mathcal{K}(q)\models\vec{x}\rightarrow\vec{x}\cdot\vec{z}$, we have
$\theta(\vec{z})=\mu(\vec{z})$ and $\theta(\vec{x})=\mu(\vec{x})$ by Eq. (8).
Since $\mathcal{K}(q)\not\models\vec{x}\rightarrow{\mathsf{Key}}(S)$, there
exists $v\in{\mathsf{Key}}(S)$ such that
$\mathcal{K}(q)\not\models\vec{x}\rightarrow v$, and hence
$\theta(v)\neq\mu(v)$ by Eq. (8). Since $v$ is necessarily in $\vec{w}$, we
have $\theta(\vec{w})\neq\mu(\vec{w})$. Let
$\vec{a}=\theta(\vec{z})=\mu(\vec{z})$,
$\vec{b}=\theta(\vec{x})=\mu(\vec{x})$, $\vec{c_{1}}=\theta(\vec{w})$, and
$\vec{c_{2}}=\mu(\vec{w})$. Thus, $\vec{c}_{1}\neq\vec{c}_{2}$. Clearly,
$\mathbf{db}\models q^{*}(\vec{a},\vec{b},\vec{c}_{1})$ and
$\mathbf{db}\models q^{*}(\vec{a},\vec{b},\vec{c}_{2})$. By Lemma D.1, it is
correct to conclude that $q(\vec{z})$ does not admit parsimonious counting on
$\vec{x}$. ∎

###### Proof of Lemma 7.5.

We can assume an atom $R$ in $q(\vec{z})$ such that the query graph contains a
path $\pi=\langle{v_{1},v_{2},\ldots,v_{n}}\rangle$ from some variable $v_{1}$
in ${\mathsf{notKey}}(R)$ to a variable $v_{n}$ in $\vec{x}$ such that
$v_{1},\ldots,v_{n}\notin{\mathsf{Key}}(R)\cup{\mathsf{frozen}}(q)$. Let
$U=\\{u\in{\mathsf{vars}}(q)\mid\mathcal{K}(q)\models\emptyset\rightarrow
u\\}$. We distinguish two cases.

Case that $v_{1},\ldots,v_{n}\notin U$.

Let $\theta,\mu,\gamma$ be three valuations over ${\mathsf{vars}}(q)$ such
that for every variable $u\in{\mathsf{vars}}(q)$,

$\displaystyle\theta(u)\neq\mu(u)$ if and only if $\displaystyle
u\in\\{v_{1},\dots,v_{n}\\};$ (9) $\displaystyle\gamma(u)=\theta(u)$ if and
only if $\displaystyle u\in U;$ (10) $\displaystyle\gamma(u)=\mu(u)$ if and
only if $\displaystyle u\in U.$ (11)

We have that ${\mathsf{vars}}(\vec{z})\subseteq U$. The valuations are well-
defined because $v_{1},\ldots,v_{n}\notin U$. Moreover, we can choose
$\gamma(\vec{z})=\vec{c}$, as follows:

$\begin{array}[]{|*{10}{c}c}\lx@intercol\hfil\hfil\lx<EMAIL_ADDRESS>of
$U$}}\hfil\lx<EMAIL_ADDRESS><EMAIL_ADDRESS>v_{1}&\dotsm&v_{n}&\vec{z}&v_{n+1}&\dotsm&v_{m}&v_{m+1}&\dotsm&v_{\ell}\\\
\cline{1-10}\cr 0&\dotsm&0&\vec{c}&0&\dotsm&0&0&\dotsm&0&(\theta)\\\
1&\dotsm&1&\vec{c}&0&\dotsm&0&0&\dotsm&0&(\mu)\\\
2&\dotsm&2&\vec{c}&0&\dotsm&0&2&\dotsm&2&(\gamma)\end{array}$

Let
$\mathbf{db}=\theta({\mathsf{body}}(q))\cup\mu({\mathsf{body}}(q))\cup\gamma({\mathsf{body}}(q))$.
We show that every repair of $\mathbf{db}$ includes
$\gamma({\mathsf{body}}(q))$, and hence $\mathbf{db}\models_{\mathsf{\tiny
cqa}}q(\vec{c})$. To this end, let $F$ be an atom of $q$. If
${\mathsf{Key}}(F)\nsubseteq U$, then by Eq. (10) and Eq. (11), $\gamma(F)$ is
key-equal to neither $\theta(F)$ nor $\mu(R)$, and, consequently, every repair
of $\mathbf{db}$ will contain $\gamma(F)$. Assume next that
${\mathsf{Key}}(F)\subseteq U$. Since $\mathcal{K}(q)$ contains
${\mathsf{Key}}(F)\rightarrow{\mathsf{vars}}(F)$, it follows that
${\mathsf{vars}}(F)\subseteq U$. Then, $\gamma(F)=\theta(F)=\mu(F)$ by Eq.
(10) and Eq. (11).

Note that $\theta(R)$ and $\mu(R)$ are key-equal, because the path $\pi$
contains no variable of ${\mathsf{Key}}(R)$. Also $\theta(R)\neq\mu(R)$,
because $v_{1}\in{\mathsf{notKey}}(R)$ and $\theta(v_{1})\neq\mu(v_{1})$. It
follows that every repair must contain either $\theta(R)$ or $\mu(R)$, but not
both.

Since $\theta(v_{n})\neq\mu(v_{n})$, we have
$\theta(\vec{x})\neq\mu(\vec{x})$. Let $\vec{b}_{\theta}=\theta(\vec{x})$ and
$\vec{b}_{\mu}=\mu(\vec{x})$. Clearly, $\mathbf{db}\models
q^{\prime}(\vec{c},\vec{b}_{\theta})$ and $\mathbf{db}\models
q^{\prime}(\vec{c},\vec{b}_{\mu})$.

Let $\mathbf{r}$ be a repair that contains $\mu(R)$, and hence
$\theta(R)\notin\mathbf{r}$. We show $\mathbf{r}\not\models
q^{\prime}(\vec{c},\vec{b_{\theta}})$. Assume for the sake of contradiction
that there is a valuation $\nu$ over ${\mathsf{vars}}(q)$ such that
$\nu({\mathsf{body}}(q))\subseteq\mathbf{r}$ and
$\nu(\vec{x})=\vec{b}_{\theta}$. We have that $\nu$ maps the sequence $\pi$ to
$\langle{\nu(v_{1}),\dots,\nu(v_{n})}\rangle$. We have
$\nu(v_{n})=\theta(v_{n})$. Since every two adjacent variables occur together
in some atom, it follows from Eq. (9) that $\nu(v_{1})=\theta(v_{1})$, hence
$\nu(R)=\theta(R)$, a contradiction. We conclude by contradiction that
$\mathbf{r}\not\models q^{\prime}(\vec{c},\vec{b_{\theta}})$. By similar
reasoning, for a repair $\mathbf{r}$ that contains $\theta(R)$, we have
$\mathbf{r}\not\models q^{\prime}(\vec{c},\vec{b_{\mu}})$. It follows that for
every repair $\mathbf{r}$ of $\mathbf{db}$, either $\mathbf{r}\not\models
q^{\prime}(\vec{c},\vec{b_{\theta}})$ or $\mathbf{r}\not\models
q^{\prime}(\vec{c},\vec{b_{\mu}})$.

Case that $\\{v_{1},\ldots,v_{n}\\}\cap U\neq\emptyset$.

We can assume a greatest integer $\ell\in\\{1,\dots,n\\}$ such that
$v_{\ell}\in U$. That is, $v_{\ell+1},v_{\ell+2},\dots,v_{n}\notin U$. We can
assume a sequence $\sigma$ of atoms that is a sequential proof of
$\mathcal{K}(q)\models\emptyset\rightarrow v_{\ell}$. Since $v_{\ell}$ is not
frozen, there is some atom $S$ in the sequential proof $\sigma$ such that
${S}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{v_{\ell}}$, and hence
$v_{\ell}\notin{S}^{+,q}$.

We show $v_{\ell+1},\ldots,v_{n}\notin{S}^{+,q}$. Assume for the sake of
contradiction $j\in\\{\ell+1,\ldots,n\\}$ such that
$\mathcal{K}(q\setminus\\{S\\})\models{\mathsf{Key}}(S)\rightarrow v_{j}$.
Since
$\mathcal{K}(q\setminus\\{S\\})\models\emptyset\rightarrow{\mathsf{Key}}(S)$
(because $S$ occurs in the sequential proof $\sigma$), we obtain
$\mathcal{K}(q\setminus\\{S\\})\models\emptyset\rightarrow v_{j}$, hence
$v_{j}\in U$, a contradiction. Consequently, $\ell\leq n$ and
$v_{\ell},v_{\ell+1},\dots,v_{n}\notin{S}^{+,q}$.

Let $\theta$, $\mu$ be two valuations over ${\mathsf{vars}}(q)$ such that for
every $u\in{\mathsf{vars}}(q)$, $\theta(u)=\mu(u)$ if and only if
$u\in{S}^{+,q}$. Since ${\mathsf{vars}}(\vec{z})\subseteq{S}^{+,q}$ by
definition (even though some variables of $\vec{z}$ may not occur in
$q\setminus\\{S\\}$), we can choose $\theta(\vec{z})=\mu(\vec{z})=\vec{c}$.

Let $\mathbf{db}=\theta(q)\cup\mu(q)$. The only facts in $\mathbf{db}$ that
are key-equal but distinct are $\theta(S)$ and $\mu(S)$. Note here that since
$S$ attacks some variable, there is a variable of ${\mathsf{notKey}}(S)$ that
is not in ${S}^{+,q}$. Consequently, $\mathbf{db}$ has exactly two repairs,
denoted $\mathbf{r}_{1}\vcentcolon=\mathbf{db}\setminus\\{\mu(S)\\}$ and
$\mathbf{r}_{2}\vcentcolon=\mathbf{db}\setminus\\{\theta(S)\\}$.

Let $\vec{d}_{1}=\theta(\vec{x})$ and $\vec{d}_{2}=\mu(\vec{x})$. Since
$v_{n}\notin{S}^{+,q}$, we have $\theta(v_{n})\neq\mu(v_{n})$. Since
$v_{n}\in{\mathsf{vars}}(\vec{x})$, $\vec{d}_{1}\neq\vec{d}_{2}$. For the
query
$q^{\prime}(\vec{z},\vec{x})\vcentcolon=\nexists{\vec{x}}\left[{q}\right]$, we
obviously have $\mathbf{db}\models q^{\prime}(\vec{c},\vec{d}_{1})$ and
$\mathbf{db}\models q^{\prime}(\vec{c},\vec{d}_{2})$. Using the same proof as
[37, Proposition 6.4], we have $\mathbf{r}_{1}\models
q^{\prime}(\vec{c},\vec{d}_{1})$ and $\mathbf{r}_{1}\not\models
q^{\prime}(\vec{c},\vec{d}_{2})$. Symmetrically, $\mathbf{r}_{2}\not\models
q^{\prime}(\vec{c},\vec{d}_{1})$ and $\mathbf{r}_{2}\models
q^{\prime}(\vec{c},\vec{d}_{2})$. Clearly, $\mathbf{db}\models_{\mathsf{\tiny
cqa}}q(\vec{c})$.

In both cases, there is a database $\mathbf{db}$ such that
$\mathbf{db}\models_{\mathsf{\tiny cqa}}q(\vec{c})$, and $\mathbf{db}$ has no
optimistic repair with respect to
${q^{\prime}}_{[{\vec{z}}\rightarrow{\vec{c}}]}$. ∎

######  Lemma D.2.

Let $q(\vec{z})$ be a self-join-free conjunctive query. Let $\vec{x}$ be a
sequence of distinct bound variables of $q(\vec{z})$. Let
$q^{\prime}(\vec{z},\vec{x})=\nexists{\vec{x}}\left[{q}\right]$. Let
$Y\cup\\{w\\}$ be a set of bound variables of $q(\vec{z})$. If
$\mathcal{K}(q)\not\models Y\rightarrow w$ and $\mathcal{K}(q^{\prime})\models
Y\rightarrow w$, then there is a path in the query graph of $q$ between some
variable of $\vec{x}$ and $w$ such that for every variable $u$ on the path,
$\mathcal{K}(q)\not\models Y\rightarrow u$.

###### Proof.

Assume $\mathcal{K}(q)\not\models Y\rightarrow w$ and
$\mathcal{K}(q^{\prime})\models Y\rightarrow w$. It is easily verified that
$\mathcal{K}(q^{\prime})\equiv\mathcal{K}(q)\cup\\{\emptyset\rightarrow\vec{x}\\}$.
From $\mathcal{K}(q^{\prime})\models Y\rightarrow w$, it follows
$\mathcal{K}(q)\models Y\cup\vec{x}\rightarrow w$. Let
$U=\\{u\in{\mathsf{vars}}(q)\mid\mathcal{K}(q)\models Y\rightarrow u\\}$.
Clearly, $Y\cup{\mathsf{free}}(q)\subseteq U$ and $w\not\in U$. If
$w\in{\mathsf{vars}}(\vec{x})$, then the empty path between $w$ and $w$ is a
path between some variable of $\vec{x}$ and $w$ that uses no variable of $U$,
and the desired result obtains. From here on, assume
$w\notin{\mathsf{vars}}(\vec{x})$. We can assume a sequence of atoms
$\langle{F_{1},\ldots,F_{n}}\rangle$ that is a minimal sequential proof of
$\mathcal{K}(q)\models Y\cup\vec{x}\rightarrow w$. Note that
$w\in{\mathsf{notKey}}(F_{n})$. Let $M$ be a minimal subset of
$\\{F_{1},\ldots,F_{n}\\}$ such that:

  * •

$F_{n}\in M$; and

  * •

for all $i,j\in\\{1,\ldots,n-1\\}$ such that $i<j$, if $F_{j}\in M$ and some
variable of ${\mathsf{Key}}(F_{j})\setminus U$ occurs in $F_{i}$, then
$F_{i}\in M$.

By construction of $M$, if some variable of $\vec{x}$ occurs in $M$, then
there is a path in the query graph between a variable of $\vec{x}$ and $w$
that uses no variable in $U$, and hence the desired result obtains. Therefore,
to conclude the proof, it suffices to show that some variable of $\vec{x}$
occurs in $M$.

Assume for the sake of contradiction that no variable of $\vec{x}$ occurs in
$M$. By construction of $M$, it holds that for every atom $F_{j}\in M$, for
every variable $v$ in ${\mathsf{Key}}(F_{j})$, either $v\in U$, or $v$ appears
in some other atom $F_{i}\in M$ with $i<j$. Consequently, if we restrict
$\langle{F_{1},\ldots,F_{n}}\rangle$ to the atoms of $M$, we obtain a
sequential proof of $\mathcal{K}(q)\models U\rightarrow w$. Since
$\mathcal{K}(q)\models Y\rightarrow U$ is obvious, it is correct to conclude
$\mathcal{K}(q)\models Y\rightarrow w$, a contradiction. ∎

######  Lemma D.3.

Let $q(\vec{z})$ be a self-join-free conjunctive query. Let $\vec{x}$ be a
sequence of distinct bound variables of $q(\vec{z})$. Let
$q^{\prime}(\vec{z},\vec{x})=\nexists{\vec{x}}\left[{q}\right]$. Assume that
$\vec{x}$ satisfies condition (II)(2) in Definition 5.2 of
$\mathsf{Cparsimony}$. For all atoms $R$ and $S$ of $q$, if
${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{S}$, then
${R}\stackrel{{\scriptstyle q^{\prime}}}{{\rightsquigarrow}}{S}$.

###### Proof.

Assume that ${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{S}$. We can
assume a witness $\langle{v_{1},\ldots,v_{n}}\rangle$ that $R$ attacks $S$ in
$q(\vec{z})$. Clearly, for every $i\in\\{1,\dots,n\\}$, we have
$v_{i}\notin{\mathsf{Key}}(R)$, and, by Lemma B.2,
$v_{i}\notin{\mathsf{frozen}}(q)$. Assume for the sake of contradiction that
${R}\stackrel{{\scriptstyle q^{\prime}}}{{\not\rightsquigarrow}}{S}$. It
suffices to show that $\vec{x}$ does not satisfy condition (II)(2) in
Definition 5.2, which is a contradiction with the lemma’s hypothesis.

Since $\langle{v_{1},\ldots,v_{n}}\rangle$ is not a witness that $R$ attacks
$S$ in $q^{\prime}(\vec{z},\vec{x})$, we can assume some
$i\in\\{1,\ldots,n\\}$ such that $v_{i}\notin{R}^{+,q}$ and
$v_{i}\in{R}^{+,q^{\prime}}$. Consequently,
$\mathcal{K}(q\setminus\\{R\\})\not\models{\mathsf{Key}}(R)\rightarrow v_{i}$
and
$\mathcal{K}(q^{\prime}\setminus\\{R\\})\models{\mathsf{Key}}(R)\rightarrow
v_{i}$. By Lemma D.2, we can assume that the query graph of
$q\setminus\\{R\\}$ has a path $\pi=\langle{x,\ldots,v_{i}}\rangle$ between
some variable $x$ in
${\mathsf{vars}}(\vec{x})\cap{\mathsf{vars}}(q^{\prime}\setminus\\{R\\})$ and
$v_{i}$ such that for every variable $u\in{\mathsf{vars}}(\pi)$, we have
$\mathcal{K}(q\setminus\\{R\\})\not\models{\mathsf{Key}}(R)\rightarrow u$.
Since ${\mathsf{vars}}(\pi)\cap{R}^{+,q}=\emptyset$ and
${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{v_{i}}$, it follows that
${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{u}$ for every
$u\in{\mathsf{vars}}(\pi)$. From Lemma B.2, it follows
${\mathsf{vars}}(\pi)\cap{\mathsf{frozen}}(q)=\emptyset$.

Then, the path $\pi\cdot\langle{v_{i-1},v_{i-2},\ldots v_{1}}\rangle$ is a
path in the query graph of $q$ between a variable of $\vec{x}$ and a variable
of ${\mathsf{notKey}}(R)$ that uses no variable of
${\mathsf{Key}}(R)\cup{\mathsf{frozen}}(q)$. It follows that $\vec{x}$
violates condition (II)(2) in Definition 5.2 of $\mathsf{Cparsimony}$. ∎

The statement of Lemma 7.6 is almost identical to Lemma D.3; the only
difference is that it deals with strong attacks.

###### Proof of Lemma 7.6.

Assume that $\vec{x}$ satisfies condition (II)(2) in Definition 5.2. The proof
is by contraposition: we assume that the attack graph of