University of
Amsterdamb.d.tencate@uva.nlhttps://orcid.org/0000-0002-2538-5846Supported by
the European Union’s Horizon 2020 research and innovation programme
(MSCA-101031081). Universitat Pompeu
Fabravictor.dalmau@upf.eduhttps://orcid.org/0000-0002-9365-7372Supported by
the MiCin under grants PID2019-109137GB-C22 and PID2022-138506NB-C22, and the
Maria de Maeztu program (CEX2021-001195-M). University of California Santa
Cruz and IBM Research
kolaitis@ucsc.eduhttps://orcid.org/0000-0002-8407-8563Partially supported by
NSF Grant IIS-1814152. University of California Santa
Cruzwwu53@ucsc.eduhttps://orcid.org/0009-0004-3341-1508 Balder ten Cate,
Victor Dalmau, Phokion G. Kolaitis, and Wei-Lin Wu [500]Theory of computation
Logic and databases Graham Cormode and Michael Shekelyan 2 27th International
Conference on Database Theory (ICDT 2024) ICDT 2024 ICDT 2024 March 25–28,
2024 Paestum, Italy 290 8

# When do homomorphism counts help in query algorithms?

Balder ten Cate  Victor Dalmau  Phokion G. Kolaitis  Wei-Lin Wu

###### Abstract

A query algorithm based on homomorphism counts is a procedure for determining
whether a given instance satisfies a property by counting homomorphisms
between the given instance and finitely many predetermined instances. In a
left query algorithm, we count homomorphisms from the predetermined instances
to the given instance, while in a right query algorithm we count homomorphisms
from the given instance to the predetermined instances. Homomorphisms are
usually counted over the semiring ${\rm Nature}$ of non-negative integers; it
is also meaningful, however, to count homomorphisms over the Boolean semiring
$\mathbb{B}$, in which case the homomorphism count indicates whether or not a
homomorphism exists. We first characterize the properties that admit a left
query algorithm over $\mathbb{B}$ by showing that these are precisely the
properties that are both first-order definable and closed under homomorphic
equivalence. After this, we turn attention to a comparison between left query
algorithms over $\mathbb{B}$ and left query algorithms over ${\rm Nature}$. In
general, there are properties that admit a left query algorithm over ${\rm
Nature}$ but not over $\mathbb{B}$. The main result of this paper asserts that
if a property is closed under homomorphic equivalence, then that property
admits a left query algorithm over $\mathbb{B}$ if and only if it admits a
left query algorithm over ${\rm Nature}$. In other words and rather
surprisingly, homomorphism counts over ${\rm Nature}$ do _not_ help as regards
properties that are closed under homomorphic equivalence. Finally, we
characterize the properties that admit both a left query algorithm over
$\mathbb{B}$ and a right query algorithm over $\mathbb{B}$.

###### keywords:

query algorithms, homomorphism, homomorphism counts, conjunctive query,
constraint satisfaction

###### category:

##  1 Introduction

Consider a scenario in which we are interested in a certain property of
database instances and we wish to find out whether or not a given instance $A$
satisfies that property by asking finitely many predetermined queries against
$A$. Naturally, which properties can be checked in this way depends on what
kind of queries we are allowed to ask. For example, if we are restricted to
using Boolean conjunctive queries and evaluating them under set semantics,
then only properties that are invariant under homomorphic equivalence stand a
chance to be checked in this way. In particular, this means that we cannot
test in this way whether a relation in a given instance contains precisely 5
tuples. In contrast, if we are also allowed to ask for the number of
homomorphisms from a given conjunctive query to $A$ (a feature that is
supported by actual database management systems), then we can find out much
more about the instance $A$, including whether it satisfies the aforementioned
property.

In this paper, we embark on a systematic study of this scenario. As usual, by
a _property_ of instances we mean a class $\mathcal{C}$ of instances closed
under isomorphisms. We write $\mathbb{B}$ for the Boolean semiring with $\lor$
and $\land$ as its operations, while we write ${\rm Nature}$ for the semiring
of the non-negative integers with $+$ and $\times$ as its operations.
Formally, we say that a class $\mathcal{C}$ of instances admits a _left query
algorithm over $\mathbb{B}$_ if there exists a finite set
$\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ of instances such that the membership
in $\mathcal{C}$ of an arbitrary instance $A$ is completely determined by
$\hom_{\mathbb{B}}(\mathcal{F},A)$, where $\hom_{\mathbb{B}}(\mathcal{F},A)$
is the $k$-tuple of Boolean values indicating for each $i\leq k$ whether or
not there is a homomorphism $F_{i}\to A$. Similarly, we say that a class
$\mathcal{C}$ of instances admits a _left query algorithm over ${\rm Nature}$_
if there exists a finite set $\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ of
instances such that the membership in $\mathcal{C}$ of an arbitrary instance
$A$ is completely determined by $\hom_{\rm Nature}(\mathcal{F},A)$, where
$\hom_{\rm Nature}(\mathcal{F},A)$ is the $k$-tuple of non-negative integers
indicating for each $i\leq k$ how many homomorphisms from $F_{i}$ to $A$ there
are. _Right query algorithms_ over $\mathbb{B}$ and over ${\rm Nature}$ are
defined similarly, except that we now count the homomorphisms from $A$ to each
$F_{i}$ instead of the homomorphisms from each $F_{i}$ to $A$.

Assume that the class $\mathcal{C}$ of instances under consideration admits a
left query algorithm over $\mathbb{B}$ or over ${\rm Nature}$ using the set
$\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$. Let $q^{F_{i}}$ be the canonical
conjunctive query associated with the instance $F_{i}$, $1\leq i\leq k$. Then
$\hom_{\mathbb{B}}(\mathcal{F},A)$ is the $k$-tuple of Boolean values denoting
whether $q^{F_{i}}(A)=1$ or $q^{F_{i}}(A)=0$, i.e., whether $q^{F_{i}}$ is
true or false on $A$ under set semantics. Similarly, $\hom_{\rm
Nature}(\mathcal{F},A)$ is the $k$-tuple of non-negative integers that are the
answers to $q^{F_{i}}$ on $A$ under bag-set semantics. Thus, intuitively, a
class $\mathcal{C}$ admits a left query algorithm over $\mathbb{B}$ or over
${\rm Nature}$ if membership in $\mathcal{C}$ is answerable by evaluating
finitely many Boolean conjunctive queries under set semantics or under bag-set
semantics, respectively. Observe that these are data complexity notions
because the queries $q^{F_{1}},\ldots,q^{F_{k}}$ are fixed while the instance
$A$ varies. Observe also that these two notions differ in expressive power:
for example, if $\mathcal{C}$ is the class of instances in which a particular
relation $R$ has precisely 5 tuples, then $\mathcal{C}$ admits a left query
algorithm over ${\rm Nature}$, but not over $\mathbb{B}$.

There are two pieces of earlier work (each with different motivation and
results) where the notion of a left query algorithm or variants of this notion
have been explored. First, Bielecki and Van den Bussche [4] defined what it
means for a query $p$ to be _derivable_ through interrogation with a query
language $L$ using a _database independent strategy_ , where the interrogation
consists of asking the cardinality $|q(A)|$ for finitely many queries $q\in
L$. When $L$ is the language of conjunctive queries with no existential
quantifiers, such strategies correspond to left-query algorithms over
$\mathbb{N}$; whereas, when $L$ is the language of Boolean conjunctive
queries, they correspond to left-query algorithms over $\mathbb{B}$. Second,
when the instances are unordered graphs, the concept of a left query algorithm
over ${\rm Nature}$ was studied by Chen et al. [9] under the name _non-
adaptive query algorithm_ ; note that Chen et al. [9] were apparently unaware
of the work by Bielecki and Van den Bussche [4]. The term “non-adaptive” is
apt as it conveys that the instances $F_{i}$ (or the associated conjunctive
queries $q^{F_{i}}$), $1\leq i\leq k$, in the set $\mathcal{F}$ depend only on
the class $\mathcal{C}$ and do not change during a run of the query algorithm.
It is also natural to consider _adaptive query algorithms_ , where the
instances $F_{i}$, $1\leq i\leq k$, are not required to be fixed up front. In
fact, such adaptive notions were explored in both [4] and [9]. In particular,
Chen et al. [9] showed that adaptive left query algorithms over ${\rm Nature}$
are more powerful than non-adaptive ones over ${\rm Nature}$. It is easy to
see, however, that the existence of an adaptive left query algorithm over
$\mathbb{B}$ implies the existence of a non-adaptive one over $\mathbb{B}$. In
this sense, adaptive left query algorithms over $\mathbb{B}$ are not more
powerful than non-adaptive ones over $\mathbb{B}$. Also, since in this paper
we study non-adaptive algorithms only (but over both $\mathbb{B}$ and ${\rm
Nature}$), we will not use the adjective “non-adaptive” here.

Our investigation begins by focusing on left query algorithms over
$\mathbb{B}$. It is easy to see that a class of instances admits a left query
algorithm over $\mathbb{B}$ if and only if it is definable by a Boolean
combination of conjunctive queries. Using tools developed by Rossman [27] to
prove the preservation-under-homomorphisms theorem in the finite, we obtain a
deeper characterization of such classes by showing that a class of instances
admits a left query algorithm over $\mathbb{B}$ if and only if it is both
first-order definable and closed under homomorphic equivalence. Clearly, if a
class of instances is closed under homomorphic equivalence, then it is a
(possibly infinite) union of homomorphic equivalence classes. We show that if
$\mathcal{C}$ is a finite union of homomorphic-equivalence classes, then
$\mathcal{C}$ admits a left query algorithm over $\mathbb{B}$ if and only if
every homomorphic-equivalence class in that union admits a left query
algorithm over $\mathbb{B}$. In contrast, a similar result does not hold for
arbitrary infinite unions.

After this, we turn attention to a comparison between left query algorithms
over $\mathbb{B}$ and left query algorithms over ${\rm Nature}$. As discussed
earlier, left query algorithms over ${\rm Nature}$ are more powerful than left
query algorithms over $\mathbb{B}$. The intuitive reason is that left query
algorithms over $\mathbb{B}$ do not differentiate between homomorphically
equivalent instances, while those over ${\rm Nature}$ do. The main (and
technically more challenging) result of this paper reveals that, in a precise
sense, this is the _only_ reason why left query algorithms over ${\rm Nature}$
are more powerful than left query algorithms over $\mathbb{B}$. More
precisely, our main theorem asserts that if a class $\mathcal{C}$ is closed
under homomorphic equivalence, then $\mathcal{C}$ admits a left query
algorithm over $\mathbb{B}$ if and only if $\mathcal{C}$ admits a left query
algorithm over ${\rm Nature}$. In other words and rather surprisingly,
homomorphism counts over ${\rm Nature}$ do _not_ help as regards properties
that are closed under homomorphic equivalence. As an immediate consequence, a
constraint satisfaction problem has a left query algorithm over ${\rm Nature}$
if and only if this problem is first-order definable.

Finally, we characterize the properties that admit both a left query algorithm
over $\mathbb{B}$ and a right query algorithm over $\mathbb{B}$. In
particular, we show that a class $\mathcal{C}$ of instances admits both a left
query algorithm over $\mathbb{B}$ and a right query algorithm over
$\mathbb{B}$ if and only if $\mathcal{C}$ is definable by a Boolean
combination of Berge-acyclic conjunctive queries. To see the point of this
result, recall that if a class admits a left query algorithm over
$\mathbb{B}$, then it is definable by a Boolean combination of conjunctive
queries. Thus, if the class admits also a right query algorithm over
$\mathbb{B}$, then these conjunctive queries can be taken to be Berge-acyclic.

Related work A classical result by Lovász [25] characterizes graph isomorphism
in terms of “left” homomorphism counts: two graphs $G$ and $H$ are isomorphic
if and only if for every graph $F$, the number of homomorphisms from $F$ to
$G$ is equal to the number of homomorphisms from $F$ to $H$. In more recent
years, there has been a study of relaxations of isomorphisms obtained by
requiring that the number of homomorphisms from $F$ to $G$ is equal to the
number of homomorphisms from $F$ to $H$, where $F$ ranges over a restricted
class of graphs [12, 11, 6]. Furthermore, a study of relaxations of
isomorphism obtained by counting the number of “right” homomorphisms to a
restricted class was carried out in [3].

There has been an extensive body of research on answering queries under
various types of access restrictions. Closer in spirit to the work reported
here is view determinacy, which is the question of whether the answers to a
query can be inferred when given access only to a certain view of the database
instance [26]. We note that view determinacy is typically concerned with non-
Boolean queries and non-Boolean views; in contrast, the question of whether a
class admits a left query algorithm over $\mathbb{B}$ can be interpreted as
the question of whether there is a finite set of Boolean conjunctive queries
that determine a given Boolean query. A study of view determinacy under bag-
set semantics was recently initiated in [24]. Section 7 contains additional
commentary on the relationship between left query algorithms over ${\rm
Nature}$ and view determinacy under bag-set semantics.

##  2 Basic Notions

