From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying

1 Introduction

An ontology-mediated query (OMQ) is a database-style query enriched with an ontology that contains domain knowledge, aiming to deliver more complete answers [Calvanese et al., 2009; Bienvenu et al., 2014; Bienvenu and Ortiz, 2015]. In OMQs, ontologies are often formulated in a description logic (DL) and query languages of interest include conjunctive queries (CQs), unions of conjunctive queries (UCQs), and instance queries (IQs). While CQs and UCQs are widely known query languages that play a fundamental role also in database systems and theory, IQs are more closely linked to DLs. In fact, an IQ takes the form C(x) with C a concept formulated in the DL that is also used for the ontology, and thus the expressive power of IQs depends on the ontology language. OMQs based on (U)CQs are more powerful than OMQs based on IQs as the latter only serve to return all objects from the data that are instances of a given class.

It is easy to see that IQs can express tree-shaped CQs with a single answer variable as well as unions thereof. In fact, this observation has been used in many technical constructions in the area, see for example [Calvanese et al., 1998; Glimm et al., 2008; Lutz, 2008; Eiter et al., 2012a]. Intriguingly, though, it was observed by Zolin [2007] that treeshaped CQs are not the limit of IQ-rewritability when we have an expressive DL such as ALC or ALCI at our disposal. For example, the CQ r(x, x), which asks to return all objects from the data that are involved in a reflexive r-loop, can be rewritten into the equivalent ALC-IQ P → ∃r.P(x). Here, P behaves like a monadic second-order variable due to the open-world assumption made for OMQs: we are free to interpret P in any possible way and when making P true at an object we are forced to make also ∃r.P true if and only if the object is involved in a reflexive r-loop. It is an interesting question, raised in [Zolin, 2007; Kikot and Zolin, 2013; Kikot et al., 2013], to precisely characterize the class of CQs that are rewritable into IQs. An important step into this direction has been made by Kikot and Zolin [2013] who identify a large class of CQs that are rewritable into IQs: a CQ is rewritable into an ALCI-IQ if it is connected and every cycle passes through the (only) answer variable; for rewritability into an ALC-IQ, one additionally requires that all variables are reachable from the answer variable in a directed sense. It remained open whether these classes are depleting, that is, whether they capture all CQs that are IQ-rewritable.

There are two additional motivations to study the stated question. The first one comes from concerns about the practical implementation of OMQs. When the ontology is formulated in a more inexpressive 'Horn DL', OMQ evaluation is possible in PTIME data complexity and a host of techniques for practically efficient OMQ evaluation is available, see for example [P´erez-Urbina et al., 2010; Eiter et al., 2012b; Trivela et al., 2015; Lutz et al., 2009]. In the case of expressive DLs such as ALC and ALCI, OMQ evaluation is CONP-complete in data complexity and efficient implementation is much more challenging. In particular, there are hardly any systems that fully support such OMQs when the actual queries are (U)CQs. In contrast, the evaluation of OMQs based on (expressive DLs and) IQs is supported by several systems such as Pellet, Hermit, and PAGOdA [Sirin et al., 2007; Glimm et al., 2014; Zhou et al., 2015]. For this reason, rewriting (U)CQs into IQs has been advocated in [Zolin, 2007; Kikot and Zolin, 2013; Kikot et al., 2013] as an approach towards efficient OMQ evaluation with expressive DLs and (U)CQs. The experiments and optimizations reported in [Kikot et al., 2013] show the potential (and challenges) of this approach.

The second motivation stems from the connection between OMQs and constraint satisfaction problems (CSPs) [Bienvenu et al., 2014; Lutz and Wolter, 2017]. Let (L,Q) denote the class of OMQs based on ontologies formulated in the DL L and the query language Q. It was observed in [Bienvenu et al., 2014] that (ALCI, IQ) is closely related to the complement of CSPs while (ALCI,UCQ) is closely related to the complement of the logical generalization MMSNP of CSP; we further remark that MMSNP is a notational variant of the complement of (Boolean) monadic disjunctive Datalog. Thus, characterizing OMQs from (ALCI, UCQ) that are rewritable into (ALCI, IQ) is related to characterizing MMSNP sentences that are equivalent to a CSP, and we also study the latter problem. In fact, the main differences to the OMQ case are that unary queries are replaced with Boolean ones and that predicates can have unrestricted arity.

