Various problems arising in the context of example-driven approaches to query discovery have turned out to be intimately related to basic structural properties of the homomorphism lattice of nite structures, such as density, or the existence of duals. In this keynote, I will review some such connections, and highlight some relevant recent results.
Let us consider the partial order (Str; hom), where Str is the set of all nite structures over some schema S, and hom denotes the existence of a homomorphism (that is, A hom B holds if there is a homomorphism from A to B, i.e., a function from the domain of A to the domain of B that preserves structure). For the purpose of this exposition, we will assume that S is a xed, nite schema, consisting of relation symbols and constant symbols. We will write A <hom B if A hom B and B 6 hom A, and we will say that A and B are homomorphically equivalent if A hom B and B hom A.
This partial order (Str; hom) turns out to have a rich structure and has been
the subject of extensive study. For a wonderful textbook on this topic (focusing
on the case of directed graphs, where the schema S consists of a single binary
relation and no constant symbols), see [
The \meet" operation N A, here is simply the direct product, and the \join" operation L A, in the case without constant symbols, is simply the disjoint union (the de nition of L A for structures with constant symbols is a little ? Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
F1 . . .
Fn > A ? more involved, we omit the details here, cf. [11]). We will refer to this lattice as the Homomorphism Lattice.
One computational problem in this context that will be relevant below is the
product homomorphism problem : given a nite set of structures A and a structure
B, the task is to decide whether N A hom B (or, equivalently, whether C hom
A for all A 2 A implies C hom B). Since the structure N A itself can be
constructed in singly exponential time, the product homomorphism problem
can be solved in NExpTime. A matching lower bound was established in [
Theorem 1 ([
One interesting direction in the study of the homomorphism lattice pertains
to density. It is known that the homomorphism lattice is not a dense lattice.
That is, there exist structures B <hom A for which there is no structure C with
B <hom C <hom A. Such pairs (B; A) are also known as gap pairs [
De nition 1. A frontier for a structure A is a nite collection of structures F such that 1. F <hom A for all F 2 F 2. For all structures C, if C <hom A, then C hom F for some F 2 F .
In other words, a frontier for A is a nite set of structures that separates A from those structures that are homomorphically strictly smaller than A, as depicted in Figure 1.
As it turns out, there is simple necessary and su cient condition for the existence of a frontier. To de ne this condition, we must consider the incidence graph of a structure A, by which we mean the bipartite multi-graph whose vertices are the elements of the domain of A and the facts of A, and such that an element and a fact are connected by an edge if the element occurs in the fact. If an element occurs multiple times in the same fact, each occurrence generates an edge (hence, this is a multi-graph).
De nition 2. A structure is acyclic if the incidence graph is acyclic, and a structure is c-acyclic if every cycle of the incidence graph passes through at least one element that is named by a constant symbol.
Note that if the schema S does not contain constant symbols, c-acyclicity is the same as acyclicity.
Theorem 2 ([11]). Every c-acyclic structure has a frontier. Moreover, given a c-acyclic structure, a frontier can be constructed in polynomial time. Conversely, if a structure A has a frontier, then A is homomorphically equivalent to a cacyclic structure.
It also follows from this result that we can test whether a given set of structures is a frontier. In fact, this problem is NP-complete.
Theorem 3. The following problem is NP-complete: given a structure A and a nite set of structures F , is F a frontier for A? Proof (sketch). For the upper bound, we use the fact that, if A is homorphically equivalent to a c-acyclic structure A0, then such A0 exists as a substructure of A (we omit the details, but this follows directly from the fact that c-acyclicity is preserved under passage from a structure to its core). Therefore, the problem can be solved in non-deterministic polynomial time as follows: rst we guess a substructure A0 and we verify that A0 is c-acyclic and homomorphically equivalent to A. Note that the existence of such A0 is a necessary precondition for B1; : : : ; Bn to be a frontier of A. Next, we apply Theorem 2 to construct a frontier F 0 for A0 (and hence for A). Finally, we verify that each F 2 F homomorphically maps to some F 0 2 F 0 and vice versa. It is not hard to see that this non-deterministic algorithm has an accepting run if and only if F is a frontier for A.
For the lower bound, we reduce from graph 3-colorability. Let A be the structure, over a 3-element domain, that consists of the facts R(a; b) for all pairs a; b with a 6= b. In addition, each of the three elements is named by a constant symbol. Since A is c-acyclic, by Theorem 2, it has a frontier F . Now, given any graph G (viewed as a relational structure with binary relation R and without constant symbols), we have that G is 3-colorable if and only if F is a frontier for the disjoint union of A with G. To see that this is the case, note that if G is 3-colorable, then the disjoint union of A with G is homomorphically equivalent to A itself, whereas if G is not 3-colorable, then the disjoint union of A with G is strictly greater than A in the homomorphism order. tu
Another, closely related topic in the study of the homomorphism lattice is that of dualities. A pair of structures (A; B) are said to be a duality pair if fC j A 6 hom Cg = fC j C hom Bg. Intuitively, this means that the entire class of structures can be partitioned into two disjoint sets: those structures into which A homomorphically maps, and those structures that homomorphically map into B. More generally a pair of nite sets of structures (A; D) is said to be a generalized homomorphism duality if fC j A 6 hom C for all A 2 Ag = fC j C hom B for some B 2 Bg. A famous in nitary example of a homomorphism duality is the following: a graph G is 2-colorable (equivalently, has a homomorphism into the 2-element clique) if and only if G does not contain a cycle of odd length (equivalently, does not not have a homomorphism from a structure consisting of a cycle of odd length).
As was shown in [
Suppose one wishes to construct a query Q on the basis of a set of data examples. For the sake of concreteness, assume that the query Q we wish to construct is a k-ary conjunctive query (k 0) over a schema S. For the purpose of our complexity analysis, we will treat the schema and the arity as xed. Each given data example will be a triple (I; a; s), where I is a database instance (over the schema S), a is a k-tuple of values from the active domain of I, and s 2 f+; g indicates whether the data example is a positive example or a negative example. We say that a query Q ts such a data example (I; a; s) if a 2 Q(I) (for the case where s = +), or a 62 Q(I) (for the case where s = ).
One natural high-level approach for constructing Q might be as in the following ow chart:
Input data examples E
Q that ts E (if it exists) no
Failure (revisit input examples) yes no
examples until only one query Q remains that ts yes
Output Q Output Q
Following this approach, three computational tasks naturally arise. The rst
task is, given an input set of data examples, to decide whether there exists a
tting query, and, if so, produce one. This has also been described a
reverseengineering problem [
Now, let E be a set of data examples, and let Q be (the canonical query
of) the direct product of all positive examples in E. It is not hard to show
that if there exists any query that ts the data examples, then Q must t the
data examples. Moreover, it already follows from the construction that Q ts
all positive examples in E, and, in order for Q to t the negative examples, it
must be the case that there is no homomorphism from Q to any of the negative
data examples in E. This shows that the existence of a conjunctive query tting
a given set of data examples, reduces to (a conjunction of instances of) the
product homomorphism problem. It is not hard to establish a reduction in the
other direction as well. Moreover, in the case where a tting conjunctive query
exists, the conjunctive query Q constructed above is guaranteed to be a greatest
tting query for the examples, that is, Q0 hom Q holds for all conjunctive
queries Q0 that t the data examples in E. Therefore, in summary, we have:
Theorem 4 ([
At this point, assuming that a tting conjunctive query does indeed exists, we have obtained a candidate query Q, which is in fact a greatest tting conjunctive query. We then arrive at the next question, which is whether Q is the only query (up to logical equivalence) that ts E. This second problem turns out, in our speci c setting, to be NP-complete. Formally, we say that the data examples in E uniquely characterize Q if Q ts E and, furthermore, every conjunctive query that ts E is logically equivalent to Q.
Theorem 5. The following problem is NP-complete: given a collection E of positive and negative examples, and a greatest tting conjunctive query Q for E, do the data examples in E uniquely characterize Q? Proof (sketch). Theorem 5 is proved by showing that the problem is computationally equivalent to the problem of testing whether a given set of structures is a frontier. In one direction, we claim that the data examples in E uniquely characterize Q if and only if the set F = f(N Q) j N is a negative example from Eg is a frontier for Q. Note that, here, as before, we take the liberty to skip over minor details by con ating conjunctive queries, data examples, and structures.
First, suppose that Q is uniquely characterized by E. We must show that F is a frontier for Q. Clearly, (N Q) hom Q. Furthermore, since Q ts the negative example N , we have that Q 6 hom N and therefore Q 6 hom (N Q). Finally, let B <hom Q, and suppose for the sake of a contradiction that B does not homomorphically map to any structure in F . It follows that B does not map to any negative example N . Therefore, (the canonical query of) B ts all examples in E and is not equivalent to Q, a contradiction. Next, suppose that F is a frontier for Q. We must show that Q is uniquely characterized by E. Suppose, for the sake of a contradiction, that Q0 ts all examples in E and is not equivalent to Q. Since Q is a greatest tting query, it must be the case that Q0 hom Q and Q 6 hom Q0. Therefore, Q hom (N Q) for some negative example N , and hence Q hom N , a contradiction.
To prove the NP lower bound, we provide an even simpler reduction in the opposite direction. Let A be any structure and F a nite set of structures such that each structure in F is homomorphically below A. Then F is a frontier for A if and only if A is uniquely characterized by the set E that consists of A itself as a positive example, and the structures in F as negative examples. tu
At this point, we know whether the examples in E uniquely characterize Q.
If the answer is Yes, then we can safely conclude that Q is the query we were
after. Otherwise, we arrive at the last of our three problems, namely, eliciting
further examples with the aim of identifying our target query with certainty.
1 The result as stated in [
Here, we enter into the territory of computational learning theory. Without
going into details, the rst question that arises is whether, by eliciting further
examples, we can even hope to arrive at a situation in which we can identify our
target conjunctive query with certainty. This question is, of course, equivalent
to the question whether the target conjunctive query is uniquely characterizable
by nitely many examples. It turns out that the answer is Yes precisely if the
target query has a nite frontier [11]. By Theorem 2, this holds precisely if the
target query is (homomorphically equivalent to) a c-acyclic conjunctive query. If
the target query is not homomorphically equivalent to a c-acyclic query, then,
no matter how many additional data examples we elicit, we will never arrive at
a situation in which our set of data examples uniquely characterizes the target
query. Remarkably, it turns out that if the target query is c-acyclic, then there
exists an e cient exact learning algorithm (in the formal sense of Angluin's
model of interactive exact learnability [
This short paper was written with the aim of highlighting some interesting topics
and their connections to the structure of the homomorphism lattice. It is by no
means a comprehensive survey of work that has been done in this area. In fact,
there is considerable literature on example-driven discovery of database queries,
description logic ontologies, and schema mappings, as discussed in the related
work sections of the papers cited here. See also [
Since we focused on the case of conjunctive queries in this exposition, one
might ask what changes when considering unions of conjunctive queries. As it
turns out, in this context there is a close correspondence between unions of
conjunctive queries and GAV schema mappings. Without going into details, this
is because a GAV schema mapping can be equivalently viewed as a mapping that
assigns to each target relation a union of conjunctive queries over the source
schema. Unique characterizations for GAV schema mappings were extensively
studied in [
We close by brie y mentioning two other interesting problems with close
connections with the structure of the homomorphism lattice. The rst is
instancelevel query de nability, which refers to de nability of relations inside a given
database instance. More speci cally, the CQ-de nability problem, consists in
deciding, given a database instance I and a relation S over the active domain of
I, whether there is a conjunctive query Q such that Q(I) = S. It turns out that
this problem is again computationally equivalent to the product homomorphism
problem (cf. [