Relational database instances A _relational database schema_ or, simply, a
_schema_ is a finite set $\sigma=\\{R_{1},\ldots,R_{m}\\}$ of relation symbols
$R_{i}$, each of which has a positive integer $r_{i}$ as its associated
_arity_. A _relational database instance_ or, simply, an _instance_ is a tuple
$A=(R_{1}^{A},\ldots,R_{m}^{A})$, where each $R_{i}^{A}$ is a relation of
arity $r_{i}$. The _facts_ of the instance $A$ are the tuples in the relations
$R_{i}^{A}$, $1\leq i\leq m$. The _active domain of $A$_, denoted
$\mathrm{adom}(A)$, is the set of all entries occurring in the facts of $A$.
All instances $A$ considered are assumed to be finite, i.e.,
$\mathrm{adom}(A)$ is finite. A _graph_ is an instance $A$ over a schema
consisting of a binary relation symbol $E$ and such that $E^{A}$ is a binary
relation that is symmetric and irreflexive.

The _incidence multigraph_ $\mathrm{inc}(A)$ of an instance $A$ is the
bipartite multigraph whose parts are the sets $\mathrm{adom}(A)$ and
$\mathrm{block}(A)=\\{(R,t):\text{\begin{math}R\in\sigma\end{math} and
\begin{math}t\in R^{A}\end{math}}\\}$, and whose edges are the pairs
$(a,(R,t))$ such that $a$ is one of the entries of $t$. A _path of length $n$_
in $A$ is a sequence $a_{0},a_{1},\ldots,a_{n}$ of elements in
$\mathrm{adom}(A)$ for which there are elements $b_{1},\ldots,b_{n}$ in
$\mathrm{block}(A)$ such that the sequence
$a_{0},b_{1},a_{1},\ldots,b_{n},a_{n}$ is a path in $\mathrm{inc}(A)$ in the
standard graph-theoretic sense (disallowing traversing an edge twice in
succession in opposite directions). Two elements $a$ and $a^{\prime}$ in
$\mathrm{adom}(A)$ are _connected_ if $a=a^{\prime}$ or there is a path
$a_{0},a_{1},\ldots,a_{n}$ in $A$ with $a=a_{0}$ and $a^{\prime}=a_{n}$. We
say that $A$ is _connected_ if every two elements $a$ and $a^{\prime}$ in
$\mathrm{adom}(A)$ are connected. A _cycle of length $n$_ in $A$ is a path of
length $n$ in $A$ with $a_{n}=a_{0}$. We say $A$ is _acyclic_ if it contains
no cycles. The _girth of $A$_ is the shortest length of a cycle in $A$ or
$\infty$ if $A$ is acyclic.

An instance $A$ is a _subinstance_ of an instance $B$ if $R^{A}\subseteq
R^{B}$, for every $R\in\sigma$.

A _class_ $\mathcal{C}$ of instances is a collection of instances over the
same schema that is closed under isomorphism (i.e., if $A\in\mathcal{C}$ and
$B$ is isomorphic to $A$, then $B\in\mathcal{C}$). Every decision problem $P$
about instances can be identified with the class of all “yes” instances of
$P$.

Homomorphisms, conjunctive queries, and canonical instances A _homomorphism_
from an instance $A$ to an instance $B$ is a function
$h:\mathrm{adom}(A)\to\mathrm{adom}(B)$ such that for every relation symbol
$R\in\sigma$ with arity $r$ and for all elements $a_{1},\ldots,a_{r}$ in
$\mathrm{adom}(A)$ with $(a_{1},\ldots,a_{r})\in R^{A}$, we have
$(h(a_{1}),\ldots,h(a_{r}))\in R^{B}$. We write $h:A\rightarrow B$ to denote
that $h$ is a homomorphism from $A$ to $B$; we also write $A\rightarrow B$ to
denote that there is a homomorphism from $A$ to $B$. We say that $A$ and $B$
are _homomorphically equivalent_ , denoted $A\mathrel{\leftrightarrow}B$, if
$A\mathrel{\rightarrow}B$ and $B\mathrel{\rightarrow}A$. Clearly,
$\mathrel{\leftrightarrow}$ is an equivalence relation on instances. We write
$\left[A\right]_{\mathrel{\leftrightarrow}}$ to denote the equivalence class
of $A$ with respect to $\mathrel{\leftrightarrow}$, i.e.,
$\left[A\right]_{\mathrel{\leftrightarrow}}=\\{B:B\mathrel{\leftrightarrow}A\\}$.

Let $\mathcal{C}$ be a class of instances. We say that $\mathcal{C}$ is
_closed under homomorphic equivalence_ if whenever $A\in{\mathcal{C}}$ and
$A\mathrel{\leftrightarrow}B$, we have that $B\in{\mathcal{C}}$. As an
example, for every instance $A$, we have that the equivalence class
$\left[A\right]_{\mathrel{\leftrightarrow}}$ is closed under homomorphic
equivalence. For a different example, the class of all $3$-colorable graphs is
closed under homomorphic equivalence.

We assume familiarity with the syntax and the semantics of first-order logic
(FO). For a FO-sentence $\varphi$, we denote by $\mathrm{Mod}(\varphi)$ the
set $\\{A:A\models\varphi\\}$ of instances $A$ that satisfy $\varphi$ under
the active domain semantics (i.e., the quantifiers range over elements of the
active domain of the instance at hand). A _Boolean conjunctive query_ (Boolean
CQ) is a FO-sentence of the form $\exists x_{1}\ldots
x_{n}(\alpha_{1}\land\cdots\land\alpha_{k})$, where each $\alpha_{j}$ is an
atomic formula of the form $R(y_{1},\ldots,y_{r})$, each variable $y_{i}$ is
among the variables $x_{1},\ldots,x_{n}$, and each variable $x_{i}$ occurs in
at least one of the atomic formulas $\alpha_{1},\ldots,\alpha_{k}$.

The _canonical instance_ of a conjunctive query $q$, denoted $A^{q}$, is the
instance whose active domain consists of the variables of $q$, and whose facts
are the conjuncts of $q$. Conversely, the _canonical conjunctive query_ of an
instance $A$, denoted $q^{A}$, has, for each $a$ in $\mathrm{adom}(A)$, an
existentially quantified variable $x_{a}$ and, for each fact
$(a_{1},\ldots,a_{r})\in R^{A}$, a conjunct $R(x_{a_{1}},\ldots,x_{a_{r}})$.
An immediate consequence of the semantics of FO is that, for every two
instances $A$ and $D$, we have that $D\models q^{A}$ if and only if
$A\rightarrow D$.

A conjunctive query is _Berge-acyclic_ if its canonical instance is acyclic,
as defined earlier. The notion of Berge-acyclicity is stronger than the more
standard notion of acyclicity in databse theory, which requires that the
conjunctive query has a join tree (see, e.g., [1]).

Homomorphism counts, left and right profiles Let ${\rm
Nature}=(N,+,\times,0,1)$ be the semiring of the non-negative integers and let
$\mathbb{B}=(\\{0,1\\},\lor,\land,0,1)$ be the Boolean semiring. If $A$ and
$B$ are two instances, then we write $\hom_{\rm Nature}(A,B)$ for the number
of homomorphisms from $A$ to $B$. For example, if $A$ is a graph and $K_{3}$
is the $3$-clique, then $\hom_{\rm Nature}(A,K_{3})$ is the number of
$3$-colorings of $A$. We extend this notion to $\hom_{\mathbb{B}}(A,B)$, where
$\hom_{\mathbb{B}}(A,B)=1$ if there is a homomorphism from $A$ to $B$, and
$\hom_{\mathbb{B}}(A,B)=0$ otherwise. For example,
$\hom_{\mathbb{B}}(A,K_{3})=1$ if $A$ is $3$-colorable, and
$\hom_{\mathbb{B}}(A,K_{3})=0$ if $A$ is not $3$-colorable.

Let $\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ be a finite non-empty set of
instances and let $A$ be an instance.

  * •

The _left profile of $A$ in $\mathcal{F}$ over ${\rm Nature}$_ is the tuple

$\hom_{\rm Nature}(\mathcal{F},A)=(\hom_{\rm Nature}(F_{1},A),\ldots,\hom_{\rm
Nature}(F_{k},A)).$

  * •

The _left profile of $A$ in $\mathcal{F}$ over $\mathbb{B}$_ is the tuple

$\hom_{\mathbb{B}}(\mathcal{F},A)=(\hom_{\mathbb{B}}(F_{1},A),\ldots,\hom_{\mathbb{B}}(F_{k},A))$.

  * •

The _right profile of $A$ in $\mathcal{F}$ over ${\rm Nature}$_ is the tuple

$\hom_{\rm Nature}(A,\mathcal{F})=(\hom_{\rm Nature}(A,F_{1}),\ldots,\hom_{\rm
Nature}(A,F_{k}))$.

  * •

The _right profile of $A$ in $\mathcal{F}$ over $\mathbb{B}$_ is the tuple

$\hom_{\mathbb{B}}(A,\mathcal{F})=(\hom_{\mathbb{B}}(A,F_{1}),\ldots,\hom_{\mathbb{B}}(A,F_{k}))$.

Let $A_{1},\ldots,A_{n}$ be instances whose active domains are pairwise
disjoint.

  * •

The _direct sum_ $A_{1}\mathbin{\oplus}\cdots\mathbin{\oplus}A_{n}$ of
$A_{1},\ldots,A_{n}$ is the instance such that
$R^{A_{1}\mathbin{\oplus}\cdots\mathbin{\oplus}A_{n}}=R^{A_{1}}\mathbin{\cup}\cdots\mathbin{\cup}R^{A_{n}}$,
for every $R\in\sigma$.

  * •

The _direct product_ $A_{1}\mathbin{\otimes}\cdots\mathbin{\otimes}A_{n}$ of
$A_{1},\ldots,A_{n}$ is the instance such that the relation
$R^{A_{1}\mathbin{\otimes}\cdots\mathbin{\otimes}A_{n}}$ consists of all
tuples $(\mathbf{a}_{1},\ldots,\mathbf{a}_{r})$ with
$(\mathbf{a}_{1}(i),\ldots,\mathbf{a}_{r}(i))\in R^{A_{i}}$, for $1\leq i\leq
n$ and for every $R\in\sigma$ of arity $r$.

The next proposition is well known and has a straightforward proof.

######  Proposition 2.1.

Let $A,B_{1},B_{2}$ be instances, and let $K\in\\{\mathbb{B},{\rm Nature}\\}$.
Then the following statements are true.

  1. 1.

$\hom_{K}(A,B_{1}\oplus B_{2})=\hom_{K}(A,B_{1})+_{K}\hom_{K}(A,B_{2})$,
provided that $A$ is connected;

  2. 2.

$\hom_{K}(A,B_{1}\otimes B_{2})=\hom_{K}(A,B_{1})\cdot_{K}\hom_{K}(A,B_{2})$;

  3. 3.

$\hom_{K}(B_{1}\oplus B_{2},A)=\hom_{K}(B_{1},A)\cdot_{K}\hom_{K}(B_{2},A)$,

where $+_{\rm Nature}$ and $\cdot_{\rm Nature}$ stand for addition $+$ and
multiplication $\times$ of non-negative integers, while $+_{\mathbb{B}}$ and
$\cdot_{\mathbb{B}}$ stand for disjunction $\lor$ and conjunction $\land$ of
the Boolean values $0$ and $1$.

##  3 Left Query Algorithms and Right Query Algorithms

In [9], Chen et al. focused on classes of graphs and introduced the notions of
a left query algorithm and a right query algorithm over the semiring ${\rm
Nature}$ of the non-negative integers. Here, we extend their framework in two
ways: first, we consider classes of instances over some arbitrary, but fixed,
schema; second, we consider left query algorithms and right query algorithms
over the Boolean semiring $\mathbb{B}$.

######  Definition 3.1.

Let $\mathcal{C}$ be a class of instances and let $K$ be the semiring
$\mathbb{B}$ or ${\rm Nature}$.

  * •

Assume that $k$ is a positive integer.

    * –

A _left $k$-query algorithm over $K$ for $\mathcal{C}$_ is a pair
$(\mathcal{F},X)$, where $\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ is a set of
instances and $X$ is a set of $k$-tuples over $K$, such that for all instances
$D$, we have that $D\in\mathcal{C}$ if and only if $\hom_{K}(\mathcal{F},D)\in
X$.

    * –

A _right $k$-query algorithm over $K$ for $\mathcal{C}$_ is a pair
$(\mathcal{F},X)$, where $\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ is a set of
instances and $X$ is a set of $k$-tuples over $K$, such that for all instances
$D$, we have that $D\in\mathcal{C}$ if and only if $\hom_{K}(D,\mathcal{F})\in
X$.

  * •

We say that $\mathcal{C}$ _admits a left query algorithm over_ $K$ if for some
$k>0$, there is a left $k$-query algorithm over $K$ for $\mathcal{C}$.
Similarly, we say that $\mathcal{C}$ _admits a right query algorithm over_ $K$
if for some $k>0$, there is a right $k$-query algorithm over $K$ for
$\mathcal{C}$.

