# Consistent Query Answering for Existential Rules under Tuple-Deletion
Semantics

Lorenzo Marconi<EMAIL_ADDRESS>
Sapienza Università di Roma, Rome, Italy Riccardo Rosati
<EMAIL_ADDRESS>
Sapienza Università di Roma, Rome, Italy

###### Abstract

We study consistent query answering over knowledge bases expressed by
existential rules. Specifically, we establish the data complexity of
consistent query answering and repair checking under tuple-deletion semantics
for a general class of disjunctive existential rules and for several
subclasses thereof (acyclic, linear, full, guarded, and sticky). In
particular, we identify several cases in which the above problems are
tractable or even first-order rewritable, and present new query rewriting
techniques that can be the basis for practical inconsistency-tolerant query
answering systems.

##  1 Introduction

_Consistent query answering_ (?) is an approach to inconsistency-tolerant
reasoning in databases and knowledge bases (KBs). The central notion of
consistent query answering is the one of _repair_. Given an _inconsistent_
database or KB $\mathcal{K}$, a repair of $\mathcal{K}$ is a consistent
database or KB that is “maximally close” to the initial $\mathcal{K}$. Several
distinct formalizations of the above notions of maximality and inconsistency
are possible, giving rise to different repair semantics.

In most of these semantics, many different repairs for the same database or KB
may exist. The problem of consistent query answering is, given a query $q$, to
compute the answers to $q$ that are true in every repair of the
database/knowledge base. Also the _repair checking_ problem is often
considered, that is, the problem of deciding whether a database or KB
$\mathcal{K}^{\prime}$ is a repair of a database or KB $\mathcal{K}$.

Consistent query answering was originally defined for relational databases
(?), but it has then been studied in the context of Description Logics
knowledge bases (see e.g. (?, ?, ?)) and rule knowledge bases, in particular
knowledge bases with _existential rules_ (?, ?, ?, ?, ?): such KBs consist of
an extensional database (set of ground atoms) and a set of first-order
implications. This is the framework studied in the present paper.

Specifically, we consider a very expressive class of existential rules that
comprises and extends both disjunctive tuple-generating dependencies (DTGDs)
and equality-generating dependencies (EGDs), the most studied forms of
existential rules studied in the literature. Specifically, the rules that we
consider in this paper correspond to the so-called _disjunctive embedded
dependencies with inequalities (DEDs)_ (?, ?, ?). We also consider five
subclasses of these dependencies, corresponding to some of the most important
subclasses studied in the literature on existential rules, i.e. the classes of
_acyclic_ , _full_ , _guarded_ , _linear_ , and _sticky_ existential rules (?,
?, ?).

Concerning the semantics, we adopt a _closed_ interpretation of the
predicates, and therefore the well-known _tuple-deletion_ semantics for
repairs (?, ?, ?, ?): a repair is a maximal (w.r.t. set inclusion) subset of
the initial database that satisfies the rules.

Then, we analyze the most important decision problems studied in consistent
query answering, that is, the query entailment problem and the repair checking
problem. For query entailment, we consider the language of Boolean unions of
conjunctive queries with inequalities (BUCQs), and analyze two different
notions of inconsistency-tolerant entailment: _AR-entailment_ , i.e.,
skeptical entailment over all the repairs, and _IAR-entailment_ , i.e.,
entailment over the intersection of all the repairs. Notably, IAR-entailment
corresponds to a sound approximation of AR-entailment.

We study the complexity of the above problems, providing a comprehensive
analysis of the data complexity (that is, the complexity with respect to the
size of the database) of repair checking and both AR-entailment and IAR-
entailment of BUCQs, for all the possible combinations of the five classes of
existential rules considered in this paper. The results are summarized in
Table 1.

Despite consistent query answering being well-known to be a computationally
hard task, our results identify many interesting classes of existential rules
in which the problems of consistent query answering and repair checking are
tractable in data complexity. Moreover, for most of these tractable classes of
existential rules we prove the _first-order rewritability_ property of the
problems studied, i.e. each of these problems can be reduced to the evaluation
of a first-order sentence over the database. This property is very interesting
not only from the theoretical viewpoint, but also towards the definition of
practical algorithms for consistent query answering based on first-order
rewriting methods, in a way similar to the case of classical query answering
(see e.g. (?, ?)).

The closest work to the present paper is (?), which presents an exhaustive
study of the complexity of consistent query answering over existential rules.
That paper inherits the open-world assumption adopted by the recent approaches
to existential rules, in which the interpretation of all predicates is open,
thus repairing an inconsistency between the database and the rules is
preferably done by (virtually) adding tuples to the initial database (that is,
tuple deletions are considered only if tuple additions can not repair the
data). Conversely, our approach adopts a closed-world assumption, in which all
predicates are closed and the only way to repair an inconsistency is through
tuple deletions. Given this semantic discrepancy, the problems studied in the
two papers are actually different, so our results can be seen as complementary
to the ones presented in (?) (see also the conclusions). We also remark that
both the language for existential rules and the query language considered
there are less expressive than the ones (disjunctive dependencies and unions
of conjunctive queries with inequalities) studied in the present paper.

The paper is structured as follows. We first introduce preliminary notions and
definitions (Section 2), as well as the notion of repair and the decision
problems that we focus on (Section 3). Then, we provide complexity results for
such problems, namely repair checking (Section 4), IAR-entailment (Section 5)
and AR-entailment (Section 6). In Section 7 we discuss our results and
conclude the paper.

Due to space limitations, the complete proofs of some theorems can be found in
the Appendix.

##  2 Databases, Dependencies and Queries

Syntax We call _predicate signature_ (or simply _signature_) a set of
predicate symbols with an associated arity. A _term_ is either a variable
symbol or a constant symbol. A _predicate atom_ (or simply _atom_) is an
expression of the form $p(\mathbf{t})$, where $p$ is a predicate of arity $n$
and $\mathbf{t}$ is a $n$-tuple of terms. We say that an atom $\alpha$ is
ground (or that $\alpha$ is a fact) if no variable occur in it. An _inequality
atom_ (or just _inequality_) is an expression of the form $t\neq t^{\prime}$,
where $t$ and $t^{\prime}$ are terms.

Given a predicate signature $\mathcal{S}$, a _DB instance_ (or simply
_database_) $\mathcal{D}$ for $\mathcal{S}$ is a set of facts over the
predicates of $\mathcal{S}$. W.l.o.g. we assume that a signature always
contains the special predicate $\bot$ of arity 0, and that no database
contains the fact $\bot$.

A _conjunction with inequalities_ $\gamma$ is a conjunction of predicate atoms
and inequality atoms of the form

$\alpha_{1}\wedge\ldots\wedge\alpha_{k}\wedge\lambda_{1}\wedge\ldots\wedge\lambda_{h}$
(1)

where $k\geq 0$, $h\geq 0$, $k+h\geq 1$, every $\alpha_{i}$ is a predicate
atom and every $\lambda_{i}$ is an inequality. We denote by
$\textit{Vars}(\gamma)$ the variables occurring in $\gamma$, by
$\textit{PA}(\gamma)$ the predicate atoms occurring in $\gamma$, and by
$\textit{Ineq}(\gamma)$ the subformula
$\lambda_{1}\wedge\ldots\wedge\lambda_{h}$. For a set of atoms $\mathcal{A}$,
we also define
$\textit{Vars}(\mathcal{A})=\bigcup_{\alpha\in\mathcal{A}}\textit{Vars}(\alpha)$.

######  Definition 1 (CQ and BCQ).

A _conjunctive query with inequalities (CQ)_ $q$ is a first-order (FO) formula
of the form $\exists\mathbf{y}\,(\gamma)$, where $\gamma$ is a conjunction
with inequalities and $\mathbf{y}$ is a sequence of variables each of which
occur in at least one atom. We also define
$\textit{Vars}(q)=\textit{Vars}(\gamma)$, $\textit{PA}(q)=\textit{PA}(\gamma)$
and $\textit{Conj}(q)=\gamma$. If every variable of $q$ occur in at least one
predicate atom, we say that $q$ is a _safe_ CQ. Moreover, if no variable of
$q$ is free (i.e., all such variables occur in $\mathbf{y}$), we say that $q$
is a _Boolean CQ (BCQ)_.

######  Definition 2 (UCQ and BUCQ).

A _union of conjunctive queries with inequalities (UCQ)_ $Q$ is an FO formula
of the form $\bigvee_{i=1}^{m}q_{i}$, where $m\geq 1$ and every $q_{i}$ is a
CQ. We denote by $\textit{CQ}(Q)$ the set of CQs occurring in $Q$, i.e.
$\textit{CQ}(Q)=\\{q_{1},\ldots,q_{m}\\}$, and we also define
$\textit{Vars}(Q)=\bigcup_{q\in\textit{CQ}(Q)}\textit{Vars}(q)$. If all CQs
$q_{i}$ are safe, we say that $Q$ is a _safe_ UCQ. Moreover, if all CQs
$q_{i}$ are Boolean, we say that $Q$ is a _Boolean UCQ (BUCQ)_.

Given a UCQ $Q$ with free variables $\mathbf{x}$, and given a tuple of
constants $\mathbf{t}$ of the same arity as $\mathbf{x}$, we denote by
$Q(\mathbf{t})$ the BUCQ obtained from $Q$ by replacing all the occurrences of
free variables with the constants in $\mathbf{t}$.

We are now ready to define the notion of dependency that we will use
throughout the paper.111Although slightly different, Definition 3 is actually
equivalent to the notion of disjunctive embedded dependency with inequalities
_and equalities_ presented in (?, ?).

######  Definition 3 (Dependency).

Given a predicate signature $\mathcal{S}$, a _disjunctive embedded dependency
with inequalities_ (or simply _dependency_) for $\mathcal{S}$ is an FO
sentence over the predicates of $\mathcal{S}$ of the form:

$\forall\mathbf{x}\,\big{(}\gamma\rightarrow Q\big{)}$ (2)

where $\mathbf{x}$ is a sequence of variables such that
$\exists\mathbf{x}\,(\gamma)$ is a safe BCQ, and $Q$ is a UCQ whose free
variables occur in $\mathbf{x}$ and such that $Q(\mathbf{t})$ is a safe BUCQ,
where $\mathbf{t}$ is any tuple of constants of the same arity as
$\mathbf{x}$.

For a dependency $\tau$ of form (2), we indicate with $\textit{body}(\tau)$
the formula $\gamma$, with $\textit{head}(\tau)$ the UCQ $Q$, and with
$\textit{PA}_{b}(\tau)$ the set $\textit{PA}(\gamma)$. Moreover, we say that
$\tau$ is _non-disjunctive_ if $m=1$, i.e. $\textit{head}(\tau)$ is a CQ $q$,
and that $\tau$ is _single-head_ if it is non-disjunctive and
$|\textit{PA}(\textit{head}(\tau))|=1$. In the rest of the paper, we will omit
that databases and dependencies are given for a certain signature.

Semantics Dependencies and safe BUCQs are subclasses of the class of domain-
independent relational calculus formulas (?). Given a domain-independent
sentence $\phi$ of the relational calculus and a set of facts $\mathcal{D}$
over the same signature, we write $\mathcal{D}\models\phi$ if the evaluation
of $\phi$ over $\mathcal{D}$ is true. Given a database $\mathcal{D}$ and a
dependency $\tau$, we say that $\tau$ is _satisfied in $\mathcal{D}$_ iff
$\mathcal{D}\models\tau$. Given a database $\mathcal{D}$ and a set of
dependencies $\Sigma$, we say that $\mathcal{D}$ is _consistent with $\Sigma$_
if all the dependencies of $\Sigma$ are satisfied in $\mathcal{D}$, i.e. if
$\mathcal{D}\models\bigwedge_{\tau\in\Sigma}\tau$.

Let $\gamma$ be a conjunction with inequalities of the form (1) and
$\mathcal{D}$ be a set of facts over the same signature of $\gamma$. An
_instantiation of $\gamma$ in $\mathcal{D}$_ is a substitution $\sigma$ of the
variables occurring in $\gamma$ with constants such that $(i)$
$\sigma(\alpha_{i})\in\mathcal{D}$ for every $i$ such that $1\leq i\leq k$;
$(ii)$ no inequality of the form $t\neq t$ (where $t$ is either a constant or
a variable) occurs in $\textit{Ineq}(\gamma)$. Moreover, given an
instantiation $\sigma$ of $\gamma$ in $\mathcal{D}$, we call _image of
$\gamma$ in $\mathcal{D}$_ the subset
$\\{\sigma(\alpha)\mid\alpha\in\textit{PA}(\gamma)\\}$ of $\mathcal{D}$. Given
a CQ $q$, an image of $q$ in $\mathcal{D}$ is any image of $\textit{Conj}(q)$
in $\mathcal{D}$. Given a UCQ $Q$, an image of $Q$ in $\mathcal{D}$ is any
image of $q$ in $\mathcal{D}$, where $q\in\textit{CQ}(Q)$.

We recall that the images of a BCQ with $k$ predicate atoms in a set of facts
$\mathcal{D}$ are at most $n^{k}$ (where $n$ is the cardinality of
$\mathcal{D}$) and can be computed in polynomial time w.r.t. the size of the
database.

