# Using Color Refinement to Boost Enumeration and Counting for Acyclic CQs of
Binary Schemas

Cristian Riveros  Pontificia Universidad Católica de Chile  Benjamin Scheidt
Humboldt-Universität zu Berlin, Germany  Nicole Schweikardt  Humboldt-
Universität zu Berlin, Germany

###### Abstract

We present an index structure, called the color-index, to boost the evaluation
of acyclic conjunctive queries (ACQs) over binary schemas. The color-index is
based on the color refinement algorithm, a widely used subroutine for graph
isomorphism testing algorithms. Given a database $D$, we use a suitable
version of the color refinement algorithm to produce a stable coloring of $D$,
an assignment from the active domain of $D$ to a set of colors $C_{D}$. The
main ingredient of the color-index is a particular database
${D_{\operatorname{col}}}$ whose active domain is $C_{D}$ and whose size is at
most $|D|$. Using the color-index, we can evaluate any free-connex ACQ $Q$
over $D$ with preprocessing time $O(|Q|\cdot|{D_{\operatorname{col}}}|)$ and
constant delay enumeration. Furthermore, we can also count the number of
results of $Q$ over $D$ in time $O(|Q|\cdot|{D_{\operatorname{col}}}|)$. Given
that $|{D_{\operatorname{col}}}|$ could be much smaller than $|D|$ (even
constant-size for some families of databases), the color-index is the first
index structure for evaluating free-connex ACQs that allows efficient
enumeration and counting with performance that may be strictly smaller than
the database size.

##  1 Introduction

An important part of database systems are _index structures_ that provide
efficient access to the stored data and help to accelerate query evaluation.
Such index structures typically rely on hash tables or balanced trees such as
B-trees or B+-trees, which boost the performance of value queries [31].
Another recent example is indices for worst-case optimal join algorithms [27].
For example, _Leapfrog Triejoin_ [33], a simple worst-case optimal algorithm
for evaluating multiway-joins on relational databases, is based on so-called
trie iterators for boosting the access under different join orders. These trie
indices have recently improved in the use of time and space [3]. Typically,
index structures are not constructed for supporting the evaluation of a single
query, but for supporting the evaluation of an entire class of queries. This
paper presents a novel kind of index structure called the _color-index_ to
boost the evaluation of free-connex acyclic conjunctive queries (fc-ACQs).

Acyclic conjunctive queries (ACQs) were introduced in [7, 10] and have since
then received a lot of attention. From Yannakakis’ seminal paper [34] it is
known that the result of every fixed ACQ $Q$ over a database $D$ can be
computed in time linear in the product of the database size $|D|$ and the
output size $|{\left\llbracket Q\right\rrbracket}(D)|$. For the particular
subclass fc-ACQ of _free-connex_ ACQs, it is even known to be linear in the
sum $|D|+|{\left\llbracket Q\right\rrbracket}(D)|$: the notion of _free-
connex_ ACQs was introduced in the seminal paper by Bagan, Durand, and
Grandjean [6], who improved Yannakakis’ result as follows. For any database
$D$, during a preprocessing phase that takes time linear in $|D|$, a data
structure can be computed that allows to enumerate, without repetition, all
the tuples of the query result ${\left\llbracket Q\right\rrbracket}(D)$, with
only a _constant_ delay between outputting any two tuples. Note that the data
structure computed in the preprocessing phase is designed for the particular
query $Q$, and the above running time statement suppresses factors that depend
on $Q$. For evaluating a new query $Q^{\prime}$, one has to start an entirely
new preprocessing phase that, again, takes time linear in $|D|$.

The main contribution of this paper is a novel index structure called the
_color-index_. Upon input of a database $D$ of a binary schema (i.e., the
schema consists of relation symbols of arity at most 2), the color-index can
be built in time $O(|D|{\cdot}\log|D|)$ in the worst-case, and for many $D$
the time is only $O(|D|)$. The main ingredient of the color-index is the
_color database_ ${D_{\operatorname{col}}}$. By using the color-index, upon
input of an arbitrary fc-ACQ $Q$ we can enumerate the tuples of the query
result ${\left\llbracket Q\right\rrbracket}(D)$ with constant delay after a
preprocessing phase that takes time linear in $|{D_{\operatorname{col}}}|$.
Compared to the above-mentioned result by Bagan, Durand, and Grandjean [6],
this accelerates the preprocessing time from $O(|D|)$ to
$O(|{D_{\operatorname{col}}}|)$. The size of ${D_{\operatorname{col}}}$ is
$O(|D|)$ in the worst-case, but depending on the particular structure of $D$,
the database ${D_{\operatorname{col}}}$ may be substantially smaller than $D$;
we show that even $O(1)$ is possible. Apart from enumerating the query result
with constant delay, the color-index can also be used to count the number of
tuples in the query result ${\left\llbracket Q\right\rrbracket}(D)$; this
takes time $O(|{D_{\operatorname{col}}}|)$ (in data complexity). To the best
of our knowledge, the color-index is the first index structure for fc-ACQs
that allows efficient enumeration and counting with performance guarantees
that may be sublinear in the database size.

The starting point for constructing the color-index is to represent $D$ by a
suitable vertex-labeled and edge-labeled directed graph, to which we then
apply a variant of the well-known _color refinement_ algorithm. Color
refinement is a simple and widely used subroutine for graph isomorphism
testing algorithms; see e.g. [8, 19] for an overview and [15, 4, 25, 26] for
details on its expressibility. Its result is a particular coloring of the
elements in the active domain of $D$. The construction of the color-index and,
in particular, the color database ${D_{\operatorname{col}}}$ is based on this
coloring. Our result relies on a close connection between the colors computed
by the color refinement algorithm and the homomorphisms from acyclic
conjunctive queries to the database. This connection between colors and
homomorphisms from tree-like structures has been used before in different
contexts [16, 20, 18, 11, 24]. Notions of index structures that are based on
concepts of bisimulations (which produce results similar to color refinement)
and geared towards conjunctive query evaluation have been proposed and
empirically evaluated, e.g., in [29, 30, 32]. But to the best of our
knowledge, the present paper is the first to use color refinement to produce
an index structure that guarantees efficient constant-delay enumeration and
counting.

The remainder of the paper is organized as follows. Section 2 fixes the basic
notation concerning databases and queries. Section 3 formalizes the general
setting of _indexing for query evaluation_. Section 4 provides the background
on fc-ACQs that is necessary for achieving our main result. Section 5 gives a
detailed description of the color-index, while Section 6 shows how it can be
utilized for enumerating and counting the results of fc-ACQs. Section 7
provides a precise statement of our main result. We conclude in Section 8 with
a summary and an outlook on future work. Further details are provided an
appendix.

##  2 Preliminaries

We write $\mathbb{N}$ for the set of non-negative integers, and we let
$\mathbb{N}_{\scriptscriptstyle\geqslant 1}:=\mathbb{N}\setminus\\{0\\}$ and
$[n]:=\\{1,\ldots,n\\}$ for all $n\in\mathbb{N}_{\scriptscriptstyle\geqslant
1}$. Whenever $G$ denotes a graph (directed or undirected), we write $V(G)$
and $E(G)$ for the set of nodes and the set of edges of $G$. Given a set
$U\subseteq V(G)$, the subgraph of $G$ _induced_ by $U$ (for short: $G[U]$) is
the graph $G^{\prime}$ such that $V(G^{\prime})=U$ and $E(G^{\prime})$ is the
set of all $e\in E(G)$ such that both endpoints of $e$ belong to $U$. A
_connected component_ of an undirected graph is a maximal connected subgraph
of $G$. A _forest_ is an undirected acyclic graph; and a _tree_ is a connected
forest.

We usually write $\bar{a}=(a_{1},\ldots,a_{k})$ to denote a $k$-tuple (for
some arity $k\in\mathbb{N}$) and write $a_{i}$ to denote its $i$-th component.
Note that there is only one tuple of arity 0, namely, the _empty tuple_
denoted as $()$. For a $k$-tuple $\bar{a}$ and an $\ell$-tuple $\bar{c}$, we
write $\bar{a}{\cdot}\bar{c}$ or $\bar{a}\bar{c}$ for the $(k{+}\ell)$-tuple
$({a}_{1},\ldots,{a}_{k},{c}_{1},\ldots,{c}_{\ell})$. Given a function
$f\colon X\to Y$ and a $k$-tuple $\bar{x}$ of elements in $X$, we write
$f(\bar{x})$ for the $k$-tuple $(f({x}_{1}),\ldots,f({x}_{k}))$. For
$S\subseteq X^{k}$ we let $f(S)=\\{f(\bar{x})\,:\,\bar{x}\in S\\}$.

We fix a countably infinite set dom for the _domain_ of potential database
entries, which we also call _constants_. A _schema_ $\sigma$ is a finite, non-
empty set of relation symbols, where each $R\in\sigma$ is equipped with a
fixed arity $\operatorname{ar}(R)\in\mathbb{N}_{\scriptscriptstyle\geqslant
1}$. A schema $\sigma$ is called _binary_ if every $R\in\sigma$ has arity
$\operatorname{ar}(R)\leqslant 2$.

A _database_ $D$ of schema $\sigma$ ($\sigma$-db, for short) is a tuple of the
form $D=(R^{D})_{R\in\sigma}$, where $R^{D}$ is a finite subset of
$\textbf{dom}^{\operatorname{ar}(R)}$. The _active domain_ $\textrm{adom}(D)$
of $D$ is the smallest subset $S$ of dom such that $R^{D}\subseteq
S^{\operatorname{ar}(R)}$ for all $R\in\sigma$. The _size_ $|D|$ of $D$ is
defined as the total number of tuples in $D$, namely,
$|D|=\sum_{R\in\sigma}|R^{D}|$.

A $k$-ary _query_ (for $k\in\mathbb{N}$) of schema $\sigma$ ($\sigma$-query,
for short) is a syntactic object $Q$ which is associated with a function
${\left\llbracket Q\right\rrbracket}$ that maps every $\sigma$-db $D$ to a
finite subset of $\textbf{dom}^{k}$, and which is _generic_ in the following
sense. For every permutation $\pi$ of dom and every $\sigma$-db $D$ we have
$\pi({\left\llbracket Q\right\rrbracket}(D))={\left\llbracket
Q\right\rrbracket}(\pi(D))$, where $\pi(D)$ is the $\sigma$-db $D^{\prime}$
with $R^{D^{\prime}}:=\pi(R^{D})$ for all $R\in\sigma$. _Boolean_ queries are
$k$-ary queries for $k=0$ and _non-Boolean_ queries are $k$-ary queries with
$k\geqslant 1$. Note that there are only two relations of arity 0, namely,
$\emptyset$ and $\\{()\\}$. For a Boolean query $Q$ we write ${\left\llbracket
Q\right\rrbracket}(D)=\texttt{true}$ to indicate that $()\in{\left\llbracket
Q\right\rrbracket}(D)$, and we write ${\left\llbracket
Q\right\rrbracket}(D)=\texttt{false}$ to indicate that ${\left\llbracket
Q\right\rrbracket}(D)=\emptyset$. In this paper we will focus on the following
evaluation tasks for a given $\sigma$-db $D$:

  * •

Boolean query evaluation: On input of a Boolean $\sigma$-query $Q$, decide if
${\left\llbracket Q\right\rrbracket}(D)=\texttt{true}$.

  * •

Non-Boolean query evaluation: Upon input of a non-Boolean $\sigma$-query $Q$,
compute the relation ${\left\llbracket Q\right\rrbracket}(D)$.

  * •

Counting query evaluation: Upon input of a $\sigma$-query $Q$, compute the
number $|{\left\llbracket Q\right\rrbracket}(D)|$ of tuples in the result of
$Q$ on $D$.

Concerning the second task, we are mainly interested in finding an
_enumeration algorithm_ for computing the tuples in ${\left\llbracket
Q\right\rrbracket}(D)$. Such an algorithm consists of two phases: the
_preprocessing phase_ and the _enumeration phase_. In the preprocessing phase,
the algorithm is allowed to do arbitrary preprocessing to build a suitable
data structure $\textsf{{DS}}_{D,Q}$. In the enumeration phase, the algorithm
can use $\textsf{{DS}}_{D,Q}$ to enumerate all tuples in ${\left\llbracket
Q\right\rrbracket}(D)$ followed by an End-Of-Enumeration message EOE. We
require here that each tuple is enumerated exactly once (i.e., without
repetitions). The _delay_ is the maximum time that passes between the start of
the enumeration phase and the first output, between the output of two
consecutive tuples, and between the last tuple and EOE.

For our algorithms, we will assume the RAM-model with a uniform cost measure.
In particular, storing and accessing elements of dom requires $O(1)$ space and
time. This assumption implies that, for any $r$-ary relation $R^{D}$, we can
construct in time $O(r\cdot|R^{D}|)$ an index that allows to enumerate $R^{D}$
with $O(1)$ delay and to test for a given $r$-tuple $\bar{c}$ whether
$\bar{c}\in R^{D}$ in time $O(r)$. Furthermore, this implies that given any
finite partial function $f\colon A\to B$, we can build a _lookup table_ in
time $O(|\textrm{dom}(f)|)$, where $\textrm{dom}(f):=\\{x\in A\,:\,f(x)\text{
is defined}\\}$, and have access to $f(a)$ in constant time.

##  3 Indexing for Query Evaluation

In this section, we formalize the setting for _indexing for query evaluation_
for the tasks of Boolean (bool), non-Boolean (enum), and counting (count)
query evaluation for a given class $\mathcal{Q}$ of queries over a fixed
schema $\sigma$. We present here the general setting. Later, we will
instantiate it for a specific class of queries. The scenario is:

  1. (1)

As input we receive a $\sigma$-db $D$. We perform an _indexing phase_ in order
to build a suitable data structure $\textsf{{DS}}_{D}$. This data structure
shall be helpful later on to efficiently evaluate _any_ query
$Q\in\mathcal{Q}$.

  2. (2)

In the _evaluation phase_ we have access to $\textsf{{DS}}_{D}$. As input, we
receive arbitrary queries $Q\in\mathcal{Q}$ and one of the three task
descriptions bool, count, or enum, where bool is only allowed in case that $Q$
is a Boolean query. The goal is to solve this query evaluation task for $Q$ on
$D$.

This scenario resembles what happens in real-world database systems, where
indexes are built to ensure efficient access to the information stored in the
database, and subsequently these indexes are used for evaluating various input
queries. We formalize the problem as:

