# Consistent Query Answering for Primary Keys on Rooted Tree Queries

Paraschos Koutris  University of Wisconsin-Madison, USA  Xiating Ouyang
University of Wisconsin-Madison, USA  Jef Wijsen  University of Mons, Belgium

###### Abstract

We study the data complexity of consistent query answering (CQA) on databases
that may violate the primary key constraints. A repair is a maximal subset of
the database satisfying the primary key constraints. For a Boolean query $q$,
the problem $\mathsf{CERTAINTY}({q})$ takes a database as input, and asks
whether or not each repair satisfies $q$. The computational complexity of
$\mathsf{CERTAINTY}({q})$ has been established whenever $q$ is a self-join-
free Boolean conjunctive query, or a (not necessarily self-join-free) Boolean
path query. In this paper, we take one more step towards a general
classification for all Boolean conjunctive queries by considering the class of
rooted tree queries. In particular, we show that for every rooted tree query
$q$, $\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$, $\mathbf{NL}$-hard $\cap$
$\mathbf{LFP}$, or $\mathbf{coNP}$-complete, and it is decidable (in
polynomial time), given $q$, which of the three cases applies. We also extend
our classification to larger classes of queries with simple primary keys. Our
classification criteria rely on query homomorphisms and our polynomial-time
fixpoint algorithm is based on a novel use of context-free grammar (CFG).

##  1 Introduction

A relational database is _inconsistent_ if it violates one or more integrity
constraints that are supposed to be satisfied. Database inconsistency is a
common issue when integrating datasets from heterogeneous sources. In this
paper, we focus on what are probably the most commonly imposed integrity
constraints on relational databases: primary keys. A primary key constraint
enforces that no two distinct tuples in the same relation agree on all primary
key attributes.

A _repair_ of such an inconsistent database instance is naturally defined as a
maximal consistent subinstance of the database. Two approaches are then
possible. In _data cleaning_ , the objective is to single out the “best”
repair, which however may not be practically possible. In _consistent query
answering_ (CQA) [2], instead of cleaning the inconsistent database instance,
we attempt to query _every_ possible repair of the database and obtain the
_consistent_ (or _certain_) answers that are returned across all repairs. In
computational complexity studies, consistent query answering is commonly
defined as the following decision problem, for a fixed Boolean query $q$ and
fixed primary keys for all relation names occurring in $q$:

  * PROBLEM $\mathsf{CERTAINTY}({q})$

  * Input: A database instance $\mathbf{db}$.

  * Question: Does $q$ evaluate to true on every repair of $\mathbf{db}$?

The CQA problem for queries $q(\vec{x})$ with free variables is to find all
sequences of constants $\vec{c}$, of the same length as $\vec{x}$, such that
$q(\vec{c})$ is true in every repair. We often do not need separate treatment
for different constants, in which case we can handle $q(\vec{x})$ as Boolean
by treating free variables as if they were constants [17, 27].

The problem $\mathsf{CERTAINTY}({q})$ is obviously in $\mathbf{coNP}$ for
every Boolean first-order query $q$. It has been extensively studied for $q$
in the class of Boolean conjunctive queries, denoted $\mathsf{BCQ}$. Despite
significant research efforts (see Section 2), the following dichotomy
conjecture remains notoriously open.

######  Conjecture 1.1.

For every query $q$ in $\mathsf{BCQ}$, $\mathsf{CERTAINTY}({q})$ is either in
$\mathbf{PTIME}$ or $\mathbf{coNP}$-complete.

An ever stronger conjecture is that the dichotomy of Conjecture 1.1 extends to
unions of conjunctive queries. Fontaine [19] showed that this stronger
conjecture implies the dichotomy theorem for conservative _Constraint
Satisfaction Problems_ (CSP) [7, 54].

On the other hand, for self-join-free queries $q$ in $\mathsf{BCQ}$, the
complexity of $\mathsf{CERTAINTY}({q})$ is well established by the next
theorem.

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

For every self-join-free query $q$ in $\mathsf{BCQ}$,
$\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$, $\mathbf{L}$-complete, or
$\mathbf{coNP}$-complete, and it is decidable in polynomial time in the size
of $q$ which of the three cases applies.

Past research has indicated that the tools for proving Theorem 1.1 largely
fall short in dealing with difficulties caused by self-joins. A notable
example concerns _path queries_ , i.e., queries of the form:

$\exists x_{1}\dotsm\exists x_{k+1}({R_{1}(\underline{x_{1}},x_{2})\land
R_{2}(\underline{x_{2}},x_{3})\land\dotsm\land
R_{k}(\underline{x_{k}},x_{k+1})}).$

If a query of this form is self-join-free (i.e., if $R_{i}\neq R_{j}$ whenever
$i\neq j$), then the “attack graph” tool [39] immediately tells us that
$\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$. However, for path queries $q$
with self-joins, $\mathsf{CERTAINTY}({q})$ exhibits a tetrachotomy between
$\mathbf{FO}$, $\mathbf{NL}$-complete, $\mathbf{PTIME}$-complete, and
$\mathbf{coNP}$-complete [32], and the complexity classification requires
sophisticated tools. Note incidentally that self-join-freeness is a
simplifying assumption that is also frequent outside CQA (e.g., [20, 5, 21,
1]).

A natural question is to extend the complexity classification for path queries
to queries that are syntactically less constrained. In particular, while path
queries are restricted to binary relation names, we aim for unrestricted
arities, as in practical database systems, which brings us to the construct of
tree queries.

A query $q$ in $\mathsf{BCQ}$ is a _rooted (ordered) tree query_ if it is
uniquely (up to a variable renaming) representable by a rooted ordered tree in
which each non-leaf vertex is labeled by a relation name, and each leaf vertex
is labeled by a unary relation name, a constant, or $\bot$. The query $q$ is
read from this tree as follows: each vertex labeled by either a relation name
or $\bot$ is first associated with a fresh variable, and each vertex labeled
by a constant is associated with that same constant; then, a vertex labeled
with relation name $R$ and associated with variable $x$ represents the query
atom $R(\underline{x},y_{1},\ldots,y_{n})$, where $y_{1},\ldots,y_{n}$ are the
symbols (variables or constants) associated with the left-to-right ordered
children of the vertex $x$. The underlined position is the primary key. Note
that a vertex labeled with a relation name of arity $n+1$ must have $n$
children. For example, consider the rooted tree in Fig. 1(a) and associate
fresh variables to its vertices as depicted in Fig. 1(b). The rooted tree thus
represents a query $q_{1}$ that contains, among others, the atoms
$C(\underline{x},y,z)$ and $R(\underline{y},u_{1},v_{1})$. It is easy to see
that every path query is a rooted tree query. The class of all rooted tree
queries is denoted $\mathsf{TreeBCQ}$. We can now present our main results.

(a) A rooted ordered tree representing $q_{1}$. (b) Each vertex is associated
with a fresh variable. (c) A rooted ordered tree representing $q_{2}$.

Figure 1: The left rooted ordered tree represents (up to a variable renaming)
the Boolean conjunctive query $q_{1}$ with atoms $C(\underline{x},y,z)$,
$R(\underline{y},u_{1},v_{1})$, $A(\underline{u_{1}})$,
$B(\underline{v_{1}})$, $R(\underline{z},u_{2},v_{2})$,
$B(\underline{u_{2}})$, $A(\underline{v_{2}})$. The right rooted ordered tree
represents $q_{2}$ with atoms $C(\underline{x},y,z)$,
$R(\underline{y},u_{1},v_{1})$, $A(\underline{u_{1}})$,
$B(\underline{v_{1}})$, $R(\underline{z},u_{2},v_{2})$,
$A(\underline{u_{2}})$, $B(\underline{v_{2}})$.

######  Theorem 1.2.

For every query $q$ in $\mathsf{TreeBCQ}$, $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{FO}$, $\mathbf{NL}$-hard $\cap$ $\mathbf{LFP}$, or
$\mathbf{coNP}$-complete, and it is decidable in polynomial time in the size
of $q$ which of the three cases applies.

Here $\mathbf{LFP}$ denotes least fixed point logic as defined in [40, p. 181]
(a.k.a. $\mathbf{FO}$[$\mathbf{LFP}$]), and $\mathbf{NL}$ denotes the class of
problems decidable by a non-deterministic Turing machine using only
logarithmic space. The classification criteria implied in Theorem 1.2 are
explicitly stated in Theorem 4.1.

It will turn out that subtree homomorphisms play a crucial role in the
complexity classification of $\mathsf{CERTAINTY}({q})$ for queries $q$ in
$\mathsf{TreeBCQ}$. For example, our results show that for the queries $q_{1}$
and $q_{2}$ represented in, respectively, Fig. 1(a) and (c),
$\mathsf{CERTAINTY}({q_{1}})$ is $\mathbf{coNP}$-complete, while
$\mathsf{CERTAINTY}({q_{2}})$ is in $\mathbf{FO}$. The difference occurs
because the two ordered subtrees rooted at $R$ are isomorphic in $q_{2}$ ($A$
precedes $B$ in both subtrees), but not in $q_{1}$. Another novel and useful
tool in the complexity classification is a context-free grammar (CFG) that
generalizes the NFA for path queries used in [32].

Once Theorem 1.2 is proved, it is natural to generalize rooted tree queries
further by allowing queries that can be represented by graphs that are not
trees.

We thereto define $\mathsf{GraphBCQ}$ (Definition 9.1), a subclass of
$\mathsf{BCQ}$ that extends $\mathsf{TreeBCQ}$. In $\mathsf{GraphBCQ}$
queries, two distinct atoms can share a variable occurring at non-primary-key
positions, which requires representations by DAGs rather than trees. Moreover,
$\mathsf{GraphBCQ}$ gives up on the acyclicity requirement that is cooked into
$\mathsf{TreeBCQ}$.

Significantly, we were able to establish the $\mathbf{FO}$-boundary in the set
$\\{\mathsf{CERTAINTY}({q})\mid q\in\mathsf{GraphBCQ}\\}$.

######  Theorem 1.3.

For every query $q$ in $\mathsf{GraphBCQ}$, it is decidable whether or not
$\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$; and when it is, a first-order
rewriting can be effectively constructed.

So far, we have not achieved a fine-grained complexity classification of all
problems in $\\{\mathsf{CERTAINTY}({q})\mid q\in\mathsf{GraphBCQ}\\}$.
However, we were able to do so for the set of Berge-acyclic queries in
$\mathsf{GraphBCQ}$, denoted $\mathsf{Graph_{Berge}BCQ}$. Recall that a
conjunctive query is Berge-acyclic if its incidence graph (i.e., the
undirected bipartite graph that connects every variable $x$ to all query atoms
in which $x$ occurs) is acyclic.

######  Theorem 1.4.

For every query $q$ in $\mathsf{Graph_{Berge}BCQ}$, the problem
$\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$, $\mathbf{NL}$-hard $\cap$
$\mathbf{LFP}$, or $\mathbf{coNP}$-complete, and it is decidable in polynomial
time in the size of $q$ which of the three cases applies.

Since
$\mathsf{TreeBCQ}\subsetneq\mathsf{Graph_{Berge}BCQ}\subsetneq\mathsf{GraphBCQ}$,
Theorem 1.2 is subsumed by Theorem 1.4. We nevertheless provide Theorem 1.2
explicitly, because its proof makes up the main part of this paper. In Section
9.2, we will discuss the challenges in extending Theorem 1.4 beyond
$\mathsf{Graph_{Berge}BCQ}$.

##  2 Related Work

Inconsistency management has been studied in various database contexts (e.g.,
graph databases [4, 3], medical databases [25], online databases [26], spatial
databases [47]), and under different repair semantics (e.g., [13, 41, 50]).
Arenas, Bertossi, and Chomicki initiated Consistent Query Answering (CQA) in
1999 [2]. Twenty years later, their contribution was acknowledged in a _Gems
of PODS session_ [6]. An overview of complexity classification results in CQA
appeared in the _Database Principles_ column of SIGMOD Record [53].

The term $\mathsf{CERTAINTY}({q})$ was coined in [51] to refer to CQA for
Boolean queries $q$ on databases that violate primary keys, one per relation,
which are fixed by $q$’s schema. The complexity classification of
$\mathsf{CERTAINTY}({q})$ for the class of self-join-free Boolean conjunctive
queries underwent a series of efforts [22, 30, 33, 34, 37], until it was
revealed that the complexity of $\mathsf{CERTAINTY}({q})$ for self-join-free
conjunctive queries displays a trichotomy between $\mathbf{FO}$,
$\mathbf{L}$-complete, and $\mathbf{coNP}$-complete [35, 39]. A few extensions
beyond this trichotomy result are known. Under the requirement of self-join-
freeness, it remains decidable whether or not $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{FO}$ in the presence of negated atoms [36], multiple keys [38], and
unary foreign keys [24].

Little is known concerning the complexity classification of the problem
$\mathsf{CERTAINTY}({q})$ beyond self-join-free conjunctive queries. For the
restricted class of Boolean path queries $q$, $\mathsf{CERTAINTY}({q})$
already exhibits a tetrachotomy between $\mathbf{FO}$, $\mathbf{NL}$-complete,
$\mathbf{PTIME}$-complete and $\mathbf{coNP}$-complete [32]. Figueira et al.
[18] have recently discovered a simple fixpoint algorithm that solves
$\mathsf{CERTAINTY}({q})$ when $q$ is a self-join free conjunctive query or a
path query such that $\mathsf{CERTAINTY}({q})$ is in $\mathbf{PTIME}$. As
already discussed in Section 1, relationships have been found between CQA and
CSP [19, 42].

The counting variant of the problem $\mathsf{CERTAINTY}({q})$, denoted
$\sharp\mathsf{CERTAINTY}({q})$, asks to count the number of repairs that
satisfy some Boolean query $q$. For self-join-free Boolean conjunctive
queries, $\sharp\mathsf{CERTAINTY}({q})$ exhibits a dichotomy between FP and
$\sharp$$\mathbf{PTIME}$-complete [45]. This dichotomy has been shown to
extend to queries with self-joins if primary keys are singletons [46], and to
functional dependencies [11]. Calautti, Console, and Pieris present in [8] a
complexity analysis of these counting problems under many-one logspace
reductions and conducted an experimental evaluation of randomized
approximation schemes for approximating the percentage of repairs that satisfy
a given query [9]. CQA is also studied under different notions of repairs like
operational repairs [10, 12] and preferred repairs [48, 29]. CQA has also been
studied for queries with aggregation, in both theory and practice [16, 28].

Theoretical research in CQA has stimulated implementations and experiments in
prototype system, using different target languages and engines: SAT [15], ASP
[44, 43, 27], BIP [31], SQL [17], logic programming [23], and hypergraph
algorithms [14].

##  3 Preliminaries

We assume disjoint sets of variables and constants. A valuation over a set $U$
of variables is a total mapping $\theta$ from $U$ to the set of constants.

Atoms and key-equal facts. Every relation name has a fixed arity, and a fixed
set of primary-key positions. We will underline primary-key positions and
assume w.l.o.g. that all primary-key positions precede all other positions. An
_atom_ is then an expression
$R(\underline{s_{1},\ldots,s_{k}},s_{k+1},\ldots,s_{n})$ where each $s_{i}$ is
a variable or a constant for $1\leq i\leq n$. The sequence
$s_{1},\ldots,s_{k}$ is called the _primary key_ (of the atom). This primary
key is called _simple_ if $k=1$, and _constant-free_ if no constant occurs in
it. An atom without variables is a _fact_. Two facts are _key-equal_ if they
use the same relation name and agree on the primary key.

Database instances, blocks, and repairs. A database schema is a finite set of
relation names. All constructs that follow are defined relative to a fixed
database schema. A database instance (or _database_ for short) is a finite set
$\mathbf{db}$ of facts using only the relation names of the schema. We write
${\mathsf{adom}}({\mathbf{db}})$ for the active domain of $\mathbf{db}$ (i.e.,
the set of constants that occur in $\mathbf{db}$). A block of $\mathbf{db}$ is
a maximal set of key-equal facts of $\mathbf{db}$. Whenever a database
instance $\mathbf{db}$ is understood, we write $R(\underline{\vec{c}},*)$ for
the block that contains all facts with relation name $R$ and primary-key value
$\vec{c}$, where $\vec{c}$ is a sequence of constants. A database instance
$\mathbf{db}$ is consistent if it contains no two distinct facts that are key-
equal (i.e., if no block of $\mathbf{db}$ contains more than one fact). A
repair of $\mathbf{db}$ is an inclusion-maximal consistent subset of
$\mathbf{db}$.

Boolean conjunctive queries. A Boolean conjunctive query is a finite set
$q=\\{R_{1}(\underline{\vec{x}_{1}},\vec{y}_{1})$, $\dots$,
$R_{n}(\underline{\vec{x}_{n}},\vec{y}_{n})\\}$ of atoms. The set $q$
represents the first-order sentence with no free-variables

$\exists u_{1}\dotsm\exists
u_{k}({R_{1}(\underline{\vec{x}_{1}},\vec{y}_{1})\land\dotsm\land
R_{n}(\underline{\vec{x}_{n}},\vec{y}_{n})}),$

and we denote ${\mathbf{vars}}({q})=\\{u_{1},\dots,u_{k}\\}$, the set of
variables that occur in $q$ and denote $\mathsf{const}({q})$ as the set of
constants that occur in $q$. We write $\mathsf{BCQ}$ for the class of Boolean
conjunctive queries.

Let $q$ be a query in $\mathsf{BCQ}$. We say that $q$ has a self-join if some
relation name occurs more than once in $q$. If $q$ has no self-joins, it is
called self-join-free. We say that $q$ is _minimal_ if it is not equivalent to
a query in $\mathsf{BCQ}$ with a strictly smaller number of atoms.

Consistent query answering. For every query $q$ in $\mathsf{BCQ}$, the
decision problem $\mathsf{CERTAINTY}({q})$ takes as input a database instance
$\mathbf{db}$, and asks whether $q$ is satisfied by every repair of
$\mathbf{db}$. It is straightforward that $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{coNP}$ for every $q\in\mathsf{BCQ}$.

Rooted relation trees. A _rooted relation tree_ is a (directed) rooted ordered
tree where each internal vertex is labeled by a relation name, and each leaf
vertex is labeled with either a unary relation name, a constant, or $\bot$,
such that every two vertices sharing the same label have the same number of
children. We denote by ${\tau}^{{u}}_{{\vartriangle}}$ the subtree rooted at
vertex $u$ in $\tau$. Any rooted relation tree $\tau$ has a string
representation recursively defined as follows:

the string representation of a tree with only one vertex is the label of that
vertex; otherwise, if the root of $\tau$ is labeled $R$ and has the following
ordered children $v_{1},v_{2},\ldots,v_{n}$, then $\tau$’s string
representation is $R(s_{1},s_{2},\dots,s_{n})$, where $s_{i}$ is the string
representation of ${\tau}^{{v_{i}}}_{{\vartriangle}}$. For example, the tree
in Fig. 1(a) has string representation $C(R(A,B),R(B,A))$. We will often blur
the distinction between rooted relation trees and their string representation.

Rooted tree query and rooted tree sets. A _querification_ of a rooted relation
tree $\tau$ is a total function $f$ with domain $\tau$’s vertex set that maps
each vertex labeled by a constant to that same constant, and injectively maps
all other vertices to variables. Such a querification naturally extends to a
mapping $f(\tau)$ of the entire tree: if $u$ is a vertex in $\tau$ with label
$R$ and children $v_{1}$, $v_{2}$, …, $v_{n}$, then $f(\tau)$ contains the
atom $R(\underline{f(u)},f(v_{1}),f(v_{2}),\dots,f(v_{n}))$. A Boolean
conjunctive query is a _rooted tree query_ if it is equal to $f(\tau)$ for
some querification $f$ of some rooted relation tree $\tau$. If $q=f(\tau)$, we
also say that $q$ is _represented_ by $\tau$, in which case we often blur the
distinction between $q$ and $\tau$. We write ${R}[{x}]$ for the unique
$R$-atom in $q$ with primary key variable $x$. $\mathsf{TreeBCQ}$ denotes the
class of rooted tree queries. It can be verified that every rooted tree query
is minimal.

