Reverse Engineering Queries in Ontology-Enriched Systems: The Case of Expressive Horn Description Logic Ontologies

1 Introduction

In recent times, ontology-enriched systems (OES) have risen as a prominent technology for data management. The appeal of OES comes from the fact that the ontology provides rich schema information or background knowledge which enriches the answers of queries. The success of this paradigm has led not only to the development of a vast amount of foundational results, but also of optimized systems used in real-life scenarios, see e.g., [Rodriguez-Muro et al., 2013; Kharlamov et al., 2015; Calvanese et al., 2016; Hovland et al., 2017] and references therein. For instance, the OES Ontop is currently being used to access exploration data generated by the petroleum company Statoil [Kharlamov et al., 2015]. In these OES, users access the data through queries usually formulated in powerful query languages such as conjunctive or path queries. Unfortunately, in real life, casual nonexpert users are often not able to specify queries using these formalisms (e.g., Statoil geologists [Hovland et al., 2017]), clearly hampering the usability of OES.

In relational databases (witnessing the same problem), an alternative approach for querying was proposed to alleviate this problem: query-by-example (QBE), where roughly, users give positive and negative examples which the system should reverse-engineer into a query conforming with the examples [Zloof, 1975]. Because of 'big data', this querying paradigm has lately gained new interest since even expert users might find it useful to explore the data in this way. As a result, QBE has been investigated for different query languages and data representations, e.g., conjunctive queries over relational data [Tran et al., 2014; ten Cate and Dalmau, 2015; Bonifati et al., 2016; Barcel´o and Romero, 2017], SPARQL queries over RDF data [Arenas et al., 2016], and path queries over graph databases [Bonifati et al., 2015].

The goal of this paper is two-fold. First, we aim at initiating research on the QBE approach to querying in the context of ontology-enriched systems. We mainly focus on establishing foundational results for QBE over OES with the ontology formulated in description logics (DLs). Formally, we introduce and study the following problem QBE(L, Q) for an ontology language L and some query language Q: given an L-knowledge base and sets of positive and negative examples, decide whether there is a query q ∈ Q such that all positive examples are certain answers to q over K, and none of the negative is. As query language Q, we consider (unions of) conjunctive queries, (U)CQs. We allow for a restricted signature Σ, which is a common feature in many OES. As a simple example, consider the knowledge base consisting of

T = {Human ⊑ Vertebrate, Vertebrate ⊑ ∃hasPart.Spine},

A = {Human(ax), hasPart(an, sp), Spine(sp), Bug(bug)}.

If the positive examples are ax, an and the negative example is bug, then q(x) = ∃y hasPart(x, y) ∧ Spine(y) is a witness query. However, there is no witnessing query for the positive examples an, bug if ax is to be avoided.

The second aim is to continue bridging the gap between DL and machine learning research. Indeed, QBE over knowledge bases can be viewed as an instantiation of the inductive logic programming (ILP) framework [Nienhuys-Cheng and de Wolf, 1997]: the background knowledge is given by a DL knowledge base and the learning goal are single rules for Q = CQ and sets of rules with the same head for Q = UCQ, respectively. In this area, the work closest to ours is perhaps [Kietz, 2002].

Our main contributions are characterizations, algorithms, and complexity bounds for QBE(L,Q) for L an expressive Horn DL L ∈ {Horn-ALCI,Horn-ALC} and Q ∈ {CQ,UCQ}. In Section 3, we start with providing natural model-theoretic characterizations for QBE(Horn-ALCI,Q) for Q ∈ {CQ, UCQ} by lifting characterizations known from the relational database setting [ten Cate and Dalmau, 2015] by replacing the database with the universal model of the knowledge base. Unfortunately, our characterizations do not give

Leif Sabellek

University of Bremen, Germany sabellek@uni-bremen.de immediate rise to a decision procedure because the universal model is typically infinite. In Section 4, we exploit the regularity of universal models and provide decision procedures running in 2-EXPTIME and CONEXPTIME for Horn-ALCI and Horn-ALC, respectively. Having these, we prove matching lower bounds, the most challenging one being a 2-EXPTIMElower bound for QBE(Horn-ALCI,Q), Q ∈ {CQ,UCQ}. Interestingly, some results depend on restricting the signature, so we consider also the variant QBEf of QBE with unrestricted signature. The following table summarizes our results.

