# Consistent Query Answering for Primary Keys on Path Queries††thanks: This
paper is an evolved version of a paper with the same title and authors
published at ACM PODS’21 [25]. In particular, the proof of Lemma 9 in the
current paper is new and replaces a flawed proof in the earlier version, and
the technical treatment in the current Section 6.3 strengthens some earlier
results.

Paraschos Koutris  University of Wisconsin-Madison, WI, USA  Xiating Ouyang
University of Wisconsin-Madison, WI, 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 consistent
subset of the database. For a Boolean query $q$, the problem
$\mathsf{CERTAINTY}({q})$ takes a database as input, and asks whether or not
each repair satisfies $q$. It is known that for any self-join-free Boolean
conjunctive query $q$, $\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$,
$\mathbf{L}$-complete, or $\mathbf{coNP}$-complete. In particular,
$\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$ for any self-join-free Boolean
path query $q$. In this paper, we show that if self-joins are allowed, the
complexity of $\mathsf{CERTAINTY}({q})$ for Boolean path queries $q$ exhibits
a tetrachotomy between $\mathbf{FO}$, $\mathbf{NL}$-complete,
$\mathbf{PTIME}$-complete, and $\mathbf{coNP}$-complete. Moreover, it is
decidable, in polynomial time in the size of the query $q$, which of the four
cases applies.

##  1 Introduction

Primary keys are probably the most common integrity constraints in relational
database systems. Although databases should ideally satisfy their integrity
constraints, data integration is today frequently cited as a cause for primary
key violations, for example, when a same client is stored with different
birthdays in two data sources. A _repair_ of such an inconsistent database
instance is then naturally defined as a maximal consistent subinstance. 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) [3], instead of cleaning the inconsistent
database instance, we change the notion of query answer: the _consistent_ (or
_certain_) _answer_ is defined as the intersection of the query answers over
all (exponentially many) repairs. In computational complexity studies,
consistent query answering is commonly defined as the data complexity of the
following decision problem, for a fixed Boolean query $q$:

Problem:

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

Input:

A database instance $\mathbf{db}$.

Question:

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

For every first-order query $q$, the problem $\mathsf{CERTAINTY}({q})$ is
obviously in $\mathbf{coNP}$. However, despite significant research efforts
(see Section 9), a fine-grained complexity classification is still largely
open. A notorious open conjecture is the following.

######  Conjecture 1.

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

On the other hand, for the smaller class of self-join-free Boolean conjunctive
queries, the complexity landscape is by now well understood, as summarized by
the following theorem.

######  Theorem 1 ([32]).

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

Abandoning the restriction of self-join-freeness turns out to be a major
challenge. The difficulty of self-joins is caused by the obvious observation
that a single database fact can be used to satisfy more than one atom of a
conjunctive query, as illustrated by Example 1. Self-joins happen to
significantly change the complexity landscape laid down in Theorem 1; this is
illustrated by Example 2. Self-join-freeness is a simplifying assumption that
is also used outside CQA (e.g., [15, 4, 16]).

######  Example 1.

Take the self-join $q_{1}=\exists x\exists y(R(\underline{x},y)\land
R(\underline{y},x))$ and its self-join-free counterpart $q_{2}=\exists
x\exists y(R(\underline{x},y)\land S(\underline{y},x))$, where the primary key
positions are underlined. Consider the inconsistent database instance
$\mathbf{db}$ in Figure 1. We have that $\mathbf{db}$ is a “no”-instance of
$\mathsf{CERTAINTY}({q_{2}})$, because $q_{2}$ is not satisfied by the repair
$\\{R(\underline{a},a)$, $R(\underline{b},b)$, $S(\underline{a},b)$,
$S(\underline{b},a)\\}$. However, $\mathbf{db}$ is a “yes”-instance of
$\mathsf{CERTAINTY}({q_{1}})$. This is because every repair that contains
$R(\underline{a},a)$ or $R(\underline{b},b)$ will satisfy $q_{1}$, while a
repair that contains neither of these facts must contain $R(\underline{a},b)$
and $R(\underline{b},a)$, which together also satisfy $q_{1}$. ∎

$\begin{array}[]{cc}\begin{array}[]{c|cc}R&\underline{1}&2\bigstrut\\\
\cline{2-3}\cr&a&a\\\ &a&b\\\ \cdashline{2-3}&b&a\\\
&b&b\end{array}&\begin{array}[]{c|cc}S&\underline{1}&2\bigstrut\\\
\cline{2-3}\cr&a&a\\\ &a&b\\\ \cdashline{2-3}&b&a\\\
&b&b\end{array}\end{array}$
Figure 1: An inconsistent database instance $\mathbf{db}$.

######  Example 2.

Take the self-join $q_{1}=\exists x\exists y\exists z(R(\underline{x},z)\land
R(\underline{y},z))$ and its self-join-free counterpart $q_{2}=\exists
x\exists y\exists z(R(\underline{x},z)\land S(\underline{y},z))$.
$\mathsf{CERTAINTY}({q_{2}})$ is known to be $\mathbf{coNP}$-complete, whereas
it is easily verified that $\mathsf{CERTAINTY}({q_{1}})$ is in $\mathbf{FO}$,
by observing that a database instance is a “yes”-instance of
$\mathsf{CERTAINTY}({q_{1}})$ if and only if it satisfies $\exists x\exists
y(R(\underline{x},y))$. ∎

This paper makes a contribution to the complexity classification of
$\mathsf{CERTAINTY}({q})$ for conjunctive queries, possibly with self-joins,
of the form

$q=\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})}),$

which we call _path queries_. The primary key positions are underlined. As
will become apparent in our technical treatment, the classification of path
queries is already very challenging, even though it is only a first step
towards Conjecture 1, which is currently beyond reach. If all $R_{i}$’s are
distinct (i.e., if there are no self-joins), then $\mathsf{CERTAINTY}({q})$ is
known to be in $\mathbf{FO}$ for path queries $q$. However, when self-joins
are allowed, the complexity landscape of $\mathsf{CERTAINTY}({q})$ for path
queries exhibits a tetrachotomy, as stated by the following main result of our
paper.

######  Theorem 2.

For each Boolean path query $q$, $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{FO}$, $\mathbf{NL}$-complete, $\mathbf{PTIME}$-complete, or
$\mathbf{coNP}$-complete, and it is decidable in polynomial time in the size
of $q$ which of the four cases applies.

Comparing Theorem 1 and Theorem 2, it is striking that there are path queries
$q$ for which $\mathsf{CERTAINTY}({q})$ is $\mathbf{NL}$-complete or
$\mathbf{PTIME}$-complete, whereas these complexity classes do not occur for
self-join-free queries (under standard complexity assumptions). So even for
the restricted class of path queries, allowing self-joins immediately results
in a more varied complexity landscape.

Let us provide some intuitions behind Theorem 2 by means of examples. Path
queries use only binary relation names. A database instance $\mathbf{db}$ with
binary facts can be viewed as a directed edge-colored graph: a fact
$R(\underline{a},b)$ is a directed edge from $a$ to $b$ with color $R$. A
repair of $\mathbf{db}$ is obtained by choosing, for each vertex, precisely
one outgoing edge among all outgoing edges of the same color. We will use the
shorthand $q=RR$ to denote the path query $q=\exists x\exists y\exists
z(R(\underline{x},y)\land R(\underline{y},z))$.

In general, path queries can be represented by words over the alphabet of
relation names. Throughout this paper, relation names are in uppercase letters
$R$, $S$, $X$, $Y$ etc., while lowercase letters $u$, $v$, $w$ stand for
(possibly empty) words. An important operation on words is dubbed _rewinding_
: if a word has a factor of the form $RvR$, then rewinding refers to the
operation that replaces this factor with $RvRvR$. That is, rewinding the
factor $RvR$ in the word $uRvRw$ yields the longer word $uRvRvRw$. For short,
we also say that $uRvRw$ _rewinds to_ the word
$\mbox{${u}\\!\cdot\\!{Rv}\\!\cdot\\!\underline{Rv}\\!\cdot\\!{R}$}w$, where
we used concatenation $(\cdot)$ and underlining for clarity. For example,
$TWITTER$ rewinds to ${TWI}\\!\cdot\\!\underline{TWI}\\!\cdot\\!{TTER}$, but
also to ${TWIT}\\!\cdot\\!\underline{TWIT}\\!\cdot\\!{TER}$ and to
${TWI}\\!\cdot\\!{T}\\!\cdot\\!\underline{T}\\!\cdot\\!{TER}$.

Let $q_{1}=RR$. It is easily verified that a database instance is a
“yes”-instance of $\mathsf{CERTAINTY}({q_{1}})$ if and only if it satisfies
the following first-order formula:

$\varphi=\exists x({\exists yR(\underline{x},y)\land\forall
y({R(\underline{x},y)\rightarrow\exists zR(\underline{y},z)})}).$

Informally, every repair contains an $R$-path of length $2$ if and only if
there exists some vertex $x$ such that every repair contains a path of length
$2$ starting in $x$.

Let $q_{2}=RRX$, and consider the database instance in Figure 2. Since the
only conflicting facts are $R(\underline{1},2)$ and $R(\underline{1},3)$, this
database instance has two repairs. Both repairs satisfy $RRX$, but unlike the
previous example, there is no vertex $x$ such that every repair has a path
colored $RRX$ that starts in $x$. Indeed, in one repair, such path starts in
$0$; in the other repair it starts in $1$. For reasons that will become
apparent in our theoretical development, it is significant that both repairs
have paths that start in $0$ and are colored by a word in the regular language
defined by $RR\left({R}\right)^{*}X$. This is exactly the language that
contains $RRX$ and is closed under the rewinding operation. In general, it can
be verified with some effort that a database instance is a “yes”-instance of
$\mathsf{CERTAINTY}({q_{2}})$ if and only if it contains some vertex $x$ such
that every repair has a path that starts in $x$ and is colored by a word in
the regular language defined by $RR\left({R}\right)^{*}X$. The latter
condition can be tested in $\mathbf{PTIME}$ (and even in $\mathbf{NL}$).

$0$$1$$2$$3$$4$$R$$R$$R$$R$$X$ Figure 2: An example database instance
$\mathbf{db}$ for $q_{2}=RRX$.

The situation is still different for $q_{3}=ARRX$, for which it will be shown
that $\mathsf{CERTAINTY}({q_{3}})$ is $\mathbf{coNP}$-complete. Unlike our
previous example, repeated rewinding of $ARRX$ into words of the language
$ARR\left({R}\right)^{*}X$ is not helpful. For example, in the database
instance of Figure 3, every repair has a path that starts in $0$ and is
colored with a word in the language defined by $ARR\left({R}\right)^{*}X$.
However, the repair that contains $R(\underline{a},c)$ does not satisfy
$q_{3}$. Unlike Figure 2, the “bifurcation” in Figure 3 can be used as a
gadget for showing $\mathbf{coNP}$-completeness in Section 7.

$0$$a$$b$$c$$A$$R$$R$$X$$R$$R$$X$ Figure 3: An example database instance
$\mathbf{db}$ for $q_{3}=ARRX$.

Organization. Section 2 introduces the preliminaries. In Section 3, the
statement of Theorem 3 gives the syntactic conditions for deciding the
complexity of $\mathsf{CERTAINTY}({q})$ for path queries $q$. To prove this
theorem, we view the rewinding operator from the perspectives of regular
expressions and automata, which are presented in Sections 4 and 5
respectively. Sections 6 and 7 present, respectively, complexity upper bounds
and lower bounds of our classification. In Section 8, we extend our
classification result to path queries with constants. Section 9 discusses
related work, and Section 10 concludes this paper.

##  2 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. We consider only $2$-ary _relation names_ , where
the first position is called the _primary key_. If $R$ is a relation name, and
$s,t$ are variables or constants, then $R(\underline{s},t)$ is an _atom_. 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 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{c},*)$ for the block that contains all facts with relation
name $R$ and primary-key value $c$. 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{{x}_{1}},{y}_{1})$, $\dots$,
$R_{n}(\underline{{x}_{n}},{y}_{n})\\}$ of atoms. We denote by
${\mathsf{vars}}({q})$ the set of variables that occur in $q$. The set $q$
represents the first-order sentence

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

where $\\{u_{1},\dots,u_{k}\\}={\mathsf{vars}}({q})$.

We say that a Boolean conjunctive query $q$ has a self-join if some relation
name occurs more than once in $q$. A conjunctive query without self-joins is
called self-join-free.

Consistent query answering. For every Boolean conjunctive query $q$, 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 for every Boolean conjunctive query
$q$, $\mathsf{CERTAINTY}({q})$ is in $\mathbf{coNP}$.

Path queries. A path query is a Boolean conjunctive query without constants of
the following form:

$q=\\{R_{1}(\underline{x_{1}},x_{2}),R_{2}(\underline{x_{2}},x_{3}),\dots,R_{k}(\underline{x_{k}},x_{k+1})\\},$

where $x_{1}$, $x_{2}$,…, $x_{k+1}$ are distinct variables, and $R_{1}$,
$R_{2}$,…, $R_{k}$ are (not necessarily distinct) relation names. It will
often be convenient to denote this query as a word $R_{1}R_{2}\dotsm R_{k}$
over the alphabet of relation names. This “word” representation is obviously
lossless up to a variable renaming. Importantly, path queries may have self-
joins, i.e., a relation name may occur multiple times. Path queries containing
constants will be discussed in Section 8. The treatment of constants is
significant, because it allows moving from Boolean to non-Boolean queries, by
using that free variables behave like constants.

##  3 The Complexity Classification

We define syntactic conditions $\mathcal{C}_{1}$, $\mathcal{C}_{2}$, and
$\mathcal{C}_{3}$ for path queries $q$. Let $R$ be any relation name in $q$,
and let $u,v,w$ be (possibly empty) words over the alphabet of relation names
of $q$.

$\mathcal{C}_{1}$:

Whenever $q=uRvRw$, $q$ is a prefix of $uRvRvRw$.

$\mathcal{C}_{2}$:

Whenever $q=uRvRw$, $q$ is a factor of $uRvRvRw$; and whenever
$q=uRv_{1}Rv_{2}Rw$ for consecutive occurrences of $R$, $v_{1}=v_{2}$ or $Rw$
is a prefix of $Rv_{1}$.

$\mathcal{C}_{3}$:

Whenever $q=uRvRw$, $q$ is a factor of $uRvRvRw$.

It is instructive to think of these conditions in terms of the rewinding
operator introduced in Section 1: $\mathcal{C}_{1}$ is tantamount to saying
that $q$ is a prefix of every word to which $q$ rewinds; and $\mathcal{C}_{3}$
says that $q$ is a factor of every word to which $q$ rewinds. These conditions
can be checked in polynomial time in the length of the word $q$. The following
result has an easy proof.

######  Proposition 1.

Let $q$ be a path query. If $q$ satisfies $\mathcal{C}_{1}$, then $q$
satisfies $\mathcal{C}_{2}$; and if $q$ satisfies $\mathcal{C}_{2}$, then $q$
satisfies $\mathcal{C}_{3}$.

The main part of this paper comprises a proof of the following theorem, which
refines the statement of Theorem 2 by adding syntactic conditions. The theorem
is illustrated by Example 3.

######  Theorem 3.

For every path query $q$, the following complexity upper bounds obtain:

  * •

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

  * •

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

  * •

if $q$ satisfies $\mathcal{C}_{3}$, then $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{PTIME}$.

Moreover, for every path query $q$, the following complexity lower bounds
obtain:

  * •

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

  * •

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

  * •

if $q$ violates $\mathcal{C}_{3}$, then $\mathsf{CERTAINTY}({q})$ is
$\mathbf{coNP}$-complete.

######  Example 3.

The query $q_{1}=RXRX$ rewinds to (and only to)
${RX}\\!\cdot\\!\underline{RX}\\!\cdot\\!{RX}$ and
${R}\\!\cdot\\!{XR}\\!\cdot\\!\underline{XR}\\!\cdot\\!{X}$, which both
contain $q_{1}$ as a prefix. It is correct to conclude that
$\mathsf{CERTAINTY}({q_{1}})$ is in $\mathbf{FO}$.

The query $q_{2}=RXRY$ rewinds only to
${RX}\\!\cdot\\!\underline{RX}\\!\cdot\\!{RY}$, which contains $q_{2}$ as a
factor, but not as a prefix. Therefore, $q_{2}$ satisfies $\mathcal{C}_{3}$,
but violates $\mathcal{C}_{1}$. Since $q_{2}$ vacuously satisfies
$\mathcal{C}_{2}$ (because no relation name occurs three times in $q_{2}$), it
is correct to conclude that $\mathsf{CERTAINTY}({q_{2}})$ is
$\mathbf{NL}$-complete.

The query $q_{3}=RXRYRY$ rewinds to
${RX}\\!\cdot\\!\underline{RX}\\!\cdot\\!{RYRY}$, to
${RXRY}\\!\cdot\\!\underline{RXRY}\\!\cdot\\!{RY}$, and to
$\mbox{${RX}\\!\cdot\\!{RY}\\!\cdot\\!\underline{RY}\\!\cdot\\!{RY}$}=\mbox{${RXR}\\!\cdot\\!{YR}\\!\cdot\\!\underline{YR}\\!\cdot\\!{Y}$}$.
Since these words contain $q_{3}$ as a factor, but not always as a prefix, we
have that $q_{3}$ satisfies $\mathcal{C}_{3}$ but violates $\mathcal{C}_{1}$.
It can be verified that $q_{3}$ violates $\mathcal{C}_{2}$ by writing it as
follows:

$q_{3}=\underbrace{\varepsilon}_{u}\underbrace{\boldsymbol{R}X}_{Rv_{1}}\underbrace{\boldsymbol{R}Y}_{Rv_{2}}\underbrace{\boldsymbol{R}Y}_{Rw}$

We have $X=v_{1}\neq v_{2}=Y$, but $Rw=RY$ is not a prefix of $Rv_{1}=RX$.
Thus, $\mathsf{CERTAINTY}({q_{3}})$ is $\mathbf{PTIME}$-complete.

Finally, the path query $q_{4}=RXRXRYRY$ rewinds, among others, to
${RX}\\!\cdot\\!{RXRY}\\!\cdot\\!\underline{RXRY}\\!\cdot\\!{RY}$, which does
not contain $q_{4}$ as a factor. It is correct to conclude that
$\mathsf{CERTAINTY}({q_{4}})$ is $\mathbf{coNP}$-complete. ∎

##  4 Regexes for $\mathcal{C}_{1}$, $\mathcal{C}_{2}$, and $\mathcal{C}_{3}$

In this section, we show that the conditions $\mathcal{C}_{1}$,
$\mathcal{C}_{2}$, and $\mathcal{C}_{3}$ can be captured by regular
expressions (or regexes) on path queries, which will be used in the proof of
Theorem 3. Since these results are within the field of _combinatorics of
words_ , we will use the term _word_ rather than _path query_.

######  Definition 1.