Every query $q$ in $\mathsf{TreeBCQ}$ is represented by a unique rooted
relation tree. Conversely, every rooted relation tree represents a query in
$\mathsf{TreeBCQ}$ that is unique up to a variable renaming. When $f(\tau)=q$,
by a slight abuse of terminology, we may use $q$ to refer to $\tau$, and use
the query variable $x$ (or the expression ${R}[{x}]$) to refer to the vertex
$u$ in $\tau$ that satisfies $f(u)=x$ and whose label is $R$. The variable $r$
is the _root variable_ of a query $q$ in $\mathsf{TreeBCQ}$ if $r$ is the root
vertex of $q$’s rooted relation tree. For two distinct vertices $x$ and $y$,
we write $x<_{{q}}y$ if the vertex $x$ is an ancestor of $y$ in $q$, and write
$x\parallel_{{q}}y$ if neither $x<_{{q}}y$ nor $y<_{{q}}x$. When $x$ and $y$
have the same label $R$, we can also write ${R}[{x}]<_{{q}}{R}[{y}]$ and
${R}[{x}]\parallel_{{q}}{R}[{y}]$ instead of $x<_{{q}}y$ and
$x\parallel_{{q}}y$ respectively. For every variable $x$ in a rooted tree
query $q$, we write ${q}^{{x}}_{{\vartriangle}}$ for the subquery of $q$ whose
rooted relation tree is the subtree rooted at vertex $x$ in $q$. A variable
$x$ is a leaf variable in $q$ if ${q}^{{x}}_{{\vartriangle}}=\bot$,
${q}^{{x}}_{{\vartriangle}}=c$, or ${q}^{{x}}_{{\vartriangle}}=A$, for some
constant $c$ or unary relation name $A$.

An _instantiation_ of a rooted relation tree $\tau$ is a total function $g$
from $\tau$’s vertex set to constants such that each vertex labeled by a
constant $c$ is mapped to $c$. Such an instantiation naturally extends to a
mapping $g(\tau)$ of the entire tree: if $u$ is a vertex in $\tau$ with label
$R$ and children $v_{1}$, $v_{2}$, …, $v_{n}$, then $g(\tau)$ contains the
fact $R(\underline{g(u)},g(v_{1}),g(v_{2}),\dots,g(v_{n}))$. A subset $S$ of
$\mathbf{db}$ is a _rooted tree set in $\mathbf{db}$ starting in $c$_ if
$S=g(\tau)$ for some instantiation $g$ of $\tau$ that maps $\tau$’s root to
$c$. A case of particular interest is when $\mathbf{db}$ is consistent, in
particular, when $\mathbf{db}$ is a repair. It can be verified that a rooted
tree set in a repair $\mathbf{r}$ is uniquely determined by a constant $c$ and
a rooted tree $\tau$ (because only one instantiation is possible); by
overloading terminology, $\tau$ is also called a rooted tree set in
$\mathbf{r}$ starting in $c$. For convenience, an empty rooted tree set,
denoted by $\bot$, starts in any constant $c$.

Homomorphism. Let $p,q\in\mathsf{BCQ}$. We write $p\leq_{{}\rightarrow{}}q$ if
there exists a homomorphism from $p$ to $q$, i.e., a mapping
$h:\mathsf{vars}({p})\rightarrow\mathsf{vars}({q})\cup\mathsf{const}({q})$
that acts as identity when applied on constants, such that for every atom
$R(\underline{\vec{x}},\vec{y})$ in $p$,
$R(\underline{h(\vec{x})},h(\vec{y}))$ is an atom of $q$. For
$u\in{\mathbf{vars}}({p})$ and $v\in{\mathbf{vars}}({q})$, we write
$p\leq_{{u}\rightarrow{v}}q$ if there exists a homomorphism $h$ from $p$ to
$q$ with $h(u)=v$. It can now be verified that for rooted tree queries $p$ and
$q$, there is a homomorphism $h$ from $p$ to $q$ if and only if there is a
label-preserving graph homomorphism from the rooted relation tree of $p$ to
that of $q$ (we assume that a leaf vertex with label $\bot$ can map to a
vertex with any label). Since rooted relation trees are _ordered_ trees, graph
homomorphisms must evidently be order-preserving. For example, there is no
homomorphism between the trees $R(A,B)$ and $R(B,A)$.

######  Example 3.1.

The following rooted tree query and its rooted relation tree are depicted in
Fig. 2:

$\displaystyle q=\\{$ $\displaystyle
A(\underline{x_{0}},x_{1},x_{2}),R(\underline{x_{1}},x_{3},x_{4}),R(\underline{x_{2}},x_{5},x_{6}),$
$\displaystyle R(\underline{x_{3}},x_{7},x_{8}),U(\underline{x_{7}}),$
$\displaystyle
X(\underline{x_{4}},c_{1}),Y(\underline{x_{5}},x_{9}),Z(\underline{x_{6}},c_{2},x_{10})\\}.$

We have:

$\displaystyle{q}^{{x_{1}}}_{{\vartriangle}}$
$\displaystyle=R(\underline{x_{1}},x_{3},x_{4}),R(\underline{x_{3}},x_{7},x_{8}),U(\underline{x_{7}}),X(\underline{x_{4}},c_{1})$
$\displaystyle=R(R(U,\bot),X(c_{1})),$
$\displaystyle{q}^{{x_{2}}}_{{\vartriangle}}$
$\displaystyle=R(\underline{x_{2}},x_{5},x_{6}),Y(\underline{x_{5}},x_{9}),Z(\underline{x_{6}},c_{2},x_{10})$
$\displaystyle=R(Y(\bot),Z(c_{2},\bot)),$
$\displaystyle{q}^{{x_{3}}}_{{\vartriangle}}$
$\displaystyle=R(\underline{x_{3}},x_{7},x_{8}),U(\underline{x_{7}})$
$\displaystyle=R(U,\bot).$

In this query $q$, we have ${R}[{x_{1}}]\parallel_{{q}}{R}[{x_{2}}]$,
${R}[{x_{1}}]<_{{q}}{R}[{x_{3}}]$, and
${R}[{x_{2}}]\parallel_{{q}}{R}[{x_{3}}]$.

(a) A rooted relation tree $\tau$ (b) A mapping $f$ from vertices in $\tau$ to
variables in $q$

Figure 2: An example rooted relation tree, where $c_{1}$ and $c_{2}$ are
constants.

##  4 The Complexity Classification

Our classification focuses on rooted tree queries ($\mathsf{TreeBCQ}$). We
will extend to $\mathsf{Graph_{Berge}BCQ}$ and $\mathsf{GraphBCQ}$ in Section
9. The classification of path queries in [32] uses a notion of “rewinding” to
deal with self-joins: a path query $u\cdot Rv\cdot Rw$ rewinds to $u\cdot
Rv\cdot Rv\cdot Rw$. Very informally, rewinding captures that query atoms with
the same relation name can be “confused” with one another (or “rewind” to one
another in our terminology) during query evaluation: in $u\cdot Rv\cdot Rw$,
once we have evaluated the prefix $u\cdot Rv\cdot R$, the last $R$ can be
confused with the first one, in which case we continue with the suffix
$Rv\cdot Rw$ (instead of merely $Rw$). We generalize the notion of rewinding
from path queries to rooted tree queries.

######  Definition 4.1 (Rewinding).

Let $q$ be a query in $\mathsf{TreeBCQ}$. Let $R(\underline{x},\dots)$ and
$R(\underline{y},\dots)$ be two (not necessarily distinct) atoms in $q$. We
define ${q}^{{R}:{y}\looparrowright{x}}$ as the following rooted tree query

${q}^{{R}:{y}\looparrowright{x}}:=\left({q\setminus{q}^{{y}}_{{\vartriangle}}}\right)\cup
f({q}^{{x}}_{{\vartriangle}}),$

for some isomorphism $f$ that maps $x$ to $y$ (i.e., $f(x)=y$), and maps every
other variable in ${q}^{{x}}_{{\vartriangle}}$ to a fresh variable.

Intuitively, the rooted tree query ${q}^{{R}:{y}\looparrowright{x}}$ can be
obtained by replacing ${q}^{{y}}_{{\vartriangle}}$ with a fresh copy of
${q}^{{x}}_{{\vartriangle}}$. Fig. 3 presents some rooted tree queries
obtained from rewinding on the rooted tree $q$ in Fig. 2.

(a) ${q}^{{R}:{x_{1}}\looparrowright{x_{2}}}$ (b)
${q}^{{R}:{x_{2}}\looparrowright{x_{1}}}$ (c)
${q}^{{R}:{x_{3}}\looparrowright{x_{1}}}$

Figure 3: An illustration of rewinding for the query of Fig. 2; the modified
subtrees are highlighted in red.

The classification criteria in [32] uses the notions of factors and prefixes
that are specific to words, which can be generalized using homomorphism on
rooted tree queries. Consider the following syntactic conditions on a rooted
tree query $q$ with root variable $r$:

  * •

$\mathsf{C}_{2}$ : for every two atoms $R(\underline{x},\dots)$ and
$R(\underline{y},\dots)$ in $q$, either
$q\leq_{{}\rightarrow{}}{q}^{{R}:{y}\looparrowright{x}}$ or
$q\leq_{{}\rightarrow{}}{q}^{{R}:{x}\looparrowright{y}}$.

  * •

$\mathsf{C}_{1}$ : for every two atoms $R(\underline{x},\dots)$ and
$R(\underline{y},\dots)$ in $q$, either
$q\leq_{{r}\rightarrow{r}}{q}^{{R}:{y}\looparrowright{x}}$ or
$q\leq_{{r}\rightarrow{r}}{q}^{{R}:{x}\looparrowright{y}}$.

It is easy to see that conditions $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$ are
decidable in polynomial time in the size of the query. We may restate
$\mathsf{C}_{2}$ and $\mathsf{C}_{1}$ using more fine-grained syntactic
conditions below.

  * •

$\mathsf{C}_{\mathsf{branch}}$ : for every two atoms
${R}[{x}]\parallel_{{q}}{R}[{y}]$ in $q$, either
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$
or
${q}^{{x}}_{{\vartriangle}}\leq_{{x}\rightarrow{y}}{q}^{{y}}_{{\vartriangle}}$.

  * •

$\mathsf{C}_{\mathsf{factor}}$ : for every two atoms ${R}[{x}]<_{{q}}{R}[{y}]$
in $q$, we have $q\leq_{{}\rightarrow{}}{q}^{{R}:{y}\looparrowright{x}}$.

  * •

$\mathsf{C}_{\mathsf{prefix}}$ : for every two atoms ${R}[{x}]<_{{q}}{R}[{y}]$
in $q$, we have $q\leq_{{r}\rightarrow{r}}{q}^{{R}:{y}\looparrowright{x}}$.

######  Lemma 4.1.

For every two atoms ${R}[{x}]\parallel_{{q}}{R}[{y}]$ in a rooted tree query
$q$, we have $q\leq_{{}\rightarrow{}}{q}^{{R}:{y}\looparrowright{x}}$ if and
only if
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$.

For the sake of simplicity, we postpone the proof of Lemma 4.1 to Appendix A.
Lemma 4.1 implies the following connections among the syntactic conditions.

######  Proposition 4.1.

$\mathsf{C}_{2}=\mathsf{C}_{\mathsf{factor}}\land\mathsf{C}_{\mathsf{branch}}$,
$\mathsf{C}_{1}=\mathsf{C}_{\mathsf{prefix}}\land\mathsf{C}_{\mathsf{branch}}$.

(a) $\mathsf{C}_{1}$ (b) $\mathsf{C}_{2},\lnot\mathsf{C}_{\mathsf{prefix}}$
(c) $\lnot\mathsf{C}_{\mathsf{branch}}$ (d) $\mathsf{C}_{1}$

(e) $\mathsf{C}_{1}$ (f) $\lnot\mathsf{C}_{\mathsf{branch}}$ (g)
$\lnot\mathsf{C}_{\mathsf{factor}}$

Figure 4: Examples of rooted relation trees. Trees annotated with
$\lnot\mathsf{C}$ violate syntactic condition $\mathsf{C}$, while trees
annotated with $\mathsf{C}$ satisfy $\mathsf{C}$. For example, the tree in (a)
satisfies $\mathsf{C}_{1}$; and the tree (b) satisfies $\mathsf{C}_{2}$ but
violates $\mathsf{C}_{\mathsf{prefix}}$.

######  Example 4.1.

Let $q$ be as in Fig. 2. We have that $q$ violates
$\mathsf{C}_{\mathsf{branch}}$ (and therefore $\mathsf{C}_{2}$), since there
is no homomorphism from $q$ to neither
${q}^{{R}:{x_{1}}\looparrowright{x_{2}}}$ nor
${q}^{{R}:{x_{2}}\looparrowright{x_{1}}}$.

Fig. 4 shows some example rooted relation trees annotated with the syntactic
conditions they satisfy or violate.

Our main classification result can now be stated.

######  Theorem 4.1 (Trichotomy Theorem).

For every query $q$ in $\mathsf{TreeBCQ}$,

  * •

if $q$ satisfies $\mathsf{C}_{2}$, then the problem $\mathsf{CERTAINTY}({q})$
is in $\mathbf{LFP}$; otherwise it is $\mathbf{coNP}$-complete; and

  * •

if $q$ satisfies $\mathsf{C}_{1}$, then the problem $\mathsf{CERTAINTY}({q})$
is in $\mathbf{FO}$; otherwise it is $\mathbf{NL}$-hard.

Let us provide some intuitions behind Theorem 4.1. Both
$\mathsf{C}_{\mathsf{prefix}}$ and $\mathsf{C}_{\mathsf{factor}}$ concern the
homomorphism from $q$ to the rooted tree query obtained by rewinding from a
subtree to its ancestor subtree, which resembles the case on path queries. The
condition $\mathsf{C}_{\mathsf{branch}}$ is vacuously satisfied for path
queries, but is crucial to the classification of rooted tree queries.

For the complexity lower bound, if $q$ violates
$\mathsf{C}_{\mathsf{branch}}$, then $\mathsf{CERTAINTY}({q})$ is
$\mathbf{coNP}$-hard. Intuitively, this is because if
${q}^{{x}}_{{\vartriangle}}$ and ${q}^{{y}}_{{\vartriangle}}$ are not
homomorphically comparable and appear in different branches, then the facts in
their common ancestor relation may “choose” which branch to satisfy, which
allows us to reduce from SAT in item (1) of Proposition 8.1. For example,
consider the query $q_{1}$ as in Fig. 1(a) and the example database instance
$\mathbf{db}$ in Fig. 5. It can be shown that there is a repair of
$\mathbf{db}$ that falsifies $q_{1}$ if and only if the following CNF formula
is satisfiable:

$\underbrace{(x_{1}\lor
x_{2})}_{C_{1}}\land\underbrace{(\overline{x_{1}}\lor\overline{x_{2}})}_{C_{2}}.$

For the complexity upper bound, if
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
the arguments above fail because the facts in their common ancestor relation
cannot “choose” which branch to satisfy anymore: informally, whenever
${q}^{{x}}_{{\vartriangle}}$ is satisfied, ${q}^{{y}}_{{\vartriangle}}$ will
be satisfied due to the homomorphism. This crucial observation from
$\mathsf{C}_{\mathsf{branch}}$ also leads to a total preorder on all self-
joining atoms, which allows us to deal with self-joining atoms in different
branches as if they were on a path.

$\begin{array}[]{ccc}\begin{array}[]{c|ccc}C&\underline{1}&2&3\bigstrut\\\
\cline{2-4}\cr\ast&c_{1}&x_{1}&z_{-}\\\ &c_{1}&x_{2}&z_{-}\\\
\cdashline{2-4}&c_{2}&z_{+}&x_{1}\\\
\ast&c_{2}&z_{+}&x_{2}\end{array}&\begin{array}[]{c|ccc}R&\underline{1}&2&3\bigstrut\\\
\cline{2-4}\cr&x_{1}&a&b\\\ \ast&x_{1}&b&a\\\ \cdashline{2-4}\ast&x_{2}&a&b\\\
&x_{2}&b&a\\\ \cdashline{2-4}\ast&z_{+}&a&b\\\
\cdashline{2-4}\ast&z_{-}&b&a\end{array}&\begin{array}[]{c|c}A&\underline{1}\\\
\cline{2-2}\cr\ast&a\\\ \\\ B&\underline{1}\\\
\cline{2-2}\cr\ast&b\end{array}\end{array}$ Figure 5: An inconsistent database
instance $\mathbf{db}$ for $\mathsf{CERTAINTY}({q_{1}})$, where $q_{1}$ is
represented in Fig. 1(a). Blocks are separated by dashed lines. The facts with
$\ast$ form a repair that falsifies $q_{1}$, corresponding to a satisfying
truth assignment $x_{1}=1$ and $x_{2}=0$.

######  Definition 4.2 (Relation $\preceq_{q}$).

Let $q$ be a query in $\mathsf{TreeBCQ}$. Let ${R}[{x}]$ and ${R}[{y}]$ be two
atoms in $q$. We write ${R}[{x}]\preceq_{q}{R}[{y}]$ if either
${R}[{x}]<_{{q}}{R}[{y}]$ or
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$.

######  Proposition 4.2.

Let $q$ be a query in $\mathsf{TreeBCQ}$ satisfying
$\mathsf{C}_{\mathsf{branch}}$. For every relation name $R$, the relation
$\preceq_{q}$ is a total preorder on all $R$-atoms in $q$.

###### Proof.

We first show that every two distinct atoms ${R}[{x}]$ and ${R}[{x}]$ are
comparable by $\preceq_{q}$. Let ${R}[{x}]$ and ${R}[{y}]$ be two distinct
atoms in $q$. The claim holds if ${R}[{x}]<_{{q}}{R}[{y}]$ or
${R}[{y}]<_{{q}}{R}[{x}]$. Otherwise, we have
${R}[{x}]\parallel_{{q}}{R}[{y}]$, and since $q$ satisfies
$\mathsf{C}_{\mathsf{branch}}$, we have either
${q}^{{x}}_{{\vartriangle}}\leq_{{x}\rightarrow{y}}{q}^{{y}}_{{\vartriangle}}$
or
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
as desired.

Next we show show that $\preceq_{q}$ is transitive. Assume
${R}[{x}]\preceq_{q}{R}[{y}]$ and ${R}[{y}]\preceq_{q}{R}[{z}]$. We
distinguish four cases.

  * •

Case that ${R}[{x}]<_{{q}}{R}[{y}]$ and ${R}[{y}]<_{{q}}{R}[{z}]$. Then we
have ${R}[{x}]<_{{q}}{R}[{z}]$, as desired.

  * •