The term “query algorithm” is natural because we can think of a query
algorithm as a procedure for determining if a given instance belongs to the
class $\mathcal{C}$: we compute the left homomorphism-count vector (in the
case of a left query algorithm) or the right homomorphism-count vector (in the
case of a right query algorithm) and test whether it belongs to $X$. When the
semiring ${\rm Nature}$ is considered, this is a somewhat abstract notion of
an algorithm because it makes no requirements on the effectiveness of the set
$X$. Not requiring $X$ to be a decidable set makes our results regarding the
non-existence of left query algorithms over ${\rm Nature}$ stronger. Moreover,
in all cases where we establish the existence of a left query algorithm over
${\rm Nature}$ or a right query algorithm over ${\rm Nature}$, the set $X$
will happen to be decidable (for the semiring $\mathbb{B}$, the set $X$ is
always finite, hence decidable).

Let $K$ be the semiring $\mathbb{B}$ or ${\rm Nature}$. It is clear that if
two classes of instances admit a left query algorithm over $K$, then so do
their complements, their union, and their intersection. Consequently, the
classes of instances that admit a left query algorithm over $K$ are closed
under Boolean combinations. Furthermore, the same holds true for right query
algorithms.

By Part 3 of Proposition 2.1, we have that if $K$ is the semiring $\mathbb{B}$
or the semiring ${\rm Nature}$, then $\hom_{K}$ is _multiplicative on the
left_ , i.e., for all instances $A_{1},\ldots,A_{n}$ and $B$, we have
$\hom_{K}(A_{1}\mathbin{\oplus}\cdots\mathbin{\oplus}A_{n},B)=\hom_{K}(A_{1},B)\cdot_{K}\
\cdots\cdot_{K}\ \hom_{K}(A_{n},B)$. It follows that, as regards the existence
of left query algorithms, we may assume that all instances in the finite set
$\mathcal{F}$ of a left query algorithm over $\mathbb{B}$ or over ${\rm
Nature}$ are connected. We state this observation as a proposition that will
be used repeatedly in the sequel.

######  Proposition 3.2.

Let $\mathcal{C}$ be a class of instances and let $K$ be the semiring
$\mathbb{B}$ or ${\rm Nature}$. Then the following statements are equivalent.

  1. 1.

$\mathcal{C}$ admits a left query algorithm $(\mathcal{F},X)$ over $K$.

  2. 2.

$\mathcal{C}$ admits a left query algorithm $(\mathcal{F},X)$ over $K$, where
every instance in the set $\mathcal{F}$ is connected.

Left profiles over ${\rm Nature}$ contain more information than left profiles
over $\mathbb{B}$. Therefore, if membership in a class $\mathcal{C}$ can be
determined using left profiles over $\mathbb{B}$, then it ought to be also
determined using left profiles over ${\rm Nature}$. Similar considerations
hold for right profiles. The next proposition makes these assertions precise.

######  Proposition 3.3.

Let $\mathcal{C}$ be a class of instances and let $\mathcal{F}$ be a finite
set of instances.

If $\mathcal{C}$ admits a left query algorithm over $\mathbb{B}$ of the form
$(\mathcal{F},X)$ for some set $X$, then $\mathcal{C}$ admits a left query
algorithm over ${\rm Nature}$ of the form $(\mathcal{F},X^{\prime})$ for some
set $X^{\prime}$. In particular, if $\mathcal{C}$ admits a left query
algorithm over $\mathbb{B}$, then it also admits a left query algorithm over
${\rm Nature}$.

Furthermore, the same holds true for right query algorithms.

######  Proof 3.4.

Assume that $\mathcal{C}$ admits a left query algorithm $(\mathcal{F},X)$ over
$\mathbb{B}$, where $\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ and
$X\subseteq\\{0,1\\}^{k}$, for some $k>0$. For every
$t=(t_{1},\ldots,t_{k})\in\\{0,1\\}^{k}$, we let $X_{t}$ be the set

$X_{t}=\\{(s_{1},\cdots,s_{k})\in{\rm Nature}^{k}:s_{i}=0\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{if and only if}\leavevmode\nobreak\
\leavevmode\nobreak\ t_{i}=0,\leavevmode\nobreak\
\mbox{for}\leavevmode\nobreak\ 1\leq i\leq k\\}$.

Consider the set $X^{\prime}=\mathop{\bigcup}_{t\in X}X_{t}$. It is easy to
verify that the pair $(\mathcal{F},X^{\prime})$ is a left $k$-query algorithm
for $\mathcal{C}$ over ${\rm Nature}$. The argument for right query algorithms
is entirely analogous.

As pointed out in the Introduction, the converse of Proposition 3.3 is not
true, in general.

We now give several examples illustrating left and right query algorithms.

######  Example 3.5.

Let $\mathcal{C}$ be the class of all triangle-free graphs, i.e., the graphs
$G$ for which there is no homomorphism from $K_{3}$ to $G$. Clearly,
$\mathcal{C}$ admits a left $1$-query algorithm $(\mathcal{F},X)$ over
$\mathbb{B}$, where $\mathcal{F}=\\{K_{3}\\}$ and $X=\\{0\\}$ (recall that
$K_{3}$ is the $3$-clique). 111This example, and several other examples in
this paper, involve graphs. Here, the word “graph” may be read as “structure
over a schema with one binary relation”. Alternatively, it may be read as
“structure over a schema with one binary relation that is symmetric and
irreflexive”, but, in the latter case, we only require the query algorithm to
behave correctly on such graphs, and we do not require the query algorithm to
distinguish such graphs from structures whose relation is not symmetric and
irreflexive.  Therefore, by Proposition 3.3, $\cal C$ admits a left $1$-query
algorithm over ${\rm Nature}$. In contrast, Chen et al. [9, Proposition 8.2]
showed that (the complement of) $\mathcal{C}$ does not admit a right query
algorithm over ${\rm Nature}$, hence (again by Proposition 3.3) it does not
admit a right query algorithm over $\mathbb{B}$.

We now recall the definition of constraint satisfaction problems.

######  Definition 3.6.

If $B$ is an instance, then the _constraint satisfaction problem_
$\mathrm{CSP}(B)$ is the following decision problem: given an instance $A$, is
there a homomorphism from $A$ to $B$?

For $k\geq 2$, let $K_{k}$ denote the $k$-clique. Then $\mathrm{CSP}(K_{k})$
is the $k$-colorability problem: given a graph $G$, is $G$ $k$-colorable?
During the past three decades, there has been an extensive study of complexity
of constraint satisfaction problems, motivated by the Feder-Vardi Conjecture
that for every instance $B$, either $\mathrm{CSP}(B)$ is NP-complete or
$\mathrm{CSP}(B)$ is solvable in polynomial time. This conjecture was
eventually confirmed independently by Bulatov [7] and Zhuk [29].

Every constraint satisfaction problem will be identified with the class of its
“yes” instances, that is, for every instance $B$, we have that
$\mathrm{CSP}(B)=\\{A:A\rightarrow B\\}$.

######  Example 3.7.

Let $B$ be an instance. Clearly, $\mathrm{CSP}(B)$ admits a right $1$-query
algorithm $(\mathcal{F},X)$ over $\mathbb{B}$, where $\mathcal{F}=\\{B\\}$ and
$X=\\{1\\}$. Therefore, by Proposition 3.3, $\mathrm{CSP}(B)$ admits a right
$1$-query algorithm $(\mathcal{F},X^{\prime})$ over ${\rm Nature}$. In
particular, the 3-colorability problem $\mathrm{CSP}(K_{3})$ admits a right
query algorithm over both $\mathbb{B}$ and ${\rm Nature}$. In contrast, it
will follow from results in Section 4 and Section 5 that $\mathrm{CSP}(K_{3})$
does not admit a left query algorithm over $\mathbb{B}$ or over ${\rm Nature}$
(see Remark 4.8).

######  Example 3.8.

Consider the homomorphic equivalence class
$\left[K_{3}\right]_{\mathrel{\leftrightarrow}}$. Note that
$\left[K_{3}\right]_{\mathrel{\leftrightarrow}}$ is the class of all graphs
that are $3$-colorable and also contain a triangle. From results in Section 4,
it will follow that $\left[K_{3}\right]_{\mathrel{\leftrightarrow}}$ does not
admit a left query algorithm over $\mathbb{B}$ (see Remark 4.8). Furthermore,
from results in Section 6, it will follow that
$\left[K_{3}\right]_{\mathrel{\leftrightarrow}}$ does not admit a right query
algorithm over $\mathbb{B}$ (see Remark 6.10).

##  4 Left Query Algorithms over $\mathbb{B}$

In this section, we investigate which classes admit a left query algorithm
over $\mathbb{B}$. It is easy to see that every class of instances that admits
a left query algorithm over $\mathbb{B}$ is closed under homomorphic
equivalence. In other words, closure under homomorphic equivalence is a
necessary condition for the existence of a left query algorithm over
$\mathbb{B}$. The next result gives an exact characterization of the classes
of instances that admit a left query algorithm over $\mathbb{B}$.

######  Theorem 4.1.

Let $\mathcal{C}$ be a class of instances. Then the following statements are
equivalent.

  1. 1.

$\mathcal{C}$ admits a left query algorithm over $\mathbb{B}$.

  2. 2.

$\mathcal{C}$ is definable by a Boolean combination of CQs.

  3. 3.

$\mathcal{C}$ is FO-definable and closed under homomorphic equivalence.

######  Proof 4.2.

We will first show the equivalence between statements (1) and (2), and then
the equivalence between statements (2) and (3).

$(1)\Longrightarrow(2)$: Let a left query algorithm over $\mathbb{B}$ for
$\mathcal{C}$ consist of $\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ and
$X\subseteq\\{0,1\\}^{k}$, and let
$\mathit{q}^{F_{1}},\ldots,\mathit{q}^{F_{k}}$ be the canonical conjunctive
queries of $F_{1},\ldots,F_{k}$, respectively. For every tuple
$t=(t_{1},\ldots,t_{k})\in X$, define

$\varphi_{t}\colonequals\bigwedge_{t_{i}=1}\mathit{q}^{F_{i}}\land\bigwedge_{t_{i}=0}\neg\mathit{q}^{F_{i}}.$

Take $\varphi\colonequals\bigvee_{t\in X}\varphi_{t}$. Then
$\mathcal{C}=\mathrm{Mod}(\varphi)$.

$(2)\Longrightarrow(1)$: Every class $\mathcal{C}$ defined by a conjunctive
query $q$ admits a left $1$-query algorithm over $\mathbb{B}$. Indeed, we can
pick $\mathcal{F}$ to consist of the canonical instance $A^{q}$ of $q$, and
$X=\\{1\\}$. It follows by closure under Boolean combinations that every class
defined by a Boolean combination of conjunctive queries also admits a left
query algorithm over $\mathbb{B}$.

$(2)\Longrightarrow(3)$: This implication is immediate because CQs are first-
order formulas whose truth is preserved by homomorphisms.

$(3)\Longrightarrow(2)$: We will use two results from [27] about the
homomorphism preservation theorem in the finite. For instances $A$ and $B$, we
write $A\leftrightarrow^{n}B$ to mean that $A$ and $B$ satisfy the same
existential positive FO-sentences of quantifier rank at most $n$, and write
$A\equiv^{n}B$ to mean that $A$ and $B$ satisfy the same FO-sentences of
quantifier rank at most $n$. The two results from [27] in our concerns are

  1. (a)

Theorem 1.9: For every $n$, there is some $m$ that depends on $n$ such that
for every instances $A$ and $B$ with $A\leftrightarrow^{m}B$, there are
instances $A^{\prime}$ and $B^{\prime}$ such that
$A\mathrel{\leftrightarrow}A^{\prime}$,
$B\mathrel{\leftrightarrow}B^{\prime}$, and $A^{\prime}\equiv^{n}B^{\prime}$.

  2. (b)

Lemma 3.9: For every $m$, the equivalence relation $A\leftrightarrow^{m}B$ has
finitely many equivalence classes over the class of all instances.

Now, let $\mathcal{C}$ be a class definable by a FO-sentence $\varphi$ and
closed under homomorphic equivalence $\mathrel{\leftrightarrow}$. Let $n$ be
the quantifier rank of $\varphi$, and let $m$ be the integer in the statement
of (a). Note that $m$ depends on $n$ only.

We claim that $\mathrm{Mod}(\varphi)=\mathcal{C}$ is closed under
$\leftrightarrow^{m}$. Indeed, assume that $A$ and $B$ are two instances such
that $A\models\varphi$ and $A\leftrightarrow^{m}B$. By (a), there are
instances $A^{\prime}$ and $B^{\prime}$ such that
$A\mathrel{\leftrightarrow}A^{\prime}$,
$B\mathrel{\leftrightarrow}B^{\prime}$, and $A^{\prime}\equiv^{n}B^{\prime}$.
It follows, successively, that

$A^{\prime}\models\varphi$ (since $A\models\varphi$,
$A\mathrel{\leftrightarrow}A^{\prime}$, and $\mathcal{C}$ is closed under
$\mathrel{\leftrightarrow}$), $B^{\prime}\models\varphi$ (since $\varphi$ has
quantifier rank $n$ and $A^{\prime}\equiv^{n}B^{\prime}$), $B\models\varphi$
(since $B\mathrel{\leftrightarrow}B^{\prime}$ and $\mathcal{C}$ is closed
under $\mathrel{\leftrightarrow}$).