We define four properties $\mathcal{B}_{1}$, $\mathcal{B}_{2a}$,
$\mathcal{B}_{2b}$, $\mathcal{B}_{3}$ that a word $q$ can possess:

$\mathcal{B}_{1}$:

For some integer $k\geq 0$, there are words $v$, $w$ such that $vw$ is self-
join-free and $q$ is a prefix of $w\left({v}\right)^{k}$.

$\mathcal{B}_{2a}$:

For some integers $j,k\geq 0$, there are words $u$, $v$, $w$ such that $uvw$
is self-join-free and $q$ is a factor of
$\left({u}\right)^{j}w\left({v}\right)^{k}$.

$\mathcal{B}_{2b}$:

For some integer $k\geq 0$, there are words $u$, $v$, $w$ such that $uvw$ is
self-join-free and $q$ is a factor of $\left({uv}\right)^{k}wv$.

$\mathcal{B}_{3}$:

For some integer $k\geq 0$, there are words $u$, $v$, $w$ such that $uvw$ is
self-join-free and $q$ is a factor of $uw\left({uv}\right)^{k}$. ∎

We can identify each condition among $\mathcal{C}_{1}$, $\mathcal{C}_{2}$,
$\mathcal{C}_{3}$, $\mathcal{B}_{1}$, $\mathcal{B}_{2a}$, $\mathcal{B}_{2b}$,
$\mathcal{B}_{3}$ with the set of all words satisfying this condition. Note
then that $\mathcal{B}_{1}\subseteq\mathcal{B}_{2a}\cap\mathcal{B}_{3}$. The
results in the remainder of this section can be summarized as follows:

  * •

$\mathcal{C}_{1}=\mathcal{B}_{1}$ (Lemma 1)

  * •

$\mathcal{C}_{2}=\mathcal{B}_{2a}\cup\mathcal{B}_{2b}$ (Lemma 3)

  * •

$\mathcal{C}_{3}=\mathcal{B}_{2a}\cup\mathcal{B}_{2b}\cup\mathcal{B}_{3}$
(Lemma 2)

Moreover, Lemma 3 characterizes $\mathcal{C}_{3}\setminus\mathcal{C}_{2}$.

######  Lemma 1.

For every word $q$, the following are equivalent:

  1. 1.

$q$ satisfies $\mathcal{C}_{1}$; and

  2. 2.

$q$ satisfies $\mathcal{B}_{1}$.

######  Lemma 2.

For every word $q$, the following are equivalent:

  1. 1.

$q$ satisfies $\mathcal{C}_{3}$; and

  2. 2.

$q$ satisfies $\mathcal{B}_{2a}$, $\mathcal{B}_{2b}$, or $\mathcal{B}_{3}$.

######  Definition 2 (First and last symbol).

For a nonempty word $u$, we write ${\mathsf{first}}({u})$ and
$\mathsf{last}({u})$ for, respectively, the first and the last symbol of $u$.
∎

######  Lemma 3.

Let $q$ be a word that satisfies $\mathcal{C}_{3}$. Then, the following three
statements are equivalent:

  1. 1.

$q$ violates $\mathcal{C}_{2}$;

  2. 2.

$q$ violates both $\mathcal{B}_{2a}$ and $\mathcal{B}_{2b}$; and

  3. 3.

there are words $u$, $v$, $w$ with $u\neq\varepsilon$ and $uvw$ self-join-free
such that either

    1. (a)

$v\neq\varepsilon$ and $\mathsf{last}({u})\cdot
wuvu\cdot{\mathsf{first}}({v})$ is a factor of $q$; or

    2. (b)

$v=\varepsilon$, $w\neq\varepsilon$, and $\mathsf{last}({u})\cdot
w\left({u}\right)^{2}\cdot{\mathsf{first}}({u})$ is a factor of $q$.

The shortest word of the form (3a) in the preceding lemma is $RRSRS$ (let
$u=R$, $v=S$, and $w=\varepsilon$), and the shortest word of the form (3b) is
$RSRRR$ (let $u=R$, $v=\varepsilon$, and $w=S$). Note that since each of
$\mathcal{C}_{2}$, $\mathcal{B}_{2a}$, and $\mathcal{B}_{2b}$ implies
$\mathcal{C}_{3}$, it is correct to conclude that the equivalence between the
first two items in Lemma 3 does not need the hypothesis that $q$ must satisfy
$\mathcal{C}_{3}$.

##  5 Automaton-Based Perspective

In this section, we prove an important lemma, Lemma 7, which will be used for
proving the complexity upper bounds in Theorem 3.

###  5.1 From Path Queries to Finite Automata

We can view a path query $q$ as a word where the alphabet is the set of
relation names. We now associate each path query $q$ with a nondeterministic
finite automaton (NFA), denoted ${\mathsf{NFA}}({q})$.

######  Definition 3 (${\mathsf{NFA}}({q})$).

Every word $q$ gives rise to a nondeterministic finite automaton (NFA) with
$\varepsilon$-moves, denoted ${\mathsf{NFA}}({q})$, as follows.

States:

The set of states is the set of prefixes of $q$. The empty word $\varepsilon$
is a prefix of $q$.

Forward transitions:

If $u$ and $uR$ are states, then there is a transition with label $R$ from
state $u$ to state $uR$. These transitions are said to be _forward_.

Backward transitions:

If $uR$ and $wR$ are states such that $|{u}|<|{w}|$ (and therefore $uR$ is a
prefix of $w$), then there is a transition with label $\varepsilon$ from state
$wR$ to state $uR$. These transitions are said to be _backward_ , and capture
the operation dubbed rewinding.

Initial and accepting states:

The initial state is $\varepsilon$ and the only accepting state is $q$. ∎

$\varepsilon$start$R$$RX$$RXR$$RXRR$$RXRRR$$R$$X$$R$$R$$R$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$
Figure 4: The ${\mathsf{NFA}}({q})$ automaton for the path query $q=RXRRR$.

Figure 4 shows the automaton ${\mathsf{NFA}}({RXRRR})$. Informally, the
forward transitions capture the automaton that would accept the word $RXRRR$,
while the backward transitions capture the existence of self-joins that allow
an application of the rewind operator. We now take an alternative route for
defining the language accepted by ${\mathsf{NFA}}({q})$, which
straightforwardly results in Lemma 4. Then, Lemma 5 gives alternative ways for
expressing $\mathcal{C}_{1}$ and $\mathcal{C}_{3}$.

######  Definition 4.

Let $q$ be a path query, represented as a word over the alphabet of relation
names. We define the language ${\mathcal{L}}^{\looparrowright}({q})$ as the
smallest set of words such that

  1. (a)

$q$ belongs to ${\mathcal{L}}^{\looparrowright}({q})$; and

  2. (b)

_Rewinding:_ if $uRvRw$ is in ${\mathcal{L}}^{\looparrowright}({q})$ for some
relation name $R$ and (possibly empty) words $u,v,w$, then $uRvRvRw$ is also
in ${\mathcal{L}}^{\looparrowright}({q})$. ∎

That is, ${\mathcal{L}}^{\looparrowright}({q})$ is the smallest language that
contains $q$ and is closed under rewinding.

######  Lemma 4.

For every path query $q$, the automaton ${\mathsf{NFA}}({q})$ accepts the
language ${\mathcal{L}}^{\looparrowright}({q})$.

######  Lemma 5.

Let $q$ be a path query. Then,

  1. 1.

$q$ satisfies $\mathcal{C}_{1}$ if and only if $q$ is a prefix of each
$p\in{\mathcal{L}}^{\looparrowright}({q})$;

  2. 2.

$q$ satisfies $\mathcal{C}_{3}$ if and only if $q$ is a factor of each
$p\in{\mathcal{L}}^{\looparrowright}({q})$.

###### Proof.

$\impliedby$ in (1) and (2) This direction is trivial, because whenever
$q=uRvRw$, we have that $uRvRvRw\in{\mathcal{L}}^{\looparrowright}({q})$.

We now show the $\implies$ direction in both items. To this end, we call an
application of the rule (b) in Definition 4 a _rewind_. By construction, each
word in ${\mathcal{L}}^{\looparrowright}({q})$ can be obtained from $q$ by
using $k$ rewinds, for some nonnegative integer $k$. Let $q_{k}$ be a word in
${\mathcal{L}}^{\looparrowright}({q})$ that can be obtained from $q$ by using
$k$ rewinds.

$\implies$ in (1) We use induction on $k$ to show that $q$ is a prefix of
$q_{k}$. For he induction basis, $k=0$, we have that $q$ is a prefix of
$q_{0}=q$. We next show the induction step $k\rightarrow k+1$. Let
$q_{k+1}=uRvRvRw$ where $q_{k}=uRvRw$ is a word in
${\mathcal{L}}^{\looparrowright}({q})$ obtained with $k$ rewinds. By the
induction hypothesis, we can assume a word $s$ such that $q_{k}=q\cdot s$.

  * •

If $q$ is a prefix of $uRvR$, then $q_{k+1}=uRvRvRw$ trivially contains $q$ as
a prefix;

  * •

otherwise $uRvR$ is a proper prefix of $q$. Let $q=uRvRt$ where $t$ is
nonempty. Since $q$ satisfies $\mathcal{C}_{1}$, $Rt$ is a prefix of $Rv$.
Then $q_{k+1}=uRvRvRw$ contains $q=u\cdot Rv\cdot Rt$ as a prefix.

$\implies$ in (2) We use induction on $k$ to show that $q$ is a factor of
$q_{k}$. For the induction basis, $k=0$, we have that $q$ is a prefix of
$q_{0}=q$. For the induction step, $k\rightarrow k+1$, let $q_{k+1}=uRvRvRw$
where $q_{k}=uRvRw$ is a word in ${\mathcal{L}}^{\looparrowright}({q})$
obtained with $k$ rewinds. By the induction hypothesis, $q_{k}=uRvRw$ contains
$q$ as a factor. If $q$ is a factor of either $uRvR$ or $RvRw$, then
$q_{k+1}=uRvRvRw$ contains $q$ as a factor. Otherwise, we can decompose
$q_{k}=u^{-}q^{-}RvRq^{+}w^{+}$ where $q=q^{-}RvRq^{+}$, $u=u^{-}q^{-}$ and
$w=q^{+}w^{+}$. Since $q$ satisfies $\mathcal{C}_{3}$, the word
$q^{-}RvRvRq^{+}$, which is a factor of $q_{k+1}$, contains $q$ as a factor. ∎

In the technical treatment, it will be convenient to consider the automaton
obtained from ${\mathsf{NFA}}({q})$ by changing its start state, as defined
next.

######  Definition 5.

If $u$ is a prefix of $q$ (and thus $u$ is a state in ${\mathsf{NFA}}({q})$),
then ${\mathsf{S\mathchar 45\relax NFA}}({q},{u})$ is the automaton obtained
from ${\mathsf{NFA}}({q})$ by letting the initial state be $u$ instead of the
empty word. Note that ${\mathsf{S\mathchar 45\relax
NFA}}({q},{\varepsilon})={\mathsf{NFA}}({q})$. It may be helpful to think of
the first $\mathsf{S}$ in ${\mathsf{S\mathchar 45\relax NFA}}({q},{u})$ as
“$\underline{\mathsf{S}}$tart at $u$.” ∎

###  5.2 Reification Lemma

In this subsection, we first define how an automaton executes on a database
instance. We then state an helping lemma which will be used in the proof of
Lemma 7, which constitutes the main result of Section 5. To improve the
readability and logical flow of our presentation, we postpone the proof of the
helping lemma to Section 5.3.

######  Definition 6 (Automata on database instances).

Let $\mathbf{db}$ be a database instance. A _path (in $\mathbf{db}$)_ is
defined as a sequence $R_{1}(\underline{c_{1}},c_{2})$,
$R_{2}(\underline{c_{2}},c_{3})$, …, $R_{n}(\underline{c_{n}},c_{n+1})$ of
facts in $\mathbf{db}$. Such a path is said to _start in $c_{1}$_. We call
$R_{1}R_{2}\dotsm R_{n}$ the _trace_ of this path. A path is said to be
_accepted_ by an automaton if its trace is accepted by the automaton.

Let $q$ be a path query and $\mathbf{r}$ be a consistent database instance. 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 path
in $\mathbf{r}$ that starts in $c$ and is accepted by ${\mathsf{NFA}}({q})$. ∎

######  Example 4.

Consider the query $q_{2}=RRX$ and the database instance of Figure 2. Let
$\mathbf{r}_{1}$ and $\mathbf{r}_{2}$ be the repairs containing, respectively,
$R(\underline{1},2)$ and $R(\underline{1},3)$. The only path with trace $RRX$
in $\mathbf{r}_{1}$ starts in $1$; and the only path with trace $RRX$ in
$\mathbf{r}_{2}$ starts in $0$. The regular expression for
${\mathcal{L}}^{\looparrowright}({q})$ is $RR\left({R}\right)^{*}X$. We have
${\mathsf{start}}({q},{\mathbf{r}_{1}})=\\{0,1\\}$ and
${\mathsf{start}}({q},{\mathbf{r}_{2}})=\\{0\\}$. ∎

The following lemma tells us that, among all repairs, there is one that is
inclusion-minimal with respect to ${\mathsf{start}}({q},{\cdot})$. In the
preceding example, the repair $\mathbf{r}_{2}$ minimizes
${\mathsf{start}}({q},{\cdot})$.

######  Lemma 6.

Let $q$ be a path query, and $\mathbf{db}$ a database instance. There exists a
repair $\mathbf{r}^{*}$ of $\mathbf{db}$ such that for every repair
$\mathbf{r}$ of $\mathbf{db}$,
${\mathsf{start}}({q},{\mathbf{r}^{*}})\subseteq{\mathsf{start}}({q},{\mathbf{r}})$.

Informally, we think of the next Lemma 7 as a _reification lemma_. The notion
of _reifiable variable_ was coined in [40, Definition 8.5], to refer to a
variable $x$ in a query $\exists x\left({\varphi(x)}\right)$ such that
whenever that query is true in every repair of a database instance, then there
is a constant $c$ such that $\varphi(c)$ is true in every repair. The
following lemma captures a very similar concept.

######  Lemma 7 (Reification Lemma for $\mathcal{C}_{3}$).

Let $q$ be a path query that satisfies $\mathcal{C}_{3}$. Then, for every
database instance $\mathbf{db}$, the following are equivalent:

  1. 1.

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

  2. 2.

there exists a constant $c$ (which depends on $\mathbf{db}$) such that for
every repair $\mathbf{r}$ of $\mathbf{db}$,
$c\in{\mathsf{start}}({q},{\mathbf{r}})$.

###### Proof.

1$\implies$2 Assume (1). By Lemma 6, there exists a repair $\mathbf{r}^{*}$ of
$\mathbf{db}$ such that for every repair $\mathbf{r}$ of $\mathbf{db}$,
${\mathsf{start}}({q},{\mathbf{r}^{*}})\subseteq{\mathsf{start}}({q},{\mathbf{r}})$.
Since $\mathbf{r}^{*}$ satisfies $q$, there is a path
$R_{1}(\underline{c_{1}},c_{2})$, $R_{2}(\underline{c_{2}},c_{3})$, …,
$R_{n}(\underline{c_{n}},c_{n+1})$ in $\mathbf{r}^{*}$ such that
$q=R_{1}R_{2}\dotsm R_{n}$. Since $q$ is accepted by ${\mathsf{NFA}}({q})$, we
have $c_{1}\in{\mathsf{start}}({q},{\mathbf{r}^{*}})$. It follows that
$c_{1}\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}})$. Therefore, there is a path in
$\mathbf{r}$ that starts in $c$ and is accepted by ${\mathsf{NFA}}({q})$. Let
$p$ be the trace of this path. By Lemma 4,
$p\in{\mathcal{L}}^{\looparrowright}({q})$. Since $q$ satisfies
$\mathcal{C}_{3}$ by the hypothesis of the current lemma, it follows by Lemma
5 that $q$ is a factor of $p$. Consequently, there is a path in $\mathbf{r}$
whose trace is $q$. It follows that $\mathbf{r}$ satisfies $q$. ∎

###  5.3 Proof of Lemma 6

We will use the following definition.

######  Definition 7 (States Set).

This definition is relative to a path query $q$. Let $\mathbf{r}$ be a
consistent database instance, and let $f$ be an $R$-fact in $\mathbf{r}$, for
some relation name $R$. The _states set_ of $f$ in $\mathbf{r}$, denoted
${\mathsf{ST}}_{q}({f},{\mathbf{r}})$, is defined as the smallest set of
states satisfying the following property, for all prefixes $u$ of $q$:

> if ${\mathsf{S\mathchar 45\relax NFA}}({q},{u})$ accepts a path in
> $\mathbf{r}$ that starts with $f$, then $uR$ belongs to
> ${\mathsf{ST}}_{q}({f},{\mathbf{r}})$.

Note that if $f$ is an $R$-fact, then all states in ${\mathsf{S\mathchar
45\relax NFA}}({q},{\mathbf{r}})$ have $R$ as their last relation name. ∎

######  Example 5.

Let $q=RRX$ and $\mathbf{r}=\\{R(\underline{a},b)$, $R(\underline{b},c)$,
$R(\underline{c},d)$, $X(\underline{d},e)$, $R(\underline{d},e)\\}$. Then
${\mathsf{NFA}}({q})$ has states $\\{\varepsilon,R,RR,RRX\\}$ and accepts the
regular language $RR\left({R}\right)^{*}X$. Since ${\mathsf{S\mathchar
45\relax NFA}}({q},{\varepsilon})$ accepts the path $R(\underline{b},c)$,
$R(\underline{c},d)$, $X(\underline{c},d)$, the states set
${\mathsf{ST}}_{q}({R(\underline{b},c)},{\mathbf{r}})$ contains
$\varepsilon\cdot R=R$. Since the latter path is also accepted by
${\mathsf{S\mathchar 45\relax NFA}}({q},{R})$, we also have $R\cdot
R\in{\mathsf{ST}}_{q}({R(\underline{b},c)},{\mathbf{r}})$. Finally, note that
${\mathsf{ST}}_{q}({R(\underline{d},e)},{\mathbf{r}})=\emptyset$, because
there is no path that contains $R(\underline{d},e)$ and is accepted by
${\mathsf{NFA}}({q})$. ∎

######  Lemma 8.

Let $q$ be a path query, and $\mathbf{r}$ a consistent database instance. If
${\mathsf{ST}}_{q}({f},{\mathbf{r}})$ contains state $uR$, then it contains
every state of the form $vR$ with $|{v}|\geq|{u}|$.

###### Proof.

Assume $uR\in{\mathsf{ST}}_{q}({f},{\mathbf{r}})$. Then $f$ is an $R$-fact and
there is a path $f\cdot\pi$ in $\mathbf{r}$ that is accepted by
${\mathsf{S\mathchar 45\relax NFA}}({q},{u})$. Let $vR$ be a state with
$|{v}|>|{u}|$. Thus, by construction, ${\mathsf{NFA}}({q})$ has a backward
transition with label $\varepsilon$ from state $vR$ to state $uR$.