Case that
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$
and
${q}^{{z}}_{{\vartriangle}}\leq_{{z}\rightarrow{y}}{q}^{{y}}_{{\vartriangle}}$.
Then we have
${q}^{{z}}_{{\vartriangle}}\leq_{{z}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
as desired.

  * •

Case that ${R}[{x}]<_{{q}}{R}[{y}]$ and
${q}^{{z}}_{{\vartriangle}}\leq_{{z}\rightarrow{y}}{q}^{{y}}_{{\vartriangle}}$.
The claim follows if ${R}[{x}]<_{{q}}{R}[{z}]$. Suppose for contradiction that
${R}[{z}]<_{{q}}{R}[{x}]$. Then ${R}[{z}]<_{{q}}{R}[{y}]$, and
${q}^{{z}}_{{\vartriangle}}$ contains more atoms than
${q}^{{y}}_{{\vartriangle}}$. However, we have
${q}^{{z}}_{{\vartriangle}}\leq_{{z}\rightarrow{y}}{q}^{{y}}_{{\vartriangle}}$,
a contradiction. It then must be that ${R}[{x}]\parallel_{{q}}{R}[{z}]$.
Suppose for contradiction that
${q}^{{x}}_{{\vartriangle}}\leq_{{x}\rightarrow{z}}{q}^{{z}}_{{\vartriangle}}$.
Then we have
${q}^{{x}}_{{\vartriangle}}\leq_{{x}\rightarrow{y}}{q}^{{y}}_{{\vartriangle}}$,
but ${R}[{x}]<_{{q}}{R}[{y}]$, a contradiction. Since $q$ satisfies
$\mathsf{C}_{\mathsf{branch}}$, we have
${q}^{{z}}_{{\vartriangle}}\leq_{{z}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
as desired.

  * •

Case that
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$
and ${R}[{y}]<_{{q}}{R}[{z}]$. The claim follows if ${R}[{x}]<_{{q}}{R}[{z}]$.
Suppose for contradiction that ${R}[{z}]<_{{q}}{R}[{x}]$. Then
${R}[{y}]<_{{q}}{R}[{x}]$, and ${q}^{{y}}_{{\vartriangle}}$ contains more
atoms than ${q}^{{x}}_{{\vartriangle}}$. However, we have
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
a contradiction. It then must be that ${R}[{x}]\parallel_{{q}}{R}[{z}]$.
Suppose for contradiction that
${q}^{{x}}_{{\vartriangle}}\leq_{{x}\rightarrow{z}}{q}^{{z}}_{{\vartriangle}}$.
Then we have
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{z}}{q}^{{z}}_{{\vartriangle}}$,
but ${R}[{y}]<_{{q}}{R}[{z}]$, a contradiction. Since $q$ satisfies
$\mathsf{C}_{\mathsf{branch}}$, it follows that
${q}^{{z}}_{{\vartriangle}}\leq_{{z}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$.

This concludes the proof. ∎

The remainder of this paper is organized as follows. Section 5 defines a
context-free grammar ${\mathsf{CFG^{\clubsuit}}}({q})$ for each
$q\in\mathsf{TreeBCQ}$, and the problem $\mathsf{CERTAIN}_{\mathsf{tr}}({q})$
that concerns ${\mathsf{CFG^{\clubsuit}}}({q})$. Lemma 5.1 concludes the
equivalence of $\mathsf{CERTAINTY}({q})$ and
$\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ if $q$ satisfies $\mathsf{C}_{2}$ (or
$\mathsf{C}_{1}$). Section 6, we show that
$\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ is in $\mathbf{LFP}$ (and in
$\mathbf{PTIME}$) if $q$ satisfies $\mathsf{C}_{\mathsf{branch}}$. In Sections
7 and 8, we show the upper bounds and lower bounds in Theorem 4.1
respectively. In Section 9, we prove Theorems 1.3 and 1.4.

##  5 Context-Free Grammar

We first generalize NFAs used in the study of path queries [32] to context-
free grammars (CFGs).

######  Definition 5.1 (${\mathsf{CFG^{\clubsuit}}}({q})$).

Let $q$ be a query in $\mathsf{TreeBCQ}$ with root variable $r$. We define a
context-free grammar ${\mathsf{CFG^{\clubsuit}}}({q})$ over the string
representations of rooted relation trees for each rooted tree query $q$. The
alphabet $\Sigma$ of ${\mathsf{CFG^{\clubsuit}}}({q})$ contains every relation
symbol and constant in $q$, open/close parentheses, $\bot$ and comma.

Whenever $v$ is a variable or a constant in $q$, there is a nonterminal symbol
$S_{v}$. Every symbol in $\Sigma$ is a terminal symbol. The rules of
${\mathsf{CFG^{\clubsuit}}}({q})$ are as follows:

  * •

for each atom ${R}[{y}]=R(\underline{y},y_{1},y_{2},\dots,y_{n})$ in $q$,
there is a forward production rule

$S_{y}\rightarrow_{q}R(S_{y_{1}},S_{y_{2}},\dots,S_{y_{n}})$ (1)

  * •

whenever ${R}[{x}]$ and ${R}[{y}]$ are atoms in $q$ such that
${R}[{x}]<_{{q}}{R}[{y}]$, there is a backward production rule

$S_{y}\rightarrow_{q}S_{x}$ (2)

  * •

for every leaf variable $u$ whose label $L$ is either $\bot$ or a unary
relation name, there is a rule

$S_{u}\rightarrow_{q}L$ (3)

  * •

for each constant $c$ in $q$, there is a rule

$S_{c}\rightarrow_{q}c$ (4)

The starting symbol of ${\mathsf{CFG^{\clubsuit}}}({q})$ is $S_{r}$ where $r$
is the root variable of $q$. A rooted relation tree $\tau$ is accepted by
${\mathsf{CFG^{\clubsuit}}}({q})$, denoted as
$\tau\in{\mathsf{CFG^{\clubsuit}}}({q})$, if the string representation of
$\tau$ can be derived from $S_{r}$, written as
$S_{r}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau$.

######  Example 5.1.

Let $q$ be as in Fig. 2(a) with variables labeled as in Fig. 2(b). The rooted
relation tree $\tau$ in Fig. 3(c) has string representation
$\tau=A(\tau_{1},\tau_{2})$ where

$\displaystyle\tau_{1}$ $\displaystyle=R(R(R(U,\bot),X(c_{1})),X(c_{1})),$
$\displaystyle\tau_{2}$ $\displaystyle=R(Y(\bot),Z(c_{2},\bot)).$

We have $S_{x_{2}}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau_{2}$ by
applying only forward rewrite rules. We show next
$S_{x_{1}}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau_{1}$, using a
backward rewrite rule $S_{x_{3}}\rightarrow_{q}S_{x_{1}}$ at some point:

$\displaystyle S_{x_{1}}$ $\displaystyle\rightarrow_{q}R(S_{x_{3}},S_{x_{4}})$
$\displaystyle\rightarrow_{q}R(S_{x_{1}},X(S_{c_{1}}))$
$\displaystyle\rightarrow_{q}R(R(S_{x_{3}},S_{x_{4}}),X(c_{1}))$
$\displaystyle\rightarrow_{q}R(R(R(S_{x_{7}},S_{x_{8}}),X(S_{c_{1}})),X(c_{1}))$
$\displaystyle\rightarrow_{q}R(R(R(U,\bot)),X(c_{1})),X(c_{1}))=\tau_{1}.$

Thus
$S_{x_{0}}\rightarrow_{q}A(S_{x_{1}},S_{x_{2}})\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}A(\tau_{1},\tau_{2})=\tau.$
So it is correct to conclude that $\tau$ is accepted by
${\mathsf{CFG^{\clubsuit}}}({q})$.

Recall from Section 3 that a rooted tree set in a repair $\mathbf{r}$ is
uniquely determined by a rooted tree $\tau$ and a constant $c$; such a rooted
tree set is said to be accepted by ${\mathsf{CFG^{\clubsuit}}}({q})$ if
$\tau\in{\mathsf{CFG^{\clubsuit}}}({q})$. For our technical treatment later,
we next define modifications of ${\mathsf{CFG^{\clubsuit}}}({q})$ by changing
its starting terminal.

######  Definition 5.2 (${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{u})$).

For a query $q$ in $\mathsf{TreeBCQ}$ and a variable $u$ in $q$, we define
${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{u})$ as the context-free grammar
that accepts a rooted relation tree $\tau$ if and only if
$S_{u}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau$.

We now introduce the _certain trace problem_. For each $q$ in
$\mathsf{TreeBCQ}$, $\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ is defined as the
following decision problem:

  * PROBLEM $\mathsf{CERTAIN}_{\mathsf{tr}}({q})$

  * Input: A database instance $\mathbf{db}$.

  * Question: Is there a constant $c\in\mathbf{db}$, such that for every repair $\mathbf{r}$ of $\mathbf{db}$, there is a rooted tree set $\tau$ in $\mathbf{r}$ starting in $c$ with $\tau\in{\mathsf{CFG^{\clubsuit}}}({q})$?

The problems $\mathsf{CERTAINTY}({q})$ and
$\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ reduce to each other if $q$ satisfies
$\mathsf{C}_{2}$.

######  Lemma 5.1.

Let $q$ be a query in $\mathsf{TreeBCQ}$ satisfying $\mathsf{C}_{2}$. Let
$\mathbf{db}$ be a database instance. Then the following statements are
equivalent:

  1. 1.

$\mathbf{db}$ is a “yes”-instance of $\mathsf{CERTAINTY}({q})$; and

  2. 2.

$\mathbf{db}$ is a “yes”-instance of $\mathsf{CERTAIN}_{\mathsf{tr}}({q})$.

The proof of Lemma 5.1 is deferred to Section 7 since it requires some useful
results to be developed in the subsequent sections.

##  6 Membership of $\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ in $\mathbf{LFP}$

In this section, we show that the problem
$\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ is expressible in $\mathbf{LFP}$ (and
thus in $\mathbf{PTIME}$) if $q$ satisfies $\mathsf{C}_{\mathsf{branch}}$. Let
$\mathbf{db}$ be a database instance. Consider the algorithm in Fig. 6,
following a dynamic programming fashion. The algorithm iteratively computes a
set $B$ of pairs $\langle{c},{y}\rangle$ until it reaches a fixpoint, ensuring
that

> whenever $\langle{c},{y}\rangle$ is added to $B$, then every repair of
> $\mathbf{db}$ contains a rooted tree set starting in $c$ that is accepted by
> ${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$.

Intuitively, this holds true because $\langle{c},{y}\rangle$ is added to $B$
if for every possible fact $f=R(\underline{c},\vec{d})$ that can be chosen by
a repair of $\mathbf{db}$, the context-free grammar
${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$ can proceed by firing forward
rule with nonterminal $S_{y}$ that consumes $f$ from the rooted tree set, or
by non-deterministically firing some backward rule of the form
$S_{y}\rightarrow_{q}S_{x}$.

The formal semantics for each pair $\langle{c},{y}\rangle$ is stated in Lemma
6.1.

Initialization Step: |  for every $c\in{\mathsf{adom}}({\mathbf{db}})$ and leaf variable or constant $u$ in $q$
---|---
|  |  add $\langle{c},{u}\rangle$ to $B$ if |  $u=c$ is a constant,
---|---
| or the label of variable $u$ in $q$ is either $\bot$,
| or $L$ with $L(\underline{c})\in\mathbf{db}$.
Iterative Rule: |  for every $c\in{\mathsf{adom}}({\mathbf{db}})$ and atom $R(\underline{y},y_{1},y_{2},\dots,y_{n})$ in $q$
|  |  add $\langle{c},{y}\rangle$ to $B$ if the following formula holds:
---

$\exists\vec{d}:R(\underline{c},\vec{d})\in\mathbf{db}\land\forall\vec{d}:\left({R(\underline{c},\vec{d})\in\mathbf{db}\rightarrow\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})}\right),$

where

$\begin{array}[]{l}\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})=\underbrace{\left({\displaystyle{\bigwedge_{1\leq
i\leq n}}\langle{d_{i}},{y_{i}}\rangle\in B}\right)}_{\text{forward
production}}\lor\underbrace{\left({\displaystyle{\bigvee_{{R}[{x}]<_{{q}}{R}[{y}]}}\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{x})}\right)}_{\text{backward
production}}\end{array}$

and $\vec{d}=\langle d_{1},d_{2},\dots,d_{n}\rangle$.

Figure 6: A fixpoint algorithm for computing a set $B$, for a fixed rooted
tree $q$.

######  Lemma 6.1.

Let $q$ be a query in $\mathsf{TreeBCQ}$ satisfying
$\mathsf{C}_{\mathsf{branch}}$. Let $\mathbf{db}$ be a database instance. Let
$B$ be the output of the algorithm in Fig. 6. Then for any constant
$c\in{\mathsf{adom}}({\mathbf{db}})$ and a variable $y$ in $q$, the following
statements are equivalent:

  1. 1.

$\langle{c},{y}\rangle\in B$; and

  2. 2.

for every repair $\mathbf{r}$ of $\mathbf{db}$, there exists a rooted tree set
$\tau$ in $\mathbf{r}$ starting in $c$ such that
$\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$.

The crux in the proof of Lemma 6.1 relies on the existence of repairs called
_frugal_ : to show item (2) of Lemma 6.1, it will be sufficient to show that
it holds true for frugal repairs. Frugal repairs also turn out to be useful in
proving Lemma 5.1 and offer an alternative perspective to the algorithm, as
stated in Corollary 7.1.

###  6.1 Frugal repairs

We first show that the evaluation result of the predicate “$\mathsf{fact}$”
and the membership in $B$ in the algorithm of Fig. 6 propagate along the total
preorder $\preceq_{q}$.

######  Lemma 6.2.

Let $q$ be a query in $\mathsf{TreeBCQ}$ satisfying
$\mathsf{C}_{\mathsf{branch}}$, and $\mathbf{db}$ a database instance. Let
${R}[{x}],{R}[{y}]$ be two atoms of $q$. Then for every fact
$R(\underline{c},\vec{d})$ in $\mathbf{db}$ and two atoms
${R}[{x}]\preceq_{q}{R}[{y}]$,

  1. 1.

if $\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{x})$ is true, then
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ is true, where
$\mathsf{fact}$ is defined by the algorithm of Fig. 6; and

  2. 2.

if $\langle{c},{x}\rangle\in B$, then $\langle{c},{y}\rangle\in B$, where $B$
is the output of the algorithm of Fig. 6; and

The technical proof of Lemma 6.2 is deferred to Appendix B.

######  Definition 6.1 (Frugal Set).

Let $q$ be a query in $\mathsf{TreeBCQ}$ satisfying
$\mathsf{C}_{\mathsf{branch}}$, and $\mathbf{db}$ a database instance. Let
$f=R(\underline{c},\vec{d})$ be an $R$-fact in $\mathbf{db}$. We define the
frugal set of $f$ in $\mathbf{db}$ with respect to $q$ as

${\mathsf{FrugalSet}}_{q}({f},{\mathbf{db}})=\\{{R}[{x}]\in\mathsf{atoms}({q})\mid\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{x})\text{
is true}\\}.$

######  Lemma 6.3.

Let $q$ be a query in $\mathsf{TreeBCQ}$ satisfying
$\mathsf{C}_{\mathsf{branch}}$, and $\mathbf{db}$ a database instance. For
every two key-equal facts $f$ and $g$ in $\mathbf{db}$, the sets
${\mathsf{FrugalSet}}_{q}({f},{\mathbf{db}})$ and
${\mathsf{FrugalSet}}_{q}({g},{\mathbf{db}})$ are comparable by $\subseteq$.

###### Proof.

Suppose for contradiction that there exists two key-equal facts
$f=R(\underline{c},\vec{d_{1}})$ and $g=R(\underline{c},\vec{d_{2}})$ in
$\mathbf{db}$ such that
${R}[{x}]\in{\mathsf{FrugalSet}}_{q}({f},{\mathbf{db}})\setminus{\mathsf{FrugalSet}}_{q}({g},{\mathbf{db}})$
and
${R}[{y}]\in{\mathsf{FrugalSet}}_{q}({g},{\mathbf{db}})\setminus{\mathsf{FrugalSet}}_{q}({f},{\mathbf{db}})$.
By Proposition 4.2, assume without loss of generality that
${R}[{x}]\preceq_{q}{R}[{y}]$. Then since
${R}[{x}]\in{\mathsf{FrugalSet}}_{q}({f},{\mathbf{db}})$, we have
$\mathsf{fact}({R}(\underline{{c}},{\vec{d_{1}}}),{x})$ is true, and thus
$\mathsf{fact}({R}(\underline{{c}},{\vec{d_{1}}}),{y})$ is true by Lemma 6.2,
and hence ${R}[{y}]\in{\mathsf{FrugalSet}}_{q}({f},{\mathbf{db}})$, a
contradiction. A similar contradiction can also be reached if
${R}[{y}]\preceq_{q}{R}[{x}]$. This completes the proof. ∎

Informally, by Lemma 6.3, among all facts of a non-empty block
$R(\underline{c},*)$ in $\mathbf{db}$, there is a (not necessarily unique)
fact $R(\underline{c},\vec{d})$ with a $\subseteq$-minimal frugal set in
$\mathbf{db}$. The repair $\mathbf{r}^{*}$ of $\mathbf{db}$ containing all
such facts is frugal in the sense that each fact in it satisfies as few
$R$-atoms as possible; and if $\mathbf{r}^{*}$ contains a rooted tree set
$\tau$ starting in $c$ accepted by
${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$, so should every repair of
$\mathbf{db}$. We now formalize this idea.

######  Definition 6.2 (Frugal repair).

Let $q$ be a query in $\mathsf{TreeBCQ}$ satisfying
$\mathsf{C}_{\mathsf{branch}}$. Let $\mathbf{db}$ be a database instance. A
_frugal repair_ $\mathbf{r}^{*}$ of $\mathbf{db}$ with respect to $q$ is
constructed by picking, from each block $R(\underline{c},*)$ of $\mathbf{db}$,
a fact $R(\underline{c},\vec{d})$ which $\subseteq$-minimizes
${\mathsf{FrugalSet}}_{q}({R(\underline{c},\vec{d})},{\mathbf{db}})$.

Lemma 6.4 is then straightforward by construction of a frugal repair.

######  Lemma 6.4.

Let $q$ be a rooted tree query satisfying $\mathsf{C}_{\mathsf{branch}}$. Let
$\mathbf{db}$ be a database instance. Let $\mathbf{r}^{*}$ be a frugal repair
of $\mathbf{db}$ with respect to $q$ and let
$R(\underline{c},\vec{d})\in\mathbf{r}^{*}$. Let ${R}[{u}]$ be an atom in $q$.
If $\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{u})$ is true, then
$\langle{c},{u}\rangle\in B$.

###### Proof.

Let $R(\underline{c},\vec{b})$ be an arbitrary fact in the block
$R(\underline{c},*)$ in $\mathbf{db}$. By construction of a frugal repair, we
have that
${\mathsf{FrugalSet}}_{q}({R(\underline{c},\vec{d})},{\mathbf{db}})\subseteq{\mathsf{FrugalSet}}_{q}({R(\underline{c},\vec{b})},{\mathbf{db}})$.
Since $R(\underline{c},\vec{d})\in\mathbf{r}^{*}$ and
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{u})$ is true, we have
${R}[{u}]\in{\mathsf{FrugalSet}}_{q}({R(\underline{c},\vec{d})},{\mathbf{db}})$.
Thus,
${R}[{u}]\in{\mathsf{FrugalSet}}_{q}({R(\underline{c},\vec{b})},{\mathbf{db}})$
and $\mathsf{fact}({R}(\underline{{c}},{\vec{b}}),{u})$ is true. Hence
$\langle{c},{u}\rangle\in B$. ∎

Lemma 6.5 shows a desirable property of frugal repairs.

######  Lemma 6.5.

Let $q$ be a query in $\mathsf{TreeBCQ}$ satisfying
$\mathsf{C}_{\mathsf{branch}}$. Let $\mathbf{db}$ be a database instance. Let
$\mathbf{r}^{*}$ be a frugal repair of $\mathbf{db}$ with respect to $q$. If
there is a rooted tree set $\tau$ in $\mathbf{r}^{*}$ starting in $c$ such
that $\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$, then
$\langle{c},{y}\rangle\in B$.

###### Proof.

Let $\tau$ be a rooted tree set starting in $c$ in $\mathbf{r}^{*}$ such that
$\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$. We recursively define a
tree trace $\mathcal{T}$ on nodes of the form $(c,x)$, where
$c\in{\mathsf{adom}}({\mathbf{r}^{*}})$ and $x$ is a variable in $q$, as
follows:

  * •

the root node of $\mathcal{T}$ is $(c,y,\tau)$; and

  * •