We obtain the same results for the variant QDEF of QBE, the problem to decide whether some q ∈ Q returns precisely the positive examples. In Section 5, we investigate the size of witness queries. This is of course vital for practical purposes since at the end the user is interested in obtaining a (witness) query to further explore the data. We particularly show that they can be double exponentially large, which is in contrast to the relational database setting. In Section 6, we discuss related work and lay out directions for future work.

An extended version with appendix can be found under www.informatik.uni-bremen.de/tdki/research/papers.html.

2 Preliminaries

Syntax. We introduce the DL Horn-ALCI [Kr¨otzsch et al., 2013]. Let NC,NR,NI be infinite disjoint sets of concept, role, and individual names, respectively. The syntax of HornALCI concepts C, D is given by the grammar:

where A ∈ NC and r ∈ {s, s- | s ∈ NR} is a role. Concepts of the form B are called basic concepts and roles of the form r- inverse roles. We identify r- with s ∈ NR if r = s-.

A Horn-ALCI TBox (ontology) T is a finite set of concept inclusions (CIs) B ⊑ C, with B a basic concept and C a Horn-ALCI concept. An ABox A is a finite set of concept and role assertions of the form A(a) and r(a, b), where A ∈ NC, r ∈ NR and a, b ∈ NI. We write ind(A) for the set of individuals in A. A Horn-ALCI knowledge base (KB) K is a pair (T , A) of a Horn-ALCI TBox T and an ABox A. The fragment Horn-ALC is obtained by disallowing inverse roles; ELI is the fragment allowing only concept inclusions C ⊑ D with C, D ::= ⊤ | A | C ⊓ D | ∃r.C.

Semantics. The semantics is defined in terms of interpretations I = (∆I , ·I ), consisting of a non-empty domain ∆I and an interpretation function ·I mapping concept names to subsets of the domain and role names to binary relations over the domain. Further, we adopt the standard name assumption, i.e., aI = a for all a ∈ NI. The interpretation of complex concepts C I is defined in the usual way [Baader et al., 2017]. An interpretation I is a model of a TBox T if BI ⊆ C I for all CIs B ⊑ C ∈ T ; and it is a model of an ABox A if (a, b) ∈ rI

for all r(a, b) ∈ A and a ∈ AI for all A(a) ∈ A. We call a KB (T , A) consistent if T and A have a common model.

Queries. A conjunctive query (CQ) is an expression of the form q(x) = ∃yϕ(x, y), where x and y are tuples of variables and ϕ(x, y) is a conjunction of atoms of the form A(v) or r(v, w) with A ∈ NC, r ∈ NR, and v, w ∈ x ∪ y. We call x answer variables and y quantified variables of q. A union of conjunctive queries (UCQ) is an expression of the form q(x) = q1(x) ∨ . . . ∨ qn(x), where each qi(x) is a CQ with answer variables x. A match of a CQ q in an interpretation I is a function π : x ∪ y → ∆I such that π(v) ∈ AI for every atom A(v) of q and (π(v), π(w)) ∈ rI for every atom r(v, w) of q. We write I |= q(a1, . . . , an) if there is a match of q in I with π(xi) = ai, for all i ≤ n. A tuple a of elements from ind(A) is a certain answer to q over a KB (T ,A), written T ,A |= q(a), if I |= q(a) for all models I of T and A.

A signature Σ is a set of concept and role names. For a given signature Σ and a query language Q, we denote with QΣ the set of all queries in Q that use only names from Σ. Given an ABox A, S+ and S- denote n-ary relations over ind(A), called positive and negative examples over A, resp.

A closely related problem is the query definability problem QDEF(L, Q) which takes as input a tuple (T , A, S+, Σ) and asks whether there is a query q(x) ∈ QΣ such that an n-tuple a is a certain answer if, and only if a ∈ S+. If a tuple (T ,A, S+, S-,Σ) is a yes-instance of QBE(L,Q), then we call the query q(x) a witness. We further define the variant QBEf(L,Q) (f standing for full) as the problem of deciding for a given tuple (T ,A, S+, S-) whether (T , A, S+, S-, Σ∗ ) ∈ QBE(L, Q), where Σ∗ is the set of all concept and role names occurring in (T ,A); QDEFf(L) is defined analogously. Besides the decision problems, we will also be interested in the size of witness queries (if they exist).