The main aim of this paper is to study the rewritability of OMQs from (L, (U)CQ) into OMQs from (L, IQ), considering as L the basic expressive DL ALC as well as extensions of ALC with inverse roles, role hierarchies, the universal role, and functional roles. We provide precise characterizations, tight complexity bounds for deciding whether a given OMQ is rewritable, and show how to construct the rewritten query when it exists. In fact, we prove that the classes of CQs from [Kikot and Zolin, 2013] are depleting, but we go significantly beyond that: while [Zolin, 2007; Kikot and Zolin, 2013; Kikot et al., 2013] aim to find IQ-rewritings that work for any ontology, we consider the more fine-grained question of rewriting into an IQ an OMQ (T ,Σ, q(x)) where T is a DL TBox formalizing the ontology, Σ is an ABox signature, and q(x) is the actual query. The 'any ontology' setup then corresponds to the special case where T is empty and Σ is full. However, gaving a non-empty TBox or a non-full ABox signature results in additional (U)CQs to become rewritable. While we admit modification of the TBox during rewriting, it turns out that this is mostly unnecessary: only in some rather special cases, a moderate extension of the TBox pays off. All this requires non-trivial generalizations of the query classes and IQ-constructions from [Kikot and Zolin, 2013]. Our completeness proofs involve techniques that stem from the connection between OMQs and CSP such as a lemma about ABoxes of high girth due to Feder and Vardi [1998]. The rewritings we construct are of polynomial size when we work with the empty TBox, but can otherwise become exponential in size.

Regarding IQ-rewritability as a decision problem, we show NP-completeness for the case of the empty TBox. This can be viewed as an underapproximation for the case with non-empty TBox and ABox signature. With non-empty TBoxes, complexities are higher. When the ABox signature is full, we obtain 2EXPTIME-completeness for DLs with inverse roles and an EXPTIME lower bound and a CONEXPTIME upper bound for DLs without inverse roles. With unrestricted ABox signature, the problem is 2NEXPTIMEcomplete for DLs with inverse roles and NEXPTIME-hard (and in 2NEXPTIME) for DLs without inverse roles. All lower bounds hold for CQs and all upper bounds capture UCQs. We also prove that it is 2NEXPTIME-complete to decide whether a given MMSNP sentence is equivalent to a CSP. This problem was known to be decidable [Madelaine and Stewart, 2007], but the complexity was open.

We also consider ALCIF, the extension of ALCI with functional roles, for which IQ-rewritability turns out to be undecidable and much harder to characterize. We give a rather subtle characterization for the case of the empty TBox and full ABox signature and show that the decision problem is then decidable and NP-complete. Since it is not clear how to apply CSP techniques, we use an approach based on ultrafilters, starting from what was done for ALC without functional roles in [Kikot and Zolin, 2013].

Full proofs are in the appendix, available at http://www. informatik.uni-bremen.de/tdki/research/papers.html.

2 Preliminaries

We use standard description logic notation and refer to [Baader et al., 2017] for full details. In contrast to the standard DL literature, we carefully distinguish between the concept language and the TBox language. We consider four concept languages. Recall that ALC-concepts are formed according to the syntax rule

where A ranges over concept names and r over role names. As usual, we use C → D as an abbreviation for ¬C ⊔ D. ALCI-concepts additionally admit the use of inverse roles r- in concept constructors ∃r-.C and ∀r-.C. With a role, we mean a role name or an inverse role. ALC u -concepts additionally admit the use of the universal role u in concept constructors ∃u.C and ∀u.C. In ALCI u -concepts, both inverse roles and the universal role are admitted.

We now introduce several TBox languages. For L one of the four concept languages introduced above, an L-TBox is a finite set of concept inclusions C ⊑ D where C and D are L concepts. So each concept language also serves as a TBox language, but there are additional TBox languages of interest. We include the letter H in the name of a TBox language to indicate that role inclusions r ⊑ s are also admitted in the TBox and likewise for the letter F and functionality assertions func(r) where in both cases r, s are role names or inverse roles in case that the concept language used admits inverse roles. So it should be understood, for example, what we mean with an ALCHI u -TBox and an ALCFI-TBox. As usual, the semantics is defined in terms of interpretations, which take the form I = (∆I , ·I ) with ∆I a non-empty domain and ·I an interpretation function. An interpretation is a model of a TBox T if it satisfies all inclusions and assertions in T , defined in the usual way. We write T |= r ⊑ s if every model of T also satisfies the role inclusion r ⊑ s.