whenever $(a,u,\sigma)$ is a node in $\mathcal{T}$ with a rooted tree set
$\sigma$ starting in $a$ in $\mathbf{r}^{*}$ for an atom
$R(\underline{u},u_{1},u_{2},\dots,u_{n})$ in $q$ and fact
$R(\underline{a},b_{1},b_{2},\dots,b_{n})$ in $\mathbf{r}^{*}$,

    * (i)

if ${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$ invokes a forward production
rule

$\displaystyle S_{u}$
$\displaystyle\rightarrow_{q}R(S_{u_{1}},S_{u_{2}},\dots,S_{u_{n}}),$

then the node $(a,u,\sigma)$ has $n$ outgoing $R$-edges to its children
$(b_{1},{u_{1}},\tau_{1})$, $(b_{2},{u_{2}},\tau_{2})$, $\dots$,
$(b_{n},{u_{n}},\tau_{n})$; or

    * (ii)

if ${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$ invokes a backward
production rule $S_{u}\rightarrow_{q}S_{v}$, then the node $(a,u,\sigma)$ has
a single outgoing $\varepsilon$-edge to its only child $(a,v,\sigma)$.

The tree trace $\mathcal{T}$ succinctly records the rule productions that
witness $\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$ in
$\mathbf{r}^{*}$. We use a structural induction to show that for every node
$(a,u,\sigma)$ in $\mathcal{T}$, $\langle{a},{u}\rangle\in B$.

  * •

Basis. The claim holds for every leaf node $(a,u,\sigma)$ in $\mathcal{T}$,
since if $\sigma=\bot$, then $\langle{a},{u}\rangle\in B$, or otherwise
$\sigma=L$ starting in $a$ in $\mathbf{r}^{*}$ for some unary relation name
$L$, and we have $L(a)$ is in $\mathbf{db}$.

  * •

Inductive step. Let $(a,u,\sigma)$ be a node in $\mathcal{T}$. Assume that for
any child node $(b,w,\sigma^{\prime})$ of $(a,u)$ in $\mathcal{T}$ (possibly
$b=a$), $\langle{b},{w}\rangle\in B.$ It suffices to argue that for the atom
${R}[{u}]=R(\underline{u},u_{1},u_{2},\dots,u_{n})$ in $q$,
$\langle{a},{u}\rangle\in B$.

(i) Case that $(a,u,\sigma)$ has child nodes $(b_{1},{u_{1}},\tau_{1})$,
$(b_{2},{u_{2}},\tau_{2})$, $\dots$, $(b_{n},{u_{n}},\tau_{n})$ in
$\mathcal{T}$ with $\sigma=R(\tau_{1},\tau_{2},\dots,\tau_{n})$. By the
inductive hypothesis $\langle{b_{i}},{u_{i}}\rangle\in B$ for every $1\leq
i\leq n$, which yields that
$\mathsf{fact}({R}(\underline{{a}},{\vec{b}}),{u})$ is true, where
$\vec{b}=\langle b_{1},b_{2},\dots,b_{n}\rangle$. Then by Lemma 6.4,
$\langle{a},{u}\rangle\in B$.

(ii) Case that $(a,u,\sigma)$ has a child node $(a,v,\sigma)$ in $\mathcal{T}$
connected with an $\varepsilon$-edge. Then there is some atom ${R}[{v}]$ with
${R}[{v}]<_{{q}}{R}[{u}]$. By the inductive hypothesis on the child
$(a,v,\sigma)$, $\langle{a},{v}\rangle\in B$. Hence $\langle{a},{u}\rangle\in
B$ by Lemma 6.2.

This completes the proof. ∎

The proof of Lemma 6.1 can now be given.

###### Proof of Lemma 6.1.

2$\implies$1 Let $\mathbf{r}^{*}$ be a frugal repair of $\mathbf{db}$ with
respect to $q$. Then there is a rooted tree set $\tau$ starting in $c$ in
$\mathbf{r}^{*}$ with $\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$.
The claim follows by Lemma 6.5.

1$\implies$2 Assume that $\langle{c},{y}\rangle\in B$. We use induction on $k$
to show that if $\langle{c},{y}\rangle$ is added to $B$ at the $k$-th
iteration, then for any repair $\mathbf{r}$ of $\mathbf{db}$, there exists a
rooted tree set $\tau$ starting in $c$ in $\tau$ with
$\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$.

  * •

Basis $k=0$. Then every $\langle{c},{u}\rangle$ is added to $B$ for every leaf
variable $u$ of $q$ such that either the label of $u$ in $q$ is $\bot$, or a
unary relation name $L$. If the label of $u$ is $\bot$, the empty rooted tree
set $\tau=\emptyset$ starting in $c$ with string representation $\bot$ is
accepted by ${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{u})$, Otherwise, we must
have $L(c)\in\mathbf{db}$, and the rooted tree set $\tau=L$ starting in $c$ is
accepted by ${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{u})$.

  * •

Inductive step. Assume that $\langle{c},{y}\rangle$ is added to $B$ in the
$k$-th iteration, and for any tuple $\langle{b},{x}\rangle$ added to $B$ prior
to the addition of $\langle{c},{y}\rangle$, any repair of $\mathbf{db}$
contains a rooted tree set
$\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{x})$ starting in $b$. Let
$\mathbf{r}$ be any repair of $\mathbf{db}$. It suffices to construct a rooted
tree set $\tau$ in $\mathbf{r}$ starting in $c$ such that
$\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$. Let
${R}[{y}]=R(\underline{y},y_{1},y_{2},\dots,y_{n})$. Let
$R(\underline{c},d_{1},d_{2},\dots,d_{n})\in\mathbf{r}$ and let
$\vec{d}=\langle d_{1},d_{2},\dots,d_{n}\rangle$. Since
$\langle{c},{y}\rangle\in B$,
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ is true. Consider two
cases.

    * –

Case that $\langle{d_{i}},{y_{i}}\rangle\in B$ for every $1\leq i\leq n$.
Since each $\langle{d_{i}},{y_{i}}\rangle$ was added to $B$ in an iteration
$<k$, by the inductive hypothesis, there is a rooted tree set $\tau_{i}$
starting in $d_{i}$ in $\mathbf{r}$ with
$\tau_{i}\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y_{i}})$, i.e.,
$S_{y_{i}}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau_{i}$. Consider the
rooted tree set $\tau=\\{R(\underline{c},\vec{d})\\}\cup\bigcup_{1\leq i\leq
n}\tau_{i}$, starting in $c$ in $\mathbf{r}$ with a string representation
$\tau=R(\tau_{1},\tau_{2},\dots,\tau_{n})$. From

$\displaystyle S_{y}$
$\displaystyle\rightarrow_{q}R(S_{y_{1}},S_{y_{2}},\dots,S_{y_{n}})$
$\displaystyle\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}R(\tau_{1},\tau_{2},\dots,\tau_{n})=\tau,$

we conclude that $\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$.

    * –

Case that $\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{x})$ is true for some
${R}[{x}]<_{{q}}{R}[{y}]$. Without loss of generality, we assume that $x$ is
the smallest with respect to $<_{{q}}$ for the atom
$R(\underline{x},x_{1},x_{2},\dots,x_{n})$. Hence we must have
$\langle{d_{i}},{x_{i}}\rangle\in B$ for every $1\leq i\leq n$, and by the
previous case, there exists a rooted tree set $\tau_{i}$ starting in $d_{i}$
such that $\tau_{i}\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{x_{i}})$, i.e.,
$S_{x_{i}}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau_{i}$. Since
${R}[{x}]<_{{q}}{R}[{y}]$, we have

$\displaystyle S_{y}$ $\displaystyle\rightarrow_{q}S_{x}$
$\displaystyle\rightarrow_{q}R(S_{x_{1}},S_{x_{2}},\dots,S_{x_{n}})$
$\displaystyle\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}R(\tau_{1},\tau_{2},\dots,\tau_{n})=\tau,$

and therefore $\tau\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{y})$.

The proof is hence complete. ∎

###  6.2 Expressibility in $\mathbf{LFP}$ and $\mathbf{FO}$

######  Lemma 6.6.

For every query $q$ in $\mathsf{TreeBCQ}$ that satisfies
$\mathsf{C}_{\mathsf{branch}}$, $\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ is
expressible in $\mathbf{LFP}$ (and thus is in $\mathbf{PTIME}$).

###### Proof.

Let $r$ be the root variable of $q$. Our algorithm first computes the set $B$,
and then checks $\exists c:\langle{c},{r}\rangle\in B.$ The algorithm is
correct by Lemma 6.1.

For a rooted tree query $q$, define the following formula in $\mathbf{LFP}$
[40]:

$\psi_{q}(s,t)\vcentcolon=\left[\mathbf{lfp}_{B,x,z}\varphi_{q}(B,x,z)\right](s,t),$
(5)

where we have

$\varphi_{q}(B,x,z):=\left(\begin{array}[]{ll}&\alpha(x)\land\left({z={R}[{u}]}\right)\\\\[4.30554pt]
\land&\exists yR(\underline{x},\vec{y})\\\\[4.30554pt]
\land&\forall\vec{y}\left({R(\underline{x},\vec{y})\rightarrow\mathsf{fact}({R}(\underline{{x}},{\vec{y}}),{u})}\right)\end{array}\right)$

and the formula $\mathsf{fact}({R}(\underline{{x}},{\vec{y}}),{u})$ is defined
in Fig. 6. The initialization step of $B$ in Fig. 6 is expressible in
$\mathbf{FO}$. Herein, $\alpha(x)$ denotes a first-order query that computes
the active domain. That is, for every database instance $\mathbf{db}$ and
constant $c$, $\mathbf{db}\models\alpha(c)$ if and only if
$c\in{\mathsf{adom}}({\mathbf{db}})$. It is easy to verify that the LFP
formula in (5) computes the set $B$ in Fig. 6. ∎

We now show that if $q$ satisfies $\mathsf{C}_{1}$, we can safely remove the
recursion from the algorithm in Fig. 6.

######  Lemma 6.7.

Let $q$ be a rooted tree query satisfying $\mathsf{C}_{1}$. Let $\mathbf{db}$
be a database. Let ${R}[{y}]=R(\underline{y},y_{1},y_{2},\dots,y_{n})$ be an
atom in $q$ and let
$R(\underline{c},\vec{d})=R(\underline{c},d_{1},d_{2},\dots,d_{n})$ be a fact
in $\mathbf{db}$. Then $\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ is
true if and only if for every atom ${T_{i}}[{y_{i}}]$ in $q$,
$\langle{d_{i}},{y_{i}}\rangle\in B$.

###### Proof.

$\impliedby$ Immediate by definition of
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$.

$\implies$ Assume that $\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ is
true. Let ${R}[{x}]$ be a minimal atom with respect to $<_{{q}}$ such that
${R}[{x}]<_{{q}}{R}[{y}]$ and
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{x})$ is true. If such an atom
${R}[{x}]$ does not exist, then the claim follows by definition of
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$. Otherwise, since
${R}[{x}]$ is minimal with respect to $<_{{q}}$, for every atom
${T_{i}}[{x_{i}}]$ in $q$, $\langle{d_{i}},{x_{i}}\rangle\in B$, where
$R(\underline{x},\vec{x})=R(\underline{x},x_{1},x_{2},\dots,x_{n})$.

It suffices to show that for every atom ${T_{i}}[{y_{i}}]$ in $q$,
$\langle{d_{i}},{y_{i}}\rangle\in B$. Let ${T_{i}}[{y_{i}}]$ be an atom in
$q$. From $\mathsf{C}_{1}$ and ${R}[{x}]<_{{q}}{R}[{y}]$,
${q}^{{y_{i}}}_{{\vartriangle}}\leq_{{y_{i}}\rightarrow{x_{i}}}{q}^{{x_{i}}}_{{\vartriangle}}$.
Thus there is some atom ${T_{i}}[{x_{i}}]$ in $q$ with
${T_{i}}[{x_{i}}]<_{{q}}{T_{i}}[{y_{i}}]$. Since
$\langle{d_{i}},{x_{i}}\rangle\in B$, by Lemma B.1,
$\langle{d_{i}},{y_{i}}\rangle\in B$. ∎

######  Lemma 6.8.

For every $q$ in $\mathsf{TreeBCQ}$ that satisfies $\mathsf{C}_{1}$,
$\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ is in $\mathbf{FO}$ .

###### Proof.

Consider the following variant of the algorithm in Fig. 6, where we simply
have

$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})=\bigwedge_{1\leq i\leq
n}\langle{d_{i}},{y_{i}}\rangle\in B.$

The variant algorithm is correct for $\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ by
Lemma 6.7. Since the size of the query $q$ is fixed, for every constant $c$
and variable $y$ in $q$, deciding whether $\langle{c},{y}\rangle\in B$ is in
$\mathbf{FO}$ since the algorithm in Fig. 6 can be expanded into a sentence of
fixed size. So is our algorithm, which checks $\exists
c:\langle{c},{r}\rangle\in B.$ ∎

##  7 Complexity Upper Bounds

In this section, we prove the upper bound results in Theorem 4.1. First, we
shall prove Lemma 5.1.

######  Lemma 7.1.

Let $q$ be a rooted tree query. Then $q$ satisfies
$\mathsf{C}_{\mathsf{factor}}$ if and only if $q\leq_{{}\rightarrow{}}\tau$
for every $\tau\in{\mathsf{CFG^{\clubsuit}}}({q})$.

###### Proof of Lemma 7.1.

Consider two directions.

$\impliedby$ Let ${R}[{x}]$ and ${R}[{y}]$ be two atoms in $q$ with
${R}[{x}]<_{{q}}{R}[{y}]$. It suffices to show that
${q}^{{R}:{y}\looparrowright{x}}\in{\mathsf{CFG^{\clubsuit}}}({q})$. Indeed,
there is an execution of $S_{r}({q}^{{R}:{y}\looparrowright{x}})$ that follows
exactly $S_{r}(q)$, until it invokes $S_{y}({q}^{{x}}_{{\vartriangle}})$,
instead of $S_{y}({q}^{{y}}_{{\vartriangle}})$ in $S_{r}(q)$. Note that
$S_{y}\rightarrow_{q}S_{x}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}{q}^{{x}}_{{\vartriangle}}$.
Thus
$S_{r}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}{q}^{{R}:{y}\looparrowright{x}}$,
concluding that
${q}^{{R}:{y}\looparrowright{x}}\in{\mathsf{CFG^{\clubsuit}}}({q})$.

$\implies$ Let $\tau\in{\mathsf{CFG^{\clubsuit}}}({q})$ with
$S_{r}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau$. We use an induction
on the number $k$ of backward transitions in
$S_{r}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau$ to show that
$q\leq_{{}\rightarrow{}}\tau$.

  * •

Basis $k=0$. We have $\tau=q$, and the claim follows.

  * •

Inductive step $k\rightarrow k+1$. Assume that if
$S_{r}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\sigma$ uses $k$ backward
transitions, then $q\leq_{{}\rightarrow{}}\sigma$.

Let $\tau\in{\mathsf{CFG^{\clubsuit}}}({q})$ such that
$S_{r}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau$ uses $k+1$ backward
transitions. Let $\sigma$ be a subtree of $\tau$ such that the execution of
$S_{r}(\sigma)$ invokes exactly $1$ backward transition
$S_{y}\rightarrow_{q}S_{x}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\sigma$.
Hence $\sigma={q}^{{x}}_{{\vartriangle}}$. Consider the rooted tree
$\tau^{*}$, obtained by replacing $\sigma={q}^{{x}}_{{\vartriangle}}$ with
$\sigma^{*}={q}^{{y}}_{{\vartriangle}}$. We have
$\tau^{*}\in{\mathsf{CFG^{\clubsuit}}}({q})$, since
$S_{r}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\tau$ would invoke
$S_{y}\stackrel{{\scriptstyle*}}{{\rightarrow}}_{q}\sigma^{*}$ and use exactly
$k$ backward transitions. By the inductive hypothesis, there is a homomorphism
$h$ from $q$ to $\tau^{*}$. If $h(q)\cap\sigma^{*}=\emptyset$, then $h(q)$ is
still present in $\tau$, and thus $q\leq_{{}\rightarrow{}}\tau$. Otherwise,
assume that the homomorphism $h$ maps ${q}^{{z}}_{{\vartriangle}}$ in $q$ to
$\sigma^{*}$. Hence ${R}[{x}]<_{{q}}{R}[{y}]<_{{q}}{R}[{z}]$. Since $q$
satisfies $\mathsf{C}_{\mathsf{factor}}$, there is a homomorphism $g$ from $q$
to ${q}^{{R}:{z}\looparrowright{x}}$, and thus a homomorphism from $q$ to
$\tau$.

The proof is now complete. ∎

The following definition is helpful in our exposition.

######  Definition 7.1.

Let $q$ be a rooted tree query. Let $\mathbf{db}$ be a database. For each
repair $\mathbf{r}$ of $\mathbf{db}$, we define
$\mathsf{start}({q},{\mathbf{r}})$ as the set containing all (and only)
constants $c\in{\mathsf{adom}}({\mathbf{r}})$ such that there is a rooted tree
set $\tau$ in $\mathbf{r}$ starting in $c$ with
$\tau\in{\mathsf{CFG^{\clubsuit}}}({q})$.

The problem $\mathsf{CERTAIN}_{\mathsf{tr}}({q})$ essentially asks whether
there is some constant $c$ such that for every repair $\mathbf{r}$ of
$\mathbf{db}$, $c\in\mathsf{start}({q},{r})$. Surprisingly, the frugal repair
$\mathbf{r}^{*}$ of $\mathbf{db}$ minimizes $\mathsf{start}({q},{\cdot})$
across all repairs of $\mathbf{db}$.

######  Lemma 7.2.

Let $q$ be a rooted tree query satisfying $\mathsf{C}_{\mathsf{branch}}$. Let
$\mathbf{db}$ be a database. Let $\mathbf{r}^{*}$ be a frugal repair of
$\mathbf{db}$. Then for any repair $\mathbf{r}$ of $\mathbf{db}$,
$\mathsf{start}({q},{\mathbf{r}^{*}})\subseteq\mathsf{start}({q},{\mathbf{r}})$.

###### Proof of Lemma 7.2.

Let $B$ be the output of the algorithm in Fig. 6. Let $\mathbf{r}^{*}$ be a
frugal repair of $\mathbf{db}$. Let $\mathbf{r}$ be any repair of
$\mathbf{db}$. We show that
$\mathsf{start}({q},{\mathbf{r}^{*}})\subseteq\mathsf{start}({q},{\mathbf{r}})$.
Let $r$ be the root variable of $q$. Assume that
$c\in\mathsf{start}({q},{\mathbf{r}^{*}})$. Then there exists a rooted tree
set $\tau$ starting in $c$ in $\mathbf{r}^{*}$ with
$\tau\in{\mathsf{CFG^{\clubsuit}}}({q})={\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{r})$.
By Lemma 6.5, we have $\langle{c},{r}\rangle\in B$. By Lemma 6.1, there exists
a rooted tree set $\tau^{\prime}$ starting in $c$ in $\mathbf{r}$ with
$\tau^{\prime}\in{\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{r})={\mathsf{CFG^{\clubsuit}}}({q})$.
Thus $c\in\mathsf{start}({q},{\mathbf{r}})$. ∎

The proof of Lemma 5.1 can now be given.

###### Proof of Lemma 5.1.

1$\implies$2 Assume (1). Let $\mathbf{r}^{*}$ be a frugal repair of
$\mathbf{db}$. Since $\mathbf{r}^{*}$ satisfies $q$, there is a rooted tree
set starting in $c$ isomorphic to $q$ in $\mathbf{r}^{*}$. Since
$q\in{\mathsf{CFG^{\clubsuit}}}({q})$, we have
$c\in\mathsf{start}({q},{\mathbf{r}^{*}})$. By Lemma 7.2, for every repair
$\mathbf{r}$ of $\mathbf{db}$,
$\mathsf{start}({q},{\mathbf{r}^{*}})\subseteq\mathsf{start}({q},{\mathbf{r}})$.
It follows that $c\in\mathsf{start}({q},{\mathbf{r}})$ for every repair
$\mathbf{r}$ of $\mathbf{db}$.