It suffices to show that $f\cdot\pi$ is accepted by ${\mathsf{S\mathchar
45\relax NFA}}({q},{v})$. Starting in state $v$, ${\mathsf{S\mathchar 45\relax
NFA}}({q},{v})$ traverses $f$ (reaching state $vR$) and then uses the backward
transition (with label $\varepsilon$) to reach the state $uR$. From there on,
${\mathsf{S\mathchar 45\relax NFA}}({q},{v})$ behaves like
${\mathsf{S\mathchar 45\relax NFA}}({q},{u})$. ∎

From Lemma 8, it follows that ${\mathsf{ST}}_{q}({f},{\mathbf{r}})$ is
completely determined by the shortest word in it.

######  Definition 8.

Let $q$ be a path query and $\mathbf{db}$ a database instance. For every fact
$f\in\mathbf{db}$, we define:

${\mathsf{cqaST}}_{q}({f},{\mathbf{db}})\vcentcolon=\bigcap\\{{\mathsf{ST}}_{q}({f},{\mathbf{r}})\mid\textnormal{$\mathbf{r}$
is a repair of $\mathbf{db}$ that contains $f$}\\},$

where $\bigcap X=\bigcap_{S\in X}S$. ∎

It is to be noted here that whenever $\mathbf{r}_{1}$ and $\mathbf{r}_{2}$ are
repairs containing $f$, then by Lemma 8,
${\mathsf{ST}}_{q}({f},{\mathbf{r}_{1}})$ and
${\mathsf{ST}}_{q}({f},{\mathbf{r}_{2}})$ are comparable by set inclusion.
Therefore, informally, ${\mathsf{cqaST}}_{q}({f},{\mathbf{db}})$ is the
$\subseteq$-minimal states set of $f$ over all repairs that contain $f$.

######  Definition 9 (Preorder $\preceq_{q}$ on repairs).

Let $\mathbf{db}$ be a database instance. For all repairs
$\mathbf{r},\mathbf{s}$ of $\mathbf{db}$, we define
$\mathbf{r}\preceq_{q}\mathbf{s}$ if for every $f\in\mathbf{r}$ and
$g\in\mathbf{s}$ such that $f$ and $g$ are key-equal, we have
${\mathsf{ST}}_{q}({f},{\mathbf{r}})\subseteq{\mathsf{ST}}_{q}({g},{\mathbf{s}})$.

Clearly, $\preceq_{q}$ is a reflexive and transitive binary relation on the
set of repairs of $\mathbf{db}$. We write $\mathbf{r}\prec_{q}\mathbf{s}$ if
both $\mathbf{r}\preceq_{q}\mathbf{s}$ and for some $f\in\mathbf{r}$ and
$g\in\mathbf{s}$ such that $f$ and $g$ are key-equal,
${\mathsf{ST}}_{q}({f},{\mathbf{r}})\subsetneq{\mathsf{ST}}_{q}({g},{\mathbf{s}})$.
∎

######  Lemma 9.

Let $q$ be a path query. For every database instance $\mathbf{db}$, there is a
repair $\mathbf{r}^{*}$ of $\mathbf{db}$ such that for every repair
$\mathbf{r}$ of $\mathbf{db}$, $\mathbf{r}^{*}\preceq_{q}\mathbf{r}$.

###### Proof.

Construct a repair $\mathbf{r}^{*}$ as follows. For every block $\mathbf{blk}$
of $\mathbf{db}$, insert into $\mathbf{r}^{*}$ a fact $f$ of $\mathbf{blk}$
such that
${\mathsf{cqaST}}_{q}({f},{\mathbf{db}})=\bigcap\\{{\mathsf{cqaST}}_{q}({g},{\mathbf{db}})\mid
g\in\mathbf{blk}\\}$. More informally, we insert into $\mathbf{r}^{*}$ a fact
$f$ from $\mathbf{blk}$ with a states set that is $\subseteq$-minimal over all
repairs and all facts of $\mathbf{blk}$. We first show the following claim.

######  Claim 1.

For every fact $f$ in $\mathbf{r}^{*}$, we have
${\mathsf{ST}}_{q}({f},{\mathbf{r}^{*}})={\mathsf{cqaST}}_{q}({f},{\mathbf{db}})$.

###### Proof.

Let $f_{1}$ be an arbitrary fact in $\mathbf{r}^{*}$. We show
${\mathsf{ST}}_{q}({f_{1}},{\mathbf{r}^{*}})={\mathsf{cqaST}}_{q}({f_{1}},{\mathbf{db}})$.

$\supseteq$ Obvious, because $\mathbf{r}^{*}$ is itself a repair of
$\mathbf{db}$ that contains $f_{1}$.

$\subseteq$ Let $f_{1}=R_{1}(\underline{c_{0}},c_{1})$. Assume by way of a
contradiction that there is
$p_{1}\in{\mathsf{ST}}_{q}({f_{1}},{\mathbf{r}^{*}})$ such that
$p_{1}\notin{\mathsf{cqaST}}_{q}({f_{1}},{\mathbf{db}})$. Then, for some
(possibly empty) prefix $p_{0}$ of $q$, there is a sequence:

$p_{0}\stackrel{{\scriptstyle\varepsilon}}{{\longrightarrow}}p_{0}^{\prime}\stackrel{{\scriptstyle
f_{1}=R_{1}(\underline{c_{0}},c_{1})}}{{\xrightarrow{\hskip
70.0pt}}}p_{1}\stackrel{{\scriptstyle\varepsilon}}{{\longrightarrow}}p_{1}^{\prime}\stackrel{{\scriptstyle
f_{2}=R_{2}(\underline{c_{1}},c_{2})}}{{\xrightarrow{\hskip
70.0pt}}}p_{2}\quad\dotsm\quad
p_{n-1}\stackrel{{\scriptstyle\varepsilon}}{{\longrightarrow}}p_{n-1}^{\prime}\stackrel{{\scriptstyle
f_{n}=R_{n}(\underline{c_{n-1}},c_{n})}}{{\xrightarrow{\hskip
70.0pt}}}p_{n}=q,$ (1)

where $f_{1},f_{2},\ldots,f_{n}\in\mathbf{r}^{*}$, for each
$i\in\\{1,\ldots,n\\}$, $p_{i}=p_{i-1}^{\prime}R_{i}$, and for each
$i\in\\{0,\ldots,n-1\\}$, either $p_{i}^{\prime}=p_{i}$ or $p_{i}^{\prime}$ is
a strict prefix of $p_{i}$ such that $p_{i}^{\prime}$ and $p_{i}$ agree on
their rightmost relation name. Informally, the sequence (1) represents an
accepting run of ${\mathsf{S\mathchar 45\relax NFA}}({q},{p_{0}})$ in
$\mathbf{r}^{*}$. Since
$p_{1}\in{\mathsf{ST}}_{q}({f_{1}},{\mathbf{r}^{*}})\setminus{\mathsf{cqaST}}_{q}({f_{1}},{\mathbf{db}})$,
we can assume a largest index $\ell\in\\{1,\ldots,n\\}$ such that
$p_{\ell}\in{\mathsf{ST}}_{q}({f_{\ell}},{\mathbf{r}^{*}})\setminus{\mathsf{cqaST}}_{q}({f_{\ell}},{\mathbf{db}})$.
By construction of $\mathbf{r}^{*}$, there is a repair $\mathbf{s}$ such that
$f_{\ell}\in\mathbf{s}$ and
${\mathsf{ST}}_{q}({f_{\ell}},{\mathbf{s}})={\mathsf{cqaST}}_{q}({f_{\ell}},{\mathbf{db}})$.
Consequently, $p_{\ell}\notin{\mathsf{ST}}_{q}({f_{\ell}},{\mathbf{s}})$. We
distinguish two cases:

Case that $\ell=n$.

Thus, the run (1) ends with

$\dotsm\quad
p_{\ell-1}\stackrel{{\scriptstyle\varepsilon}}{{\longrightarrow}}p_{\ell-1}^{\prime}\stackrel{{\scriptstyle
f_{\ell}=R_{\ell}(\underline{c_{\ell-1}},c_{\ell})}}{{\xrightarrow{\hskip
70.0pt}}}p_{\ell}=q.$

Thus, the rightmost relation name in $q$ is $R_{\ell}$. Since
$f_{\ell}\in\mathbf{s}$, it is clear that
$p_{\ell}\in{\mathsf{ST}}_{q}({f_{\ell}},{\mathbf{s}})$, a contradiction.

Case that $\ell<n$.

Thus, the run (1) includes

$\dotsm\quad
p_{\ell-1}\stackrel{{\scriptstyle\varepsilon}}{{\longrightarrow}}p_{\ell-1}^{\prime}\stackrel{{\scriptstyle
f_{\ell}=R_{\ell}(\underline{c_{\ell-1}},c_{\ell})}}{{\xrightarrow{\hskip
70.0pt}}}p_{\ell}\stackrel{{\scriptstyle\varepsilon}}{{\longrightarrow}}p_{\ell}^{\prime}\stackrel{{\scriptstyle
f_{\ell+1}=R_{\ell+1}(\underline{c_{\ell}},c_{\ell+1})}}{{\xrightarrow{\hskip
70.0pt}}}p_{\ell+1}\quad\dotsm,$

where $\ell+1$ can be equal to $n$. Clearly,
$p_{\ell+1}\in{\mathsf{ST}}_{q}({f_{\ell+1}},{\mathbf{r}^{*}})$. Assume
without loss of generality that $\mathbf{s}$ contains
$f_{\ell+1}^{\prime}\vcentcolon=R_{\ell+1}(\underline{c_{\ell}},c_{\ell+1}^{\prime})$,
which is key-equal to $f_{\ell+1}$ (possibly
$c_{\ell+1}^{\prime}=c_{\ell+1}$). From
$p_{\ell}\notin{\mathsf{ST}}_{q}({f_{\ell}},{\mathbf{s}})$, it follows
$p_{\ell+1}\notin{\mathsf{ST}}_{q}({f_{\ell+1}^{\prime}},{\mathbf{s}})$.
Consequently,
$p_{\ell+1}\notin{\mathsf{cqaST}}_{q}({f_{\ell+1}^{\prime}},{\mathbf{db}})$.
By our construction of $r^{*}$, we have
$p_{\ell+1}\notin{\mathsf{cqaST}}_{q}({f_{\ell+1}},{\mathbf{db}})$.
Consequently,
$p_{\ell+1}\in{\mathsf{ST}}_{q}({f_{\ell+1}},{\mathbf{r}^{*}})\setminus{\mathsf{cqaST}}_{q}({f_{\ell+1}},{\mathbf{db}})$,
which contradicts that $\ell$ was chosen to be the largest such an index
possible.

The proof of Claim 1 is now concluded. ∎

To conclude the proof of the lemma, let $\mathbf{r}$ be any repair of
$\mathbf{db}$, and let $f\in\mathbf{r}^{*}$ and $f^{\prime}\in\mathbf{r}$ be
two key-equal facts in $\mathbf{db}$. By Claim 1 and the construction of
$\mathbf{r}^{*}$, we have that
${\mathsf{ST}}_{q}({f},{\mathbf{r}^{*}})={\mathsf{cqaST}}_{q}({f},{\mathbf{db}})\subseteq{\mathsf{cqaST}}_{q}({f^{\prime}},{\mathbf{db}})\subseteq{\mathsf{ST}}_{q}({f^{\prime}},{\mathbf{r}}),$
as desired. ∎

We can now give the proof of Lemma 6.

###### Proof of Lemma 6.

Let $\mathbf{db}$ be a database instance. Then by Lemma 9, there is a repair
$\mathbf{r}^{*}$ of $\mathbf{db}$ such that for every repair $\mathbf{r}$ of
$\mathbf{db}$, $\mathbf{r}^{*}\preceq_{q}\mathbf{r}$. It suffices to show that
for every repair $\mathbf{r}$ of $\mathbf{db}$,
${\mathsf{start}}({q},{\mathbf{r}^{*}})\subseteq{\mathsf{start}}({q},{\mathbf{r}})$.
To this end, consider any repair $\mathbf{r}$ and
$c\in{\mathsf{start}}({q},{\mathbf{r}^{*}})$. Let $R$ be the first relation
name of $q$. Since $c\in{\mathsf{start}}({q},{\mathbf{r}^{*}})$, there is
$d\in{\mathsf{adom}}({\mathbf{r}^{*}})$ such that
$R\in{\mathsf{ST}}_{q}({R(\underline{c},d)},{\mathbf{r}^{*}})$. Then, there is
a unique $d^{\prime}\in{\mathsf{adom}}({\mathbf{r}})$ such that
$R(\underline{c},d^{\prime})\in\mathbf{r}$, where it is possible that
$d^{\prime}=d$. From $\mathbf{r}^{*}\preceq_{q}\mathbf{r}$, it follows
${\mathsf{ST}}_{q}({R(\underline{c},d)},{\mathbf{r}^{*}})\subseteq{\mathsf{ST}}_{q}({R(\underline{c},d^{\prime})},{\mathbf{r}})$.
Consequently,
$R\in{\mathsf{ST}}_{q}({R(\underline{c},d^{\prime})},{\mathbf{r}})$, which
implies $c\in{\mathsf{start}}({q},{\mathbf{r}})$. This conclude the proof. ∎

##  6 Complexity Upper Bounds

We now show the complexity upper bounds of Theorem 3.

###  6.1 A $\mathbf{PTIME}$ Algorithm for $\mathcal{C}_{3}$

We now specify a polynomial-time algorithm for $\mathsf{CERTAINTY}({q})$, for
path queries $q$ that satisfy condition $\mathcal{C}_{3}$. The algorithm is
based on the automata defined in Definition 5, and uses the concept defined
next.

######  Definition 10 (Relation $\vdash_{q}$).

Let $q$ be a path query and $\mathbf{db}$ a database instance. For every
$c\in{\mathsf{adom}}({q})$ and every prefix $u$ of $q$, we write
$\mathbf{db}\vdash_{q}\langle{c},{u}\rangle$ if every repair of $\mathbf{db}$
has a path that starts in $c$ and is accepted by ${\mathsf{S\mathchar 45\relax
NFA}}({q},{u})$. ∎

An algorithm that decides the relation $\vdash_{q}$ can be used to solve
$\mathsf{CERTAINTY}({q})$ for path queries satisfying $\mathcal{C}_{3}$.
Indeed, by Lemma 7, for path queries satisfying $\mathcal{C}_{3}$,
$\mathbf{db}$ is a “yes”-instance for the problem $\mathsf{CERTAINTY}({q})$ if
and only if there is a constant $c\in{\mathsf{adom}}({\mathbf{db}})$ such that
$\mathbf{db}\vdash_{q}\langle{c},{u}\rangle$ with $u=\varepsilon$.

Initialization Step: | $N\leftarrow\\{\langle{c},{q}\rangle\mid c\in{\mathsf{adom}}({\mathbf{db}})\\}.$
---|---
Iterative Rule: |  | if |  $uR$ is a prefix of $q$, and
---|---
|  $R(\underline{c},*)$ is a nonempty block in $\mathbf{db}$ s.t. for every
$R(\underline{c},y)\in\mathbf{db}$, $\langle{y},{uR}\rangle\in N$
then |
| $N\leftarrow
N\cup\underbrace{\\{\langle{c},{u}\rangle\\}}_{\mathrm{forward}}\cup\underbrace{\\{\langle{c},{w}\rangle\mid\mbox{${\mathsf{NFA}}({q})$
has a backward transition from $w$ to $u$}\\}}_{\mathrm{backward}}.$
Figure 5: Polynomial-time algorithm for computing $\\{\langle{c},{u}\rangle\mid\mathbf{db}\vdash_{q}\langle{c},{u}\rangle\\}$, for a fixed path query $q$ satisfying $\mathcal{C}_{3}$. | Iteration |  Tuples added to $N$
---|---
init. | <0, RRX>, <1, RRX>, <2, RRX>, <3, RRX>, <4, RRX>, <5, RRX>
1 | <4, RR>
2 | <3, R>, <3, RR>
3 | <2, R>, <2, RR>
4 | <1, R>, <1, RR>
5 | <0, R>, <0, RR>, <0, $\varepsilon$>
$0$$1$$2$$3$$4$$5$$R$$R$$R$$R$$R$$R$$R$$X$
Figure 6: Example run of our algorithm for $q=RRX$, on the database instance
$\mathbf{db}$ shown at the right.

Figure 5 shows an algorithm that computes
$\\{\langle{c},{u}\rangle\mid\mathbf{db}\vdash_{q}\langle{c},{u}\rangle\\}$ as
the fixed point of a binary relation $N$. The _Initialization Step_ inserts
into $N$ all pairs $\langle{c},{q}\rangle$, which is correct because
$\mathbf{db}\vdash_{q}\langle{c},{q}\rangle$ holds vacuously, as $q$ is the
accepting state of ${\mathsf{S\mathchar 45\relax NFA}}({q},{q})$. Then, the
_Iterative Rule_ is executed until $N$ remains unchanged; it intrinsically
reflects the constructive proof of Lemma 9:
$\mathbf{db}\vdash_{q}\langle{c},{u}\rangle$ if and only if for every fact
$f=R(\underline{c},d)\in\mathbf{db}$, we have
$uR\in{\mathsf{cqaST}}_{q}({f},{\mathbf{db}})$. Figure 6 shows an example run
of the algorithm in Figure 5. The next lemma states the correctness of the
algorithm.

######  Lemma 10.

Let $q$ be a path query. Let $\mathbf{db}$ be a database instance. Let $N$ be
the output relation returned by the algorithm in Figure 5 on input
$\mathbf{db}$. Then, for every $c\in{\mathsf{adom}}({\mathbf{db}})$ and every
prefix $u$ of $q$,

$\langle{c},{u}\rangle\in N$ if and only if
$\mathbf{db}\vdash_{q}\langle{c},{u}\rangle$.

###### Proof.

$\impliedby$ Proof by contraposition. Assume $\langle{c},{u}\rangle\notin N$.
The proof shows the construction of a repair $\mathbf{r}$ of $\mathbf{db}$
such that $\mathbf{r}$ has no path that starts in $c$ and is accepted by
${\mathsf{S\mathchar 45\relax NFA}}({q},{u})$. Such a repair shows
$\mathbf{db}\not\vdash_{q}\langle{c},{u}\rangle$.

We explain which fact of an arbitrary block $R(\underline{a},*)$ of
$\mathbf{db}$ will be inserted in $\mathbf{r}$. Among all prefixes of $q$ that
end with $R$, let $u_{0}R$ be the longest prefix such that
$\langle{a},{u_{0}}\rangle\notin N$. If such $u_{0}R$ does not exist, then an
arbitrarily picked fact of the block $R(\underline{a},*)$ is inserted in
$\mathbf{r}$. Otherwise, the _Iterative Rule_ in Figure 5 entails the
existence of a fact $R(\underline{a},b)$ such that
$\langle{b},{u_{0}R}\rangle\notin N$. Then, $R(\underline{a},b)$ is inserted
in $\mathbf{r}$. We remark that this repair $\mathbf{r}$ is constructed in
exactly the same way as the repair $\mathbf{r}^{*}$ built in the proof of
Lemma 9.