An ABox is a set of concept assertions A(a) and role assertions r(a, b) where A is a concept name, r a role name, and a, b are individual names. We use ind(A) to denote the set of all individual names that occur in A. An interpretation is a model of an ABox A if it satisfies all concept and role assertions in A, that is, a ∈ AI when A(a) is in A and (a, b) ∈ rI when r(a, b) is in A. An ABox is consistent with a TBox T if A and T have a common model. A signature Σ is a set of concept and role names. We use sig(T ) to denote the set of concept and role names that occur in the TBox T , and likewise for other syntactic objects such as ABoxes. A Σ-ABox is an ABox A such that sig(A) ⊆ Σ.

A conjunctive query (CQ) is 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(x) or r(x, y) with A a concept name, r a role name, and x, y ∈ x ∪ y. We call x the answer variables of q(x) and y quantified variables. For purposes of uniformity, we use r-(x, y) as an alternative notation to denote an atom r(y, x) in a CQ. In fact, when speaking about an atom r(x, y) in a CQ q(x), we generally also include the case that r = s- and s(y, x) is the actual atom in q(x), unless explicitly noted otherwise. Every CQ q(x) = ∃yϕ(x, y) gives raise to a directed graph Gq whose nodes are the elements of x ∪ y and that contains an edge from x to y if ϕ(x, y) contains an atom r(x, y). The corresponding undirected graph is denoted Guq (it might contain self loops). We can thus use standard terminology from graph theory to CQs, saying for example that a CQ is connected. A homomorphism from q(x) to an interpretation I is a function h : x∪y →∆I such that h(x) ∈ AI for every atomA(x) of q(x) and (h(x), h(y)) ∈ rI for every atom r(x, y) of q(x). We write I |= q(a) and call a an answer to q(x) on I if there is a homomorphism from q(x) to I with h(x) = a.

A union of conjunctive queries (UCQ) q(x) is a disjunction of one or more CQs that all have the same answer variables x. We say that a UCQ is connected if every CQ in it is. The arity of a (U)CQ is the number of answer variables in it. For L ∈ {ALC,ALCI,ALC u ,ALCI u }, an L-instance query (L-IQ) takes the form C(x) where C is an L concept and x a variable. We write I |= C(a) if a ∈ C I . All instance queries have arity 1.

An ontology-mediated query (OMQ) takes the form Q = (T , Σ, q(x)) with T a TBox, Σ ⊆ sig(T ) ∪ sig(q) an ABox signature, and q(x) a query. 1 The arity of Q is the arity of q(x) and Q is Boolean if it has arity zero. When Σ is sig(T )∪ sig(q), then for brevity we denote it with Σfull and speak of the full ABox signature. Let A be a Σ-ABox. A tuple a ∈ ind(A) is an answer to Q on A if I |= q(a) for all models I of A and T . We say that Q is empty if for all Σ-ABoxes A, there is no answer to Q on A. Let Q1,Q2 be OMQs, Qi = (Ti,Σ, qi(x)) for i ∈ {1, 2}. Then Q1 is contained in Q2, written Q1 ⊆ Q2, if for all Σ-ABoxes A, every answer to Q1 on A is also an answer to Q2 on A. Further, Q1 and Q2 are equivalent, written Q1 ≡ Q2, if Q1 ⊆ Q2 and Q2 ⊆ Q1.

We use (L,Q) to refer to the OMQ language in which the TBox is formulated in the language L and where the actual queries are from the language Q, such as in (ALCF,UCQ). For brevity, we generally write (L, IQ) instead of (L, L′ -IQ) when L′ is the concept language underlying the TBox language L, so for example (ALCHI, IQ) is short for (ALCHI , ALCI-IQ).

Definition 1. Let (L,Q) be an OMQ language. An OMQ Q = (T , Σ, q(x)) is (L, Q)-rewritable if there is an OMQ Q′ from (L, Q) such that the answers to Q and to Q′ are identical on any Σ-ABox that is consistent with T . In this case, we say that Q is rewritable into Q′ and call Q′ a rewriting of Q.

Let (L,Q) be an OMQ-language. IQ-rewritability in (L, Q) is the problem to decide whether a given (unary) OMQ Q = (T ,Σ, q(x)) from (L,Q) is (L, IQ)-rewritable; for brevity, we simply speak of IQ-rewritability of Q when this is the case. The following examples show that IQ-rewritability of Q depends on several factors. All claims made are sanctioned by results established in this paper.