2$\implies$1 Let $\mathbf{r}$ be any repair of $\mathbf{db}$. By our
hypothesis that (2) holds true, there is some
$c\in\mathsf{start}({q},{\mathbf{r}})$. Let $\tau$ be a rooted tree set in
$\mathbf{r}$ starting in $c$ with $\tau\in{\mathsf{CFG^{\clubsuit}}}({q})$.
Since $q$ satisfies $\mathsf{C}_{2}$ by the hypothesis of the current lemma,
it follows by Lemma 7.1 that $q\leq_{{}\rightarrow{}}\tau$. Consequently,
$\mathbf{r}$ satisfies $q$. ∎

The upper bounds in Theorem 4.1 thus follows.

######  Proposition 7.1.

For every $q$ in $\mathsf{TreeBCQ}$,

  1. 1.

if $q$ satisfies $\mathsf{C}_{2}$, then $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{LFP}$; and

  2. 2.

if $q$ satisfies $\mathsf{C}_{1}$, then $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{FO}$.

###### Proof.

Immediate from Lemmas 5.1, 6.6, and 6.8 by noting that $\mathsf{C}_{1}$
implies $\mathsf{C}_{2}$. ∎

Interestingly, for each query $q$ in $\mathsf{TreeBCQ}$ satisfying
$\mathsf{C}_{2}$, “checking the frugal repair is all you need”. A repair with
this property is known as a “universal repair” in [49].

######  Corollary 7.1.

Let $q$ be a query in $\mathsf{TreeBCQ}$, and let $\mathbf{db}$ be a database
instance. Let $\mathbf{r}^{*}$ be a frugal repair of $\mathbf{db}$ with
respect to $q$. If $q$ satisfies $\mathsf{C}_{2}$, then $\mathbf{db}$ is a
“yes”-instance of $\mathsf{CERTAINTY}({q})$ if and only if $\mathbf{r}^{*}$
satisfies $q$.

###### Proof.

Let $\mathbf{r}^{*}$ be a frugal repair of $\mathbf{db}$ with respect to $q$.

$\implies$ This direction is straightforward. $\impliedby$ Assume that
$\mathbf{r}^{*}$ satisfies $q$. Let $r$ be the root variable of $q$. Hence
there exists a constant $c$ in $\mathbf{db}$, such that there exists a rooted
relation tree $\tau$ in $\mathbf{r}^{*}$ that is isomorphic to $q$ accepted by
${\mathsf{S\text{-}CFG^{\clubsuit}}}({q},{r})$. Then by Lemma 6.5,
$\langle{c},{r}\rangle\in B$, where $B$ is the output of algorithm in Fig. 6.
Hence $\mathbf{db}$ is a “yes”-instance for
$\mathsf{CERTAIN}_{\mathsf{tr}}({q})$, and by Lemma 5.1, a “yes”-instance for
$\mathsf{CERTAINTY}({q})$. ∎

##  8 Complexity Lower Bounds

In this section, we show the hardness results in Theorem 4.1.

We define a canonical copy of a query $q$ as a set of facts $\mu(q)$, where
$\mu$ maps each variable in $q$ to a unique constant. The following notation
will be central in all our reductions. For a query $q$, variables $x_{i}$ in
$q$ and distinct constants $c_{i}$, we denote

$\langle{q},{[x_{1},x_{2},\dots,x_{n}\rightarrow
c_{1},c_{2},\dots,c_{n}]}\rangle$

as the canonical copy $\mu(q)$, where

$\mu(z)=\begin{cases}c_{i}&\text{if }z=x_{i}\\\ \text{a fresh distinct
constant}&\text{otherwise}.\end{cases}$

######  Lemma 8.1.

$\mathsf{CERTAINTY}({q})$ is $\mathbf{coNP}$-hard for each $q$ in
$\mathsf{TreeBCQ}$ that violates $\mathsf{C}_{2}$.

###### Proof.

Since $q$ violates $\mathsf{C}_{2}$, there exist two atoms
$R(\underline{p},\dots)$ and $R(\underline{n},\dots)$ in $q$ such that there
is no homomorphism from $q$ to neither ${q}^{{R}:{p}\looparrowright{n}}$ nor
${q}^{{R}:{n}\looparrowright{p}}$.

Consider now the root atom $A(\underline{r},\dots)$. It must be that $r\neq
p$, since otherwise, there would be a homomorphism from $q$ to
${q}^{{R}:{n}\looparrowright{p}}$, a contradiction. Similarly, we have that
$r\neq n$. Hence, the root atom is distinct from $R(\underline{p},\dots)$ and
$R(\underline{n},\dots)$. We also have that $r<_{{q}}p$ and $r<_{{q}}n$.

We present a reduction from $\mathsf{MonotoneSAT}$: Given a monotone CNF
formula $\varphi$, i.e., each clause in $\varphi$ contains either all positive
literals or all negative literals, does $\varphi$ has a satisfying assignment?

Let $\varphi$ be a monotone CNF formula. We construct an instance
$\mathbf{db}$ for $\mathsf{CERTAINTY}({q})$ as follows.

  * •

for each variable $z$ in $\varphi$, we introduce the facts
$\langle{{q}^{{p}}_{{\vartriangle}}},{[p\rightarrow z]}\rangle$ and
$\langle{{q}^{{n}}_{{\vartriangle}}},{[n\rightarrow z]}\rangle$;

  * •

for each positive literal $z$ in clause $C$, we introduce the facts
$\langle{q\setminus{{q}^{{p}}_{{\vartriangle}}}},{[r,p\rightarrow
C,z]}\rangle$;

  * •

for each negative literal $z$ in clause $\overline{C}$, we introduce the facts
$\langle{q\setminus{{q}^{{n}}_{{\vartriangle}}}},{[r,n\rightarrow\overline{C},z]}\rangle$;

Observe that the instance $\mathbf{db}$ has two types of inconsistent blocks.
For relation $A$, we have a block for each positive or negative clause, where
the primary key position is the clause. For relation $R$, for every variable
$z$ we have a block of size two, which corresponds to choosing a true/false
assignment for $z$. All the other relations are consistent.

Additionally, for a positive literal $z\in C$, the set of facts
$\langle{{q}^{{p}}_{{\vartriangle}}},{[p\rightarrow
z]}\rangle\cup\langle{q\setminus{{q}^{{p}}_{{\vartriangle}}}},{[r,p\rightarrow
C,z]}\rangle$ make $q$ true; similarly for a negative literal
$z\in\overline{C}$, the facts
$\langle{{q}^{{n}}_{{\vartriangle}}},{[n\rightarrow
z]}\rangle\cup\langle{q\setminus{{q}^{{n}}_{{\vartriangle}}}},{[n,p\rightarrow\overline{C},z]}\rangle$
make $q$ true. Note also that
$\langle{{q}^{{n}}_{{\vartriangle}}},{[n\rightarrow
z]}\rangle\cup\langle{q\setminus{{q}^{{p}}_{{\vartriangle}}}},{[r,p\rightarrow
C,z]}\rangle$ is a canonical copy of ${q}^{{R}:{p}\looparrowright{n}}$ (and
hence cannot satisfy $q$), while
$\langle{{q}^{{p}}_{{\vartriangle}}},{[p\rightarrow
z]}\rangle\cup\langle{q\setminus{{q}^{{n}}_{{\vartriangle}}}},{[r,n\rightarrow\overline{C},z]}\rangle$
is a canonical copy of ${q}^{{R}:{n}\looparrowright{p}}$ (which also cannot
satisfy $q$).

Now we argue that $\varphi$ has a satisfying assignment $\chi$ if and only if
$\mathbf{db}$ has a repair $\mathbf{r}$ that does not satisfy $q$.

$\implies$ Assume that $\varphi$ has a satisfying assignment $\chi$. Consider
the repair $\mathbf{r}$ of $\mathbf{db}$ that

  * •

for each variable $z$, if $\chi(z)=\mathsf{true}$, picks
$\langle{{q}^{{n}}_{{\vartriangle}}},{[n\rightarrow z]}\rangle$, or otherwise
$\langle{{q}^{{p}}_{{\vartriangle}}},{[p\rightarrow z]}\rangle$;

  * •

for each positive clause $C$, picks
$\langle{q\setminus{{q}^{{p}}_{{\vartriangle}}}},{[r,p\rightarrow
C,z]}\rangle$ where $z$ is a positive literal in $C$ with
$\chi(z)=\mathsf{true}$; and

  * •

for each negative clause $\overline{C}$, picks
$\langle{q\setminus{{q}^{{n}}_{{\vartriangle}}}},{[r,n\rightarrow\overline{C},\overline{z}]}\rangle$
where $\overline{z}$ is a negative literal in $\overline{C}$ with
$\chi(z)=\mathsf{false}$.

We show that $\mathbf{r}$ does not satisfy $q$. Indeed, for each positive
clause $C$, there is a literal $z\in C$ with $\chi(z)=\mathsf{true}$, and thus
$\langle{q\setminus{{q}^{{p}}_{{\vartriangle}}}},{[r,p\rightarrow
C,z]}\rangle\subseteq\mathbf{r}$. However, we have
$\langle{{q}^{{n}}_{{\vartriangle}}},{[n\rightarrow
z]}\rangle\subseteq\mathbf{r}$, and thus $q$ is not satisfied. Similarly, for
each negative clause $\overline{C}$, there is a literal
$\overline{z}\in\overline{C}$ with $\chi(z)=\mathsf{false}$, and thus
$\langle{q\setminus{{q}^{{n}}_{{\vartriangle}}}},{[n,p\rightarrow\overline{C},z]}\rangle\subseteq\mathbf{r}$.
However, we have $\langle{{q}^{{p}}_{{\vartriangle}}},{[p\rightarrow
z]}\rangle\subseteq\mathbf{r}$ and hence this part also cannot satisfy $q$.
Hence $\mathbf{r}$ does not satisfy $q$.

$\impliedby$ Now assume that $\mathbf{db}$ has a repair $\mathbf{r}$ that does
not satisfy $q$. Consider the assignment $\chi$ that sets
$\chi(z)=\mathsf{true}$ if $\langle{{q}^{{n}}_{{\vartriangle}}},{[n\rightarrow
z]}\rangle\subseteq\mathbf{r}$, or otherwise $\chi(z)=\mathsf{false}$. We
argue that $\varphi$ is satisfied. For each positive clause $C$, there exists
some $z\in C$ such that
$\langle{q\setminus{{q}^{{p}}_{{\vartriangle}}}},{[r,p\rightarrow
C,z]}\rangle\subseteq\mathbf{r}$. Since $\mathbf{r}$ does not satisfy $q$, it
must be that $\langle{{q}^{{p}}_{{\vartriangle}}},{[p\rightarrow
z]}\rangle\nsubseteq\mathbf{r}$ and thus
$\langle{{q}^{{n}}_{{\vartriangle}}},{[n\rightarrow
z]}\rangle\subseteq\mathbf{r}$. By construction, $z$ is true and the clause
$C$ is satisfied. Similarly, the negative clauses are all satisfied by the
assignment. ∎

######  Lemma 8.2.

Let $q$ be a rooted tree query. If there exist two distinct atoms
$R(\underline{x},\dots)$ and $R(\underline{y},\dots)$ such that $x<_{{q}}y$
and there is no root homomorphism from ${q}^{{y}}_{{\vartriangle}}$ to
${q}^{{x}}_{{\vartriangle}}$ (i.e., it does not hold that
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$),
then $\mathsf{CERTAINTY}({q})$ is $\mathbf{NL}$-hard.

###### Proof.