We remark that allowing individual names in witness queries might be desirable in some applications, where the user knows some 'special' individuals which are relevant for her query. We show that our choice of forbidding them is without loss of generality. Let QBEc(L,Q) be the variant of QBE(L,Q) that takes another input I ⊆ ind(A) and allows the witness query to use constants from I. We then have:

Lemma 1. QBEc(L,Q) and QDEFc(L,Q) reduce in polynomial time to QBE(L,Q) and QDEF(L,Q), resp., for Q ∈ {CQ,UCQ}, for any L.

Throughout the paper, we will assume that the input knowledge base (T ,A) is consistent and that S+ is not empty. Both conditions can be effectively checked and if one of them isn't satisfied the reasoning problems become easier, see appendix.

Moreover, we assume that all TBoxes T are in ELI⊥-normal form, that is, CIs in T take one of the following forms:

where A,A′ ,B range over concept names and r ranges over roles. It has been shown that every Horn-ALCI TBox T can be transformed in polynomial time to an ELI⊥ TBox T ′ such that T ′ is a conservative extension of T [Bienvenu et al., 2016], and it is easily verified that then (T ,A, S+, S-,Σ) ∈ QBE(Horn-ALCI,Q) iff (T ′ , A, S+, S-, Σ) ∈ QBE(ELI⊥, Q), for Q∈{CQ, UCQ}.

3 Model-Theoretic Characterizations

In this section, we provide model-theoretic characterizations of QBE and QDEF, setting the foundations for the development of our decision procedures later on. We presume the standard notion of Σ-homomorphisms between interpretations (cf. appendix) and write I →Σ J if there is a homomorphism restricted to the signature Σ from I to J , and (I, a) →Σ (J , b) if there is such homomorphism that additionally maps the tuple a from ∆I to b from ∆J . We drop the Σ in case it comprises all relevant names.

Our characterization is based on the notion of direct products. Let I, J be interpretations. The direct product I ⊗J of I and J is the interpretation defined by ∆I⊗J = ∆I ×∆J ,

for all concept names A and role names r. The product (I, a) ⊗ (J , b) is defined as (I ⊗ J , a ⊗ b), where (a1, . . . , an)⊗(b1, . . . , bn) = ((a1, b1), . . . , (an, bn)). Given Σ, a product Πni=1 (Ii, ai) = (I1, a1)⊗. . .⊗(In, an) is called Σ-safe if every element of the tuple a1 ⊗ . . . ⊗ an appears in the extension of some concept or role name from Σ in Πni=1 (Ii, ai); again, we drop Σ in case it is trivial.

Let us recall the characterization for QBE with CQs over relational databases [ten Cate and Dalmau, 2015; Barcel´o and Romero, 2017]. For the sake of simplicity, we state it here in our terminology, that is, consider ABoxes instead of databases. Given an ABox A and sets S+, S- of examples over A, there is a CQ distinguishing S+ and S- iff

1. Πa∈S+(IA, a) is safe, and

where IA is A viewed as an interpretation. The intuition behind this characterization is as follows: the constructed product can be viewed as CQ with answer variables Πa∈S+a; in fact, this CQ is the least general generalization of the positive examples. Condition 1 ensures that it is a well-defined CQ by requiring all answer variables to actually appear, and Condition 2 ensures that no negative examples are returned.

We argue, however, that this simple characterization does not apply to the case with ontologies. In fact, the example from the introduction does not satisfy Condition 1, but there exists a witness query. We lift the characterization to take into account non-empty TBoxes using universal interpretations.

Universal Interpretations. Let (T ,A) be a consistent HornALCI KB and T in ELI⊥-normal form. A type for T is a subset t of the concept names in T such that T |= ⊓t ⊑ A implies A ∈ t for all concept names A. When a ∈ ind(A), t, t′ are types for T , and r is a role, we write