Example 2. (1) IQ-rewritability depends on the topology of the actual query. Let q1(x) = r(x, x). The OMQ

1 The requirement Σ ⊆ sig(T )∪sig(q) is harmless since symbols in the ABox that are not from sig(T )∪sig(q) do not affect answers.

• (∅,Σfull, q1(x)) is rewritable into the OMQ (∅,Σfull,C(x)) from (ALC, IQ) where C is P → ∃r.P. In contrast, let q2(x) = ∃y s(x, y) ∧ r(y, y). The OMQ (∅,Σfull, q2(x)) is not rewritable into an OMQ from (ALCI, IQ).
• If we are not allowed to extend the TBox, IQrewritability depends on whether or not inverse roles are available. Let Σ = {r, s} and q(x) = ∃y r(y, x) ∧ s(y, x). The OMQ Q = (∅,Σ, q(x)) is rewritable into the OMQ (∅, Σ, C(x)) from (ALCI, IQ) where C is P → ∃r-.∃s.P. Q is also rewritable into the OMQ (T ,Σ,C ′ (x)) from (ALC, IQ) where T = {∃s.P ⊑ ∀r.P ′ }, and C is P → P ′ , but it is not rewritable into any OMQ (T ,Σ,C ′′ (x)) from (ALC, IQ) with T = ∅.
• IQ-rewritability depends on the TBox. Let q(x) = ∃x1∃y1∃y2∃zA(x) ∧ r(x, x1) ∧ r(x1, y1) ∧ r(x1, y2) ∧ r(y1, z) ∧ r(y2, z) ∧ B1(y1) ∧ B2(y2). The OMQ (∅,Σfull, q(x)) is not rewritable into an OMQ from (ALCI, IQ). Let T = {A ⊑ ∃r.∃r.(B1 ⊓ B2 ⊓ ∃r.⊤)}. The OMQ (T ,Σfull, q(x)) is rewritable into the OMQ (T , Σfull, A(x)) from (ALC, IQ).
• IQ-rewritability depends on the ABox signature. Let q(x) be the CQ from (3) without the atom A(x) and let T be as in (3). The OMQ (T ,Σfull, q(x)) is not rewritable into an OMQ from (ALCI, IQ). Let Σ = {A}. The OMQ (T ,Σ, q(x)) is rewritable into the OMQ (T ,Σ,A(x)) from (ALC, IQ).

Note that we are allowed to completely rewrite the TBox when constructing IQ-rewritings, which might seem questionable from a practical perspective. Fortunately, though, it turns out the TBox can always be left untouched or, in some rare cases, only needs to be slightly extended. Also note that an alternative definition of IQ-rewritability obtained by dropping the restriction to ABoxes consistent with T in Definition 1. All results obtained in this paper hold under both definitions. We comment on this throughout the paper and refer to the alternative version as unrestricted IQ-rewritability.

3 Characterizations

We aim to provide characterizations of OMQs that are IQrewritable. On the one hand, these characterizations clarify which OMQs are IQ-rewritable and which are not. On the other hand, they form the basis for deciding IQ-rewritability. We first concentrate on the case of DLs (and IQs) with inverse roles and then move on to DLs without inverse roles. In the final part of this section, we consider the case where the TBox is empty, both with and without inverse roles.

3.1 The CaseWith Inverse Roles

To state the characterization, we need some preliminaries. Let q(x) be a CQ. A cycle in q(x) is a sequence of non-identical atoms r0(x0, x1), . . . , rn-1(xn-1, xn) in q(x), n ≥ 1, where 2

1. r0, . . . , rn-1 are (potentially inverse) roles,
2. xi ̸= xj for 0 ≤ i < j < n, and x0 = xn.

2 We require the atoms be non-identical to prevent r(x0, x1), r-(x1, x0) from being a cycle (both atoms are identical).

The length of this cycle is n. We say that q(x) is x-acyclic if every cycle in it passes through x and use qcon (x) to denote the result of restricting q(x) to those atoms that only use variables reachable in Guq from x. Both notions are lifted to UCQs by applying them to every CQ in the UCQ. A contraction of q(x) is a CQ obtained from q(x) by zero or more variable identifications, where the identification of x with any other variable yields x.

Let T be an ALCHI u -TBox and q(x) a UCQ. We use qacyc(x) to denote the UCQ that consists of all x-acyclic CQs obtained by starting with a contraction of a CQ from q(x) and then replacing zero or more atoms r(y, z) with s(y, z) when T |= s ⊑ r. We write qcon acyc (x) to denote (qacyc)con (x).