Assume for the sake of contradiction that there is a path $\pi$ in
$\mathbf{r}$ that starts in $c$ and is accepted by ${\mathsf{S\mathchar
45\relax NFA}}({q},{u})$. Let $\pi\vcentcolon=R_{1}(\underline{c_{0}},c_{1})$,
$R_{2}(\underline{c_{1}},c_{2})$, …, $R_{n}(\underline{c_{n-1}},c_{n})$ where
$c_{0}=c$. Since $\langle{c_{0}},{u}\rangle\not\in N$ and
$\langle{c_{n}},{q}\rangle\in N$, there is a longest prefix $u_{0}$ of $q$,
where $|{u_{0}}|\geq|{u}|$, and $i\in\\{1,\dots,n\\}$ such that
$\langle{c_{i-1}},{u_{0}}\rangle\not\in N$ and
$\langle{c_{i}},{u_{0}R_{i}}\rangle\in N$. From
$\langle{c_{i-1}},{u_{0}}\rangle\not\in N$, it follows that $\mathbf{db}$
contains a fact $R_{i}(\underline{c_{i-1}},d)$ such that
$\langle{d},{u_{0}R_{i}}\rangle\not\in N$. Then
$R_{i}(\underline{c_{i-1}},c_{i})$ would not be chosen in a repair,
contradicting $R_{i}(\underline{c_{i-1}},c_{i})\in\mathbf{r}$.

$\implies$ Assume that $\langle{c},{u}\rangle\in N$. Let $\ell$ be the number
of executions of the _Iterative Rule_ that were used to insert
$\langle{c},{u}\rangle$ in $N$. We show
$\mathbf{db}\vdash_{q}\langle{c},{u}\rangle$ by induction on $\ell$.

The basis of the induction, $\ell=0$, holds because the _Initialization Step_
is obviously correct. Indeed, since $q$ is an accepting state of
${\mathsf{S\mathchar 45\relax NFA}}({q},{q})$, we have
$\mathbf{db}\vdash_{q}\langle{c},{q}\rangle$. For the inductive step,
$\ell\rightarrow\ell+1$, we distinguish two cases.

####  Case that $\langle{c},{u}\rangle$ is added to $N$ by the _forward_ part
of the _Iterative Rule_.

That is, $\langle{c},{u}\rangle$ is added because $\mathbf{db}$ has a block
$\\{R(\underline{c},d_{1})$, …, $R(\underline{c},d_{k})\\}$ with $k\geq 1$ and
for every $i\in\\{1,\dots,k\\}$, we have that $\langle{d_{i}},{uR}\rangle$ was
added to $N$ by a previous execution of the _Iterative Rule_. Let $\mathbf{r}$
be an arbitrary repair of $\mathbf{db}$. Since every repair contains exactly
one fact from each block, we can assume $i\in\\{1,\dots,k\\}$ such that
$R(\underline{c},d_{i})\in\mathbf{r}$. By the induction hypothesis,
$\mathbf{db}\vdash_{q}\langle{d_{i}},{uR}\rangle$ and thus $\mathbf{r}$ has a
path that starts in $d_{i}$ and is accepted by ${\mathsf{S\mathchar 45\relax
NFA}}({q},{uR})$. Clearly, this path can be left extended with
$R(\underline{c},d_{i})$, and this left extended path is accepted by
${\mathsf{S\mathchar 45\relax NFA}}({q},{u})$. Note incidentally that the path
in $\mathbf{r}$ may already use $R(\underline{c},d_{i})$, in which case the
path is cyclic. Since $\mathbf{r}$ is an arbitrary repair, it is correct to
conclude $\mathbf{db}\vdash_{q}\langle{c},{u}\rangle$.

####  Case that $\langle{c},{u}\rangle$ is added to $N$ by the _backward_ part
of the _Iterative Rule_.

Then, there exists a relation name $S$ and words $v,w$ such that $u=vSwS$, and
$\langle{c},{u}\rangle$ is added because $\langle{c},{vS}\rangle$ was added in
the same iteration. Then, ${\mathsf{S\mathchar 45\relax NFA}}({q},{u})$ has an
$\varepsilon$-transition from state $u$ to $vS$. Let $\mathbf{r}$ be an
arbitrary repair of $\mathbf{db}$. By the reasoning in the previous case,
$\mathbf{r}$ has a path that starts in $c$ and is accepted by
${\mathsf{S\mathchar 45\relax NFA}}({q},{vS})$. We claim that $\mathbf{r}$ has
a path that starts in $c$ and is accepted by ${\mathsf{S\mathchar 45\relax
NFA}}({q},{u})$. Indeed, ${\mathsf{S\mathchar 45\relax NFA}}({q},{u})$ can use
the $\varepsilon$-transition to reach the state $vS$, and then behave like
${\mathsf{S\mathchar 45\relax NFA}}({q},{vS})$. This concludes the proof. ∎

The following corollary is now immediate.

######  Corollary 1.

Let $q$ be a path query. Let $\mathbf{db}$ be a database instance, and
$c\in{\mathsf{adom}}({\mathbf{db}})$. Then, the following are equivalent:

  1. 1.

$c\in{\mathsf{start}}({q},{\mathbf{r}})$ for every repair $\mathbf{r}$ of
$\mathbf{db}$; and

  2. 2.

$\langle{c},{\epsilon}\rangle\in N$, where $N$ is the output of the algorithm
in Figure 5.

Finally, we obtain the following tractability result.