• a ⇝T ,A r t if T ,A |= ∃r.⊓t(a) and t is maximal with this condition, and
• t ⇝Tr t′ if T |= ⊓t ⊑ ∃r.⊓t′ and t′ is maximal with this condition.

A path for A and T is a finite sequence π = ar0t1 · · · tn-1rn-1tn, n ≥ 0, with a ∈ ind(A), r0, . . . , rn-1 roles, and t1, . . . , tn types for T such that

• r0 t1 and (ii) ti ⇝Tri ti+1 for every 1 ≤ i < n.

We use tail(π) to denote the last element of a path π. Let Paths be the set of all paths for A and T . The universal model UT ,A of (T ,A) is defined as follows:

It is well-known that UT ,A is universal in the sense that T ,A |= q(a) iff UT ,A |= q(a) for every UCQ q(x) and every tuple a of individuals [Bienvenu and Ortiz, 2015].

We state now our characterization for Q = CQ.

Theorem 1. For every Horn-ALCI KB (T ,A), all n-ary relations S+ and S- over ind(A), and signatures Σ, we have:

• (T ,A, S+, S-,Σ) ∈ QBE(Horn-ALCI, CQ) iff
• Πa∈S+(UT ,A, a) is Σ-safe, and
• Πa∈S+(UT ,A, a) ̸→Σ (UT ,A, b) for all b ∈ S-.
• (T ,A, S+,Σ) ∈ QDEF(Horn-ALCI, CQ) iff

Thus, the characterization is the same as in the database setting with IA replaced by UT ,A. Note that UT ,A is possibly infinite, so the product is, in contrast to the database case, not the witness. In fact, the proof for direction (⇐) merely shows that there is a witness, but in a non-constructive way based on the finite outdegree of UT ,A. Hence, Theorem 1 does not give immediate bounds on the size of witness queries.

In case of UCQs the additional expressive power leaves us with a simpler characterization, the product is compensated for by the use of disjunction in the query language and is thus not necessary anymore.

Theorem 2. For every Horn-ALCI KB (T ,A), all n-ary relations S+ and S- over ind(A), and signatures Σ, we have:

• (T ,A, S+, S-,Σ) ∈ QBE(Horn-ALCI,UCQ) iff (UT ,A, a) is Σ-safe and (UT ,A, a) ̸→Σ (UT ,A, b), for all a ∈ S+ and b ∈ S-.
• (T ,A, S+,Σ) ∈ QDEF(Horn-ALCI,UCQ) iff (UT ,A, a) is Σ-safe and (UT ,A, a) ̸→Σ (UT ,A, b) for all a ∈ S+ and b ∈ ind(A)n \ S+.

4 Complexity of QBE and QDEF

Based on the characterizations in Theorems 1 and 2, we now pinpoint the precise complexity for the introduced decision problems. We start with observing that Σ-safety (in both theorems) can be checked in exponential time by computing first UT ,A up to depth 1, computing the product (only in case of Theorem 1), and directly checking the condition.

Lemma 3. Σ-safety can be decided in EXPTIME.

For Conditions 2 and 2' of Theorem 1 it is sufficient to give an algorithm for deciding Πa∈S+(UT ,A, a) →Σ (UT ,A, b) for some b; this algorithm can also be used for the homomorphism checks in Theorem 2 by treating the elements a ∈ S+ individually. Note that there is no immediate decision procedure, as the involved interpretations UT ,A are typically infinite. We can, however, exploit regularity of UT ,A.

Let us fix an input (T , A, S+, S-, Σ) with k = |S+|, and denote with U k T ,A the product Πki=1UT ,A. Observe first that U k T ,A might be disconnected and that for our purposes it suffices to consider the substructure P of U k T ,A containing all elements from ind(A)k and everything that is reachable from there; thus, the domain ∆P of P is the smallest set such that:

• ind(A)k ⊆ ∆P , and whenever p ∈ ∆P and (p, p′ ) ∈ rU k T ,A or (p′ , p) ∈ rU k T ,A , then also p′ ∈ ∆P .

It is easy to show that for a∗ = Πa∈S+a, we have:

For what follows, it is convenient to characterize rP in terms of (tuples of) types, similar to the definition of UT ,A. For doing so, let TP be the set of all types for T and ∆ = ind(A) ∪ TP. Then define, for each role r, a binary relation ↪→T ,A r on∆k by taking c ↪→T ,A r d iff c = (c1, . . . , ck) and d = (d1, . . . , dk) and for each 1 ≤ i ≤ k we have:

• if ci, di ∈ ind(A), then r(ci, di) ∈ A or r-(di, ci) ∈ A;
• if ci ∈ ind(A), di ∈ TP, then ci ⇝T ,A r di;
• if ci, di ∈ TP, then ci ⇝Tr di or di ⇝Tr- ci.

For p = (π1, . . . , πk) ∈ ∆P , denote with tail(p) the tuple (tail(π1), . . . , tail(πn)). It should be clear that we have

• (p, p′ ) ∈ rP iff tail(p) ↪→T ,A r tail(p′ ).

We give a characterization for (P, a∗ )→Σ (UT ,A, b), which will be the basis of our decision procedure. Intuitively, we decompose P into the non-tree-shaped part with domain N = ind(A)k and the tree-shaped subinterpretations below each a ∈ N (which are characterized alone by their roots, similar to UT ,A). The latter have to be decomposed again because they might be mapped to different parts of UT ,A. We denote with Pc for c ∈ ∆k the sub-interpretation of P rooted at some c. Moreover, we use the notation UT ,t for a type t for T as an abbreviation for UT ,{A(at)|A∈t} and denote with at its root. Given some Σ-role r, a tuple c ∈ ∆k , a set T ⊆ ∆k , and a type t ∈ TP, we write (r, c, T, t) ∈ PHom, for partial homomorphism, if there is a partial function g : ∆Pc → ∆UT ,t satisfying the following conditions:

• g is a homomorphism on its domain;
• g(c) = π for some π = atrt′ ∈ ∆UT ,t ;
• if g(p) is defined and (p, p′ ) ∈ sPc for a Σ-role s, then either g(p) = at and tail(p) ∈ T or g(p′ ) is defined.

Intuitively, (r, c, T, t) belongs to PHom if there is a homomorphism from Pc to the subtree rooted at some r-successor of the root at of UT ,t given that some parts of Pc can be 'delayed' to T when they map to at. The component T is necessary because of the 'bidirectional nature' of Horn-ALCI. In general, a homomorphism (P, a∗ ) →Σ (UT ,A, b) does not map subtrees of P to subtrees in UT ,A, and T is used to synchronize between different subtrees of UT ,A, see the characterization below. For c ∈ ∆k , t ∈ TP we write c →Σ t if there is a Σ-homomorphism from an element of type c to an element of type t. We further denote with tpUT ,A (π) the type of π in UT ,A and with P|N the restriction of P to domain N. We establish the following characterization.

Lemma 5. (P, a∗ ) →Σ (UT ,A, b) iff there is a Σhomomorphism h : (P|N, a∗ ) →Σ (UT ,A, b) and a labeling T (π) ⊆ ∆k for every π ∈ range(h) ∪ ind(A) such that:

1. for every p ∈ N, we have p ∈ T(h(p));
2. for every c ∈ T(π), we have c →Σ tpUT ,A (π);
3. for every π ∈ range(h) ∪ ind(A), every c ∈ T(π), and every d with c ↪→T ,A r d one of the following is true:
4. (a) there is some π′ ∈ range(h) ∪ ind(A) such that (π, π′ ) ∈ rUT ,A and d ∈ T (π′ ), or
5. (b) (r, d, T(π), tpUT ,A (π)) ∈ PHom.

4.1 Horn-ALCI

We now devise a decision procedure for the criterion in Lemma 5. First observe that there are only double exponentially many mappings h and T , since a∗ is forced to be mapped to b, parts disconnected from a∗ can be neglected, and UT ,A has bounded outdegree. We can thus enumerate all possible such mappings. Conditions 1, 2, and 3(a) can be checked in double exponential time using straightforward algorithms. For Condition 3(b), we devise a mosaic-based decision procedure similar to an algorithm in [Jung et al., 2017].