By (b), the equivalence relation $\leftrightarrow^{m}$ has finitely many
equivalence classes. Let $A_{1},\ldots,A_{k}$ be representatives from each of
these equivalence classes (one per equivalence class). For different $i,j$ in
$\\{1,\ldots,k\\}$, let $\psi_{i,j}$ be an existential positive FO-sentence of
quantifier rank at most $m$ such that $A_{i}\models\psi_{i,j}$ but not
$A_{j}\models\psi_{i,j}$, and let $\psi(A_{i})$ be the conjunction of all
$\psi_{i,j}$. Each $\psi(A_{i})$ is a Boolean combination of conjunctive
queries and it holds for every instance $B$ that $B\leftrightarrow^{m}A_{i}$
if and only if $B\models\psi(A_{i})$. Then $\varphi$ is equivalent to the
disjunction $\bigvee_{A_{i}\models\varphi}\psi(A_{i})$ since
$\mathrm{Mod}(\varphi)$ is closed under $\leftrightarrow^{m}$. Indeed, if
$B\models\varphi$, then $B\leftrightarrow^{m}A_{i}$ for some $A_{i}$ that
satisfies $\varphi$, hence $B\models\psi(A_{i})$. Conversely, if
$B\models\bigvee_{A_{i}\models\varphi}\psi(A_{i})$, then $B\models\psi(A_{i})$
for some $A_{i}$ that satisfies $\varphi$; it follows that
$B\leftrightarrow^{m}A_{i}$, hence $B\models\varphi$.

######  Corollary 4.3.

A class $\mathcal{C}$ of instances that is closed under homomorphic
equivalence admits a left query algorithm over $\mathbb{B}$ if and only if
$\mathcal{C}$ is FO-definable.

Corollary 4.3, in particular, applies to classes of the form
$\mathrm{CSP}(A)$, since such classes are closed under homomorphic
equivalence. It was shown in [28] that testing, for a given instance $A$,
whether $\mathrm{CSP}(A)$ is FO-definable, is NP-complete (and in fact, in
polynomial time when $A$ is a _core_ , i.e. when there is no homomorphism from
$A$ to a proper subinstance of $A$). It follows that testing if a given
$\mathrm{CSP}(A)$ admits a left query algorithm over $\mathbb{B}$ is NP-
complete. This extends to finite unions of CSPs:

######  Proposition 4.4.

The following problem is NP-complete: given instances $A_{1},\ldots,A_{n}$,
does $\bigcup_{1\leq i\leq n}\mathrm{CSP}(A_{i})$ admit a left query algorithm
over $\mathbb{B}$?

######  Proof 4.5.

Without loss of generality, assume that the instances $A_{1},\ldots,A_{n}$ are
pairwise homomorphically incomparable (because, if $A_{j}\to A_{k}$, then
$A_{j}$ can be removed without affecting the class defined by $\bigcup_{1\leq
i\leq n}\mathrm{CSP}(A_{i})$). It is known that, in this case, $\bigcup_{1\leq
i\leq n}\mathrm{CSP}(A_{i})$ is FO-definable if and only if for each $1\leq
i\leq n$, $\mathrm{CSP}(A_{i})$ is FO-definable (this may be considered
folklore, see [5, Lemma 5.13] for an explicit proof). The result follows, by
Corollary 4.3.

Corollary 4.3 also applies to classes of the form
$\left[A\right]_{\mathrel{\leftrightarrow}}$, and we can derive a similar
complexity bound. This will be obtained using the following proposition.

######  Proposition 4.6.

Let $A$ be an instance and $\mathit{K}\in\\{\mathbb{B},{\rm Nature}\\}$. Then
the following statements are equivalent.

  1. 1.

$\left[A\right]_{\mathrel{\leftrightarrow}}$ has a left query algorithm over
$\mathit{K}$.

  2. 2.

$\mathrm{CSP}(A)$ has a left query algorithm over $\mathit{K}$.

######  Proof 4.7.

Let $\mathit{K}\in\\{\mathbb{B},{\rm Nature}\\}$ throughout the proof.

$(2)\Longrightarrow(1)$: Clearly,
$\left[A\right]_{\mathrel{\leftrightarrow}}=\mathrm{CSP}(A)\mathbin{\cap}\\{B:A\mathrel{\rightarrow}B\\}$.
Also, $\\{B:A\mathrel{\rightarrow}B\\}$ admits an obvious left query algorithm
over $\mathit{K}$. The result follows by closure under Boolean combinations.

$(1)\Longrightarrow(2)$: Assume $\mathrm{CSP}(A)$ has no left query algorithm
over $\mathit{K}$. Let $\mathcal{F}$ be an arbitrary finite set of connected
instances (think: candidate left query algorithm for
$\left[A\right]_{\mathrel{\leftrightarrow}}$). Since $\mathrm{CSP}(A)$ has no
left query algorithm over $\mathit{K}$, there are instances
$P\in\mathrm{CSP}(A)$ and $Q\notin\mathrm{CSP}(A)$ such that
$\hom_{\mathit{K}}(\mathcal{F},P)=\hom_{\mathit{K}}(\mathcal{F},Q)$. Let
$P^{\prime}=P\mathbin{\oplus}A$ and let $Q^{\prime}=Q\mathbin{\oplus}A$. Then,
by construction, $P^{\prime}\in\left[A\right]_{\mathrel{\leftrightarrow}}$ and
$Q^{\prime}\notin\left[A\right]_{\mathrel{\leftrightarrow}}$ but
$\hom_{\mathit{K}}(\mathcal{F},P^{\prime})=\hom_{\mathit{K}}(\mathcal{F},Q^{\prime})$
(cf. Proposition 2.1). Therefore, by Proposition 3.2,
$\left[A\right]_{\mathrel{\leftrightarrow}}$ has no left query algorithm over
$\mathit{K}$.

Consequently, the following problem is also NP-complete: _given an instance
$A$, does $\left[A\right]_{\mathrel{\leftrightarrow}}$ admit a left query
algorithm over $\mathbb{B}$?_

######  Remark 4.8.

In Example 3.7, we asserted that the class $\mathrm{CSP}(K_{3})$ of
3-colorable graphs admits no left query algorithm over $\mathbb{B}$.
Furthermore, in Example 3.8, we asserted that
$\left[K_{3}\right]_{\mathrel{\leftrightarrow}}$ (i.e., the class of graphs
that are 3-colorable and also contain a triangle) admits no left query
algorithm over $\mathbb{B}$. Corollary 4.3 and Proposition 4.6, now account
for the non-existence of a left query algorithm over $\mathbb{B}$ for these
classes: the reason is these two classes are not FO-definable. In the next
section (see Corollary 5.9), we will see that the same explanation accounts
for the fact that these classes admit no left query algorithm over ${\rm
Nature}$ either.

Proposition 4.6 extends to finite unions of homomorphic equivalence classes.

######  Theorem 4.9.

For all instances $A_{1},\ldots,A_{n}$, the following statements are
equivalent.

  1. 1.

$\mathop{\bigcup}_{1\leq i\leq
n}\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$ admits a left query
algorithm over $\mathbb{B}$ (equivalently, is FO-definable).

  2. 2.

Each $\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$, for $i=1,\ldots,n$,
admits a left query algorithm over $\mathbb{B}$ (equivalently, is FO-
definable).

######  Proof 4.10.

It is clear that the second statement implies the first. We will prove by
induction on $n$ that the first statement implies the second. The base case
($n=1$) is immediate since (i) and (ii) coincide. Next, let $n>1$ and
$\mathcal{C}\colonequals\mathop{\bigcup}_{1\leq i\leq
n}\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$. We proceed by
contraposition: suppose that $\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$
does not admit a left query algorithm over $\mathbb{B}$, for some $i\leq n$.
We may assume without loss of generality that $A_{1},\ldots,A_{n}$ are
pairwise not homomorphically equivalent. Note that $\mathrel{\rightarrow}$
induces a preorder among $A_{1},\ldots,A_{n}$ and, since $n$ is finite, there
is a maximal. Without loss of generality, assume that $A_{n}$ is a maximal,
that is, $A_{n}\not\mathrel{\rightarrow}A_{i}$ for all $i<n$. We distinguish
two cases.

(1) $\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$ admits a left query
algorithm over $\mathbb{B}$. Then, for some $i\leq n-1$,
$\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$ does not admit a left query
algorithm over $\mathbb{B}$. By induction hypothesis, we have
$\mathcal{C}^{\prime}\colonequals\mathop{\bigcup}_{1\leq i\leq
n-1}\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$ does not admit a left
query algorithm over $\mathbb{B}$. Then it follows that $\mathcal{C}$ does not
admit a left query algorithm over $\mathbb{B}$ either, for otherwise
$\mathcal{C}^{\prime}=\mathcal{C}\setminus\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$
would admit a left query algorithm over $\mathbb{B}$.

(2) $\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$ does not admit a left
query algorithm over $\mathbb{B}$. By Proposition 4.6, $\mathrm{CSP}(A_{n})$
does not admit a left query algorithm over $\mathbb{B}$ either. Let
$\mathcal{F}$ be an arbitrary finite non-empty set of connected instances.
Since $\mathrm{CSP}(A_{n})$ does not admit a left query algorithm over
$\mathbb{B}$, there are $P\in\mathrm{CSP}(A_{n})$ and
$Q\notin\mathrm{CSP}(A_{n})$ such that
$\hom_{\mathbb{B}}(\mathcal{F},P)=\hom_{\mathbb{B}}(\mathcal{F},Q)$. It
follows that

  * •

$(P\mathbin{\oplus}A_{n})\in\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$,
because both $P,A_{n}\in\mathrm{CSP}(A_{n})$,

  * •

$(Q\mathbin{\oplus}A_{n})\notin\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$,
because $Q\notin\mathrm{CSP}(A_{n})$,

  * •

for all $i<n$,
$(Q\mathbin{\oplus}A_{n})\notin\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$,
because $A_{n}\not\mathrel{\rightarrow}A_{i}$, and

  * •

$\hom_{\mathbb{B}}(\mathcal{F},P\mathbin{\oplus}A_{n})=\hom_{\mathbb{B}}(\mathcal{F},Q\mathbin{\oplus}A_{n})$,
because the instances in $\mathcal{F}$ are all connected.

The first three points above give $(P\mathbin{\oplus}A_{n})\in\mathcal{C}$ and
$(Q\mathbin{\oplus}A_{n})\notin\mathcal{C}$. Therefore, by Proposition 3.2,
$\mathcal{C}$ has no left query algorithm over $\mathbb{B}$.

Note that Theorem 4.9 only applies to finite unions of homomorphic-equivalence
classes. It may fail for infinite unions. Specifically, the class of all
instances trivially admits a left query algorithm over $\mathbb{B}$, and it is
the union of all equivalence classes
$\left[A\right]_{\mathrel{\leftrightarrow}}$, as $A$ varies over all
instances; however, as seen earlier,
$\left[K_{3}\right]_{\mathrel{\leftrightarrow}}$ does not admit any left query
algorithm over $\mathbb{B}$.

######  Corollary 4.11.

The following problem is NP-complete: given instance $A_{1},\ldots,A_{n}$,
does $\bigcup_{1\leq i\leq n}\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$
admit a left query algorithm over $\mathbb{B}$?

Each class $\mathcal{C}$ that is closed under homomorphic equivalence can
trivially be represented as a possibly-infinite union of classes of the form
$\left[A\right]_{\mathrel{\leftrightarrow}}$. The algorithmic problem of
testing for the existence of a left query algorithm, of course, makes sense
only for finitely presented inputs. This motivates the above corollary.

As a last case study, consider Boolean Datalog programs, i.e., Datalog
programs with a zero-ary goal predicate. We omit a detailed definition of the
syntax and semantics of Datalog, which can be found, e.g., in [1]. Each
Datalog program $P$ naturally defines a class of instances $\mathcal{C}_{P}$.
It is well known that _the class $\mathcal{C}_{P}$ is closed under homomorphic
equivalence_. Furthermore, $\mathcal{C}_{P}$ is FO-definable if and only if
$P$ is “bounded” (meaning that there is a fixed number $n$, depending only on
$P$ and not on the input instance, such that $P$ reaches its fixed point after
at most $n$ iterations), as was first shown by [2] and also follows from [27].
The boundedness problem for Boolean Datalog programs is undecidable [14].
Therefore, we have the following result.

######  Corollary 4.12.

The following problem is undecidable: given a Boolean Datalog program $P$,
does $\mathcal{C}_{P}$ admit a left query algorithm over $\mathbb{B}$.

##  5 Existence vs. Counting: When Does Counting Not Help?

Left query algorithms over ${\rm Nature}$ are more powerful than left query
algorithms over $\mathbb{B}$. This is trivially so because query algorithms
over $\mathbb{B}$ cannot distinguish homomorphically equivalent instances.

######  Example 5.1.