Theorem 3. Let L ∈ {ALCI,ALCHI} and let Q = (T ,Σ, q(x)) be a unary OMQ from (L,UCQ) that is nonempty. Then the following are equivalent:

1. Q is IQ-rewritable, that is, it is rewritable into an OMQ Q′ = (T ′ , Σ, C(x)) from (L, IQ);
2. Q is rewritable into an OMQ Q′ = (T ,Σ,C(x)) from (L, IQ);
3. Q ≡ (T ,Σ, qcon acyc (x)).

When L is replaced with Lu , then the same equivalences hold except that qcon acyc is replaced with qacyc.

Note that Theorem 3 excludes empty OMQs, but these are trivially IQ-rewritable. It implies that, in the considered cases, it is never necessary to modify the TBox when constructing an IQ-rewriting. Further, it emerges from the proof that it is never necessary to introduce fresh role names in the rewriting (while fresh concept names are crucial). Theorem 3 also applies to unrestricted IQ-rewritability (where also ABoxes are admitted that are inconsistent with the TBox from the OMQ): unrestricted IQ-rewritability trivially implies IQrewritability and the converse is an easy consequence of the fact that every OMQ that is IQ-rewritable has an IQ-rewriting based on the same TBox.

We now give some ideas about the proof of Theorem 3. The most interesting implication is "1 ⇒ 3". A central step is to show that if Q = (T ,Σ, q(x)) is IQ-rewritable into an OMQ Q′ , then Q ⊆ Qacyc := (T ,Σ, qacyc(x)), that is, when A |= Q(a) for some Σ-ABox A, then A |= Qacyc(a). To this end, we first construct from A a Σ-ABox Ag of high girth (that is, without small cycles) in a way such that (a) Ag homomorphically maps to A and (b) from A |= Q′ (a) it follows that Ag |= Q′ (a), thus Ag |= Q(a). Due to the high girth of Ag and exploiting (a variation of the) tree model property for ALCHI, we can then show that Ag |= Q(a) implies Ag |= Qacyc(a). Because of (a), it follows that A |= Qacyc(a). In the direction "3 ⇒ 2", we construct actual rewritings, based on the following lemma, an extension of a result of Kikot and Zolin [Kikot and Zolin, 2013] with TBoxes and ABox signatures (and UCQs instead of CQs).

Lemma 4. Let Q = (T ,Σ, q(x)) be an OMQ from (ALCHI u ,UCQ). Then

1. if q(x) is x-acyclic and connected, then Q is rewritable into an OMQ (T , Σ, C(x)) with C(x) an ALCI-IQ and
2. if q(x) is x-acyclic, then Q is rewritable into an OMQ (T , Σ, C(x)) with C(x) an ALCI u -IQ.

The size of the IQs C(x) is polynomial in the size of q(x).

We give the construction of the ALCI-IQ q′ (x) in Point 1 of Lemma 4. Let Q = (T ,Σ, q(x)) be an OMQ from (ALCHI u ,UCQ) with q(x) x-acyclic and connected. To construct q′ (x), we first construct for each CQ p(x) in q(x) an ELI-concept Cp, that is, an ALCI-concept that uses only the constructors ⊓, ∃r.C, and ∃r-.C. In fact, since p(x) is xacyclic and connected, we can repeatedly choose and remove atoms of the form r(x, y) that occur in a cycle in p(x) and will eventually end up with a tree-shaped CQ p′ (x). 3 Here, treeshaped means that the undirected graph Gup′ is a tree and that there are no multi-edges, that is, if r(y, z) is an atom, then there is no atom s(y, z) with s ̸= r. Next, extend p′ (x) to obtain another tree-shaped CQ p′′ (x) by taking a fresh concept name P /∈ Σ, and adding r(x′ , y) and P(x′ ) for each removed atom r(x, y), x′ a fresh variable. We can now view p′′ (x) as an ELI-concept Cp in the obvious way. The desired ALCI-IQ q′ (x) is (P → ⊔ p(x) a CQ in q(x) Cp)(x).

3.2 The CaseWithout Inverse Roles