Problem: $\textup{{IndexingEval}}(\sigma,\mathcal{Q})$ Indexing:
$\left\\{\text{ \begin{tabular}[]{rl}{input:}&\\!\\!\\! a $\sigma$-db $D$\\\
{result:}&\\!\\!\\! a data structure $\textsf{{DS}}_{D}$\end{tabular}
}\right.$  Evaluation: $\left\\{\\!\\!\\!\text{
\begin{tabular}[]{rl}{input:}&\\!\\!\\! \parbox[t]{266.67867pt}{ a
$\sigma$-query $Q\in\mathcal{Q}$, and a task description in
$\\{\textsl{{bool}},\textsl{{enum}},\textsl{{count}}\\}$ }\\\
{output:}&\\!\\!\\! \parbox[t]{266.67867pt}{ the correct answer solving the
given task for ${\left\llbracket Q\right\rrbracket}(D)$ }\end{tabular}
}\right.$

The _indexing time_ is the time used for building the data structure
$\textsf{{DS}}_{D}$. It only depends on the input database $D$, and we usually
measure it by a function $f_{\operatorname{index}}(D)$ that provides an upper
bound on the time it takes to perform the indexing phase for $D$.

The time it takes to answer a Boolean query $Q$ on $D$ or for counting the
number of result tuples of a query $Q$ on $D$ depends on $Q$ and the
particular properties of the data structure $\textsf{{DS}}_{D}$. We usually
measure these times by functions $f_{\textsl{{bool}}}(Q,D)$ and
$f_{\textsl{{count}}}(Q,D)$ that provide an upper bound on the time it takes
to perform the task by utilizing the data structure $\textsf{{DS}}_{D}$.
Concerning the task enum, we measure the preprocessing time and the delay by
functions $f_{\operatorname{prep}}(Q,D)$ and $f_{\operatorname{delay}}(Q,D)$
that provide upper bounds on the time taken for preprocessing and the delay,
respectively, when using the data structure $\textsf{{DS}}_{D}$ to enumerate
${\left\llbracket Q\right\rrbracket}(D)$.

Note that for measuring running times we use $D$ and not $|D|$ (e.g.,
$f_{\textsl{{bool}}}(Q,D)$), because we want to allow the running time
analysis to be more fine-grained than just depending on the number of tuples
of $D$. The main result of this paper is a solution for
$\textup{{IndexingEval}}(\sigma,\mathcal{Q})$ where $\mathcal{Q}$ is the class
$\textsf{{fc-ACQ}}[\sigma]$ of all _free-connex acyclic conjunctive queries_
of a _binary_ schema $\sigma$ (i.e., all $R\in\sigma$ have arity
$\operatorname{ar}(R)\leqslant 2$).

##  4 Free-Connex Acyclic CQs

This section provides the necessary definitions and known results concerning
$\textsf{{fc-ACQ}}[\sigma]$. We fix a countably infinite set var of
_variables_ such that $\textbf{var}\cap\textbf{dom}=\emptyset$. An _atom_ $a$
of schema $\sigma$ is of the form $R(x_{1},\ldots,x_{r})$ where $R\in\sigma$,
$r=\operatorname{ar}(R)$, and $x_{1},\ldots,x_{r}\in\textbf{var}$. We write
$\textrm{vars}(a)$ for the set of variables occurring in $a$. Let
$k\in\mathbb{N}$. A $k$-ary _conjunctive query_ (CQ) of schema $\sigma$ is of
the form

$\textit{Ans}(z_{1},\ldots,z_{k})\leftarrow a_{1},\ldots,a_{d}$ (1)

where $d\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$, $a_{j}$ is an atom of
schema $\sigma$ for every $j\in[d]$, and $z_{1},\ldots,z_{k}$ are $k$ pairwise
distinct variables in $\bigcup_{j\in[d]}\textrm{vars}(a_{j})$. The expression
to the left (right) of $\leftarrow$ is called the _head_ (_body_) of the
query. For a CQ $Q$ of the form (1) we let
$\textrm{atoms}(Q)=\\{a_{1},\ldots,a_{d}\\}$,
$\textrm{vars}(Q)=\bigcup_{j\in[d]}\textrm{vars}(a_{j})$, and
$\textrm{free}(Q)=\\{z_{1},\ldots,z_{k}\\}$. The _(existentially) quantified_
variables are the elements in
$\textrm{quant}(Q):=\textrm{vars}(Q)\setminus\textrm{free}(Q)$. A CQ $Q$ is
called _Boolean_ if $\textrm{free}(Q)=\emptyset$, and it is called _full_ (or,
_quantifier-free_) if $\textrm{quant}(Q)=\emptyset$. The _size_ $|Q|$ of the
query is defined as $|\textrm{atoms}(Q)|$.

The semantics are defined as usual. A _valuation_ $\nu$ for $Q$ is a mapping
$\nu\colon\textrm{vars}(Q)\to\textbf{dom}$. A valuation $\nu$ is a
_homomorphism_ from $Q$ to a $\sigma$-db $D$ if for every atom
$R(x_{1},\ldots,x_{r})\in\textrm{atoms}(Q)$ we have
$(\nu(x_{1}),\ldots,\nu(x_{r}))\in R^{D}$. The _query result_ of a CQ $Q$ of
the form (1) on the $\sigma$-DB $D$ is defined as the set of tuples

${\left\llbracket
Q\right\rrbracket}(D)\;:=\;\\{\,(\nu(z_{1}),\ldots,\nu(z_{k}))\,:\,\nu\text{
is a homomorphism from $Q$ to $D$}\,\\}.$ (2)

The _hypergraph_ $H(Q)$ of a CQ $Q$ is defined as follows. Its vertex set is
$\textrm{vars}(Q)$, and it contains a hyperedge $\textrm{vars}(a)$ for every
$a\in\textrm{atoms}(Q)$. The _Gaifman graph_ $G(Q)$ of $Q$ is the undirected
simple graph with vertex set $\textrm{vars}(Q)$, and it contains the edge
$\\{x,y\\}$ whenever $x,y$ are distinct variables such that
$x,y\in\textrm{vars}(a)$ for some $a\in\textrm{atoms}(Q)$.

_Acyclic_ CQs and _free-connex acyclic_ CQs are standard notions studied in
the database theory literature (cf. [7, 10, 17, 6, 1]; see [9] for an
overview). A CQ $Q$ is called _acyclic_ if its hypergraph $H(Q)$ is _$\alpha$
-acyclic_, i.e., there exists an undirected tree $T=(V(T),E(T))$ (called a
_join-tree_ of $H(Q)$ and of $Q$) whose set of nodes $V(T)$ is precisely the
set of hyperedges of $H(Q)$, and where for each variable
$x\in\textrm{vars}(Q)$ the set $\\{t\in V(T)\,:\,x\in t\\}$ induces a
connected subtree of $T$. A CQ $Q$ is _free-connex acyclic_ if it is acyclic
_and_ the hypergraph obtained from $H(Q)$ by adding the hyperedge
$\textrm{free}(Q)$ is $\alpha$-acyclic.

Note that any CQ $Q$ that is either Boolean or full is free-connex acyclic iff
it is acyclic. However, $\textit{Ans}(x,z)\leftarrow R(x,y),R(y,z)$ is an
example of a query that is acyclic, but not free-connex acyclic.

For the special case of a _binary_ schema, there is a particularly simple
characterization of (free-connex) acyclic CQs that will be useful for our
purpose (see Appendix A for a proof).

######  Proposition 4.1 (Folklore).

A CQ $Q$ of a _binary_ schema $\sigma$ is _acyclic_ iff its Gaifman graph
$G(Q)$ is acyclic. The CQ $Q$ is _free-connex acyclic_ iff $G(Q)$ is acyclic
and the following statement is true: For every connected component $C$ of
$G(Q)$, the subgraph of $C$ induced by the set $\textrm{free}(Q)\cap V(C)$ is
connected or empty.

We write $\textsf{{fc-ACQ}}[\sigma]$ to denote the set of all free-connex
acyclic CQs of schema $\sigma$. In the following, we state two seminal results
by Yannakakis [34] and Bagan, Durand, and Grandjean [6] that will be crucial
for the main result of this paper.

######  Theorem 4.2 (Yannakakis [34]).

For every schema $\sigma$ there is an algorithm that receives as input a
$\sigma$-db $D$ and a Boolean acyclic CQ $Q$ of schema $\sigma$ and takes time
$O(|Q|{\cdot}|D|)$ to decide if ${\left\llbracket
Q\right\rrbracket}(D)=\texttt{true}$.

In the literature, Yannakakis’ result is often described in terms of _data
complexity_ , i.e., running time components that depend on the query are
hidden in the O-notation. Adopting this view, Yannakakis’ result states that
Boolean acyclic CQs can be evaluated with linear-time data complexity. Bagan,
Durand, and Grandjean [6] achieved an influential result for the task of
enumerating the set ${\left\llbracket Q\right\rrbracket}(D)$ for (non-Boolean)
_free-connex acyclic_ CQs $Q$: They found an enumeration algorithm with
$O(|D|)$ preprocessing time and constant delay. This statement refers to data
complexity, i.e., running time components that depend on the query are hidden
in the O-notation. Several proofs of (and different algorithms for) Bagan,
Durand and Grandjean’s theorem are available in the literature [6, 5, 12, 28,
21, 22, 23]; all of them focus on data complexity. For this paper we need a
more refined statement that takes into account the combined complexity of the
problem, and that is implicit in [9] (see Appendix A).

######  Theorem 4.3.

For every schema $\sigma$ there is an enumeration algorithm that receives as
input a $\sigma$-db $D$ and a query $Q\in\textsf{{fc-ACQ}}[\sigma]$ and that
computes within preprocessing time $O(|Q|{\cdot}|D|)$ a data structure for
enumerating ${\left\llbracket Q\right\rrbracket}(D)$ with delay
$O(|\textrm{free}(Q)|)$.

Our main result provides a solution for the problem
$\textup{{IndexingEval}}(\sigma,\textsf{{fc-ACQ}}[\sigma])$ for _binary_
schemas $\sigma$. The data structure $\textsf{{DS}}_{D}$ that we build for a
given database $D$ during the indexing phase will provide a new database
${D_{\operatorname{col}}}$. This database ${D_{\operatorname{col}}}$ is
potentially much smaller than $D$, and it will allow us to improve the
preprocessing time provided by Theorem 4.3 to
$O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$. At a first glance one may be
tempted to believe that it should be straightforward to generalize our result
from binary to arbitrary schemas by representing databases of a non-binary
schema $\sigma$ as databases of a suitably chosen binary schema
$\sigma^{\prime}$. However, the notion of fc-ACQs is quite subtle, and an fc-
ACQ of schema $\sigma$ might translate into a CQ of schema $\sigma^{\prime}$
that is not an fc-ACQ (see Appendix A.3 for an example), hence prohibiting to
straightforwardly reduce the case of general schemas to our results for fc-
ACQs over binary schemas.

##  5 Construction of the color-index

For the remainder of this paper let us fix an arbitrary _binary_ schema
$\sigma$, i.e., every $R\in\sigma$ has arity $\operatorname{ar}(R)\leqslant
2$. Our main result is a solution for
$\textup{{IndexingEval}}(\sigma,\textsf{{fc-ACQ}}[\sigma])$. In this section,
we describe the indexing phase of our solution. Upon input of a $\sigma$-db
$D$, we will build a data structure $\textsf{{DS}}_{D}$ that we call the
_color-index_ for $\textsf{{fc-ACQ}}[\sigma]$. To describe this data
structure, we need the following notions.

#### Graph representation

Let $D$ be a $\sigma$-db that we receive as input. We start by encoding self-
loops in $D$ into unary predicates. Let $\bar{\sigma}$ be the schema obtained
by inserting into $\sigma$ a new unary relation symbol $S_{R}$ for every
$R\in\sigma$ with $\operatorname{ar}(R)=2$. We turn $D$ into a
$\bar{\sigma}$-db $\bar{D}$ by letting $R^{\bar{D}}=R^{D}$ for every
$R\in\sigma$, and $S_{R}^{\bar{D}}:=\\{(v)\,:\,(v,v)\in R^{D}\\}$ for every
$R\in\sigma$ with $\operatorname{ar}(R)=2$. Thus, relation $S_{R}$ of
$\bar{D}$ consists of all elements $v$ such that $(v,v)\in R^{D}$ (i.e.,
$(v,v)$ is a _self-loop_ w.r.t. $R$ in $D$). Note that self-loops are still
present in each binary relation $R$, and $S_{R}$ is a redundant representation
of these self-loops. Clearly, the size of $\bar{D}$ is linear in the size of
$D$.

We represent $\bar{D}$ as a vertex-labeled and edge-labeled directed graph
$\bar{G}=(\bar{V},\bar{E},\textnormal{{vl}},\textnormal{{el}})$ as follows:
$\bar{V}=\textrm{adom}(D)$ and $\bar{E}$ consists of all directed edges
$(v,w)$ such that $v\neq w$ and $(v,w)\in R^{\bar{D}}$ or $(w,v)\in
R^{\bar{D}}$ for some $R\in\bar{\sigma}$ with $\operatorname{ar}(R)=2$.
Further, we define the vertex- and edge-labeling functions vl and el:

$\displaystyle\textnormal{{vl}}(v)\;\;$ $\displaystyle:=\;\;\;$
$\displaystyle\\{\,U\in\bar{\sigma}\,:\,\operatorname{ar}(U)=1,\ (v)\in
U^{\bar{D}}\,\\}\vskip 3.0pt plus 1.0pt minus 1.0pt$
$\displaystyle\textnormal{{el}}(v,w)\;\;$ $\displaystyle:=$
$\displaystyle\\{\,(R,\rightarrow)\,:\,R\in\bar{\sigma},\
\operatorname{ar}(R)=2,\ (v,w)\in R^{\bar{D}}\,\\}\ \,\cup$
$\displaystyle\\{\,(R,\leftarrow)\,:\,R\in\bar{\sigma},\
\operatorname{ar}(R)=2,\ (w,v)\in R^{\bar{D}}\,\\}$

for every vertex $v\in\bar{V}$ and every edge $(v,w)\in\bar{E}$.

Note that $(\bar{V},\bar{E})$ is a self-loop-free simple and symmetric
directed graph. Self-loops present in $D$ are not represented by (labeled)
edges but by vertex-labels in $\bar{G}$ (to enable this, we moved over from
$D$ to $\bar{D}$). For every edge $(v,w)\in\bar{E}$, the label
$\textnormal{{el}}(v,w)$ determines the label $\textnormal{{el}}(w,v)$ of the
corresponding “backwards edge” as follows. If
$\textnormal{{el}}(v,w)=\lambda$, then
$\textnormal{{el}}(w,v)=\widetilde{\lambda}$ for the _dual_ label
$\widetilde{\lambda}:=\\{(R,\rightarrow)\,:\,(R,\leftarrow)\in\lambda\\}\cup\\{(R,\leftarrow)\,:\,(R,\rightarrow)\in\lambda\\}$.

Let $L_{\bar{V}}:=\textrm{img}(\textnormal{{vl}})$ and
$L_{\bar{E}}:=\textrm{img}(\textnormal{{el}})$ be the sets of labels that are
actually used as vertex labels and edge labels, respectively, of $\bar{G}$.
One can easily check that $\bar{G}$ can be generated in time $O(|\bar{D}|)$,
and $|\bar{E}|=O(|\bar{D}|)$. Furthermore, although the number of potential
labels of vl and el could be exponential in $|\bar{\sigma}|$, it holds that
the number of actual labels $|L_{\bar{V}}|$ and $|L_{\bar{E}}|$ is at most
linear in $|\bar{D}|$.

######  Example 5.1.

Consider the following running example about movies and actors taken almost
verbatim from [2, Fig. 2]. The schema $\sigma^{\operatorname{ex}}$ has four
binary relations symbols Plays, ActedBy, Movie, and Screentime (denoted by P,
A, M, and S), and the database $D^{\operatorname{ex}}$ has the following
relations and tuples:

| P |  |
---|---|---
| PS | LM
| PS | MM
| A |  |
---|---|---
| LM | PS
| MM | PS
| M |  |
---|---|---
| LM | Dr.S
| MM | Dr.S
| S |  |
---|---|---
| LM | 18m
| MM | 34m

where Peter Sellers (PS) is an actor who plays as Lionel Mandrake (LM) and
Merkin Muffley (MM) in the same movie “Dr. Strangelove” (Dr.S). Each character
appears 18 minutes (18m) and 34 minutes (34m) in the movie, respectively. In
Figure 1(a), we show its corresponding vertex-labeled and edge-labeled
directed graph $\bar{G}^{\operatorname{ex}}$.  $\lrcorner$

PSLM18mDr.SMM34m$(\textbf{P},\rightarrow),(\textbf{A},\leftarrow)$$(\textbf{P},\leftarrow),(\textbf{A},\rightarrow)$$(\textbf{P},\leftarrow),(\textbf{A},\rightarrow)$$(\textbf{P},\rightarrow),(\textbf{A},\leftarrow)$$(\textbf{M},\leftarrow)$$(\textbf{M},\rightarrow)$$(\textbf{M},\rightarrow)$$(\textbf{M},\leftarrow)$$(\textbf{S},\leftarrow)\,$$(\textbf{S},\rightarrow)$$(\textbf{S},\rightarrow)$$\,(\textbf{S},\leftarrow)$
(a)

BRYGRY$(\textbf{P},\rightarrow),(\textbf{A},\leftarrow)$$(\textbf{P},\leftarrow),(\textbf{A},\rightarrow)$$(\textbf{P},\leftarrow),(\textbf{A},\rightarrow)$$(\textbf{P},\rightarrow),(\textbf{A},\leftarrow)$$(\textbf{M},\leftarrow)$$(\textbf{M},\rightarrow)$$(\textbf{M},\rightarrow)$$(\textbf{M},\leftarrow)$$(\textbf{S},\leftarrow)$$(\textbf{S},\rightarrow)$$(\textbf{S},\rightarrow)$$(\textbf{S},\leftarrow)$
(b)

BRYG$(\textbf{P},\rightarrow),(\textbf{A},\leftarrow)$$(\textbf{P},\leftarrow),(\textbf{A},\rightarrow)$$(\textbf{M},\leftarrow)$$(\textbf{M},\rightarrow)$$(\textbf{S},\rightarrow)$$(\textbf{S},\leftarrow)$
(c)

Figure 1: (a) shows the graph $\bar{G}^{\operatorname{ex}}$ representing the
database $D^{\operatorname{ex}}$ from Example 5.1 (all vertices $v$ have the
same label $\textnormal{{vl}}(v)=\emptyset$), (b) shows a coarsest stable
coloring of $\bar{G}^{\operatorname{ex}}$, and (c) shows a graph representing
the color database $D^{\operatorname{ex}}_{\operatorname{col}}$ of
$D^{\operatorname{ex}}$.

#### Color refinement

Once having produced $\bar{G}$, we apply to it a suitable variant of the well-
known _color refinement_ algorithm. A high-level description of this
algorithm, basically taken from [8], is as follows. The algorithm classifies
the vertices of $\bar{G}$ by iteratively refining a coloring of the vertices.
Initially, each vertex $v$ has color $\textnormal{{vl}}(v)$. Then, in each
step of the iteration, two vertices $v,w$ that currently have the same color
get different refined colors if for some color $c$ of the currently used
vertex-colors and for some edge-label $\lambda\in L_{\bar{E}}$, we have
${\\#}_{\rightarrow}^{\lambda}({v},{c})\neq{\\#}_{\rightarrow}^{\lambda}({w},{c})$.
Here, for any vertex $u$ of $\bar{G}$, we let
${\\#}_{\rightarrow}^{\lambda}({u},{c}):=|{N}_{\rightarrow}^{\lambda}({u},{c})|$
where ${N}_{\rightarrow}^{\lambda}({u},{c})$ denotes the set of all outgoing
$\bar{E}$-neighbors $u^{\prime}$ of $u$ (i.e., $(u,u^{\prime})\in\bar{E}$)
such that $\textnormal{{el}}(u,u^{\prime})=\lambda$ and $u^{\prime}$ has color
$c$. The process stops if no further refinement is achieved, resulting in a
_stable coloring_ of the vertices.

In [8], Berkholz, Bonsma, and Grohe showed that this can be implemented in
such a way that it runs in time $O((|\bar{V}|+|\bar{E}|)\log|\bar{V}|)$. To
formally state their result, we need the following notation. Let
$f\colon\bar{V}\to S$ be a function, where $S$ is any set. We say that a
function $\textnormal{{col}}\colon\bar{V}\to C$ _refines_ $f$ iff for all
$v,w\in\bar{V}$ with $\textnormal{{col}}(v)=\textnormal{{col}}(w)$ we have
$f(v)=f(w)$. Further, we say that col _is stable_ iff for all $v,w\in\bar{V}$
with $\textnormal{{col}}(v)=\textnormal{{col}}(w)$, and for every edge-label
$\lambda\in L_{\bar{E}}$ and for every color $c\in C$ we have:
${\\#}_{\rightarrow}^{\lambda}({v},{c})={\\#}_{\rightarrow}^{\lambda}({w},{c})$.
Finally, col is a _coarsest stable coloring that refines vl_ iff col is
stable, col refines vl, and for every coloring
$\textnormal{{col}}^{\prime}\colon\bar{V}\to C^{\prime}$ (for some set
$C^{\prime}$) that is stable and that refines vl we have:
$\textnormal{{col}}^{\prime}$ refines col. The main result of [8] implies the
following theorem (see Appendix B for details).

######  Theorem 5.2 ([8]).

For any vertex-labeled and edge-labeled directed simple graph
$\bar{G}=(\bar{V},\bar{E},\textnormal{{vl}},\textnormal{{el}})$, within time
$O((|\bar{V}|+|\bar{E}|)\log|\bar{V}|)$ one can compute a coloring
$\textnormal{{col}}\colon\bar{V}\to C$ (for a suitably chosen set $C$), such
that col is a coarsest stable coloring that refines vl.

In the indexing phase, we apply the algorithm provided by Theorem 5.2 to
$\bar{G}$. Let $f_{\operatorname{col}}(\bar{D})$ denote the time taken for
this, and note that $f_{\operatorname{col}}(\bar{D})\in
O(|\bar{D}|\cdot\log|\textrm{adom}(\bar{D})|)$. Note that this is the _worst-
case_ complexity; in case that $\bar{D}$ has a particularly simple structure,
the algorithm may terminate already in time $O(|\bar{D}|)$.

As a result we obtain a _coarsest stable coloring
$\textnormal{{col}}\colon\textrm{adom}(\bar{D})\to C$ that refines vl_, for a
suitable set $C$. Note that the number $|\textrm{img}(\textnormal{{col}})|$ of
colors used by col is the smallest number possible in order to obtain a stable
coloring that refines vl, and, moreover, the coarsest stable coloring that
refines vl is _unique_ up to a renaming of colors.

######  Example 5.3.

Figure 1(b) displays a stable coloring of the graph
$\bar{G}^{\operatorname{ex}}$ (Figure 1(a)) that corresponds to the database
$D^{\operatorname{ex}}$ presented in Example 5.1. For presentation, vertices
are labeled with their corresponding colors (blue (B), red (R), green (G),
yellow (Y)). The reader can check that this is the coarsest stable coloring
that refines vl (in this case vl is trivial).  $\lrcorner$

Note that although nodes with the same color are “isomorphic” in the previous
example (in the sense that there is an isomorphism of the graph onto itself
that maps a node of this color to any other node of the same color), this is
not always true. One can see that in the graph  all black nodes will receive
the same color, although the black nodes on the left component are not
“isomorphic” to the black nodes in the right component.

For later use let us summarize some crucial properties of col. Analogously to
${N}_{\rightarrow}^{\lambda}({u},{c})$ and
${\\#}_{\rightarrow}^{\lambda}({u},{c})$, let
${\\#}_{\leftarrow}^{\lambda}({u},{c}):=|{N}_{\leftarrow}^{\lambda}({u},{c})|$,
where ${N}_{\leftarrow}^{\lambda}({u},{c})$ denotes all incoming
$\bar{E}$-neighbors $u^{\prime}$ of $u$ (i.e., $(u^{\prime},u)\in\bar{E}$)
such that $\textnormal{{el}}(u^{\prime},u)=\lambda$ and
$\textnormal{{col}}(u^{\prime})=c$.

######  Fact 5.4.

For all $v,w\in\bar{V}$ with $\textnormal{{col}}(v)=\textnormal{{col}}(w)$, we
have:

  1. (a)

$\textnormal{{vl}}(v)=\textnormal{{vl}}(w)$, and

  2. (b)

${\\#}_{\rightarrow}^{\lambda}({v},{c})={\\#}_{\rightarrow}^{\lambda}({w},{c})$
for all $\lambda\in L_{\bar{E}}$ and all $c\in C$, and

  3. (c)

${\\#}_{\leftarrow}^{\lambda}({v},{c})={\\#}_{\leftarrow}^{\lambda}({w},{c})$
for all $\lambda\in L_{\bar{E}}$ and all $c\in C$.

###### Proof.

(a) and (b) are met because col is a refinement of vl and col is stable. (c)
follows from (b) because $\bar{E}$ is symmetric and the label of a backward
edge is the dual of the label of the corresponding forward edge, and hence
${N}_{\leftarrow}^{\lambda}({v},{c})={N}_{\rightarrow}^{\widetilde{\lambda}}({v},{c})$.
∎

We now proceed to the final step of the indexing phase, in which we use col to
build the so-called _color-index_ data structure.

#### The color-index

To describe the color-index structure $\textsf{{DS}}_{D}$, we use the
following notation. For all $c,c^{\prime}\in C$ and every edge-label $\lambda$
we let
${\\#}_{\rightarrow}^{\lambda}({c},{c^{\prime}}):={\\#}_{\rightarrow}^{\lambda}({v},{c^{\prime}})$
for some (and hence, for every, by Fact 5.4) $v\in\bar{V}$ with
$\textnormal{{col}}(v)=c$. For every potential edge-label $\lambda$ (i.e.,
$\lambda\subseteq\\{(R,\rightarrow),\,(R,\leftarrow)\,:\,R\in\bar{\sigma},\,\operatorname{ar}(R)=2\\}$
with $\lambda\neq\emptyset$) we let

$\displaystyle{\widehat{\\#}}_{\rightarrow}^{\lambda}({c},{c^{\prime}})$
$\displaystyle\ :=\
\sum_{\lambda^{\prime}\supseteq\lambda}{\\#}_{\rightarrow}^{\lambda^{\prime}}({c},{c^{\prime}})$
and $\displaystyle{\widehat{N}}_{\rightarrow}^{\lambda}({v},{c})$
$\displaystyle\ :=\
\bigcup_{\lambda^{\prime}\supseteq\lambda}{N}_{\rightarrow}^{\lambda^{\prime}}({v},{c})\;,$

where the considered $\lambda^{\prime}$ are actual edge-labels in
$L_{\bar{E}}$. The reason why we exclude $\lambda=\emptyset$ is that we do not
need it. Including it would only unnecessarily blow up the number of tuples
present in ${D_{\operatorname{col}}}$. The data structure $\textsf{{DS}}_{D}$
that we build during the indexing phase consists of the following five
components:

  1. (1)

the schema $\bar{\sigma}$ and the $\bar{\sigma}$-db $\bar{D}$;

  2. (2)

a lookup table to access the color $\textnormal{{col}}(v)$ given a vertex
$v\in\bar{V}$, and an (inverse) lookup table to access the set
$\\{v\in\bar{V}\,:\,\textnormal{{col}}(v)=c\\}$ given a $c\in C$, plus the
number $n_{c}$ of elements in this set;

  3. (3)

lookup tables to access the set
${\widehat{N}}_{\rightarrow}^{\lambda}({v},{c})$, given a potential edge-label
$\lambda$, a vertex $v\in\bar{V}$, and a color $c\in C$;

  4. (4)

lookup tables to access the number
${\widehat{\\#}}_{\rightarrow}^{\lambda}({c},{c^{\prime}})$, given a potential
edge-label $\lambda$ and colors $c,c^{\prime}\in C$;

  5. (5)

the _color database_ ${D_{\operatorname{col}}}$ of the _color schema_
$\sigma_{\operatorname{col}}$ defined as follows:

     * •

The schema $\sigma_{\operatorname{col}}$ consists of all the _unary_ relation
symbols of $\bar{\sigma}$ and a binary relation symbol $E_{\lambda}$ for every
potential edge-label $\lambda$ (i.e.,
$\lambda\subseteq\\{(R,\rightarrow),\,(R,\leftarrow)\,:\,R\in\bar{\sigma},\,\operatorname{ar}(R)=2\\}$
with $\lambda\neq\emptyset$).

     * •

The $\sigma_{\operatorname{col}}$-db ${D_{\operatorname{col}}}$ is defined as
follows. For each unary relation symbol $U\in\bar{\sigma}$ we let
$U^{{D_{\operatorname{col}}}}$ be the set of unary tuples $(c)$ for all $c\in
C$ such that there is a $(v)\in U^{\bar{D}}$ with $\textnormal{{col}}(v)=c$.
For every potential edge-label $\lambda$ we let
$E_{\lambda}^{{D_{\operatorname{col}}}}$ be the set of all tuples
$(c,c^{\prime})\in C\times C$ such that
${\widehat{\\#}}_{\rightarrow}^{\lambda}({c},{c^{\prime}})>0$. Note that
$\textrm{adom}({D_{\operatorname{col}}})=C$.

######  Example 5.5.

For our example database $D^{\operatorname{ex}}$ (Example 5.1), one can check
that the corresponding color database
$D^{\operatorname{ex}}_{\operatorname{col}}$ is:

| $E_{\\{(\textbf{P},\rightarrow),(\textbf{A},\leftarrow)\\}}$ |  |
---|---|---
| B | R
| $E_{\\{(\textbf{S},\rightarrow)\\}}$ |  |
---|---|---
| R | Y
| $E_{\\{(\textbf{M},\rightarrow)\\}}$ |  |
---|---|---
| R | G
| $E_{\\{(\textbf{P},\leftarrow),(\textbf{A},\rightarrow)\\}}$ |  |
---|---|---
| R | B
| $E_{\\{(\textbf{S},\leftarrow)\\}}$ |  |
---|---|---
| Y | R
| $E_{\\{(\textbf{M},\leftarrow)\\}}$ |  |
---|---|---
| G | R

Further,
$E^{D^{\operatorname{ex}}_{\operatorname{col}}}_{\\{(\textbf{P},\rightarrow)\\}}=E^{D^{\operatorname{ex}}_{\operatorname{col}}}_{\\{(\textbf{A},\leftarrow)\\}}=E^{D^{\operatorname{ex}}_{\operatorname{col}}}_{\\{(\textbf{P},\rightarrow),(\textbf{A},\leftarrow)\\}}$,
$E^{D^{\operatorname{ex}}_{\operatorname{col}}}_{\\{(\textbf{P},\leftarrow)\\}}=E^{D^{\operatorname{ex}}_{\operatorname{col}}}_{\\{(\textbf{A},\rightarrow)\\}}=E^{D^{\operatorname{ex}}_{\operatorname{col}}}_{\\{(\textbf{P},\leftarrow),(\textbf{A},\rightarrow)\\}}$
and $E^{D^{\operatorname{ex}}_{\operatorname{col}}}_{\lambda}=\emptyset$ for
all the remaining potential edge-labels $\lambda$. In Figure 1(c), we present
a graph representing the tuples of
$D^{\operatorname{ex}}_{\operatorname{col}}$.  $\lrcorner$

Note that after having performed the color refinement algorithm (taking time
$f_{\operatorname{col}}(D)$), all the components (1)–(5) of
$\textsf{{DS}}_{D}$ can be built in total time $O(|D|)$. (Recall from the
problem statement in Section 3 that the schema $\sigma$ is fixed and not part
of the input. Thus, the exponential dependency on $\sigma$ caused by
considering all potential edge labels is suppressed by the O-notation. In
Appendix D we outline how the exponential dependency on $\sigma$ can be
avoided.) In summary, the indexing phase takes time
$f_{\operatorname{col}}(D)+O(|D|)$. The color-index database
${D_{\operatorname{col}}}$ has size $O(|D|)$ in the _worst case_ ; but
$|{D_{\operatorname{col}}}|$ might be substantially smaller than $|D|$ in case
that $D$ has a particularly well-behaved structure. We formalize this
statement in the following result.

######  Proposition 5.6.

There is a database family ${\\{D^{n}\\}}_{n\geqslant 3}$ with
$|D^{n}|\in\Theta(n)$ but $|{D^{n}_{\operatorname{col}}}|\in O(1)$.

###### Proof.

Let $\sigma=\\{R\\}$ with $\operatorname{ar}(R)=2$. For $n\in\mathbb{N}$ with
$n\geqslant 3$ let $D^{n}$ be the $\sigma$-db $D$ with active domain $[n]$,
where the relation $R^{D}$ consists of the tuple $(n,1)$ and the tuples
$(i,i{+}1)$ for all $i<n$. I.e., $D$ is a directed cycle on $n$ nodes. Note
that $\bar{D}=D$. The graph
$\bar{G}=(\bar{V},\bar{E},\textnormal{{vl}},\textnormal{{el}})$ looks as
follows: $\bar{V}=[n]$, $\bar{E}=R^{D}\cup\\{(j,i)\,:\,(i,j)\in R^{D}\\}$,
$\textnormal{{vl}}(i)=\emptyset$ for every $i\in[n]$, and for every $(i,j)\in
R^{D}$ we have $\textnormal{{el}}(i,j)=\\{(R,\rightarrow)\\}$ and
$\textnormal{{el}}(j,i)=\\{(R,\leftarrow)\\}$.

The color refinement algorithm will stop after time
$f_{\operatorname{col}}(\bar{D})=O(n)$ by assigning each node $i\in[n]$ the
same color $\textnormal{{col}}(i)=c$, where $C=\\{c\\}$ consists of only one
color (note that this is a coarsest stable coloring of $\bar{G}$ that refines
vl).

Clearly, $L_{\bar{E}}$ consists of only the edge-labels
$\\{(R,\rightarrow)\\}$ and $\\{(R,\leftarrow)\\}$, and
${\\#}_{\rightarrow}^{\\{(R,\rightarrow)\\}}({c},{c})=1$ and
${\\#}_{\rightarrow}^{\\{(R,\leftarrow)\\}}({c},{c})=1$. Thus,
${\widehat{\\#}}_{\rightarrow}^{\\{(R,\rightarrow)\\}}({c},{c})=1={\widehat{\\#}}_{\rightarrow}^{\\{(R,\leftarrow)\\}}({c},{c})$.
Furthermore, for
$\lambda_{\textit{max}}:=\\{(R,\rightarrow),\allowbreak(R,\leftarrow)\\}$ we
have ${\widehat{\\#}}_{\rightarrow}^{\lambda_{\textit{max}}}({c},{c})=0$.

In summary, ${D_{\operatorname{col}}}$ is the database with active domain
$C=\\{c\\}$, and with relations
$E^{{D_{\operatorname{col}}}}_{\\{(R,\rightarrow)\\}}=E^{{D_{\operatorname{col}}}}_{\\{(R,\leftarrow)\\}}=\\{(c,c)\\}$
and $E^{{D_{\operatorname{col}}}}_{\lambda_{\textit{max}}}=\emptyset$. In
particular, $|{D_{\operatorname{col}}}|=2$, while $|D|=n$. ∎

Note that we define the color-index (and, in particular,
$\sigma_{\operatorname{col}}$ and ${D_{\operatorname{col}}}$) considering the
binary relation symbols $E_{\lambda}$ for every potential edge-label
$\lambda$, i.e.,
$\lambda\subseteq\\{\mbox{(R,$\rightarrow$)},\allowbreak(R,\leftarrow)\,:\,R\in\bar{\sigma},\,\operatorname{ar}(R)=2\\}$
with $\lambda\neq\emptyset$. This implies an exponential blow-up on
$|\sigma|$. However, given that we assume that $\sigma$ is fixed, this blow-up
is a constant factor in the running time. By spending some more effort, one
can avoid the exponential blow-up on $|\sigma|$ entirely; details on this can
be found in Appendix D.

##  6 Evaluation using the color-index

This section shows how to use the color-index $\textsf{{DS}}_{D}$ to evaluate
any free-connex acyclic CQ $Q$ over $D$. I.e., we describe the _evaluation
phase_ of our solution for $\textup{{IndexingEval}}(\sigma,\textsf{{fc-
ACQ}}[\sigma])$. We assume that the color-index $\textsf{{DS}}_{D}$ (including
the color database ${D_{\operatorname{col}}}$) of the given database $D$ has
already been built during the indexing phase. Let $Q\in\textsf{{fc-
ACQ}}[\sigma]$ be an arbitrary query that we may receive as an input during
the evaluation phase. We first explain how the evaluation tasks can be
simplified by focusing on _connected_ queries.

#### Connected queries

We say that a CQ $Q$ is _connected_ iff its Gaifman graph $G(Q)$ is connected.
Intuitively, if a CQ $Q$ is not connected, then we can write $Q$ as

$\textit{Ans}(\bar{z}_{1},\ldots,\bar{z}_{\ell})\ \leftarrow\
\bar{\alpha}_{1}(\bar{z}_{1},\bar{y}_{1}),\ldots,\bar{\alpha}_{\ell}(\bar{z}_{\ell},\bar{y}_{\ell})$

such that each $\bar{\alpha}_{i}(\bar{z}_{i},\bar{y}_{i})$ is a sequence of
atoms, $\textrm{vars}(\bar{\alpha}_{i}(\bar{z}_{i},\bar{y}_{i}))$ and
$\textrm{vars}(\bar{\alpha}_{j}(\bar{z}_{j},\bar{y}_{j}))$ are disjoint for
$i\neq j$, and for each $i\in[\ell]$ the CQ
$Q_{i}:=\textit{Ans}(\bar{z}_{i})\leftarrow\bar{\alpha}_{i}(\bar{z}_{i},\bar{y}_{i})$
is connected. To simplify notation we assume w.l.o.g. that in the head of $Q$
the variables are ordered in exactly the same way as in the list
$\bar{z}_{1},\ldots,\bar{z}_{\ell}$. One can easily check that this
decomposition satisfies

${\left\llbracket Q\right\rrbracket}(D)={\left\llbracket
Q_{1}\right\rrbracket}(D)\times\cdots\times{\left\llbracket
Q_{\ell}\right\rrbracket}(D)\qquad\text{and}\qquad|{\left\llbracket
Q\right\rrbracket}(D)|=|{\left\llbracket
Q_{1}\right\rrbracket}(D)|\cdot\ldots\cdot|{\left\llbracket
Q_{\ell}\right\rrbracket}(D)|$

for every $\sigma$-db $D$. Then, we can compute $|{\left\llbracket
Q\right\rrbracket}(D)|$ by first computing each number $|{\left\llbracket
Q_{i}\right\rrbracket}(D)|$ and then multiplying all values in $O(|Q|)$-time.
Similarly, for enumerating ${\left\llbracket Q\right\rrbracket}(D)$ one can
convert constant-delay enumeration algorithms for $Q_{1},\ldots,Q_{\ell}$ into
one for $Q$ by iterating in nested loops over the outputs of ${\left\llbracket
Q_{1}\right\rrbracket}(D),\ldots,\allowbreak{\left\llbracket
Q_{\ell}\right\rrbracket}(D)$. By the previous argument, in the following we
will concentrate on the evaluation of _connected_ CQs without loss of
generality. For the remainder of this section, let us fix an arbitrary
_connected_ CQ $Q\in\textsf{{fc-ACQ}}[\sigma]$ and assume that its head is of
the form $\textit{Ans}(x_{1},\ldots,x_{k})$ (with $k\geqslant 0$).

#### The modified query $\bar{Q}$

When receiving the connected query $Q\in\textsf{{fc-ACQ}}[\sigma]$ with head
$\textit{Ans}(x_{1},\ldots,x_{k})$, the first step is to remove the self-loops
of $Q$. I.e., we translate $Q$ into the query $\bar{Q}$ over schema
$\bar{\sigma}$ as follows: $\bar{Q}$ is obtained from $Q$ by replacing every
atom of the form $R(x,x)$ with the atom $S_{R}(x)$. Obviously, the Gaifman
graph of the query remains unchanged, i.e., $G(\bar{Q})=G(Q)$. Clearly,
$\bar{Q}$ is a connected query in $\textsf{{fc-ACQ}}[\bar{\sigma}]$ such that
${\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})={\left\llbracket
Q\right\rrbracket}(D)$, and $\bar{Q}$ is _self-loop-free_ , i.e., every binary
atom of $\bar{Q}$ is of the form $R(x,y)$ with $x\neq y$ and $R\in\sigma$ with
$\operatorname{ar}(R)=2$.

#### The color query ${Q_{\operatorname{col}}}$

Next, we transform $\bar{Q}$ into a query ${Q_{\operatorname{col}}}$ of schema
$\sigma_{\operatorname{col}}$. We start by picking an arbitrary variable $r$
in $\textrm{free}(\bar{Q})$, and if $\bar{Q}$ is a Boolean query (i.e.,
$\textrm{free}(\bar{Q})=\emptyset$), then we pick $r$ as an arbitrary variable
in $\textrm{vars}(\bar{Q})$. This $r$ will be fixed throughout the remainder
of this section.

Since $\bar{Q}$ is connected and $\bar{Q}\in\textsf{{fc-ACQ}}[\bar{\sigma}]$,
the following is obtained from Proposition 4.1: Picking $r$ as the _root node_
turns the Gaifman graph $G(\bar{Q})$ into a rooted tree $T$. Furthermore,
there exists a strict linear order $<$ on $\textrm{vars}(\bar{Q})$ that is
compatible with the descendant relation of the rooted tree $T$ (i.e., for all
$x,y\in\textrm{vars}(\bar{Q})$ such that $x\neq y$ and $y$ is a descendant of
$x$ in $T$, we have $x<y$) _and_ that satisfies $x<y$ for all variables
$x\in\textrm{free}(\bar{Q})$ and $y\in\textrm{quant}(\bar{Q})$. Such a $<$ can
be obtained based on a variant of breadth-first search of $G(\bar{Q})$ that
starts with the root node $r$ and that prioritizes free over quantified
variables using separate queues for free and for quantified variables. We
choose an arbitrary such order $<$, and we fix it throughout the remainder of
this section. We will henceforth assume that $r=x_{1}$ and that
$x_{1}<x_{2}<\cdots<x_{k}$ (by reordering the variables $x_{1},\ldots,x_{k}$
in the head of $\bar{Q}$ and $Q$, this can be achieved without loss of
generality).

Based on $\bar{Q}$ and our choice of $<$, we construct the _color query_
${Q_{\operatorname{col}}}$ of schema $\sigma_{\operatorname{col}}$ by using
the following procedure. The query ${Q_{\operatorname{col}}}$ has exactly the
same head as $\bar{Q}$ (and $Q$). We initialize
$\textrm{atoms}({Q_{\operatorname{col}}})$ to consist of all the _unary_ atoms
of $\bar{Q}$. Afterwards we loop through all edges $e$ of the Gaifman graph
$G(\bar{Q})$ and proceed as follows. Let $e=\\{x,y\\}$ with $x<y$. Initialize
$\lambda_{e}$ to be the empty set. For every $R\in\bar{\sigma}$ such that
$R(x,y)\in\textrm{atoms}(\bar{Q})$, insert into $\lambda_{e}$ the tuple
$(R,\rightarrow)$. For every $R\in\sigma$ such that
$R(y,x)\in\textrm{atoms}(\bar{Q})$, insert into $\lambda_{e}$ the tuple
$(R,\leftarrow)$. After having completed the construction of $\lambda_{e}$, we
insert into $\textrm{atoms}({Q_{\operatorname{col}}})$ the atom
$E_{\lambda_{e}}(x,y)$ (note that $\lambda_{e}\neq\emptyset$).

######  Example 6.1.

Let $\sigma=\\{R\\}$ with $\operatorname{ar}(R)=2$, and let $Q$ be the query

$\textit{Ans}(x_{1},x_{2})\leftarrow
R(x_{1},x_{2}),R(x_{3},x_{1}),R(x_{2},x_{2}).$

By Proposition 4.1 it is easy to see that $Q\in\textsf{{fc-ACQ}}[\sigma]$.
Note that $\bar{\sigma}=\\{R,S_{R}\\}$, and $\bar{Q}$ is:
$\textit{Ans}(x_{1},x_{2})\;\leftarrow\;R(x_{1},x_{2}),\,R(x_{3},x_{1}),\,S_{R}(x_{2}).$

Choosing $x_{1}$ as the root of the Gaifman graph $G(\bar{Q})$, letting
$x_{1}<x_{2}<x_{3}$, we get that
$\lambda_{\\{x_{1},x_{2}\\}}=\\{(R,\rightarrow)\\}$, and
$\lambda_{\\{x_{1},x_{3}\\}}=\\{(R,\leftarrow)\\}$. Furthermore,
${Q_{\operatorname{col}}}$ is the query:

$\textit{Ans}(x_{1},x_{2})\;\leftarrow\;S_{R}(x_{2}),\,E_{\\{(R,\rightarrow)\\}}(x_{1},x_{2}),\,E_{\\{(R,\leftarrow)\\}}(x_{1},x_{3})\,.$

Recall that when defining the color query ${Q_{\operatorname{col}}}$, we
defined labels $\lambda_{e}$ for every edge $e$ of the Gaifman graph
$G(\bar{Q})$. For every node $x$ of $G(\bar{Q})$, we let $\lambda_{x}$ be the
set of all unary relation symbols $U\in\bar{\sigma}$ such that
$U(x)\in\textrm{atoms}(\bar{Q})$. The following lemma summarizes the crucial
correspondence between homomorphisms from $\bar{Q}$ to $\bar{D}$, the labels
$\lambda_{e}$ and $\lambda_{x}$ associated to the edges $e$ and the nodes $x$
of the Gaifman graph of $\bar{Q}$, and the labeled graph
$\bar{G}=(\bar{V},\bar{E},\textnormal{{vl}},\textnormal{{el}})$.

######  Lemma 6.2.

A mapping $\nu\colon\textrm{vars}(\bar{Q})\to\textbf{dom}$ is a homomorphism
from $\bar{Q}$ to $\bar{D}$ iff the following is true:

  1. (1)

$\textnormal{{vl}}(\nu(x))\supseteq\lambda_{x}$, for every
$x\in\textrm{vars}(\bar{Q})$, and

  2. (2)

$(\nu(x),\nu(y))\in\bar{E}$ and
$\textnormal{{el}}(\nu(x),\nu(y))\supseteq\lambda_{e}$, for every edge
$e=\\{x,y\\}$ of $G(\bar{Q})$ with $x<y$.

###### Proof.

This is an immediate consequence of our choice of
$\bar{G}=(\bar{V},\bar{E},\textnormal{{vl}},\textnormal{{el}})$, $\bar{Q}$,
the sets $\lambda_{x}$ for all $x\in\textrm{vars}(\bar{Q})$ and the sets
$\lambda_{e}$ for all edges $e$ of $G(\bar{Q})$. ∎

Note that the queries $Q$, $\bar{Q}$, and ${Q_{\operatorname{col}}}$ have the
same head and the same Gaifman graph. Thus, as $Q\in\textsf{{fc-
ACQ}}[\sigma]$, also $\bar{Q}\in\textsf{{fc-ACQ}}[\bar{\sigma}]$ and
${Q_{\operatorname{col}}}\in\textsf{{fc-ACQ}}[\sigma_{\operatorname{col}}]$.
Upon input of $Q$ we can compute in time $O(|Q|)$ the rooted tree $T$, the
queries $\bar{Q}$ and ${Q_{\operatorname{col}}}$, and lookup tables to obtain
$O(1)$-time access to $\lambda_{x}$ and $\lambda_{e}$ for each node $x$ and
edge $e$ of the Gaifman graph of $Q$.

#### Evaluation phase for bool

As a warm-up, we start with the evaluation of _Boolean_ queries. For this
task, we assume that $\bar{Q}$ is a Boolean query, and as described before, we
assume w.l.o.g. that $\bar{Q}$ is connected. The following lemma shows that
evaluating $\bar{Q}$ on $\bar{D}$ can be reduced to evaluating the color query
${Q_{\operatorname{col}}}$ on the color database ${D_{\operatorname{col}}}$.

######  Lemma 6.3.

If $\bar{Q}$ is a Boolean query, then
${\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})={\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$.

The proof easily follows from Lemma 6.2, our particular choice of
${Q_{\operatorname{col}}}$ and ${D_{\operatorname{col}}}$, and the fact that
col is a stable coloring of $\bar{G}$ that refines vl (see Appendix C for
details).

Since ${Q_{\operatorname{col}}}$ is acyclic, we use the algorithm from Theorem
4.2 to compute
${\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$
in time $O(|{Q_{\operatorname{col}}}|{\cdot}|{D_{\operatorname{col}}}|)$. From
Lemma 6.3 we know that
${\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})={\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$.
In summary, by using the information produced during the indexing phase, we
can solve the task of evaluating a Boolean query $Q$ on $D$ in time
$O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$.

#### Evaluation phase for enum

We now move to the non-Boolean case. We assume that $\bar{Q}$ is a connected
$k$-ary query for some $k\geqslant 1$. Recall that the head of $\bar{Q}$ and
${Q_{\operatorname{col}}}$ is of the form $\textit{Ans}(x_{1},\ldots,x_{k})$
with $x_{1}<\cdots<x_{k}$, where $<$ is the fixed order we used for
constructing the query ${Q_{\operatorname{col}}}$. Further, recall that $T$ is
the rooted tree obtained from the Gaifman graph $G(\bar{Q})$ by selecting
$r=x_{1}$ as its root. For each $1<i\leqslant k$, there is a unique $j<i$ such
that $x_{j}$ is the parent of node $x_{i}$ in $T$; we will henceforth write
$p(x_{i})$ to denote this particular $x_{j}$.

The following technical lemma highlights the connection between
${\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$ and
${\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$
that will allow us to use the color-index for enumerating
${\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$.

To state the lemma, we need the following notation. For any $i\in[k]$, we say
that $(v_{1},\ldots,v_{i})$ is a _partial output_ of $\bar{Q}$ over $\bar{D}$
of color $(c_{1},\ldots,c_{k})$ iff there exists $(v_{i+1},\ldots,v_{k})$ such
that $(v_{1},\ldots,v_{i},\allowbreak
v_{i+1},\ldots,v_{k})\in{\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$ and
$(\textnormal{{col}}(v_{1}),\ldots,\textnormal{{col}}(v_{k}))=(c_{1},\ldots,c_{k})$.

######  Lemma 6.4.

Suppose that the head of $Q$ (and $\bar{Q}$ and ${Q_{\operatorname{col}}}$) is
of the form $\textit{Ans}(x_{1},\ldots,x_{k})$ with $x_{1}<\cdots<x_{k}$ and
$k\geqslant 1$. The following statements are true:

  1. (a)

For every
$(v_{1},\ldots,v_{k})\in{\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$ we
have
$(\textnormal{{col}}(v_{1}),\ldots,\textnormal{{col}}(v_{k}))\in{\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$.

  2. (b)

For all
$\overline{c}=(c_{1},\ldots,c_{k})\in{\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$,
and for every $v_{1}\in\textrm{adom}(\bar{D})$ with
$\textnormal{{col}}(v_{1})=c_{1}$, $(v_{1})$ is a partial output of $\bar{Q}$
over $\bar{D}$ of color $\overline{c}$. Moreover, if $(v_{1},\ldots,v_{i})$ is
a partial output of $\bar{Q}$ over $\bar{D}$ of color $\overline{c}$ and
$e=\\{x_{j},x_{i+1}\\}$ is an edge of $G(\bar{Q})$ with $x_{j}<x_{i+1}$, then
$(v_{1},\ldots,v_{i},v_{i+1})$ is a partial output of $\bar{Q}$ over $\bar{D}$
of color $\overline{c}$ for every
$v_{i+1}\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i+1}})$ and,
furthermore,
${\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i+1}})\neq\emptyset$.

The proof uses Lemma 6.2, our particular choice of ${Q_{\operatorname{col}}}$
and ${D_{\operatorname{col}}}$, and the fact that col is a stable coloring of
$\bar{G}$ that refines vl (see Appendix C for details).

For solving the task enum, we proceed as follows: We use Theorem 4.3 with
input ${D_{\operatorname{col}}}$ and ${Q_{\operatorname{col}}}$ to carry out a
preprocessing phase in time
$O(|{Q_{\operatorname{col}}}|{\cdot}|{D_{\operatorname{col}}}|)$ and then
enumerate the tuples in
${\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$
with delay $O(k)$. Each time we receive a tuple
$\overline{c}=(c_{1},\ldots,c_{k})\in{\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$,
we carry out the following algorithm:

> for all $v_{1}\in\bar{V}$ with $\textnormal{{col}}(v_{1})=c_{1}$ do
> $\textsc{Enum}((v_{1});\overline{c})$

For all $i\in[k]$, the procedure
$\textsc{Enum}((v_{1},\ldots,v_{i});\overline{c})$ is as follows:

> if $i=k$ then output $(v_{1},\ldots,v_{k})$
> else
>  let $x_{j}:=p(x_{i+1})$ and let $e:=\\{x_{j},x_{i+1}\\}$
>  for all
> $v_{i+1}\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i+1}})$ do
> $\textsc{Enum}((v_{1},\ldots,v_{i},v_{i+1});\overline{c})$
> endelse.

Clearly, for each fixed
$\overline{c}=(c_{1},\ldots,c_{k})\in{\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$
this outputs, without repetition, tuples $(v_{1},\ldots,v_{k})\in\bar{V}^{k}$
such that
$(\textnormal{{col}}(v_{1}),\ldots,\allowbreak\textnormal{{col}}(v_{k}))=\overline{c}$.
From Lemma 6.4(b) we obtain that the output consists of precisely those tuples
$(v_{1},\ldots,v_{k})$ with color
$(\textnormal{{col}}(v_{1}),\ldots,\textnormal{{col}}(v_{k}))\allowbreak=\overline{c}$
that belong to ${\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$. From Lemma
6.4(a) we obtain that, in total, the algorithm enumerates all the tuples
$(v_{1},\ldots,v_{k})$ in ${\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$.

From Lemma 6.4(b) we know that every time we encounter a loop of the form “for
all $v_{i+1}\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i+1}})$”,
the set ${\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i+1}})$ is non-
empty. Thus, by using the lookup tables built during the indexing phase, we
obtain that the delay between outputting any two tuples of
${\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$ is $O(k)$.

In summary, by using the information produced during the indexing phase, we
can enumerate ${\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$ with delay
$O(k)$ after a preprocessing phase that takes time
$O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$.

#### Evaluation phase for count

In case that $\bar{Q}$ is a _Boolean_ query, the number of answers is either 0
or 1, and the result for the task count can be obtained by evaluating the
Boolean query as described previously.

In case that $\bar{Q}$ is a $k$-ary query for some $k\geqslant 1$, we make the
same assumptions and use the same notation as for enum. For solving the task
count, we proceed as follows. For every $c\in C$, let $v_{c}$ be the first
vertex in the lookup table for the set
$\\{v\in\bar{V}\,:\,\textnormal{{col}}(v)=c\\}$ (this is part of the color-
index $\textsf{{DS}}_{D}$ that has been produced during the indexing phase).
For every $x\in\textrm{vars}(\bar{Q})$ and for every $c\in C$ let
$f_{1}(c,x):=1$ if $\textnormal{{vl}}(v_{c})\supseteq\lambda_{x}$, and let
$f_{1}(c,x)=0$ otherwise. Note that $f_{1}(c,x)$ indicates whether one (and
thus, every) vertex of color $c$ satisfies all the unary atoms of the form
$U(x)$ that occur in $\bar{Q}$. By using the lookup tables built during the
indexing phase and the lookup tables for $\lambda_{x}$ and $\lambda_{e}$ built
during the evaluation phase after having received the input query $Q$, we can
compute in time $O(|C|{\cdot}|\bar{Q}|)$ a lookup table that gives us
$O(1)$-time access to $f_{1}(c,x)$ for all $c\in C$ and all
$x\in\textrm{vars}(\bar{Q})$.

Recall that $T$ denotes the rooted tree obtained from the Gaifman graph
$G(\bar{Q})$ by choosing $x_{1}$ to be its root. For every node $x$ of $T$ we
let $\textit{ch}(x)$ be the set of its children, and we let $T_{x}$ be the
subtree of $T$ rooted at $x$. For $x\neq x_{1}$ we write $\textit{p}(x)$ to
denote the parent of $x$ in $T$.

We perform a bottom-up pass of $T$ and fix the following notions: For every
$c\in C$ and for every _leaf_ $x$ of $T$, let:

$f_{\downarrow}(c,x)\ :=\ \ f_{1}(c,x).$

For every $c\in C$ and every node $y\neq x_{1}$ of $T$, for
$e:=\\{\textit{p}(y),y\\}$ let:

$g(c,y)\ :=\ \ \sum_{c^{\prime}\in C}\ f_{\downarrow}(c^{\prime},y)\cdot\
{\widehat{\\#}}_{\rightarrow}^{\lambda_{e}}({c},{c^{\prime}}).$

For every $c\in C$ and for every node $x$ of $T$ that is not a leaf, let:

$f_{\downarrow}(c,x)\ :=\ \
f_{1}(c,x)\cdot\\!\\!\prod_{y\in\textit{ch}(x)}g(c,y).$

By induction (bottom-up along $T$) it is straightforward to prove the
following lemma (see Appendix C).

######  Lemma 6.5.

For every $c\in C$ and every $v\in\bar{V}$ with $\textnormal{{col}}(v)=c$, the
following is true for all $x\in V(T)$:

  1. (a)

$f_{\downarrow}(c,x)$ is the number of mappings $\nu\colon V(T_{x})\to\bar{V}$
satisfying $\nu(x)=v$ and

    1. (1)

for every $x^{\prime}\in V(T_{x})$ we have
$\textnormal{{vl}}(\nu(x^{\prime}))\supseteq\lambda_{x^{\prime}}$, and

    2. (2)

for every edge $e=\\{x^{\prime},y^{\prime}\\}$ in $T_{x}$ with
$x^{\prime}<y^{\prime}$ we have
$(\nu(x^{\prime}),\nu(y^{\prime}))\in\bar{E}$ and
$\textnormal{{el}}(\nu(x^{\prime}),\nu(y^{\prime}))\supseteq\lambda_{e}$.

  2. (b)

For every $y\in\textit{ch}(x)$, the number $g(c,y)$ is the number of mappings
$\nu\colon\\{x\\}\cup V(T_{y})\to\bar{V}$ satisfying $\nu(x)=v$ and

    1. (1)

for every $x^{\prime}\in V(T_{y})$ we have
$\textnormal{{vl}}(\nu(x^{\prime}))\supseteq\lambda_{x^{\prime}}$, and

    2. (2)

for every edge $e=\\{x^{\prime},y^{\prime}\\}$ in $T_{x}$ with
$x^{\prime}<y^{\prime}$ and $x^{\prime},y^{\prime}\in\\{x\\}\cup V(T_{y})$ we
have
$(\nu(x^{\prime}),\nu(y^{\prime}))\in\bar{E}$ and
$\textnormal{{el}}(\nu(x^{\prime}),\nu(y^{\prime}))\supseteq\lambda_{e}$.

For the particular case where $x=x_{1}$, Lemmas 6.5(a) and 6.2 yield that

$\sum_{c\in C}\ n_{c}\cdot
f_{\downarrow}(c,x_{1})\quad\text{is}\quad\parbox[t]{284.52756pt}{the number
of homomorphisms from $\bar{Q}$ to $\bar{D}$,\\\ where $n_{c}$ is the number
of nodes $v\in\bar{V}$ with $\textnormal{{col}}(v)=c$.}$

It is straightforward to see that a lookup table that provides $O(1)$-time
access to $f_{\downarrow}(c,x)$ and $g(c,y)$ for all $c\in C$ and all
$x,y\in\textrm{vars}(\bar{Q})$ can be computed in time
$O(|\bar{Q}|{\cdot}|{D_{\operatorname{col}}}|)$. Hence, also $\sum_{c\in C}\
n_{c}\cdot f_{\downarrow}(c,x_{1})$ can be computed in time
$O(|\bar{Q}|{\cdot}|{D_{\operatorname{col}}}|)=O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$.

In the particular case where $\textrm{free}(Q)=\textrm{vars}(Q)$, the number
of homomorphisms from $\bar{Q}$ to $\bar{D}$ is precisely the number
$|{\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})|$. This solves the task
count in case that $\textrm{free}(\bar{Q})=\textrm{vars}(\bar{Q})$.

To solve the task count in case that
$\textrm{free}(\bar{Q})\neq\textrm{vars}(\bar{Q})$, we additionally perform a
bottom-up pass of the subtree $T^{\prime}$ of $T$ induced by
$\textrm{free}(\bar{Q})$ (to see that $T^{\prime}$ is indeed a tree, recall
Proposition 4.1). For each leaf $x$ of $T^{\prime}$ and every $c\in C$ we let

$f^{\prime}_{\downarrow}(c,x):=1\ \ \text{if}\ f_{\downarrow}(c,x)\geqslant
1,\quad\text{and}\ \ f^{\prime}_{\downarrow}(c,x):=0\ \text{otherwise.}$

For every $c\in C$ and every node $y\neq x_{1}$ of $T^{\prime}$, for
$e:=\\{\textit{p}(y),y\\}$ let

$g^{\prime}(c,y)\ :=\ \ \sum_{c^{\prime}\in C}\
f^{\prime}_{\downarrow}(c^{\prime},y)\cdot\
{\widehat{\\#}}_{\rightarrow}^{\lambda_{e}}({c},{c^{\prime}}).$

For every $c\in C$ and for every node $x$ of $T^{\prime}$ that is not a leaf,
let

$f^{\prime}_{\downarrow}(c,x)\ :=\ \
f_{1}(c,x)\cdot\\!\\!\prod_{y\in\textit{ch}(x)}g^{\prime}(c,y).$

By induction (bottom-up along $T^{\prime}$) one can show that for every $c\in
C$ and every $v\in\bar{V}$ with $\textnormal{{col}}(v)=c$,
$f^{\prime}_{\downarrow}(c,x_{1})$ is the number of tuples
$(v_{1},\ldots,v_{k})\in{\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$
with $v_{1}=v$. Thus,

$|{\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})|\ \ =\ \ \sum_{c\in C}\
n_{c}\cdot f^{\prime}_{\downarrow}(c,x_{1}).$

Furthermore, this number can be computed in time
$O(|\bar{Q}|{\cdot}|{D_{\operatorname{col}}}|)$. In summary, we compute the
number $|{\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})|$ in time
$O(|\bar{Q}|{\cdot}|{D_{\operatorname{col}}}|)$.

##  7 Statement of our main result

From Sections 5 and 6 we directly obtain our following main result, where
${D_{\operatorname{col}}}$ is the _color database_ produced for the input
database $D$ during the indexing phase. Note that ${D_{\operatorname{col}}}$
has size $O(|D|)$ in the worst-case; but depending on the particular structure
of $D$, the size $|{D_{\operatorname{col}}}|$ might be substantially smaller
than $|D|$ (even $O(1)$ is possible, cf. Proposition 5.6).

######  Theorem 7.1.

For every binary schema $\sigma$, the problem
$\textup{{IndexingEval}}(\sigma,\textsf{{fc-ACQ}}[\sigma])$ can be solved with
indexing time $f_{\operatorname{col}}(D)+O(|D|)$, such that afterwards, every
Boolean acyclic query $Q$ can be answered in time
$O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$. Furthermore, for every query
$Q\in\textsf{{fc-ACQ}}[\sigma]$ we can enumerate the tuples in
${\left\llbracket Q\right\rrbracket}(D)$ with delay $O(|\textrm{free}(Q)|)$
after preprocessing time $O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$, and we can
compute the number $|{\left\llbracket Q\right\rrbracket}(D)|$ of result tuples
in time $O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$.

##  8 Final Remarks

Our main result provides a solution for the problem
$\textup{{IndexingEval}}(\sigma,\textsf{{fc-ACQ}}[\sigma])$ for any _binary_
schema $\sigma$. Our approach can be summarized as follows. Upon input of a
database $D$ of schema $\sigma$, during the indexing phase we construct a
vertex-labeled and edge-labeled directed graph $\bar{G}$ that represents $D$.
We then use a suitable version of the well-known color refinement algorithm to
construct a coarsest stable coloring
$\textnormal{{col}}\colon\textrm{adom}(D)\to C$ (for a suitable set $C$ of
colors) that refines the vertex-labels of $\bar{G}$. Based on this, we
construct the data structure $\textsf{{DS}}_{D}$ that we call _color-index_
and that we view as the result of the indexing phase. The main ingredient of
$\textsf{{DS}}_{D}$ is the _color database_ ${D_{\operatorname{col}}}$. This
is a database of a newly constructed schema $\sigma_{\operatorname{col}}$; its
active domain is the set $C$.

During the evaluation phase, we can access the color-index
$\textsf{{DS}}_{D}$. When receiving an arbitrary $k$-ary input query
$Q\in\textsf{{fc-ACQ}}[\sigma]$, we use $\textsf{{DS}}_{D}$ (and, in
particular, ${D_{\operatorname{col}}}$) to

  * •

answer $Q$, in case that $k=0$, in time
$O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$,

  * •

compute $|{\left\llbracket Q\right\rrbracket}(D)|$ in time
$O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$, and

  * •

enumerate ${\left\llbracket Q\right\rrbracket}(D)$ with delay $O(k)$ after
$O(|Q|{\cdot}|{D_{\operatorname{col}}}|)$ preprocessing.

It was known previously that each of these query evaluation tasks can be
solved (without access to our color-index $\textsf{{DS}}_{D}$) in time
$O(|Q|{\cdot}|D|)$. Our result provides an improvement from $|D|$ to
$|{D_{\operatorname{col}}}|$. In the worst-case,
$|{D_{\operatorname{col}}}|=O(|D|)$; but depending on the particular structure
of $D$, the color database ${D_{\operatorname{col}}}$ may be much smaller than
$D$ (see Proposition 5.6).

#### Future work

Obvious questions (we currently work on) are:

_Can our approach be generalized from fc-ACQs to queries of free-connex tree-
width $\leqslant k$, for any fixed $k\geqslant 1$?_ When sticking with binary
schemas, we believe that this can be achieved by using a variant of the
$k$-dimensional Weisfeiler-Leman algorithm (cf. [15, 19]).

_Can our approach be generalized from binary schemas to arbitrary schemas?_
Due to subtleties concerning the notion of fc-ACQs, a straightforward
representation of databases over an arbitrary schema $\sigma$ by databases of
a suitably chosen binary schema $\sigma^{\prime}$ apparently does not help to
easily lift our results from binary to arbitrary schemas (see Appendix A.3).
To solve the case for arbitrary schemas, a generalization of the color
refinement algorithm from graphs to hypergraphs would be desirable. Böker [14]
provided a color refinement algorithm that seems promising for handling
queries $Q$ that are free-connex _Berge-acyclic_. But a new color refinement
algorithm needs to be developed to handle also free-connex acyclic queries
that are not free-connex Berge-acyclic.

_Can our approach be lifted to a dynamic scenario?_ The _dynamic Yannakakis_
approach of Idris, Ugarte, and Vansummeren [21] lifts Theorem 4.3 to a dynamic
scenario, where a fixed query $Q$ shall be evaluated against a database $D$
that is frequently updated. Note that our color-index $\textsf{{DS}}_{D}$ is
not built for a fixed query, but for supporting _all_ queries. When receiving
an update for the database $D$, we would have to modify the color-index
$\textsf{{DS}}_{D}$ accordingly. Already a small change of the color of a
single vertex or its local neighborhood in $\bar{G}$ might impose drastic
changes in the result of the color refinement algorithm and might change the
size of ${D_{\operatorname{col}}}$ from $O(1)$ to $\Theta(|D|)$, or vice
versa. (For example, consider the database $D^{n}$ from the proof of
Proposition 5.6. Inserting the tuple $(1,1)$ into the $R$-relation leads to a
coarsest stable coloring with approximately $n/2$ colors; and subsequently
deleting $(1,1)$ from the $R$-relation again reduces the number of colors to
1.) Nevertheless, it is an interesting question if $\textsf{{DS}}_{D}$ can be
updated in time proportional to the actual difference between the two versions
of $\textsf{{DS}}_{D}$ before and after the update.

_What is the potential practical impact of our approach?_ To further reduce
the size of ${D_{\operatorname{col}}}$, one may decide to let the color
refinement procedure only run for a fixed number $r$ of rounds. The resulting
coarser variant of our color-index can still be used for evaluating fc-ACQs of
radius up to $r$. We believe that this variant of the color-index deserves a
detailed experimental evaluation.

## References

  * [1] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison-Wesley, 1995.
  * [2] Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc.  Foundations of modern query languages for graph databases.  ACM Comput. Surv., 50(5):68:1–68:40, 2017.
  * [3] Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, Juan L. Reutter, Javiel Rojas-Ledesma, and Adrián Soto.  Worst-case optimal graph joins in almost no space.  In SIGMOD, pages 102–114. ACM, 2021.
  * [4] V. Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky.  Graph Isomorphism, Color Refinement, and Compactness.  Computational Complexity, 26(3):627–685, September 2017.
  * [5] Guillaume Bagan.  Algorithmes et complexité des problèmes d’énumération pour l’évaluation de requêtes logiques. (Algorithms and complexity of enumeration problems for the evaluation of logical queries).  PhD thesis, University of Caen Normandy, France, 2009.
  * [6] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In Proceedings of the 16th Annual Conference of the EACSL, CSL’07, Lausanne, Switzerland, September 11–15, 2007, pages 208–222, 2007.
  * [7] Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis.  On the desirability of acyclic database schemes.  J. ACM, 30(3):479–513, 1983.
  * [8] Christoph Berkholz, Paul S. Bonsma, and Martin Grohe.  Tight lower and upper bounds for the complexity of canonical colour refinement.  Theory Comput. Syst., 60(4):581–614, 2017.
  * [9] Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt.  Constant delay enumeration for conjunctive queries: a tutorial.  ACM SIGLOG News, 7(1):4–33, 2020.
  * [10] Philip A. Bernstein and Nathan Goodman.  Power of natural semijoins.  SIAM J. Comput., 10(4):751–771, 1981.
  * [11] Jeroen Bollen, Jasper Steegmans, Jan Van Den Bussche, and Stijn Vansummeren.  Learning Graph Neural Networks using Exact Compression.  In Proceedings of the 6th Joint Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), GRADES & NDA ’23, New York, NY, USA, 2023. Association for Computing Machinery.
  * [12] Johann Brault-Baron.  De la pertinence de l’énumération : complexité en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order).  PhD thesis, University of Caen Normandy, France, 2013.
  * [13] Johann Brault-Baron.  Hypergraph Acyclicity Revisited.  ACM Comput. Surv., 49(3):54:1–54:26, 2016.
  * [14] Jan Böker.  Color Refinement, Homomorphisms, and Hypergraphs.  In Ignas Sau and Dimitrios M. Thilikos, editors, Graph-Theoretic Concepts in Computer Science, volume 11789 of Lecture Notes in Computer Science, pages 338–350. Springer, Cham, 2019.
  * [15] Jin-yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identification.  Combinatorica, 12(4):389–410, 1992.
  * [16] Zdeněk Dvořák.  On Recognizing Graphs by Numbers of Homomorphisms.  Journal of Graph Theory, 64(4):330–342, 2010.
  * [17] Georg Gottlob, Nicola Leone, and Francesco Scarcello.  Hypertree decompositions and tractable queries.  J. Comput. Syst. Sci., 64(3):579–627, 2002.
  * [18] Martin Grohe.  Word2vec, Node2vec, Graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data.  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS’20, pages 1–16. ACM, 2020.
  * [19] Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer.  Color Refinement and Its Applications.  In Guy Van den Broeck, Kristian Kersting, Sriraam Natarajan, and David Poole, editors, An Introduction to Lifted Probabilistic Inference. The MIT Press, 2021.
  * [20] Martin Grohe, Kristian Kersting, Martin Mladenov, and Erkal Selman.  Dimension Reduction via Colour Refinement.  In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014, Lecture Notes in Computer Science, pages 505–516, Berlin, Heidelberg, 2014. Springer.
  * [21] Muhammad Idris, Martín Ugarte, and Stijn Vansummeren.  The Dynamic Yannakakis algorithm: Compact and efficient query processing under updates.  In Proc. 2017 ACM International Conference on Management of Data (SIGMOD Conference 2017), Chicago, IL, USA, May 14–19, 2017, pages 1259–1274, 2017.
  * [22] Muhammad Idris, Martín Ugarte, Stijn Vansummeren, Hannes Voigt, and Wolfgang Lehner.  Conjunctive queries with inequalities under updates.  PVLDB, 11(7):733–745, 2018.
  * [23] Muhammad Idris, Martín Ugarte, Stijn Vansummeren, Hannes Voigt, and Wolfgang Lehner.  Efficient query processing for dynamically changing datasets.  SIGMOD Record, 48(1):33–40, 2019.
  * [24] Moe Kayali and Dan Suciu.  Quasi-Stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality.  In Proceedings of the VLDB Endowment, volume 16, pages 803–815, December 2022.
  * [25] Sandra Kiefer.  The Weisfeiler-Leman Algorithm: An Exploration of Its Power.  ACM SIGLOG News, 7(3):5–27, November 2020.
  * [26] Sandra Kiefer, Pascal Schweitzer, and Erkal Selman.  Graphs Identified by Logics with Counting.  ACM Transactions on Computational Logic, 23(1):1:1–1:31, October 2021.
  * [27] Hung Q Ngo, Ely Porat, Christopher Ré, and Atri Rudra.  Worst-case optimal join algorithms.  Journal of the ACM (JACM), 65(3):1–40, 2018.
  * [28] Dan Olteanu and Jakub Závodný.  Size bounds for factorised representations of query results.  ACM Trans. Database Syst., 40(1):2:1–2:44, 2015.
  * [29] François Picalausa, George H. L. Fletcher, Jan Hidders, and Stijn Vansummeren.  Principles of Guarded Structural Indexing.  In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 245–256. OpenProceedings.org, 2014.
  * [30] François Picalausa, Yongming Luo, George H. L. Fletcher, Jan Hidders, and Stijn Vansummeren.  A Structural Approach to Indexing Triples.  In Elena Simperl, Philipp Cimiano, Axel Polleres, Oscar Corcho, and Valentina Presutti, editors, The Semantic Web: Research and Applications, Lecture Notes in Computer Science, pages 406–421, Berlin, Heidelberg, 2012. Springer.
  * [31] Raghu Ramakrishnan and Johannes Gehrke.  Database management systems, volume 3.  McGraw-Hill New York, 2003.
  * [32] Thanh Tran, Gunter Ladwig, and Sebastian Rudolph.  Managing Structured and Semistructured RDF Data Using Structure Indexes.  IEEE Transactions on Knowledge and Data Engineering, 25(9):2076–2089, September 2013.
  * [33] Todd L. Veldhuizen.  Triejoin: A simple, worst-case optimal join algorithm.  In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 96–106. OpenProceedings.org, 2014.
  * [34] Mihalis Yannakakis.  Algorithms for acyclic database schemes.  In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings, pages 82–94, 1981.

## APPENDIX

##  Appendix A Details on acyclic and free-connex acyclic conjunctive queries

###  A.1 Proof of Proposition 4.1

Let $\sigma$ be a binary schema, i.e., every $R\in\sigma$ has arity
$\operatorname{ar}(R)\leqslant 2$. In the following, if $G$ is a (hyper)graph,
then we denote by $G-e$ the resulting (hyper)graph after removing the
(hyper)edge $e\in E(G)$ from $G$. If a vertex becomes isolated due to this
procedure, we remove it as well. Further, we denote by $G+e$ the (hyper)graph
resulting from adding the (hyper)edge $e$ to $G$. First we show that we can
assume that $Q$ contains no loops and only uses predicates of arity exactly 2.

######  Claim A.1.

$Q$ is free-connex acyclic iff $Q^{\prime}$ is free-connex acyclic, where
$\textrm{atoms}(Q^{\prime}):=\\{R(x,y)\,:\,R(x,y)\in\textrm{atoms}(Q),\
x{\neq}y\\}$ and
$\textrm{free}(Q^{\prime}):=\textrm{free}(Q)\cap\textrm{vars}(Q^{\prime})$.

###### Proof.

($\Rightarrow$) Let $Q$ be free-connex acyclic. Then $H(Q)+\textrm{free}(Q)$
has a join-tree $T$. We translate $T$ into a join-tree $T^{\prime}$ for
$H(Q^{\prime})+\textrm{free}(Q^{\prime})$ as follows. First, we replace the
node $\textrm{free}(Q)$ in $T$ with $\textrm{free}(Q^{\prime})$. Then, for
every hyperedge $e=\\{x\\}$, we look for a neighbor $f$ of $e$ in $T$ such
that $x\in f$. If there is none, we let $f$ be an arbitrary neighbor. Then we
connect all other neighbors of $e$ in $T$ with $f$ and remove $e$ from $T$.
The resulting graph is still a tree and the set of nodes containing $x$ still
induces a connected subtree, or it is empty — but in that case also
$x\not\in\textrm{vars}(Q^{\prime})$. I.e., now the set of nodes in
$T^{\prime}$ is precisely the set of hyperedges of
$H(Q^{\prime})+\textrm{free}(Q^{\prime})$, and for every
$x\in\textrm{vars}(Q^{\prime})$, the set $\\{t\in V(T^{\prime})\,:\,x\in t\\}$
still induces a connected subtree. Hence, $T^{\prime}$ is a join-tree for
$H(Q^{\prime})+\textrm{free}(Q^{\prime})$.

Since $Q$ is free-connex acyclic, there also exists a join-tree $T$ for
$H(Q)$. With the same reasoning as above, $T$ can be transformed into a join-
tree for $H(Q^{\prime})$. In summary, we obtain that $Q^{\prime}$ is free-
connex acyclic.

($\Leftarrow$) Let $Q^{\prime}$ be free-connex acyclic. Then
$H(Q^{\prime})+\textrm{free}(Q^{\prime})$ has a join-tree $T^{\prime}$. We can
extend $T^{\prime}$ to a join-tree $T$ for $H(Q)+\textrm{free}(Q)$ as follows.
First, we replace the node $\textrm{free}(Q^{\prime})$ in $T^{\prime}$ with
$\textrm{free}(Q)$. For every hyperedge $e$ in $H(Q)$ of the form $e=\\{x\\}$
we add $e$ as a new node to $T^{\prime}$ and insert the edge $\\{e,f\\}$ into
$T^{\prime}$ as follows: If $x\not\in\textrm{vars}(Q^{\prime})$ we let $f$ be
an arbitrary node in $V(T^{\prime})$. Otherwise, let $f\in V(T^{\prime})$ be a
node such that $x\in f$. It is easy to verify that the resulting tree $T$ is a
join-tree for $H(Q)+\textrm{free}(Q)$. Since $Q^{\prime}$ is free-connex
acyclic, there also exists a join-tree $T$ for $H(Q^{\prime})$. With the same
reasoning as above, $T^{\prime}$ can be transformed into a join-tree for
$H(Q)$. In summary, we obtain that $Q$ is free-connex acyclic. ∎

Due to the above claim, we can assume w.l.o.g. that $Q$ contains no self-loops
and only uses predicates of arity 2. Notice that this means that $H(Q)=G(Q)$.
It is well-known that for undirected graphs the notion of $\alpha$-acyclicity
and the standard notion of acyclicity for graphs coincide. I.e., a graph is
$\alpha$-acyclic iff it is acyclic (see [13] for an overview). Hence, in our
setting, $H(Q)=G(Q)$ is $\alpha$-acyclic, if and only if it is acyclic, i.e.,
a forest. This immediately yields the first statement of Proposition 4.1. The
second statement of Proposition 4.1 is obtained by the following claim.

######  Claim A.2.

$Q$ is free-connex acyclic iff $G(Q)$ is acyclic and the following statement
is true: (**) For every connected component $C$ of $G(Q)$, the subgraph of $C$
induced by the set $\textrm{free}(Q)\cap V(C)$ is connected or empty.

###### Proof.

$(\Rightarrow)$ By assumption, $Q$ is free-connex acyclic. I.e., $H(Q)$ is
$\alpha$-acyclic and $H(Q)+\textrm{free}(Q)$ is $\alpha$-acyclic. Since
$H(Q)=G(Q)$, and since on graphs $\alpha$-acyclicity coincides with
acyclicity, this means that $G(Q)$ is acyclic, i.e., it is a forest.

Since $H(Q)+\textrm{free}(Q)$ is $\alpha$-acyclic, there exists a join-tree
$T$ for $H(Q)+\textrm{free}(Q)$. To prove (**) we proceed by induction on the
number of nodes in the join-tree of $H(Q)+\textrm{free}(Q)$.

If $T$ has at most two nodes, $H(Q)$ consists of a single hyperedge, and this
is of the form $\\{x,y\\}$ with $x\neq y$. Therefore, $G(Q)$ consists of a
single edge $\\{x,y\\}$, and in this case (**) trivially holds.

In the inductive case, let $T$ be a join tree of $H(Q)+\textrm{free}(Q)$.
Consider some leaf $e$ of $T$ (i.e, $e$ only has one neighbor in $T$) of the
form $e=\\{x,y\\}$ and its parent $p$. Then, $T-e$ is a join-tree for
$H(Q^{\prime})+\textrm{free}(Q)$ where
$\textrm{atoms}(Q^{\prime}):=\\{R(z_{1},z_{2})\in\textrm{atoms}(Q)\,:\,\\{z_{1},z_{2}\\}\neq\\{x,y\\}\\}$
and $\textrm{free}(Q^{\prime})$ is the set of all variables in
$\textrm{free}(Q)$ that occur in an atom of $Q^{\prime}$. It is easy to see
that this implies the existence of a join-tree $T^{\prime}$ for
$H(Q^{\prime})+\textrm{free}(Q^{\prime})$. Since, furthermore, $G(Q^{\prime})$
is acyclic, the query $Q^{\prime}$ is free-connex acyclic, and by induction
hypothesis, (**) is true for $G(Q^{\prime})$. Note that
$G(Q^{\prime})=G(Q)-e$. Obviously, $x$ and $y$ are in the same connected
component $C$ in $G(Q)$. We have to consider the relationship between $x$, $y$
and the rest of $C$.

Since $e$ is a leaf in $T$, $x,y\in p$ would imply that $p=\textrm{free}(Q)$.
Using that we know that

  1. (i)

either $y$ only has $x$ as a neighbor in $G(Q)$ or vice-versa, or

  2. (ii)

$x$ and $y$ are both free variables and both have other neighbors than $y$ and
$x$, respectively.

_Case (i)_ : Assume w.l.o.g. that $x$ is the only vertex adjacent to $y$ in
$G(Q)$. Then $C^{\prime}:=C-\\{x,y\\}$ is a connected component in
$G(Q^{\prime})$, $y\not\in\textrm{vars}(Q^{\prime})$, i.e., in particular also
$y\not\in\textrm{free}(Q^{\prime})$. By induction hypothesis,
$\textrm{free}(Q^{\prime})\cap V(C^{\prime})$ induces a connected subgraph on
$C^{\prime}$. If $y\not\in\textrm{free}(Q)$ it follows trivially, that
$\textrm{free}(Q)\cap V(C)$ induces a connected subgraph on $C$. If
$y\in\textrm{free}(Q)$ and $\textrm{free}(Q)\cap V(C)=\\{y\\}$, this is also
trivial. Otherwise, there exists a $z\in\textrm{free}(Q)\cap V(C)$ different
from $y$. Since $x,y,z$ are all in the same connected component $C$, but $x$
is the only vertex adjacent to $y$, there must be another vertex $w$ that is
adjacent to $x$. Therefore, $x$ is part of another node $\\{x,w\\}$ somewhere
in $T$, which by definition means that $x$ must be in $p$. Since
$y,z\in\textrm{free}(Q)$, $y$ must also be in $p$. Therefore,
$p=\textrm{free}(Q)$ and that means $x\in\textrm{free}(Q)$. Hence,
$\textrm{free}(Q)\cap V(C)$ forms a connected component on $C$ in this case as
well.

_Case (ii)_ : Assume that both variables $x$ and $y$ are free and both have
another vertex adjacent to them in $G(Q)$. Then
$x,y\in\textrm{free}(Q^{\prime})$ (i.e.,
$\textrm{free}(Q)=\textrm{free}(Q^{\prime})$) and removing the edge
$\\{x,y\\}$ splits $C$ into two connected components $C_{x}$, $C_{y}$. By
induction hypothesis, $\textrm{free}(Q^{\prime})\cap V(C_{x})$ and
$\textrm{free}(Q^{\prime})\cap V(C_{y})$ induce connected subgraphs on $C_{x}$
and $C_{y}$, respectively, and $x$ (and $y$, resp.) are part of them. Thus,
adding the edge $\\{x,y\\}$ establishes a connection between them, so
$\textrm{free}(Q)\cap V(C)$ also induces a connected subtree on $C$.

Every other connected component $D\neq C$ in $G(Q)$ is also one in
$G(Q^{\prime})$. Thus, (**) is true for $G(Q)$.

$(\Leftarrow)$ By assumption, $G(Q)$ is acyclic and (**) is satisfied. Since
$G(Q)=H(Q)$ and $\alpha$-acyclicity coincides with acyclicity on graphs, $Q$
is acyclic. It remains to show that $H(Q)+\textrm{free}(Q)$ has a join-tree.

We proceed by induction over the number of vertices in $G(Q)$. Recall that $Q$
only uses binary relation symbols and that it has no self-loops. Thus, in the
base case, $G(Q)$ consists of two vertices connected by an edge. Since
$H(Q)=G(Q)$, it is easy to see that $H(Q)+\textrm{free}(Q)$ has a join-tree.

In the inductive case, let $C$ be a connected component of $G(Q)$ that
contains a quantified variable, i.e., $\textrm{free}(Q)\cap V(C)\neq V(C)$. If
no such component exists, $H(Q)+\textrm{free}(Q)$ has a trivial join-tree by
letting all hyperedges of $H(Q)$ be children of $\textrm{free}(Q)$ in $T$.

Because of (**) there must be a leaf $x$ in $C$ such that
$x\not\in\textrm{free}(Q)$. Let $y$ be the parent of $x$, i.e., let
$\\{x,y\\}$ be an (or rather, the only) edge in $G(Q)$ that contains $x$. Let
$H^{\prime}:=H(Q)-\\{x,y\\}$. Then $H^{\prime}=H(Q^{\prime})$ for the query
$Q^{\prime}$ where
$\textrm{atoms}(Q^{\prime})=\\{R(z_{1},z_{2})\in\textrm{atoms}(Q)\,:\,x\not\in\\{z_{1},z_{2}\\}\\}$
and $\textrm{free}(Q^{\prime})=\textrm{free}(Q)\setminus\\{x\\}$.

Let $T^{\prime}$ be the join-tree that exists by induction hypothesis for
$H(Q^{\prime})+\textrm{free}(Q^{\prime})$, i.e., for
$H^{\prime}+\textrm{free}(Q)\setminus\\{x\\}$.

If $x\not\in\textrm{free}(Q)$, we can extend $T^{\prime}$ to a join-tree $T$
for $H(Q)$ by adding the edge $\\{x,y\\}$ as a child node to some node that
contains $y$ in $T^{\prime}$. We can similarly handle the case
$\textrm{free}(Q)=\\{x\\}$ by also inserting $\\{x\\}$ as a child of
$\\{x,y\\}$.

If $x\in\textrm{free}(Q)$ but $\textrm{free}(Q)\varsupsetneqq\\{x\\}$, it
holds that $y\in\textrm{free}(Q)$, by the assumption that
$\textrm{free}(Q)\cap V(C)$ induces a connected subgraph. In this case we can
add $\\{x,y\\}$ as a child of $\textrm{free}(Q)$. ∎

###  A.2 Proof of Theorem 4.3

We provide further definitions that are taken from [9]. We use these
definitions for the proof of Theorem 4.3 below.

A _tree decomposition_ (TD, for short) of a CQ $Q$ and its hypergraph $H(Q)$
is a tuple $\textit{TD}=(T,\textit{bag})$, such that:

  1. (1)

$T=(V(T),E(T))$ is a finite undirected tree, and

  2. (2)

bag is a mapping that associates with every node $t\in V(T)$ a set
$\textit{bag}(t)\subseteq\textrm{vars}(Q)$ such that

    1. (a)

for each atom $a\in\textrm{atoms}(Q)$ there exists $t\in V(T)$ such that
$\textrm{vars}(a)\subseteq\textit{bag}(t)$,

    2. (b)

for each variable $v\in\textrm{vars}(Q)$ the set
$\textit{bag}^{-1}(v):=\\{t\in V(T)\,:\,v\in\textit{bag}(t)\\}$ induces a
connected subtree of $T$.

The _width_ of $\textit{TD}=(T,\textit{bag})$ is defined as
$\textit{width}(\textit{TD})=\max_{t\in V(T)}|\textit{bag}(t)|-1$.

A _generalized hypertree decomposition_ (GHD, for short) of a CQ $Q$ and its
hypergraph $H(Q)$ is a tuple $\textit{H}=(T,\textit{bag},\textit{cover})$ that
consists of a tree decomposition $(T,\textit{bag})$ of $Q$ and a mapping cover
that associates with every node $t\in V(T)$ a set
$\textit{cover}(t)\subseteq\textrm{atoms}(Q)$ such that
$\textit{bag}(t)\subseteq\bigcup_{a\in\textit{cover}(t)}\textrm{vars}(a)$. The
sets $\textit{bag}(t)$ and $\textit{cover}(t)$ are called the _bag_ and the
_cover_ associated with node $t\in V(T)$. The _width_ of a GHD H is defined as
the maximum number of atoms in a cover-label of a node of $T$, i.e.,
$\textit{width}(\textit{H})=\max_{t\in V(T)}|\textit{cover}(t)|$. The
_generalized hypertree width_ of a CQ $Q$, denoted $\textit{ghw}(Q)$, is
defined as the minimum width over all its generalized hypertree
decompositions.

A tree decomposition $\textit{TD}=(T,\textit{bag})$ of a CQ $Q$ is _free-
connex_ if there is a set $U\subseteq V(T)$ that induces a connected subtree
of $T$ and that satisfies the condition $\textrm{free}(Q)=\bigcup_{t\in
U}\textit{bag}(t)$. Such a set $U$ is called a _witness_ for the free-
connexness of TD. A GHD is free-connex if its tree decomposition is free-
connex. The _free-connex generalized hypertree width_ of a CQ $Q$, denoted
$\textit{fc-ghw}(Q)$, is defined as the minimum width over all its free-connex
generalized hypertree decompositions.

It is known ([17, 6, 12]; see also [9] for an overview as well as proof
details) that the following is true for every schema $\sigma$ and every CQ $Q$
of schema $\sigma$:

  1. (I)

$Q$ is acyclic iff $\textit{ghw}(Q)=1$.

  2. (II)

$Q$ is free-connex acyclic iff $\textit{fc-ghw}(Q)=1$.

A GHD $\textit{H}=(T,\textit{bag},\textit{cover})$ of a CQ $Q$ is called
_complete_ if, for each atom $a\in\textrm{atoms}(Q)$ there exists a node $t\in
V(T)$ such that $\textrm{vars}(a)\subseteq\textit{bag}(t)$ and
$a\in\textit{cover}(t)$.

The following has been shown in [9] (see Theorem 4.2 in [9]):

######  Theorem A.3 ([9]).

For every schema $\sigma$ there is an algorithm which receives as input a
query $Q\in\textsf{{fc-ACQ}}[\sigma]$, a complete free-connex width 1 GHD
$\textit{H}=(T,\textit{bag},\textit{cover})$ of $Q$ along with a witness
$U\subseteq V(T)$, and a $\sigma$-db $D$ and computes within preprocessing
time $O(|V(T)|{\cdot}|D|)$ a data structure that allows to enumerate
${\left\llbracket Q\right\rrbracket}(D)$ with delay $O(|U|)$.

It is known that for every schema $\sigma$ there is an algorithm that receives
as input a query $Q\in\textsf{{fc-ACQ}}[\sigma]$ and computes in time $O(|Q|)$
a free-connex width 1 GHD of $Q$ ([5]; see also Section 5.1 in [9]). When
applying to this GHD the construction used in the proof of [9, Lemma 3.3], and
afterwards performing the completion construction from [9, Remark 3.1], one
can compute in time $O(|Q|)$ a GHD
$\textit{H}=(T,\textit{bag},\textit{cover})$ of $Q$ along with a witness
$U\subseteq V(T)$ that satisfy the assumptions of Theorem A.3 and for which,
additionally, the following is true: $|U|\leqslant|\textrm{free}(Q)|$ and
$|V(T)|\in O(|Q|)$. In summary, this provides a proof of Theorem 4.3.

###  A.3 An example concerning a non-binary schema

At a first glance one may be tempted to believe that it should be
straightforward to generalize our main result from binary to arbitrary schemas
by representing databases of a non-binary schema $\sigma$ as databases of a
suitably chosen binary schema $\sigma^{\prime}$. However, the notion of fc-
ACQs is quite subtle, and an fc-ACQ of schema $\sigma$ might translate into a
CQ of schema $\sigma^{\prime}$ that is not an fc-ACQ, hence prohibiting to
straightforwardly reduce the case of general schemas to our results for fc-
ACQs over binary schemas. Here is a concrete example.

Let us consider a schema consisting of a single, ternary relation symbol $R$.
A straightforward way to represent a database $D$ of this schema by an edge-
labeled bipartite digraph $D^{\prime}$ is as follows. $D^{\prime}$ has 3 edge-
relations called $E_{1},E_{2},E_{3}$. Every element in the active domain of
$D$ is a node of $D^{\prime}$. Furthermore, every tuple
$t=(a_{1},a_{2},a_{3})$ in the $R$-relation of $D$ serves as a node of
$D^{\prime}$, and we insert into $D^{\prime}$ an $E_{1}$-edge $(t,a_{1})$, an
$E_{2}$-edge $(t,a_{2})$, and an $E_{3}$-edge $(t,a_{3})$. Now, a CQ $Q$ posed
against $D$ translates into a CQ $Q^{\prime}$ posed against $D^{\prime}$ as
follows: $Q^{\prime}$ has the same head as $Q$. For each atom $R(x,y,z)$ in
the body of $Q$ we introduce a new variable $u$ and insert into the body of
$Q^{\prime}$ the atoms $E_{1}(u,x),E_{2}(u,y),E_{3}(u,z)$.

We want to build an index structure on $D$ that supports constant-delay
enumeration and counting for all fc-ACQs $Q$ posed against $D$. The problem is
that an fc-ACQ $Q$ against $D$ does _not_ necessarily translate into an _fc-
ACQ_ $Q^{\prime}$ against $D^{\prime}$ — and therefore, lifting our approach
from binary to arbitrary schemas is not so easy. Here is a specific example of
such a query $Q$:

$\textit{Ans}(x,y,z)\ \leftarrow\ R(x,y,z),\ R(x,x,y),\ R(y,y,z),\ R(z,z,x).$

This query is an fc-ACQ (as a witness, take the join-tree whose root is
labeled with $R(x,y,z)$ and has 3 children labeled with the remaining atoms in
the body of the query). But the associated query $Q^{\prime}$ is

$\textit{Ans}(x,y,z)\
\leftarrow\begin{array}[t]{l}E_{1}(u_{1},x),E_{2}(u_{1},y),E_{3}(u_{1},z),\\\
E_{1}(u_{2},x),E_{2}(u_{2},x),E_{3}(u_{2},y),\\\
E_{1}(u_{3},y),E_{2}(u_{3},y),E_{3}(u_{3},z),\\\
E_{1}(u_{4},z),E_{2}(u_{4},z),E_{3}(u_{4},x).\end{array}$

Note that the Gaifman-graph of $Q^{\prime}$ is not acyclic (it contains the
cycle $x-u_{2}-y-u_{3}-z-u_{4}-x$). Therefore, by Proposition 4.1,
$Q^{\prime}$ is not an fc-ACQ. This simple example illustrates that the
straightforward encoding of the database $D$ as a database over a binary
schema won’t help to easily lift the main result of this paper from binary to
arbitrary schemas.

##  Appendix B Proof of Theorem 5.2

###### Proof of Theorem 5.2.

We slightly adapt the proof of Theorem 12 in [8] since we also have to
consider vertex colors. Nothing interesting happens when we do that, though.

Let $G^{\prime}=(\bar{V}\cup V^{\prime},E^{\prime},\alpha)$ be the vertex-
colored digraph where $V^{\prime}:=\\{v_{(u,w)}\,:\,(u,w)\in\bar{E}\\}$,
$E^{\prime}:=\\{(u,v_{u,w})\,:\,(u,w)\in\bar{E}\\}\cup\\{(v_{u,w},w)\,:\,(u,w)\in\bar{E}\\}$
and $\alpha(u):=\textnormal{{vl}}(u)$ for all $u\in\bar{V}$ and
$\alpha(v_{e}):=\textnormal{{el}}(e)$ for all $v_{e}\in V^{\prime}$. According
to [8], one can compute a coarsest stable coloring $\beta^{\prime}$ of
$G^{\prime}$ that refines $\alpha$ (and therefore also vl) in time
$O((|\bar{V}|+|V^{\prime}|+|E^{\prime}|)\cdot\log(|\bar{V}|+|V^{\prime}|))$.
In the case of $G^{\prime}$ (a graph without edge-colors), stable means that
for all $u,v$ such that $\beta^{\prime}(u)=\beta^{\prime}(v)$ it holds that
$|{N}_{\rightarrow}({u},{c})|=|{N}_{\rightarrow}({v},{c})|$ for all
$c\in\textrm{img}(\beta^{\prime})$. Here, ${N}_{\rightarrow}({u},{c})$ denotes
the set of all outgoing $E^{\prime}$-neighbors $w$ of $u$ such that
$\beta^{\prime}(w)=c$.

We will now show that a stable coloring of $\bar{G}$ corresponds to a stable
coloring of $G^{\prime}$ and vice-versa.

($\Rightarrow$): Let $\beta$ be a stable coloring of $\bar{G}$. Let
$\beta^{\prime}$ be the extension of $\beta$ to $G^{\prime}$ where for all
$v_{(u,w)}\in V^{\prime}$ we let
$\beta^{\prime}(v_{(u,w)}):=(\textnormal{{el}}(u,w),\beta(w))$. Now we argue
that $\beta^{\prime}$ is stable on $G^{\prime}$. Notice that the colors on $V$
and on $V^{\prime}$ are distinct, therefore it suffices to consider the
following two cases:

_Case 1_ : Let $u,v\in\bar{V}$ such that
$\beta^{\prime}(u)=\beta^{\prime}(v)$. Notice that $u$ and $v$ only have
neighbors in $V^{\prime}$, therefore for all colors $c\in\textrm{img}(\beta)$
of the original coloring $\beta$, we have
$|{N}_{\rightarrow}({u},{c})|=|{N}_{\rightarrow}({v},{c})|=0$. Next, observe
that for every color $c\in\textrm{img}(\beta)$, there is a one-to-one
correspondence between the set

$\displaystyle{N}_{\rightarrow}^{\lambda}({u},{c})$
$\displaystyle=\\{w\in\bar{V}\,:\,(u,w)\in\bar{E},\
\textnormal{{el}}(u,w)=\lambda,\ \beta(w)=c\\},\;\text{and the set}$
$\displaystyle{N}_{\rightarrow}({u},{d})$
$\displaystyle=\\{v_{(u,w)}\,:\,(u,w)\in\bar{E},\
\textnormal{{el}}(u,w)=\lambda,\ \beta(w)=c\\},\;\text{where
}d=(\lambda,c)\in\textrm{img}(\beta^{\prime}).$

Thus, let $c\in\textrm{img}(\beta^{\prime})$ of the form $(\lambda,d)$. Then
$|{N}_{\rightarrow}({u},{c})|=|{N}_{\rightarrow}^{\lambda}({u},{d})|=|{N}_{\rightarrow}^{\lambda}({v},{d})|=|{N}_{\rightarrow}({v},{c})|$.
I.e., the coloring $\beta^{\prime}$ is stable.

_Case 2_ : Let $v_{e},v_{f}\in V^{\prime}$ such that
$\beta^{\prime}(v_{e})=\beta^{\prime}(v_{f})$. Since there is only one
outgoing neighbor for both $v_{e}$ and $v_{f}$ by construction, it is easy to
see that $|{N}_{\rightarrow}({v_{e}},{d})|=1$ and
$|{N}_{\rightarrow}({v_{f}},{d^{\prime}})|=1$ for specific colors
$d,d^{\prime}\in\textrm{img}(\beta)$ and 0 else. By construction,
$\beta^{\prime}(v_{e})=(\lambda,d)$ and
$\beta^{\prime}(v_{f})=(\lambda^{\prime},d^{\prime})$. Since
$\beta^{\prime}(v_{e})=\beta^{\prime}(v_{f})$, $d=d^{\prime}$ must hold.

($\Leftarrow$): In the backwards-direction, let $\beta^{\prime}$ be a stable
coloring of $G^{\prime}$ and let $\beta$ be the restriction of
$\beta^{\prime}$ to $V$. We must argue, that $\beta$ is a stable coloring for
$\bar{G}$. Notice that for all $v_{(u,v)},v_{(u^{\prime},v^{\prime})}\in
V^{\prime}$ we have that
$\beta^{\prime}(v_{(u,v)})=\beta^{\prime}(v_{(u^{\prime},v^{\prime})})$ if and
only if $\textnormal{{el}}(u,v)=\textnormal{{el}}(u^{\prime},v^{\prime})$ and
$\beta^{\prime}(v)=\beta^{\prime}(v^{\prime})$.

Let $u,v\in\bar{V}$ such that $\beta(u)=\beta(v)$, let
$c\in\textrm{img}(\beta)$ and let
${N}_{\rightarrow}^{\lambda}({u},{c})=\\{w_{1},\dots,w_{\ell}\\}$ for some
$\lambda$. By the above observation, there must be a
$d\in\textrm{img}(\beta^{\prime})$ such that
${N}_{\rightarrow}({u},{d})=\\{v_{(u,w_{1})},\dots,v_{(u,w_{\ell})}\\}$. Since
$\beta^{\prime}(u)=\beta^{\prime}(v)$ this means that
${N}_{\rightarrow}({v},{d})=\\{v_{(v,w_{1}^{\prime})},\dots,v_{(v,w^{\prime}_{\ell})}\\}$,
which by the above observation also means that
$\beta^{\prime}(w^{\prime}_{i})=c$, i.e.,
${N}_{\rightarrow}^{\lambda}({v},{c})=\\{w_{1}^{\prime},\dots,w_{\ell}^{\prime}\\}$.
Hence, the coloring $\beta$ is stable.

Finally, it is clear that if $\beta$ were not a coarsest stable coloring, then
$\beta^{\prime}$ would not be a coarsest stable coloring either. Thus, we can
use the algorithm from [8] to compute a coarsest stable coloring $\beta$ for
$\bar{G}$ that refines vl in time
$O((|\bar{V}|+|V^{\prime}|+|E^{\prime}|)\cdot\log(|\bar{V}|+|V^{\prime}|))=O((|\bar{V}|+|\bar{E}|)\cdot\log(|\bar{V}|+|\bar{E}|))=O((|\bar{V}|+|\bar{E}|)\cdot\log|\bar{V}|)$.
∎

##  Appendix C Missing Proofs in Section 6

Let $D$, $Q\in\textsf{{fc-ACQ}}[\sigma]$ be fixed in this section. Recall that
$\textrm{vars}(\bar{Q})=\textrm{vars}({Q_{\operatorname{col}}})$ and
$G(\bar{Q})=G({Q_{\operatorname{col}}})$.

###  C.1 Fundamental Observations for the Results of Section 6

######  Observation C.1.

For every color $c\in C$ and for every $u\in\textrm{adom}(\bar{D})$ with
$\textnormal{{col}}(u)=c$ we have: $\\{U\,:\,(c)\in
U^{{D_{\operatorname{col}}}}\\}=\textnormal{{vl}}(u)$.

###### Proof.

This trivially follows from the following facts: By definition, $(c)\in
U^{{D_{\operatorname{col}}}}$ iff there exists a $v\in\textrm{adom}(\bar{D})$
with $\textnormal{{col}}(v)=c$ and $(v)\in U^{\bar{D}}$. Furthermore, $(v)\in
U^{\bar{D}}$ iff $U\in\textnormal{{vl}}(v)$. Finally, the coloring col refines
vl, i.e., for all $u,v\in\textrm{adom}(\bar{D})$ with
$\textnormal{{col}}(u)=\textnormal{{col}}(v)$ we have
$\textnormal{{vl}}(u)=\textnormal{{vl}}(v)$. ∎

For every variable $x\in\textrm{vars}(\bar{Q})$ other than the root $x_{1}$,
let $\textit{p}(x)$ be the unique _parent_ of $x$, that is the unique
$z\in\textrm{vars}(\bar{Q})$ such that $z<x$ and $e:=\\{x,z\\}$ is an edge in
$G(\bar{Q})$. We write $\textit{pe}(x)$ to denote the edge
$\\{\textit{p}(x),x\\}$ connecting $x$ with its parent $\textit{p}(x)$.
Conversely, for all $x\in\textrm{vars}(\bar{Q})$, let $\textit{ch}(x)$ be the
set of all children of $x$, i.e., all $y\in\textrm{vars}(\bar{Q})$ such that
$\textit{p}(y)=x$.

Using Lemma 6.2, one obtains:

######  Corollary C.2.

A mapping $\nu:\textrm{vars}(\bar{Q})\to\textbf{dom}$ is a homomorphism from
$\bar{Q}$ to $\bar{D}$ if and only if:

  1. (1)

For all $x\in\textrm{vars}(\bar{Q})$ we have:
$\lambda_{x}\subseteq\textnormal{{vl}}(\nu(x))$, and

  2. (2)

For all $x\in\textrm{vars}(\bar{Q})$ with $x\neq x_{1}$ we have:
$\nu(x)\in{\widehat{N}}_{\rightarrow}^{\lambda}({\nu(y)},{d})$, where
$y=\textit{p}(x)$, $\lambda=\lambda_{\textit{pe}(x)}$ and
$d=\textnormal{{col}}(\nu(x))$.

###### Proof.

Condition (1) is the same as in Lemma 6.2. It remains to show that condition
(2) holds if and only if condition (2) of Lemma 6.2 holds. Notice that for
every edge $e=\\{x,y\\}$ of $G(\bar{Q})$ with $y<x$ it holds that
$y=\textit{p}(x)$ and $\lambda_{e}=\lambda_{\textit{pe}(x)}$. Let $u=\nu(y)$
and $w=\nu(x)$. Then $(u,w)\in\bar{E}$ and
$\textnormal{{el}}(u,w)\supseteq\lambda_{e}$ holds if and only if
$w\in{N}_{\rightarrow}^{\lambda^{\prime}}({u},{d})$ for
$d=\textnormal{{col}}(w)$ and $\lambda^{\prime}\supseteq\lambda_{e}$. This is
the case if and only if
$w\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({u},{d})$, i.e., iff
$\nu(x)\in{\widehat{N}}_{\rightarrow}^{\lambda}({\nu(y)},{d})$. ∎

######  Lemma C.3.

Let $\mu:\textrm{vars}({Q_{\operatorname{col}}})\to C$ be a homomorphism from
${Q_{\operatorname{col}}}$ to ${D_{\operatorname{col}}}$. For every
$x\in\textrm{vars}({Q_{\operatorname{col}}})$ that is not a leaf of $T$, for
every $v\in\bar{V}$ with $\textnormal{{col}}(v)=\mu(x)$, and for every
$z\in\textit{ch}(x)$ we have:
${\widehat{N}}_{\rightarrow}^{\lambda}({v},{d})\neq\emptyset$, where
$\lambda=\lambda_{\textit{pe}(z)}$ and $d=\mu(z)$.

###### Proof.

Let $x\in\textrm{vars}({Q_{\operatorname{col}}})$ with
$\textit{ch}(x)\neq\emptyset$, let $v\in\bar{V}$ such that
$\textnormal{{col}}(v)=\mu(x)=f$ and let $z\in\textit{ch}(x)$. Let
$\lambda=\lambda_{\textit{pe}(z)}$ and $d=\mu(z)$.

Then, $E_{\lambda}(x,z)\in\textrm{atoms}({Q_{\operatorname{col}}})$ and since
$\mu$ is a homomorphism, $(\mu(x),\mu(z))\in
E_{\lambda}^{{D_{\operatorname{col}}}}$, i.e., $(f,d)\in
E_{\lambda}^{{D_{\operatorname{col}}}}$. This means that
${\widehat{\\#}}_{\rightarrow}^{\lambda}({f},{d})>0$, which means that for
every $u\in\bar{V}$ with $\textnormal{{col}}(u)=f$,
${\widehat{N}}_{\rightarrow}^{\lambda}({u},{d})\neq\emptyset$, which means in
particular that ${\widehat{N}}_{\rightarrow}^{\lambda}({v},{d})\neq\emptyset$.
∎

######  Lemma C.4.

Let $\mu:\textrm{vars}({Q_{\operatorname{col}}})\to C$ and
$\nu:\textrm{vars}(\bar{Q})\to\bar{V}$ be mappings such that for all
$x\in\textrm{vars}(\bar{Q})$ we have that:

  1. (a)

$\textnormal{{col}}(\nu(x))=\mu(x)$, and

  2. (b)

$x=x_{1}$ or $\nu(x)\in{\widehat{N}}_{\rightarrow}^{\lambda}({\nu(y)},{d})$
where $y=\textit{p}(x)$, $\lambda=\lambda_{\textit{pe}(x)}$ and $d=\mu(x)$.

Then, $\mu$ is a homomorphism from ${Q_{\operatorname{col}}}$ to
${D_{\operatorname{col}}}$ if and only if $\nu$ is a homomorphism from
$\bar{Q}$ to $\bar{D}$.

###### Proof.

($\Rightarrow$): We use Corollary C.2 to verify that $\nu$ is a homomorphism
from $\bar{Q}$ to $\bar{D}$:

(1): Let $x\in\textrm{vars}(\bar{Q})$ and let $\nu(x)=u$ and $\mu(x)=c$. We
must show that $\textnormal{{vl}}(u)\supseteq\lambda_{x}$. Since $\mu$ is a
homomorphism from ${Q_{\operatorname{col}}}$ to ${D_{\operatorname{col}}}$,
$\lambda_{x}\subseteq\\{U\,:\,(c)\in U^{{D_{\operatorname{col}}}}\\}=:A$.
Since $\textnormal{{col}}(u)=c$ by (a), we have $A=\textnormal{{vl}}(u)$ using
Observation C.1. Thus, $\lambda_{x}\subseteq\textnormal{{vl}}(u)$.

(2): This follows directly from (b).

($\Leftarrow$): Let $x\in\textrm{vars}({Q_{\operatorname{col}}})$ and let
$\mu(x)=c$ and $\nu(x)=u$. Note that $\textnormal{{col}}(u)=c$.

Suppose $U(x)\in\textrm{atoms}({Q_{\operatorname{col}}})$, then we must show
that $(c)\in U^{{D_{\operatorname{col}}}}$. By definition of
${Q_{\operatorname{col}}}$ and $\bar{Q}$, we also have
$U(x)\in\textrm{atoms}(\bar{Q})$. It follows from Corollary C.2 that
$\textnormal{{vl}}(u)\supseteq\lambda_{x}$, and thus in particular
$U\in\textnormal{{vl}}(u)$. According to Observation C.1 it therefore also
holds that $U\in\\{U^{\prime}\,:\,(c)\in
U^{\prime{D_{\operatorname{col}}}}\\}$, i.e., $(c)\in
U^{{D_{\operatorname{col}}}}$.

Suppose there exists a $y\in\textrm{vars}({Q_{\operatorname{col}}})$ such that
$E_{\lambda}(x,y)\in\textrm{atoms}({Q_{\operatorname{col}}})$. Then by
definition of ${Q_{\operatorname{col}}}$, $x<y$ and $\lambda=\lambda_{e}$ for
$e=\\{x,y\\}$. Let $w:=\nu(y)$ and let $d:=\mu(y)$. Again, note that
$\textnormal{{col}}(w)=d$. We must show that $(c,d)\in
E_{\lambda}^{{D_{\operatorname{col}}}}$. It follows from Corollary C.2 that
$w\in{\widehat{N}}_{\rightarrow}^{\lambda}({u},{d})$, i.e.,
${\widehat{\\#}}_{\rightarrow}^{\lambda}({c},{d})>0$. Thus, by definition of
${D_{\operatorname{col}}}$, $(c,d)\in E_{\lambda}^{{D_{\operatorname{col}}}}$.
∎

###  C.2 Proof of Lemma 6.3

If there is a homomorphism $\nu:\textrm{vars}(\bar{Q})\to\bar{V}$ from
$\bar{Q}$ to $\bar{D}$, then let
$\mu:\textrm{vars}({Q_{\operatorname{col}}})\to C$ with
$\mu(x)=\textnormal{{col}}(\nu(x))$ for all
$x\in\textrm{vars}({Q_{\operatorname{col}}})$. Then, according to Corollary
C.2, the mappings $\mu$ and $\nu$ match the requirements (a) and (b) of Lemma
C.4, which means $\mu$ is a homomorphism as well.

If there is a homomorphism $\mu:\textrm{vars}({Q_{\operatorname{col}}})\to C$
from ${Q_{\operatorname{col}}}$ to ${D_{\operatorname{col}}}$, we can combine
Lemma C.4 with Lemma C.3 to obtain a homomorphism
$\nu:\textrm{vars}(\bar{Q})\to\bar{V}$ from $\bar{Q}$ to $\bar{D}$. ∎

###  C.3 Preparing the proof of Lemma 6.4

For the next two lemmas, consider a fixed
$\bar{c}:=(c_{1},\dots,c_{k})\in{\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$
and a fixed homomorphism $\mu:\textrm{vars}({Q_{\operatorname{col}}})\to C$
from ${Q_{\operatorname{col}}}$ to ${D_{\operatorname{col}}}$, that witnesses
$\bar{c}\in{\left\llbracket{Q_{\operatorname{col}}}\right\rrbracket}({D_{\operatorname{col}}})$,
i.e., $\mu(x_{i})=c_{i}$ for all $i\in[k]$. For $\ell\in[k]$, we call an
$\ell$-tuple $(v_{1},\dots,v_{\ell})$ _consistent with_
$\bar{c}:=(c_{1},\dots,c_{k})$, if for all $i\in[\ell]$
$\textnormal{{col}}(v_{i})=c_{i}$, and all $j<i$ where $e:=\\{x_{i},x_{j}\\}$
is an edge in $G(\bar{Q})$ we have
$v_{i}\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i}})$. Note
that $(v_{1})$ is consistent with $\bar{c}$ for every
$v_{1}\in\textrm{adom}(\bar{D})$ with $\textnormal{{col}}(v_{1})=c_{1}$.

######  Lemma C.5.

Let $\ell\in\\{1,\dots,k{-}1\\}$ and let $(v_{1},\dots,v_{\ell})$ be
consistent with $\bar{c}$. Let $x_{j}=\textit{p}(x_{\ell+1})$ and
$\lambda=\lambda_{\textit{pe}(x_{\ell+1})}$. Then,
$(v_{1},\dots,v_{\ell},v_{\ell+1})$ is consistent with $\bar{c}$ for all
$v_{\ell+1}\in{\widehat{N}}_{\rightarrow}^{\lambda}({v_{j}},{c_{\ell+1}})$.

###### Proof.

Let
$v_{\ell+1}\in{\widehat{N}}_{\rightarrow}^{\lambda}({v_{j}},{c_{\ell+1}})$. It
suffices to show that $(v_{1},\dots,v_{\ell},v_{\ell+1})$ is consistent. Let
$i\in[\ell+1]$. Clearly, $\textnormal{{col}}(v_{i})=c_{i}$ holds. Let $j<i$
such that $e:=\\{x_{i},x_{j}\\}$ is an edge in $G(\bar{Q})$. If
$i\leqslant\ell$, then
$v_{i}\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i}})$ since
$(v_{1},\dots,v_{\ell})$ is consistent with $\bar{c}$. If $i=\ell+1$, then we
have already seen that $x_{j}$ is unique. This means we have
$x_{j}=\textit{p}(x_{i})$ and $e=\textit{pe}(x_{i})$. By choice of
$v_{i}=v_{\ell+1}$,
$v_{i}\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i}})$.

Thus, $(v_{1},\dots,v_{\ell},v_{\ell+1})$ is consistent. ∎

######  Lemma C.6.

For every $\ell\in[k]$ the following is true: Every $\ell$-tuple consistent
with $\bar{c}$ is a partial output of $\bar{Q}$ over $\bar{D}$ of color
$\bar{c}$; and vice versa, every partial output of $\bar{Q}$ over $\bar{D}$ of
color $\bar{c}$ is consistent with $\bar{c}$.

###### Proof.

Let $(v_{1},\dots,v_{\ell})$ be consistent with $\bar{c}$. We show that there
exists a homomorphism $\nu:\textrm{vars}(\bar{Q})\to\bar{V}$ from $\bar{Q}$ to
$\bar{D}$ such that $\nu(x_{i})=v_{i}$ for all $i\in[\ell]$ and
$\textnormal{{col}}(\nu(z))=\mu(z)$ for all $z\in\textrm{vars}(\bar{Q})$. From
that it directly follows that $(v_{1},\dots,v_{\ell})$ is a partial output.

We define $\nu$ along the order $<$ on $\textrm{vars}(\bar{Q})$ (which implies
a top-down approach). For all $i\in[\ell]$, let $\nu(x_{i}):=v_{i}$.

For all $z\in\textrm{vars}(\bar{Q})$ such that $z\neq x_{i}$ for all
$i\in[\ell]$, let $y=\textit{p}(z)$. Since $y<z$, $\nu(y)$ is already defined
and $\textnormal{{col}}(\nu(y))=\mu(y)$. Let $u=\nu(y)$, $f=\mu(z)$ and
$e:=\textit{pe}(z)$. By Lemma C.3 we know that
${\widehat{N}}_{\rightarrow}^{\lambda_{e}}({u},{f})$ is not empty. We choose
an arbitrary $w\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({u},{f})$ and let
$\nu(z):=w$. Clearly, $\textnormal{{col}}(\nu(w))=f=\mu(z)$. According to
Lemma C.4, $\nu$ is a homomorphism.

Let $(v_{1},\dots,v_{\ell})$ be a partial output of $\bar{Q}$ over $\bar{D}$
of color $\bar{c}$. We have to show that it is consistent with $\bar{c}$. Let
$i\in[\ell]$. Clearly, $\textnormal{{col}}(v_{i})=c_{i}$. Let $j<i$ such that
$e:=\\{x_{j},x_{i}\\}$ is an edge in $G(\bar{Q})$. Since
$(v_{1},\dots,v_{\ell})$ is a partial output, there exists a homomorphism
$\nu$ from $\bar{Q}$ to $\bar{D}$ such that $\nu(x_{i})=v_{i}$ and
$\nu(x_{j})=v_{j}$. Notice that $x_{j}=\textit{p}(x_{i})$,
$e=\textit{pe}(x_{i})$ and $\textnormal{{col}}(v_{i})=c_{i}$. Thus, by
Corollary C.2 we get that
$v_{i}\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i}})$. ∎

###  C.4 Proof of Lemma 6.4

  1. (a)

Since
$(v_{1},\dots,v_{k})\in{\left\llbracket\bar{Q}\right\rrbracket}(\bar{D})$,
there exists a homomorphism $\nu:\textrm{vars}(\bar{Q})\to\bar{V}$ from
$\bar{Q}$ to $\bar{D}$ such that $\nu(x_{i})=v_{i}$ for all $i\in[k]$. Let
$\mu:\textrm{vars}({Q_{\operatorname{col}}})\to C$ with
$\mu(x)=\textnormal{{col}}(\nu(x))$ for all
$x\in\textrm{vars}({Q_{\operatorname{col}}})$. Using Corollary C.2, we can
apply Lemma C.4 to $\mu$ and $\nu$. Thus, $\mu$ is a homomorphism witnessing
that
$(\textnormal{{col}}(v_{1}),\dots,\textnormal{{col}}(v_{k}))\in{\left\llbracket
Q\right\rrbracket}({D_{\operatorname{col}}})$.

  2. (b)

For every $v_{1}\in\textrm{adom}(\bar{D})$ with
$\textnormal{{col}}(v_{1})=c_{1}$, $(v_{1})$ is a partial output of $\bar{Q}$
over $\bar{D}$ of color $\bar{c}$ because $(v_{1})$ is consistent with
$\bar{c}$. If $(v_{1},\ldots,v_{i})$ is a partial output of $\bar{Q}$ over
$\bar{D}$ of color $\bar{c}$, then it is also consistent with $\bar{c}$. If
$e=\\{x_{j},x_{i+1}\\}$ is an edge of $G(\bar{Q})$ with $x_{j}<x_{i+1}$, then
$(v_{1},\ldots,v_{i},v_{i+1})$ is also consistent with $\bar{c}$ for every
$v_{i+1}\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i+1}})$ and
thus also a partial output of $\bar{Q}$ over $\bar{D}$ of color $\overline{c}$
for every
$v_{i+1}\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i+1}})$.
${\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v_{j}},{c_{i+1}})\neq\emptyset$
holds by Lemma C.3. ∎

###  C.5 Proof of Lemma 6.5

We prove this lemma by induction over the tree $T$.

_Base case_ : Let $v\in\bar{V}$, $\textnormal{{col}}(v)=c$ and let $x$ be a
leaf. Then (b) trivially holds, since $\textit{ch}(x)=\emptyset$. To prove
(a), notice that $V(T_{x})=\\{x\\}$ and $E(T_{x})=\emptyset$. Thus, there is
at most one $\nu:V(T_{x})\to\bar{V}$ such that $\nu(x)=v$; and it exists if
and only if $\textnormal{{vl}}(\nu(x))\supseteq\lambda_{x}$. By definition,
$f_{\downarrow}(c,x)=f_{1}(c,x)$ and $f_{1}(c,x)=1$ if and only if
$\textnormal{{vl}}(v_{c})\supseteq\lambda_{x}$ and 0 otherwise. Since
$\textnormal{{col}}(v)=c$, we have
$\textnormal{{vl}}(v)=\textnormal{{vl}}(v_{c})$ according to Observation C.1.
Hence, condition (a)(1) holds. Condition (a)(2) holds trivially, because
$E(T_{x})=\emptyset$.

_Inductive step_ : Let $x\in T$ such that $x$ is not a leaf, and let
$v\in\bar{V}$ with $\textnormal{{col}}(v)=c$.

_Induction hypothesis_ : For every $y\in\textit{ch}(x)$, every $d\in C$ and
every $w\in\bar{V}$ with $\textnormal{{col}}(w)=d$, $f_{\downarrow}(d,y)$ is
the number of mappings $\nu:V(T_{y})\to\bar{V}$ satisfying $\nu(y)=w$ and

  1. (1)

for every $x^{\prime}\in V(T_{y})$ we have
$\textnormal{{vl}}(\nu(x^{\prime}))\supseteq\lambda_{x^{\prime}}$, and

  2. (2)

for every edge $e=\\{x^{\prime},y^{\prime}\\}$ in $T_{y}$ with
$x^{\prime}<y^{\prime}$ we have
$(\nu(x^{\prime}),\nu(y^{\prime}))\in\bar{E}$ and
$\textnormal{{el}}(\nu(x^{\prime}),\nu(y^{\prime}))\supseteq\lambda_{e}$.

_Claim_ : For every $y\in\textit{ch}(x)$, $g(c,y)$ is the number of mappings
$\nu:\\{x\\}\cup V(T_{y})\to\bar{V}$ satisfying $\nu(x)=v$ and

  1. (1)

for every $x^{\prime}\in V(T_{y})$ we have
$\textnormal{{vl}}(\nu(x^{\prime}))\supseteq\lambda_{x^{\prime}}$, and

  2. (2)

for every edge $e=\\{x^{\prime},y^{\prime}\\}$ in $T_{y}$ with
$x^{\prime}<y^{\prime}$
we have $(\nu(x^{\prime}),\nu(y^{\prime}))\in\bar{E}$ and
$\textnormal{{el}}(\nu(x^{\prime}),\nu(y^{\prime}))\supseteq\lambda_{e}$, and

  3. (3)

for $e=\\{x,y\\}$ we have $(\nu(x),\nu(y))\in\bar{E}$ and
$\textnormal{{el}}(\nu(x),\nu(y))\supseteq\lambda_{e}$.

###### Proof.

Notice that (1) and (2) are the same conditions as in the induction
hypothesis. Since every mapping has to map $x$ to $v$, every child
$y\in\textit{ch}(x)$ has to be mapped to a $w$ such that $(v,w)\in\bar{E}$ and
$\textnormal{{el}}(v,w)\supseteq\lambda_{e}$ for $e=\\{x,y\\}$ according to
(3), i.e., we know that $y$ has to be mapped to an outgoing $\bar{E}$-neighbor
$w$ of $v$ such that $\textnormal{{el}}(v,w)\supseteq\lambda_{e}$. That is,
any $w\in{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v},{c^{\prime}})$ for any
$c^{\prime}\in C$ is a valid choice, i.e., we have
$|{\widehat{N}}_{\rightarrow}^{\lambda_{e}}({v},{c^{\prime}})|={\widehat{\\#}}_{\rightarrow}^{\lambda_{e}}({c},{c^{\prime}})$
choices for $w$ for all $c^{\prime}\in C$. Once we chose a $w$ in this way and
let $\nu(y)=w$, we can use the induction hypothesis to get the number of
choices we have to map the remaining variables such that $\nu(y)=w$ and (1)
and (2) hold, which is $f_{\downarrow}(\textnormal{{col}}(w),y)$. Thus, we get
that the number of mappings is $\sum_{c^{\prime}\in
C}f_{\downarrow}(c^{\prime},y)\cdot{\widehat{\\#}}_{\rightarrow}^{\lambda_{e}}({c},{c^{\prime}})$,
which is $g(c,y)$ by definition. ∎

Notice that condition (1) is the same as (b)(1) and if we merge the conditions
(2) and (3) above, we get the condition (2)(b). Therefore, it follows from
this claim that statement (b) holds.

_Claim_ : $f_{\downarrow}(c,x)$ is the number of mappings
$\nu:V(T_{x})\to\bar{V}$ satisfying $\nu(x)=v$ and

  1. (1)

for every $x^{\prime}\in V(T_{x})$ we have
$\textnormal{{vl}}(\nu(x^{\prime}))\supseteq\lambda_{x^{\prime}}$, and

  2. (2)

for every edge $e=\\{x^{\prime},y^{\prime}\\}$ in $T_{x}$ with
$x^{\prime}<y^{\prime}$
we have $(\nu(x^{\prime}),\nu(y^{\prime}))\in\bar{E}$ and
$\textnormal{{el}}(\nu(x^{\prime}),\nu(y^{\prime}))\supseteq\lambda_{e}$.

###### Proof.

In the same way as in the base case, we can see that the number of mappings is
0 unless $f_{1}(c,x)$ is 1. If $f_{1}(c,x)$ is 1, then, according to (2), a
valid mapping must put every $y\in\textit{ch}(x)$ on an outgoing
$\bar{E}$-neighbor $w$ of $v$ such that
$\textnormal{{el}}(v,w)\supseteq\lambda_{e}$ where $e=\\{x,y\\}$.

Thus, every valid mapping must fulfill the requirements (1)-(3) of the
previous claim for every $y\in\textit{ch}(y)$ if we restrict it to
$\\{x\\}\cup T_{y}$. On the other hand, these trees only intersect in $x$ for
all children. Thus, we can combine every map $\nu:\\{x\\}\cup
V(T_{y})\to\bar{V}$ of a child $y$ that adheres to these requirements with
every other map $\nu^{\prime}:\\{x\\}\cup V(T_{y^{\prime}})$ of every other
child $y^{\prime}$ that adheres to these requirements, and we will get a map
$\nu$ that satisfies (1) and (2). Thus, by the previous claim, we get a total
of $\prod_{y\in\textit{ch}(x)}g(c,y)$ choices if $f_{1}(c,x)$ is 1 and 0
choices if $f_{1}(c,x)$ is 0, which is precisely $f_{\downarrow}(c,x)$. ∎

It follows directly from this claim that statement (a) holds.∎

##  Appendix D A modified approach that avoids the exponential dependency on
$\sigma$

Before finalizing this paper, we had two versions of our construction. Version
1 is clean, easy to understand, and easily proved to be correct — but has an
exponential dependency on the schema. Version 2 is more complicated, more
difficult to be proved to be correct — but avoids the exponential dependency
on the schema. Once having understood the construction of Version 1, we
believe that the overall idea of Version 2 can be explained with only moderate
additional effort. But presenting only Version 2 without prior explanation of
Version 1, we believe, the main idea of our index structure (and its
correctness) would have been much harder to grasp. Version 2 works as follows.

In the definition of the color-index structure $\textsf{{DS}}_{D}$, instead of
$\widehat{N}_{\rightarrow}^{\lambda}$ and
$\widehat{\\#}_{\rightarrow}^{\lambda}$, we only need
$N_{\rightarrow}^{\lambda}$ and $\\#_{\rightarrow}^{\lambda}$ for each
$\lambda\in L_{\bar{E}}$. But the definition of the color database
${D_{\operatorname{col}}}$ and the color schema $\sigma_{\operatorname{col}}$
are quite different than in Section 5: $\sigma_{\operatorname{col}}$ has only
one binary relation symbol $E$, all the unary relation symbols of
$\bar{\sigma}$, and further unary relation symbols $U_{(R,\rightarrow)}$ and
$U_{(R,\leftarrow)}$ for each binary symbol $R$ in $\sigma$.

The color-database ${D_{\operatorname{col}}}$ is constructed as follows.
Initialize it to be the empty database. For each unary symbol
$S\in\bar{\sigma}$ and each color $c\in C$, insert into the $S$-relation of
${D_{\operatorname{col}}}$ the element $c$ iff the $S$-relation of $\bar{D}$
contains a node of color $c$. For each edge-label $\lambda\in L_{\bar{E}}$ and
all colors $c,c^{\prime}\in C$ with
${\\#}_{\rightarrow}^{\lambda}({c},{c^{\prime}})>0$, insert into the active
domain a new element $e_{\lambda,c,c^{\prime}}$ and insert into the
$E$-relation of ${D_{\operatorname{col}}}$ an edge from $c$ to
$e_{\lambda,c,c^{\prime}}$ and an edge from $e_{\lambda,c,c^{\prime}}$ to
$c^{\prime}$. Furthermore, for every $(R,\ast)\in\lambda$, insert into the
$U_{(R,\ast)}$-relation of ${D_{\operatorname{col}}}$ the element
$e_{\lambda,c,c^{\prime}}$.

In Section 6, the definition of the color query ${Q_{\operatorname{col}}}$ has
to be modified as follows. First, initialize the body of
${Q_{\operatorname{col}}}$ to contain all the unary atoms present in the body
of $\bar{Q}$. Then, we enrich the body of the query as follows: We loop
through the edges $e$ of the Gaifman graph $G(\bar{Q})$ of $\bar{Q}$. For each
$e$, we proceed as follows. Introduce a new variable $z_{e}$. Let $x<y$ be the
two variables that are the endpoints of edge $e$. Insert into the body of
${Q_{\operatorname{col}}}$ the new atoms $E(x,z_{e}),E(z_{e},y)$ and,
moreover, $U_{(R,\ast)}(z_{e})$ for every $(R,\ast)\in\lambda_{e}$ (where
$\lambda_{e}$ is defined in the same way as in Section 6). This completes the
definition of the body of ${Q_{\operatorname{col}}}$. The head of
${Q_{\operatorname{col}}}$ contains the same variables as the head of
$\bar{Q}$, and in addition to these, also the variables $z_{e}$ for all those
edges $e$ of $G(\bar{Q})$ where both endpoints of $e$ belong to the head of
$\bar{Q}$. For later use let us write $f$ for a bijection that maps all these
edges $e$ to the numbers $1,\dots,k{-}1$, where $k$ is the number of variables
in the head of $\bar{Q}$. The reason why we have to add these variables
$z_{e}$ to the head of ${Q_{\operatorname{col}}}$ is to ensure that the query
${Q_{\operatorname{col}}}$ is an fc-ACQ (this is needed for being able to use
Theorem 4.3).

Finally, the details on the evaluation phase for enum have to be modified
accordingly: We use Theorem 4.3 to enumerate (with constant delay) the result
tuples of ${Q_{\operatorname{col}}}$ on ${D_{\operatorname{col}}}$. Now, these
tuples are of the form $t:=(c_{1},\dots,c_{k},e_{1},\dots,e_{k{-}1})$, where
the $c_{1},\dots,c_{k}$ are colors in $C$, and the $e_{1},\dots,e_{k{-}1}$ are
elements of ${D_{\operatorname{col}}}$ of the form $e_{\lambda,c,c^{\prime}}$.

In the enumeration algorithm presented in Section 6 we now have to do the
following modifications: $\overline{c}$ is replaced by $t$. And in the final
for-loop we replace $\hat{N}_{\rightarrow}^{\lambda_{e}}$ by
$N_{\rightarrow}^{\mu_{e}}$, where $\mu_{e}$ is defined as follows. Let
$j:=f(e)$. Let $\mu_{e}$ consist of exactly those $(R,\ast)$, for which
$e_{j}$ is in the $U_{(R,\ast)}$-relation of ${D_{\operatorname{col}}}$. A
careful inspection of the obtained algorithm shows that it indeed enumerates,
without duplicates, all the tuples in the result of $Q$ on $D$.

Note that also the proof of our counting result can be adapted in such a way
that it builds upon Version 2 instead of Version 1. We plan to include details
on Version 2 (as well as correctness proofs) in the journal version of this
paper.