Let $\mathcal{C}$ be the isomorphism class of the instance $A$ consisting of
the fact $R(a,a)$ (in other words, the single-node reflexive digraph). Since
$\mathcal{C}$ is not closed under homomorphism equivalence, it does not admit
a left query algorithm (nor a right query algorithm) over $\mathbb{B}$. On the
other hand, it admits a left query algorithm over ${\rm Nature}$: by counting
the number of homomorphisms from $A$ to a given input instance $B$, we can
verify that $B$ contains a reflexive node; and by counting the number of
homomorphisms from the instance $A^{\prime}$ consisting of a single edge
$R(a,b)$, we can verify that the total number of edges in the graph is equal
to 1. More precisely, let $\mathcal{F}=\\{A,A^{\prime}\\}$ and let
$X=\\{(1,1)\\}$. Then $(\mathcal{F},X)$ is a left query algorithm over ${\rm
Nature}$ for $\mathcal{C}$.

As it turns out, in a precise sense, this is the only reason why left query
algorithms over ${\rm Nature}$ are more powerful than left query algorithms
over $\mathbb{B}$: the ability to count does not give more power when it comes
to classes that are closed under homomorphic equivalence. This follows from
the next theorem.

######  Theorem 5.2.

Let $\mathcal{C}$ be a class of instances closed under homomorphic
equivalence. For every finite set $\mathcal{F}$ of connected instances, the
following statements are equivalent.

  1. 1.

$\mathcal{C}$ admits a left query algorithm over ${\rm Nature}$ of the form
$(\mathcal{F},X)$ for some set $X$.

  2. 2.

$\mathcal{C}$ admits a left query algorithm over $\mathbb{B}$ of the form
$(\mathcal{F},X^{\prime})$ for some set $X^{\prime}$.

######  Proof 5.3.

The case $\mathcal{C}=\emptyset$ is trivial, so we will assume that
$\mathcal{C}$ is non-empty. The implication $(2)\Longrightarrow(1)$ is given
by Proposition 3.3. Let us prove the implication $(1)\Longrightarrow(2)$.

Let $(\mathcal{F},X)$ be a left query algorithm over ${\rm Nature}$ for
$\mathcal{C}$ where $\mathcal{F}=\\{F_{1},\dots,F_{k}\\}$ of pairwise non-
isomorphic instances and $X\subseteq{\rm Nature}^{k}$. It is enough to focus
on simple sets $X$, where a set $X$ is simple if for every $1\leq i\leq k$ and
every $\mathbf{t},\mathbf{t}^{\prime}\in X$, $\mathbf{t}(i)=0$ iff
$\mathbf{t}^{\prime}(i)=0$. Indeed, assume that $(1)\Rightarrow(2)$ holds
whenever $X$ is simple. Then, if $X$ is not simple, partition $X$ into maximal
simple subsets $X_{1},\dots,X_{r}$ and, for every $1\leq i\leq r$, let
$\mathcal{C}_{i}$ be the class of instances that admits the left query
algorithm $(\mathcal{F},X_{i})$. It is easy to verify that $\mathcal{C}_{i}$
is closed under homomorphic equivalence and, hence, by assumption, admits a
left query algorithm over $\mathbb{B}$ of the form
$(\mathcal{F},X_{i}^{\prime})$ for some set $X_{i}^{\prime}$. Then
$(\mathcal{F},\mathop{\bigcup}_{1\leq i\leq r}X_{i}^{\prime})$ is a left query
algorithm over $\mathbb{B}$ for $\mathcal{C}$.

Let us assume that $X$ is simple and non-empty (otherwise
$\mathcal{C}=\emptyset$, contradicting our assumption) and let $\mathbf{t}\in
X$. We can assume, by reordering the instances in $\mathcal{F}$ if necessary,
that there exists $s\geq 0$, such that $\mathbf{t}(i)>0$ for every $i\leq s$
and $\mathbf{t}(i)=0$ for every $i>s$.

Consider the FO-sentence defined as:

$\varphi=\bigwedge_{i\leq s}q^{F_{i}}\land\bigwedge_{i>s}\neg q^{F_{i}}$

We shall prove that $\mathrm{Mod}(\varphi)=\mathcal{C}$, and therefore
$\mathcal{C}$ admits a left query algorithm over $\mathbb{B}$ (namely, the
left query algorithm $(\mathcal{F},\\{\mathbf{t}^{\prime}\\})$ where
$\mathbf{t}^{\prime}(i)=1$ for $i\leq s$ and $\mathbf{t}^{\prime}(i)=0$ for
$i>s$). Since $\mathrm{Mod}(\varphi)=\mathcal{C}$ already holds when $s=0$, we
assume $s>0$ in the sequel.

To this end we shall need the following two technical lemmas.

######  Lemma 5.4.

Let $\mathbf{t}_{1},\dots,\mathbf{t}_{r}\in{\rm Nature}^{s}$ satisfying the
following conditions:

  1. 1.

For every $1\leq i\leq s$, there exists $1\leq j\leq r$ such that
$\mathbf{t}_{j}(i)\neq 0$.

  2. 2.

For every different $i,i^{\prime}\in\\{1,\dots,s\\}$, there exists $1\leq
j\leq r$ such that $\mathbf{t}_{j}(i)\neq\mathbf{t}_{j}(i^{\prime})$.

Then there exists some integer $c>0$ such that for every
$\mathbf{b}\in\mathbb{Z}^{s}$ whose entries are integers divisible by $c$,
there is a multivariate polynomial with integer coefficients
$p(x_{1},\dots,x_{r})$ of degree $s$ satisfying $p(0,\dots,0)=0$ (that is,
such that the independent term is zero) and such that, for each $1\leq i\leq
s$, $p(\mathbf{t}_{1}(i),\dots,\mathbf{t}_{r}(i))=\mathbf{b}(i)$.

######  Proof 5.5.

Most likely this follows from known results but, in any case, we provide a
self-contained proof. Let $\mathcal{G}$ be the set of all linear combinations
$a_{1}\mathbf{t}_{1}+\cdots a_{r}\mathbf{t}_{r}$ where each $a_{i}$ is a non-
negative integer. It follows from condition (1) that $\mathcal{G}$ contains a
tuple where all entries are positive. Moreover it follows from (2) that
$\mathcal{G}$ contains a tuple where all entries are different and positive.
Indeed, if $\mathbf{t},\mathbf{u}\in\mathcal{G}$ and
$\mathbf{v}=d\mathbf{t}+\mathbf{u}$ for $d\in{\rm Nature}$ large enough, then
for every different $i,i^{\prime}\in\\{1,\dots,s\\}$, we have

($\mathbf{t}(i)\neq\mathbf{t}(i^{\prime})$ or
$\mathbf{u}(i)\neq\mathbf{u}(i^{\prime})$) implies
$\mathbf{v}(i)\neq\mathbf{v}(i^{\prime})$.

Now, let $\mathbf{u}=a_{1}\mathbf{t}_{1}+\cdots+a_{r}\mathbf{t}_{r}$ be any
tuple where all entries are different and positive. It is easy to see that the
$(s\times s)$-matrix $M$ whose rows are
$\mathbf{u}^{1},\mathbf{u}^{2},\dots,\mathbf{u}^{s}$ is non-singular. Indeed,
if $\mathbf{u}=(u_{1},\dots,u_{s})$, then $\text{det}(M)=u_{1}\cdots
u_{s}\cdot\text{det}(N)$, where $N$ is the $(s\times s)$-matrix with rows
$\mathbf{u}^{0},\mathbf{u}^{1},\dots,\mathbf{u}^{s-1}$ which is Vandermonde.
It is well known that Vandermonde matrices are non-singular whenever
$\mathbf{u}$ has no repeated elements (see [18] for example).

To finish the proof we choose $c$ to be $|\text{det}(M)|$. By assumption all
entries of $\mathbf{b}$ are divisible by $c$ which implies that all entries of
$M^{-1}\textbf{b}$ are integers, that is, $\mathbf{b}$ can be expressed as
$e_{1}\mathbf{u}^{1}+\cdots+e_{s}\mathbf{u}^{s}$ for some
$e_{1},\dots,e_{s}\in\mathbb{Z}$. Hence, the polynomial
$p(x_{1},\dots,x_{r})=e_{1}y^{1}+\cdots+e_{s}y^{s}$ where
$y=a_{1}x_{1}+\cdots+a_{r}x_{r}$ satisfies the claim.

######  Lemma 5.6.

Let $F,F^{\prime}$ be instances such that there is no surjective homomorphism
from $F$ onto $F^{\prime}$. Then there exists some subinstance $H$ of
$F^{\prime}$ such that $\hom_{{\rm Nature}}(F,H)\neq\hom_{{\rm
Nature}}(F^{\prime},H)$.

######  Proof 5.7.

This is a natural adaptation of the Lovász’s proof that two instances are
isomorphic if and only if they have the same left homomorphism-count vector.

For every instance $G$, we write $\mathrm{sur}_{\rm Nature}(G,F^{\prime})$ for
the number of surjective homomorphisms from $G$ onto $F^{\prime}$; moreover,
for every subset $S\subseteq\mathrm{adom}(F^{\prime})$, we write $\hom_{\rm
Nature}^{S}(G,F^{\prime})$ for the number of homomorphisms
$h:G\mathrel{\rightarrow}F^{\prime}$ whose range is contained in $S$. Let
$n\colonequals\left|\mathrm{adom}(F^{\prime})\right|$. By the Inclusion-
Exclusion Principle, then

$\mathrm{sur}_{\rm
Nature}(G,F^{\prime})=\sum_{S\subseteq\mathrm{adom}(F^{\prime})}(-1)^{n-\left|S\right|}\hom_{\rm
Nature}^{S}(G,F^{\prime}).$

Since $\mathrm{sur}_{\rm Nature}(F,F^{\prime})=0$ and $\mathrm{sur}_{\rm
Nature}(F^{\prime},F^{\prime})>0$, we have $\mathrm{sur}_{\rm
Nature}(F,F^{\prime})\neq\mathrm{sur}_{\rm Nature}(F^{\prime},F^{\prime})$ and
it follows by the above discussion that there is a subset
$S\subseteq\mathrm{adom}(F^{\prime})$ such that $\hom_{\rm
Nature}^{S}(F,F^{\prime})\neq\hom_{\rm Nature}^{S}(F^{\prime},F^{\prime})$.
Let $H$ be the maximum subinstance of $F^{\prime}$ with
$\mathrm{adom}(H)\subseteq S$, then we have $\hom_{\rm Nature}(F,H)=\hom_{\rm
Nature}^{S}(F,F^{\prime})\neq\hom_{\rm
Nature}^{S}(F^{\prime},F^{\prime})=\hom_{\rm Nature}(F^{\prime},H)$.

Let us now continue with the proof that $\mathrm{Mod}(\varphi)=\mathcal{C}$.
The direction $\supseteq$ is immediate. For the converse, we must prove that
every $B\in\mathrm{Mod}(\varphi)$ belongs also to $\mathcal{C}$. Let
$B\in\mathrm{Mod}(\varphi)$, and choose an arbitrary $A\in\mathcal{C}$ (by the
assumption that $\mathcal{C}\neq\emptyset$). Let $\mathbf{t}^{A}=\hom_{\rm
Nature}(\mathcal{F},A)$ and $\mathbf{t}^{B}=\hom_{\rm Nature}(\mathcal{F},B)$.
Note that $\mathbf{t}^{A}(i)=\mathbf{t}^{B}(i)=0$ for every $i>s$ and
$\mathbf{t}^{A}(i)$ and $\mathbf{t}^{B}(i)$ are strictly positive for every
$i\leq s$.

Let $\mathcal{H}=\\{H_{1},\dots,H_{r}\\}$ be the non-empty set of instances
constructed as follows:

  1. (i)

For every $1\leq i\leq s$, $F_{i}$ is contained in $\mathcal{H}$.

  2. (ii)

For every $i,i^{\prime}\in\\{1,\dots,s\\}$ such that there is no surjective
homomorphism $F_{i}\rightarrow F_{i^{\prime}}$, $\mathcal{H}$ contains the
instance $H$ given by Lemma 5.6.

For each $1\leq i\leq r$, let $\mathbf{t}_{i}=\hom_{\rm
Nature}(\\{F_{1},\ldots,F_{s}\\},H_{i})$. It can be readily verified that
$\mathbf{t}_{1},\dots,\mathbf{t}_{r}$ satisfy the conditions of Lemma 5.4.
Condition (1) is guaranteed due to step (i) in the construction of
$\mathcal{H}$. For condition (2), let $i,i^{\prime}$ be any pair of different
integers in $\\{1,\dots,s\\}$. Since $F_{i}$ and $F_{i^{\prime}}$ are not
isomorphic, it must be the case that there is no surjective homomorphism
$F_{i}\rightarrow F_{i^{\prime}}$ or there is no surjective homomorphism
$F_{i^{\prime}}\rightarrow F_{i}$. Hence, due to step (ii), $\mathcal{H}$
contains some instance $H_{j}$ witnessing
$\mathbf{t}_{j}(i)\neq\mathbf{t}_{j}(i^{\prime})$.

Let $c>0$ be given by Lemma 5.4, let $\mathbf{b}\in\mathbb{Z}^{s}$ where
$\mathbf{b}(i)=c(\mathbf{t}^{B}(i)-\mathbf{t}^{A}(i))$ for every $1\leq i\leq
s$, and let $p(x_{1},\dots,x_{r})$ be the polynomial given by Lemma 5.4 for
$\mathbf{b}$. We can express $p(x_{1},\dots,x_{r})$ as
$p_{A}(x_{1},\dots,x_{r})-p_{B}(x_{1},\dots,x_{r})$ where all the coefficients
in $p_{A}$ and $p_{B}$ are positive.