We consider OMQs whose TBoxes are formulated in a DL L that does not admit inverse roles. Note that inverse roles are then also not admitted in the IQ used in the rewriting. We first observe that this has less impact than one might expect: inverse roles in the IQ-rewriting can be eliminated and in fact Points 1 and 3 from Theorem 3 are still equivalent. However, there is also a crucial difference: unless the universal role is present, the elimination of inverse roles requires an extension of the TBox and thus the equivalence of Points 1 and 2 of Theorem 3 fails. In fact, this is illustrated by Point (2) of Example 2. We thus additionally characterize IQ-rewritability without modifying the TBox. We also show that, with the universal role, it is not necessary to extend the TBox.

We start with some preliminaries. An extended conjunctive query (eCQ) is a CQ that also admits atoms of the form C(x), C a (potentially compound) concept, and UeCQs and extended ABoxes (eABoxes) are defined analogously. The semantics is defined in the expected way. Every eCQ q(x) gives rise to an eABox Aq by viewing the variables in q(x) as individual names and the atoms as assertions.

Let q(x) be an eCQ. We use dreach(q) to denote the set of all variables reachable from x in the directed graph Gq and say that q(x) is x-accessible if dreach(q) contains all variables. For V a set of variables from q(x) that includes x, q(x)|V denotes the restriction of q(x) to the atoms that use only variables from V .

Let T be an ALC-TBox. An eCQ p(x) is a T -decoration of a CQ q(x) if

1. p(x) is obtained from q(x) by adding, for each y ∈ dreach(q) and each subconcept C of T , the atom C(y) or the atom¬C(y);
2. the eABox Ap is consistent with T .

3 Note that x is the answer variable and recall that we might have r = s- and thus also choose atoms s(y, x).

For a UCQ q(x), we use qdeco (x) to denote the UeCQ that consists of all eCQs p(x)|dreach(p)(x), where p(x) is a T - decoration of a CQ from q(x). We write qdeco acyc (x) to denote (qacyc)deco (x). We now give the results announced above.

Theorem 5. Let L ∈ {ALC,ALCH} and let Q = (T ,Σ, q(x)) be a unary OMQ from (L,UCQ) that is nonempty. Then the following are equivalent:

1. Q is rewritable into an OMQ from (L, IQ);
2. Q is rewritable into an OMQ (T ∪ T ′ ,Σ,C(x)) from (L, IQ);
3. Q is rewritable into an OMQ from (LI, IQ);
4. If Σ = Σfull, then the following are equivalent:
5. Q is rewritable into an OMQQ′ = (T , Σfull, C(x)) from (L, IQ);
6. Q ≡ (T , Σfull, qdeco acyc (x)).

If, furthermore, L is replaced with Lu and LI with LI u , then Conditions 1 to 3 are further equivalent to:

1. Q is rewritable into an OMQ Q′ = (T ,Σ,C(x)) from (Lu , IQ).

Characterizing IQ-rewritability in the case where L ∈ {ALC,ALCH}, the TBox (is non-empty and) cannot be extended, and Σ ̸= Σfull remains an open problem.

In the directions "3 ⇒ 2", "5 ⇒ 4", and "3 ⇒ 6", we have to construct IQ-rewritings. This is done by starting with the rewriting from the proof of Lemma 4 and then modifying it appropriately. As in the case of Theorem 3, it is straightforward to see that all results stated in Theorem 5 also apply to unrestricted IQ-rewritability.

3.3 The Case of Empty TBoxes

We consider OMQs in which the TBox is empty as an important special case. Since it is then not interesting to have an ABox signature, this corresponds to the rewritability of (U)CQs into L-instance queries, for some concept language L (and thus no OMQs are involved). The importance of this case is due to the fact that it provides an 'underapproximation' of the IQ-rewritability of OMQs, while also being easier to characterize and computationally simpler.

We say that an UCQ q(x) is L-IQ-rewritable if there is an L-IQ q′ (x) that is equivalent to q(x) in the sense that the OMQs (∅, Σfull, q(x)) and (∅, Σfull, q′ (x)) are equivalent (and in passing, we define the equivalence between two UCQs in exactly the same way). The following proposition makes precise what we mean by underapproximation.

Proposition 6. Let L ∈ {ALC,ALCI,ALC u ,ALCI u }. If a UCQ q(x) is L-IQ-rewritable, then so is any OMQ (T , Σ, q(x)) from (LH, UCQ).

Proposition 6 is essentially a corollary of Theorem 7 below. As illustrated by Case (3) of Example 2, its converse fails.

We now characterize IQ-rewritability in the case of the empty TBox. A subquery of a CQ q(x) is a CQ q′ (x) obtained from q(x) by dropping atoms. A subquery of a UCQ q(x) is a UCQ obtained by including as a CQ at most one subquery of each CQ in q(x).

