We investigate the problem of computing small conjunctive queries that separate positive from negative examples in ontology-enriched systems. This work builds upon prior research on the query-by-example paradigm, which focused on the existence of separating queries. Here, we go beyond mere existence and study how to construct separating queries that are both correct and compact. Specifically, we define a new recursive notion of homomorphism based on Trémaux trees (normal spanning trees), show that it allows us to extract small separating conjunctive queries from the chase (universal model), and provide an algorithm for this query construction process. Our results ofer both theoretical insights and practical tools for making ontology-based query-by-example more usable for end-users.
The query-by-example (QBE) paradigm has recently emerged as a promising approach for making
ontology-enriched systems (OES) more accessible to non-expert users. By allowing users to provide sets
of positive and negative examples instead of formal queries, QBE bridges the gap between intuitive data
exploration and formal query languages like description-logic concepts [
In this paper, we investigate the computational construction of small separating CQs in OES. Our focus lies not on particular DLs to formulate the ontology but rather on existential rules in general, however we restrict attention to unary and binary predicates. The core technical contribution of this work is a novel use of Trémaux trees (also known as: normal spanning trees) to guide the search for separating queries. By leveraging the tree structure, we define a recursive notion of homomorphisms — called Trémaux homomorphisms — and show that existence of a Trémaux homomorphism coincides with existence of a usual homomorphism. These new homomorphisms allow us to develop a new algorithmic approach to extracting small separating queries from the chase of a knowledge base — a canonical representation of its entailments. Our approach not only advances the theoretical understanding of query computation in OES but also opens up new directions for developing more intuitive and compact interfaces for QBE tools.
Signature. Consider a countable set C of constants and a countable set R of relations such that each relation in R has an arity ar() ∈ N. These two sets must be disjoint and together they constitute the signature. In Description Logic, constants are usually referred to as individuals, unary relations are called (atomic) concepts, and binary relations are roles. Further assume a countably infinite set V of variables disjoint with the signature. A term is either a constant or a variable.1 Syntax. An atom is of the form (1, . . . , ) : where each is a term and is an -ary relation. A substitution is a partial mapping : V →↦ C ∪ V . If is an atom, then denotes the term obtained by simultaneously replacing all occurrences of each variable by () if defined. 2 Given sets and ℬ of atoms, a match of in ℬ is a substitution such that ⊆ ℬ , where := { | ∈ } . We write =| ℬ if there is such a match. Then =| is a preorder (i.e. reflexive and transitive) on the set of all sets of atoms. From each match of in ℬ, we obtain a so-called homomorphism from to ℬ as the mapping ℎ : C ∪ V → C ∪ V where ℎ() := () if the latter is defined and ℎ() := otherwise; there are no further homomorphisms. Given a set of atoms, Var() is the set of all variables in and Terms() consists of all terms in .
Semantics. An interpretation ℐ is a set of atoms, and a database is a finite set of atoms. 3 A
tuplegenerating dependency (TGD) or existential rule is of the form ℬ ⇒ ℋ where the body ℬ and the head ℋ
are finite sets of atoms. Var(ℬ) ∩ Var(ℋ) is called the frontier of ℬ ⇒ ℋ. An interpretation ℐ is a model
of a database if =| ℐ. A TGD ℬ ⇒ ℋ is satisfied in an interpretation ℐ if every match of ℬ in ℐ
can be extended to a match of ℋ in ℐ (i.e. for each match of ℬ in ℐ, there is a match of ℋ in ℐ such
that, for each variable ∈ Var(ℬ), if () is defined, then () = () , else () is also undefined).
A knowledge base (KB) is a pair (, ) consisting of a database and a finite set of TGDs (called
ontology). An interpretation ℐ is a model of (, ) if it is a model of and satisfies all TGDs in .
Chase. In the setting considered here, each KB (, ) has a model (i.e. is consistent). Such a model
can be constructed by means of the chase: it initializes an interpretation ℐ with the database and
then, simply put, it successively extends ℐ whenever there is a TGD in such that there is match of its
body in ℐ that cannot be extended to a match of the head in ℐ. The limit of this construction is also
called chase, viz. the chase of (, ), symbol: chase(, ). The chase does not terminate for every KB,
meaning that chase(, ) might be countably infinite, and diferent variants of the chase exist [
Conjunctive Queries. An -ary conjunctive query (CQ) is of the form (1, . . . , ) : where each
is a variable, called answer variable, and is a finite set of atoms. A mapping : { 1, . . . , } → C
is an answer to this CQ w.r.t. an interpretation ℐ if =| ℐ (i.e. if can be extended to a match from
to ℐ), and is a certain answer to this CQ w.r.t. a KB (, ) if it is an answer to the CQ w.r.t. every
model of (, ). Query Answering is the problem consisting of all tuples of (string encodings of) a
KB, a CQ, and a mapping such that the mapping is a certain answer to the CQ w.r.t. the KB. In general,
query answering is undecidable [
Query Containment. Given CQs (1, . . . , ) : 1 and (1, . . . , ) : 2 with the same answer
variables, we say that the first is contained in the second if, for every interpretation ℐ, each answer to
the first CQ in ℐ is also an answer to the second CQ in ℐ. This is the case if. there is match of 2 in
1 that preserves the answer variables, i.e. where ( ) = for each [
Unions of Conjunctive Queries. A union of conjunctive queries (UCQ) is of the form (1, . . . , ) :
1 ⊔ 2 ⊔ · · · ⊔ where each (1, . . . , ) : is a CQ and all these CQs have the same arity and
the same answer variables. Answers to this UCQ w.r.t. ℐ are all answers to any CQ (1, . . . , ) :
w.r.t. ℐ, and similarly for the certain answers w.r.t. (, ). Given UCQs (1, . . . , ) : 1 ⊔ · · · ⊔ ℓ and
(1, . . . , ) : 1 ⊔ · · · ⊔ with the same answer variables, the first is contained in the second if.,
for each index ∈ {1, . . . , ℓ}, there is some index ∈ {1, . . . , } such that the CQ (1, . . . , ) : is
contained in the CQ (1, . . . , ) : [
Translation to First-order Logic. Databases, CQs, and TGDs can be syntactically translated into ifrst-order logic by replacing each finite set of atoms by its conjunction ⋀︀ and adding quantifiers for the variables. In particular, a database translates to ∃ 1. ∃ 2. . . . ∃ . ⋀︀ for an arbitrary enumeration Var() = {1, 2, . . . , }, a CQ (1, . . . , ) : translates to ∃ 1. ∃ 2. . . . ∃ . ⋀︀ for an arbitrary enumeration Var() ∖ {1, 2, . . . , } = {1, 2, . . . , }, and a TGD ℬ ⇒ ℋ translates to ∀ 1. ∀ 2. . . . ∀ . (⋀︀ ℬ → ∃ 1. ∃ 2. . . . ∃ . ⋀︀ ℋ) for arbitrary enumerations Var(ℬ) = {1, 2, . . . , } and Var(ℋ) ∖ Var(ℬ) = {1, 2, . . . , }. Assuming The Axiom of Choice, the Löwenheim-Skolem Theorem implies that this translation preserves the semantics — it sufices to consider countable structures in order to interpret first-order theories over at most countable signatures. Since we can rewrite between countable structures (first-order interpretations) and the above defined interpretations in the obvious way, every first-order model yields a model in the above sense and vice versa.
Products. Given finitely many sets 1, . . . , of atoms, their product 1 × · · · × is a set consisting of the atoms ( (11, . . . , 1), . . . , (1, . . . , )) : for all atoms (11, . . . , 1) : ∈ 1, . . . , (1, . . . , ) : ∈ , where : (C ∪ V) → C ∪ V is an arbitrary bijection such that (, . . . , ) = for each constant and otherwise (1, . . . , ) is a variable (i.e. if the are not all the same constant). Since V is countably infinite, such bijections always exist. In technical considerations we use this function only implicitly and rather assume that all atoms in the product are of the form ((11, . . . , 1), . . . , (1, . . . , )) : , where constants and according tuples (, . . . , ) are treated as synonyms.
Undirected Graphs. An undirected graph (with loops) is a pair (, ) consisting of a set of vertices and a set of edges such that consists of subsets of with one or two elements. Edges with one element are called loops. A walk from a vertex to a vertex is a sequence 0, 1, . . . , of vertices such that 0 = , = , and {−1 , } ∈ for each ∈ {1, . . . , }; its length is . It is a path if all vertices are pairwise distinct, and it is empty if = 0. We say that a vertex is reachable from another vertex if there is a walk from to . A graph (, ) is connected if each vertex is reachable from each other vertex. The distance between vertices and is the smallest length of a path from to , or ∞ if no such path exists. A cycle is a non-empty walk that starts and ends with the same vertex and otherwise consists of pairwise distinct vertices, and we call a graph (, ) acyclic if it does not contain any cycles. A connected, acyclic undirected graph is usually called an undirected tree. In each undirected tree, there is a unique shortest path from each vertex to each other vertex. Furthermore, each undirected tree (, ) with a distinguished vertex 0, called the root, admits a partial order ≤ on , namely where ≤ if the (unique) shortest path from 0 to can be extended to the (unique) shortest path from 0 to .
Further Notions. Consider a set of atoms. Given a set of terms, the subset of generated by is the smallest subset ℬ of containing all atoms from that involve some term contained in or occuring in some atom in ℬ. The induced graph of is the undirected graph := (, ) where consists of all terms and consists of all edges {, } such that and occur together in some atom involving a predicate with arity ≥ 2 (where and might be equal). The distance in between two terms is the distance between them in . We call connected if the induced graph is connected. Similarly, a CQ (1, . . . , ) : is connected if is connected.
The query-by-example (QBE) paradigm considers a KB (, ) and sets and of positive and, respectively, negative examples. These examples are mappings from a fixed set of answer variables 1, . . . , to the set of constants. A solution is a (U)CQ that separates the positive from the negative examples in the sense that all mappings in are certain answers w.r.t. the KB but none of the negative ones. QBE is useful in situations where users do not have the ability to formulate queries themselves — they can then rather use such a solution query.
As solutions we will only consider constant-free (U)CQs, i.e. where no constants occur in the atoms. To this end, we ignore the semantics of constants and rather treat them as if they were variables. Formally, we use constant-ignoring homomorphisms from to ℬ, which are defined like homomorphisms but without the requirement to leave constants unchanged (i.e. ℎ() = is not required for each constant ).
Definition 1. Consider a KB (, ), variables 1, . . . , , and finite sets and of mappings : { 1, . . . , } → C. A (U)CQ with answer variables 1, . . . , separates and if all mappings in are certain answers to it w.r.t. (, ) but no mapping in is a certain answer.
By slightly adapting the proof of Theorem 1 in [
Specifically, it follows that there is a constant-free CQ separating and if. there is a connected such CQ. Both above conditions can be decided if the chase terminates — in this case we obtain a CQ that separates and and is most specific w.r.t. query containment as the query (1, . . . , ) : , where the atom set is the product× =1 chase(, ) specifically constructed with a bijection such that all values of are variables (since we want a constant-free CQ) and ( ()) = for each answer variable .
Existence of a constant-free separator CQ is undecidable w.r.t. ℰ ℒℐ KBs [
For the cases where a CQ separator does not exist, there could still be a UCQ separator. Of course,
such a UCQ exists if., for each positive example ∈ , there is a CQ separating {} and , say
(1, . . . , ): — a UCQ separating and is then (1, . . . , ):⨆︀∈ . For this reason, existence
of a constant-free separator UCQ w.r.t. Horn-ℒ KBs is complete for (deterministic) exponential time
[
Determining the minimal number of disjuncts is already NP-hard since we can reduce the
minimumset-cover problem [
In practice, one might do it the greedy way: determine a first maximal subset 1 of such that a CQ separating 1 and exists, next find a maximal subset 2 of ∖ 1 that can be separated from by a CQ, and likewise continue inductively with the remaining positive examples until none is left over.
When we are only interested in a subset S of the set R of relations to be used in the separator (U)CQs, then Theorem 2 holds accordingly when the -fold product× =1 chase(, ) is replaced by its subset consisting of all atoms with a relation in S.
A Trémaux tree of an undirected graph is a spanning tree such that every edge of the graph connects
an ancestor–descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a
19th-century French author who used a form of depth-first search as a strategy for solving mazes. In
computer science they are also called depth-first trees [
Definition 3. Let (, ) be a connected undirected graph with loops. Further let 0 ∈ be a vertex. A Trémaux tree of (, ) with root 0 is a subset of such that 1. (, ) is an undirected tree, and 2. ≤ or ≤ for each edge {, } ∈ , where ≤ is the induced partial order of (, ) for root 0.
Although the following result is already known, we want to provide an own proof.5 Proposition 4. For each finite connected undirected graph with loops and with a distinguished vertex, a Trémaux tree can be computed in polynomial time.
Proof. Assume that (, ) is a connected undirected graph with loops and let 0 be a distinguished vertex from . In the following, we will devise a recursive procedure that produces a Trémaux tree. Firstly, initialize an undirected graph (, ) where := . During the run of the procedure, we maintain a set of unprocessed vertices that we initialize as := . The invariant during the construction is that, for each processed vertex ∈ ∖ , there is a unique shortest path from 0 to within (, ). The computation starts by calling the following recursive procedure on the distinguished vertex 0.
Process(): Mark as processed by removing from . The unprocessed neighborhood of is the set () := { | ∈ and {, } ∈ }. Define the undirected graph ( ′, ′) by ′ := {} ∪ (), ′ := { {, } | ∈ () } ∪ { {1, 2} | 1, 2 ∈ () and 1 ∼ 2 }, where 1 ∼ 2 if 1 is reachable from 2 in the subgraph (, )↾ := (, { | ∈ and ⊆ }). Note that ∼ is an equivalence relation on (), i.e. it is reflexive, symmetric, and transitive. Thus, the subgraph of ( ′, ′) obtained by removing is a disjoint union of complete graphs,6 and all vertices of each such complete graph are connected with by an edge. A schematic presentation of the graph ( ′, ′) is given in Figure 1. For each complete graph, select one vertex . . .
() , delete from all edges from into that complete graph except {, }, and then proceed recursively by calling Process(). Note that, if 0, 1, . . . , is the unique shortest path from 0 to within (, ), then 0, 1, . . . , , is the unique shortest path from 0 to within (, ), i.e. the invariant is satisfied. 5In fact, the author only later recognized that Trémaux trees have already been well investigated. 6A complete graph is a graph in which all vertices are connected by an edge.
After termination, the invariant is still satisfied and so it follows that the resulting graph (, ) is an undirected tree. It remains to show that ≤ or ≤ for each edge {, } ∈ , where ≤ is the partial order on that is induced by (, ) for root 0. For this purpose, consider an edge {, } ∈ . • If {, } has not been deleted, i.e. is contained in , then either the unique shortest path from 0 to can be extended to the unique shortest path from 0 to or vice versa. It follows that either ≤ or ≤ . • Otherwise, the edge {, } has been deleted from , i.e. during the call either of Process() or of Process(). We only treat the first case, the other is analogous. During the call of Process(), ′ a vertex ′ in the complete graph containing was selected and all edges from into this complete graph except {, ′} were deleted, see Figure 2. Due to the invariant it follows that, after termination, the unique shortest path from 0 to must go through and thus ≤ must be satisfied.
We conclude that, after termination, the resulting graph (, ) is a Trémaux tree of (, ) with root 0.
Since each vertex is processed only once, there are only linearly many calls to the procedure Process(·) . It is well-known that graph reachability can be decided in polynomial time and thus the intermediate graph ( ′, ′) during each call to Process(·) can be constructed in polynomial time. We conclude that the initial call of Process(0) terminates in polynomial time.
In the remainder of this article we assume that the signature consists only of constants, unary relations, and binary relations.
Definition 5. Let be a database and a term in . A Trémaux order of with root is the partial order ≤ on Terms() induced by some Trémaux tree of the induced graph with root .
According to Proposition 4, Trémaux orders can be computed in polynomial time.
Let be a database and 0 a term occurring in . Further assume that ≤ is a Trémaux order of with root 0 and denote by ≺ the neighborhood relation of ≤ , i.e. ≺ if < and there is no such that < < . Note that, if ≺ , then the edge {, } must be present, i.e. there is a role such that contains at least one of the atoms (, ) : or (, ) : . We will also write (, ) : − for the latter, where − denotes the inverse of , i.e. we do not distinguish between the atoms (, ) : and (, ) : − . For each ≺ , we choose some atom (, ) : in , where is a role or an inverse − , and then set , := . To indicate that ≺ and , = , we occasionally write ≺ .
Example 6. Consider the database := {(, ) : , (, ) : , (, ) : , (, ) : , (, ) : , (, ) : } and let be the root term. The induced graph := (, ) has vertex set := {, , } and edge set := {{, }, {, }, {, }}. A Trémaux tree of with root is (, ) with edge set := {{, }, {, }}. The induced partial order ≤ , which is a Trémaux order of with root , has the neighborhood relation ≺ where ≺ ≺ . We choose , := and , := . The below figure shows the Trémaux order ≤ , where solid lines represent edges in the Trémaux tree and dashed lines represent the remaining edges.
− −
Consider a KB (, ) defined over a signature that consists only of constants, unary relations, and binary relations. Further consider a single answer variable 1 and finite sets and of mappings : { 1} → C, which are the positive and negative examples, such that there is a constant-free CQ that separates and . Our goal now is to construct a small separating CQ.
By assumption, the two conditions in Theorem 2 must be satisfied. Condition 1 ensures that we can ifnd a term in the -fold product of the chase that “describes” all commonalities of the positive examples, viz. in our setting the tuple (1) consisting of all ( 1) where ranges over . Condition 2 ensures that these commonalities are not all fulfilled by any negative example. Together both conditions ensure the existence of a separating CQ.
Specifically by Condition 2” there is a depth such that it sufices to consider all terms with a distance ≤ to (1), and already this finite 7 subset ↾ of the -fold product of chase(, ) does not admit, for any negative example , a constant-ignoring homomorphism to chase(, ) that maps (1) to ( 1). We then obtain a separating CQ 1 : ↾ when ↾ is taken from the product× =1 chase(, ) specifically constructed with a bijection such that ( (1)) = 1 and all values of are variables. However, this CQ can be quite large.
Now we exploit the particular structure of a Trémaux order in order to recursively define Trémaux homomorphisms, and then we show that existence of a constant-ignoring homomorphism is equivalent to existence of such a Trémaux homomorphism. Afterwards, we show how a small subset of ↾ can be extracted for which 1 : is already a CQ separating and .
Definition 7. Let be a connected database, a term in , and ℬ a set of atoms. Further let ≤ be a Trémaux order of . A Trémaux homomorphism from to ℬ up to is a partial mapping ℓ : Terms() →↦ Terms(ℬ) that fulfills the following conditions: 1. ℓ() is defined for each ≤ . 2. ℓ() : ∈ ℬ for each : ∈ where is a unary relation and ≤ . 3. (ℓ(1), ℓ(2)) : ∈ ℬ for each (1, 2) : ∈ where is a binary relation (or its inverse), 1 ≤ , and 2 ≤ . 4. ℓ can be extended to a Trémaux homomorphism from to ℬ up to each where ≺ .
Formally: for each where ≺ , there is some such that (ℓ(), ) : ∈ ℬ and the extended partial mapping ℓ ∪ { ↦→ } is a Trémaux homomorphism from to ℬ up to .
Proposition 8. Let be a connected database, ℬ a set of atoms, a term in , and a term in ℬ. Further let ≤ be a Trémaux order of with root . The following statements are equivalent.
1. There is a constant-ignoring homomorphism from to ℬ that maps to 2. { ↦→ } is a Trémaux homomorphism from to ℬ up to . 7Since there are only finitely many TGDs, the chase is finitely branching. ≥ this subset into a CQ. (ℎ(′), ℎ(′)) : ∈ ℬ
.
Therefore ℎ already satisfies Conditions 2 and 3 in Definition 7 for every term in Proof. Regarding the only-if direction, let ℎ be a homomorphism from to ℬ such that ℎ() = . those ≤ ). Condition 4 follows by induction w.r.t. ≤ since, if ′ ≺ ′, then (′, ′) : ∈ and thus (not only for
In the converse direction, we obtain a homomorphism in the limit. More specifically, we can lazily build it by Condition 4, i.e. we traverse through along ≺ of all partial mappings ℓ ∪ {′ ↦→ ′}. This yields a well-defined mapping since, on the one hand, starting from and construct the union assignments of terms that are smaller w.r.t. ≤
are never overwritten and, on the other hand, all terms ′ Definition 3. Since all terms are reachable from , this limit mapping is defined for all terms in . next to a term ′ (i.e. where ′ ≺ ′) can be processed independently of each other due to Condition 2 in
One point worthy of remark is that, since all terms next to a term can be processed independently, we can easily implement a parallel procedure for deciding homomorphism existence when the signature is at most binary.8
Finally, we come back to our goal of constructing a small separating CQ. Proposition 8 yields that, for each ∈ , the partial mapping { (1) ↦→ ( 1)} is no Trémaux homomorphism from ↾ to chase(, ) up to (1), and thus Conditions 2 or 3 in Definition 7 must already be violated by the root (1) or, by following the recursion in Condition 4, one of them must be violated by a term (1). We use this observation to collect a small but suficiently large subset of ↾ that already witnesses the non-existence of homomorphisms for all negative examples, and afterwards transform
We initialize the subset of ↾ as the empty set. Furthermore, we maintain a mapping that assigns to each term in ↾ a set of partial mappings, where we initialize ( (1)) := { { (1) ↦→ ( 1)} | ∈ } and () := ∅ for each term ̸= (1). The invariant is that each set () will always contain only such mappings ℓ where ℓ() is defined for each ≤ from ↾ to chase(, ) up to . We start with processing (1), i.e. we call Process( (1)). and that are no Trémaux homomorphisms Process(): For each ℓ ∈ (), do the following.
1. Choose one of the following two instructions and try to execute it. If it cannot be executed, try the other.
the atom : to . a) Try to choose a unary atom : in ↾ where ℓ() : is not in chase(, ), and add is not in chase(, ), and add the atom (, ) : to .
b) Try to choose a binary atom (, ) : in ↾ such that ≤ and where (ℓ(), ℓ()) : 2. If none of the two above instructions can be executed, then choose a term where ≺ such that, for each term where (ℓ(), ) : is in chase(, ), the extension ℓ ∪ { ↦→ } is no Trémaux homomorphism from ↾ to chase(, ) up to . Due to the invariant and Condition 4 in Definition 7, such a term
must exist. Then, add the atom (, ) : to and further add ℓ ∪ { ↦→ } to () for each where (ℓ(), ) : is in chase(, ).
Afterwards, call Process() for each where ≺ and () ̸= ∅.
concepts has already been considered [
It is easy to see that the above procedure yields a minimal separating CQ (i.e. with a smallest number
of atoms) when there is only one negative example. The author claims that with a suitable strategy the
procedure can also yield minimal CQs for multiple negative examples, but existing results on verifying
extremal separating CQs already imply high computational complexity even without TGDs [
Future Prospects. In order to expand on this result, it would be interesting to lift the current restriction to only one answer variable of separating CQs and, furthermore, to investigate how higherarity relations in the signature can be handled.
This work has been supported by Deutsche Forschungsgemeinschaft (DFG) in Project 389792660 (TRR 248: Foundations of Perspicuous Software Systems) and in Project 558917076 (Construction and Repair of Description-logic Knowledge Bases) as well as by the Saxon State Ministry for Science, Culture, and Tourism (SMWK) by funding the Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI).
During the preparation of abstract and introduction of this work, the author used ChatGPT in order to: Paraphrase and reword, Improve writing style. After using this tool, the author reviewed and edited the content as needed and takes full responsibility for the publication’s content.