Subclasses of dependencies We say that a dependency of the form (2) is
_linear_ in the case when $|\textit{PA}(\gamma)|=1$. Moreover, if
$|\textit{CQ}(Q)|=1$ and $\textit{Vars}(Q)\subseteq\textit{Vars}(\gamma)$,
then we say that the dependency is _full non-disjunctive_ , or simply _full_.

Given a set of dependencies $\Sigma$, we call _dependency graph_ of $\Sigma$
the directed graph $G(\Sigma)$ whose vertices are the dependencies of $\Sigma$
and such that there is one edge from the vertex $\tau_{1}$ to $\tau_{2}$ iff
the head of $\tau_{1}$ contains an atom whose predicate appears in a predicate
atom of the body of $\tau_{2}$. We say that $\Sigma$ is _acyclic_ if there is
no cyclic path in $G(\Sigma)$. Given a set of acyclic dependencies $\Sigma$,
we call _topological order of $\Sigma$_ any topological order of $G(\Sigma)$,
i.e. a sequence $\langle\tau_{1},\ldots,\tau_{h}\rangle$ of the dependencies
of $\Sigma$ such that, if $i\geq j$, then the vertex $\tau_{i}$ is not
reachable from the vertex $\tau_{j}$ in $G(\Sigma)$.

We than recall the classes of guarded and sticky dependencies. A dependency
$\tau$ is _guarded_ if there exists an atom $\alpha$ of $\textit{body}(\tau)$
such that $\textit{Vars}(\alpha)=\textit{Vars}(\textit{body}(\tau))$.
Obviously, if a set of dependencies is linear, it is also guarded. As usual,
in order to introduce the stickiness property, we need the following auxiliary
definition. Given a set of dependencies $\Sigma$, for each dependency
$\tau\in\Sigma$ we say that a variable $x$ occurring in
$\textit{body}(\tau)$222We assume w.l.o.g. that distinct dependencies use
distinct variables. is _marked_ if: $(i)$ there exists an atom of
$\textit{head}(\tau)$ in which $x$ does not occur, or $(ii)$ there exist a
dependency $\tau^{\prime}$ and a predicate $p$ such that $\textit{head}(\tau)$
and $\textit{body}(\tau^{\prime})$ contain $p(\mathbf{t})$ and
$p(\mathbf{t^{\prime}})$, respectively, and $x$ is the $i$-th variable of
$\mathbf{t}$ only if the $i$-th term of $\mathbf{t^{\prime}}$ is a marked
variable. Then, we say that $\Sigma$ is _sticky_ if, for every dependency
$\tau\in\Sigma$, every marked variable occurs in $\textit{body}(\tau)$ at most
once.

We assume the reader to be familiar with the basic notions of computational
complexity. In this paper we focus on the _data complexity_ of the problems
studied, i.e. the complexity with respect to the size of the database.

##  3 Repairs and Decision Problems

We are now ready to define the notion of repair, the different entailment
semantics and the decision problems that we study.

######  Definition 4 (Repairs).

Given a database $\mathcal{D}$ and a set of dependencies $\Sigma$, a _repair_
of $\langle\Sigma,\mathcal{D}\rangle$ is a maximal subset of $\mathcal{D}$
that is consistent with $\Sigma$.

Let us call $\mathsf{rep}_{\Sigma}(\mathcal{D})$ the set of all the possible
repairs of $\langle\Sigma,\mathcal{D}\rangle$ and let
$\mathsf{intRep}_{\Sigma}(\mathcal{D})=\bigcap_{\mathcal{D}^{\prime}\in\mathsf{rep}_{\Sigma}(\mathcal{D})}\mathcal{D}^{\prime}$.
It is immediate to see that a repair always exists for every
$\langle\Sigma,\mathcal{D}\rangle$ (since the empty database satisfies every
dependency).

The first decision problems that we define are related to two distinct notions
of entailment of formulas w.r.t. the repairs of a database.

######  Definition 5 (Entailment).

Given a database $\mathcal{D}$, a set of dependencies $\Sigma$, and a domain-
independent FO sentence $\phi$, we say that: $(i)$
_$\langle\Sigma,\mathcal{D}\rangle$ entails $\phi$ under the AR semantics_ (or
_$\langle\Sigma,\mathcal{D}\rangle$ AR-entails $\phi$_ for short) if
$\mathcal{D}^{\prime}\models\phi$ for every
$\mathcal{D}^{\prime}\in\mathsf{rep}_{\Sigma}(\mathcal{D})$; $(ii)$
_$\langle\Sigma,\mathcal{D}\rangle$ entails $\phi$ under the IAR semantics_
(or _$\langle\Sigma,\mathcal{D}\rangle$ IAR-entails $\phi$_ for short) if
$\mathsf{intRep}_{\Sigma}(\mathcal{D})\models\phi$.

It is easy to verify that, even in the presence of a single dependency with
two predicate atoms in the body, the two semantics are different.

In the rest of the paper, we will study _BUCQ entailment_ , i.e. the
entailment of safe BUCQs, under both semantics. We will call this problem
_instance checking_ in the case when the BUCQ is a fact.

The following properties, whose proof is immediate, show two important
correspondences between the AR and the IAR semantics of entailment.

######  Proposition 1.

Instance checking under the AR semantics coincides with instance checking
under the IAR semantics. Moreover, in the case of linear dependencies,
entailment under the AR semantics coincides with entailment under the IAR
semantics.

We now define another important decision problem studied in the context of
CQA. Given a set of dependencies $\Sigma$ and two databases $\mathcal{D}$ and
$\mathcal{D}^{\prime}$, we call _repair checking_ the problem of checking
whether a $\mathcal{D}^{\prime}$ is a repair of
$\langle\Sigma,\mathcal{D}\rangle$

From now on, in all the decision problems we study, we assume w.l.o.g. that
all the predicates occurring in $\mathcal{D}$ also occur in $\Sigma$.
Moreover, we denote by $\textit{Pred}(\Sigma)$ the set of predicates occurring
in $\Sigma$.

##  4 Repair Checking

In this section we study the data complexity of repair checking in the classes
of dependencies previously mentioned.

#### Lower bounds

We remark that all the lower bounds shown in this section also hold if the
dependencies are restricted to be single-head and without inequalities in the
head.

First, we prove the problem to be PTIME-hard in the case when such
dependencies are linear+sticky.

######  Theorem 1.

There exist a set of linear+sticky dependencies and a pair of databases for
which repair checking is PTIME-hard w.r.t. data complexity.

Proof (sketch).  The thesis can be proved showing a reduction from the HORN
SAT problem. ∎

Then, we extend the PTIME lower bound shown in (?, Thm 5) for full
dependencies to the case of full+guarded dependencies.

######  Theorem 2.

There exist a set of full+guarded dependencies and a pair of databases for
which repair checking is PTIME-hard w.r.t. data complexity.

Furthermore, the results provided in (?) imply that, in the general case,
repair checking is coNP-hard. We establish the same lower bound for the case
of guarded+sticky dependencies.

######  Theorem 3.

There exist a set of guarded+sticky dependencies and a pair of databases for
which repair checking is coNP-hard w.r.t. data complexity.

#### Upper bounds

As shown in (?, Proposition 4), in the general case the problem is in coNP. We
show that the problem can be solved in PTIME if the set of dependencies is
either linear or full, extending the same complexity result proved in (?, ?)
for less expressive dependencies. Moreover, we show that the problem is in
$\mathrm{AC}^{0}$ for acyclic sets of dependencies, as well as for full+linear
and full+sticky dependencies.

We first consider the case of either linear or full dependencies, for which
the following holds.

######  Theorem 4.

Repair checking is in PTIME w.r.t. data complexity in the case of either
linear or full dependencies.

We now focus on the case of acyclic dependencies, and we start by showing the
following property.

######  Proposition 2.

Let $\Sigma$ be a set of acyclic dependencies, and let $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ be two databases. Then, $\mathcal{D}^{\prime}$ is a
repair of $\langle\Sigma,\mathcal{D}\rangle$ iff $\mathcal{D}^{\prime}$ is
consistent with $\Sigma$ and, for every
$\alpha\in\mathcal{D}\setminus\mathcal{D}^{\prime}$,
$\mathcal{D}^{\prime}\cup\\{\alpha\\}$ is inconsistent with $\Sigma$.

For the case of acyclic dependencies, we now show how to decide repair
checking by means of an FO sentence. To this aim, in order to represent the
subset $\mathcal{D}^{\prime}$ of $\mathcal{D}$, we will make use of an
auxiliary alphabet that contains a predicate symbol $\accentset{\ast}{p}$ for
every $p\in\textit{Pred}(\Sigma)$ (and $\accentset{\ast}{p}$ is of the same
arity as $p$). Given a formula $\phi$, we denote by $\textit{aux}(\phi)$ the
formula obtained from $\phi$ replacing every predicate atom $p(\mathbf{t})$
with $\accentset{\ast}{p}(\mathbf{t})$, i.e. the atom obtained from
$p(\mathbf{t})$ by replacing its predicate with the corresponding predicate in
the auxiliary alphabet. Similarly, given a set of atoms $\mathcal{A}$, we
denote by $\textit{aux}(\mathcal{A})$ the set
$\\{\textit{aux}(\alpha)\mid\alpha\in\mathcal{A}\\}$.

Now we can define the formula $\Psi^{\mathit{inc}}(\Sigma)$ as follows:

$\Psi^{\mathit{inc}}(\Sigma)=\bigvee_{\tau\in\Sigma}\exists\mathbf{x}\,\big{(}\textit{aux}(\textit{body}(\tau))\wedge\neg\textit{aux}(\textit{head}(\tau))\big{)}$

where $\mathbf{x}$ contains all the variables occurring in
$\textit{body}(\tau)$. It is easy to see that such a formula returns true when
evaluated over a database $\textit{aux}(\mathcal{D})$ iff the latter is
inconsistent with $\Sigma$.

Then, we define the auxiliary formula
$\Psi^{\mathit{inc}}(\Sigma,p(\mathbf{x}))$, where $p(\mathbf{x})$ is an atom:
it is obtained from the formula $\Psi^{\mathit{inc}}(\Sigma)$ by replacing
every atom $\accentset{\ast}{p}(\mathbf{t})$ with the conjunction of
equalities $\mathbf{t}=\mathbf{x}$.

######  Definition 6 (Repair checking sentence 1).

Let $\Sigma$ be a set of acyclic dependencies. We define the formula
$\Psi^{\mathit{rc}}(\Sigma)$ as follows:

$\neg\Psi^{\mathit{inc}}(\Sigma)\wedge\bigwedge_{p\in\textit{Pred}(\Sigma)}\forall\mathbf{x}\,\big{(}p(\mathbf{x})\wedge\neg\accentset{\ast}{p}(\mathbf{x})\rightarrow\Psi^{\mathit{inc}}(\Sigma,p(\mathbf{x})\big{)}$

where $\mathbf{x}=x_{1},\ldots,x_{m}$ if $m$ is the arity of $p$.

Based on this definition and Proposition 2, it is possible to prove the
following property.

######  Theorem 5.

Let $\Sigma$ be a set of acyclic dependencies, and let $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ be two databases. Then,
$\mathcal{D}\cup\textit{aux}(\mathcal{D}^{\prime})\models\Psi^{\mathit{rc}}(\Sigma)$
iff $\mathcal{D}^{\prime}$ is a repair of $\langle\Sigma,\mathcal{D}\rangle$.

######  Corollary 1.

Repair checking is in $\mathrm{AC}^{0}$ w.r.t. data complexity in the case of
acyclic dependencies.

######  Example 1.

Let $\mathcal{D}=\\{P(a,b),P(a,c),T(a),R(d,b),\allowbreak R(e,b)\\}$ and
$\Sigma=\\{\forall x\,(P(x,y)\wedge T(x)\rightarrow\exists z\,R(z,y))\\}$.
Note that $\Sigma$ is a set of acyclic dependencies and it is neither linear
nor full. With such an input, the sentence $\Psi^{\mathit{rc}}(\Sigma)$ is
equal to:

$\begin{array}[]{l}\neg\exists
x,y\,\big{(}\accentset{\ast}{P}(x,y)\wedge\accentset{\ast}{T}(x)\wedge\neg\exists
z\,\accentset{\ast}{R}(z,y)\big{)}\wedge\\\ \forall
x,y\,\big{(}P(x,y)\wedge\neg\accentset{\ast}{P}(x,y)\rightarrow\\\
\qquad\exists x^{\prime},y^{\prime}\,(x^{\prime}=x\wedge
y^{\prime}=y\wedge\accentset{\ast}{T}(x^{\prime})\wedge\neg\exists
z^{\prime}\,\accentset{\ast}{R}(z^{\prime},y^{\prime}))\big{)}\wedge\\\
\forall x\,\big{(}T(x)\wedge\neg\accentset{\ast}{T}(x)\rightarrow\\\
\qquad\exists
x^{\prime},y^{\prime}\,(\accentset{\ast}{P}(x^{\prime},y^{\prime})\wedge
x^{\prime}=x\wedge\neg\exists
z^{\prime}\,\accentset{\ast}{R}(z^{\prime},y^{\prime}))\big{)}\wedge\\\
\forall x,y\,\big{(}R(x,y)\wedge\neg\accentset{\ast}{R}(x,y)\rightarrow\\\
\qquad\exists
x^{\prime},y^{\prime}\,(\accentset{\ast}{P}(x^{\prime},y^{\prime})\wedge\accentset{\ast}{T}(x^{\prime})\wedge\neg\exists
z^{\prime}\,(z^{\prime}=x\wedge x^{\prime}=y)\big{)}\end{array}$

One can verify that
$\mathsf{rep}_{\Sigma}(\mathcal{D})=\\{\mathcal{D}\setminus{P(a,c)},\mathcal{D}\setminus{T(a)}\\}$
and that these are the only two possible subsets of $\mathcal{D}$ such that
$\mathcal{D}\cup\textit{aux}(\mathcal{D}^{\prime})\models\Psi^{\mathit{rc}}(\Sigma)$.

Finally, we address the cases of full+sticky and full+linear dependencies. To
this aim, we will prove a general property that holds for every set of full
dependencies $\Sigma$ that enjoys the following _CQ-FO-rewritability_
property.

######  Definition 7.

We call a set of dependencies $\Sigma$ _CQ-FO-rewritable_ if $\Sigma$ is such
that classical conjunctive query answering over $\Sigma$ is FO-rewritable,
that is, for every conjunctive query $q(\mathbf{x})$ (where $\mathbf{x}$ are
the free variables of the query) there exists an FO query
$\phi_{q}(\mathbf{x})$ such that, for every database $\mathcal{D}$ and for
every tuple of constants $\mathbf{t}$ of the same arity as $\mathbf{x}$,
$\langle\Sigma,\mathcal{D}\rangle\models q(\mathbf{t})$ iff
$\mathcal{D}\models\phi_{q}(\mathbf{t})$.

Now, let $\Sigma$ be CQ-FO-rewritable and let $p\in\textit{Pred}(\Sigma)$ be a
$k$-ary predicate. We define the following formula:

$\Phi^{\mathit{wc}}_{p}(\Sigma)=\forall\mathbf{x}\,(q_{p}^{\Sigma}(\mathbf{x})\rightarrow
p(\mathbf{x}))$

where $\mathbf{x}=x_{1},\ldots,x_{k}$ and $q_{p}^{\Sigma}$ is a FO-rewriting
of the atomic query $p(\mathbf{x})$ (with free variables $\mathbf{x}$) w.r.t.
$\Sigma$, expressed over the auxiliary predicate symbols. We then define

$\Phi^{\mathit{wc}}(\Sigma)=\bigwedge_{p\in\textit{Pred}(\Sigma)}\Phi^{\mathit{wc}}_{p}(\Sigma)$

Moreover, given a set of atoms $\mathcal{A}$ over the auxiliary predicates, we
define $\Phi^{\mathit{wc}}(\mathcal{A},\Sigma)$ as the formula (with free
variables $\textit{Vars}(\mathcal{A})$) obtained from
$\Phi^{\mathit{wc}}(\Sigma)$ by replacing every occurrence of every auxiliary
atom $\accentset{\ast}{r}(\mathbf{t})$ with the formula
$(\accentset{\ast}{r}(\mathbf{t})\vee\bigvee_{r(\mathbf{t^{\prime}})\in\mathcal{A}}\sigma(\mathbf{t},\mathbf{t^{\prime}}))$,
where $\sigma(\mathbf{t},\mathbf{t^{\prime}})$ is a most general unifier (MGU)
for $\accentset{\ast}{r}(\mathbf{t})$ and
$\accentset{\ast}{r}(\mathbf{t^{\prime}})$ (if $\mathbf{t}$ and
$\mathbf{t^{\prime}}$ do not unify, then
$\sigma(\mathbf{t},\mathbf{t^{\prime}})=\textit{false}$). E.g. if
$\Phi^{\mathit{wc}}(\Sigma)$ is the sentence $\forall
x_{1},x_{2}\,((\accentset{\ast}{s}(x_{1},x_{2})\vee\accentset{\ast}{r}(x_{2},x_{1}))\rightarrow
r(x_{1},x_{2}))$, then
$\Phi^{\mathit{wc}}(\\{\accentset{\ast}{r}(y_{1},y_{2})\\},\Sigma)$ is the
sentence $\forall
x_{1},x_{2}\,\big{(}(\accentset{\ast}{s}(x_{1},x_{2})\vee(\accentset{\ast}{r}(x_{2},x_{1})\vee(y_{1}=x_{2}\wedge
y_{2}=x_{1})))\rightarrow r(x_{1},x_{2})\big{)}$.

We are now ready to define the FO sentence $\Phi^{\mathit{rc}}(\Sigma)$.

######  Definition 8 (Repair checking sentence 2).

Given a CQ-FO-rewritable set of dependencies $\Sigma$, we define
$\Phi^{\mathit{rc}}(\Sigma)$ as the FO sentence

$\Phi^{\mathit{wc}}(\Sigma)\wedge\neg\exists\mathbf{y}\,\big{(}p(\mathbf{y})\wedge\neg\accentset{\ast}{p}(\mathbf{y})\wedge\Phi^{\mathit{wc}}(\\{\accentset{\ast}{p}(\mathbf{y})\\},\Sigma)\big{)}$

It is now possible to show that $\Phi^{\mathit{rc}}(\Sigma)$ constitutes a
sound and complete FO-rewriting for the repair checking problem, i.e. such a
formula is evaluated to true over the database
$\mathcal{D}\cup\textit{aux}(\mathcal{D}^{\prime})$ iff $\mathcal{D}^{\prime}$
is a repair of $\langle\Sigma,\mathcal{D}\rangle$. Therefore, the following
property holds.

######  Theorem 6.

Let $\Sigma$ be a CQ-FO-rewritable set of full dependencies. For every pair of
databases $\mathcal{D},\mathcal{D}^{\prime}$, deciding whether
$\mathcal{D}^{\prime}$ is a repair of $\langle\Sigma,\mathcal{D}\rangle$ is in
$\mathrm{AC}^{0}$ w.r.t. data complexity.

It is now easy to show that CQ-FO-rewritability holds for the classes of
dependencies we are focusing on (as well as for acyclic+full dependencies).

######  Proposition 3.

Every set of acyclic+full dependencies, every set of full+linear dependencies
and every set of full+sticky dependencies is CQ-FO-rewritable.

As an immediate consequence of Theorem 6 and Proposition 3, we obtain the
following property.

######  Corollary 2.

Repair checking is in $\mathrm{AC}^{0}$ w.r.t. data complexity in the case of
full+linear or full+sticky dependencies.

##  5 BUCQ Entailment under IAR Semantics

In this section we focus on the problem of IAR-entailment of safe BUCQs. In
the rest of the paper, everytime we write BUCQs we actually refer to safe
BUCQs.

#### Lower bounds

First, we are able to show that instance checking is already
$\mathrm{\Pi}^{p}_{2}$-hard for the class of guarded+sticky dependencies.

######  Theorem 7.

There exist a set of guarded+sticky dependencies, a BUCQ and a database for
which instance checking is $\mathrm{\Pi}^{p}_{2}$-hard w.r.t. data complexity.

Proof (sketch).  The proof is obtained through a reduction from the complement
of the 2-QBF problem. ∎

We can also prove a coNP lower bound for instance checking in the case of
acyclic+guarded+sticky dependencies and in the case of full+guarded
dependencies.

######  Theorem 8.

There exist a set of acyclic+guarded+sticky dependencies, a BUCQ and a
database for which instance checking is coNP-hard w.r.t. data complexity.

Proof (sketch).  The proof is obtained through a reduction from the complement
of the 3-CNF problem. ∎

######  Theorem 9.

There exist a set of full+guarded dependencies, a BUCQ and a database for
which instance checking is coNP-hard w.r.t. data complexity.

Proof (sketch).  The proof is obtained through a reduction from the complement
of the 3-CNF problem. ∎

Finally, from Theorem 1 above and Theorem 4.1 of (?) it follows that:

######  Corollary 3.

There exist a set of linear+sticky dependencies, a BUCQ and a database for
which instance checking is PTIME-hard w.r.t. data complexity.

#### Upper bounds

For proving the upper bounds for IAR-entailment, we first introduce the
following auxiliary definition. Given a set of dependencies $\Sigma$ and a
database $\mathcal{D}$, we say that a subset $\mathcal{D}^{\prime}$ of
$\mathcal{D}$ is _weakly consistent with $\langle\Sigma,\mathcal{D}\rangle$_
if there exists a subset $\mathcal{D}^{\prime\prime}$ of $\mathcal{D}$ such
that $\mathcal{D}^{\prime}\subseteq\mathcal{D}^{\prime\prime}$ and
$\mathcal{D}^{\prime\prime}$ is consistent with $\Sigma$.

Most of the algorithms that we present for IAR-entailment rely on checking if
a set of facts is weakly consistent.

For the general case we present the Algorithm 1 that, given a database
$\mathcal{D}$, a set of arbitrary dependencies $\Sigma$, a BUCQ $Q$, checks
whether $Q$ is IAR-entailed by $\langle\Sigma,\mathcal{D}\rangle$.

Algorithm 1 IAR-CQEnt

0: A set of dependencies $\Sigma$, a database $\mathcal{D}$, a BUCQ $Q$;

0: A Boolean value;

1: if there exists an image $M$ of $Q$ in $\mathcal{D}$ such that there exists
no $\mathcal{D}^{\prime}\subseteq\mathcal{D}$ such that $\mathcal{D}^{\prime}$
is weakly consistent with $\Sigma$ in $\mathcal{D}$ and
$\mathcal{D}^{\prime}\cup M$ is not weakly consistent with $\Sigma$ in
$\mathcal{D}$ then

2: return true;

3: else

4: return false;

The correctness of this algorithm follows easily from the definition of the
IAR semantics.

######  Proposition 4.

The algorithm IAR-CQEnt $(\Sigma,\mathcal{D},Q)$ returns true iff the BUCQ $Q$
is IAR-entailed by $\langle\Sigma,\mathcal{D}\rangle$.

The above property implies the following upper bounds.

######  Theorem 10.

IAR-entailment is: $(i)$ in $\mathrm{\Pi}^{p}_{2}$ w.r.t. data complexity in
the general case of arbitrary dependencies; $(ii)$ in coNP w.r.t. data
complexity in the case of full dependencies.

We now consider acyclic dependencies, and establish the coNP membership of
IAR-entailment of BUCQs for such a class of dependencies.

######  Theorem 11.

IAR-entailment is in coNP w.r.t. data complexity in the case of acyclic
dependencies.

###### Proof.

First, observe that $Q$ is IAR-entailed by $\langle\Sigma,\mathcal{D}\rangle$
iff there exists an image $M$ of $Q$ in $\mathcal{D}$ such that
$M\subseteq\mathsf{intRep}_{\Sigma}(\mathcal{D})$, i.e. $M$ is contained in
every repair of $\langle\Sigma,\mathcal{D}\rangle$. Therefore, if
$M_{1},\ldots,M_{m}$ are the images of $Q$ in $\mathcal{D}$, then $Q$ is IAR-
entailed by $\langle\Sigma,\mathcal{D}\rangle$ iff there exist $m$ repairs of
$\langle\Sigma,\mathcal{D}\rangle$ $\mathcal{R}_{1},\ldots,\mathcal{R}_{m}$
such that $M_{i}\not\subseteq\mathcal{R}_{i}$ for every $i$ such that $1\leq
i\leq m$. Since $m$ is bounded by $n^{k}$, where $n$ is the size of
$\mathcal{D}$ and $k$ is the number of predicate atoms of $Q$, and by
Corollary 1 repair checking in the case of acyclic dependencies is in
$\mathrm{AC}^{0}$ w.r.t. data complexity, the thesis follows. ∎

As for linear dependencies, we show the following property (which, by
Proposition 1, also holds for AR-entailment).

######  Theorem 12.

IAR-entailment is in PTIME w.r.t. data complexity in the case of linear
dependencies.

Proof (sketch).  When $\Sigma$ consists of linear dependencies, its unique
repair $\mathcal{D}^{\prime}$ of $\langle\Sigma,\mathcal{D}\rangle$ can be
computed in PTIME. Then, the query can be evaluated over
$\mathcal{D}^{\prime}$ in $\mathrm{AC}^{0}$. ∎

Then, we focus on the class of acyclic+linear dependencies, and we first show
the following property.

######  Lemma 1.

Let $\Sigma$ be a set of linear dependencies, let $\mathcal{D}$ be a database,
and let $Q$ be a BUCQ. Then, $Q$ is AR-entailed (or, equivalently, IAR-
entailed) by $\langle\Sigma,\mathcal{D}\rangle$ iff there exists an image $M$
of $Q$ in $\mathcal{D}$ such that, for each $\alpha\in M$, $\\{\alpha\\}$ is
weakly consistent with $\langle\Sigma,\mathcal{D}\rangle$.

Proof (sketch).  If the dependencies of $\Sigma$ are linear, then the repair
is unique. In this case, we have that $(i)$ such image $M$ must be weakly
consistent with $\langle\Sigma,\mathcal{D}\rangle$ and $(ii)$ a set of facts
is weakly consistent with $\langle\Sigma,\mathcal{D}\rangle$ iff every fact
contained in it is weakly consistent with $\langle\Sigma,\mathcal{D}\rangle$.
∎

Now, in a way similar to the case of repair checking with acyclic
dependencies, we define an FO sentence that decides weak consistency.

Given a set of acyclic+linear dependencies $\Sigma$, where
$\langle\tau_{1},\ldots,\tau_{h}\rangle$ is a topological order of $\Sigma$,
and an atom $\alpha$, we define the formula $\Psi^{wc}(\alpha,\Sigma)$ as
follows: $(i)$ if $\Sigma=\emptyset$, then
$\Psi^{wc}(\alpha,\Sigma)=\mathit{true}$; $(ii)$ if $\Sigma\neq\emptyset$,
then $\Psi^{wc}(\alpha,\Sigma)$ is the formula

$\begin{array}[]{l}\displaystyle\bigwedge_{\footnotesize\begin{array}[]{c}\tau_{i}\in\Sigma\wedge\\\
\textit{BodyUnify}(\alpha,\tau_{i},\sigma)\end{array}}\Big{(}\bigvee_{q\in\textit{CQ}(\textit{head}(\tau_{i}))}\exists\mathbf{x}\,\big{(}\sigma(\textit{Conj}(q))\wedge\\\
\displaystyle\qquad\qquad\qquad\,\bigwedge_{\beta\in\textit{PA}(q)}\Psi^{wc}(\sigma(\beta),\\{\tau_{i+1},\ldots,\tau_{h}\\})\big{)}\Big{)}\end{array}$

where $\textit{BodyUnify}(\alpha,\tau_{i},\sigma)$ is true iff the atom
$\alpha$ unifies with $\textit{body}(\tau_{i})$ with MGU $\sigma$, and
$\mathbf{x}$ is the sequence of all the variables of $\tau$ that have not been
substituted by $\sigma$.

######  Lemma 2.

Let $\Sigma$ be a set of acyclic+linear dependencies, let $\alpha$ be an atom
and let $\sigma$ be a substitution of the variables occurring in $\alpha$ with
constants. Then, for every database $\mathcal{D}$, $\sigma(\alpha)$ is weakly
consistent with $\langle\Sigma,\mathcal{D}\rangle$ iff
$\sigma(\alpha)\in\mathcal{D}$ and
$\mathcal{D}\models\sigma(\Psi^{wc}(\alpha,\Sigma))$.

Then, we define the formula $\Psi^{wc}(\Sigma)$ as follows:

$\bigwedge_{p\in\textit{Pred}(\Sigma)}\forall\mathbf{x}\,(\accentset{\ast}{p}(\mathbf{x})\rightarrow\Psi^{wc}(p(\mathbf{x}),\Sigma))$

From Lemma 2, it immediately follows that $\mathcal{D}^{\prime}$ is weakly
consistent with $\langle\Sigma,\mathcal{D}\rangle$ iff
$\mathcal{D}\cup\textit{aux}(\mathcal{D}^{\prime})\models\Psi^{wc}(\Sigma)$.

Now, based on Lemma 1, we can exploit the formula $\Psi^{wc}(\alpha,\Sigma)$
to define an FO sentence that is able to decide query entailment for
acyclic+linear dependencies.

######  Definition 9 (IAR-entailment sentence 1).

Given a BCQ $q$ of the form $\exists\mathbf{x}\,(\gamma)$, we define as
$\Psi^{iar}(q,\Sigma)$ the following FO sentence:

$\exists\mathbf{x}\,\Big{(}\gamma\wedge\bigwedge_{\alpha\in\textit{PA}(\gamma)}\Psi^{wc}(\alpha,\Sigma)\Big{)}$

Moreover, given a BUCQ $Q$, we define

$\Psi^{iar}(Q,\Sigma)=\bigvee_{q\in\textit{CQ}(Q)}\Psi^{iar}(q,\Sigma)$

The following theorem is an immediate consequence of the above definition of
$\Psi^{iar}(Q,\Sigma)$, Lemma 1 and Lemma 2.

######  Theorem 13.

Let $\Sigma$ be a set of acyclic+linear dependencies, let $\mathcal{D}$ be a
database, and let $Q$ be a BUCQ. Then, $Q$ is IAR-entailed (or equivalently
AR-entailed) by $\langle\Sigma,\mathcal{D}\rangle$ iff
$\mathcal{D}\models\Psi^{iar}(Q,\Sigma)$.

######  Corollary 4.

IAR- and AR-entailment are in $\mathrm{AC}^{0}$ w.r.t. data complexity in the
case of acyclic+linear dependencies.

######  Example 2.

Let $\mathcal{D}=\\{P(a),T(a,b),T(c,b),\allowbreak R(c,b,a)\\}$ and
$\Sigma=\\{\forall x,y\,\allowbreak(T(x,y)\rightarrow\exists
z\,R(x,y,z)),\forall x,y\,(P(x)\rightarrow\exists y\,T(x,y)\wedge x\neq
y)\\}$. Note that $\Sigma$ is a set of acyclic+linear dependencies, and
$\mathcal{D}$ is inconsistent with $\Sigma$. Since we are under the conditions
of Proposition 1, there is only one minimal way of solving such an
inconsistency. In particular, we delete $T(a,b)$ and, consequently, $P(a)$.
Thus, we have that
$\mathsf{rep}_{\Sigma}(\mathcal{D})=\\{\mathsf{intRep}_{\Sigma}(\mathcal{D})\\}=\\{\\{T(c,b),R(c,b,a)\\}\\}$.

Let us now consider queries $q_{1}=\exists x,y\,T(x,y)$ and $q_{2}=\exists
x,y,z\,(P(x)\wedge R(y,z,x))$. The rewritten queries are
$\Psi^{iar}(q_{1},\Sigma)=\exists x,y\,(T(x,y)\wedge\exists z\,R(x,y,z))$ and
$\Psi^{iar}(q_{2},\Sigma)=\exists x,y,z\,(P(x)\wedge R(y,z,x)\wedge\exists
y^{\prime}\,(T(x,y^{\prime})\wedge x\neq y^{\prime}\wedge\exists
z^{\prime}\,R(x,y^{\prime},z^{\prime})))$. One can verify that
$\mathsf{intRep}_{\Sigma}(\mathcal{D})\models q_{1}$ as well as
$\mathcal{D}\models\Psi^{iar}(q_{1},\Sigma)$, and that
$\mathsf{intRep}_{\Sigma}(\mathcal{D})\not\models q_{2}$ as well as
$\mathcal{D}\not\models\Psi^{iar}(q_{2},\Sigma)$.

Finally, for the cases of acyclic+full, full+sticky and full+linear
dependencies, in a way similar to the repair checking problem, we prove a
general property that holds for every set of full dependencies $\Sigma$ that
enjoys the CQ-FO-rewritability property.

Let $\mathcal{P}=\\{p_{1},\ldots,p_{m}\\}$ be a set of predicates. We define
$\textit{Atoms}(\mathcal{P})$ as the set of atoms
$\bigcup_{p_{i}\in\mathcal{P}}\\{p_{i}(x_{i,1},\ldots,x_{i,h})\\}$, where $h$
is the arity of $p_{i}$.

Then, let $k$ be a positive integer. We define $\textit{Atoms}(\mathcal{P},k)$
as the set of atoms
$\bigcup_{i\in\\{1,\ldots,k\\}}\textit{Atoms}(\mathcal{P})^{i}$, where
$\textit{Atoms}(\mathcal{P})^{i}$ is the set of atoms obtained from
$\textit{Atoms}(\mathcal{P})$ replacing every occurrence of a variable
$x_{j,\ell}$ with the variable $x_{j,\ell}^{i}$.

Then, given a CQ-FO-rewritable set of dependencies $\Sigma$, a set of atoms
$\mathcal{A}\subseteq\textit{Atoms}(\mathcal{P},k)$ (with $\mathbf{y}$ the
tuple of variables in $\textit{Vars}(\mathcal{A})$) and a BCQ $q$ of the form
$\exists\mathbf{x}\,(\gamma)$ (where we assume w.l.o.g. that
$\mathbf{x}\cap\mathbf{y}=\emptyset$), let $\Phi^{ni}(\mathcal{A},q,\Sigma)$
be the formula (with free variables $\mathbf{x}$)

$\exists\mathbf{y}\>\Big{(}\big{(}\bigwedge_{\alpha\in\mathcal{A}}\alpha\big{)}\wedge\Phi^{\mathit{wc}}(\mathcal{A})\wedge\neg\Phi^{\mathit{wc}}(\mathcal{A}\cup\textit{Atoms}(q))\Big{)}$

where $\mathbf{y}$ is the tuple of variables in $\textit{Vars}(\mathcal{A})$
and $\textit{Atoms}(q)$ is the set of atoms occurring in $q$.

######  Definition 10 (IAR-entailment sentence 2).

Let $\Sigma$ be a CQ-FO-rewritable set of dependencies, let $q$ be a BCQ, and
let $k$ be a positive integer. We define $\Phi^{\mathit{iar}}(q,\Sigma,k)$ as
the sentence

$\exists\mathbf{x}\>\Big{(}\gamma\wedge\neg\Big{(}\bigwedge_{\mathcal{A}\in\textit{Atoms}(\textit{Pred}(\Sigma),k)}\Phi^{ni}(\mathcal{A},q)\Big{)}\Big{)}$

It is now possible to prove that, for every database $\mathcal{D}$,
$\mathcal{D}\models\Phi^{\mathit{iar}}(q,\Sigma,k)$ iff $q$ is IAR-entailed by
$\langle\Sigma,\mathcal{D}\rangle$. Moreover, the above sentence and property
can be immediately extended to the case of BUCQs. Consequently, the following
property holds.

######  Theorem 14.

Let $\Sigma$ be a set of full dependencies and let $\Sigma$ be CQ-FO-
rewritable. For every BUCQ $Q$ and for every database $\mathcal{D}$, deciding
whether $\langle\Sigma,\mathcal{D}\rangle$ IAR-entails $Q$ is in
$\mathrm{AC}^{0}$ w.r.t. data complexity.

As a consequence of the above theorem and of Proposition 3, we get the
following property.

######  Corollary 5.

IAR-entailment is in $\mathrm{AC}^{0}$ w.r.t. data complexity in the case of
either acyclic+full, or full+linear or full+sticky dependencies.

##  6 BUCQ Entailment under AR Semantics

We now turn our attention to the problem of AR-entailment of BUCQs.

As for the lower bounds for AR-entailment, almost all of them follow from the
ones already shown for the instance checking problem. Here, we show the
following property.

######  Theorem 15.

There exist a set of acyclic+full+guarded+sticky dependencies, a BUCQ and a
database for which AR-entailment is coNP-hard w.r.t. data complexity.

Proof (sketch).  The proof is obtained through a reduction from the complement
of the 3-CNF problem. ∎

Notice that, as a consequence of the previous theorem, both in the case of
acyclic+linear dependencies and in the case of full+sticky dependencies, AR-
entailment of BUCQs is coNP-hard, and therefore computationally harder than
IAR-entailment of BUCQs (which is in $\mathrm{AC}^{0}$ in both cases).

Moreover, we establish the following upper bounds for the case of arbitrary,
full, and acyclic dependencies.

######  Theorem 16.

AR-entailment is $(a)$ in $\mathrm{\Pi}^{p}_{2}$ w.r.t. data complexity in the
general case of arbitrary dependencies; $(b)$ in coNP w.r.t. data complexity
in the case of either full or acyclic dependencies.

###### Proof.

Notice that a BUCQ $Q$ is not AR-entailed by
$\langle\Sigma,\mathcal{D}\rangle$ iff there exists a subset
$\mathcal{D}^{\prime}$ of $\mathcal{D}$ such that $(i)$ $\mathcal{D}^{\prime}$
is a repair of $\langle\Sigma,\mathcal{D}\rangle$ and $(ii)$
$\mathcal{D}^{\prime}\not\models Q$. Therefore, the theses $(a)$ and $(b)$
follow from the fact that repair checking is, respectively, in coNP and in
PTIME. ∎

##  7 Discussion and Conclusions

Existential | RC | IC | BUCQE | BUCQE
---|---|---|---|---
rules class | IAR | AR
A+L[+S] | in $\mathrm{AC}^{0}$ | in $\mathrm{AC}^{0}$ | in $\mathrm{AC}^{0}$
F+L[+S] | in $\mathrm{AC}^{0}$ | in $\mathrm{AC}^{0}$ | in $\mathrm{AC}^{0}$
A+F[+G][+S] | in $\mathrm{AC}^{0}$ | in $\mathrm{AC}^{0}$ | in $\mathrm{AC}^{0}$ | coNP (1)
F+S[+A][+G] | in $\mathrm{AC}^{0}$ | in $\mathrm{AC}^{0}$ | in $\mathrm{AC}^{0}$ | coNP (1)(5)
L[+S] | PTIME (2) | PTIME | PTIME (2)
A[+G][+S] | in $\mathrm{AC}^{0}$ | coNP | coNP | coNP (1)
F[+G] | PTIME (3)(4) | coNP | coNP | coNP (1)(5)
All[+G][+S] | coNP (1)(6) |  $\mathrm{\Pi}^{p}_{2}$ (1) |  $\mathrm{\Pi}^{p}_{2}$ (1) |  $\mathrm{\Pi}^{p}_{2}$ (1)(2)
A = Acyclic, F = Full, G = Guarded, L = Linear, S = Sticky
Table 1: Data complexity results for all the classes of existential rules
considered in this work. Joined cells indicate that the two entailment
problems coincide (see Proposition 1). All entries are completeness results
(except the $\mathrm{AC}^{0}$ ones), and the [+X] notation indicates that the
same complexity holds if the considered class also belongs to X. We recall
that L implies G (i.e. linear dependencies are a subclass of guarded
dependencies).

The results presented in the previous sections allow us to draw a complete
picture of the data complexity of repair checking and both AR-entailment and
IAR-entailment of BUCQs, for all the possible combinations of the five classes
of existential rules considered in this paper.

Table 1 summarizes all the data complexity results presented in the paper.
With the exception of the cases in $\mathrm{AC}^{0}$, every result is a
completeness results for the complexity class reported. Every such result is
actually new. However, some of the results (the ones marked with numbers)
extend previously known lower and/or upper bounds. More precisely:

  * (1)

Extends the lower bound proved in (?) for denials;

  * (2)

Extends the upper bound proved in (?) for non-disjunctive LAV TGDs without
inequalities;

  * (3)

Extends the lower bound from (?) for full TGDs;

  * (4)

Extends the upper bound proved in (?) for denials;

  * (5)

Extends the upper bound proved in (?) for GAV TGDs;

  * (6)

The upper bound comes from (?).

In our opinion, the most important consequence of our results is the
identification of many classes of existential rules in which the problems
studied are in $\mathrm{AC}^{0}$ and FO-rewritable. On the one hand, this is a
bit surprising, since consistent query answering is generally known to be a
computationally hard task. On the other hand, for the problems in
$\mathrm{AC}^{0}$ we have actually shown that such problems can be solved by
the evaluation of an FO sentence over the database: therefore, these results
(and in particular Definition 6, Definition 8, Definition 9 and Definition 10)
can be a starting point towards the development of practical algorithms for
consistent query answering based on FO rewriting techniques.

Another very interesting future research direction of this work is extending
our framework towards the combination of open-world assumption (OWA) and
closed-world assumption (CWA). Many studies have proposed forms of combination
of OWA and CWA in knowledge bases (see e.g. (?, ?, ?, ?, ?)). Specifically,
for consistent query answering in existential rules the present paper has
studied a “purely closed” approach, in which all predicates have a closed
interpretation, while previous work has considered “open” approaches, as
explained in the introduction. It would be very interesting to study a hybrid
approach, in which the predicates can be partitioned into an “open” and a
“closed” class. This kind of combination of OWA and CWA is usually very
challenging from the computational viewpoint, however both our results and the
results for consistent query answering in existential rules under OWA
presented in (?) (although for a more restricted language for existential
rules than ours) are quite promising.

Finally, consistent query answering has important connections with the problem
of _controlled query evaluation_ (?), i.e. the problem of evaluating queries
on a database (or knowledge base) in the presence of a logical specification
of a privacy policy that should not be violated by the query answers. We are
very interested in investigating the consequences of our results for such a
problem.

### Acknowledgments

This work was partially supported by: projects FAIR (PE0000013) and SERICS
(PE00000014) under the MUR National Recovery and Resilience Plan funded by the
European Union.

## References

  * Abiteboul et al. Abiteboul, S., Hull, R., & Vianu, V. (1995).  Foundations of Databases.  Addison-Wesley.
  * Afrati & Kolaitis Afrati, F. N., & Kolaitis, P. G. (2009).  Repair checking in inconsistent databases: algorithms and complexity.  In Fagin, R. (Ed.), Database Theory - ICDT 2009, 12th International Conference, St. Petersburg, Russia, March 23-25, 2009, Proceedings, Vol. 361 of ACM International Conference Proceeding Series, pp. 31–41. ACM.
  * Ahmetaj et al. Ahmetaj, S., Ortiz, M., & Simkus, M. (2020).  Polynomial rewritings from expressive description logics with closed predicates to variants of datalog.  Artif. Intell., 280, 103220.
  * Amendola et al. Amendola, G., Leone, N., Manna, M., & Veltri, P. (2018).  Enhancing existential rules by closed-world variables.  In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, p. 1676–1682. AAAI Press.
  * Arenas et al. Arenas, M., Bertossi, L., & Chomicki, J. (1999).  Consistent query answers in inconsistent databases.  In Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 1999, p. 68–79, New York, NY, USA. Association for Computing Machinery.
  * Arming et al. Arming, S., Pichler, R., & Sallinger, E. (2016).  Complexity of Repair Checking and Consistent Query Answering.  In Martens, W., & Zeume, T. (Eds.), 19th International Conference on Database Theory (ICDT 2016), Vol. 48 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 21:1–21:18, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * Baget et al. Baget, J., Leclère, M., Mugnier, M., & Salvat, E. (2011).  On rules with existential variables: Walking the decidability line.  Artif. Intell., 175(9-10), 1620–1654.
  * Bertossi Bertossi, L. E. (2019).  Database repairs and consistent query answering: Origins and further developments.  In Suciu, D., Skritek, S., & Koch, C. (Eds.), Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pp. 48–58. ACM.
  * Bienvenu Bienvenu, M. (2012).  On the complexity of consistent query answering in the presence of simple ontologies.  In Hoffmann, J., & Selman, B. (Eds.), Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada. AAAI Press.
  * Bienvenu et al. Bienvenu, M., Bourgaux, C., & Goasdoué, F. (2019).  Computing and explaining query answers over inconsistent dl-lite knowledge bases.  J. Artif. Intell. Res., 64, 563–644.
  * Bienvenu & Bourhis Bienvenu, M., & Bourhis, P. (2019).  Mixed-world reasoning with existential rules under active-domain semantics.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, p. 1558–1565. AAAI Press.
  * Calautti et al. Calautti, M., Greco, S., Molinaro, C., & Trubitsyna, I. (2022).  Preference-based inconsistency-tolerant query answering under existential rules.  Artif. Intell., 312, 103772.
  * Calì et al. Calì, A., Gottlob, G., & Lukasiewicz, T. (2012a).  A general datalog-based framework for tractable query answering over ontologies.  J. Web Semant., 14, 57–83.
  * Calì et al. Calì, A., Gottlob, G., & Pieris, A. (2012b).  Towards more expressive ontology languages: The query answering problem.  Artif. Intell., 193, 87–128.
  * Chomicki & Marcinkowski Chomicki, J., & Marcinkowski, J. (2005).  Minimal-change integrity maintenance using tuple deletions.  Inf. Comput., 197(1-2), 90–121.
  * Deutsch Deutsch, A. (2018).  FOL modeling of integrity constraints (dependencies).  In Liu, L., & Özsu, M. T. (Eds.), Encyclopedia of Database Systems, Second Edition. Springer.
  * Deutsch & Tannen Deutsch, A., & Tannen, V. (2005).  XML queries and constraints, containment and reformulation.  Theor. Comput. Sci., 336(1), 57–87.
  * König et al. König, M., Leclère, M., & Mugnier, M. (2015a).  Query rewriting for existential rules with compiled preorder.  In Yang, Q., & Wooldridge, M. J. (Eds.), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pp. 3106–3112. AAAI Press.
  * König et al. König, M., Leclère, M., Mugnier, M., & Thomazo, M. (2015b).  Sound, complete and minimal ucq-rewriting for existential rules.  Semantic Web, 6(5), 451–475.
  * Lembo et al. Lembo, D., Rosati, R., & Savo, D. F. (2019).  Revisiting controlled query evaluation in description logics.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, p. 1786–1792. AAAI Press.
  * Lukasiewicz et al. Lukasiewicz, T., Malizia, E., Martinez, M. V., Molinaro, C., Pieris, A., & Simari, G. I. (2022).  Inconsistency-tolerant query answering for existential rules.  Artif. Intell., 307(C).
  * Lukasiewicz et al. Lukasiewicz, T., Malizia, E., & Molinaro, C. (2018).  Complexity of approximate query answering under inconsistency in datalog±.  In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, p. 1921–1927. AAAI Press.
  * Lukasiewicz et al. Lukasiewicz, T., Martinez, M. V., Pieris, A., & Simari, G. (2015).  From classical to consistent query answering under existential rules.  Proceedings of the AAAI Conference on Artificial Intelligence, 29(1).
  * Lukasiewicz et al. Lukasiewicz, T., Martinez, M. V., & Simari, G. I. (2012).  Inconsistency handling in datalog+/- ontologies.  In Raedt, L. D., Bessiere, C., Dubois, D., Doherty, P., Frasconi, P., Heintz, F., & Lucas, P. J. F. (Eds.), ECAI 2012 - 20th European Conference on Artificial Intelligence. Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track, Montpellier, France, August 27-31 , 2012, Vol. 242 of Frontiers in Artificial Intelligence and Applications, pp. 558–563. IOS Press.
  * Lutz et al. Lutz, C., Seylan, I., & Wolter, F. (2019).  The data complexity of ontology-mediated queries with closed predicates.  Log. Methods Comput. Sci., 15(3).
  * Lutz et al. Lutz, C., Seylan, u., & Wolter, F. (2013).  Ontology-based data access with closed predicates is inherently intractable (sometimes).  In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI 2013, p. 1024–1030. AAAI Press.
  * Rosati Rosati, R. (2011).  On the complexity of dealing with inconsistency in description logic ontologies.  In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume Two, IJCAI 2011, p. 1057–1062. AAAI Press.
  * Staworko & Chomicki Staworko, S., & Chomicki, J. (2010).  Consistent query answers in the presence of universal constraints.  Information Systems, 35(1), 1–22.
  * ten Cate et al. ten Cate, B., Fontaine, G., & Kolaitis, P. G. (2012).  On the data complexity of consistent query answering.  In Deutsch, A. (Ed.), 15th International Conference on Database Theory, ICDT 2012, Berlin, Germany, March 26-29, 2012, pp. 22–33. ACM.
  * Wijsen Wijsen, J. (2005).  Database repairing using updates.  ACM Trans. Database Syst., 30(3), 722–768.

## Appendix

Auxiliary definitions and results

In what follows, we present some auxiliary results which will be useful for
proving some of the complexity results we presented in the paper. In
particular, we want to find the complexity of checking weak consistency in the
general case and in the case of full dependencies.

First, we recall the following property for the consistency problem.

######  Proposition 5.

Deciding consistency of a database with a set of dependencies is in
$\mathrm{AC}^{0}$ w.r.t. data complexity.

###### Proof.

The proof immediately follows from the fact that a database $\mathcal{D}$ is
consistent with $\Sigma$ iff
$\mathcal{D}\models\bigwedge_{\tau\in\Sigma}\tau$, and from the fact that
evaluating a domain-independent FO sentence over a database is in
$\mathrm{AC}^{0}$ w.r.t. data complexity. ∎

From the above property and from the definition of weak consistency, it
immediately follows that:

######  Lemma 3.

In the general case (arbitrary dependencies), deciding weak consistency is in
NP w.r.t. data complexity.

We now turn our attention to full dependencies. W.l.o.g., from now on we will
assume that each full dependency $\tau$ is such that
$\textit{head}(\tau)=\alpha$, where $\alpha$ is a predicate atom. Note indeed
that:

  * •

it is always possible to pass from a full dependency to a set of single-head
ones;

  * •

each $\tau$ of the form $\forall\mathbf{x}\,(\varphi(\mathbf{x})\rightarrow
x\neq t)$333W.l.o.g. we assume that no inequality of the form $t\neq t$ or
$c\neq d$, where $c$ and $d$ are distinct constants, appears in $\tau$. (with
$x\in\mathbf{x}$) can be rewritten as
$\forall\mathbf{x}\,(\sigma(\varphi(\mathbf{x}))\rightarrow\bot)$,444Recall
that $\bot$ is a special predicate. where $\sigma$ is the substitution
$x\mapsto t$.

We recall the notion of _chase_ for DEDs (?), that we apply and adapt to the
subclass of full dependencies. Formally, we use the function
$\mathit{Chase}(\mathcal{D},\Sigma)$ that, given a set of facts $\mathcal{D}$
and a set of full dependencies $\Sigma$, returns the smallest set of facts
$\mathcal{D}^{\prime}$ such that $\mathcal{D}\subseteq\mathcal{D}^{\prime}$
and, for every $\tau\in\Sigma$ and for every instantiation $\sigma$ of
$\textit{body}(\tau)$ in $\mathcal{D}^{\prime}$,
$\sigma(\textit{head}(\tau))\in\mathcal{D}^{\prime}$.

It is well-known that, in case of full dependencies, such a set is
deterministically computable in polynomial time.

Consequently, the following property holds.

######  Lemma 4.

Let $\Sigma$ be a set of full dependencies, and let $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ be two databases such that
$\mathcal{D}^{\prime}\subseteq\mathcal{D}$. Deciding whether
$\mathcal{D}^{\prime}$ is weakly consistent with
$\langle\Sigma,\mathcal{D}\rangle$ is in PTIME w.r.t. data complexity.

###### Proof.

It is straightforward to see that $\mathcal{D}^{\prime}$ is weakly consistent
with $\langle\Sigma,\mathcal{D}\rangle$ iff
$\mathit{Chase}(\mathcal{D}^{\prime},\Sigma)\subseteq\mathcal{D}$. ∎

Proof of Theorem 1

We prove the thesis by showing that the HORN SAT problem can be reduced to
repair checking.

Let $\phi$ be a set of $n$ ground Horn rules. We assume w.l.o.g. that there is
at least one rule without head in $\phi$ (i.e. a clause with only negated
variables). Let $\phi^{\prime}$ be obtained from $\phi$ by slightly modifying
rules without heads as follows: every rule without head $r$ is replaced by the
rule with the same body as $r$ and with the new variable $u$ in the head;
moreover, if $\phi$ contains only one rule without head, then we add the rule
$u\rightarrow u$ to $\phi^{\prime}$ (so $\phi^{\prime}$ always contains at
least two rules with $u$ in the head). It is immediate to verify that $\phi$
is unsatisfiable iff $u$ belongs to all the models (and hence to the minimal
model) of $\phi^{\prime}$.

Now, we associate an id $r_{i}$ to every Horn rule in $\phi^{\prime}$, with
$r_{1}$ associated to a rule having $u$ in the head. Then, let
$\phi^{\prime}(x)$ be the rules of $\phi^{\prime}$ having the variable $x$ in
their head, let $\mathit{PV}(\phi^{\prime})$ be the set of propositional
variables occurring in $\phi^{\prime}$ and, for every rule $r_{i}$, let
$\mathit{BV}(r_{i})$ be the set of variables in the body of $r_{i}$. We define
$\mathcal{D}$ as the set of facts

$\begin{array}[]{l}\bigcup_{x\in\mathit{PV}(\phi^{\prime})}\\{H(r_{i_{1}},x,1,2),H(r_{i_{2}},x,2,3),\ldots,H(r_{i_{h}},x,h,1)\mid\\\
\hfill|\phi^{\prime}(x)|=h\\}\\\
\cup\bigcup_{r_{i}\in\phi^{\prime}}\\{B(r_{i},x)\mid
x\in\mathit{BV}(r_{i})\\}\end{array}$

Finally, we define the following set of linear+sticky dependencies $\Sigma$:

$\begin{array}[]{l}\forall x,y,z,w\,(H(x,y,z,w)\rightarrow\exists
v\,B(x,v))\\\ \forall x,y,z,w\,(H(x,y,z,w)\rightarrow\exists
v,t\,H(v,y,w,t))\\\ \forall x,y\,(B(x,y)\rightarrow\exists
z,w,v\,H(z,y,w,v))\\\ \forall x,y,z,w\,(H(x,y,z,w)\rightarrow
H(r_{1},u,1,2))\\\ \forall x,y\,(B(x,y)\rightarrow H(r_{1},u,1,2))\end{array}$

Observe that: the first dependency of $\Sigma$ implies that if for a rule
there are no more body atoms, the head atom of that rule is deleted; the
second dependency implies that if a head atom is deleted, all the head atoms
with that variable are deleted; the third dependency implies that if there are
no head atoms for a variable, all the body atoms for that variable are
deleted; the fourth and fifth dependencies imply that, if the atom
$H(r,u,1,2)$ is deleted, then all the atoms are deleted.

Therefore, it can be verified that for every variable $x$ that belongs to the
minimal model of $\phi^{\prime}$, no fact of the form $H(\\_,x,\\_,\\_)$ or
$B(x,\\_)$ belong to the (unique) repair of
$\langle\Sigma,\mathcal{D}\rangle$. Consequently, the minimal model of
$\phi^{\prime}$ contains $u$ (i.e. $\phi$ is unsatisfiable) iff the fact
$H(r_{1},u,1,2)$ does not belong to the repair of
$\langle\Sigma,\mathcal{D}\rangle$, which immediately implies (given the
fourth and fifth rules of $\Sigma$) that $\phi$ is unsatisfiable iff the empty
database is the repair of $\langle\Sigma,\mathcal{D}\rangle$. ∎

Proof of Theorem 2

We prove the thesis using a modification of the reduction from Horn 3-CNF
satisfiability shown in the proof of (?, Thm. 5) for the case of full TGDs.

Let $\phi$ be a Horn 3-CNF formula. We denote by $\mathit{CL}(\phi)$ the set
of clauses of $\phi$, and by $\mathit{PV}(\phi)$ the set of propositional
variables of $\phi$. Let $\Sigma$ be the following set of full+guarded
dependencies:

$\begin{array}[]{l}\forall x,w\>(A(w)\wedge U(x,w)\rightarrow M(x))\\\ \forall
x,y,z\>(P(x,y,z)\wedge M(x)\wedge M(y)\rightarrow M(z))\\\ \forall
x,y,z\>(N(x,y,z)\wedge M(x)\wedge M(y)\wedge M(z)\rightarrow F)\\\ \forall
x\>(M(x)\rightarrow A(x))\end{array}$

Then, let

$\begin{array}[]{l}\mathcal{D}=\\{M(x),A(x)\mid
x\in\mathit{PV}(\phi)\\}\,\cup\\\ \qquad\\{U(x,y)\mid
x\in\mathit{CL}(\phi)\wedge y\in\mathit{PV}(\phi)\\}\,\cup\\\
\qquad\\{P(x,y,z)\mid x,y\rightarrow z\in\mathit{CL}(\phi)\\}\,\cup\\\
\qquad\\{N(x,y,z)\mid x,y,z\rightarrow\bot\in\mathit{CL}(\phi)\\}\end{array}$

and let $\mathcal{D}^{\prime}=\mathcal{D}\setminus\\{M(x),A(x)\mid
x\in\mathit{PV}(\phi)\\}$. It is easy to verify that $\phi$ is unsatisfiable
iff $\mathcal{D}^{\prime}$ is a repair of $\langle\Sigma,\mathcal{D}\rangle$.
In particular, if $\phi$ is satisfiable, then $\mathcal{D}^{\prime}$ is not a
repair of $\langle\Sigma,\mathcal{D}\rangle$ because the database
$\mathcal{D}^{\prime\prime}=\mathcal{D}^{\prime}\cup\\{M(x)\mid
x\in\mathit{MM}(\phi)\\}$, where $\mathit{MM}(\phi)$ is the minimal model of
$\phi$, is consistent with $\Sigma$. ∎

Proof of Theorem 3

We prove the thesis by showing a reduction from CNF SAT. The reduction is
obtained by modifying the reduction from 2-QBF shown in Theorem 4.7 of (?).

Let $\Sigma$ be the following set of guarded+sticky dependencies:

$\begin{array}[]{l}R(x,y,z,w)\rightarrow\exists
x^{\prime},y^{\prime},z^{\prime}\>R(x^{\prime},y^{\prime},z^{\prime},z)\\\
R(x,0,y,z)\wedge R(x,1,y^{\prime},z^{\prime})\wedge
R_{\mathit{aux}}(x,y,z,y^{\prime},z^{\prime})\rightarrow\\\ \qquad
U(x,y,z,y^{\prime},z^{\prime})\end{array}$

Now let $\phi=\psi_{1}\wedge\ldots\wedge\psi_{n}$ be a CNF formula, where
every $\psi_{i}$ is a clause. Let $\mathit{PV}(\phi)$ be the set of
propositional variables occurring in $\phi$.

Let $\mathcal{D}^{\prime}$ be the following database:

$\begin{array}[]{l}\\{R(a,1,i,(i\bmod n)+1)\mid a\textrm{ occurs positively in
}\psi_{i}\\}\,\cup\\\ \\{R(a,0,i,(i\bmod n)+1)\mid a\textrm{ occurs negatively
in }\psi_{i}\\}\end{array}$

and let
$\mathcal{D}=\mathcal{D}^{\prime}\cup\\{R_{\mathit{aux}}(a,b,c,d,e)\mid
a,b,c,d,e\in\mathit{PV}(\phi)\\}$.

We prove that $\mathcal{D}^{\prime}$ is a repair of
$\langle\Sigma,\mathcal{D}\rangle$ iff $\phi$ is unsatisfiable. First, it is
immediate to see that $\mathcal{D}^{\prime}$ is consistent with $\Sigma$. Now,
due to the first dependency of $\Sigma$, if there exists
$\mathcal{D}^{\prime\prime}$ such that
$\mathcal{D}^{\prime}\subset\mathcal{D}^{\prime\prime}\subseteq\mathcal{D}$
and $\mathcal{D}^{\prime\prime}$ is consistent with $\Sigma$, then for every
conjunct $\psi_{i}$ there must exist at least one fact from $R$ of the form
$R(\\_,\\_,i,\\_)$ in $\mathcal{D}^{\prime\prime}$. But, due to the second
dependency of $\Sigma$, this is possible if and only if $\phi$ is satisfiable.
Consequently, $\mathcal{D}^{\prime}$ is a repair of
$\langle\Sigma,\mathcal{D}\rangle$ iff $\phi$ is unsatisfiable. ∎

Proof of Theorem 4

For the case of full dependencies, we start the proof by noticing that, given
a set of dependencies $\Sigma$, a database $\mathcal{D}$ and a subset
$\mathcal{D}^{\prime}$ of $\mathcal{D}$, $\mathcal{D}^{\prime}$ is a repair of
$\langle\Sigma,\mathcal{D}\rangle$ iff $\mathcal{D}^{\prime}$ is consistent
with $\Sigma$ and there exists no
$\alpha\in\mathcal{D}\setminus\mathcal{D}^{\prime}$ such that
$\mathcal{D}^{\prime}\cup\\{\alpha\\}$ is weakly consistent with $\Sigma$.
Consequently, Lemma 4 implies the thesis.

For linear dependencies, consider the algorithm Compute-Repair-Linear
(Algorithm 2) that, given a set of linear dependencies $\Sigma$ and a database
$\mathcal{D}$, computes the unique repair of
$\langle\Sigma,\mathcal{D}\rangle$.

Algorithm 2 Compute-Repair-Linear

0: A database $\mathcal{D}$, a set of dependencies $\Sigma$;

0: A database $\mathcal{D}^{\prime}$;

1: let $\mathcal{D}^{\prime}=\mathcal{D}$;

2: repeat

3: for all dependencies $\tau\in\Sigma$ do

4: for all instantiations $\sigma$ of $\textit{body}(\tau)$ in
$\mathcal{D}^{\prime}$ such that $\textit{head}(\sigma(\tau))$ has no image in
$\mathcal{D}^{\prime}$ do

5:
$\mathcal{D}^{\prime}=\mathcal{D}^{\prime}\setminus\textit{PA}_{b}(\sigma(\tau))$;

6: until a fixpoint for $\mathcal{D}^{\prime}$ is reached;

7: return $\mathcal{D}^{\prime}$;

It is immediate to verify that the algorithm is correct and runs in PTIME. ∎

Proof of Proposition 2

We prove by induction that, if $\mathcal{D}^{\prime}$ is not a repair of
$\langle\Sigma,\mathcal{D}\rangle$, then there exists
$\alpha\in\mathcal{D}\setminus\mathcal{D}^{\prime}$ such that
$\mathcal{D}^{\prime}\cup\\{\alpha\\}$ is consistent with $\Sigma$ (the other
direction of the proof is straightforward). Let us stratify the set of
predicates according to the dependencies (layer $1$ = predicates not occurring
in the body of any dependency; layer $i$ = predicates occurring only in the
body of dependencies such that only predicates of layers lower than $i$ occur
in the head). Let $\mathcal{D}_{i},\mathcal{D}_{i}^{\prime}$ denote
respectively the projection of $\mathcal{D}$ and $\mathcal{D}^{\prime}$ on the
predicates of layer $i$. Now:

Base case: if $\mathcal{D}_{1}\neq\mathcal{D}_{1}^{\prime}$, then there exists
a fact $\alpha\in\mathcal{D}_{1}\setminus\mathcal{D}^{\prime}$ such that
$\mathcal{D}^{\prime}\cup\\{\alpha\\}$ is consistent with $\Sigma$ (which is
due to the fact that $\alpha$ cannot generate new instantiations of bodies of
dependencies, because its predicate does not appear in any body of a
dependency);

Inductive case: if $\mathcal{D}_{j}=\mathcal{D}_{j}^{\prime}$ for each $i$
such that $1\leq j\leq i$, then for every dependency $\tau$ of the $i$-th
layer, every instantiation $\sigma$ of $\textit{body}(\tau)$ in $\mathcal{D}$
such that $\mathcal{D}\models\sigma(\textit{head}(\tau))$ is also such that
$\mathcal{D}^{\prime}\models\sigma(\textit{head}(\tau))$, consequently
$\mathcal{D}^{\prime}\cup\sigma(\textit{body}(\tau))$ is consistent with
$\Sigma$, hence $\sigma(\textit{body}(\tau))\subseteq\mathcal{D}^{\prime}$
(otherwise $\mathcal{D}^{\prime}$ would not be a repair of
$\langle\Sigma,\mathcal{D}\rangle$). Therefore, if
$\alpha\in\mathcal{D}_{i+1}\setminus\mathcal{D}_{i+1}^{\prime}$, then
$\mathcal{D}^{\prime}\cup\\{\alpha\\}$ is inconsistent with $\Sigma$. ∎

Proof of Theorem 5

First, it is immediate to verify that, for every instantiation $\sigma$ of
$p(\mathbf{x})$,
$\textit{aux}(\mathcal{D}^{\prime})\models\Psi^{\mathit{inc}}(\Sigma,\sigma(p(\mathbf{x})))$
if and only if
$\textit{aux}(\mathcal{D}^{\prime})\cup\\{\sigma(p(\mathbf{x}))\\}\models\Psi^{\mathit{inc}}(\Sigma)$.
Then, from Proposition 2 and from the fact that
$\textit{aux}(\mathcal{D}^{\prime})\models\Psi^{\mathit{inc}}(\Sigma)$ iff
$\mathcal{D}^{\prime}$ is not consistent with $\Sigma$, it follows that
$\mathcal{D}\cup\textit{aux}(\mathcal{D}^{\prime})\models\Psi^{\mathit{rc}}(\Sigma)$
iff $\mathcal{D}^{\prime}$ is a repair of $\langle\Sigma,\mathcal{D}\rangle$.
∎

Proof of Proposition 3

To prove the proposition, we introduce some auxiliary definitions. Given a
single-head full dependency $\tau$, we define the TGD $\tau_{t}$ as the TGD
obtained from $\tau$ deleting all the inequality atoms in its body. Moreover,
given a set of full dependencies $\Sigma$, we denote by $\mathit{TGD}(\Sigma)$
the set of full TGDs $\\{\tau_{t}\mid\tau\in\Sigma\\}$.

Now, the key observation is that it is very easy to modify existing rewriting
techniques for conjunctive queries over TGDs to deal with single-head full
dependencies without inequalities. E.g., the algorithm shown in (?) can very
easily be adapted to such single-head full dependencies with inequality atoms
in rule bodies. Indeed, since the dependencies are full, no variable is
deleted by the rewriting steps, which implies that the rewriting of every CQ
over $\Sigma$ can be obtained essentially in the same way as in the case of
the corresponding $\mathit{TGD}(\Sigma)$: the additional inequality atoms can
just be collected along the rewriting steps, and returned in the final
rewritten query (which is thus a UCQ with inequalities rather than a simple
UCQ). This immediately implies the following property.

######  Lemma 5.

Let $\Sigma$ be a set of full dependencies. If $\mathit{TGD}(\Sigma)$ is CQ-
FO-rewritable, then $\Sigma$ is CQ-FO-rewritable.

Now, since acyclic TGDs, linear TGDs and sticky TGDs have the CQ-FO-
rewritability property (see e.g. (?, ?)), the above lemma immediately implies
that the CQ-FO-rewritability property holds for every set of dependencies that
is either acyclic+full, or full+linear, or full+sticky. ∎

Proof of Theorem 6

First, we state the following property, whose proof immediately follows from
the definition of chase and the definition of repair.

######  Lemma 6.

Let $\Sigma$ be a set of full dependencies, and let $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ be two databases. Then, $\mathcal{D}^{\prime}$ is a
repair of $\langle\Sigma,\mathcal{D}\rangle$ iff
$\mathit{Chase}(\mathcal{D}^{\prime},\Sigma)\subseteq\mathcal{D}$ and, for
every fact $\alpha\in\mathcal{D}\setminus\mathcal{D}^{\prime}$,
$\mathit{Chase}(\mathcal{D}^{\prime}\cup\\{\alpha\\},\Sigma)\not\subseteq\mathcal{D}$.

We now prove that, for every CQ-FO-rewritable set of dependencies $\Sigma$,
the sentence $\Phi^{\mathit{rc}}(\Sigma)$ encodes the conditions of the above
lemma in terms of an FO sentence.

First, it is easy to verify that the following property holds.

######  Lemma 7.

Let $\Sigma$ be a CQ-FO-rewritable set of full dependencies, and let
$\mathcal{D}$ and $\mathcal{D}^{\prime}$ be two databases. Then,
$\mathcal{D}\cup\textit{aux}(\mathcal{D}^{\prime})\models\Phi^{\mathit{wc}}(\Sigma)$
iff $\mathit{Chase}(\mathcal{D}^{\prime},\Sigma)\subseteq\mathcal{D}$.
Moreover, for every set of atoms $\mathcal{A}$ and for every instantiation
$\sigma$ of $\textit{Vars}(\mathcal{A})$,
$\mathcal{D}\cup\textit{aux}(\mathcal{D}^{\prime})\models\sigma(\Phi^{\mathit{wc}}(\mathcal{A},\Sigma))$
iff
$\mathit{Chase}(\mathcal{D}^{\prime}\cup\sigma(\mathcal{A}),\Sigma)\subseteq\mathcal{D}$.

Now, Lemma 6 and Lemma 7 imply that, for every set of dependencies $\Sigma$
that is full and CQ-FO-rewritable,
$\mathcal{D}\cup\textit{aux}(\mathcal{D}^{\prime})\models\Phi^{\mathit{rc}}(\Sigma)$
iff $\mathcal{D}^{\prime}$ is a repair of $\langle\Sigma,\mathcal{D}\rangle$.
Thus, repair checking is FO-rewritable for every $\Sigma$ that is full and CQ-
FO-rewritable and, consequently, the problem is in $\mathrm{AC}^{0}$. ∎

Proof of Theorem 7

We prove the thesis by showing a reduction from 2-QBF that is obtained by
slightly modifying the reduction from 2-QBF shown in Theorem 4.7 of (?) (as
well as the reduction shown in the proof of Theorem 3).

Let $\Sigma$ be the following set of guarded+sticky dependencies:

$\begin{array}[]{l}\forall x,y,z,w\,R(x,y,z,w)\rightarrow\exists
x^{\prime},y^{\prime},z^{\prime}\,R(x^{\prime},y^{\prime},z^{\prime},z)\\\
\forall x,y,z,y^{\prime},z^{\prime}\,R(x,0,y,z)\wedge
R(x,1,y^{\prime},z^{\prime})\wedge\\\ \qquad
R_{\mathit{aux}}(x,y,z,y^{\prime},z^{\prime})\rightarrow
U(x,y,z,y^{\prime},z^{\prime})\end{array}$

Now let
$\phi=\forall\mathbf{x}\,\exists\mathbf{y}\,(\psi_{1}\wedge\ldots\wedge\psi_{n})$
be a 2-QBF, where every $\psi_{i}$ is a clause over the propositional
variables $\mathbf{x},\mathbf{y}$. Let
$\textit{Vars}(\phi)=\mathbf{x}\cup\mathbf{y}$.

Let $\mathcal{D}_{1}$ be the following database:

$\begin{array}[]{l}\\{R(z,1,i,(i\bmod n)+1)\mid z\textrm{ occurs positively in
}\psi_{i}\\}\,\cup\\\ \\{R(z,0,i,(i\bmod n)+1)\mid z\textrm{ occurs negatively
in }\psi_{i}\\}\end{array}$

Let $\mathcal{D}_{2}=\\{R_{\mathit{aux}}(z_{1},z_{2},z_{3},z_{4},z_{5})\mid
z_{1},z_{2},z_{3},z_{4},z_{5}\in\textit{Vars}(\phi)\\}$. Let
$\mathcal{D}_{3}=\\{R(x,1,0,0),R(x,0,0,0)\mid x\in\mathbf{x}\\}$. Finally, let
$\mathcal{D}=\mathcal{D}_{1}\cup\mathcal{D}_{2}\cup\mathcal{D}_{3}\cup\\{R(a,a,1,a)\\}$.

We prove that $\langle\Sigma,\mathcal{D}\rangle$ AR-entails $R(a,a,1,a)$ iff
$\phi$ is valid.

First, for every interpretation $I_{\mathbf{x}}$ of $\mathbf{x}$, let
$\mathcal{D}(I_{\mathbf{x}})=\\{R(x,1,0,0)\mid
I_{\mathbf{x}}(x)=1\\}\cup\\{R(x,0,0,0)\mid I_{\mathbf{x}}(x)=0\\}$ (notice
that $\mathcal{D}(I_{\mathbf{x}})\subset\mathcal{D}_{3}$).

Now let us assume that $\phi$ is not valid, and let $I_{\mathbf{x}}$ be an
interpretation of $\mathbf{x}$ such that there exists no interpretation
$I_{\mathbf{y}}$ of $\mathbf{y}$ such that $I_{\mathbf{x}}\cup
I_{\mathbf{y}}\models\psi_{1}\wedge\ldots\wedge\psi_{n}$. We prove that
$\mathcal{D}_{2}\cup\mathcal{D}(I_{\mathbf{x}})$ is a repair of
$\langle\Sigma,\mathcal{D}\rangle$. Indeed, if a fact from
$\mathcal{D}_{1}\cup\\{R(a,a,1,a)\\}$ is added to such a set, then consistency
would be possible only adding, for every conjunct $\psi_{i}$, at least one
fact of the form $R(\\_,\\_,i,\\_)$ in $\mathcal{D}_{1}$. But, due to due to
the second dependency of $\Sigma$, this is possible if and only if $\phi$ is
satisfiable. Consequently, $\mathcal{D}_{2}\cup\mathcal{D}(I_{\mathbf{x}})$ is
a repair of $\langle\Sigma,\mathcal{D}\rangle$, which implies that
$\langle\Sigma,\mathcal{D}\rangle$ does not AR-entail $R(a,a,1,a)$.

Conversely, assume that $\phi$ is valid. Let $I_{\mathbf{x}}$ be any
interpretation of $\mathbf{x}$. Then, there exists an interpretation
$I_{\mathbf{y}}$ of $\mathbf{y}$ such that $I_{\mathbf{x}}\cup
I_{\mathbf{y}}\models\psi_{1}\wedge\ldots\wedge\psi_{n}$. Now let
$\mathcal{D}(I_{\mathbf{y}})=\\{R(y,z,w,v)\mid y\in\mathbf{y}\wedge
z=I_{\mathbf{y}}(y)\wedge R(y,z,w,v)\in\mathcal{D}_{1}\\}$. It is immediate to
verify that $\mathcal{D}_{2}\cup\mathcal{D}(I_{\mathbf{y}})$ is consistent
with $\Sigma$. Now, suppose $\mathcal{D}^{\prime}$ is a repair of
$\langle\Sigma,\mathcal{D}\rangle$ and suppose
$R(a,a,1,a)\not\in\mathcal{D}^{\prime}$. This implies that all the facts of
$\mathcal{D}_{1}$ of the form $R(\\_,\\_,n,1)$ do not belong to
$\mathcal{D}^{\prime}$ (because $R(a,a,1,a)$ can only violate the first
dependency of $\Sigma$), which in turn implies (again due to the first
dependency of $\Sigma$) that all the facts of $\mathcal{D}_{1}$ of the form
$R(\\_,\\_,n-1,n)$ do not belong to $\mathcal{D}^{\prime}$, and so on: this
iteratively proves that _all_ the facts of $\mathcal{D}_{1}$ do not belong to
$\mathcal{D}^{\prime}$. Therefore, $R(a,a,1,a)\not\in\mathcal{D}^{\prime}$
implies that $\mathcal{D}^{\prime}\cap\mathcal{D}_{1}=\emptyset$, that is,
there is no fact of the form $R(y,\\_,\\_,\\_)$ with $y\in\mathbf{y}$ in
$\mathcal{D}^{\prime}$. But this immediately implies that
$\mathcal{D}^{\prime}\cup\mathcal{D}(I_{\mathbf{y}})$ is consistent with
$\Sigma$, thus contradicting the hypothesis that $\mathcal{D}^{\prime}$ is a
repair of $\langle\Sigma,\mathcal{D}\rangle$. Consequently, $R(a,a,1,a)$
belongs to every repair of $\langle\Sigma,\mathcal{D}\rangle$, and therefore
$\langle\Sigma,\mathcal{D}\rangle$ AR-entails $R(a,a,1,a)$. ∎

Proof of Theorem 8

The proof is obtained through a reduction from 3-CNF. Let $\Sigma$ be the
following set of acyclic+guarded+sticky dependencies:

$\begin{array}[]{l}\forall x\,(V(x,1)\wedge V(x,0)\rightarrow U_{1}(x))\\\
\forall
x,y_{1},y_{2},y_{3},z_{1},z_{2},z_{3}\,(C_{1}(x,y_{1},z_{1},y_{2},z_{2},y_{3},z_{3})\wedge\\\
\quad V(y_{1},z_{1})\wedge V(y_{2},z_{2})\wedge V(y_{3},z_{3})\rightarrow\\\
\quad\quad U_{2}(y_{1},z_{1},y_{2},z_{2},y_{3},z_{3}))\\\ \ldots\\\ \forall
x,y_{1},y_{2},y_{3},z_{1},z_{2},z_{3}\,(C_{7}(x,y_{1},z_{1},y_{2},z_{2},y_{3},z_{3})\wedge\\\
\quad V(y_{1},z_{1})\wedge V(y_{2},z_{2})\wedge V(y_{3},z_{3})\rightarrow\\\
\quad\quad U_{2}(y_{1},z_{1},y_{2},z_{2},y_{3},z_{3}))\\\ \forall
x,y_{1},y_{2},y_{3},y_{4},y_{5},y_{6}\\\
\quad(C_{1}(x,y_{1},y_{2},y_{3},y_{4},y_{5},y_{6})\rightarrow\\\ \qquad\exists
w_{1},w_{2},w_{3},w_{4},w_{5},w_{6}\>C_{2}(x,w_{1},w_{2},w_{3},w_{4},w_{5},w_{6}))\\\
\ldots\\\ \forall x,y_{1},y_{2},y_{3},y_{4},y_{5},y_{6}\\\
\quad(C_{6}(x,y_{1},y_{2},y_{3},y_{4},y_{5},y_{6})\rightarrow\\\ \qquad\exists
w_{1},w_{2},w_{3},w_{4},w_{5},w_{6}\>C_{7}(x,w_{1},w_{2},w_{3},w_{4},w_{5},w_{6}))\\\
U\rightarrow\exists
x,y_{1},y_{2},y_{3},y_{4},y_{5},y_{6}\>C_{1}(x,y_{1},y_{2},y_{3},y_{4},y_{5},y_{6})\end{array}$

Then, let $\mathcal{D}$ be the following database that contains:
$V(a,0),V(a,1)$ for each variable $a$ occurring in $\phi$; 7 facts
$C_{1},\ldots,C_{7}$ for each clause of $\phi$ (each such fact represents an
evaluation of the three variables of the clause that make the clause true);
and the fact $U$.

E.g. if the $i$-th clause is $\neg a\vee\neg b\vee c$, then $\mathcal{D}$ is:

$\begin{array}[]{r@{\
}l}\mathcal{D}=\\{&C_{1}(i,a,0,b,0,c,0),C_{2}(i,a,0,b,0,c,1),\\\
&C_{3}(i,a,0,b,1,c,0),C_{4}(i,a,0,b,1,c,1),\\\
&C_{5}(i,a,1,b,0,c,0),C_{6}(i,a,1,b,0,c,1),\\\ &C_{7}(i,a,1,b,1,c,1)\
\\}\end{array}$

We prove that the fact $U$ belongs to all the repairs of
$\langle\Sigma,\mathcal{D}\rangle$ iff $\phi$ is unsatisfiable.

In fact, if $\phi$ is unsatisfiable, then there is no repair of
$\langle\Sigma,\mathcal{D}\rangle$ without any fact of $C_{1}$, consequently
$U$ belongs to all the repairs of $\langle\Sigma,\mathcal{D}\rangle$.
Conversely, if $\phi$ is satisfiable, then there is a repair (where the
extension of $V$ corresponds to the interpretation satisfying $\phi$) that for
each clause does not contain at least one of the 7 facts $C_{1},\ldots,C_{7}$
representing the clause. Due to the dependencies between $C_{i}$ and
$C_{i+1}$, this implies that there is a repair that for each clause does not
contain any fact $C_{1}$, and therefore (due to the last dependency) it does
not contain the fact $U$. ∎

Proof of Theorem 9

The proof is by reduction from 3-CNF. We define the following set $\Sigma$ of
full+guarded dependencies:

$\begin{array}[]{l}\forall
x_{1},x_{2},x_{3},v_{1},v_{2},v_{3},y,z\,(S(z)\wedge\\\ \quad
C(y,z,x_{1},v_{1},x_{2},v_{2},x_{3},v_{3})\wedge V(x_{1},v_{1})\rightarrow
S(y))\\\ \forall x_{1},x_{2},x_{3},v_{1},v_{2},v_{3},y,z\,(S(z)\wedge\\\ \quad
C(y,z,x_{1},v_{1},x_{2},v_{2},x_{3},v_{3})\wedge V(x_{2},v_{2})\rightarrow
S(y))\\\ \forall x_{1},x_{2},x_{3},v_{1},v_{2},v_{3},y,z\,(S(z)\wedge\\\ \quad
C(y,z,x_{1},v_{1},x_{2},v_{2},x_{3},v_{3})\wedge V(x_{3},v_{3})\rightarrow
S(y))\\\ \forall x\,(V(x,0)\wedge V(x,1)\rightarrow U)\end{array}$

Given a 3-CNF formula $\phi$ with $m$ clauses, in the database $\mathcal{D}$,
we represent every clause of $\phi$ with a fact $C$: e.g. if the $i$-th clause
of $\phi$ is $a\vee\neg b\vee c$, we add the fact $C(i-1,i,a,1,b,0,c,1)$.

Moreover, the database contains the facts $V(p,0),V(p,1)$ for every
propositional variable $p$, and the facts

$\begin{array}[]{r@{}l}\\{S(1),S(2),\ldots,S(m)\\}\end{array}$

We prove that $\phi$ is unsatisfiable iff the fact $S(a_{m})$ belongs to all
the repairs of $\langle\Sigma,\mathcal{D}\rangle$.

First, if $\phi$ is satisfiable, then let $P$ be the set of propositional
variables occurring in $\phi$, let $I$ be an interpretation (subset of $P$)
satisfying $\phi$, and let $\mathcal{D}^{\prime}$ be the following subset of
$\mathcal{D}$:

$\begin{array}[]{r@{}l}\mathcal{D}^{\prime}=\mathcal{D}\setminus(&\\{V(p,0)\mid
p\in P\cap I\\}\;\cup\\\ &\\{V(p,1)\mid p\in P\setminus
I\\}\cup\\{S(a_{1}),\ldots,S(a_{m})\\})\end{array}$

It is immediate to verify that $\mathcal{D}^{\prime}$ is consistent with
$\Sigma$ and that $\mathcal{D}^{\prime}\cup\\{S(a_{m})\\}$ is not weakly
consistent with $\langle\Sigma,\mathcal{D}\rangle$. This is proved by the fact
that the addition of $S(a_{m})$ creates a sequence of instantiations of the
bodies of the first three dependencies of $\Sigma$ that requires (to keep the
consistency of the set) to add to $\mathcal{D}^{\prime}\cup\\{S(a_{m})\\}$
first the fact $S(a_{m-1})$, then $S(a_{m-2})$, and so on until $S(a_{1})$:
this in turn would imply to also add $S(a_{0})$, but $S(a_{0})$ does not
belong to $\mathcal{D}$, which proves that the set
$\mathcal{D}^{\prime}\cup\\{S(a_{m})\\}$ is not weakly consistent with
$\langle\Sigma,\mathcal{D}\rangle$. Consequently, there exists a repair of
$\langle\Sigma,\mathcal{D}\rangle$ that does not contain $S(a_{m})$.

On the other hand, given a guess of the atoms of the $V$ predicate satisfying
the fourth dependency and corresponding to an interpretation of the
propositional variables that does not satisfy $\phi$, it is immediate to
verify that the sequence of instantiations of the bodies of the first three
dependencies of $\Sigma$ mentioned above (which has previously lead to the
need of adding $S(a_{0})$ to the set) is blocked by the absence of some fact
for $V$. More precisely: there exists $k\leq m$ such that the atoms
$S(a_{k}),S(a_{k+1}),\ldots,S(a_{m})$ can be added to all the repairs
corresponding to such a guess of the $V$ atoms. This immediately implies that,
if $\phi$ is unsatisfiable, then $S(a_{m})$ belongs to all the repairs of
$\langle\Sigma,\mathcal{D}\rangle$. ∎

Proof of Proposition 4

It is immediate to see that, if for an image $M$ there exists no subset
$\mathcal{D}^{\prime}$ of $\mathcal{D}$ satisfying the conditions of the
algorithm, then there exists no repair of $\langle\Sigma,\mathcal{D}\rangle$
that does not contain $M$, therefore $Q$ is IAR-entailed by
$\langle\Sigma,\mathcal{D}\rangle$. Conversely, if, for every image $M$ of the
query, such a subset $\mathcal{D}^{\prime}$ exists, then
$\mathcal{D}^{\prime}$ belongs to at least a repair $\mathcal{R}$ of
$\langle\Sigma,\mathcal{D}\rangle$ which does not contain $M$, and therefore
$M$ is not contained in the intersection of all the repairs of
$\langle\Sigma,\mathcal{D}\rangle$, thus no image of $Q$ is contained in the
intersection of all the repairs, which implies that $Q$ is not IAR-entailed by
$\langle\Sigma,\mathcal{D}\rangle$. ∎

Proof of Theorem 10

First, observe that consistency of a database w.r.t. a set of dependencies can
be decided in $\mathrm{AC}^{0}$ w.r.t. data complexity, as well as the
evaluation of a BUCQ over a database. Then, theses $(i)$ and $(ii)$ follow
from Algorithm 1, Proposition 4, other than, respectively, Lemma 3 and Lemma
4. ∎

Proof of Theorem 14

First, it is easy to verify that the following property holds.

######  Lemma 8.

For every set of full dependencies $\Sigma$ such that $\Sigma$ is CQ-FO-
rewritable, for every set of atoms $\mathcal{A}$, for every BCQ $q$, for every
instantiation $\sigma$ of $\textit{Vars}(q)$, and for every database
$\mathcal{D}$, $\mathcal{D}\models\sigma(\Phi^{ni}(\mathcal{A},q,\Sigma))$ iff
there exists an instantiation $\sigma^{\prime}$ of
$\textit{Vars}(\mathcal{A})$ such that
$\mathit{Chase}(\sigma^{\prime}(\textit{Atoms}(\mathcal{A})),\Sigma)\subseteq\mathcal{D}$
and
$\mathit{Chase}(\sigma^{\prime}(\textit{Atoms}(\mathcal{A}))\cup\sigma(\textit{Atoms}(q)),\Sigma)\not\subseteq\mathcal{D}$.

Then, the following property follows from the previous lemma and from the fact
that, for every database $\mathcal{D}^{\prime}$ of size not greater than $k$,
there exists a subset $\mathcal{A}$ of
$\textit{Atoms}(\textit{Pred}(\Sigma),k)$ such that $\mathcal{D}^{\prime}$ is
an image of $\mathcal{A}$.

######  Lemma 9.

For every set of full dependencies $\Sigma$ such that $\Sigma$ is CQ-FO-
rewritable, for every BCQ $q$, for every positive integer $k$, and for every
instantiation $\sigma$ of $\textit{Vars}(q)$, and for every database
$\mathcal{D}$, $\mathcal{D}\models\Phi^{\mathit{iar}}(q,\Sigma,k)$ iff there
exists an image $M$ of $q$ in $\mathcal{D}$ such that, for every database
$\mathcal{D}^{\prime}$ such that $\mathcal{D}^{\prime}\subseteq\mathcal{D}$
and $|\mathcal{D}^{\prime}|\leq k$, if
$\mathit{Chase}(\mathcal{D}^{\prime},\Sigma)\subseteq\mathcal{D}$ then
$\mathit{Chase}(\mathcal{D}^{\prime}\cup M,\Sigma)\subseteq\mathcal{D}$.

Finally, it is easy to verify that, if $\Sigma$ is CQ-FO-rewritable, then for
every database $\mathcal{D}$ and for every BCQ $q$, if there exists a subset
$\mathcal{D}^{\prime}$ of $\mathcal{D}$ such that
$\mathit{Chase}(\mathcal{D}^{\prime},\Sigma)\subseteq\mathcal{D}$ and
$\mathit{Chase}(\mathcal{D}^{\prime}\cup M,\Sigma)\not\subseteq\mathcal{D}$,
then there exists a subset $\mathcal{D}^{\prime\prime}$ of $\mathcal{D}$ such
that $\mathit{Chase}(\mathcal{D}^{\prime\prime},\Sigma)\subseteq\mathcal{D}$
and $\mathit{Chase}(\mathcal{D}^{\prime\prime}\cup
M,\Sigma)\not\subseteq\mathcal{D}$ and $|\mathcal{D}^{\prime\prime}|\leq k$,
where $k$ is an integer that depends on $\Sigma$ and $q$ (so it does not
depend on $\mathcal{D}$).

This property and Lemma 9 immediately imply that BCQ entailment under IAR
semantics is FO-rewritable, and thus in $\mathrm{AC}^{0}$ w.r.t. data
complexity.

The FO-rewritability property immediately extends to the case when the query
is a BUCQ $Q$, since $\langle\Sigma,\mathcal{D}\rangle$ IAR-entails $Q$ iff
there exists a BCQ $q\in Q$ such that $\langle\Sigma,\mathcal{D}\rangle$ IAR-
entails $q$. ∎

Proof of Theorem 15

The following reduction from 3-CNF SAT uses a set of dependencies $\Sigma$
that is acyclic+full+guarded+sticky:

$\begin{array}[]{l}\forall x\>(V(x,0)\wedge V(x,1)\rightarrow U(x))\\\ \forall
x_{1},v_{1},x_{2},v_{2},x_{3},v_{3},z\\\
\qquad(\mathit{NC}(z,x_{1},v_{1},x_{2},v_{2},x_{3},v_{3})\rightarrow
V(x_{1},v_{1}))\\\ \forall x_{1},v_{1},x_{2},v_{2},x_{3},v_{3},z\\\
\qquad(\mathit{NC}(z,x_{1},v_{1},x_{2},v_{2},x_{3},v_{3})\rightarrow
V(x_{2},v_{2}))\\\ \forall x_{1},v_{1},x_{2},v_{2},x_{3},v_{3},z\\\
\qquad(\mathit{NC}(z,x_{1},v_{1},x_{2},v_{2},x_{3},v_{3})\rightarrow
V(x_{3},v_{3}))\end{array}$

Then, given a 3-CNF $\phi=\psi_{1}\wedge\ldots\wedge\psi_{n}$, $\mathcal{D}$
contains the following facts:

$\begin{array}[]{l}\mathcal{D}=\\{V(a,0),V(a,1)\mid
a\in\textit{Vars}(\phi)\\}\>\cup\\\
\qquad\\{\mathit{NC}(i,a,1,b,0,c,1)\mid\psi_{i}=\neg a\vee b\vee\neg
c\\}\end{array}$

Finally, we define the BCQ

$q=\exists
x_{1},v_{1},x_{2},v_{2},x_{3},v_{3},z\>\mathit{NC}(z,x_{1},v_{1},x_{2},v_{2},x_{3},v_{3})$

It is now easy to verify that $\phi$ is unsatisfiable iff
$\langle\Sigma,\mathcal{D}\rangle$ AR-entails $q$. ∎