For every polynomial $q(x_{1},\dots,x_{r})$ where the independent term is
zero, consider the instance $H_{q}$ defined inductively as follows:

  * •

If $q=x_{j}$, then $H_{q}$ is $H_{j}$.

  * •

If $q=u+v$, then $H_{q}$ is $H_{u}\oplus H_{v}$.

  * •

If $q=u\cdot v$, then $H_{q}=H_{u}\otimes H_{v}$.

######  Lemma 5.8.

Let $H_{q}$ be constructed as above. Then:

  1. 1.

$H_{q}\rightarrow F_{1}\oplus\cdots\oplus F_{s}$.

  2. 2.

Let $F$ be a connected instance and let $\mathbf{t}=\hom_{\rm
Nature}(F,\mathcal{H})$. Then $\hom_{{\rm Nature}}(F,H_{q})=q(\mathbf{t})$.

This lemma directly follows from the definition of $H_{q}$. More precisely,
the first item follows from the fact that $H_{j}\rightarrow
F_{1}\oplus\cdots\oplus F_{s}$ for every $H_{j}\in\mathcal{H}$ (as can be
shown by a straightforward induction argument). The second item follows from
the definition of $H_{q}$ and Proposition 2.1.

Let $A^{\prime}=A_{1}\oplus\cdots\oplus A_{c}\oplus H_{p_{A}}$ where
$A_{1},\dots,A_{c}$ are disjoint copies of $A$. Similarly, define
$B^{\prime}=B_{1}\oplus\cdots\oplus B_{c}\oplus H_{p_{B}}$ where
$B_{1},\dots,B_{c}$ are disjoint copies of $B$. We claim that
$\mathbf{t}^{A^{\prime}}=\hom_{\rm Nature}(\mathcal{F},A^{\prime})$ and
$\mathbf{t}^{B^{\prime}}=\hom_{\rm Nature}(\mathcal{F},B^{\prime})$ coincide.

Let $1\leq i\leq k$ and consider first the case $i>s$. It follows from Lemma
5.8(1) that $F_{i}\not\rightarrow H_{p_{A}}$. Indeed, if $F_{i}\rightarrow
H_{p_{A}}$, then $F_{i}\rightarrow F_{i^{\prime}}$ for some $i^{\prime}\leq s$
implying that $\mathcal{C}=\emptyset$, contradicting our assumption. Similarly
$F_{i}\not\rightarrow H_{p_{B}}$. Consequently,
$\mathbf{t}^{A^{\prime}}(i)=c\cdot\mathbf{t}^{A}(i)=0=c\cdot\mathbf{t}^{B}(i)=\mathbf{t}^{B^{\prime}}(i)$.
For the other case, namely $i\leq s$, we have

$\displaystyle\mathbf{t}^{B^{\prime}}(i)-\mathbf{t}^{A^{\prime}}(i)$
$\displaystyle=\hom_{{\rm Nature}}(F_{i},B^{\prime})-\hom_{{\rm
Nature}}(F_{i},A^{\prime})$ $\displaystyle=c\cdot\hom_{{\rm
Nature}}(F_{i},B)-c\cdot\hom_{{\rm Nature}}(F_{i},A^{\prime}))+\hom_{{\rm
Nature}}(F_{i},H_{p_{B}})-\hom_{{\rm Nature}}(F_{i},H_{p_{A}})$
$\displaystyle=c\cdot(\mathbf{t}^{B}(i)-\mathbf{t}^{A}(i))+\hom_{{\rm
Nature}}(F_{i},H_{p_{B}})-\hom_{{\rm Nature}}(F_{i},H_{p_{A}})$
$\displaystyle=c\cdot(\mathbf{t}^{B}(i)-\mathbf{t}^{A}(i))+p_{B}(\mathbf{t}_{1}(i),\dots,\mathbf{t}_{r}(i))-p_{A}(\mathbf{t}_{1}(i),\dots,\mathbf{t}_{r}(i))$
$\displaystyle=c\cdot(\mathbf{t}^{B}(i)-\mathbf{t}^{A}(i))-p(\mathbf{t}_{1}(i),\dots,\mathbf{t}_{r}(i))$
$\displaystyle=c\cdot(\mathbf{t}^{B}(i)-\mathbf{t}^{A}(i))-\mathbf{b}(i)=0,$

where $\hom_{{\rm
Nature}}(F_{i},H_{p_{A}})=p_{A}(\mathbf{t}_{1}(i),\dots,\mathbf{t}_{r}(i))$
and $\hom_{{\rm
Nature}}(F_{i},H_{p_{B}})=p_{B}(\mathbf{t}_{1}(i),\dots,\mathbf{t}_{r}(i))$
hold by Lemma 5.8(2).

To finish the proof, note that since $\mathbf{t}^{A}(i)>0$ for every $1\leq
i\leq s$ it follows by Lemma 5.8(1) that $A^{\prime}\rightarrow A$, and, hence
$A\leftrightarrow A^{\prime}$. Similarly we have $B^{\prime}\leftrightarrow
B$. Since $\mathcal{C}$ is closed under homomorphic equivalence we have that
$A^{\prime}\in\mathcal{C}$. Since
$\mathbf{t}^{A^{\prime}}=\mathbf{t}^{B^{\prime}}$ it follows that $B^{\prime}$
and, hence, $B$ belong to $\mathcal{C}$ as well.

######  Corollary 5.9.

Let $\mathcal{C}$ be a class of instances closed under homomorphic
equivalence. Then the following statements are equivalent.

  1. 1.

$\mathcal{C}$ admits a left query algorithm over ${\rm Nature}$.

  2. 2.

$\mathcal{C}$ admits a left query algorithm over $\mathbb{B}$.

  3. 3.

$\mathcal{C}$ is FO-definable.

The equivalence of statements (1) and (2) follows from Theorem 5.2 together
with Proposition 3.2. The equivalence of statements (2) and (3) was already
established in Corollary 4.3.

We would like to point out some interesting special cases of Theorem 5.2. The
first pertains to CSPs. Let us say that a constraint satisfaction problem
$\mathrm{CSP}(B)$ is “ _determined by $\hom_{K}(\mathcal{F},\cdot)$_” for some
$K\in\\{\mathbb{B},{\rm Nature}\\}$ and some class $\mathcal{F}$ of instances,
if the following holds for all instances $A$ and $A^{\prime}$: if
$\hom_{K}(\mathcal{F},A)=\hom_{K}(\mathcal{F},A^{\prime})$ then
$A\in\mathrm{CSP}(B)$ iff $A^{\prime}\in\mathrm{CSP}(B)$. Then Theorem 5.2 can
be rephrased as follows: for every finite set of connected instances
$\mathcal{F}$, every CSP determined by $\hom_{\rm Nature}(\mathcal{F},\cdot)$
is determined by $\hom_{\mathbb{B}}(\mathcal{F},\cdot)$. In contrast, for
$\mathcal{T}$ the infinite class of all trees, the CSPs determined by
$\hom_{\mathbb{B}}(\mathcal{T},\cdot)$ form a proper subclass of those
determined by $\hom_{\rm Nature}(\mathcal{T},\cdot)$.222 Note that the
definitions of $\hom_{\rm Nature}(\mathcal{F},\cdot)$ and
$\hom_{\mathbb{B}}(\mathcal{F},\cdot)$ extend naturally to infinite classes
$\mathcal{F}$. This follows from results in [8], because the former are
precisely the CSPs that can be solved using arc-consistency, while the latter
are precisely the CSPs that can be solved using basic linear programming
relaxation (BLP). See [23, Example 99] for an example of a CSP that can be
solved using BLP but not using arc-consistency.

The second special case pertains to homomorphic-equivalence classes. Given the
importance of homomorphic equivalence as a notion of equivalence in database
theory, it is natural to ask when a database instance $A$ can be uniquely
identified up to homomorphic equivalence by means of a left query algorithm.
As we saw earlier, in Section 4, for left query algorithm over $\mathbb{B}$,
this is the case if and only if $\mathrm{CSP}(A)$ is FO-definable (a condition
that can be tested effectively, and, in fact, is NP-complete to test). It
follows from Corollary 5.9 that the same criterion determines whether $A$ can
be uniquely identified up to homomorphic equivalence by means of a left query
algorithm over ${\rm Nature}$. This extends naturally to finite unions of
homomorphic equivalence classes.

Finally, let us consider again classes $\mathcal{C}$ defined by a Boolean
Datalog program $P$. It follows from the results we mentioned in Section 4
that such a class of instances $\mathcal{C}$ admits a left query algorithm
over ${\rm Nature}$ if and only if $P$ is bounded, and that testing for the
existence of a left query algorithm over ${\rm Nature}$ is undecidable.

##  6 Right Query Algorithms

Just as for left query algorithms, we have that every class of instances that
admits a right query algorithm over $\mathbb{B}$ is closed under homomorphic
equivalence. However, _unlike_ left query algorithms, a class of instances
that admits a right query algorithm over $\mathbb{B}$ is not necessarily FO-
definable. Concretely, as we saw in Example 3.7, the class of 3-colorable
graphs admits a right query algorithm over $\mathbb{B}$, but is not FO-
definable. In fact, _every_ constraint satisfaction problem $\mathrm{CSP}(A)$
admits a right query algorithm over $\mathbb{B}$, and the FO-definable ones
are precisely those that admit a left query algorithm over $\mathbb{B}$. The
next result is straightforward.

######  Proposition 6.1.

Let $\mathcal{C}$ be a class of instances. Then $\mathcal{C}$ admits a right
query algorithm over $\mathbb{B}$ if and only if $\mathcal{C}$ is definable by
a Boolean combination of CSPs.

We also saw in Section 3 that not every homomorphic-equivalence closed FO-
definable class admits a right query algorithm over $\mathbb{B}$. For example,
the class of triangle-free graphs does not admit a right query algorithm over
$\mathbb{B}$ (or even over ${\rm Nature}$). This raises the question which
homomorphic-equivalence closed FO-definable classes admit a right query
algorithm over $\mathbb{B}$. Equivalently, _which classes $\mathcal{C}$ that
admit a left query algorithm over $\mathbb{B}$, admit a right query algorithm
over $\mathbb{B}$_? We will address this question next by making use of two
known results.

######  Theorem 6.2 (Sparse Incomparability Lemma, [22]).

Let $m,n\geq 0$. For every instance $B$ there is an instance $B^{*}$ of girth
at least $m$ such that, for all instances $D$ with
$\left|\mathrm{adom}(D)\right|\leq n$, we have $B\in\mathrm{CSP}(D)$ if and
only if $B^{*}\in\mathrm{CSP}(D)$.

A _finite homomorphism duality_ is a pair of finite sets
$(\mathcal{F},\mathcal{D})$ such that, for every instance $A$, the following
are equivalent: (i) $F\to A$ for some $F\in\mathcal{F}$; (ii) $A\not\to D$ for
all $D\in\mathcal{D}$. We make use of the following known characterization of
this notion.

######  Theorem 6.3 ([13]).

Let $A$ be an instance. Then the following statements are equivalent.

  1. 1.

$A$ is homomorphically equivalent to an acyclic instance.

  2. 2.

There is a finite homomorphism duality $(\mathcal{F},\mathcal{D})$ with
$\mathcal{F}=\\{A\\}$.

  3. 3.

There is a finite homomorphism duality $(\mathcal{F},\mathcal{D})$ with
$\mathcal{F}=\\{A\\}$ and where $\mathcal{D}$ consists of instances $D$ for
which $\mathrm{CSP}(D)$ is FO-definable.

To see the implication $(2)\Longrightarrow(3)$, note that, if
$(\mathcal{F},\mathcal{D})$ is a finite homomorphism duality, then
$\bigcup_{D\in\mathcal{D}}\mathrm{CSP}(D)$ is a FO-definable class (because it
is defined by the negation of the UCQ $\bigvee_{F\in\mathcal{F}}q^{F}$). It
follows, by the same reasoning as in the proof of Proposition 4.4, that exists
$\mathcal{D}^{\prime}\subseteq\mathcal{D}$ such that
$(\mathcal{F},\mathcal{D}^{\prime})$ is a finite homomorphism duality and such
that, for each $D\in\mathcal{D}^{\prime}$, we have that $\mathrm{CSP}(D)$ is
FO-definable.

Our next result characterizes the classes that admit both a left query
algorithm and a right query algorithm over $\mathbb{B}$.

######  Theorem 6.4.

Let $\mathcal{C}$ be a class of instances. Then the following statements are
equivalent.

  1. 1.

$\mathcal{C}$ admits both a left query algorithm and a right query algorithm
over $\mathbb{B}$.

  2. 2.

$\mathcal{C}$ admits a left query algorithm over ${\rm Nature}$ and a right
query algorithm over $\mathbb{B}$.

  3. 3.

$\mathcal{C}$ is definable by a Boolean combination of Berge-acyclic CQs.

  4. 4.

$\mathcal{C}$ is definable by a Boolean combination of FO-definable CSPs.

######  Proof 6.5.