Theorem 7. Let q(x) be a UCQ. Then

1. q(x) is rewritable into an ALCI-IQ iff there is a subquery q′ (x) of q(x) that is x-acyclic, connected, and equivalent to q(x);
2. q(x) is rewritable into anALC-IQ iff there is a subquery q′ (x) of q(x) that is x-acyclic, x-accessible, and equivalent to q(x).

When L-IQs are replaced with Lu -IQs, then the same equivalences hold except that connectedness/x-accessibility is dropped.

Note that Theorem 7 also characterizes rewritability of CQs; the query q′ (x) is then also a CQ rather than a UCQ. This is in contrast to Theorems 3 and 5 where the queries qcon acyc (x) and qdeco acyc (x) are UCQs even when the query q(x) from the OMQ that we start with is a CQ. Another crucial difference is that qcon acyc (x) and qdeco acyc (x) can be of size exponential in the size of the original OMQ while the query q′ (x) in Theorem 7 is of size polynomial in the size of q(x).

4 Complexity

We determine the complexity of deciding IQ-rewritability in various OMQ languages, based on the established characterizations and starting with the case of empty TBoxes.

Theorem 8. For every Q ∈ {CQ,UCQ} and L ∈ {ALC,ALCI,ALC u ,ALCI u }, it is NP-complete to decide whether a given query from Q is L-IQ-rewritable.

The upper bound in Theorem 8 is by guessing the query q′ (x) from Theorem 7 and verifying that it satisfies the properties stated there. The lower bound is by a reduction from 3-colorability.

We next consider the case where TBoxes can be nonempty, starting with the assumption that the ABox signature is full since this results in (slightly) lower complexity.

Theorem 9. Let Q ∈ {CQ, UCQ}. For OMQs based on the full ABox signature, IQ-rewritability is

1. EXPTIME-hard in (ALC,Q) and in CONEXPTIME in (ALCH, Q) and
2. 2EXPTIME-complete in (ALCI,Q) and (ALCHI,Q).

The lower bounds are by reduction from OMQ evaluation on ABoxes of the form {A(a)}, A a concept name, which is EXPTIME-complete in (ALCH, CQ) and 2EXPTIMEcomplete in (ALCHI, CQ) [Lutz, 2008]. The upper bounds are derived from the OMQ containment checks suggested by Condition 3 of Theorem 3 and Condition 4 of Theorem 5. Since we work with the full ABox signature, the nonemptiness condition from these theorems is void (there are no empty OMQs) and OMQ containment is closely related to OMQ evaluation, which allows us to derive upper bounds for the former from the latter; in fact, these bounds are exactly the ones stated in Theorem 9. We have to exercise some care, for two reasons: first, we admit UCQs as the actual query and thus the trivial reduction of OMQ containment to OMQ evaluation that is possible for CQs (which can be viewed as an ABox) does not apply. And second, we aim for upper bounds that exactly match the complexity of OMQ containment while the UCQs qcon acyc (x) and qdeco acyc (x) involved in the containment checks are of exponential size. What rescues us is that each of the CQs in these UCQs is only of polynomial size.

We finally consider the case where the ABox signature is unrestricted.

Theorem 10. IQ-rewritability is

1. NEXPTIME-hard in (ALC, CQ) and
2. 2NEXPTIME-complete in all of (ALCI, CQ), (ALCI,UCQ), (ALCHI, CQ), (ALCHI,UCQ).

The lower bound in Point 1 is by reduction from OMQ emptiness in (ALC, CQ), which is NEXPTIME-complete [Baader et al., 2016]. For the one in Point 2, we use a reduction from OMQ containment, which is 2NEXPTIMEcomplete in (ALCI, CQ) [Bourhis and Lutz, 2016]. The upper bounds are obtained by appropriate containment checks as suggested by our characterizations, and we again have to deal with UCQs with exponentially many CQs. Note that Theorem 10 leaves open the complexity of IQ-rewritability in (ALC, CQ), between NEXPTIME and 2NEXPTIME. The same gap exists for OMQ containment [Bourhis and Lutz, 2016] as well as in the related problems of FO-rewritability and Datalog-rewritability [Feier et al., 2017].

5 Functional Roles

We consider DLs with functional roles. A fundamental observation is that for the basic such DL ALCF, IQ-rewritability is undecidable. This can be proved by a reduction from OMQ emptiness in (ALCF, IQ) [Baader et al., 2016].