A mosaic represents the neighborhood of an element in ∆UT ,A of some type t ∈ TP, together with 'types' of elements from ∆P which can be mapped there. Formally, a mosaic is a tuple M = (t, T, r0, t0, T0, . . . , rn, tn, Tn) with n ≤ |T |, t, ti ∈ TP, T, Ti ⊆ ∆k \ N, and ri Σ-roles such that:

• (i) t0 ⇝r0 t and t ⇝ri ti for all 1 ≤ i ≤ n;
• (ii) if t ⇝r t′ , there is an 1 ≤ i ≤ n with (ri, ti) = (r, t′ );
• (iii) t ∈ T implies t →Σ t;
• (iv) for every t ∈ T and every t ↪→T ,A r t′ for some Σ-role r, we either have r = r0 and t′ ∈ T0 or r = ri and t′ ∈ Ti, for some 1 ≤ i ≤ n.

Intuitively, t0 is the predecessor type of t and t1, . . . , tn are the successors via roles ri. Condition (iv) ensures that successors of types t ∈ T mapped to t can be mapped to either t0 or some ti. Given a set ˆ T ⊆ ∆k \ N, a root mosaic for ˆ T is a tuple M = (t, T, r0, t0, T0, . . . , rn, tn, Tn) satisfying (i)-(iii)