The equivalence of statements (1) and (2) follows from Corollary 5.9. The
proof of the remaining equivalences is as follows.

$(1)\Longrightarrow(3)$ By Theorem 4.1 and Proposition 6.1, $\mathcal{C}$ is
definable by a Boolean combination $\varphi$ of CQs, as well as by a Boolean
combination $\psi$ of CSPs. Let $\varphi^{\prime}$ be obtained from $\varphi$
by replacing each conjunctive query $q$ by the disjunction of all homomorphic
images of $q$ that are Berge-acyclic. We claim that $\varphi^{\prime}$ defines
$\mathcal{C}$.

By Theorem 6.3, we know that $\varphi^{\prime}$ is also equivalent to a
Boolean combination of CSPs, which we may call $\psi^{\prime}$. Let $n$ be the
maximum size of a CSP occurring in $\psi$ and $\psi^{\prime}$. Also, let $m$
be greater than the maximum size of the CQs in $\varphi$. Let $B$ be any
instance, and let $B^{*}$ now be the instance given by Theorem 6.2 (for $m,n$
as chosen above). By construction, $B$ and $B^{*}$ agree with each other on
their membership in CSPs of size at most $n$, which include all CSPs occurring
in $\psi$ as well as $\psi^{\prime}$, and therefore, $B$ and $B^{*}$ agree on
$\psi$ and $\psi^{\prime}$. Since $\psi$ is equivalent to $\varphi$ and
$\psi^{\prime}$ is equivalent to $\varphi^{\prime}$, this means that $B$ and
$B^{*}$ agree on $\varphi$ and $\varphi^{\prime}$. Furthermore, by
construction, $\varphi^{\prime}$ is equivalent to $\varphi$ on instances of
girth at least $m$ (because every homomorphic image of a CQ of size less than
$m$ in such an instance must be acyclic). In particular, It follows that
$B^{*}\models\varphi$ iff $B^{*}\models\varphi^{\prime}$. Putting everything
together, we have that $B\models\varphi$ iff $B^{*}\models\varphi$ iff
$B^{*}\models\varphi^{\prime}$ iff $B\models\varphi^{\prime}$.

$(3)\Longrightarrow(4)$ This follows from Theorem 6.3 (for $A$ the canonical
instance of $q$): we simply replace each Berge-acyclic conjunctive query $q$
by the conjunction $\bigwedge_{D\in\mathcal{D}}\neg\mathrm{CSP}(D)$.

$(4)\Longrightarrow(1)$ This follows from Theorem 4.1 and Proposition 6.1.

Let $\mathcal{C}$ be a class that admits a left query algorithm over
$\mathbb{B}$ or, equivalently, let $\mathcal{C}$ be definable by a Boolean
combination of CQs. It follows that $\mathcal{C}$ admits a right query
algorithm over $\mathbb{B}$ if and only if $\mathcal{C}$ is definable by a
Boolean combination of _Berge-acyclic_ CQs. Similarly, let $\mathcal{C}$ be a
class that admits a right query algorithm over $\mathbb{B}$ or, equivalently,
let $\mathcal{C}$ be definable by a Boolean combination of CSPs. It follows
that $\mathcal{C}$ admits a left query algorithm over $\mathbb{B}$ if and only
if $\mathcal{C}$ is definable by a Boolean combination of _FO-definable_ CSPs.

Finally, we will consider the question when a class of the form
$\left[A\right]_{\mathrel{\leftrightarrow}}$ admits a right query algorithm
over $\mathbb{B}$.

######  Theorem 6.6.

Let $A$ be an instance. Then the following statements are equivalent.

  1. 1.

$\left[A\right]_{\mathrel{\leftrightarrow}}$ has a right query algorithm over
$\mathbb{B}$.

  2. 2.

$\\{B:A\mathrel{\rightarrow}B\\}$ has a right query algorithm over
$\mathbb{B}$.

  3. 3.

$A$ is homomorphically equivalent to an acyclic instance.

Moreover, testing whether this holds (for a given instance $A$) is NP-
complete.

######  Proof 6.7.

We will close a cycle of implications.

$(1)\Longrightarrow(2)$: For this, we use the exponentiation operation $X^{Y}$
[17]. This operation has the property that $X\to Y^{Z}$ if and only if
$X\mathbin{\otimes}Z\to Y$. Assume $\\{B:A\mathrel{\rightarrow}B\\}$ does not
admit a right query algorithm over $\mathbb{B}$. Consider an arbitrary finite
set of instances $\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ (think: candidate
right query algorithm for $\left[A\right]_{\mathrel{\leftrightarrow}}$). Since
$\\{B:A\mathrel{\rightarrow}B\\}$ does not admit a right query algorithm over
$\mathbb{B}$, for the set
$\mathcal{F}^{A}\colonequals\\{F_{1}^{A},\ldots,F_{k}^{A}\\}$ there are
instances $P$ and $Q$ with $A\mathrel{\rightarrow}P$ and
$A\not\mathrel{\rightarrow}Q$ such that
$\hom_{\mathbb{B}}(P,\mathcal{F}^{A})=\hom_{\mathbb{B}}(Q,\mathcal{F}^{A})$
or, equivalently,
$\hom_{\mathbb{B}}(P\mathbin{\otimes}A,\mathcal{F})=\hom_{\mathbb{B}}(Q\mathbin{\otimes}A,\mathcal{F})$.
Let $P^{\prime}\colonequals P\mathbin{\otimes}A$ and let
$Q^{\prime}\colonequals Q\mathbin{\otimes}A$. Then, by Proposition 2.1,
$P^{\prime}\in\left[A\right]_{\mathrel{\leftrightarrow}}$ and
$Q^{\prime}\notin\left[A\right]_{\mathrel{\leftrightarrow}}$ but
$\hom_{\mathbb{B}}(P^{\prime},\mathcal{F})=\hom_{\mathbb{B}}(Q^{\prime},\mathcal{F})$.
Therefore $\left[A\right]_{\mathrel{\leftrightarrow}}$ has no right query
algorithm over $\mathbb{B}$.

$(2)\Longrightarrow(3)$: Assume that $\\{B\mid A\to B\\}$ admits a right query
algorithm for $\mathbb{B}$. We will construct a finite homomorphism duality
$(\mathcal{F},\mathcal{D})$ with $\mathcal{F}=\\{A\\}$. It then follows by
Theorem 6.3 that $A$ is homomorphically equivalent to an acyclic instance. Let
$B_{1},\ldots B_{n}$ be all those instances $B_{i}$ used by the right query
algorithm for which it holds that $A\not\to B_{i}$. We claim that
$(\\{A\\},\\{B_{1},\ldots,B_{n}\\})$ is a finite homomorphism duality. Let $C$
be any instance. If $C\to B_{i}$ for some $i\leq n$, then $A\not\to C$
(otherwise, by transitivity, we would have that $A\to B_{i}$). Conversely, if
$A\not\to C$, then the algorithm must answer “no” on input $C$ while it
answers “yes” on input $C\mathbin{\oplus}A$. Therefore, one of the right-
queries made by the algorithm must differentiate $C$ from
$C\mathbin{\oplus}A$. It is easy to see that the right-query in question must
consist of an instance into which $C$ maps but $A$ does not. This instance
must then be among the $B_{i}$, and $C\to B_{i}$.

$(3)\Longrightarrow(1)$: By Theorem 6.3, there is a finite homomorphism
duality $(\\{A\\},\mathcal{D})$. In particular, for all instances $C$, we have
that $C\in\left[A\right]_{\mathrel{\leftrightarrow}}$ if and only if $C\to A$
and $C\not\to D$ for all $D\in\mathcal{D}$.

To test if a given instance is homomorphically equivalent to an acyclic
instance, it suffices to test that its core is acyclic (equivalently, that it
has an acyclic retract). This can clearly be done in NP. The NP-hardness
follows directly from Theorem 6 in [10].

The preceding Theorem 6.6 can be thought of as an analogue of Proposition 4.6
for right query algorithms. Again, this result extends to finite unions of
homomorphic-equivalence classes.

######  Theorem 6.8.

For all instances $A_{1},\ldots,A_{n}$, the following statements are
equivalent.

  1. 1.

$\mathop{\bigcup}_{1\leq i\leq
n}\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$ admits a right query
algorithm over $\mathbb{B}$.

  2. 2.

Each $\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$, for $i=1,\ldots,n$,
admits a right query algorithm over $\mathbb{B}$.

In particular, testing whether this holds (for given instances
$A_{1},\ldots,A_{n}$) is NP-complete.

######  Proof 6.9.

It is clear that the second statement implies the first. We will prove by
induction on $n$ that the first statement implies the second. The base case
($n=1$) is immediate since then statements (1) and (2) coincide. Next, let
$n>1$ and $\mathcal{C}\colonequals\mathop{\bigcup}_{1\leq i\leq
n}\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$. We proceed by
contraposition, assuming that $\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$
does not admit a right query algorithm over $\mathbb{B}$ for some $i\leq n$.
We may assume without loss of generality that $A_{1},\ldots,A_{n}$ are
pairwise not homomorphically equivalent. Note that $\mathrel{\rightarrow}$
induces a preorder among $A_{1},\ldots,A_{n}$ and, since $n$ is finite, there
is a minimal. Without loss of generality, assume that $A_{n}$ is a minimal,
that is, $A_{i}\not\mathrel{\rightarrow}A_{n}$ for all $i<n$. We distinguish
two cases.

(1) $\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$ admits a right query
algorithm over $\mathbb{B}$. Then, for some $i\leq n-1$,
$\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$ does not admit any right
query algorithm over $\mathbb{B}$. By induction hypothesis, we have
$\mathcal{C}^{\prime}\colonequals\mathop{\bigcup}_{1\leq i\leq
n-1}\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$ does not admit any right
query algorithm over $\mathbb{B}$. Then $\mathcal{C}$ does not admit a right
query algorithm over $\mathbb{B}$ either, since
$\mathcal{C}^{\prime}=\mathcal{C}\setminus\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$.

(2) $\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$ does not admit any right
query algorithm over $\mathbb{B}$. By Theorem 6.6, the class
$\\{B:A\mathrel{\rightarrow}B\\}$ does not admit any right query algorithm
over $\mathbb{B}$, either. Consider an arbitrary finite non-empty set of
instances $\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$. Since
$\\{B:A\mathrel{\rightarrow}B\\}$ does not admit any right query algorithm
over $\mathbb{B}$, for the set
$\mathcal{F}^{A_{n}}=\\{F_{1}^{A_{n}},\ldots,F_{k}^{A_{n}}\\}$ there are
instances $P$ and $Q$ with $A_{n}\mathrel{\rightarrow}P$ and
$A_{n}\not\mathrel{\rightarrow}Q$ such that
$\hom_{\mathbb{B}}(P,\mathcal{F}^{A_{n}})=\hom_{\mathbb{B}}(Q,\mathcal{F}^{A_{n}})$,
which implies that
$\hom_{\mathbb{B}}(P\mathbin{\otimes}A_{n},\mathcal{F})=\hom_{\mathbb{B}}(Q\mathbin{\otimes}A_{n},\mathcal{F})$.
It follows by Proposition 2.1 that

  * •

$(P\mathbin{\otimes}A_{n})\in\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$
because $A_{n}\mathrel{\rightarrow}P$,

  * •

$(Q\mathbin{\otimes}A_{n})\notin\left[A_{n}\right]_{\mathrel{\leftrightarrow}}$
because $A_{n}\not\mathrel{\rightarrow}Q$,

  * •

for all $i<n$,
$(Q\mathbin{\otimes}A_{n})\notin\left[A_{i}\right]_{\mathrel{\leftrightarrow}}$
because $A_{i}\not\mathrel{\rightarrow}A_{n}$.

Let $P^{\prime}\colonequals P\mathbin{\otimes}A_{n}$ and let
$Q^{\prime}\colonequals Q\mathbin{\otimes}A_{n}$. Then the above discussion
yields that $P^{\prime}\in\mathcal{C}$ and $Q^{\prime}\notin\mathcal{C}$ while
$\hom_{\mathbb{B}}(P^{\prime},\mathcal{F})=\hom_{\mathbb{B}}(Q^{\prime},\mathcal{F})$.
Therefore, $\mathcal{C}$ does not admit any right query algorithm over
$\mathbb{B}$.

######  Remark 6.10.

We saw in Example 3.5 that the class of triangle-free graphs, which clearly
has a left query algorithm over $\mathbb{B}$, does not admit a right query
algorithm over $\mathbb{B}$ or over ${\rm Nature}$. Observe that this class is
defined by the negation of the “triangle” conjunctive query $\exists
xyz(R(x,y)\land R(y,z)\land R(z,x))$. In light of Theorem 6.4, the lack of a
right query algorithm over $\mathbb{B}$ for this class can be “explained” by
the fact that this conjunctive query is not Berge-acyclic. Furthermore, in
Example 3.8 we mentioned that the class
$\left[K_{3}\right]_{\mathrel{\leftrightarrow}}$, that is, the class of graphs
that are 3-colorable and also contain a triangle, does not admit a right query
algorithm over $\mathbb{B}$. This follows from Theorem 6.6.

We conclude this section with an open problem.