Theorem 11. In (ALCF, CQ), IQ-rewritability is undecidable.

In the following, we show that decidability is regained in the case where the TBox is empty (apart from functionality assertions). This is challenging because functionality assertions have a strong and subtle impact on rewritability. As before, the only interesting ABox signature to be combined with 'empty' TBoxes is the full ABox signature. We use F to denote the TBox language in which TBoxes are sets of functionality assertions and concentrate on rewriting into IQs that may use inverse roles.

Example 12. Consider the CQ p(x) = ∃y(s(x, y) ∧ r(y, y)) from Point 1 of Example 2. Then Qs = (Ts,Σfull, p(x)) and Qr = (Tr,Σfull, p(x)) with Tw = {func(w)} for w ∈ {r, s} are both rewritable into an OMQ (Tw,Σfull, qw(x)) with qw(x) an ALCI-IQ. The rewritings are neither trivial to find nor entirely easy to understand. In fact, for qs(x) we can use ∀s.P → ∃s.(P → ∃r.P). For qr(x), we introduce three fresh concept names rather than a single one and use them in a way inspired by graph colorings:

Before giving a characterization of rewritable queries, we introduce some preliminaries. Let q(x) be a CQ and T an ALCIF-TBox. A sequence x0, . . . , xn of variables in q(x) is a functional path in q(x) from x0 to xn w.r.t. T if for all i < n there is a role r such that func(r) ∈ T and r(xi, xi+1) is in q(x). We say that q(x) is f-acyclic w.r.t. T if for every cycle r0(x0, x1), . . . , rn-1(xn-1, xn) in q(x), one of the following holds:

• there is a functional path in q(x) from x to some xi;
• func(ri) ∈ T or func(ri ) ∈ T for all i < n and there is a functional path y0, . . . , ym in q(x) with x0 = y0 = ym such that {x0, . . . , xn-1} ⊆ {y0, . . . , ym}.

We are now ready to state the characterization.

Theorem 13. An OMQ Q = (T , Σfull, q(x)) from (F, UCQ) is rewritable into an OMQ from (F,ALCI-IQ) iff there is a subquery q′ (x) of q(x) that is f-acyclic, connected, and equivalent to q(x).

When ALCI-IQ is replaced with ALCI u -IQ, the same equivalence holds except that connectedness is dropped.

The proof of Theorem 13 extends the ultrafilter construction from [Kikot and Zolin, 2013]. We remark that the "if" direction in Theorem 13 even holds for OMQs Q = (T ,Σ, q(x)) from (ALCIF,UCQ). Thus, the case of the 'empty' TBox can again be seen as an underapproximation of the general case. We further remark that T remains unchanged in the construction of the IQ-rewritings and that the constructed rewritings are of polynomial size.

Theorem 14. For OMQs from (F,UCQ), rewritability into (F,ALCI-IQ) is NP-complete.

6 MMSNP and CSP

Recall from the introduction that the OMQ languages studied in this paper are closely related to CSPs and their logical generalization MMSNP. In fact, the techniques used to establish the results in Sections 3 and 4 can be adapted to determine the complexity of deciding whether a given MMSNP sentence is equivalent to a CSP. In a nutshell, we prove that an MMSNP-sentence is equivalent to a CSP iff it is preserved under disjoint union and equivalent to a generalized CSP (a CSP with multiple templates), and that both properties can be reduced to containment between MMSNP sentences which is 2NEXPTIME-complete [Bourhis and Lutz, 2016]. The latter reduction involves constructing an MMSNP sentence ϕacyc that is reminiscent of the query qacyc in Theorem 3. Full details are given in the appendix.

Theorem 15. It is 2NEXPTIME-complete to decide whether a given MMSNP-sentence is equivalent to a CSP.

7 Conclusion

We have made a leap forward in understanding the relation between (U)CQs and IQs in ontology-mediated querying. Interesting open problems include a characterization of IQrewritability for DLs with functional roles when the TBox is non-empty and characterizations for DLs with transitive roles. The remarks after Theorem 4 and 10 mention further problems left open. In addition, it would be worthwhile to continue the effort from [Kikot et al., 2013] to understand the value of IQ-rewritings for the purposes of efficient practical implementation.

Acknowledgements

Cristina Feier and Carsten Lutz were supported by ERC Consolidator Grant 647289 CODA. Frank Wolter was supported by EPSRC UK grant EP/M012646/1.