We may assume without loss of generality two things $(i)$ there is no atom
$R(\underline{z},\dots)$ such that $z\notin\\{x,y\\}$, $x<_{{q}}z<_{{q}}y$ (we
then say that the two $R$-atoms are consecutive), and $(ii)$ for any
$y<_{{q}}z$, $z\neq y$, we have
${q}^{{z}}_{{\vartriangle}}\leq_{{z}\rightarrow{y}}{q}^{{y}}_{{\vartriangle}}$.
Indeed, we can pick $R(\underline{x},\dots)$ and $R(\underline{y},\dots)$ to
be the pair of consecutive $R$-atoms that violates the root homomorphism
condition and occurs lowest in the rooted tree. Such a pair must always
exists, since the root homomorphism property is transitive, i.e., if
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{z}}{q}^{{z}}_{{\vartriangle}}$
and
${q}^{{z}}_{{\vartriangle}}\leq_{{z}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
then we also have that
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$.

We present a reduction from the complement of REACHABILITY problem, which is
$\mathbf{NL}$-hard: Given a directed acyclic graph $G=(V,E)$ and $s,t\in V$,
is there a directed path from $s$ to $t$ in $G$?

We construct an instance $\mathbf{db}$ for $\mathsf{CERTAINTY}({q})$ as
follows. First, we introduce two new constants $s^{\prime}$ and $t^{\prime}$.
Then:

  * •

for each $u\in V\cup\\{s^{\prime}\\}$, introduce
$\langle{q\setminus{q}^{{x}}_{{\vartriangle}}},{[x\rightarrow u]}\rangle$;

  * •

for every edge $(u,v)\in E\cup\\{(s^{\prime},s),(t,t^{\prime})\\}$, introduce
$\langle{{q}^{{x}}_{{\vartriangle}}\setminus{q}^{{y}}_{{\vartriangle}}},{[x,y\rightarrow
u,v]}\rangle$;

  * •

for every vertex $u\in V$, introduce
$\langle{{q}^{{y}}_{{\vartriangle}}},{[y\rightarrow u]}\rangle$.

Note that the above construction guarantees that only $R$ has inconsistent
blocks.

We now argue that there is a directed path $(u_{1},u_{2},\dots,u_{k})$ with
$(u_{i},u_{i+1})\in E$, $u_{1}=s$ and $u_{k}=t$ in $G$ if and only if there is
a repair of $\mathbf{db}$ that does not satisfy $q$.

$\implies$ Assume that there exists a directed path
$(u_{1},u_{2},\dots,u_{k})$ with $(u_{i},u_{i+1})\in E$, $u_{1}=s$ and
$u_{k}=t$ in $G$. Denote $u_{0}=s^{\prime}$ and $u_{k+1}=t^{\prime}$. Let
$\mathbf{r}$ be the repair that picks
$\langle{{q}^{{x}}_{{\vartriangle}}\setminus{q}^{{y}}_{{\vartriangle}}},{[x,y\rightarrow
u_{i},u_{i+1}]}\rangle$ for every $1\leq i\leq k-1$, and
$\langle{{q}^{{y}}_{{\vartriangle}}},{[y\rightarrow u]}\rangle$ for any other
vertex $u$. Suppose for contradiction that $\mathbf{r}$ satisfies $q$ with a
valuation $\theta$. It is not possible that
$\theta(q)\subseteq\langle{{q}^{{y}}_{{\vartriangle}}},{[y\rightarrow
u]}\rangle$ for any $u\notin V$ since the size does not fit.

We argue that we must have $\theta(x)=u_{i}$ and $\theta(y)=u_{i+1}$ for some
$0\leq i<k$. If $\theta(x)=u_{i}\in\\{u_{0},u_{1},\dots,u_{k}\\}$, then we
must have $\theta(y)=u_{i+1}$ since
$\langle{{q}^{{x}}_{{\vartriangle}}\setminus{q}^{{y}}_{{\vartriangle}}},{[x,y\rightarrow
u,v]}\rangle$ is a canonical copy. Suppose for contradiction that
$\theta(x)\notin\\{u_{0},u_{1},\dots,u_{k}\\}$. It is not possible that
$\theta(x)=u_{k+1}=t^{\prime}$ since by construction, there is no rooted tree
set rooted at $t^{\prime}$. Note that there is no atom
$R(\underline{z},\dots)$ such that $z\notin{x,y}$, $x<_{{q}}z<_{{q}}y$. Hence
$\theta(x)$ cannot fall on the path connecting any $u_{i}$ and $u_{i+1}$, and
$\theta({q}^{{x}}_{{\vartriangle}})$ must be contained in some
$\langle{{q}^{{x}}_{{\vartriangle}}\setminus{q}^{{y}}_{{\vartriangle}}},{[x,y\rightarrow
u_{i},u_{i+1}]}\rangle$. Then, there must be an atom $R(\underline{z},\dots)$
such that (i) $x<_{{q}}z$, (ii) $z\parallel_{{q}}y$ and (iii)
$\theta({q}^{{x}}_{{\vartriangle}})$ is contained in
$\langle{{q}^{{z}}_{{\vartriangle}}},{[z\rightarrow\theta(x)]}\rangle$, which
is impossible since the sizes do not fit.

By construction, there is a canonical copy of ${q}^{{y}}_{{\vartriangle}}$
rooted at $u_{i+1}$. If this canonical copy is contained in
$\langle{{q}^{{x}}_{{\vartriangle}}\setminus{q}^{{y}}_{{\vartriangle}}},{[x,y\rightarrow
u_{i+1},u_{i+2}]}\rangle$, then there is a root homomorphism from
${q}^{{y}}_{{\vartriangle}}$ to
${q}^{{x}}_{{\vartriangle}}\setminus{q}^{{y}}_{{\vartriangle}}$, and so from
${q}^{{y}}_{{\vartriangle}}$ to ${q}^{{x}}_{{\vartriangle}}$, a contradiction.
Otherwise, there exists some atom $R(\underline{z},\dots)$ such that $(i)$
$y<_{{q}}z$ and $(ii)$
${q}^{{y}}_{{\vartriangle}}\setminus{q}^{{z}}_{{\vartriangle}}$ has a root
homomorphism to
${q}^{{x}}_{{\vartriangle}}\setminus{q}^{{y}}_{{\vartriangle}}$. Recall now
that from our initial assumption we must have that
${q}^{{z}}_{{\vartriangle}}\leq_{{z}\rightarrow{y}}{q}^{{y}}_{{\vartriangle}}$.
This implies that we can now generate a root homomorphism from
${q}^{{y}}_{{\vartriangle}}$ to ${q}^{{x}}_{{\vartriangle}}$, a contradiction.

$\impliedby$ Assume that there is no directed path from $s$ to $t$ in $G$.
Consider any repair $\mathbf{r}$ of $\mathbf{db}$. Since $G$ is acyclic, there
exists a maximal sequence $u_{0},u_{1},\dots,u_{k}$ with $k\geq 1$ such that
$u_{0}=s^{\prime}$, $u_{1}=s$,
$\langle{{q}^{{x}}_{{\vartriangle}}\setminus{q}^{{y}}_{{\vartriangle}}},{[x,y\rightarrow
u_{i},u_{i+1}]}\rangle\subseteq\mathbf{r}$ for $0\leq i<k$ and
$\langle{{q}^{{y}}_{{\vartriangle}}},{[y\rightarrow
u_{k}]}\rangle\subseteq\mathbf{r}$. Then, the following set of facts satisfies
$q$:

$\displaystyle\langle{q\setminus{q}^{{x}}_{{\vartriangle}}},{[x\rightarrow
u_{k-1}]}\rangle\cup$
$\displaystyle\langle{{q}^{{x}}_{{\vartriangle}}\setminus{q}^{{y}}_{{\vartriangle}}},{[x,y\rightarrow
u_{k-1},u_{k}]}\rangle\cup$
$\displaystyle\langle{{q}^{{y}}_{{\vartriangle}}},{[y\rightarrow
u_{k}]}\rangle.$

This shows that $\mathsf{CERTAINTY}({q})$ is $\mathbf{NL}$-hard since
$\mathbf{NL}$ is closed under complement. ∎

######  Lemma 8.3.

$\mathsf{CERTAINTY}({q})$ is $\mathbf{NL}$-hard for each $q$ in
$\mathsf{TreeBCQ}$ that violates $\mathsf{C}_{1}$.

###### Proof.

Assume that $q$ violates $\mathsf{C}_{1}$. Then there exist two distinct atoms
$R(\underline{x},\dots)$ and $R(\underline{y},\dots)$ in $q$ such that there
is no root homomorphism from ${q}^{{y}}_{{\vartriangle}}$ to
${q}^{{x}}_{{\vartriangle}}$ or from ${q}^{{x}}_{{\vartriangle}}$ to
${q}^{{y}}_{{\vartriangle}}$. If $x\parallel_{{q}}y$, Lemma 4.1 implies that
$\mathsf{C}_{2}$ is also violated, so $\mathsf{CERTAINTY}({q})$ is
$\mathbf{coNP}$-hard from Lemma 8.1. Otherwise, $\mathsf{CERTAINTY}({q})$ is
$\mathbf{NL}$-hard by Lemma 8.2. ∎

We conclude with the desired lower bounds.

######  Proposition 8.1.

For every $q$ in $\mathsf{TreeBCQ}$,

  1. 1.

if $q$ violates $\mathsf{C}_{2}$, then $\mathsf{CERTAINTY}({q})$ is
$\mathbf{coNP}$-hard; and

  2. 2.

if $q$ violates $\mathsf{C}_{1}$, then $\mathsf{CERTAINTY}({q})$ is
$\mathbf{NL}$-hard.

###### Proof.

Immediate from Lemma 8.1 and 8.3. ∎

##  9 Extending the Trichotomy

In this section, we extend the complexity classification for rooted tree
queries to larger classes of Boolean conjunctive queries. We postpone most
proofs to Appendix C.

###  9.1 From $\mathsf{TreeBCQ}$ to $\mathsf{GraphBCQ}$

We define $\mathsf{GraphBCQ}$, a subclass of $\mathsf{BCQ}$ that extends
$\mathsf{TreeBCQ}$.

######  Definition 9.1 ($\mathsf{GraphBCQ}$).

$\mathsf{GraphBCQ}$ is the class of Boolean conjunctive queries $q$ satisfying
the following conditions:

  1. 1.

every atom in $q$ is of the form $R(\underline{x},y_{1},\ldots,y_{n})$ where
$x$ is a variable and $y_{1},\ldots,y_{n}$ are symbols (variables or
constants) such that no variable occurs twice in the atom; and

  2. 2.

if $R(\underline{x},y_{1},\ldots,y_{n})$ and
$S(\underline{u},v_{1},\ldots,v_{m})$ are distinct atoms of $q$, then $x\neq
u$. Note that $R$ and $S$ need not be distinct.

For a query $q$ in $\mathsf{BCQ}$, we define ${\mathcal{G}}({q})$ as the
undirected graph whose vertices are the atoms of $q$; two atoms are adjacent
if they have a variable in common. The connected components of $q$ are the
connected components of ${\mathcal{G}}({q})$. Note that queries in
$\mathsf{GraphBCQ}$, unlike $\mathsf{TreeBCQ}$, can have more than one
connected component. The following lemma implies that the complexity of
$\mathsf{CERTAINTY}({q})$ is equal to the highest complexity of
$\mathsf{CERTAINTY}({q^{\prime}})$ over every connected component $q^{\prime}$
of $q$.

######  Lemma 9.1.

Let $q$ be a minimal query in $\mathsf{BCQ}$ with connected components
$q_{1}$, $q_{2}$, $\dots$, $q_{n}$. Then:

  1. 1.

for every $1\leq i\leq n$, there exists a first order reduction from the
problem $\mathsf{CERTAINTY}({q_{i}})$ to $\mathsf{CERTAINTY}({q})$; and

  2. 2.

for every database instance $\mathbf{db}$, $\mathbf{db}$ is a “yes”-instance
of the problem $\mathsf{CERTAINTY}({q})$ if and only if for every $1\leq i\leq
n$, $\mathbf{db}$ is a “yes”-instance of $\mathsf{CERTAINTY}({q_{i}})$.

######  Proposition 9.1.

If $q$ is a connected minimal conjunctive query in
$\mathsf{GraphBCQ}\setminus\mathsf{TreeBCQ}$, then $\mathsf{CERTAINTY}({q})$
is $\mathbf{L}$-hard (and not in $\mathbf{FO}$); if $q$ is also Berge-acyclic,
then $\mathsf{CERTAINTY}({q})$ is $\mathbf{coNP}$-hard.

###### Proof of Theorems 1.3 and 1.4.

Let $q$ be a query in $\mathsf{GraphBCQ}$. Then the minimal query $q^{*}$ of
$q$ is also in $\mathsf{GraphBCQ}$. If every connected component of $q^{*}$ is
in $\mathsf{TreeBCQ}$ and satisfies $\mathsf{C}_{1}$, then
$\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$. Otherwise, there exists some
connected component $q^{\prime}$ of $q^{*}$ that is either not in
$\mathsf{TreeBCQ}$, or violates $\mathsf{C}_{1}$, and
$\mathsf{CERTAINTY}({q})$ is $\mathbf{L}$-hard or $\mathbf{NL}$-hard by Lemma
9.1, Proposition 9.1, and Theorem 4.1. Assume that $q$ is also Berge-acyclic.
If some connected component $q^{\prime}$ of $q^{*}$ is not in
$\mathsf{TreeBCQ}$, then $\mathsf{CERTAINTY}({q})$ is
$\mathbf{coNP}$-complete; or otherwise, $\mathsf{CERTAINTY}({q})$ exhibits a
trichotomy by Theorem 4.1. ∎

Lemma 9.2 (adapted from [52]) is essential to the proof of Proposition 9.1,
but is of independent interest. It relates the complexity of CQA on queries
with self-joins to that on self-join-free queries.

Given a query $q$ in $\mathsf{BCQ}$, a _self-join-free version of $q$_,
denoted ${q}^{\mathsf{sjf}}$, is any self-join-free Boolean conjunctive query
obtained from $q$ by (only) renaming relation names. For example, a self-join-
free version of $\\{R(\underline{x},y),R(\underline{y},x)\\}$ is
$\\{R(\underline{x},y),S(\underline{y},x)\\}$.

######  Lemma 9.2 (Bridging Lemma).

Let $q$ be a minimal query in $\mathsf{BCQ}$ and $\mathcal{C}$ a complexity
class. If $\mathsf{CERTAINTY}({{q}^{\mathsf{sjf}}})$ is $\mathcal{C}$-hard,
then $\mathsf{CERTAINTY}({q})$ is $\mathcal{C}$-hard.

The Bridging Lemma is illustrated by Example 9.1.

######  Example 9.1.

For $q_{1}=\\{R(\underline{x},y,z),R(\underline{z},x,y)\\}$, we have
${q_{1}}^{\mathsf{sjf}}=\\{R_{1}(\underline{x},y,z),R_{2}(\underline{z},x,y)\\}$.
By Theorem 1.1 [34], $\mathsf{CERTAINTY}({{q_{1}}^{\mathsf{sjf}}})$ is
$\mathbf{L}$-complete, and thus $\mathsf{CERTAINTY}({q_{1}})$ is
$\mathbf{L}$-hard by Lemma 9.2.

For $q_{2}=\\{R(\underline{x},z),R(\underline{y},z)\\}$, we have
${q_{2}}^{\mathsf{sjf}}=\\{R_{1}(\underline{x},z),R_{2}(\underline{y},z)\\}$.
Although by Theorem 1.1 [34], $\mathsf{CERTAINTY}({{q_{2}}^{\mathsf{sjf}}})$
is $\mathbf{coNP}$-complete, $\mathsf{CERTAINTY}({q_{2}})$ is in $\mathbf{FO}$
because $q_{2}\equiv q_{2}^{\prime}$ where
$q_{2}^{\prime}=\\{R(\underline{x},z)\\}$. Lemma 9.2 does not apply here
because $q_{2}$ is not minimal.

###  9.2 Open Challenges

So far, we have established the $\mathbf{FO}$-boundary of
$\mathsf{CERTAINTY}({q})$ for all queries $q$ in $\mathsf{GraphBCQ}$, and a
fine-grained complexity classification for all Berge-acyclic queries in
$\mathsf{GraphBCQ}$, which include all rooted tree queries. We briefly discuss
the remaining syntactic restrictions.

The complexity classification of $\mathsf{CERTAINTY}({q})$ for queries $q$ in
$\mathsf{GraphBCQ}$ that are not Berge-acyclic is likely to impose new
challenges. In particular, Figueira et al. [18] showed that for $q_{1}$ in
Example 9.1 (that is not Berge-acyclic), the complement of
$\mathsf{CERTAINTY}({q_{1}})$ is complete for Bipartite Matching under
LOGSPACE-reductions.

The restriction imposed by $\mathsf{GraphBCQ}$ that every variable occurs at
most once at a primary-key position allows for an elegant graph
representation. We found that dropping this requirement imposes serious
challenges. The following Proposition 9.2 hints at the difficulty of having to
“correlate two rooted tree branches” that share the same primary-key variable.

######  Proposition 9.2.

Consider the following queries:

  * •

$q_{1}=\\{R(\underline{u},x_{1}),R(\underline{x_{1}},x_{2}),S(\underline{u},y_{1}),S(\underline{y_{1}},y_{2})\\};$

  * •

$q_{2}=q_{1}\cup\\{X(\underline{x_{2}},x_{3})\\};$ and

  * •

$q_{3}=q_{1}\cup\\{X(\underline{x_{2}},x_{3}),Y(\underline{y_{2}},y_{3})\\}.$

Then we have $\mathsf{CERTAINTY}({q_{1}})$ is in $\mathbf{FO}$,
$\mathsf{CERTAINTY}({q_{2}})$ is in $\mathbf{NL}$-hard $\cap$ $\mathbf{LFP}$,
and $\mathsf{CERTAINTY}({q_{3}})$ is $\mathbf{coNP}$-complete.

The restrictions that no atom contains repeated variables, and that no
constant occurs at a primary-key position ease the technical treatment, but it
is likely that they can be dropped at the price of some technical involvement.
On the other hand, all our techniques fundamentally rely on the restriction
that primary keys are simple.

##  10 Conclusion

We established a fine-grained complexity classification of the problem
$\mathsf{CERTAINTY}({q})$ for all rooted tree queries $q$. We then lifted our
complexity classification to a larger class of queries. A notorious open
problem in consistent query answering is Conjecture 1.1, which conjectures
that for every query $q$ in $\mathsf{BCQ}$, $\mathsf{CERTAINTY}({q})$ is
either in $\mathbf{PTIME}$ or $\mathbf{coNP}$-complete. Despite our progress,
this problem remains open even under the restriction that all primary keys are
simple.

Acknowledgements. The authors thank the anonymous reviewers for their
constructive feedback and comments. This work is supported by the National
Science Foundation under grant IIS-1910014 and the Anthony Klug NCR
Fellowship.

## References

  * [1] M. Arenas, P. Barceló, and M. Monet.  The complexity of counting problems over incomplete databases.  ACM Trans. Comput. Log., 22(4):21:1–21:52, 2021.
  * [2] M. Arenas, L. E. Bertossi, and J. Chomicki.  Consistent query answers in inconsistent databases.  In PODS, pages 68–79. ACM Press, 1999.
  * [3] P. Barceló and G. Fontaine.  On the data complexity of consistent query answering over graph databases.  In ICDT, volume 31 of LIPIcs, pages 380–397. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.
  * [4] P. Barceló and G. Fontaine.  On the data complexity of consistent query answering over graph databases.  J. Comput. Syst. Sci., 88:164–194, 2017.
  * [5] C. Berkholz, J. Keppeler, and N. Schweikardt.  Answering conjunctive queries under updates.  In PODS, pages 303–318. ACM, 2017.
  * [6] L. E. Bertossi.  Database repairs and consistent query answering: Origins and further developments.  In PODS, pages 48–58. ACM, 2019.
  * [7] A. A. Bulatov.  Complexity of conservative constraint satisfaction problems.  ACM Trans. Comput. Log., 12(4):24:1–24:66, 2011.
  * [8] M. Calautti, M. Console, and A. Pieris.  Counting database repairs under primary keys revisited.  In PODS, pages 104–118. ACM, 2019.
  * [9] M. Calautti, M. Console, and A. Pieris.  Benchmarking approximate consistent query answering.  In PODS, pages 233–246. ACM, 2021.
  * [10] M. Calautti, L. Libkin, and A. Pieris.  An operational approach to consistent query answering.  In PODS, pages 239–251. ACM, 2018.
  * [11] M. Calautti, E. Livshits, A. Pieris, and M. Schneider.  Counting database repairs entailing a query: The case of functional dependencies.  In PODS, pages 403–412. ACM, 2022.
  * [12] M. Calautti, E. Livshits, A. Pieris, and M. Schneider.  Uniform operational consistent query answering.  In PODS, pages 393–402. ACM, 2022.
  * [13] J. Chomicki and J. Marcinkowski.  Minimal-change integrity maintenance using tuple deletions.  Inf. Comput., 197(1-2):90–121, 2005.
  * [14] J. Chomicki, J. Marcinkowski, and S. Staworko.  Hippo: A system for computing consistent answers to a class of SQL queries.  In EDBT, volume 2992 of Lecture Notes in Computer Science, pages 841–844. Springer, 2004.
  * [15] A. A. Dixit and P. 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] A. A. Dixit and P. G. Kolaitis.  Cavsat: Answering aggregation queries over inconsistent databases via SAT solving.  In SIGMOD Conference, pages 2701–2705. ACM, 2021.
  * [17] Z. Fan, P. Koutris, X. Ouyang, and J. Wijsen.  Lincqa: Faster consistent query answering with linear time guarantees.  Proc. ACM Manag. Data, 1(1):38:1–38:25, 2023.
  * [18] D. Figueira, A. Padmanabha, L. Segoufin, and C. Sirangelo.  A simple algorithm for consistent query answering under primary keys.  In ICDT, volume 255 of LIPIcs, pages 24:1–24:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [19] G. Fontaine.  Why is it hard to obtain a dichotomy for consistent query answering?  ACM Trans. Comput. Log., 16(1):7:1–7:24, 2015.
  * [20] C. Freire, W. Gatterbauer, N. Immerman, and A. Meliou.  The complexity of resilience and responsibility for self-join-free conjunctive queries.  Proc. VLDB Endow., 9(3):180–191, 2015.
  * [21] C. Freire, W. Gatterbauer, N. Immerman, and A. Meliou.  New results for the complexity of resilience for binary conjunctive queries with self-joins.  In PODS, pages 271–284. ACM, 2020.
  * [22] A. Fuxman and R. J. Miller.  First-order query rewriting for inconsistent databases.  J. Comput. Syst. Sci., 73(4):610–635, 2007.
  * [23] G. Greco, S. Greco, and E. Zumpano.  A logical framework for querying and repairing inconsistent databases.  IEEE Trans. Knowl. Data Eng., 15(6):1389–1408, 2003.
  * [24] M. Hannula and J. Wijsen.  A dichotomy in consistent query answering for primary keys and unary foreign keys.  In PODS, pages 437–449. ACM, 2022.
  * [25] L. A. Kahale, A. M. Khamis, B. Diab, Y. Chang, L. C. Lopes, A. Agarwal, L. Li, R. A. Mustafa, S. Koujanian, R. Waziry, et al.  Meta-analyses proved inconsistent in how missing data were handled across their included primary trials: A methodological survey.  Clinical Epidemiology, 12:527–535, 2020.
  * [26] Y. Katsis, A. Deutsch, Y. Papakonstantinou, and V. Vassalos.  Inconsistency resolution in online databases.  In ICDE, pages 1205–1208. IEEE Computer Society, 2010.
  * [27] A. A. E. Khalfioui, J. Joertz, D. Labeeuw, G. Staquet, and J. Wijsen.  Optimization of answer set programs for consistent query answering by means of first-order rewriting.  In CIKM, pages 25–34. ACM, 2020.
  * [28] A. A. E. Khalfioui and J. Wijsen.  Consistent query answering for primary keys and conjunctive queries with counting.  In ICDT, volume 255 of LIPIcs, pages 23:1–23:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [29] B. Kimelfeld, E. Livshits, and L. Peterfreund.  Counting and enumerating preferred database repairs.  Theor. Comput. Sci., 837:115–157, 2020.
  * [30] P. G. Kolaitis and E. Pema.  A dichotomy in the complexity of consistent query answering for queries with two atoms.  Inf. Process. Lett., 112(3):77–85, 2012.
  * [31] P. G. Kolaitis, E. Pema, and W. Tan.  Efficient querying of inconsistent databases with binary integer programming.  Proc. VLDB Endow., 6(6):397–408, 2013.
  * [32] P. Koutris, X. Ouyang, and J. Wijsen.  Consistent query answering for primary keys on path queries.  In PODS, pages 215–232. ACM, 2021.
  * [33] P. Koutris and D. Suciu.  A dichotomy on the complexity of consistent query answering for atoms with simple keys.  In ICDT, pages 165–176. OpenProceedings.org, 2014.
  * [34] P. Koutris and J. Wijsen.  The data complexity of consistent query answering for self-join-free conjunctive queries under primary key constraints.  In PODS, pages 17–29. ACM, 2015.
  * [35] P. Koutris and J. 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.
  * [36] P. Koutris and J. Wijsen.  Consistent query answering for primary keys and conjunctive queries with negated atoms.  In PODS, pages 209–224. ACM, 2018.
  * [37] P. Koutris and J. Wijsen.  Consistent query answering for primary keys in logspace.  In ICDT, volume 127 of LIPIcs, pages 23:1–23:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [38] P. Koutris and J. Wijsen.  First-order rewritability in consistent query answering with respect to multiple keys.  In PODS, pages 113–129. ACM, 2020.
  * [39] P. Koutris and J. Wijsen.  Consistent query answering for primary keys in datalog.  Theory Comput. Syst., 65(1):122–178, 2021.
  * [40] L. Libkin.  Elements of Finite Model Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004\.
  * [41] A. Lopatenko and L. E. Bertossi.  Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics.  In ICDT, volume 4353 of Lecture Notes in Computer Science, pages 179–193. Springer, 2007.
  * [42] C. Lutz and F. Wolter.  On the relationship between consistent query answering and constraint satisfaction problems.  In ICDT, volume 31 of LIPIcs, pages 363–379. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.
  * [43] M. Manna, F. Ricca, and G. Terracina.  Taming primary key violations to query large inconsistent data via ASP.  Theory Pract. Log. Program., 15(4-5):696–710, 2015.
  * [44] M. C. Marileo and L. E. Bertossi.  The consistency extractor system: Answer set programs for consistent query answering in databases.  Data Knowl. Eng., 69(6):545–572, 2010.
  * [45] D. Maslowski and J. Wijsen.  A dichotomy in the complexity of counting database repairs.  J. Comput. Syst. Sci., 79(6):958–983, 2013.
  * [46] D. Maslowski and J. Wijsen.  Counting database repairs that satisfy conjunctive queries with self-joins.  In ICDT, pages 155–164. OpenProceedings.org, 2014.
  * [47] M. A. Rodríguez, L. E. Bertossi, and M. C. Marileo.  Consistent query answering under spatial semantic constraints.  Inf. Syst., 38(2):244–263, 2013.
  * [48] S. Staworko, J. Chomicki, and J. Marcinkowski.  Prioritized repairing and consistent query answering in relational databases.  Ann. Math. Artif. Intell., 64(2-3):209–246, 2012.
  * [49] B. ten Cate, G. Fontaine, and P. G. Kolaitis.  On the data complexity of consistent query answering.  In A. Deutsch, editor, 15th International Conference on Database Theory, ICDT ’12, Berlin, Germany, March 26-29, 2012, pages 22–33. ACM, 2012\.
  * [50] J. Wijsen.  Database repairing using updates.  ACM Trans. Database Syst., 30(3):722–768, 2005.
  * [51] J. Wijsen.  On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases.  In PODS, pages 179–190. ACM, 2010.
  * [52] J. Wijsen.  Corrigendum to ”counting database repairs that satisfy conjunctive queries with self-joins”.  CoRR, abs/1903.12469, 2019.
  * [53] J. Wijsen.  Foundations of query answering on inconsistent databases.  SIGMOD Rec., 48(3):6–16, 2019.
  * [54] D. Zhuk.  A proof of the CSP dichotomy conjecture.  J. ACM, 67(5):30:1–30:78, 2020.