######  Question 6.11.

Does a suitable analogue of Theorem 5.2 hold for right query algorithms?

##  7 Summary and Discussion of Related Topics

Inspired by the work of Chen et al. [9], we extended their framework and
studied various types of query algorithms, where a query algorithm for a class
$\mathcal{C}$ of instances determines whether a given input instance belongs
to $\mathcal{C}$ by making a finite number of (predetermined) queries that ask
for the existence of certain homomorphisms or for the number of certain
homomorphisms. Specifically, we introduced and studied _left query algorithms_
and _right query algorithms_ over $\mathbb{B}$, as well as over ${\rm
Nature}$. Our results delineate the differences in expressive power between
these four types of query algorithms. In particular, they pinpoint when the
ability to count homomorphisms is essential for the existence of left query
algorithms.

Relationship to view determinacy Recently, Kwiecien et al. [24] studied view
determinacy under bag semantics. In particular, they obtained a decidability
result for determinacy with respect to Boolean views under bag-set semantics.
We will briefly describe their framework and relate it to ours. At the most
abstract level, a _view_ is simply a function $f$ that takes as input a
database instance. Specifically, under set semantics, every Boolean CQ
specifies a view that is a function from database instances to $\\{0,1\\}$,
while, under bag-set semantics, every Boolean CQ specifies a view that is a
function from database instances to ${\rm Nature}$. We say that a finite
collection of views $f_{1},\ldots,f_{k}$ _determines_ a view $g$, if for all
database instances $A$ and $B$, if $f_{i}(A)=f_{i}(B)$ for all $i\leq k$, then
$g(A)=g(B)$. The aforementioned result from [24] asserts that the following
problem is decidable: given views $f_{1},\ldots,f_{k}$ and $g$ specified by
Boolean CQs under bag-set semantics, is $g$ is determined by
$f_{1},\ldots,f_{k}$?

We now describe the relationship between the above notion of view determinacy
and our framework. Let $\mathcal{C}$ be a class of instances and let
$\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ be a finite set of instances. Then the
following are equivalent:

  1. 1.

There exists a set $X$ such that $(\mathcal{F},X)$ is a left query algorithm
over ${\rm Nature}$ for $\mathcal{C}$,

  2. 2.

$f_{1},\ldots,f_{k}$ determine $g_{\mathcal{C}}$ where $f_{i}(A)=\hom_{\rm
Nature}(F_{i},A)$ and $g_{\mathcal{C}}$ is the indicator function of
$\mathcal{C}$ (i.e., $g_{\mathcal{C}}(A)=1$ if $A\in\mathcal{C}$ and
$g_{\mathcal{C}}(A)=0$ otherwise).

This tells that there are some important differences between our framework and
the one in [24]: (i) when we study the existence of left query algorithms, the
set $\mathcal{F}$ is not fixed, whereas, in the view determinacy problem, the
views are given as part of the input; (ii) in the view determinacy problem
studied in [24], the view $g$ is specified by a CQ with bag-set semantics,
whereas in our case $g$ is a Boolean-valued function since it is the indicator
function of a class of instances, (iii) we do not assume that the class
$\mathcal{C}$ is specified by a Boolean CQ. Indeed, if $\mathcal{C}$ were
specified by a Boolean CQ $q$, then a left query algorithm would trivially
exist, where $\mathcal{F}$ simply consists of (the canonical instance of) $q$
itself.

Other semirings Query algorithm over $\mathbb{B}$ and query algorithm over
${\rm Nature}$ can be viewed as special cases of a more general setting,
namely that of a query algorithm over a semiring. There is a body of research
in the interface of databases and semirings, including the study of provenance
of database queries using semirings [16, 19], the study of the query
containment problem under semiring semantics [15, 21], and, more recently, the
study of Datalog under semiring semantics [20]. In these studies, the
semirings considered are _positive_ , which means that they are commutative
semirings with no zero divisors and with the property that the sum of any two
non-zero elements is non-zero. It is perfectly meaningful to define
homomorphism counts over positive semirings and then investigate query
algorithms over such semirings. In particular, it may be interesting to
investigate query algorithms over the _tropical semiring_
$\mathbb{R}=(R\cup\\{\infty\\},\min,+)$, where $R$ is the set of real numbers,
since it is well known that various _shortest-distance_ problems can be
naturally captured using this semiring.

Adaptive query algorithms The query algorithms $(\mathcal{F},X)$ studied in
this paper are _non-adaptive_ , in the sense that the set
$\mathcal{F}=\\{F_{1},\ldots,F_{k}\\}$ is fixed up-front. In contrast, an
_adaptive_ query algorithm may decide the set of instances $\mathcal{F}$ at
run-time, that is to say, the choice of $F_{i}$ may depend on the
homomorphism-count vector for $F_{1},\ldots,F_{i-1}$. As pointed out in the
Introduction, whenever a class $\mathcal{C}$ admits an adaptive left (right)
query algorithm over $\mathbb{B}$, then it also admits a non-adaptive left
(right) query algorithm over $\mathbb{B}$. Note that the most “economical” (as
regards the number of instances used) non-adaptive algorithm for a class
$\mathcal{C}$ may use a larger set $\mathcal{F}$ of instances than the
adaptive one, but the number of instances used by the non-adaptive algorithm
is still finite. Thus, adaptive query algorithms over $\mathbb{B}$ do not
offer higher expressive power than adaptive ones. The situation for ${\rm
Nature}$ is quite different: it was shown in [9] that _every_ isomorphism-
closed class of instances (in particular, every homomorphic-equivalence closed
class) admits an adaptive left $k$-query algorithm over ${\rm Nature}$ already
for $k=3$; therefore, adaptive left query algorithms over ${\rm Nature}$ have
higher expressive power than adaptive left query algorithms over $\mathbb{B}$,
even when it comes to homomorphic-equivalence closed classes. Switching sides,
note that the class of triangle-free graphs (Example 3.5) does not admit an
adaptive right query algorithm over ${\rm Nature}$, as was shown in [9,
Proposition 8.2]; hence it is a meaningful question to ask: which homomorphic-
equivalence closed classes admit an adaptive right query algorithm over ${\rm
Nature}$?

## References

  * [1] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases, volume 8.  Addison-Wesley Reading, 1995.
  * [2] Miklos Ajtai and Yuri Gurevich.  Datalog vs first-order logic.  Journal of Computer and System Sciences, 49(3):562–588, 1994.  30th IEEE Conference on Foundations of Computer Science.  URL: https://www.sciencedirect.com/science/article/pii/S0022000005800716, doi:https://doi.org/10.1016/S0022-0000(05)80071-6.
  * [3] Albert Atserias, Phokion G Kolaitis, and Wei-Lin Wu.  On the expressive power of homomorphism counts.  In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–13. IEEE, 2021.
  * [4] Michal Bielecki and Jan Van den Bussche.  Database interrogation using conjunctive queries.  In Database Theory - ICDT 2003, 9th Int. Conf., 2003, Proceedings, volume 2572 of Lecture Notes in Computer Science, pages 259–269. Springer, 2003.  URL: https://doi.org/10.1007/3-540-36285-1_17, doi:10.1007/3-540-36285-1\\_17.
  * [5] Meghyn Bienvenu, Balder Ten Cate, Carsten Lutz, and Frank Wolter.  Ontology-based data access: A study through disjunctive Datalog, CSP, and MMSNP.  ACM Trans. Database Syst., 39(4), December 2015.  URL: https://doi.org/10.1145/2661643, doi:10.1145/2661643.
  * [6] Jan Böker, Yijia Chen, Martin Grohe, and Gaurav Rattan.  The complexity of homomorphism indistinguishability.  In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, volume 138 of LIPIcs, pages 54:1–54:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.54, doi:10.4230/LIPIcs.MFCS.2019.54.
  * [7] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Chris Umans, editor, 58th IEEE Annual Symp. on Found. of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319–330. IEEE Computer Society, 2017.  URL: https://doi.org/10.1109/FOCS.2017.37, doi:10.1109/FOCS.2017.37.
  * [8] Silvia Butti and Víctor Dalmau.  Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the constraint satisfaction problem.  In International Symposium on Mathematical Foundations of Computer Science, 2021.
  * [9] Yijia Chen, Jörg Flum, Mingjun Liu, and Zhiyang Xun.  On algorithms based on finitely many homomorphism counts.  In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [10] Víctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi.  Constraint satisfaction, bounded treewidth, and finite-variable logics.  In Principles and Practice of Constraint Programming - CP 2002, 8th International Conference, CP 2002, Proceedings, volume 2470 of Lecture Notes in Computer Science, pages 310–326. Springer, 2002.  URL: https://doi.org/10.1007/3-540-46135-3_21, doi:10.1007/3-540-46135-3\\_21.
  * [11] Holger Dell, Martin Grohe, and Gaurav Rattan.  Lovász meets Weisfeiler and Leman.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107 of LIPIcs, pages 40:1–40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.40, doi:10.4230/LIPIcs.ICALP.2018.40.
  * [12] Zdenek Dvorák.  On recognizing graphs by numbers of homomorphisms.  J. Graph Theory, 64(4):330–342, 2010.  URL: https://doi.org/10.1002/jgt.20461, doi:10.1002/jgt.20461.
  * [13] Jan Foniok, Jaroslav Nešetřil, and Claude Tardif.  Generalised dualities and maximal finite antichains in the homomorphism order of relational structures.  European Journal of Combinatorics, 29(4):881–899, 2008.
  * [14] Haim Gaifman, Harry Mairson, Yehoshua Sagiv, and Moshe Y. Vardi.  Undecidable optimization problems for database logic programs.  J. ACM, 40(3):683–713, jul 1993.  URL: https://doi.org/10.1145/174130.174142, doi:10.1145/174130.174142.
  * [15] Todd J. Green.  Containment of conjunctive queries on annotated relations.  Theory Comput. Syst., 49(2):429–459, 2011.  URL: https://doi.org/10.1007/s00224-011-9327-6, doi:10.1007/s00224-011-9327-6.
  * [16] Todd J. Green, Gregory Karvounarakis, and Val Tannen.  Provenance semirings.  In Leonid Libkin, editor, Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007, pages 31–40. ACM, 2007.  URL: https://doi.org/10.1145/1265530.1265535, doi:10.1145/1265530.1265535.
  * [17] Pavol Hell and Jaroslav Nešetřil.  Graphs and homomorphisms, volume 28 of Oxford lecture series in mathematics and its applications.  Oxford University Press, 2004.
  * [18] Dan Kalman.  The generalized Vandermonde matrix.  Mathematics Magazine, 57(1):15–21, 1984.
  * [19] Grigoris Karvounarakis and Todd J. Green.  Semiring-annotated data: queries and provenance?  SIGMOD Rec., 41(3):5–14, 2012.  URL: https://doi.org/10.1145/2380776.2380778, doi:10.1145/2380776.2380778.
  * [20] Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang.  Convergence of datalog over (pre-) semirings.  In PODS ’22: Int. Conf. on Management of Data, Philadelphia, 2022, pages 105–117. ACM, 2022.  URL: https://doi.org/10.1145/3517804.3524140, doi:10.1145/3517804.3524140.
  * [21] Egor V. Kostylev, Juan L. Reutter, and András Z. Salamon.  Classification of annotation semirings over containment of conjunctive queries.  ACM Trans. Database Syst., 39(1):1:1–1:39, 2014.  URL: https://doi.org/10.1145/2556524, doi:10.1145/2556524.
  * [22] Gábor Kun.  Constraints, MMSNP and expander relational structures.  Combinatorica, 33(3):335–347, 2013.
  * [23] Gábor Kun and Mario Szegedy.  A new line of attack on the dichotomy conjecture.  European Journal of Combinatorics, 52:338–367, 2016.  Special Issue: Recent Advances in Graphs and Analysis.  URL: https://www.sciencedirect.com/science/article/pii/S0195669815001778, doi:https://doi.org/10.1016/j.ejc.2015.07.011.
  * [24] Jaroslaw Kwiecien, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja.  Determinacy of real conjunctive queries. the boolean case.  In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’22, page 347–358, New York, NY, USA, 2022\. Association for Computing Machinery.  URL: https://doi.org/10.1145/3517804.3524168, doi:10.1145/3517804.3524168.
  * [25] László Lovász.  Operations with structures.  Acta Math. Acad. Sci. Hungar, 18(3-4):321–328, 1967.
  * [26] Alan Nash, Luc Segoufin, and Victor Vianu.  Views and queries: Determinacy and rewriting.  ACM Trans. Database Syst., 35(3), jul 2010.  URL: https://doi.org/10.1145/1806907.1806913, doi:10.1145/1806907.1806913.
  * [27] Benjamin Rossman.  Homomorphism preservation theorems.  Journal of the ACM (JACM), 55(3):1–53, 2008.
  * [28] Claude Tardif, Cynthia Loten, and Benoit Larose.  A characterisation of first-order constraint satisfaction problems.  Logical Methods in Computer Science, 3, 2007.
  * [29] Dmitriy Zhuk.  A proof of CSP dichotomy conjecture.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331–342. IEEE Computer Society, 2017.  URL: https://doi.org/10.1109/FOCS.2017.38, doi:10.1109/FOCS.2017.38.