above, T0 = ∅, and the variant (iv') of (iv) which is obtained by replacing 't ∈ T ' with 't ∈ T \ ˆ T '.

We define a mosaic elimination procedure as follows. Define a sequence of sets of mosaics by starting with M0 as the set of all mosaics and root mosaics, and obtain Mi+1 from Mi by removing all (root) mosaics M = (t, T, r0, t0, T0, . . . , rn, tn, Tn) fromMi violating the following compatibility condition:

• (E) for every 1 ≤ j ≤ n, there is an M ′ = (t′ , T ′ , r′0 , t′0 , T ′0 , . . . , r′m, t′m, T ′m) ∈ Mi such that t = t′0 , rj = r′0 , tj = t′ , T ′0 ⊆ T, and Tj ⊆ T ′ .

Let ˆMbe where the sequenceM0 ⊇M1 ⊇ . . . stabilizes.

Lemma 6. (ˆ r, ˆt, ˆ T, ˆ t) ∈ PHom iff ˆMcontains a root mosaic M = (t, T, r0, t0, T0, . . . , rn, tn, Tn) for ˆ T with t = ˆ t and a mosaic M ′ = (t′ , T ′ , r′0 , t′0 , T ′0 , . . . , r′m, t′m, T ′m) with ˆt ∈ T ′ and r0 = ˆ r such that t = t′0 , ri = r′0 , ti = t′ , T ′0 ⊆ T, and Ti ⊆ T ′ for some i.

It remains to discuss the running time of our procedure. The set ∆ has size |A| + 2|T | , thus ∆k is of size NA,T ,k := (|A| + 2|T | )k . Hence, the number of mosaics is bounded by 2NA,T ,k . In each round of the elimination procedure at least one mosaic is removed, thus the procedure terminates after double exponentially many steps. Finally, the checks in (E) can be implemented in exponential time. We thus conclude:

We show next a matching lower bound.

Lemma 8. For L = ELI and Q ∈ {CQ, UCQ}, QBE(L,Q) and QDEF(L, Q) are 2-EXPTIME-hard.

We reduce the word problem for exponential space bounded alternating Turing machines (ATM) which is 2-EXPTIMEhard [Chandra et al., 1981]. Given an ATM M and a word w, we construct a TBox T such that M accepts w iff (UT ,A, a) →Σ (UT ,A, b) for A = {A(a),B(b)} and some signature Σ. We assume without loss of generality that instead of halting in the accepting state, M enters an infinite loop of special states without changing the tape anymore. We sketch the main idea by describing the universal model.

Below a, T enforces the infinite tree that is obtained by repeatedly glueing the pattern in Figure 1(a) to its leaves (as indicated by ◦; only Σ-symbols depicted). Note that this pattern (without the outgoing path labeled with α0, α1) is in fact the basic one of a computation tree of an ATM: a universal configuration of length 2n (labeled with U) followed by a branch into two existential configurations of the same length (labeled with E1, E2). We call this the skeleton tree. Apart from the skeleton tree, for every possible choice of α0, α1, a path of the shape depicted in the right starts from every node of the tree. There, α0 and α1 range over all possible triples containing the content of three consecutive tape cells, e.g., 〈a, b, c〉 or 〈a, (q, b), c〉.

Below b, T enforces an infinite tree as illustrated in Figure 1(b), having the following properties:

• It starts with a path of length 2n labeled with the initial configuration, encoded using triples.
• All other nodes are labeled with a pair β = (α, α′ ) with α, α′ triples as described above. In this case, α (resp., α′ ) is intended to represent the content of the tape cell in the current (resp., previous) configuration.
• Every path of length 2n (between Ex and U or U and Ex), e.g., β0, . . . , β2n-1 in Figure 1, corresponds to the description of a valid configuration of M, and a possible predecessor configuration.
• This is continued infinitely, always switching between universal and existential configurations, as depicted.

It is instructive to consider some homomorphism h0 of the skeleton tree below a into the tree below b. Informally, h0 can be thought of as a labeling of the skeleton (and thus of the computation tree) with actual configurations. It remains to ensure that the transition relation of M is obeyed, which is done as follows. Every node in the tree below b has also outgoing paths of the same shape as the one depicted in the left side (for the sake of clarity and space they are not depicted in Fig. 1). However, it has only such paths for every α, α′ except the label β = α0, α1 at the current node. Let now v be a node in the skeleton tree and assume its image v′ = h0(v) has label β = (α, α′ ). Clearly, h0 can be extended for all outgoing paths except the one labeled with α0 = α and α1 = α′ . Additionally, by construction, the end of this path can only be mapped to the corresponding cell in the previous configuration. The homomorphism condition ensures that the computation tree obeys the transition relation.

Summarizing, from Lemma 8 and Corollary 7 we obtain: Theorem 9. For L = Horn-ALCI and Q ∈ {CQ,UCQ}, QBE(L, Q) and QDEF(L, Q) are 2-EXPTIME-complete.

We remark that the hardness proof crucially relies on Σ. For CQs, it is adapted to the unrestricted signature case by adding an assertion A′ (a′ ) to the ABox, and enforcing below a′ a tree identical (up to Σ-homomorphisms) to the tree below a, by using fresh copies of non-Σ concept names. The product of the trees below a and a′ is then as in the proof of Lemma 8.

This approach does not apply to UCQs. In fact, the problem becomes easier with unrestricted signature. To see the reason for this complexity drop, note that, for a TBox T in normal form, we have (UT ,A, a) → (UT ,A, b) iff (UT ,A|ind(A), a) → (UT ,A, b). This can be straightforwardly decided in exponential time, see the appendix.

Theorem 10. For L = Horn-ALCI, QBEf(L,UCQ) and QDEFf (L, UCQ) are EXPTIME-complete.

4.2 Horn-ALC

For Horn-ALC, note that the characterizations in Theorems 1 and 2 and Lemma 5 are still valid since Horn-ALC is a fragment of Horn-ALCI. However, the absence of inverse roles simplifies the decision procedure of PHom which is the bottleneck for Horn-ALCI. Indeed, both Pc and the anonymous parts of UT ,t are directed regular trees where all roles point away from the root, so the set T can be ignored and we can decide PHom by applying standard techniques for regular trees.

Lemma 11. Given (T ,A, S+, S-,Σ) with (T ,A) a HornALC KB, the relation PHom can be decided in EXPTIME.

Applying this Lemma, we obtain a CONEXPTIME upper bound for deciding QBE from the algorithm devised in the previous section. A matching lower bound is inherited from the database setting [ten Cate and Dalmau, 2015]. For UCQs, a careful analysis of Lemma 5 yields an EXPTIME upper bound; the matching lower bound is obtained by a reduction from subsumption in Horn-ALC [Kr¨otzsch et al., 2013].

Theorem 12. For L = Horn-ALC, QBE(L, Q) and QDEF(L,Q) are CONEXPTIME-complete if Q = CQ and EXPTIME-complete if Q = UCQ. All results also hold with unrestricted signature.

5 Size of Witness Queries

We finally investigate the size of witness queries. We first establish the following double exponential lower bound.

Lemma 13. There is a family of Horn-ALC knowledge bases (Tn, An)n≥1, sets of examples S+ and S-, a signature Σ, and a polynomial p(n) such that, for all n ≥ 1, |Tn ∪An| ≤ p(n), (Tn, An, S+, S-, Σ) ∈ QBE(Horn-ALC, (U)CQ) and every (U)CQ witnessing this is of size Ω(22n ).

The main idea for the lower bound is to give Horn-ALC knowledge bases (Tn,An) over two individuals a, b such that in UTn,An the trees below a and b are Σ-homomorphically equivalent to I2n and J2n, respectively, where In, Jn are given by the following recursive 'definitions':

It can be shown that (In, a) ̸→Σ (Jn, b), but that (I ′ , a) →Σ (Jn, b) for any sub-interpretation I ′ of In. Thus, the smallest Σ-(U)CQ distinguishing between a and b in (Tn,An) is (I2n , a) viewed as CQ, whose size is Ω(22n ).

For Horn-ALC, a matching upper bound is obtained by an analysis of Lemma 5 and the observations made in the previous Section. For Horn-ALCI, we obtain a four-fold exponential upper bound on the size of the witness query by viewing the check for PHom as a reachability game on pushdown systems and apply known results from there [Kupferman et al., 2010; Carayol and Hague, 2014]. We leave the exact sizes for future work.

Theorem 14. If (T ,A, S+, S-,Σ) ∈ QBE(L, CQ), there is a witness query of at most double (resp., four-fold) exponential size if L = Horn-ALC (resp., L = Horn-ALCI).

6 Discussion and FutureWork

Our investigation opens a new whole research avenue towards improving the usability of ontology-enriched systems. From the theoretical perspective, the most natural next step is to broaden our understanding to different ontology and query languages. Given the state of the art of OES, we are particularly interested in 'lightweight' DLs, such as DL-Lite and EL; our results already provide a solid basis for these logics. For non-Horn or Datalog± ontologies it will be more challenging - a good starting point for non-Horn DLs might be [Botoeva et al., 2016b]. As for the query language, we will study regular path queries. From the practical perspective, it suggests itself to develop systems for QBE over KBs which not only implement reverse-engineering algorithms, but also allow interaction with the user, as done e.g., in [Bonifati et al., 2014; Diaz et al., 2016]. Given the high complexity of QBE, it will be also important to design heuristics [Tran et al., 2014; Mottin et al., 2016] or approximations [Barcel´o and Romero, 2017], as for relational databases. We note that some approximations considered by Barcel´o and Romero [2017] do not directly lead to better complexity in the context of OES. For example, 2-EXPTIME-hardness in Lemma 8 already holds for tree-shaped CQs. Another possible approximation is bounding the size of the witness queries.

Related within DL research is the study of query conservative extensions (QCE), where the question is whether two given ontologies or two knowledge bases can be distinguished by a query (without providing examples). Indeed, in the context of QCE, characterizations based on homomorphisms and universal models have been devised and inverse roles also tend to increase the complexity, see [Botoeva et al., 2016a] for a recent survey, and references therein. We are, however, not aware of any direct reductions between QBE and QCE.

Within the broader context of machine learning, we believe that our results lay the foundations for questions related to learnability of queries, see [Cohen and Page, 1995] for an overview. In this line, one could investigate an ILP inspired variant: if an instance (T ,A, S+, S-,Σ) of QBE does not have a witness, is there an extension T ′ ⊇ T such that there is a witness? In the context of active learning, one would be interested in learning a (conjunctive) query with membership and/or equivalence queries over a DL knowledge base. Finally, it would be interesting to extend the recently introduced framework of learning concepts over background structures of small degree and having only local access to the data [Grohe and Ritzert, 2017] with an ontology.

Acknowledgments

The authors were funded by EU's Horizon 2020 programme under the Marie Skłodowska-Curie grant 663830, the Research Foundation - Flanders project G.0428.15, and ERC consolidator grant 647289 CODA, respectively.