##  Appendix A Missing Proofs in Section 4

###### Proof of Lemma 4.1.

We denote

$p={q}^{{R}:{y}\looparrowright{x}}=\left({q\setminus{q}^{{y}}_{{\vartriangle}}}\right)\cup
f({q}^{{x}}_{{\vartriangle}}),$

for some isomorphism $f$ that maps every variable in
${q}^{{x}}_{{\vartriangle}}$ to a fresh variable, except for $x$, which we
have $f(x)=y$.

Assume first that
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
witnessed by the homomorphism $h$ with $h(y)=x$. It is easy to verify that the
homomorphism $g:{\mathbf{vars}}({q})\rightarrow{\mathbf{vars}}({p})$ with

$g(z)=\begin{cases}z&\text{ if
$z\in{\mathbf{vars}}({q\setminus{q}^{{y}}_{{\vartriangle}}})$},\\\
f(h(z))&\text{ otherwise}\end{cases}$

is a homomorphism from $q$ to $p$.

Assume there is a homomorphism
$h:{\mathbf{vars}}({q})\rightarrow{\mathbf{vars}}({p})$ from $q$ to $p$. Hence

$h(q)=h(q\setminus{q}^{{y}}_{{\vartriangle}})\cup
h({q}^{{y}}_{{\vartriangle}})\subseteq\left({q\setminus{q}^{{y}}_{{\vartriangle}}}\right)\cup
f({q}^{{x}}_{{\vartriangle}}).$

Note that $q$ is minimal, i.e., there is no automorphism $\alpha$ such that
$\alpha(q)\subsetneq q$. If $h(y)=y$, since $q$ is minimal, we have
$h(q\setminus{q}^{{y}}_{{\vartriangle}})=q\setminus{q}^{{y}}_{{\vartriangle}}$,
and we have $h({q}^{{y}}_{{\vartriangle}})\subseteq
f({q}^{{x}}_{{\vartriangle}})$. Thus
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
witnessed by the homomorphism $g=f^{-1}\circ h$ with
$g(y)=f^{-1}(h(y))=f^{-1}(y)=x$, as desired.

Suppose for contradiction that $h(y)\neq y$. In this case, we have
$h(q\setminus{q}^{{y}}_{{\vartriangle}})\cap
f({q}^{{x}}_{{\vartriangle}})\neq\emptyset$.

We argue that $y=f(x)<_{{p}}h(y)$. Case (i) Assume $h(y)<_{{p}}y=f(x)$ holds.
Then $h$ maps the unique path of nodes from $r$ to $y$ in $q$ to the unique
path from $h(r)$ to $h(y)$ in $p$. While we have $r=h(r)$ or $r<_{{p}}h(r)$,
but since $h(y)<_{{p}}y$, this is not possible because the path from $h(r)$ to
$h(y)$ in $p$ is strictly shorter than the path from $r$ to $y$ in $q$. Case
(ii) Assume $h(y)\parallel_{{p}}y=f(x)$ holds. Let $y_{0}=y$, and for each
$i\geq 1$, $y_{i}=h(y_{i-1})$. We argue that variables $y_{0}$, $y_{1}$,
$\dots$ are all distinct, thereby reaching a contradiction to the finite size
of $q$. Assume first that $y_{1}$ is a left sibling of $y_{0}$ in $q$: for the
greatest common ancestor $y^{*}$ of $y_{1}$ and $y_{0}$, there is an atom
$R(\underline{y^{*}},..,y_{l},..,y_{r})$ such that $y_{l}$ and $y_{r}$ are
ancestors of $y_{1}$ and $y_{0}$. The arguments for the case where $y_{1}$ is
a right sibling of $y_{0}$ in $q$ is similar. Note that $y_{1}$ appears in
both $p$ and $q$ and its subtree is not affected by the rewinding operation
since $y_{1}\parallel_{{p}}y_{0}$. Since $y_{1}$ is a left sibling of $y_{0}$
and that the children of rooted trees are ordered, $h(y_{1})$ is a left
sibling of $h(y_{0})$, that is $y_{2}$ is a left sibling of $y_{1}$ in $q$,
and this process continues. Since each $y_{i+1}$ is a left sibling of $y_{i}$,
the variables need to be distinct, or otherwise there is some $y_{j+1}$ is a
right sibling of $y_{j}$, a contradiction.

Let ${T}[{z}]$ be the greatest common ancestor of ${R}[{x}]$ and ${R}[{y}]$ in
$q$ and let $u$ and $v$ be variables in ${T}[{z}]$ such that $u<_{{q}}x$ and
$v<_{{q}}y$ and $u\parallel_{{q}}v$. Hence $z$ appears in both $q$ and $p$.
Hence $z<_{{p}}h(z)$ but $h(z)\neq z$. We have

$|{{q}^{{u}}_{{\vartriangle}}}|+|{{q}^{{v}}_{{\vartriangle}}}|+1\leq|{{q}^{{z}}_{{\vartriangle}}}|\leq|{{p}^{{h(z)}}_{{\vartriangle}}}|,$

because the homomorphism maps ${q}^{{z}}_{{\vartriangle}}$ to the subtree of
$p$, rooted at $h(z)$.

We show that $v<_{{q}}h(z)$. Since $z<_{{q}}h(z)$ and $v$ is the immediate
child of $z$, we can have either $v<_{{q}}h(z)$ or $v\parallel_{{q}}h(z)$.
Suppose for contradiction that $v\parallel_{{q}}h(z)$, then
$h(z)\notin\\{u,v\\}$. Then,
${p}^{{h(z)}}_{{\vartriangle}}={q}^{{h(z)}}_{{\vartriangle}}$ since the
rewinding leaves ${q}^{{h(z)}}_{{\vartriangle}}$ intact. But that implies
$h({q}^{{z}}_{{\vartriangle}})\subseteq{q}^{{h(z)}}_{{\vartriangle}}$ with
$z<_{{q}}h(z)$, a contradiction.

Therefore, we have

$|{{q}^{{u}}_{{\vartriangle}}}|+|{{q}^{{v}}_{{\vartriangle}}}|+1\leq|{{p}^{{h(z)}}_{{\vartriangle}}}|\leq|{{p}^{{v}}_{{\vartriangle}}}|\leq|{{q}^{{v}}_{{\vartriangle}}}|-|{{q}^{{y}}_{{\vartriangle}}}|+|{{q}^{{x}}_{{\vartriangle}}}|,$

where the second inequality follows by construction of rewinding that replaces
${q}^{{y}}_{{\vartriangle}}$ with ${q}^{{x}}_{{\vartriangle}}$.

This yields

$0\leq|{{q}^{{u}}_{{\vartriangle}}}|-|{{q}^{{x}}_{{\vartriangle}}}|\leq-|{{q}^{{y}}_{{\vartriangle}}}|-1<0,$

a contradiction. ∎

##  Appendix B Missing Proofs in Section 6

We first show that the formula in Fig. 6 propagate on root homomorphism.

######  Lemma B.1.

Let $q$ be a rooted tree query and $\mathbf{db}$ a database instance. Then for
constants $c,d_{1},d_{2},\dots,d_{n}\in{\mathsf{adom}}({\mathbf{db}})$ where
$\vec{d}=\langle d_{1},d_{2},\dots,d_{n}\rangle$ and any two atoms ${R}[{x}]$
and ${R}[{y}]$ with
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
the following statements hold:

  1. 1.

if $\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{x})$ is true, then
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ is true; and

  2. 2.

if $\langle{c},{x}\rangle\in B$, then $\langle{c},{y}\rangle\in B$.

###### Proof.

We show both (1) and (2) by an induction on the height $k$ of the atom
${R}[{y}]$ in $q$.

  * •

Basis $k=0$. In this case, $y$ is a leaf variable of $q$ and (1) holds
vacuously. Assume that the label of $y$ is $L$, then there is an atom
$L(\underline{y})$ in $q$. Then there must be an atom $L(\underline{x})$ in
$q$. From $\langle{c},{x}\rangle\in B$, we have
$L(\underline{c})\in\mathbf{db}$, and thus $\langle{c},{y}\rangle\in B$ by the
initialization step.

  * •

Inductive step. Assume that both (1) and (2) holds if the height of
${q}^{{y}}_{{\vartriangle}}$ is less than $k$. Consider the case where the
height of ${q}^{{y}}_{{\vartriangle}}$ is $k$.

First we show (1) holds. Assume that
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{x})$ holds. Let
${R}[{x}]=R(\underline{x},x_{1},x_{2},\dots,x_{n})$ and
${R}[{y}]=R(\underline{y},y_{1},y_{2},\dots,y_{n})$. Consider two cases.

    * –

Case (I) that the following formula is true

$\bigwedge_{1\leq i\leq n}\langle{d_{i}},{x_{i}}\rangle\in B.$ (6)

To show $\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ holds, it suffices
to show

$\bigwedge_{1\leq i\leq n}\langle{d_{i}},{y_{i}}\rangle\in B.$

Consider any $y_{i}$. If $y_{i}$ is a leaf variable with label $\bot$, then
$\langle{d_{i}},{y_{i}}\rangle\in B$ by the initialization step. Otherwise,
there is an atom ${T}[{y_{i}}]$ in $q$. Since
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
there is some atom ${T}[{x_{i}}]$ in $q$ such that
${q}^{{y_{i}}}_{{\vartriangle}}\leq_{{y_{i}}\rightarrow{x_{i}}}{q}^{{x_{i}}}_{{\vartriangle}}$
and $\langle{d_{i}},{x_{i}}\rangle\in B$, by Equation (6). Since the height of
${T}[{y_{i}}]$ is less than $k$, by the inductive hypothesis for (2), we have
$\langle{d_{i}},{y_{i}}\rangle\in B$.

    * –

Case (II) that there is some atom ${R}[{u}]<_{{q}}{R}[{x}]$, such that
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{u})$ is true.

If ${R}[{u}]<_{{q}}{R}[{y}]$, then
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ holds. Otherwise, we must
have ${R}[{u}]\parallel_{{q}}{R}[{y}]$. Indeed, if not, we would have
${R}[{y}]<_{{q}}{R}[{u}]<_{{q}}{R}[{x}]$, but
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
a contradiction.

We argue that
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{u}}{q}^{{u}}_{{\vartriangle}}$.
If not, then by $\mathsf{C}_{\mathsf{branch}}$, we have
${q}^{{u}}_{{\vartriangle}}\leq_{{u}\rightarrow{y}}{q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$,
but ${R}[{u}]<_{{q}}{R}[{x}]$, a contradiction.

Note that we just established
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{u})$ is true and
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{u}}{q}^{{u}}_{{\vartriangle}}$
for ${R}[{u}]<_{{q}}{R}[{x}]$. If Case (I) holds when
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{u})$ is true, then
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ is true, as desired.
Otherwise, by the previous argument in Case (II), either
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ is true as desired, or
there is another atom ${R}[{w}]$ such that
${R}[{w}]<_{{q}}{R}[{u}]<_{{q}}{R}[{x}]$ and
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{w}}{q}^{{w}}_{{\vartriangle}}$.
Since there are only finitely many $R$-atoms in $q$, this process must
terminate and show that $\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ is
true.

For (2), assume that $\langle{c},{x}\rangle\in B$. For every fact
$R(\underline{c},\vec{d})\in\mathbf{db}$,
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{x})$ holds. By (1),
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$ holds for every
$R(\underline{c},\vec{d})\in\mathbf{db}$. Hence $\langle{c},{y}\rangle\in B$.

The proof is now complete. ∎

###### Proof of Lemma 6.2.

The lemma follows from Lemma B.1 if
${q}^{{y}}_{{\vartriangle}}\leq_{{y}\rightarrow{x}}{q}^{{x}}_{{\vartriangle}}$.
Assume that ${R}[{x}]<_{{q}}{R}[{y}]$, and both (1) and (2) are
straightforward by definition of
$\mathsf{fact}({R}(\underline{{c}},{\vec{d}}),{y})$. ∎

##  Appendix C Missing Proofs in Section 9

###### Proof of Lemma 9.1.

For item (1), let $\mathbf{db}$ be an instance for
$\mathsf{CERTAINTY}({q_{i}})$ and construct an instance
$\mathbf{db}^{\prime}=\mathbf{db}\cup\bigcup_{j\neq i}D[q_{j}]$ for
$\mathsf{CERTAINTY}({q})$, where $D[q_{j}]$ is a canonical copy of $q_{j}$.
Clearly, $\mathbf{db}^{\prime}$ can be constructed in $\mathbf{FO}$. Next, we
show that $\mathsf{CERTAINTY}({q_{i}})$ is true on $\mathbf{db}$ if and only
if $\mathsf{CERTAINTY}({q})$ is true on $\mathbf{db}^{\prime}$.

Assume that $\mathbf{db}$ is a “yes”-instance for
$\mathsf{CERTAINTY}({q_{i}})$. Let $\mathbf{r}^{\prime}$ be any repair of
$\mathbf{db}^{\prime}$. We have $\bigcup_{j\neq
i}D[q_{j}]\subseteq\mathbf{r}^{\prime}$, since each $D[q_{j}]$ is consistent.
Thus $\mathbf{r}=\mathbf{r}^{\prime}\setminus\bigcup_{j\neq i}D[q_{j}]$ is a
repair of $\mathbf{db}$, and we have that $\mathbf{r}$ satisfies $q_{i}$. Then
$\mathbf{r}^{\prime}$ satisfies $q$, since $\mathbf{r}$ also contains
$D[q_{j}]$, which satisfies $q_{j}$ for $j\neq i$.

Assume that $\mathbf{db}^{\prime}$ is a “yes”-instance for
$\mathsf{CERTAINTY}({q})$. Let $\mathbf{r}$ be any repair of $\mathbf{db}$. It
remains to show that $\mathbf{r}$ satisfy $q_{i}$. Let
$\mathbf{r}^{\prime}=\mathbf{r}\cup\bigcup_{j\neq i}D[q_{j}]$. Hence
$\mathbf{r}^{\prime}$ is a repair of $\mathbf{db}^{\prime}$, and and there is
a valuation $\mu$ such that $\mu(q)\subseteq\mathbf{r}^{\prime}$. It suffices
to show that $\mu(q_{i})\subseteq\mathbf{r}$. Suppose not, since each $q_{i}$
is connected and each $D[q_{j}]$ is connected, we must have
$\mu(q_{i})\subseteq D[q_{j}]$ for some $j\neq i$, which implies a
homomorphism from $q_{i}$ to $q_{j}$, contradicting that $q$ is minimal. Thus
$\mu(q_{i})\subseteq\mathbf{r}$, as desired.

Item (2) is proved in Lemma B.1 in [32]. ∎

###### Proof of Bridging Lemma.

For each atom $N(\underline{\vec{x}},\vec{y})$ in ${q}^{\mathsf{sjf}}$, we
denote $\pi(N)=R$ if $R(\underline{\vec{x}},\vec{y})$ in $q$.

We present a reduction from $\mathsf{CERTAINTY}({{q}^{\mathsf{sjf}}})$ to
$\mathsf{CERTAINTY}({q})$ in $\mathbf{FO}$.

Let ${\mathbf{db}}^{\mathsf{sjf}}$ be an instance for
$\mathsf{CERTAINTY}({{q}^{\mathsf{sjf}}})$ and
$N(\alpha_{1},\alpha_{2},\dots,\alpha_{n})$ an atom in ${q}^{\mathsf{sjf}}$.
Consider a mapping $\phi$ from facts to facts that for any fact
$f=N(f_{1},f_{2},\dots,f_{n})$ in ${\mathbf{db}}^{\mathsf{sjf}}$,

$\phi(f)=\pi(N)(\langle f_{1},\alpha_{1}\rangle,\langle
f_{2},\alpha_{2}\rangle,\dots,\langle f_{n},\alpha_{n}\rangle)$

where each $\langle f_{i},\alpha_{i}\rangle$ is a fresh constant such that
$\langle f_{i},\alpha_{i}\rangle=\langle f_{j},\alpha_{j}\rangle$ if and only
if $f_{i}=f_{j}$ and $\alpha_{i}=\alpha_{j}$. Let $\mathbf{db}=\\{\phi(f)\mid
f\in{\mathbf{db}}^{\mathsf{sjf}}\\}$.

We first show that $\phi$ is bijective from ${\mathbf{db}}^{\mathsf{sjf}}$ to
$\mathbf{db}$. By construction, $\phi$ is onto. Suppose $\phi$ is not
injective, then there exist two distinct facts $f=R(f_{1},f_{2},\dots,f_{n})$
and $g=S(g_{1},g_{2},\dots,g_{m})$ from atoms
$R(\alpha_{1},\alpha_{2},\dots,\alpha_{n})$ and
$S(\beta_{1},\beta_{2},\dots,\beta_{m})$ in ${q}^{\mathsf{sjf}}$ such that
$\phi(f)=\phi(g)$. We then have $m=n$, $\pi(R)=\pi(S)$ and for each $1\leq
i\leq n$, $\langle f_{i},\alpha_{i}\rangle=\langle g_{i},\beta_{i}\rangle$,
implying that
$\pi(R)(\alpha_{1},\alpha_{2},\dots,\alpha_{n})=\pi(S)(\beta_{1},\beta_{2},\dots,\beta_{m})$
in $q$, but $q$ is minimal, a contradiction.

We show that ${\mathbf{db}}^{\mathsf{sjf}}$ is a “yes”-instance for
$\mathsf{CERTAINTY}({{q}^{\mathsf{sjf}}})$ if and only if $\mathbf{db}$ is a
“yes”-instance for $\mathsf{CERTAINTY}({q})$. Towards this end, let
${\mathbf{r}}^{\mathsf{sjf}}$ be a repair of ${\mathbf{db}}^{\mathsf{sjf}}$,
and consider the set $\mathbf{r}=\\{\phi(f)\mid
f\in{\mathbf{r}}^{\mathsf{sjf}}\\}$. It is easy to see that $\mathbf{r}$ is a
repair of $\mathbf{db}$. Hence it is sufficent to show that
${\mathbf{r}}^{\mathsf{sjf}}$ satisfies ${q}^{\mathsf{sjf}}$ if and only if
$\mathbf{r}$ satisfies $q$.

Therefore, ${\mathbf{r}}^{\mathsf{sjf}}$ satisfies ${q}^{\mathsf{sjf}}$ if and
only if there exists a valuation $\mu$ such that
$\mu({q}^{\mathsf{sjf}})\subseteq{\mathbf{r}}^{\mathsf{sjf}}$. That is, for
every fact $f=R(\mu(\alpha_{1}),\mu(\alpha_{2}),\dots,\mu(\alpha_{n}))$ in
${\mathbf{r}}^{\mathsf{sjf}}$, $\phi(f)\in\mathbf{r}$. Since $\phi$ is
bijective, this is equivalent to $\phi(\mu(q))\subseteq\mathbf{r}$. This shows
that $\mathbf{r}$ satisfies $q$. The other direction follows similarly since
$\phi$ is bijective. ∎