$\varphi_{q}(N,x,z):=\left(\begin{array}[]{ll}&\left({\alpha(x)\land
z=\mbox{`$\mathtt{q}$'}}\right)\\\\[4.30554pt]
\lor&\left({\bigvee_{\mathtt{uR}\leq\mathtt{q}}\left({\left({z=\mbox{`$\mathtt{u}$'}}\right)\land\exists
yR(\underline{x},y)\land\forall y\left({R(\underline{x},y)\rightarrow
N(y,\mbox{`$\mathtt{uR}$'})}\right)}\right)}\right)\\\\[4.30554pt]
\lor&\left({\bigvee_{\begin{subarray}{c}\varepsilon<\mathtt{u}<\mathtt{uv}\leq\mathtt{q}\\\
\mathsf{last}({\mathtt{u}})=\mathsf{last}({\mathtt{v}})\end{subarray}}\left({N(x,\mbox{`$\mathtt{u}$'})\land
z=\mbox{`$\mathtt{uv}$'}}\right)}\right)\end{array}\right)$

Figure 7: Definition of $\varphi_{q}(N,x,z)$. The predicate $\alpha(x)$ states
that $x$ is in the active domain, and $<$ is shorthand for _“is a strict
prefix of”._

######  Lemma 11.

For each path query $q$ satisfying $\mathcal{C}_{3}$,
$\mathsf{CERTAINTY}({q})$ is expressible in Least Fixpoint Logic, and hence is
in $\mathbf{PTIME}$.

###### Proof.

For a path query $q$, define the following formula in LFP [33]:

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

where $\varphi_{q}(N,x,z)$ is given in Figure 7. 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}})$. Further, $u\leq v$ means that
$u$ is a prefix of $v$; and $u<v$ means that $u$ is a proper prefix of $v$.
Thus, $u<v$ if and only if $u\leq v$ and $u\neq v$. The formula
$\varphi_{q}(N,x,z)$ is positive in $N$, which is a $2$-ary predicate symbol.
It is understood that the middle disjunction ranges over all nonempty prefixes
$uR$ of $q$ (possibly $u=\varepsilon$). The last disjunction ranges over all
pairs $(u,uv)$ of distinct nonempty prefixes of $q$ that agree on their last
symbol. We used a different typesetting to distinguish the constant words
$\mathtt{q}$, $\mathtt{uR}$, $\mathtt{uv}$ from first-order variables $x$,
$z$. It is easily verified that the LFP query (2) expresses the algorithm of
Figure 5. ∎

Since the formula (2) in the proof of Lemma 11 uses universal quantification,
it is not in Existential Least Fixpoint Logic, which is equal to
$\mathsf{DATALOG}_{\neg}$ [33, Theorem 10.18].

###  6.2 $\mathbf{FO}$-Rewritability for $\mathcal{C}_{1}$

We now show that if a path query $q$ satisfies $\mathcal{C}_{1}$, then
$\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$, and a first-order rewriting for
$q$ can be effectively constructed.

######  Definition 11 (First-order rewriting).

If $q$ is a Boolean query such that $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{FO}$, then a _(consistent) first-order rewriting_ for $q$ is a first-
order sentence $\psi$ such that for every database instance $\mathbf{db}$, the
following are equivalent:

  1. 1.

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

  2. 2.

$\mathbf{db}$ satisfies $\psi$. ∎

######  Definition 12.

If $q=\\{R_{1}(\underline{x_{1}},x_{2})$, $R_{2}(\underline{x_{2}},x_{3})$, …,
$R_{k}(\underline{x_{k}},x_{k+1})\\}$, $k\geq 1$, and $c$ is a constant, then
${q}_{[c]}$ is the Boolean conjunctive query
${q}_{[c]}\vcentcolon=\\{R_{1}(\underline{c},x_{2}),R_{2}(\underline{x_{2}},x_{3}),\dots,R_{k}(\underline{x_{k}},x_{k+1})\\}$.
∎

######  Lemma 12.

For every nonempty path query $q$ and constant $c$, the problem
$\mathsf{CERTAINTY}({{q}_{[c]}})$ is in $\mathbf{FO}$. Moreover, it is
possible to construct a first-order formula $\psi(x)$, with free variable $x$,
such that for every constant $c$, the sentence $\exists x\left({\psi(x)\land
x=c}\right)$ is a first-order rewriting for ${q}_{[c]}$.

###### Proof.

The proof inductively constructs a first-order rewriting for ${q}_{[c]}$,
where the induction is on the number $n$ of atoms in $q$. For the basis of the
induction, $n=1$, we have ${q}_{[c]}=R(\underline{c},y)$. Then, the first-
order formula $\psi(x)=\exists yR(\underline{x},y)$ obviously satisfies the
statement of the lemma.

We next show the induction step, $n\rightarrow n+1$. Let
$R(\underline{x_{1}},x_{2})$ be the left-most atom of $q$, and assume that
$p\vcentcolon=q\setminus\\{R(\underline{x_{1}},x_{2})\\}$ is a path query with
$n\geq 1$ atoms. By the induction hypothesis, it is possible to construct a
first-order formula $\varphi(z)$, with free variable $z$, such that for every
constant $d$,

$\exists z\left({\varphi(z)\land z=d}\right)$ is a first-order rewriting for
${p}_{[d]}$. (3)

We now define $\psi(x)$ as follows:

$\psi(x)=\exists y\left({R(\underline{x},y)}\right)\land\forall
z\left({R(\underline{x},z)\rightarrow\varphi(z)}\right).$ (4)

We will show that for every constant $c$, $\exists x\left({\psi(x)\land
x=c}\right)$ is a first-order rewriting for ${q}_{[c]}$. To this end, let
$\mathbf{db}$ be a database instance. It remains to be shown that
$\mathbf{db}$ is a “yes”-instance of $\mathsf{CERTAINTY}({{q}_{[c]}})$ if and
only if $\mathbf{db}$ satisfies $\exists x\left({\psi(x)\land x=c}\right)$.

$\impliedby$ Assume $\mathbf{db}$ satisfies $\exists x\left({\psi(x)\land
x=c}\right)$. Because of the conjunct $\exists
y\left({R(\underline{x},y)}\right)$ in (4), we have that $\mathbf{db}$
includes a block $R(\underline{c},*)$. Let $\mathbf{r}$ be a repair of
$\mathbf{db}$. We need to show that $\mathbf{r}$ satisfies ${q}_{[c]}$.
Clearly, $\mathbf{r}$ contains $R(\underline{c},d)$ for some constant $d$.
Since $\mathbf{db}$ satisfies $\exists z\left({\varphi(z)\land z=d}\right)$,
the induction hypothesis (3) tells us that $\mathbf{r}$ satisfies ${p}_{[d]}$.
It is then obvious that $\mathbf{r}$ satisfies ${q}_{[c]}$.

$\implies$ Assume $\mathbf{db}$ is a “yes”-instance for
$\mathsf{CERTAINTY}({{q}_{[c]}})$. Then $\mathbf{db}$ must obviously satisfy
$\exists y\left({R(\underline{c},y)}\right)$. Therefore, $\mathbf{db}$
includes a block $R(\underline{c},*)$. Let $\mathbf{r}$ be an arbitrary repair
of $\mathbf{db}$. There exists $d$ such that
$R(\underline{c},d)\in\mathbf{r}$. Since $\mathbf{r}$ satisfies ${q}_{[c]}$,
it follows that $\mathbf{r}$ satisfies ${p}_{[d]}$. Since $\mathbf{r}$ is an
arbitrary repair, the induction hypothesis (3) tells us that $\mathbf{db}$
satisfies $\exists z\left({\varphi(z)\land z=d}\right)$. It is then clear that
$\mathbf{db}$ satisfies $\exists x\left({\psi(x)\land x=c}\right)$. ∎

######  Lemma 13.

For every path query $q$ that satisfies $\mathcal{C}_{1}$, the problem
$\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$, and a first-order rewriting for
$q$ can be effectively constructed.

###### Proof.

By Lemmas 5 and 7, a database instance $\mathbf{db}$ is a “yes”-instance for
$\mathsf{CERTAINTY}({q})$ if and only if there is a constant $c$ (which
depends on $\mathbf{db}$) such that $\mathbf{db}$ is a “yes”-instance for
$\mathsf{CERTAINTY}({{q}_{[c]}})$. By Lemma 12, it is possible to construct a
first-order rewriting $\exists x\left({\psi(x)\land x=c}\right)$ for
${q}_{[c]}$. It is then clear that $\exists x\left({\psi(x)}\right)$ is a
first-order rewriting for $q$. ∎

###  6.3 An $\mathbf{NL}$ Algorithm for $\mathcal{C}_{2}$

We show that $\mathsf{CERTAINTY}({q})$ is in $\mathbf{NL}$ if $q$ satisfies
$\mathcal{C}_{2}$ by expressing it in linear Datalog with stratified negation.
The proof will use the syntactic characterization of $\mathcal{C}_{2}$
established in Lemma 3.

######  Lemma 14.

For every path query $q$ that satisfies $\mathcal{C}_{2}$, the problem
$\mathsf{CERTAINTY}({q})$ is in linear Datalog with stratified negation (and
hence in $\mathbf{NL}$).

In the remainder of this section, we develop the proof of Lemma 14.

######  Definition 13.

Let $q$ be a path query. We define ${\mathsf{NFA^{\min}}}({q})$ as the
automaton that accepts $w$ if $w$ is accepted by ${\mathsf{NFA}}({q})$ and no
proper prefix of $w$ is accepted by ${\mathsf{NFA}}({q})$. ∎

It is well-known that such an automaton ${\mathsf{NFA^{\min}}}({q})$ exists.

######  Example 6.

Let $q=RXRYR$. Then, $RXRYRYR$ is accepted by ${\mathsf{NFA}}({q})$, but not
by ${\mathsf{NFA^{\min}}}({q})$, because the proper prefix $RXRYR$ is also
accepted by ${\mathsf{NFA}}({q})$. ∎

######  Definition 14.

Let $q$ be a path query and $\mathbf{r}$ be a consistent database instance. We
define ${\mathsf{start^{\min}}}({q},{\mathbf{r}})$ as the set containing all
(and only) constants $c\in{\mathsf{adom}}({\mathbf{r}})$ such that there is a
path in $\mathbf{r}$ that starts in $c$ and is accepted by
${\mathsf{NFA^{\min}}}({q})$. ∎

######  Lemma 15.

Let $q$ be a path query. For every consistent database instance $\mathbf{r}$,
we have that
${\mathsf{start}}({q},{\mathbf{r}})={\mathsf{start^{\min}}}({q},{\mathbf{r}})$.

###### Proof.

By construction,
${\mathsf{start^{\min}}}({q},{\mathbf{r}})\subseteq{\mathsf{start}}({q},{\mathbf{r}})$.
Next assume that $c\in{\mathsf{start}}({q},{\mathbf{r}})$ and let $\pi$ be the
path that starts in $c$ and is accepted by ${\mathsf{NFA}}({q})$. Let
$\pi^{-}$ be the shortest prefix of $\pi$ that is accepted by
${\mathsf{NFA}}({q})$. Since $\pi^{-}$ starts in $c$ and is accepted by
${\mathsf{NFA^{\min}}}({q})$, it follows
$c\in{\mathsf{start^{\min}}}({q},{\mathbf{r}})$. ∎

######  Lemma 16.

Let $u\cdot v\cdot w$ be a self-join-free word over the alphabet of relation
names. Let $s$ be a suffix of $uv$ that is distinct from $uv$. For every
integer $k\geq 0$, ${\mathsf{NFA^{\min}}}({s\left({uv}\right)^{k}wv})$ accepts
the language of the regular expression
$s\left({uv}\right)^{k}\left({uv}\right)^{*}wv$.

###### Proof.

Let $q=s\left({uv}\right)^{k}wv$. Since $u\cdot v\cdot w$ is self-join-free,
applying the rewinding operation, zero, one, or more times, in the part of $q$
that precedes $w$ will repeat the factor $uv$. This gives words of the form
$s\left({uv}\right)^{\ell}wv$ with $\ell\geq k$. The difficult case is where
we rewind a factor of $q$ that itself contains $w$ as a factor. In this case,
the rewinding operation will repeat a factor of the form
$v_{2}\left({uv}\right)^{\ell}wv_{1}$ such that $v=v_{1}v_{2}$ and
$v_{2}\neq\varepsilon$, which results in words of one of the following forms
($s=s_{1}\cdot v_{2}$):

$\begin{array}[]{l}\mbox{${\left({s\left({uv}\right)^{\ell_{1}}uv_{1}}\right)}\\!\cdot\\!{v_{2}\left({uv}\right)^{\ell_{2}}wv_{1}}\\!\cdot\\!\underline{v_{2}\left({uv}\right)^{\ell_{2}}wv_{1}}\\!\cdot\\!{\left({v_{2}}\right)}$};\mbox{\
or}\\\
\mbox{${\left({s_{1}}\right)}\\!\cdot\\!{v_{2}\left({uv}\right)^{\ell}wv_{1}}\\!\cdot\\!\underline{v_{2}\left({uv}\right)^{\ell}wv_{1}}\\!\cdot\\!{\left({v_{2}}\right)}$}.\end{array}$

These words have a prefix belonging to the language of the regular expression
$s\left({uv}\right)^{k}\left({uv}\right)^{*}wv$. ∎

######  Definition 15.

Let $\mathbf{db}$ be a database instance, and $q$ a path query.

For $a,b\in{\mathsf{adom}}({\mathbf{db}})$, we write $\mathbf{db}\models
a\stackrel{{\scriptstyle q}}{{\longrightarrow}}b$ if there exists a path in
$\mathbf{db}$ from $a$ to $b$ with trace $q$. Even more formally,
$\mathbf{db}\models a\stackrel{{\scriptstyle q}}{{\longrightarrow}}b$ if
$\mathbf{db}$ contains facts
$R_{1}(\underline{a_{1}},a_{2}),R_{2}(\underline{a_{2}},a_{3}),\ldots,R_{|{q}|}(\underline{a_{|{q}|}},a_{|{q}|+1})$
such that $R_{1}R_{2}\dotsm R_{|{q}|}=q$. We write $\mathbf{db}\models
a\stackrel{{\scriptstyle q_{1}}}{{\longrightarrow}}b\stackrel{{\scriptstyle
q_{2}}}{{\longrightarrow}}c$ as a shorthand for $\mathbf{db}\models
a\stackrel{{\scriptstyle q_{1}}}{{\longrightarrow}}b$ and $\mathbf{db}\models
b\stackrel{{\scriptstyle q_{2}}}{{\longrightarrow}}c$.

We write $\mathbf{db}\models a\stackrel{{\scriptstyle
q}}{{\longrightarrow\\!\\!\\!\\!\\!\\!\\!\\!\longrightarrow}}b$ if there
exists a _consistent path_ in $\mathbf{db}$ from $a$ to $b$ with trace $q$,
where a path is called consistent if it does not contain two distinct key-
equal facts.

A constant $c\in{\mathsf{adom}}({\mathbf{db}})$ is called _terminal for $q$ in
$\mathbf{db}$_ if for some (possibly empty) proper prefix $p$ of $q$, there is
a consistent path in $\mathbf{db}$ with trace $p$ that cannot be right
extended to a consistent path in $\mathbf{db}$ with trace $q$. ∎

Note that for every $c\in{\mathsf{adom}}({\mathbf{db}})$, we have
$c\stackrel{{\scriptstyle\varepsilon}}{{\longrightarrow\\!\\!\\!\\!\\!\\!\\!\\!\longrightarrow}}c$.
Clearly, if $q$ is self-join-free, then $c\stackrel{{\scriptstyle
q}}{{\longrightarrow}}d$ implies $c\stackrel{{\scriptstyle
q}}{{\longrightarrow\\!\\!\\!\\!\\!\\!\\!\\!\longrightarrow}}d$ (the converse
implication holds vacuously true).

######  Example 7.

Let
$\mathbf{db}=\\{R(\underline{c},d),S(\underline{d},c),R(\underline{c},e),T(\underline{e},f)\\}$.
Then, $c$ is terminal for $RSRT$ in $\mathbf{db}$ because the path
$R(\underline{c},d),S(\underline{d},c)$ cannot be right extended to a
consistent path with trace $RSRT$, because $d$ has no outgoing $T$-edge. Note
incidentally that $\mathbf{db}\models c\stackrel{{\scriptstyle
RS}}{{\longrightarrow\\!\\!\\!\\!\\!\\!\\!\\!\longrightarrow}}c\stackrel{{\scriptstyle
RT}}{{\longrightarrow\\!\\!\\!\\!\\!\\!\\!\\!\longrightarrow}}f$, but
$\mathbf{db}\not\models c\stackrel{{\scriptstyle
RSRT}}{{\longrightarrow\\!\\!\\!\\!\\!\\!\\!\\!\longrightarrow}}f$. ∎

######  Lemma 17.

Let $\mathbf{db}$ be a database instance, and
$c\in{\mathsf{adom}}({\mathbf{db}})$. Let $q$ be a path query. Then, $c$ is
terminal for $q$ in $\mathbf{db}$ if and only if $\mathbf{db}$ is a
“no”-instance of $\mathsf{CERTAINTY}({{q}_{[c]}})$, with ${q}_{[c]}$ as
defined by Definition 12.

###### Proof.

$\implies$ Straightforward. $\impliedby$ Assume $\mathbf{db}$ is a
“no”-instance of $\mathsf{CERTAINTY}({{q}_{[c]}})$. Then, there is a repair
$\mathbf{r}$ of $\mathbf{db}$ such that $\mathbf{r}\not\models{q}_{[c]}$. The
empty path is a path in $\mathbf{r}$ that starts in $c$ and has trace
$\varepsilon$, which is a prefix of $q$. We can therefore assume a longest
prefix $p$ of $q$ such there exists a path $\pi$ in $\mathbf{r}$ that starts
in $c$ and has trace $p$. Since $\mathbf{r}$ is consistent, $\pi$ is
consistent. From $\mathbf{r}\not\models{q}_{[c]}$, it follows that $p$ is a
proper prefix of $q$. By Definition 15, $c$ is terminal for $q$ in
$\mathbf{db}$. ∎

We can now give the proof of Lemma 14.

###### Proof of Lemma 14.

Assume $q$ satisfies $\mathcal{C}_{2}$. By Lemma 3, $q$ satisfies
$\mathcal{B}_{2a}$ or $\mathcal{B}_{2b}$. We treat the case that $q$ satisfies
$\mathcal{B}_{2b}$ (the case that $q$ satisfies $\mathcal{B}_{2a}$ is even
easier). We have that $q$ is a factor of $\left({uv}\right)^{k}wv$, where $k$
is chosen as small as possible, and $uvw$ is self-join-free. The proof is
straightforward if $k=0$; we assume $k\geq 1$ from here on. To simplify
notation, we will show the case where $q$ is a suffix of
$\left({uv}\right)^{k}wv$; our proof can be easily extended to the case where
$q$ is not a suffix, at the price of some extra notation. There is a suffix
$s$ of $uv$ such that $q=s\left({uv}\right)^{k-1}wv$.

We first define a unary predicate $P$ (which depends on $q$) such that
$\mathbf{db}\models P(d)$ if for some $\ell\geq 0$, there are constants
$d_{0},d_{1},\ldots,d_{\ell}\in{\mathsf{adom}}({\mathbf{db}})$ with $d_{0}=d$
such that:

  1. (i)

$\mathbf{db}\models d_{0}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{1}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{2}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}\dotsm\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{\ell}$;

  2. (ii)

for every $i\in\\{0,1,\ldots,\ell\\}$, $d_{i}$ is terminal for $wv$ in
$\mathbf{db}$; and

  3. (iii)

either $d_{\ell}$ is terminal for $uv$ in $\mathbf{db}$, or
$d_{\ell}\in\\{d_{0},\ldots,d_{\ell-1}\\}$.

######  Claim 2.

The definition of the predicate $P$ does not change if we replace item (i) by
the stronger requirement that for every $i\in\\{0,1,\ldots,\ell-1\\}$, there
exists a path $\pi_{i}$ from $d_{i}$ to $d_{i+1}$ with trace $uv$ such that
the composed path $\pi_{0}\cdot\pi_{1}\cdots\pi_{\ell-1}$ is consistent.

###### Proof.

It suffices to show the following statement by induction on increasing $l$:

> whenever there exist $l\geq 1$ and constants $d_{0},d_{1},\dots,d_{l}$ with
> $d_{0}=d$ such that conditions (i), (ii), and (iii) hold, there exist
> another constant $k\geq 1$ and constants $c_{0},c_{1},\dots,c_{k}$ with
> $c_{0}=d$ such that conditions (i), (ii), and (iii) hold, and, moreover, for
> each $i\in\\{0,1,\dots,k-1\\}$, there exists a path $\pi_{i}$ from $c_{i}$
> to $c_{i+1}$ such that the composed path
> $\pi_{0}\cdot\pi_{1}\cdots\pi_{k-1}$ is consistent.

Basis $l=1$.

Then we have $\mathbf{db}\models d_{0}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{1}$, witnessed by a path $\pi_{0}$. Since $uv$ is
self-join-free, the path $\pi_{0}$ is consistent. The claim thus follows with
$k=l=1$, $c_{0}=d_{0}$ and $c_{1}=d_{1}$.

Inductive step $l\rightarrow l+1$.

Assume that the statement holds for any integer in $\\{1,2,\ldots,l\\}$.
Suppose that there exist $l\geq 2$ and constants $d_{0},d_{1},\dots,d_{l+1}$
with $d_{0}=d$ such that conditions (i), (ii), and (iii) hold.

For $i\in\\{0,\ldots,l\\}$, let $\pi_{i}$ be a path with trace $uv$ from
$d_{i}$ to $d_{i+1}$ in $\mathbf{db}$. The claim holds if the composed path
$\pi_{0}\cdot\pi_{1}\cdots\pi_{l}$ is consistent, with $k=l+1$ and
$c_{i}=d_{i}$ for $i\in\\{0,1,\dots,l+1\\}$.

Now, assume that for some $i<j$, the paths that show $\mathbf{db}\models
d_{i}\stackrel{{\scriptstyle uv}}{{\longrightarrow}}d_{i+1}$ and
$\mathbf{db}\models d_{j}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{j+1}$ contain, respectively,
$R(\underline{a},b_{1})$ and $R(\underline{a},b_{2})$ with $b_{1}\neq b_{2}$.
It is easily verified that

$\mathbf{db}\models d_{0}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{1}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{2}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}\dotsm\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{i}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{j+1}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}\dotsm\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{l+1},$

where the number of $uv$-steps is strictly less than $l+1$. Informally, we
follow the original path until we reach $R(\underline{a},b_{1})$, but then
follow $R(\underline{a},b_{2})$ instead of $R(\underline{a},b_{1})$, and
continue on the path that proves $\mathbf{db}\models
d_{j}\stackrel{{\scriptstyle uv}}{{\longrightarrow}}d_{j+1}$. Then the claim
holds by applying the inductive hypothesis on constants
$d_{0},d_{1},\ldots,d_{i},d_{j+1},\ldots,d_{l+1}$.

The proof is now complete. ∎

Since we care about the expressibility of the predicate $P$ in Datalog, Claim
2 is not cooked into the definition of $P$. The idea is the same as in an
$\mathbf{NL}$-algorithm for reachability: if there exists a directed path from
$s$ to $t$, then there is such a path without repeated vertices; but we do not
care for repeated vertices when computing reachability.

######  Claim 3.

The definition of predicate $P$ does not change if we require that for
$i\in\\{0,1,\ldots,\ell-1\\}$, $d_{i}$ is not terminal for $uv$ in
$\mathbf{db}$.

###### Proof.

Assume that for some $0\leq i<\ell$, $d_{i}$ is terminal for $uv$ in
$\mathbf{db}$. Then, all conditions in the definition are satisfied by
choosing $\ell$ equal to $j$. ∎

Claim 3 is not cooked into the definition of $P$ to simplify the the encoding
of $P$ in Datalog.

Next, we define a unary predicate $O$ such that $\mathbf{db}\models O(c)$ for
a constant $c$ if $c\in{\mathsf{adom}}({\mathbf{db}})$ and one of the
following holds true:

  1. 1.

$c$ is terminal for $s\left({uv}\right)^{k-1}$ in $\mathbf{db}$; or

  2. 2.

there is a constant $d\in{\mathsf{adom}}({\mathbf{db}})$ such that both
$\mathbf{db}\models c\stackrel{{\scriptstyle
s\left({uv}\right)^{k-1}}}{{\xrightarrow{\hskip
30.0pt}\\!\\!\\!\\!\\!\\!\\!\\!\longrightarrow}}d$ and $\mathbf{db}\models
P(d)$.

######  Claim 4.

Let $c\in{\mathsf{adom}}({\mathbf{db}})$. The following are equivalent:

  1. (I)

there is a repair $\mathbf{r}$ of $\mathbf{db}$ that contains no path that
starts in $c$ and whose trace is in the language of the regular expression
$s\left({uv}\right)^{k-1}\left({uv}\right)^{*}wv$; and

  2. (II)

$\mathbf{db}\models O(c)$.

###### Proof.

Let $wv=S_{0}S_{1}\dotsm S_{m-1}$ and $uv=R_{0}R_{1}\dotsm R_{n-1}$.

(I)$\implies$(II) Assume that item (I) holds true. Let the first relation name
of $s$ be $R_{i}$. Starting from $c$, let $\pi$ be a maximal (possibly
infinite) path in $\mathbf{r}$ that starts in $c$ and has trace
$R_{i}R_{i+1}R_{i+2}\dotsm$, where addition is modulo $n$. Since $\mathbf{r}$
is consistent, $\pi$ is deterministic. Since $\mathbf{r}$ is finite, $\pi$
contains only finitely many distinct edges. Therefore, $\pi$ ends either in a
loop or in an edge $R_{j}(\underline{d},e)$ such that
$\mathbf{db}\models\neg\exists yR_{j+1}(\underline{e},y)$ (recall that
$\mathbf{r}$ contains a fact from every block of $\mathbf{db}$). Assume that
$\pi$ has a prefix $\pi^{\prime}$ with trace $s\left({uv}\right)^{k-1}$; if
$e$ occurs at the non-primary key position of the last $R_{n-1}$-fact of
$\pi^{\prime}$ or of any $R_{n-1}$-fact occurring afterwards in $\pi$, then it
follows from item (I) that there exist a (possibly empty) prefix $pS_{j}$ of
$wv$ and a constant $f\in{\mathsf{adom}}({\mathbf{r}})$ such that
$\mathbf{r}\models e\stackrel{{\scriptstyle p}}{{\longrightarrow}}f$ and
$\mathbf{db}\models\neg\exists yS_{j}(\underline{f},y)$. It is now easily
verified that $\mathbf{db}\models O(c)$.

(II)$\implies$(I) Assume $\mathbf{db}\models O(c)$. It is easily verified that
the desired result holds true if $c$ is terminal for
$s\left({uv}\right)^{k-1}$ in $\mathbf{db}$. Assume from here on that $c$ is
not terminal for $s\left({uv}\right)^{k-1}$ in $\mathbf{db}$. That is, for
every repair $\mathbf{r}$ of $\mathbf{db}$, there is a constant $d$ such that
$\mathbf{r}\models c\stackrel{{\scriptstyle
s\left({uv}\right)^{k-1}}}{{\xrightarrow{\hskip 30.0pt}}}d$. Then, there is a
consistent path $\alpha$ with trace $s\left({uv}\right)^{k-1}$ from $c$ to
some constant $d\in{\mathsf{adom}}({\mathbf{db}})$ such that
$\mathbf{db}\models P(d)$, using the stronger definition of $P$ implied by
Claims 2 and 3. Let $d_{0},\ldots,d_{\ell}$ be as in our (stronger) definition
of $P(d)$, that is, first, $d_{1},\ldots,d_{\ell-1}$ are not terminal for $uv$
in $\mathbf{db}$ (cf. Claim 3), and second, there is a $\subseteq$-minimal
consistent subset $\pi$ of $\mathbf{db}$ such that $\pi\models
d_{0}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{1}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{2}\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}\dotsm\stackrel{{\scriptstyle
uv}}{{\longrightarrow}}d_{\ell}$ (cf. Claim 2). We construct a repair
$\mathbf{r}$ as follows:

  1. 1.

insert into $\mathbf{r}$ all facts of $\pi$;

  2. 2.

for every $i\in\\{0,\ldots,\ell\\}$, $d_{i}$ is terminal for $wv$ in
$\mathbf{db}$. We ensure that $\mathbf{r}\models d_{i}\stackrel{{\scriptstyle
S_{0}S_{1}\dotsm S_{j_{i}}}}{{\xrightarrow{\hskip 30.0pt}}}e_{i}$ for some
$j_{i}\in\\{0,\ldots,m-2\\}$ and some constant $e_{i}$ such that
$\mathbf{db}\models\neg\exists yS_{j_{i}+1}(\underline{e_{i}},y)$;

  3. 3.

if $d_{\ell}$ is terminal for $uv$ in $\mathbf{db}$, then we ensure that
$\mathbf{r}\models d_{\ell}\stackrel{{\scriptstyle R_{0}R_{1}\dotsm
R_{j}}}{{\xrightarrow{\hskip 30.0pt}}}e$ for some $j\in\\{0,\ldots,n-2\\}$ and
some constant $e$ such that $\mathbf{db}\models\neg\exists
yS_{j+1}(\underline{e},y)$;

  4. 4.

insert into $\mathbf{r}$ the facts of $\alpha$ that are not key-equal to a
fact already in $\mathbf{r}$; and

  5. 5.

complete $\mathbf{r}$ into a $\subseteq$-maximal consistent subset of
$\mathbf{db}$.

Since $\mathbf{r}$ is a repair of $\mathbf{db}$, there exists a path $\delta$
with trace $s\left({uv}\right)^{k-1}$ in $\mathbf{r}$ that starts from $c$. If
$\delta\neq\alpha$, then $\delta$ must contain a fact of $\pi$ that was
inserted in step 1. Consequently, no matter whether $\delta=\alpha$ or
$\delta\neq\alpha$, the endpoint of $\delta$ belongs to
$\\{d_{0},\ldots,d_{\ell}\\}$. It follows that there is a (possibly empty)
path from $\delta$’s endpoint to $d_{\ell}$ whose trace is of the form
$\left({uv}\right)^{*}$. Two cases can occur:

  * •

$d_{\ell}$ is terminal for $uv$ in $\mathbf{db}$.

  * •

$d_{\ell}$ is not terminal for $uv$ in $\mathbf{db}$. Then there is
$j\in\\{0,\ldots,\ell-1\\}$ such that $d_{j}=d_{\ell}$. Then, there is a path
of the form $\left({uv}\right)^{*}$ that starts from $\delta$’s endpoint and
eventually loops.

Since, by construction, each $d_{i}$ is terminal for $wv$ in $\mathbf{r}$, it
will be the case that $\delta$ cannot be extended to a path in $\mathbf{r}$
whose trace is of the form $s\left({uv}\right)^{k}\left({uv}\right)^{*}wv$. ∎

######  Claim 5.

The unary predicate $O$ is expressible in linear Datalog with stratified
negation.

###### Proof.

The construction of the linear Datalog program is straightforward. Concerning
the computation of predicates $P$ and $O$, note that it can be checked in
$\mathbf{FO}$ whether or not a constant $c$ is terminal for some path query
$q$, by Lemmas 12 and 17. The only need for recursion comes from condition (i)
in the definition of the predicate $P$, which searches for a directed path of
a particular form. We give a program for $q=UVUVWV$, where $\mathtt{c(X)}$
states that $\mathtt{X}$ is a constant, and $\mathtt{ukey(X)}$ states that
$\mathtt{X}$ is the primary key of some $U$-fact.
$\mathtt{consistent(X1,X2,X3,X4)}$ is true if either $\mathtt{X1\neq X3}$ or
$\mathtt{X2=X4}$ (or both).

>
>     uvterminal(X) :- c(X), not ukey(X).
>     uvterminal(X) :- u(X,Y), not vkey(Y).
>     wvterminal(X) :- c(X), not wkey(X).
>     wvterminal(X) :- w(X,Y), not vkey(Y).
>
>     uv2terminal(X) :- uvterminal(X).
>     uv2terminal(X1) :- u(X1,X2), v(X2,X3), uvterminal(X3).
>
>     uvpath(X1,X3) :- u(X1,X2), v(X2,X3), wvterminal(X1), wvterminal(X2),
> wvterminal(X3).
>     uvpath(X1,X4) :- uvpath(X1,X2), u(X2,X3), v(X3,X4), wvterminal(X3),
> wvterminal(X4).
>
>     p(X) :- uvterminal(X), wvterminal(X). %%% the empty path.
>     p(X) :- uvpath(X,Y), uvterminal(Y).
>     p(X) :- uvpath(X,Y), uvpath(Y,Y). %%% p and uvpath are not mutually
> recursive.
>
>     o(X) :- uv2terminal(X).
>     o(X1) :- u(X1,X2), v(X2,X3), u(X3,X4), v(X4,X5),
> consistent(X1,X2,X3,X4), consistent(X2,X3,X4,X5), p(X5).
>

The above program is in linear Datalog with stratified negation. It is easily
seen that any path query satisfying $\mathcal{B}_{2b}$ admits such a program
for the predicate $O$. ∎

By Lemmas 7, 15, and 16, the following are equivalent:

  1. (a)

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

  2. (b)

for every constant $c_{i}\in{\mathsf{adom}}({q})$, there is a repair
$\mathbf{r}$ of $\mathbf{db}$ that contains no path that starts in $c_{i}$ and
whose trace is in the language of the regular expression
$s\left({uv}\right)^{k-1}\left({uv}\right)^{*}wv$.

By Claim 4, item (b) holds true if and only if for every
$c\in{\mathsf{adom}}({\mathbf{db}})$, $\mathbf{db}\models\neg O(c)$. It
follows from Claim 5 that the latter test is in linear Datalog with stratified
negation, which concludes the proof of Lemma 14. ∎

##  7 Complexity Lower Bounds

In this section, we show the complexity lower bounds of Theorem 3. For a path
query $q=\\{R_{1}(x_{1},x_{2})$, …, $R_{k}(x_{k},x_{k+1})\\}$ and constants
$a,b$, we define the following database instances:

$\displaystyle\phi_{a}^{b}[q]$ $\displaystyle\vcentcolon=$
$\displaystyle\\{R_{1}(a,\Box_{2}),R_{2}(\Box_{2},\Box_{3}),\dots,R_{k}(\Box_{k},b)\\}$
$\displaystyle\phi_{a}^{\bot}[q]$ $\displaystyle\vcentcolon=$
$\displaystyle\\{R_{1}(a,\Box_{2}),R_{2}(\Box_{2},\Box_{3}),\dots,R_{k}(\Box_{k},\Box_{k+1})\\}$
$\displaystyle\phi_{\bot}^{b}[q]$ $\displaystyle\vcentcolon=$
$\displaystyle\\{R_{1}(\Box_{1},\Box_{2}),R_{2}(\Box_{2},\Box_{3}),\dots,R_{k}(\Box_{k},b)\\}$

where the symbols $\Box_{i}$ denoted fresh constants not occurring elsewhere.
Significantly, two occurrences of $\Box_{i}$ will represent different
constants.

###  7.1 $\mathbf{NL}$-Hardness

We first show that if a path query violates $\mathcal{C}_{1}$, then
$\mathsf{CERTAINTY}({q})$ is $\mathbf{NL}$-hard, and therefore not in
$\mathbf{FO}$.

######  Lemma 18.

If a path query $q$ violates $\mathcal{C}_{1}$, then $\mathsf{CERTAINTY}({q})$
is $\mathbf{NL}$-hard.

###### Proof.

Assume that $q$ does not satisfy $\mathcal{C}_{1}$. Then, there exists a
relation name $R$ such that $q=uRvRw$ and $q$ is not a prefix of $uRvRvRw$. It
follows that $Rw$ is not a prefix of $RvRw$. Since $Rv\neq\varepsilon$, there
exists no (conjunctive query) homomorphism from $q$ to $uRw$.

The problem $\mathsf{REACHABILITY}$ takes as input a directed graph $G(V,E)$
and two vertices $s,t\in V$, and asks whether $G$ has a directed path from $s$
to $t$. This problem is $\mathbf{NL}$-complete and remains
$\mathbf{NL}$-complete when the inputs are acyclic graphs. Recall that
$\mathbf{NL}$ is closed under complement. We present a first-order reduction
from $\mathsf{REACHABILITY}$ to the complement of $\mathsf{CERTAINTY}({q})$,
for acyclic directed graphs.

Let $G=(V,E)$ be an acyclic directed graph and $s,t\in V$. Let
$G^{\prime}=(V\cup\\{s^{\prime},t^{\prime}\\},E\cup\\{(s^{\prime},s),(t,t^{\prime})\\})$,
where $s^{\prime},t^{\prime}$ are fresh vertices. We construct an input
instance $\mathbf{db}$ for $\mathsf{CERTAINTY}({q})$ as follows:

  * •

for each vertex $x\in V\cup\\{s^{\prime}\\}$, we add $\phi_{\bot}^{x}[u]$;

  * •

for each edge $(x,y)\in E\cup\\{(s^{\prime},s),(t,t^{\prime})\\}$, we add
$\phi_{x}^{y}[Rv]$; and

  * •

for each vertex $x\in V$, we add $\phi^{\bot}_{x}[Rw]$.

This construction can be executed in $\mathbf{FO}$. Figure 8 shows an example
of the above construction. Observe that the only conflicts in $\mathbf{db}$
occur in $R$-facts outgoing from a same vertex.

$s^{\prime}$$s$$a$$t$$t^{\prime}$$u$$u$$u$$u$$Rw$$Rw$$Rw$$Rv$$Rv$$Rv$$Rv$
Figure 8: Database instance for the $\mathbf{NL}$-hardness reduction from the
graph $G$ with $V=\\{s,a,t\\}$ and $E=\\{(s,a),(a,t)\\}$.

We now show that there exists a directed path from $s$ to $t$ in $G$ if and
only if there exists a repair of $\mathbf{db}$ that does not satisfy $q$.

$\implies$ Suppose that there is a directed path from $s$ to $t$ in $G$. Then,
$G^{\prime}$ has a directed path $P=s,x_{0},x_{1},\dots,t,t^{\prime}$. Then,
consider the repair $\mathbf{r}$ that chooses the first $R$-fact from
$\phi_{x}^{y}[Rv]$ for each edge $(x,y)$ on the path $P$, and the first
$R$-fact from $\phi_{y}^{\bot}[Rw]$ for each $y$ not on the path $P$. We show
that $\mathbf{r}$ falsifies $q$. Assume for the sake of contradiction that
$\mathbf{r}$ satisfies $q$. Then, there exists a valuation $\theta$ for the
variables in $q$ such that $\theta(q)\subseteq\mathbf{r}$. Since, as argued in
the beginning of this proof, there exists no (conjunctive query) homomorphism
from $q$ to $uRw$, it must be that all facts in $\theta(q)$ belong to a path
in $\mathbf{r}$ with trace $u\left({Rv}\right)^{k}$, for some $k\geq 0$.
Since, by construction, no constants are repeated on such paths, there exists
a (conjunctive query) homomorphism from $q$ to $u\left({Rv}\right)^{k}$, which
implies that $Rw$ is a prefix of $RvRw$, a contradiction. We conclude by
contradiction that $\mathbf{r}$ falsifies $q$.

$\impliedby$ Proof by contradiction. Suppose that there is no directed path
from $s$ to $t$ in $G$. Let $\mathbf{r}$ be any repair of $\mathbf{db}$; we
will show that $\mathbf{r}$ satisfies $q$. Indeed, there exists a maximal path
$P=x_{0},x_{1},\dots,x_{n}$ such that $x_{0}=s^{\prime}$, $x_{1}=s$, and
$\phi_{x_{i}}^{x_{i+1}}[Rv]\subseteq\mathbf{r}$. By construction, $s^{\prime}$
cannot reach $t^{\prime}$ in $G^{\prime}$, and thus $x_{n}\neq t^{\prime}$.
Since $P$ is maximal, we must have
$\phi_{x_{n}}^{\bot}[Rw]\subseteq\mathbf{r}$. Then
$\phi_{\bot}^{x_{n-1}}[u]\cup\phi_{x_{n-1}}^{x_{n}}[Rv]\cup\phi_{x_{n}}^{\bot}[Rw]$
satisfies $q$. ∎

###  7.2 $\mathbf{coNP}$-Hardness

Next, we show the $\mathbf{coNP}$-hard lower bound.

######  Lemma 19.

If a path query $q$ violates $\mathcal{C}_{3}$, then $\mathsf{CERTAINTY}({q})$
is $\mathbf{coNP}$-hard.

###### Proof.

If $q$ does not satisfy $\mathcal{C}_{3}$, then there exists a relation $R$
such that $q=uRvRw$ and $q$ is not a factor of $uRvRvRw$. Note that this means
that there is no homomorphism from $q$ to $uRvRvRw$. Also, $u$ must be
nonempty (otherwise, $q=RvRw$ is trivially a suffix of $RvRvRw$). Let $S$ be
the first relation of $u$.

The proof is a first-order reduction from $\mathsf{SAT}$ to the complement of
$\mathsf{CERTAINTY}({q})$. The problem $\mathsf{SAT}$ asks whether a given
propositional formula in CNF has a satisfying truth assignment.

Given any formula $\psi$ for $\mathsf{SAT}$, we construct an input instance
$\mathbf{db}$ for $\mathsf{CERTAINTY}({q})$ as follows:

  * •

for each variable $z$, we add $\phi_{z}^{\bot}[Rw]$ and
$\phi_{z}^{\bot}[RvRw]$;

  * •

for each clause $C$ and positive literal $z$ of $C$, we add $\phi_{C}^{z}[u]$;

  * •

for each clause $C$ and variable $z$ that occurs in a negative literal of $C$,
we add $\phi_{C}^{z}[uRv]$.

This construction can be executed in $\mathbf{FO}$. Figure 9 depicts an
example of the above construction. Intuitively, $\phi_{z}^{\bot}[Rw]$
corresponds to setting the variable $z$ to true, and $\phi_{z}^{\bot}[RvRw]$
to false. There are two types of conflicts that occur in $\mathbf{db}$. First,
we have conflicting facts of the form $S(\underline{C},*)$; resolving this
conflict corresponds to the clause $C$ choosing one of its literals. Moreover,
for each variable $z$, we have conflicting facts of the form
$R(\underline{z},*)$; resolving this conflict corresponds to the variable $z$
choosing a truth assignment.

$(x_{2}\vee\overline{x_{3}})$$(x_{1}\vee\overline{x_{2}})$$x_{3}$$x_{2}$$x_{1}$$-$$+$$-$$+$$-$$+$$u$$uRv$$u$$uRv$$Rw$$RvRw$$Rw$$RvRw$$Rw$$RvRw$
Figure 9: Database instance for the $\mathbf{coNP}$-hardness reduction from
the formula
$\psi=(x_{1}\vee\overline{x_{2}})\wedge(x_{2}\vee\overline{x_{3}})$.

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

$\implies$ Assume that there exists a satisfying truth assignment $\sigma$ for
$\psi$. Then for any clause $C$, there exists a variable $z_{C}\in C$ whose
corresponding literal is true in $C$ under $\sigma$. Consider the repair
$\mathbf{r}$ that:

  * •

for each variable $z$, it chooses the first $R$-fact of $\phi_{z}^{\bot}[Rw]$
if $\sigma(z)$ is true, otherwise the first $R$-fact of
$\phi_{z}^{\bot}[RvRw]$;

  * •

for each clause $C$, it chooses the first $S$-fact of $\phi_{C}^{z}[u]$ if
$z_{C}$ is positive in $C$, or the first $S$-fact of $\phi_{C}^{z}[uRv]$ if
$z_{C}$ is negative in $C$.

Assume for the sake of contradiction that $\mathbf{r}$ satisfies $q$. Then we
must have a homomorphism from $q$ to either $uRw$ or $uRvRvRw$. But the former
is not possible, while the latter contradicts $\mathcal{C}_{3}$. We conclude
by contradiction that $\mathbf{r}$ falsifies $q$.

$\impliedby$ Suppose that there exists a repair $\mathbf{r}$ of $\mathbf{db}$
that falsifies $q$. Consider the assignment $\sigma$:

$\sigma(z)=\begin{cases}\mbox{true}&\mbox{if
$\phi_{z}^{\bot}[Rw]\subseteq\mathbf{r}$}\\\ \mbox{false}&\mbox{if
$\phi_{z}^{\bot}[RvRw]\subseteq\mathbf{r}$}\end{cases}$

We claim that $\sigma$ is a satisfying truth assignment for $\psi$. Indeed,
for each clause $C$, the repair must have chosen a variable $z$ in $C$. If $z$
appears as a positive literal in $C$, then
$\phi_{C}^{z}[u]\subseteq\mathbf{r}$. Since $\mathbf{r}$ falsifies $q$, we
must have $\phi_{z}^{\bot}[Rw]\subseteq\mathbf{r}$. Thus, $\sigma(z)$ is true
and $C$ is satisfied. If $z$ appears in a negative literal, then
$\phi_{C}^{z}[uRv]\subseteq\mathbf{r}$. Since $\mathbf{r}$ falsifies $q$, we
must have $\phi_{z}^{\bot}[RvRw]\subseteq\mathbf{r}$. Thus, $\sigma(z)$ is
false and $C$ is again satisfied. ∎

###  7.3 $\mathbf{PTIME}$-Hardness

Finally, we show the $\mathbf{PTIME}$-hard lower bound.

######  Lemma 20.

If a path query $q$ violates $\mathcal{C}_{2}$, then $\mathsf{CERTAINTY}({p})$
is $\mathbf{PTIME}$-hard.

###### Proof.

Suppose $q$ violates $\mathcal{C}_{2}$. If $q$ also violates $\mathcal{C}_{3}$
, then the problem $\mathsf{CERTAINTY}({q})$ is $\mathbf{PTIME}$-hard since it
is $\mathbf{coNP}$-hard by Lemma 19. Otherwise, it is possible to write
$q=uRv_{1}Rv_{2}Rw$, with three consecutive occurrences of $R$ such that
$v_{1}\neq v_{2}$ and $Rw$ is not a prefix of $Rv_{1}$. Let $v$ be the maximal
path query such that $v_{1}=vv_{1}^{+}$ and $v_{2}=vv_{2}^{+}$. Thus
$v_{1}^{+}\neq v_{2}^{+}$ and the first relation names of $v_{1}^{+}$ and
$v_{2}^{+}$ are different.

Our proof is a reduction from the Monotone Circuit Value Problem (MCVP) known
to be $\mathbf{PTIME}$-complete [18]:

Problem:

$\mathsf{MCVP}$

Input:

A monotone Boolean circuit $C$ on inputs $x_{1}$, $x_{2}$, $\dots$, $x_{n}$
and output gate $o$; an assignment $\sigma:\\{x_{i}\mid 1\leq i\leq
n\\}\rightarrow\\{0,1\\}$.

Question:

What is the value of the output $o$ under $\sigma$?

We construct an instance $\mathbf{db}$ for $\mathsf{CERTAINTY}({q})$ as
follows:

  * •

for the output gate $o$, we add $\phi_{\bot}^{o}[uRv_{1}]$;

  * •

for each input variable $x$ with $\sigma(x)=1$, we add
$\phi_{x}^{\bot}[Rv_{2}Rw]$;

  * •

for each gate $g$, we add $\phi_{\bot}^{g}[u]$ and
$\phi_{g}^{\bot}[Rv_{2}Rw]$;

  * •

for each AND gate $g=g_{1}\land g_{2}$, we add

$\phi_{g}^{g_{1}}[Rv_{1}]\cup\phi_{g}^{g_{2}}[Rv_{1}].$

Here, $g_{1}$ and $g_{2}$ can be gates or input variables; and

  * •

for each OR gate $g=g_{1}\lor g_{2}$, we add

$\begin{array}[]{*{6}{l}}&\phi_{g}^{c_{1}}[Rv]&\cup&\phi_{c_{1}}^{g_{1}}[v_{1}^{+}]&\cup&\phi_{c_{1}}^{c_{2}}[v_{2}^{+}]\\\\[2.15277pt]
\cup&\phi_{\bot}^{c_{2}}[u]&\cup&\phi_{c_{2}}^{g_{2}}[Rv_{1}]&\cup&\phi_{c_{2}}^{\bot}[Rw]\end{array}$

where $c_{1},c_{2}$ are fresh constants.

This construction can be executed in $\mathbf{FO}$. An example of the gadget
constructions is shown in Figure 10. We next show that the output gate $o$ is
evaluated to $1$ under $\sigma$ if and only if each repair of $\mathbf{db}$
satisfies $q$.

$g$$g_{2}$$g_{1}$$u$$Rv_{1}$$Rv_{1}$$Rv_{2}Rw$ (a) AND gate

$g$$g_{1}$$g_{2}$$c_{1}$$c_{2}$$u$$Rv_{2}Rw$$v_{1}^{+}$$Rv$$v_{2}^{+}$$u$$Rw$$Rv_{1}$
(b) OR gate

Figure 10: Gadgets for the $\mathbf{PTIME}$-hardness reduction.

$\implies$ Suppose the output gate $o$ is evaluated to $1$ under $\sigma$.
Consider any repair $\mathbf{r}$. We construct a sequence of gates starting
from $o$, with the invariant that every gate $g$ evaluates to $1$, and there
is a path of the form $uRv_{1}$ in $\mathbf{r}$ that ends in $g$. The output
gate $o$ evaluates to $1$, and also we have that
$\phi_{\bot}^{o}[uRv_{1}]\subseteq\mathbf{r}$ by construction. Suppose that we
are at gate $g$. If there is a $Rv_{2}Rw$ path in $\mathbf{r}$ that starts in
$g$, the sequence ends and the query $q$ is satisfied. Otherwise, we
distinguish two cases:

  1. 1.

$g=g_{1}\land g_{2}$. Then, we choose the gate with
$\phi_{g}^{g_{i}}[Rv_{1}]\subseteq\mathbf{r}$. Since both gates evaluate to 1
and $\phi_{\bot}^{g}[u]\subseteq\mathbf{r}$, the invariant holds for the
chosen gate.

  2. 2.

$g=g_{1}\lor g_{2}$. If $g_{1}$ evaluates to $1$, we choose $g_{1}$. Observe
that
$\phi_{\bot}^{g}[u]\cup\phi_{g}^{c_{1}}[Rv]\cup\phi_{c_{1}}^{g_{1}}[v_{1}^{+}]$
creates the desired $uRv_{1}$ path. Otherwise $g_{2}$ evaluates to $1$. If
$\phi_{c_{2}}^{\bot}[Rw]\subseteq\mathbf{r}$, then there is a path with trace
$uRv_{1}$ ending in $g$, and a path with trace $Rv_{2}Rw$ starting in $g$, and
therefore $\mathbf{r}$ satisfies $q$. If
$\phi_{c_{2}}^{\bot}[Rw]\nsubseteq\mathbf{r}$, we choose $g_{2}$ and the
invariant holds.

If the query is not satisfied at any point in the sequence, we will reach an
input variable $x$ evaluated at $1$. But then there is an outgoing $Rv_{2}Rw$
path from $x$, which means that $q$ must be satisfied.

$\impliedby$ Proof by contraposition. Assume that $o$ is evaluated to $0$
under $\sigma$. We construct a repair $\mathbf{r}$ as follows, for each gate
$g$:

  * •

if $g$ is evaluated to 1, we choose the first $R$-fact in
$\phi_{g}^{\bot}[Rv_{2}Rw]$;

  * •

if $g=g_{1}\land g_{2}$ and $g$ is evaluated to $0$, let $g_{i}$ be the gate
or input variable evaluated to $0$. We then choose $\phi_{g}^{g_{i}}[Rv_{1}]$;

  * •

if $g=g_{1}\lor g_{2}$ and $g$ is evaluated to $0$, we choose
$\phi_{g}^{c_{1}}[Rv]$; and

  * •

if $g=g_{1}\lor g_{2}$, we choose $\phi_{c_{2}}^{g_{2}}[Rv_{1}]$.

For a path query $p$, we write ${\mathsf{head}}({p})$ for the variable at the
key-position of the first atom, and ${\mathsf{rear}}({p})$ for the variable at
the non-key position of the last atom.

Assume for the sake of contradiction that $\mathbf{r}$ satisfies $q$. Then,
there exists some valuation $\theta$ such that
$\theta(uRv_{1}Rv_{2}Rw)\subseteq\mathbf{r}$. Then the gate
$g^{*}\vcentcolon=\theta({\mathsf{head}}({Rv_{1}}))$ is evaluated to $0$ by
construction. Let $g_{1}\vcentcolon=\theta({\mathsf{rear}}({Rv_{1}}))$. By
construction, for $g^{*}=g_{1}\land g_{2}$ or $g^{*}=g_{1}\lor g_{2}$, we must
have $\phi_{g}^{g_{1}}[Rv_{1}]\subseteq\mathbf{r}$ and $g_{1}$ is a gate or an
input variable also evaluated to $0$. By our construction of $\mathbf{r}$,
there is no path with trace $Rv_{2}Rw$ outgoing from $g_{1}$. However,
$\theta(Rv_{2}Rw)\subseteq\mathbf{r}$, this can only happen when $g_{1}$ is an
OR gate, and one of the following occurs:

  * •

Case that $|{Rw}|\leq|{Rv_{1}}|$, and the trace of $\theta(Rv_{2}Rw)$ is a
prefix of $Rvv_{2}^{+}Rv_{1}$. Then $Rw$ is a prefix of $Rv_{1}$, a
contradiction.

  * •

Case that $|{Rw}|>|{Rv_{1}}|$, and $Rvv_{2}^{+}Rv_{1}$ is a prefix of the
trace of $\theta(Rv_{2}Rw)$. Consequently, $Rv_{1}$ is a prefix of $Rw$. Then,
for every $k\geq 1$, ${\mathcal{L}}^{\looparrowright}({q})$ contains
$uRv_{1}\left({Rv_{2}}\right)^{k}Rw$. It is now easily verified that for large
enough values of $k$, $uRv_{1}Rv_{2}w$ is not a factor of
$uRv_{1}\left({Rv_{2}}\right)^{k}Rw$. By Lemmas 5 and 19,
$\mathsf{CERTAINTY}({q})$ is $\mathbf{coNP}$-hard. ∎

##  8 Path Queries with Constants

We now extend our complexity classification of $\mathsf{CERTAINTY}({q})$ to
path queries in which constants can occur.

######  Definition 16 (Generalized path queries).

A generalized path query is a Boolean conjunctive query of the following form:

$q=\\{R_{1}(\underline{s_{1}},s_{2}),R_{2}(\underline{s_{2}},s_{3}),\dots,R_{k}(\underline{s_{k}},s_{k+1})\\},$
(5)

where $s_{1}$, $s_{2}$,…, $s_{k+1}$ are constants or variables, all distinct,
and $R_{1}$, $R_{2}$,…, $R_{k}$ are (not necessarily distinct) relation names.
Significantly, every constant can occur at most twice: at a non-primary-key
position and the next primary-key-position.

The _characteristic prefix_ of $q$, denoted by ${\mathsf{char}}({q})$, is the
longest prefix

$\\{R_{1}(\underline{s_{1}},s_{2}),R_{2}(\underline{s_{2}},s_{3}),\dots,R_{\ell}(\underline{s_{\ell}},s_{\ell+1})\\},0\leq\ell\leq
k$

such that no constant occurs among $s_{1}$, $s_{2}$, …, $s_{\ell}$ (but
$s_{\ell+1}$ can be a constant). Clearly, if $q$ is constant-free, then
${\mathsf{char}}({q})=q$. ∎

######  Example 8.

If $q=\\{R(\underline{x},y)$, $S(\underline{y},0)$, $T(\underline{0},1)$,
$R(\underline{1},w)\\}$, where $0$ and $1$ are constants, then
${\mathsf{char}}({q})=\\{R(\underline{x},y)$, $S(\underline{y},0)\\}$. ∎

The following lemma implies that if a generalized path query $q$ starts with a
constant, then $\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$. This explains
why the complexity classification in the remainder of this section will only
depend on ${\mathsf{char}}({q})$.

######  Lemma 21.

For any generalized path query $q$, $\mathsf{CERTAINTY}({p})$ is in
$\mathbf{FO}$, where $p\vcentcolon=q\setminus{\mathsf{char}}({q})$.

We now introduce some definitions and notations used in our complexity
classification. The following definition introduces a convenient syntactic
shorthand for characteristic prefixes previously defined in Definition 16.

######  Definition 17.

Let $q=\\{R_{1}(\underline{x_{1}},x_{2})$, $R_{2}(\underline{x_{2}},x_{3})$,
…, $R_{k}(\underline{x_{k}},x_{k+1})\\}$ be a path query. We write
$[\\![{q},{c}]\\!]$ for the generalized path query obtained from $q$ by
replacing $x_{k+1}$ with the constant $c$. The constant-free path query $q$
will be denoted by $[\\![{q},{\top}]\\!]$, where $\top$ is a distinguished
special symbol. ∎

######  Definition 18 (Prefix homomorphism).

Let

$\displaystyle q$ $\displaystyle=$
$\displaystyle\\{R_{1}(\underline{s_{1}},s_{2}),R_{2}(\underline{s_{2}},s_{3}),\dots,R_{k}(\underline{s_{k}},s_{k+1})\\}$
$\displaystyle p$ $\displaystyle=$
$\displaystyle\\{S_{1}(\underline{t_{1}},t_{2}),S_{2}(\underline{t_{2}},t_{3}),\dots,R_{\ell}(\underline{s_{\ell}},s_{\ell+1})\\}$

be generalized path queries. A _homomorphism from $q$ to $p$_ is a
substitution $\theta$ for the variables in $q$, extended to be the identity on
constants, such that for every $i\in\\{1,\dots,k\\}$,
$R_{i}(\underline{\theta(s_{i})},\theta(s_{i+1}))\in p$. Such a homomorphism
is a _prefix homomorphism_ if $\theta(s_{1})=t_{1}$. ∎

######  Example 9.

Let $q=\\{R(\underline{x},y)$, $R(\underline{y},1)$, $S(\underline{1},z)\\}$,
and $p=\\{R(\underline{x},y)$, $R(\underline{y},z)$, $R(\underline{y},1)\\}$.
Then
${\mathsf{char}}({q})=\\{R(\underline{x},y),R(\underline{y},1)\\}=[\\![{RR},{1}]\\!]$
and $p=[\\![{RRR},{1}]\\!]$. There is a homomorphism from
${\mathsf{char}}({q})$ to $p$, but there is no prefix homomorphism from
${\mathsf{char}}({q})$ to $p$. ∎

The following conditions generalize $\mathcal{C}_{1}$, $\mathcal{C}_{2}$, and
$\mathcal{C}_{3}$ from constant-free path queries to generalized path queries.
Let $\gamma$ be either a constant or the distinguished symbol $\top$.

$\mathcal{D}_{1}$:

Whenever ${\mathsf{char}}({q})=[\\![{uRvRw},{\gamma}]\\!]$, there is a prefix
homomorphism from ${\mathsf{char}}({q})$ to $[\\![{uRvRvRw},{\gamma}]\\!]$.

$\mathcal{D}_{2}$:

Whenever ${\mathsf{char}}({q})=[\\![{uRvRw},{\gamma}]\\!]$, there is a
homomorphism from ${\mathsf{char}}({q})$ to $[\\![{uRvRvRw},{\gamma}]\\!]$;
and whenever ${\mathsf{char}}({q})=[\\![{uRv_{1}Rv_{2}Rw},{\gamma}]\\!]$ for
consecutive occurrences of $R$, $v_{1}=v_{2}$ or there is a prefix
homomorphism from $[\\![{Rw},{\gamma}]\\!]$ to $[\\![{Rv_{1}},{\gamma}]\\!]$.

$\mathcal{D}_{3}$:

Whenever ${\mathsf{char}}({q})=[\\![{uRvRw},{\gamma}]\\!]$, there is a
homomorphism from ${\mathsf{char}}({q})$ to $[\\![{uRvRvRw},{\gamma}]\\!]$.

It is easily verified that if $\gamma=\top$, then $\mathcal{D}_{1}$,
$\mathcal{D}_{2}$, and $\mathcal{D}_{3}$ are equivalent to, respectively,
$\mathcal{C}_{1}$, $\mathcal{C}_{2}$, and $\mathcal{C}_{3}$. Likewise, the
following theorem degenerates to Theorem 3 for path queries without constants.

######  Theorem 4.

For every generalized path query $q$, the following complexity upper bounds
obtain:

  * •

if $q$ satisfies $\mathcal{D}_{1}$, then $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{FO}$;

  * •

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

  * •

if $q$ satisfies $\mathcal{D}_{3}$, then $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{PTIME}$.

The following complexity lower bounds obtain:

  * •

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

  * •

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

  * •

if $q$ violates $\mathcal{D}_{3}$, then $\mathsf{CERTAINTY}({q})$ is
$\mathbf{coNP}$-complete.

Finally, the proof of Theorem 4 reveals that for generalized path queries $q$
containing at least one constant, the complexity of $\mathsf{CERTAINTY}({q})$
exhibits a trichotomy (instead of a tetrachotomy as in Theorem 4).

######  Theorem 5.

For any generalized path query $q$ containing at least one constant, the
problem $\mathsf{CERTAINTY}({q})$ is either in $\mathbf{FO}$,
$\mathbf{NL}$-complete, or $\mathbf{coNP}$-complete.

##  9 Related Work

Inconsistencies in databases have been studied in different contexts [8, 21,
22]. Consistent query answering (CQA) was initiated by the seminal work by
Arenas, Bertossi, and Chomicki [3]. After twenty years, their contribution was
acknowledged in a _Gems of PODS session_ [5]. An overview of complexity
classification results in CQA appeared recently in the _Database Principles_
column of SIGMOD Record [41].

The term $\mathsf{CERTAINTY}({q})$ was coined in [39] 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 started with the work by Fuxman and Miller [17], and was further
pursued in [23, 26, 27, 28, 30, 32], which eventually 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. A few extensions beyond this trichotomy result are
known. It remains decidable whether or not $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{FO}$ for self-join-free Boolean conjunctive queries with negated
atoms [29], with respect to multiple keys [31], and with unary foreign keys
[20], all assuming that $q$ is self-join-free.

Little is known about $\mathsf{CERTAINTY}({q})$ beyond self-join-free
conjunctive queries. Fontaine [14] showed that if we strengthen Conjecture 1
from conjunctive queries to unions of conjunctive queries, then it implies
Bulatov’s dichotomy theorem for conservative CSP [6]. This relationship
between CQA and CSP was further explored in [34]. In [1], the authors show the
$\mathbf{FO}$ boundary for $\mathsf{CERTAINTY}({q})$ for constant-free Boolean
conjunctive queries $q$ using a single binary relation name with a singleton
primary key. Figueira et al. [13] 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}$.

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 [37]. This dichotomy has been shown to
extend to self-joins if primary keys are singletons [38], and to functional
dependencies [7].

In practice, systems supporting CQA have often used efficient solvers for
Disjunctive Logic Programming, Answer Set Programming (ASP) or Binary Integer
Programming (BIP), regardless of whether the CQA problem admits a first-order
rewriting [2, 9, 10, 11, 12, 19, 24, 35, 36].

##  10 Conclusion

We established a complexity classification in consistent query answering
relative to primary keys, for path queries that can have self-joins: for every
path query $q$, the problem $\mathsf{CERTAINTY}({q})$ is in $\mathbf{FO}$,
$\mathbf{NL}$-complete, $\mathbf{PTIME}$-complete, or
$\mathbf{coNP}$-complete, and it is decidable in polynomial time in the size
of $q$ which of the four cases applies. If $\mathsf{CERTAINTY}({q})$ is in
$\mathbf{FO}$ or in $\mathbf{PTIME}$, rewritings of $q$ can be effectively
constructed in, respectively, first-order logic and Least Fixpoint Logic .

For binary relation names and singleton primary keys, an intriguing open
problem is to generalize the form of the queries, from paths to directed
rooted trees, DAGs, or general digraphs. The ultimate open problem is
Conjecture 1, which conjectures that for every Boolean conjunctive query $q$,
$\mathsf{CERTAINTY}({q})$ is either in $\mathbf{PTIME}$ or
$\mathbf{coNP}$-complete.

Acknowledgements. This work is supported by the National Science Foundation
under grant IIS-1910014.

## References

  * [1] F. N. Afrati, P. G. Kolaitis, and A. Vasilakopoulos.  Consistent answers of conjunctive queries on graphs.  CoRR, abs/1503.00650, 2015.
  * [2] A. Amezian El 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.
  * [3] M. Arenas, L. E. Bertossi, and J. Chomicki.  Consistent query answers in inconsistent databases.  In PODS, pages 68–79. ACM Press, 1999.
  * [4] C. Berkholz, J. Keppeler, and N. Schweikardt.  Answering conjunctive queries under updates.  In PODS, pages 303–318. ACM, 2017.
  * [5] L. E. Bertossi.  Database repairs and consistent query answering: Origins and further developments.  In PODS, pages 48–58. ACM, 2019.
  * [6] A. A. Bulatov.  Complexity of conservative constraint satisfaction problems.  ACM Trans. Comput. Log., 12(4):24:1–24:66, 2011.
  * [7] 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.
  * [8] J. Chomicki and J. Marcinkowski.  Minimal-change integrity maintenance using tuple deletions.  Inf. Comput., 197(1-2):90–121, 2005.
  * [9] 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.
  * [10] 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.
  * [11] A. A. Dixit and P. G. Kolaitis.  Consistent answers of aggregation queries via SAT.  In ICDE, pages 924–937. IEEE, 2022.
  * [12] 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.
  * [13] 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.
  * [14] 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.
  * [15] 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.
  * [16] 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.
  * [17] A. Fuxman and R. J. Miller.  First-order query rewriting for inconsistent databases.  J. Comput. Syst. Sci., 73(4):610–635, 2007.
  * [18] L. M. Goldschlager.  The monotone and planar circuit value problems are log space complete for P.  SIGACT News, 9(2):25–29, July 1977.
  * [19] 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.
  * [20] 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.
  * [21] 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.
  * [22] Y. Katsis, A. Deutsch, Y. Papakonstantinou, and V. Vassalos.  Inconsistency resolution in online databases.  In ICDE, pages 1205–1208. IEEE Computer Society, 2010.
  * [23] 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.
  * [24] 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.
  * [25] P. Koutris, X. Ouyang, and J. Wijsen.  Consistent query answering for primary keys on path queries.  In PODS, pages 215–232. ACM, 2021.
  * [26] 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.
  * [27] 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.
  * [28] 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.
  * [29] P. Koutris and J. Wijsen.  Consistent query answering for primary keys and conjunctive queries with negated atoms.  In PODS, pages 209–224. ACM, 2018.
  * [30] 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.
  * [31] P. Koutris and J. Wijsen.  First-order rewritability in consistent query answering with respect to multiple keys.  In PODS, pages 113–129. ACM, 2020.
  * [32] P. Koutris and J. Wijsen.  Consistent query answering for primary keys in datalog.  Theory Comput. Syst., 65(1):122–178, 2021.
  * [33] L. Libkin.  Elements of Finite Model Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004\.
  * [34] 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.
  * [35] 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.
  * [36] 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.
  * [37] D. Maslowski and J. Wijsen.  A dichotomy in the complexity of counting database repairs.  J. Comput. Syst. Sci., 79(6):958–983, 2013.
  * [38] D. Maslowski and J. Wijsen.  Counting database repairs that satisfy conjunctive queries with self-joins.  In ICDT, pages 155–164. OpenProceedings.org, 2014.
  * [39] J. Wijsen.  On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases.  In PODS, pages 179–190. ACM, 2010.
  * [40] J. Wijsen.  Certain conjunctive query answering in first-order logic.  ACM Trans. Database Syst., 37(2):9:1–9:35, 2012.
  * [41] J. Wijsen.  Foundations of query answering on inconsistent databases.  SIGMOD Rec., 48(3):6–16, 2019.

##  Appendix A Proofs for Section 4

###  A.1 Preliminary Results

We define $\left({q}\right)^{k}=\varepsilon$ if $k=0$. The following lemma
concerns words having a proper suffix that is also a prefix.

######  Lemma 22.

If $w$ is a prefix of the word $uw$ with $u\neq\varepsilon$, then $w$ is a
prefix of $\left({u}\right)^{|{w}|}$. Symmetrically, if $u$ is a suffix $uw$
with $w\neq\varepsilon$, then $u$ is a suffix of $\left({w}\right)^{|{u}|}$.

###### Proof.

Assume $w$ is a prefix of $uw$ with $u\neq\varepsilon$. The desired result is
obvious if $|{w}|\leq|{u}|$, in which case $w$ is a prefix of $u$. In the
remainder of the proof, assume $|{w}|>|{u}|$. The desired result becomes clear
from the following construction:

The word $w_{1}$ is the occurrence of $w$ that is a prefix of $uw$. The word
$u_{2}$ is the length-$|{u}|$ prefix of $w$. Obviously, $u_{2}=u$. The word
$u_{2}u_{3}$ is the length-$2|{u}|$ prefix of $w$. Obviously, $u_{3}=u_{2}$.
And so on. It is now clear that $w$ is a prefix of $\left({u}\right)^{|{w}|}$.
Note that this construction requires $u\neq\varepsilon$. This concludes the
proof. ∎

######  Definition 19 (Episode).

An _episode_ of $q$ is a factor of $q$ of the form $RuR$ such that $R$ does
not occur in $u$. Let $q=\ell RuRr$ where $RuR$ is an episode. We say that
this episode is _right-repeating (within $q$)_ if $r$ is a prefix of
$\left({uR}\right)^{|{r}|}$. Symmetrically, we say that this episode is _left-
repeating_ if $\ell$ is a suffix of $\left({Ru}\right)^{|{\ell}|}$. ∎

For example, let
$q=AMAA\overbrace{MAAM}^{e_{1}}A\overbrace{MAAM}^{e_{2}}AAMAB$. Then the
episode called $e_{1}$ is left-repeating, while the episode $e_{2}$ is neither
left-repeating nor right-repeating.

######  Definition 20 (Offset).

Let $u$ and $w$ be words. We say that $u$ has _offset_ $n$ in $w$ if there
exists words $p$, $s$ such that $|{p}|=n$ and $w=pus$. ∎

######  Lemma 23 (Repeating lemma).

Let $q$ be a word that satisfies $\mathcal{C}_{3}$. Then, every episode of $q$
is either left-repeating or right-repeating (or both).

###### Proof.

Let $RuR$ be an episode in $q=\ell RuRr$. By the hypothesis of the lemma, $q$
is a factor of
$p\vcentcolon=\mbox{${\ell}\\!\cdot\\!{Ru}\\!\cdot\\!\underline{Ru}\\!\cdot\\!{Rr}$}$.
Since $|{q}|-|{p}|=|{u}|+1$, the offset of $q$ in $p$ is $\leq|{u}|+1$. Since
$R$ does not occur in $u$, it must be that $q$ is either a prefix or a suffix
of $p$. We distinguish two cases:

Case that $q$ is a suffix of $p$.

Then, it is easily verified that $\ell$ is a suffix of $\ell Ru$. By Lemma 22,
$\ell$ is a suffix of $\left({Ru}\right)^{|{\ell}|}$, which means that $RuR$
is left-repeating within $q$.

Case that $q$ is a prefix of $p$.

We have that $r$ is a prefix of $uRr$. By Lemma 22, $r$ is a prefix of
$\left({uR}\right)^{|{r}|}$, which means that $RuR$ is right-repeating.

This concludes the proof. ∎

######  Definition 21.

If $q$ is a word over an alphabet $\Sigma$, then ${\mathsf{symbols}}({q})$ is
the set that contains all (and only) the symbols that occur in $q$.

######  Lemma 24 (Self-join-free episodes).

Let $q$ be a word that satisfies $\mathcal{C}_{3}$. Let $L\ell L$ be the
right-most occurrence of an episode that is left-repeating in $q$. Then,
$L\ell$ is self-join-free.

###### Proof.

Consider for the sake of contradiction that $L\ell$ is not self-join-free.
Since $L\not\in{\mathsf{symbols}}({\ell})$, it must be that $\ell$ has a
factor $MmM$ such that $Mm$ is self-join-free. By Lemma 23, $MmM$ must be
left-repeating or right-repeating, which requires
$L\in{\mathsf{symbols}}({Mm})$, a contradiction. ∎

###  A.2 Proof of Lemma 1

###### Proof of Lemma 1.

The implication 2$\implies$1 is obvious. To show 1$\implies$2, assume that $q$
satisfies $\mathcal{C}_{1}$. The desired result is obvious if $q$ is self-
join-free. Assume from here on that $q$ is not self-join-free. Then, we can
write $q=\ell RmRr$, such that $\ell Rm$ is self-join-free. That is, the
second occurrence of $R$ is the left-most symbol that occurs a second time in
$q$. By $\mathcal{C}_{1}$, $q$ is a prefix of $\ell RmRmRr$. It follows that
$Rr$ is a prefix of $RmRr$. By Lemma 22, $Rr$ is a prefix of
$\left({Rm}\right)^{|{r}|+1}$. It follows that there is a $k$ such that $q$ is
a prefix of $\ell\left({Rm}\right)^{k}$. ∎

###  A.3 Proof of Lemma 2

###### Proof of Lemma 2.

The proof of 2$\implies$1 is straightforward. We show next the direction
1$\implies$2. To this end, assume that $q$ satisfies $\mathcal{C}_{3}$. The
desired result is obvious if $q$ is self-join-free (let $j=k=0$ in
$\mathcal{B}_{2a}$). Assume that $q$ has a factor $L\ell L\cdot m\cdot RrR$
where $L\ell L$ and $RrR$ are episodes such that ${\mathsf{symbols}}({L\ell
L})$, ${\mathsf{symbols}}({RrR})$, and ${\mathsf{symbols}}({m})$ are pairwise
disjoint. Then, by Lemma 23, $L\ell L$ must be left-repeating, and $RrR$
right-repeating. By Lemma 24, $L\ell$ and $rR$ are self-join-free. Then $q$ is
of the form $\mathcal{B}_{2a}$. By letting $j=0$ or $k=0$, we obtain the
situation where the number of episodes that are factors of $q$ is zero or one.

The only difficult case is where two episodes overlap. Assume that $q$ has an
episode that is left-repeating (the case of a right-repeating episode is
symmetrical). Assume that this left-repeating episode is
$e_{1}\vcentcolon=L\ell RoL$ in
$q\vcentcolon=\dotsm\begin{array}[]{l}\overbrace{L\ell
RoL}^{e_{1}}rR\\\\[-12.05553pt]
\phantom{L\ell}\underbrace{\phantom{RoLrR}}_{e_{2}}\end{array}\dotsm$, where
it can be assumed that $e_{1}$ is the right-most episode that is left-
repeating. Then, $\ell\neq\varepsilon\neq r$ implies
${\mathsf{first}}({\ell})\neq{\mathsf{first}}({r})$ (or else $e_{1}$ would not
be right-most, a contradiction). By a similar reasoning, $\ell=\varepsilon$
implies $r\neq\varepsilon$. Therefore, it is correct to conclude $\ell\neq r$.
It can also be assumed without loss of generality that $r$ shares no symbols
with $e_{1}$, by choosing $R$ as the first symbol after $e_{1}$ that also
occurs in $e_{1}$. Now assume $e_{2}$ is right-repeating, over a length
$>|{oL}|$. Then $q$ contains a factor $\begin{array}[]{l}\overbrace{L\ell
RoL}^{e_{1}}rR\\\\[-12.05553pt]
\phantom{L\ell}\underbrace{\phantom{RoLrR}}_{e_{2}}\end{array}\cdot oL$. Then,
$q$ rewinds to a word $p$ with factor:

$\begin{array}[]{l}\overbrace{L\ell RoL}^{e_{1}}rR\\\\[-12.05553pt]
\phantom{L\ell}\underbrace{\phantom{RoLrR}}_{e_{2}}\end{array}\cdot
o\begin{array}[]{l}\overbrace{L|\ell RoL}^{e_{1}}rR\\\\[-12.05553pt]
\phantom{L\ell}\underbrace{\phantom{RoLrR}}_{e_{2}}\end{array}\cdot oL,$

where the vertical bar $|$ is added to indicate a distinguished position. It
can now be verified that $q$ is not a factor of $p$, because of the
alternation of $e_{1}$ and $e_{2}$ which does not occur in $q$. This
contradicts the hypothesis of the lemma. In particular, the words that start
at position $|$ are $r$ and $\ell$ in, respectively, $q$ and $p$. We conclude
by contradiction that $e_{2}$ cannot be right-repeating over a length
$>|{oL}|$. Thus, following the right-most occurrence of $e_{1}$, the word $q$
can contain fresh word $r$, followed by $RoL$, which is a suffix of $e_{1}$.
This is exactly the form $\mathcal{B}_{2b}$.

A remaining, and simpler, case is where two episodes overlap by a single
symbol $R=L$, giving $q\vcentcolon=\dotsm\begin{array}[]{l}\overbrace{L\ell
L}^{e_{1}}rL\\\\[-12.05553pt]
\phantom{L\ell}\underbrace{\phantom{LrR}}_{e_{2}}\end{array}\dotsm$, where
$e_{1}$ is the right-most episode that is left-repeating, and $L$ is the first
symbol after $e_{1}$ that also occurs in $e_{1}$. Therefore, $L$ does not
occur in $\ell\cdot r$, and $\ell\neq r$. Indeed, if $\ell=\varepsilon=r$,
then $e_{1}$ is not right-most; and if $\ell\neq\varepsilon\neq r$, then
${\mathsf{first}}({\ell})\neq{\mathsf{first}}({r})$, or else $e_{1}$ would not
be right-most, a contradiction. The word $q$ rewinds to a word $p$ with factor
$\begin{array}[]{l}\overbrace{L\ell L}^{e_{1}}r\overbrace{L\ell
L}^{e_{1}}rL,\\\\[-12.05553pt]
\phantom{L\ell}\underbrace{\phantom{LrL}}_{e_{2}}\phantom{\ell}\underbrace{\phantom{LrL}}_{e_{2}}\end{array}$
and $|{p}|-|{q}|=|{\ell}|+|{r}|+2$. It is easily verified that $e_{2}$ cannot
be right-repeating for $>0$ symbols. For instance, consider the case where
$r\neq\varepsilon$ and $e_{2}$ is right-repeating for $1$ symbol, meaning that
$q$ has suffix $\begin{array}[]{l}\overbrace{L\ell
L}^{e_{1}}rL\cdot{\mathsf{first}}({r}),\\\\[-12.05553pt]
\phantom{L\ell}\underbrace{\phantom{LrR}}_{e_{2}}\end{array}$ and $p$ has
suffix $\begin{array}[]{l}\overbrace{L\ell L}^{e_{1}}r\overbrace{L\ell
L}^{e_{1}}rL\cdot{\mathsf{first}}({r}).\\\\[-12.05553pt]
\phantom{L\ell}\underbrace{\phantom{LrL}}_{e_{2}}\phantom{\ell}\underbrace{\phantom{LrL}}_{e_{2}}\end{array}$
If we left-align these suffixes, then there is a mismatch between
${\mathsf{first}}({r})$ and the leftmost symbol of $L\ell$. The other
possibility is to right-align these suffixes, but then $e_{1}$ cannot be
genuinely left-repeating within $q$. ∎

###  A.4 Proof of Lemma 3

###### Proof of Lemma 3.

Assume that $q$ satisfies $\mathcal{C}_{3}$. By Lemma 2, $q$ satisfies
$\mathcal{B}_{2a}$, $\mathcal{B}_{2b}$, or $\mathcal{B}_{3}$.

1$\implies$2 By contraposition. Assume that (2) does not hold. Then, either
$q$ satisfies $\mathcal{B}_{2a}$ or $q$ satisfies $\mathcal{B}_{2b}$. Assume
that $q=aRb_{1}Rb_{2}Rc$ for three consecutive occurrences of $R$ such that
$b_{1}\neq b_{2}$. It suffices to show that $Rc$ is a prefix of $Rb_{1}$. It
is easily verified that $b_{1}\neq b_{2}$ cannot happen if $q$ satisfies
$\mathcal{B}_{2a}$. Therefore, $q$ satisfies $\mathcal{B}_{2b}$. The word in
$\left({uv}\right)^{k}wv$ in $\mathcal{B}_{2b}$ indeed allows for suffix
$vu\cdot vw\cdot v$ where the first and second occurrence of $v$ are followed,
respectively, by $u$ and $w$. Then, in $q$, we have that $w$ is followed by a
prefix of $v$, and therefore $\mathcal{C}_{2}$ is satisfied.

2$\implies$3 The hypothesis is that $q$ satisfies $\mathcal{B}_{3}$, but
falsifies both $\mathcal{B}_{2a}$ and $\mathcal{B}_{2b}$. We can assume $k\geq
0$ and self-join-free word $uvw$ such that $q$ is a factor of
$uw\left({uv}\right)^{k}$, but $q$ falsifies $\mathcal{B}_{2a}$ and
$\mathcal{B}_{2b}$. It must be that $u\neq\varepsilon$ and the offset of $q$
in $uw\left({uv}\right)^{k}$ is $<|{u}|$, for otherwise $q$ is a factor of
$w\left({uv}\right)^{k}$ and therefore satisfies $\mathcal{B}_{2a}$, a
contradiction. Also, one of $v$ or $w$ must not be the empty word, or else $q$
is a factor of $u\left({u}\right)^{k}$, and therefore satisfies
$\mathcal{B}_{2a}$ (and also satisfies $\mathcal{B}_{2b}$). We now consider
the length of $q$. The word $uwuvu$ is a factor of $\left({wu}\right)^{2}vu$,
and thus satisfies $\mathcal{B}_{2b}$. If $v=\emptyset$, then the word $uwuu$
is a factor of $\left({wu}\right)^{2}u$, and thus satisfies
$\mathcal{B}_{2b}$. It is now correct to conclude that one of the following
must occur:

  * •

$v\neq\emptyset$ and $\mathsf{last}({u})\cdot wuvu\cdot{\mathsf{first}}({v})$
is a factor of $q$; or

  * •

$v=\emptyset$, $w\neq\emptyset$ and $\mathsf{last}({u})\cdot
w\left({u}\right)^{2}\cdot{\mathsf{first}}({u})$ is a factor of $q$.

3$\implies$1 Assume (3). Consider first the case $v\neq\varepsilon$. Let
$u=\hat{u}R$ and $v=S\hat{v}$. We have $R\neq S$, since $uv$ is self-join-
free. By item (3a), $q$ has a factor $R\cdot w\hat{u}RS\hat{v}\hat{u}R\cdot
S$, with three consecutive occurrences of $R$. It is easily verified that
$w\hat{u}\neq S\hat{v}\hat{u}$, and that $RS$ is not a prefix of $Rw\hat{u}$.
Therefore $q$ falsifies $\mathcal{C}_{2}$.

Consider next the case $v=\varepsilon$ (whence $w\neq\varepsilon$). Let
$u=\hat{u}R$. By item (3b), $q$ has a factor $R\cdot
w\hat{u}R\hat{u}R\cdot{\mathsf{first}}({u})$, with three consecutive
occurrences of $R$. Since $w\hat{u}\neq\hat{u}$ and
${\mathsf{first}}({u})\neq{\mathsf{first}}({w})$, it follows that $q$
falsifies $\mathcal{C}_{2}$. ∎

##  Appendix B Proofs for Section 8

###  B.1 Proof of Lemma 21

Lemma 21 is an immediate corollary of Lemma 27, which states that whenever a
generalized path query starts with a constant, then $\mathsf{CERTAINTY}({q})$
is in $\mathbf{FO}$. Its proof needs two helping lemmas.

######  Lemma 25.

Let $q=q_{1}\cup q_{2}\cup\dotsm\cup q_{k}$ be a Boolean conjunctive query
such that for all $1\leq i<j\leq k$,
$\mathsf{vars}({q_{i}})\cap\mathsf{vars}({q_{j}})=\emptyset$. Then, the
following are equivalent for every database instance $\mathbf{db}$:

  1. 1.

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

  2. 2.

for each $1\leq i\leq k$, $\mathbf{db}$ is a “yes”-instance for
$\mathsf{CERTAINTY}({q_{i}})$.

###### Proof.

We give the proof for $k=2$. The generalization to larger $k$ is
straightforward.

1$\implies$2 Assume that (1) holds true. Then each repair $\mathbf{r}$ of
$\mathbf{db}$ satisfies $q$, and therefore satisfies both $q_{1}$ and $q_{2}$.
Therefore, $\mathbf{db}$ is a “yes”-instance for both
$\mathsf{CERTAINTY}({q_{1}})$ and $\mathsf{CERTAINTY}({q_{2}})$.

2$\implies$1 Assume that (2) holds true. Let $\mathbf{r}$ be any repair of
$\mathbf{db}$. Then there are valuations $\mu$ from $\mathsf{vars}({q_{1}})$
to ${\mathsf{adom}}({\mathbf{db}})$, and $\theta$ from
$\mathsf{vars}({q_{2}})$ to ${\mathsf{adom}}({\mathbf{db}})$ such that
$\mu(q_{1})\subseteq\mathbf{r}$ and $\theta(q_{2})\subseteq\mathbf{r}$. Since
$\mathsf{vars}({q_{1}})\cap\mathsf{vars}({q_{2}})=\emptyset$ by construction,
we can define a valuation $\sigma$ as follows, for every variable
$z\in\mathsf{vars}({q_{1}})\cup\mathsf{vars}({q_{2}})$:

$\sigma(z)=\begin{cases}\mu(z)&\mbox{if $z\in\mathsf{vars}({q_{1}})$}\\\
\theta(z)&\mbox{if $z\in\mathsf{vars}({q_{2}})$}\end{cases}$

From
$\sigma(q)=\sigma(q_{1})\cup\sigma(q_{2})=\mu(q_{1})\cup\theta(q_{2})\subseteq\mathbf{r}$,
it follows that $\mathbf{r}$ satisfies $q$. Therefore, $\mathbf{db}$ is a
“yes”-instance for $\mathsf{CERTAINTY}({q})$. ∎

######  Lemma 26.

Let $q$ be a generalized path query with

$q=\\{R_{1}(\underline{s_{1}},s_{2}),R_{2}(\underline{s_{2}},s_{3}),\dots,R_{k}(\underline{s_{k}},c)\\},$

where $c$ is a constant, and each $s_{i}$ is either a constant or a variable
for all $i\in\\{1,\dots,k\\}$. Let

$p=\\{R_{1}(\underline{s_{1}},s_{2}),R_{2}(\underline{s_{2}},s_{3}),\dots,R_{k}(\underline{s_{k}},s_{k+1}),N(\underline{s_{k+1}},s_{k+2})\\},$

where $s_{k+1}$, $s_{k+2}$ are fresh variables to $q$ and $N$ is a fresh
relation to $q$. Then there exists a first-order reduction from
$\mathsf{CERTAINTY}({q})$ to $\mathsf{CERTAINTY}({p})$.

###### Proof.

Let $\mathbf{db}$ be an instance for $\mathsf{CERTAINTY}({q})$ and consider
the instance $\mathbf{db}\cup\\{N(\underline{c},d)\\}$ for
$\mathsf{CERTAINTY}({p})$ where $d$ is a fresh constant to
${\mathsf{adom}}({\mathbf{db}})$.

We show that $\mathbf{db}$ is a “yes”-instance for $\mathsf{CERTAINTY}({q})$
if and only if $\mathbf{db}\cup\\{N(\underline{c},d)\\}$ is a “yes”- instance
for $\mathsf{CERTAINTY}({p})$.

$\implies$ Assume $\mathbf{db}$ is a “yes”-instance for
$\mathsf{CERTAINTY}({q})$. Let $\mathbf{r}$ be any repair of
$\mathbf{db}\cup\\{N(\underline{c},d)\\}$, and thus
$\mathbf{r}\setminus\\{N(\underline{c},d)\\}$ is a repair for $\mathbf{db}$.
Then there exists a valuation $\mu$ with
$\mu(q)\subseteq\mathbf{r}\setminus\\{N(\underline{c},d)\\}$. Consider the
valuation $\mu^{+}$ from $\mathsf{vars}({q})\cup\\{s_{k+1},s_{k+2}\\}$ to
${\mathsf{adom}}({\mathbf{db}})\cup\\{c,d\\}$ that agrees with $\mu$ on