Attacks. Let $q$ be a self-join-free Boolean CQ. For every atom $F\in q$, we
define $F^{+,q}$ as the set of all variables in $q$ that are functionally
determined by $\mathsf{key}(F)$ with respect to all functional dependencies of
the form $\mathsf{key}(G)\rightarrow\mathsf{vars}({G})$ with $G\in
q\setminus\\{F\\}$. Following [34], the _attack graph_ of $q$ is a directed
graph whose vertices are the atoms of $q$. There is a directed edge, called
_attack_ , from $F$ to $G$ ($F\neq G$), written
$F\stackrel{{\scriptstyle{q}}}{{\leadsto}}G$, if there exists a path between
$F$ and $G$ in the query such that every two adjacent atoms share a variable
not in $F^{+,q}$. The attack is called weak if
$\mathsf{key}(F)\rightarrow\mathsf{key}(G)$, otherwise it is called strong. It
was proved in [34] that for a self-join-free Boolean CQ $q$,
$\mathsf{CERTAINTY}({q})$ is $\mathbf{coNP}$-hard if and only if there exist
two atoms $F\neq G$ that attack each other and at least one of the attacks is
strong.

We can now prove the proposition.

###### Proof of Proposition 9.1.

Let $q$ be a minimal connected query in $\mathsf{GraphBCQ}$.

Assume that $q$ is not a rooted tree query. Then, there exist two atoms
$R(\underline{x},\dots,z,\dots)$ and $S(\underline{y},\dots,z,\dots)$ with
$x\neq y$ (and possibly $R=S$) in $q$. Consider now ${q}^{\mathsf{sjf}}$, and
let $R_{0}$ and $S_{0}$ be the corresponding atoms of $R$ and $S$ in
${q}^{\mathsf{sjf}}$.

Since $q$ satisfies (1) and (3), so does ${q}^{\mathsf{sjf}}$, and we have
$R_{0}^{+,{q}^{\mathsf{sjf}}}=\\{x\\}$ and
$S_{0}^{+,{q}^{\mathsf{sjf}}}=\\{y\\}$. Hence
$R_{0}\stackrel{{\scriptstyle{q}^{\mathsf{sjf}}}}{{\leadsto}}S_{0}$, and
similarly,
$S_{0}\stackrel{{\scriptstyle{q}^{\mathsf{sjf}}}}{{\leadsto}}R_{0}$. By [34]
$\mathsf{CERTAINTY}({{q}^{\mathsf{sjf}}})$ is $\mathbf{L}$-hard (due to this
cycle in the attack graph of ${q}^{\mathsf{sjf}}$), and so is
$\mathsf{CERTAINTY}({q})$ by Lemma 9.2.

Next we additionally assume that $q$ is Berge-acyclic, that is,
$q\in\mathsf{Graph_{Berge}BCQ}$. We thus have either $x\not\rightarrow_{{q}}y$
or $y\not\rightarrow_{{q}}x$. Indeed, otherwise there exist atoms
$R_{0},R_{1},\dots,R_{n}$ and $S_{0},S_{1},\dots,S_{m}$ and variables
$x_{0},x_{1},x_{2},\dots,x_{n+1}$, $y_{0},y_{1},\dots,y_{m+1}$ in
${q}^{\mathsf{sjf}}$ where $x_{0}=x$, $x_{n+1}=y$, $y_{0}=y$, $y_{m+1}=x$ such
that ${q}^{\mathsf{sjf}}$ contains atoms
$R_{i}(\underline{x_{i}},\dots,x_{i+1},\dots)$ for every $0\leq i\leq n$ and
$S_{i}(\underline{y_{i}},y_{i+1})$ for every $0\leq i\leq m$. Then,

$\\{x_{0},R_{0},x_{1},R_{1},\dots,R_{n},x_{n+1}(=y=y_{0}),S_{0},y_{1},S_{1},\dots,S_{m},y_{m+1}(=x=x_{0})\\}$

is a Berge-cycle in ${q}^{\mathsf{sjf}}$, a contradiction to that
${q}^{\mathsf{sjf}}$ (and $q$) are Berge-acyclic. This implies that at least
one of the two attacks is strong. Hence, applying the result from [34],
$\mathsf{CERTAINTY}({{q}^{\mathsf{sjf}}})$ is $\mathbf{coNP}$-hard (due to
this strong cycle in the attack graph of ${q}^{\mathsf{sjf}}$), and so is
$\mathsf{CERTAINTY}({q})$ by Lemma 9.2. ∎

We define two first-order formula $\varphi_{R}(u)$ and $\varphi_{S}(u)$:

$\displaystyle\varphi_{R}(u)$ $\displaystyle=\exists
yR(\underline{u},y)\land\forall y\left({R(\underline{u},y)\rightarrow\exists
zR(\underline{y},z)}\right)$ $\displaystyle\varphi_{S}(u)$
$\displaystyle=\exists yS(\underline{u},y)\land\forall
y\left({S(\underline{u},y)\rightarrow\exists zS(\underline{y},z)}\right)$

######  Lemma C.1 ([32]).

For $q=R(\underline{c},y),R(\underline{y},z)$, the $\mathbf{FO}$-rewriting of
the query $\mathsf{CERTAINTY}({q})$ is $\varphi_{R}(c)$.

######  Lemma C.2.

Let
$q=\\{R(\underline{u},x_{1}),R(\underline{x_{1}},x_{2}),S(\underline{u},y_{1}),S(\underline{y_{1}},y_{2})\\}$.
Then $\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$.

###### Proof.

Let $\mathbf{db}$ be a database instance. We show that $\mathbf{db}$ is a
“yes”-instance for $\mathsf{CERTAINTY}({q})$ if and only if $\mathbf{db}$
satisfies the formula

$\exists c:\varphi_{R}(c)\land\varphi_{S}(c).$

$\impliedby$ This direction is straightforward. Let $\mathbf{r}$ be any repair
of $\mathbf{db}$. By Lemma C.1, $\mathbf{r}$ contains a path of $RR$ starting
in $c$ and a path $SS$ starting in $c$. Hence $\mathbf{r}$ satisfies $q$.

$\implies$ Assume that $\mathbf{db}$ does not satisfy $\mathbf{r}$. We
construct a falsifying repair $\mathbf{r}$ of $\mathbf{db}$ as follows: For
each constant $c\in{\mathsf{adom}}({\mathbf{db}})$:

  * •

if $R(\underline{c},*)$ is empty and $S(\underline{c},*)$ is nonempty, pick an
arbitrary fact from $S(\underline{c},*)$;

  * •

if $R(\underline{c},*)$ is nonempty and $S(\underline{c},*)$ is empty, pick an
arbitrary fact from $R(\underline{c},*)$;

  * •

Assume that $R(\underline{c},*)$ and $S(\underline{c},*)$ are nonempty. If
$\varphi_{R}(c)$ is false, we pick $R(\underline{c},d_{1})$ such that
$R(\underline{d_{1}},*)$ is empty; or otherwise $\varphi_{S}(c)$ is false, we
pick $S(\underline{c},d_{2})$ such that $S(\underline{d_{2}},*)$ is empty.

We argue that $\mathbf{r}$ is a falsifying repair. Suppose for contradiction
that $\mathbf{r}$ satisfies $q$ and $u$ is mapped to $c$. Assume that
$R(\underline{c},d_{1}),S(\underline{c},d_{2})\in\mathbf{r}$. If
$\varphi_{R}(c)$ is false, then we would have picked a fact
$R(\underline{c},d_{1})$ such that $R(\underline{d_{1}},*)$ is empty, a
contradiction, and so is the other case where $\varphi_{S}(c)$ is false. ∎

######  Lemma C.3.

Let
$q=\\{R(\underline{u},x_{1}),R(\underline{x_{1}},x_{2}),X(\underline{x_{2}},x_{3}),S(\underline{u},y_{1}),S(\underline{y_{1}},y_{2})\\}$.
Then $\mathsf{CERTAINTY}({q})$ is in $\mathbf{NL}$-hard and in $\mathbf{LFP}$.

###### Proof.

The $\mathbf{NL}$-hardness proof follows by modifying the proof of Lemma 7.1
in [32] to also add a copy of $SS$ path starting in every vertex
$v\in\\{s^{\prime}\\}\cup V$.

Let $\mathbf{db}$ be a database instance. We revise the algorithm in Fig. 6
for $\mathsf{CERTAINTY}({RRX})$ as follows:

  * •

Initialize $N=\\{\langle{c},{x_{2}}\rangle\mid
X(\underline{c},*)\neq\emptyset\\}$

  * •

while $N$ is not fixed:

  * •

add $\langle{c},{x_{1}}\rangle$ to $N$ if

$\exists dR(\underline{c},d)\land\forall d\left({R(\underline{c},d)\rightarrow
f_{2}(R(\underline{c},d),R(\underline{x_{1}},x_{2}))}\right),$

where

$f_{2}(R(\underline{c},d),R(\underline{x_{1}},x_{2}))=\langle{d},{x_{2}}\rangle\in
N\lor\underbrace{\left({\varphi_{S}(c)\land
f_{1}(R(\underline{c},d),R(\underline{u},x_{1}))}\right)}_{\text{rewinding to
$R(\underline{u},x_{1})$ allowed only when $\varphi_{S}(c)$ is true}}$

  * •

add $\langle{c},{u}\rangle$ to $N$ if

$\varphi_{S}(c)\land\exists dR(\underline{c},d)\land\forall
d\left({R(\underline{c},d)\rightarrow
f_{1}(R(\underline{c},d),R(\underline{u},x_{1}))}\right),$

where

$f_{1}(R(\underline{c},d),R(\underline{u},x_{1}))=\langle{d},{x_{1}}\rangle\in
N.$

Our algorithm essentially first computes the set $N$ and then checks $\exists
c:\langle{c},{u}\rangle\in N$. Notice that this algorithm is in
$\mathbf{LFP}$. To show correctness, we argue that there exists a constant $c$
such that $\langle{c},{u}\rangle\in N$ if and only if $\mathbf{db}$ is a
“yes”-instance for $\mathsf{CERTAINTY}({q})$.

To this end, we need to define a refined notion of frugal repairs that take
into account of $\varphi_{S}(u)$ constructed as follows:

  * •

pick an arbitrary fact from every nonempty block $X(\underline{c},*)$;

  * •

for every nonempty block $S(\underline{c},*)$, if $\varphi_{S}(c)$ is true,
pick an arbitrary fact; or otherwise, pick $S(\underline{c},d)$ such that
$S(\underline{d},*)$ is empty; and

  * •

for every fact $R(\underline{c},d)$ in the block $R(\underline{c},*)$, we
define the frugal index of $R(\underline{c},d)$ to be

    * –

$0$, if $\varphi_{S}(c)\land f_{1}(R(\underline{c},d),R(\underline{u},x_{1}))$
is true;

    * –

$1$, if $\varphi_{S}(c)\land f_{1}(R(\underline{c},d),R(\underline{u},x_{1}))$
is false and $f_{2}(R(\underline{c},d),R(\underline{x_{1}},x_{2}))$ is true;
or

    * –

$2$, otherwise.

We then pick the fact $R(\underline{c},d)$ from each nonempty block
$R(\underline{c},*)$ with the largest frugal index.

######  Definition C.1.

An extended $RRX$-path in a repair $\mathbf{r}$ is a sequence of facts
$R(\underline{c_{0}},c_{1}),R(\underline{c_{1}},c_{2}),\dots,R(\underline{c_{n-1}},c_{n}),X(\underline{c_{n}},c_{n+1})$
in $\mathbf{r}$ for some $n\geq 2$ such that for every $0\leq i\leq n-2$,
there exists an $SS$-path in $\mathbf{r}$ starting in $c_{i}$.

The following claim concludes the proof.

######  Claim C.1.

The following statements are equivalent:

  1. 1.

$\langle{c},{u}\rangle\in N$;

  2. 2.

there exists an extended $RRX$-path in $\mathbf{r}^{*}$ starting in $c$; and

  3. 3.

for every repair $\mathbf{r}$ in $\mathbf{db}$, there exists an extended
$RRX$-path in $\mathbf{r}$ starting in $c$.

###### Proof.

(3) $\implies$ (2) Straightforward. (2) $\implies$ (1) Let
$R(\underline{c_{0}},c_{1}),R(\underline{c_{1}},c_{2}),\dots,R(\underline{c_{n-1}},c_{n}),X(\underline{c_{n}},c_{n+1})$
be an extended $RRX$-path in $\mathbf{r}^{*}$ for some $n\geq 2$ and
$c_{0}=c$. Since for every $0\leq i\leq n-2$, there exists an $SS$-path in
$\mathbf{r}^{*}$ starting in $c_{i}$, by construction of $\mathbf{r}^{*}$, we
have that $\varphi_{S}(c_{i})$ is true for every $0\leq i\leq n-2$.

We have that $\langle{c_{n}},{x_{2}}\rangle\in N$. Then for
$R(\underline{c_{n-1}},*)$, we have that
$f_{2}(R(\underline{c_{n-1}},c_{n}),R(\underline{x_{1}},x_{2}))$ is true. Then
by the choice of the frugal repair $\mathbf{r}^{*}$, the frugal index of
$R(\underline{c_{n-1}},c_{n})$ is at most 1, and thus
$f_{2}(R(\underline{c_{n-1}},c^{\prime}_{n}),R(\underline{x_{1}},x_{2}))$ is
true for every fact $R(\underline{c_{n-1}},c^{\prime}_{n})$ in the block
$R(\underline{c_{n-1}},*)$. Hence $\langle{c_{n-1}},{x_{1}}\rangle\in N$.

Then, we must have
$f_{1}(R(\underline{c_{n-2}},c_{n-1},R(\underline{u},x_{1}))$ is true, because
$\langle{c_{n-1}},{x_{1}}\rangle\in N$. Notice that $\varphi_{S}(c_{n-2})$ is
true, the frugal index of $R(\underline{c_{n-2}},c_{n-1})$ is $0$. Then by
construction of $\mathbf{r}^{*}$, for every fact
$R(\underline{c_{n-2}},c_{n-1}^{\prime})$ in block $R(\underline{c_{n-2}},*)$,
$f_{1}(R(\underline{c_{n-2}},c_{n-1},R(\underline{u},x_{1}))$ is true. Hence
$\langle{c_{n-2}},{u}\rangle\in N$. Additionally, for every fact
$R(\underline{c_{n-2}},c_{n-1}^{\prime})$ in block $R(\underline{c_{n-2}},*)$,
$\varphi_{S}(c_{n-2})\land
f_{1}(R(\underline{c_{n-2}},c_{n-1},R(\underline{u},x_{1}))$ is true, and thus
$f_{2}(R(\underline{c_{n-2}},c^{\prime}_{n-1},R(\underline{x_{1}},x_{2}))$ is
also true. This gives $\langle{c_{n-2}},{x_{1}}\rangle\in N$.

This argument may continue, until we yield that
$\langle{c_{0}},{u}\rangle=\langle{c},{u}\rangle\in N$.

(1) $\implies$ (3) Assume that $\langle{c},{u}\rangle$ in $N$. Let
$\mathbf{r}$ be any repair of $\mathbf{db}$. We inductively construct an
extended $RRX$-path in $\mathbf{r}$ starting in $c$. Assume that
$R(\underline{c_{0}},c_{1})\in\mathbf{r}$ with $c_{0}=c$. Hence
$\varphi_{S}(c_{0})$ is true, and that $\langle{c_{1}},{x_{1}}\rangle\in N$.
Let $R(\underline{c_{1}},c_{2})\in\mathbf{r}$, and we have
$f_{2}(R(\underline{c_{1}},c_{2}),R(\underline{x_{1}},x_{2}))$ is true. If
$\langle{c_{2}},{x_{2}}\rangle\in N$, let
$X(\underline{c_{2}},c_{3})\in\mathbf{r}$ and then the proof is complete since
$R(\underline{c_{0}},c_{1}),R(\underline{c_{1}},c_{2}),X(\underline{c_{2}},c_{3})$
is an extended $RRX$-path in $\mathbf{r}$. Otherwise, we have that
$\varphi_{S}(c_{1})\land
f_{1}(R(\underline{c_{1}},c_{2}),R(\underline{u},x_{1}))$ is true. Therefore,
$\varphi_{S}(c_{1})$ is true and $\langle{c_{2}},{x_{1}}\rangle\in N$. This
process thus continues, until we have produced facts
$R(\underline{c_{0}},c_{1}),R(\underline{c_{1}},c_{2}),\dots,R(\underline{c_{n-1}},c_{n})$,
such that $\varphi_{S}(c_{i})$ is true for $0\leq i\leq n-2$ and
$\langle{c_{n}},{x_{2}}\rangle\in N$, which gives a fact
$X(\underline{c_{n}},c_{n+1})\in\mathbf{r}$. Hence there exists an extended
$RRX$-path in $\mathbf{r}$ starting in $c_{0}=c$. ∎

Now, assume that $\langle{c},{u}\rangle\in N$. Then by Claim C.1, every repair
$\mathbf{r}$ of $\mathbf{db}$ contains an extended $RRX$-path starting in $c$,
which satisfies $q$. Assume that $\langle{c},{u}\rangle\notin N$. Then by
Claim C.1, there is no extended $RRX$-path in $\mathbf{r}^{*}$, and thus
$\mathbf{r}^{*}$ does not satisfy $q$. ∎

######  Lemma C.4.

Let
$q=\\{R(\underline{u},x_{1}),R(\underline{x_{1}},x_{2}),X(\underline{x_{2}},x_{3}),S(\underline{u},y_{1}),S(\underline{y_{1}},y_{2}),Y(\underline{y_{2}},y_{3})\\}$.
Then $\mathsf{CERTAINTY}({q})$ is $\mathbf{coNP}$-complete.

###### Proof.

For $\mathbf{coNP}$-hardness, we present a reduction from Monotone SAT: given
a monotone CNF formula $\varphi$, does $\varphi$ have a satisfying assignment?

Let $\varphi$ be a monotone CNF formula. We construct a database $\mathbf{db}$
for $\mathsf{CERTAINTY}({q})$ as follows:

  * •

for each variable $z$ in $\varphi$, introduce a copy of

$z^{-}=\langle{\\{R(\underline{u},x_{1}),R(\underline{x_{1}},x_{2}),X(\underline{x_{2}},x_{3}),S(\underline{u},y_{1}),Y(\underline{y_{1}},y_{2})\\}},{[u\rightarrow
z]}\rangle$

and a copy of

$z^{+}=\langle{\\{R(\underline{u},x_{1}),X(\underline{x_{1}},x_{2}),S(\underline{u},y_{1}),S(\underline{y_{1}},y_{2}),Y(\underline{y_{2}},y_{3})\\}},{[u\rightarrow
z]}\rangle;$

  * •

for each positive literal $z$ in a positive clause $C$, introduce a copy of

$C_{z}=\langle{\\{R(\underline{u},x_{1}),R(\underline{x_{1}},x_{2}),X(\underline{x_{2}},x_{3}),S(\underline{u},y_{1})\\}},{[u,y_{1}\rightarrow
C,z]}\rangle,$

  * •

for each negative literal $\overline{z}$ in a negative clause $\overline{C}$,
introduce a copy of

$\overline{C}_{z}=\langle{\\{R(\underline{u},x_{1}),S(\underline{u},y_{1}),S(\underline{y_{1}},y_{2}),Y(\underline{y_{2}},y_{3})\\}},{[u,x_{1}\rightarrow\overline{C},z]}\rangle.$

Note that by construction, the only inconsistencies happen at each block
$R(\underline{z},*)$ and $S(\underline{z},*)$, because each $R$-block may
choose either an $R$-edge or an $RX$-edge; and each $S$-block may choose
either an $S$-edge or an $SY$-edge. Surprisingly, there are $4$ possible
repairs for each variable $z$, but it is sufficient to encode a Boolean choice
between $z=0$ and $z=1$. An example gadget is shown in Fig. 7.

We show that $\varphi$ has a satisfying assignment if and only if there is a
repair of $\mathbf{db}$ that does not satisfy $q$.

$\implies$ Assume that $\sigma$ is a satisfying assignment to $\varphi$. We
now construct a repair $\mathbf{r}$ of $\mathbf{db}$ as follows. For each