The Combined Complexity of Reasoning with Closed Predicates in Description Logics

Abstract

We investigate the computational cost of combining the open and closed world assumptions in Description Logics. Unlike previous works, which have considered data complexity and focused mostly on lightweight DLs, we study combined complexity for a wide range of DLs, from lightweight to very expressive ones. From existing results for the standard setting, where all predicates are interpreted under the open world assumption, and the well-known relationship between closed predicates and concept constructors like disjunction and nominals, we infer bounds on the combined complexity of reasoning in the presence of closed predicates. We show that standard reasoning requires exponential time even for weak logics like E L, while answering conjunctive queries becomes hard at least for coNEXPTIME, and in most cases even for 2EXPTIME. An important stepping stone for our results, that is interesting on its own right, is to prove that conjunctive query answering in (plain) ALCO is hard for coNEXPTIME in combined complexity. This singles out nominals as a previously unidentified source of additional complexity when answering queries over expressive DLs.

-

As fragments of classical first-order predicate logic, description logics (DLs) have an open-world semantics. That is, knowledge bases (KBs) are interpreted as the set of all relational structures that satisfy what is explicitly stated in the KB, and where any statement whose truth is not directly implied by the knowledge base can be interpreted in an arbitrary way. However, this open-world view of DLs is not the most adequate in all cases, and in particular, when DLs are used to describe domain-specific knowledge to be leveraged when querying data sources, but the sources stem from traditional (closedworld) databases that fully describe the instances that are to be included in a relation. For example, when the students enrolled in some course are extracted from a database, this information should be considered complete, and query answering algorithms should exploit this to exclude irrelevant models and infer more query answers.

Combining open and closed world reasoning is not a new topic in DLs [ 3 ], but it has received renewed attention in recent years [ 20,19,7,30 ]. A prominent proposal for achieving partial closed world reasoning is to use DBoxes instead of ABoxes as the

This work has been supported by the Austrian Science Fund (FWF) projects T515 and P25207. assertional component of KBs [30]. Syntactically, a DBox looks just like an ABox, but semantically, it is interpreted like a database: the instances of the concepts and roles in the DBox are given exactly by the assertions it contains, and the unique name assumption is made for the active domain of the individuals occurring in it. We follow a recent generalization of this setting, where instead of replacing ABoxes by DBoxes, we enrich the terminological component of KBs with a set of concepts and roles that are to be interpreted as closed predicates [ 19 ]. In this way, some ABox assertions are interpreted under closed semantics, as in DBoxes, while others are considered open, as in ABoxes.

There are not many works studying the complexity of reasoning with closed predicates. For the DL-Lite family and for E L, the data complexity of ontology mediated query answering has been considered [ 7,19 ]. The authors of these works consider a conjunctive query together with a terminological component (a TBox and possibly a set of closed predicates), and study the complexity of answering such a query over an input data instance (an ABox or a DBox). Under the standard open-world semantics for all predicates, this is a central problem that has received great attention in the last decade in the DL community. Most research focuses on the cases where the problem is tractable, or even first-order rewritable. Unfortunately, the tractability of query answering is lost in the presence of DBoxes, even for the core fragments of DL-Lite and E L [ 7 ]. In a nutshell, closed predicates cause the convexity property to be lost, allowing a KB to entail a disjunction of facts without entailing any of the disjuncts. An in-depth analysis of this and a careful classification of tractable cases can be found in [ 19 ].

In this paper, we take a closer look at the computational complexity of reasoning in the presence of closed predicates. Unlike previous works, we consider the combined complexity of reasoning, that is, not only the data is considered as an input, but also the terminological information, and in the case of query answering, the query. Rather than focusing on a few lightweight DLs, we consider a range of logics including very expressive ones, and use existing results in the literature to infer many tight bounds on the computational complexity of query answering. It was shown already in [30] that closed predicates can be simulated, under the standard open world semantics, in any extension of ALC that supports nominals, and conversely, nominals can be simulated by closed predicates (the latter does not depend on any of the availability of any the constructs of ALC). It is also easy to show that closed predicates suffice to easily express full disjunction and atomic negation in any logic supporting qualified existential restrictions, hence adding closed predicates to plain E L already results in the full expressiveness of ALCO, and makes standard reasoning require exponential time in the worst case.

For query answering, we build on the reduction from ALC to E L to show that the constructors that make query answering 2EXPTIME-hard in extensions of ALC (namely inverses [ 17 ], or transitive roles together with role hierarchies [ 6 ]), have the same effect in the analogous extensions of E L in the presence of closed predicates (i.e., E LI and E LHtrans). However, since the precise complexity of query answering in ALCO remains open, we cannot infer tight bounds for the extensions of E L with closed predicates that do not support these additional constructs. This leads us to the main technical contribution of the paper: we show that conjunctive query answering over ALCO (with the standard open-world semantics) is coNEXPTIME-hard. Hence the same holds in the presence of closed predicates for E L and its extensions. Although we leave a matching upper bound open for future work, we exhibit nominals (or closed predicates) as a previously unidentified source of increased complexity for query answering in expressive DLs. 2

Preliminaries

We assume the reader is familiar with DLs and, in particular, with E L and ALCO. We use NC and NR for concept names and roles, respectively. The notions of a TBox T , an ABox A, and an interpretation I = ( I ; I ) are defined in the usual way. The notions of satisfaction I j= T and I j= A are also as usual. We make the standard name assumption (SNA), i.e., aI = a for all I and individuals a. For combining the open- and closed-world semantics, we enrich KBs with a set of closed predicates. That is, we consider knowledge bases (KBs) K = (T ; ; A), where T is a TBox, NC [ NR, and A is an ABox. We call the set of closed predicates in K. For such a K and an interpretation I, we write I j= K if (a) I j= T and I j= A, (b) for all concept names A 2 , if e 2 AI , then A(e) 2 A, and (c) for all roles r 2 , if (e; e0) 2 rI , then r(e; e0) 2 A.

In case = ;, K is boils down to a usual DL KB and I j= K captures the usual notion of satisfaction. In this case, we may simply write K = (T ; A).

Note that in this paper KBs with closed predicates have the semantics as in [ 19 ], which relies on the SNA. However, all complexity results of this paper can be recast for the semantics of [ 7 ] that employs a weaker form of unique name assumption. 3

Standard Reasoning

Interpreting some predicates as closed allows one to simulate negation, disjunction, and nominals in plain E L, making it as expressive as full ALCO.

Theorem 1. Assume a consistent ALCO KB K = (T ; A). For every nominal fag that appears in K, let Da be a fresh concept name. Then we can construct in linear time an E L KB K0 = (T 0; ; A0) with closed predicates such that: 1. Every model I of K0 is a model of K. Moreover, DaI = fagI for every fag in K. 2. Every model I of K can be transformed into a model of K0 by modifying the interpretation of concept names and roles that do not appear in K.

Proof. The extension of E L with atomic negation (i.e., negation is applied to concept names only), denoted E L:, is known to be a notational variant of ALC [ 1 ]. Hence we simply show how to construct K0 = (T 0; ; A0) for a given E LO: KB K = (T ; A). We do this in two steps: first we eliminate nominals and obtain from K = (T ; A) an E L: KB K1 = (T1; 1; A1). Then we transform K1 = (T1; 1; A1) into the desired K0 = (T 0; ; A0) in E L. Let 1 = fDa j fag appears in Kg;

A1 = A [ fDa(a) j fag appears in Kg:

This ensures that DaI = fagI in every model of A1 where the predicates in 1 are interpreted as closed. Hence we can simply replace each concept fag by Da in T to obtain the desired T1. Next, for eliminating negation from (T1; 1; A1), we let =

A0 = A1 [ fDu(a1); Du(a2); D1(a1); D2(a2)g To obtain T 0 from T1, we replace every negated concept name :A by a fresh concept name A, and add the following axioms, where rA is a fresh role name: (1) (3) A u A v D? 9rA:D1 v A

> v 9rA:Du (2) 9rA:D2 v A (4) Note that, since there are no assertions of the form D?(a) in A0, we have D?I = ; in every model I of K0, and hence D? behaves as the special concept ?. This and axiom (1) ensure disjointness of A and A, while axioms (2) – (4) together with the assertions for the closed predicates Du, D1 and D2 ensure that e 2 AI or e 2 (A)I for every e 2 I . Indeed, let I be a model of K0 and let e 2 I be arbitrary. Then by axiom (2) there exists e0 2 I such that (e; e0) 2 rI and e0 2 DuI . But since Du is closed, then e0 2 fa1; a2g. If e0 = a1, then e0 2 D1I , so e 2 (9rA:D1)I and e 2 AI by axiom (3). Analogously, if e0 = a2, we can use axiom (4) to infer that e 2 (A)I . This ensures that A has exactly the same extension as :A in every model of K, and the claim follows.

This easy reduction allows us to extend to E L hardness results known for ALC. We can also infer upper bounds for logics with closed predicates, from known results under the standard open-world semantics, by exploiting the fact that in DLs that contain ALC, closed predicates can be simulated using nominals (see [26] and Prop. 1 in [30]): Theorem 2. For every DL KB (T ; ; A) there exists a logically equivalent KB of the form (T [ T 0; ;; A), where T 0 is a set of ALCO axioms whose size is polynomially bounded by the size of A.

This already allows us to obtain an almost complete picture of the landscape for standard reasoning tasks. The following theorem is stated for KB satisfiability, but note that it also applies to other traditional reasoning tasks like subsumption and instance checking since they are mutually reducible to each other in ALC, and hence also in any logic containing E L with closed predicates.

Corollary 1. The following bounds for deciding satisfiability of (T ; ; A) hold: 1. EXPTIME-complete if T and A are in any DL containing E L and contained in

SHOQ or SHOI. 2. NEXPTIME-complete if T and A are in any DL containing E LIF and contained in

SHOIQ. 3. N2EXPTIME-complete if T and A are in SRIQ or SROIQ, and in 2EXPTIME if T and A are in SROQ or SROI.

Proof. The lower bound of item (1) follows from Theorem 1 and the well known EXPTIME-hardness of KB satisfiability in ALC [29]. Similarly, the hardness of items (2) and (3) follows from Theorem 1 together with the NEXPTIME-hardness of ALCOIF [31], and the N2EXPTIME-hardness of SROIQ [ 13 ]. For the upper bounds, we use Theorem 2 and the fact that KB satisfiability is decidable in the mentioned bounds for the listed logics: SHOQ and SHOI in EXPTIME, SROQ and SROI in 2EXPTIME, SHOIQ in NEXPTIME, SROIQ in N2EXPTIME (see [ 4,13 ] and references therein).

Query Answering

In this section we consider the query answering problem over DL KBs. We cannot easily transfer complexity upper bounds from known KB satisfiability since, in general, queries are not naturally expressible in the syntax of DLs, and encoding them as part of a KB usually requires exponential space. We focus in conjunctive queries (CQs), whose syntax and semantics are defined in the usual way. In a nutshell, a CQ is a conjunction of atoms of the forms A(x) or r(x; y), for a concept name A or a role name r, and variables x; y. In what follows, all queries are Boolean queries with all variables existentially quantified. The decision problem we consider is query entailment: deciding whether a given query q is true in all the models of a given KB (T ; ; A).

It is well known that, under the classical open-world semantics, CQ entailment is hard for 2EXPTIME in most expressive DLs, but the complexity drops to EXPTIME in Horn fragments that disallow disjunction. Unfortunately, since the presence of closed predicates causes disjunction to be expressible, 2EXPTIME-hardness extends to many extensions of E L. For CQs, 2EXPTIME-hardness can be shown whenever the DL supports inverse roles [ 17 ], or a single left-identity axiom r t v t, or a transitive super role of some role [ 6 ]. If we consider query languages that extend CQs, like positive queries or (fragments of) conjunctive (2-way) regular path queries (C(2)RPQs), the same hardness holds already for plain ALC [25], and hence for E L with closed predicates.

Below we denote by E LLI the extension of E L with a single left-identity axiom r t v t, and by E LHtrans the extension of E L with role inclusions and a transitive role. Note that both logics are sublogics of E L++.

Theorem 3. Deciding (T ; ; A) j= q is hard for 2EXPTIME in all the following cases: 1. T and A are in E LI and q is a CQ. 2. T and A are in E LLI or in E LHtrans, and q is a CQ. 3. T and A are in E L and q is either a positive query, a -free CRPQ, or a -free

C2RPQ with only two variables.

Proof. We have shown in Theorem 1 that for every ALC KB K there is an E L KB K0 that has essentially the same models, and may only differ in the interpretation of symbols not occurring in K. Hence, for every query q, we have K j= q iff K0 j= q. This translation can be applied to extensions of ALC, and results in a KB with the same properties in the analogous extension of E L. In particular, an ALCI KB is rewritten into a E LI one, and an SH KB into an E LHtrans one. From this an existing results for ALC and its extensions, we obtain the desired lower bounds: item 1 follows from [ 18 ], item 2 follows from [ 6 ], and item 3 follows from [25].

Matching upper bounds are known, even for significantly more expressive queries and logics: in the standard setting, with no closed predicates, entailment of positive two-way regular path queries (P2RPQs) is in 2EXPTIME for any DL contained in ZIQ, ZOQ, ZOI, SHIQ, SHOQ, or SHOI [ 4 ]. From this and Theorem 2, we get the same upper bound for ZOQ, ZOI, SHOQ, SHOI and their sublogics. Corollary 2. Let q be a P2RPQ. Then deciding (T ; ; A) j= q is 2EXPTIME complete TfohreTsaamnedhAolidnsafonry qDaL CcoQntiaf iTninagndE LAaanrde icnonataDinLecdoinntaZinOinQg,EZLOIIo,rSEHLOLI.Q, SHOI.

Corollary 2 implies that query entailment in the presence of closed predicates is almost always 2EXPTIME-complete in combined complexity. But there are some exceptions. On the one hand, the interaction of nominals, inverses, and counting makes query entailment very challenging. In the plain open-world setting, entailment of conjunctive queries is coN2EXPTIME-hard for ALCOIF [ 10 ], and it has been shown to be decidable [28], but no elementary upper bounds on its complexity are known. For its extension with transitive roles, and for the well known SHOIQ, decidability remains open. Hence, in the presence of closed predicates, we do not get any interesting upper bounds for DLs that simultaneously support inverses and counting, like ALCIF and SHIQ. Moreover, obtaining such bounds seems very hard. We remark that the authors of [ 7 ] proved that query entailment in ALCIF with closed predicates and query entailment under the standard open-world semantics in ALCOIF are mutually reducible.

On the other hand, the mentioned 2EXPTIME lower bounds for CQs require the presence of either inverse roles, left identity axioms, or transitivity and role hierarchies. For E L (with closed predicates), ALC, and their extensions that have neither inverses nor left identities, we only have the EXPTIME lower bound from KB satisfiability, and the 2EXPTIME upper bound of Corollary 2. Without closed predicates, CQ entailment for plain ALC, and even for ALCHQ, is feasible in single exponential time [ 18,24 ]. A natural question is whether nominals, or equivalently, closed predicates, can be added to ALCHQ without increasing the worst-case complexity of CQ entailment. Unfortunately, the answer is negative (unless coNEXPTIME = EXPTIME), as we show next.

A coNEXPTIME lower bound for CQ entailment in ALCO

In this section, we show that deciding whether (T ; A) 6j= q for a given CQ q and a given ALCO KB (T ; A) (with the standard open-world semantics), is hard for nondeterministic single exponential time. By Theorem 1, the same applies to E L in the presence of closed predicates.

Before we start with the proof, we recall a useful property of ALCO: for query answering, it is enough to focus on forest-shaped models. A forest is a set F of nonempty words such that w c 2 F with w non-empty implies w 2 F . An interpretation I is forest-shaped if there is a bijection f from its domain to a forest, such that – f (aI ) has length one for every individual a, and – (e; e0) 2 rI implies that either e0 = a for some individual a, or f (e0) is of the form f (e) c for some symbol c.

For many DLs and query languages, it has been shown that query entailment can be decided over forest shaped interpretations. This applies also to CQs over ALCO KBs: Lemma 1 ([ 9,4 ]). Let K be a given ALCO KB and let q be a CQ. Then K 6j= q iff there is a forest shaped interpretation I such that I j= K and I 6j= q.

Now we show our lower bound. The proof is by reduction from the following coNEXPTIME-complete variant of the tiling problem: Definition 1 (Domino System). A domino system D is a triple (T; H; V ), where T = f0; : : : ; k 1g, k 0, is a finite set of tile types and H; V T T represent the horizontal and vertical matching conditions. Let D be a domino system and c = c0; : : : ; cn 1 an initial condition, i.e. an n-tuple of tile types. A mapping : f0; : : : ; 2n+1 1g f0; : : : ; 2n+1 1g ! T is a solution for D and c iff for all x; y < 2n+1, the following holds (where i denotes addition modulo i): – if (x; y) = t and (x 2n+1 1; y) = t0, then (t; t0) 2 H – if (x; y) = t and (x; y 2n+1 1) = t0, then (t; t0) 2 V – (i; 0) = ci for i < n.

For the reduction, we do not need a full ALCO knowledge base, but a simple ABox with single concept assertion CD;c(a) for a complex ALCO concept CD;c. We show how to translate a given domino system D and initial condition c = c0 cn 1 into an assertion CD;c(a) and query qD;c such that each forest-shaped model I of CD;c(a) that satisfies I 6j= qD;c encodes a solution to D and c, and conversely each solution to D and c gives rise to a model of CD;c(a) with I 6j= qD;c.

Our reduction is based on the proof of coNEXPTIME-hardness of rooted query entailment in ALCI [ 17 ], and also resembles the similar proof for S [ 6 ]. In fact, the first part of the concept CD;c, which generates forest models that encode a potential solutions, is essentially as in [ 17 ]. The second part and the query are quite different, since they exploit nominals to detect errors in potential solutions.

Constructing the ABox. We now define the complex concept CD;c, and the desired ABox is fCD;c(a)g. We assume that CD;c is a conjunction of the form CD1;c u CD2;c.

For convenience, let m = 2n + 2. The purpose of the first conjunct CD1;c is to enforce a binary tree of depth m, whose edges are labeled with a single role r, and whose leaves are labeled with the numbers 0; : : : ; 2m 1 of a binary counter C, implemented using concept names B0; : : : ; Bm. Intuitively, each of these leaves ` stores a position in the 2n+1 2n+1-grid to be tiled: the bits B0; : : : Bn encode the horizontal position x, and the bits Bn+1; : : : Bm encode the vertical position y. We also use a concept name Di for each tile type i 2 T . Each leaf g storing a position (x; y) has as r-children three ‘grid nodes’ gh, gright , and gup labeled G, which satisfy all the following conditions: 1. gh represents the grid node with position (x; y), and stores the same bit address as g (that is, gh and g coincide on the interpretation of all Bi). 2. gright and gup represent the right- and up-neighbor of g, and respectively store the addresses (x 2n+1 1; y) and (x; y 2n+1 1). 3. gh is labeled Gh, while gright and gup are labeled Gs. 4. gh (resp., gright , gup ) satisfies exactly one concept Di, representing the assigned tile type (x; y) (resp., (x 2n+1 1; y), (x; y 2n+1 1)). 5. The tiling of the gh nodes respects the initial condition, that is, if `h stores the position (i; 0), then it satisfies Dci . 6. The tiling of gright and gup respect the matching conditions, that is, if gh satisfies Di, gright satisfies Dj , and gup satisfies Dj0 , then (Di; Dj ) 2 H and (Di; Dj0 ) 2 V .

The tree we have described almost describes a solution for D, except for the crucial fact that different copies of the same node in the grid may have different types assigned. That is, for an address (x; y), the gright and gup nodes with address (x; y) need not satisfy the same Di as the gh with address (x; y). We call a model I of CD1;c(a) proper if it satisfies the following condition: (?) For every pair g 2 GIh, g0 2 GsI such that g 2 Bi iff g0 2 Bi for all 0 there exists some i < k such that fg; g0g DiI . i m,

We can use an ALC concept CD1;c to enforce a tree as above, such that deciding the existence of a solution for D and c reduces to finding a proper model of CD1;c. Such constructions exist in the literature, and in fact, the concept we described is just a minor modification of the conjunction CD1;c u u CD6;c given in [ 17 ], hence we omit its rather technical definition. Instead, we rely on the following claim: Lemma 2 (implicit in [ 17 ]). Let D be a domino system and c an initial condition. Then we can build an ALC concept CD1;c such that there exists a solution for D and c iff there exists a proper model of CD1;c(a). Moreover, the size of CD1;c and the time needed to construct it are polynomially bounded by the size of D.

We construct below a query qD;c that does not match a forest model of CD1;c(a) iff (?) is satisfied. By Lemmas 2 and 1, this suffices to decide whether there exists a solution for D and c. But before defining qD;c, we define the second conjunct CD2;c of CD;c. Its purpose is to add nodes and labels to the forest models of CD1;c(a) that allow us to test for (?) using a CQ.

For defining CD2;c, we use the following additional alphabet symbols: – two individual names ai and ai and one concept name Ai for each bit Bi, 0 – an individual name tj for each tile type j < k, – a concept T stating that some individual stands for a tile type. i m,

Each G node g is linked via r-arcs to the individuals ai; ai that encode its bit address. We also link g nodes to the individuals that stand for the tile types, but we do it differently for the Gh nodes and the Gs nodes, as follows: – If g is a Gh-node with tile type Di, then g has an r-arc to ti.

– If g is a Gs-node with tile type Di, then g has an r-arc to each tj with j 6= i. Finally, we make both ai and ai instances of Ai, for each bit i, and we make all tile types tj instances of T . Formally, this is all ensured using the conjunction C12 u C22 of the following two concepts:

C12 = 8rm+1:

Bi ! 9r:faig u :Bi ! 9r:faig u l 0 i m l 0 i<k

0 i m C22 = 8rm+2: ( l fai; aig ! Ai u ft0; : : : tk 1g ! T

Di ! (Gh ! 9r:ftig) u (Gs ! (

l 0 j<k;j6=i 9r:tj )) yA0A0 yA1A1

AmyAm

T yT x1 . . . x2

Gs

Now we are ready to define our ABox fCD;c(a)g, by taking CD2;c = C12 u C22 as defined above, CD1;c as in Lemma 2, and CD;c = CD1;c u CD2;c. Every model of CD;c(a) is a model of CD1;c(a), and every forest model of CD1;c(a) can be extended to a model of CD;c(a) while preserving properness, hence from Lemma 2 we get: Lemma 3. D and c have a solution iff there exists a proper forest model of CD;c(a).

It is only left to define a query qD;c that matches a forest model of CD;c(a) if and only if it is not proper. We will rely on the following properties ensured by CD1;c. First, the connections to the individuals representing the bit address ensure the following: (y) Let g; g0 be two G-nodes. Then g and g0 share an r-arc to a common individual from ai; ai for each 0 i m iff they have the same bit address.

Since the links to the tile types for the Gh-nodes and for the Gs-nodes are inverted, we also have: (z) Let gh be a Gh-node and gs be a Gs-node. Then there exists some tj such that both gh and gs have an r-arc to tj iff gh and gs have different tile types.

Hence, to establish non-properness it suffices to find a Gh-node and a Gs-node that share an r-arc to a common individual from ai; ai for each 0 i m (and hence share the same address), but also share a link to a tj node (and hence have different tile type). This is done with the following query: qD;c =9x1; x2; yA0 ; ; : : : ; yAm ; yT :Gh(x1); Gs(x2); r(x1; yA0 ); A0(yA0 ); : : : ; r(x1; yAm ); Am(yAm ); r(x1; yT ); T (yT ); r(x2; yA0 ); A0(yA0 ); : : : ; r(x2; yAm ); Am(yAm ); r(x2; yT ); T (yT ): The query qD;c is illustrated in Figure 1. To see that qD;c has a match iff (?) fails, we first note that x1 can only be matched to a Gh node and x2 to a Gs node. Each yAi must be matched to an instance of Ai, which is one of ai and ai. Since x1 and x2 are connected to all the yAi , then they need to have either ai or ai as common successor, for each i, in every model where the query has a match. By (y), this is the case exactly when they have the same bit address. The variable yT can match instances of T , which are only the tile type individuals tj , and since x1 and x2 are both connected to yT , we have that x1 and x2 can only be matched to nodes sharing a link to a common tj . By (z), and since the matches of x1 and x2 are a Gh node and a Gs node, they must have a different tile type. Hence the query has a match iff there are a Gh node gh and a Gs node gs that have the same bit address and different tile types, that is, there is a pair violating the condition of (?) and the model is not proper. Hence we get that there is a model I of CD;c(a) where there is no match for qD;c, and iff there exist a proper model of CD;c(a) iff there is a solution for D and c.

Lemma 4. CD;c(a) 6j= qD;c iff there is a solution for D and c.

From this, the hardness of the given tiling problem, and Theorem 1, we get: Theorem 4. The following problems are hard for coNEXPTIME: – deciding (;; fC(a)g) j= q for q a CQ and C an ALCO concept, and – deciding (T ; ; A) j= q for q a CQ and T ; A in E L.

Unfortunately, we do not have matching upper bounds. We believe that both problems are likely to be solvable in coNEXPTIME, but we are still working on a suitable algorithm. 5

Discussion and Outlook

In this paper we have given several bounds on the combined complexity of reasoning in various DLs in the presence of closed predicates, for standard reasoning problems like KB satisfiability, as well as for answering queries ranging from CQs to P2RPQs. Unlike the data-complexity, that is coNP-complete in practically all cases (from DL-Litecore [ 7,19 ] to expressive DLs like ALCHOQ and ALCHOI [ 21 ]), the combined complexity offers a complex landscape. We summarize some results in Table 1, emphasizing the cases in which closed predicates have an interesting effect on the complexity.

Apart from establishing the precise complexity of query answering in DLs between ALCO and ALCHOQ (without closed predicates), and in all DLs between E L and ALCHOQ with closed predicates, other problems remain open. Notably, in this paper we have not considered the DL-Lite family. An algorithm for CQ entailment in DL-LiteF was developed in [ 7 ] to obtain a coNP upper bound in data complexity, but it only yields very high bounds on the combined complexity that are likely not to be optimal. That algorithm deals with the intricate interactions of inverse roles, functionality, and closed predicates, that behave as nominals, and it may be possible to use the characterization of countermodels given there as a starting point for a better combined complexity upper bound. In the DL-Lite variants that do not support functionality, countermodels are likely to have a simpler structure. However, even in these simpler languages, it is not apparent whether interesting upper bounds can be obtained by simple adaptations of existing techniques. In particular, it has been shown that singleton nominals do not increase neither the data nor the combined complexity of DL-Lite [ 11 ], but the effect of the combination of nominals and (restricted) disjunction that results from closed predicates remains to be studied for the DL-Lite family.

Finally, we have seen that in general, the disjunctive information encoded by closed predicates has a negative effect on the complexity of reasoning. In the light of this, it EL ELH ELI

trans Horn-SHOI Horn-SHOQ ELIF Horn-SHIQ ELOIF , Horn-SHOIQ ALCO

KB consistency

NEXPTIME N2EXPTIME [ 10 ] NEXPTIME N2EXPTIME [ 10 ] SHOIQ [31] open (Cor. 1.2) open Table 1: Combined complexity of reasoning in description logics with/without closed predicates. By we indicate lower bounds, by upper bounds, and the rest are all completeness results. For the cells marked with , decidability if only simple roles occur in the query follows from [28], but no complexity upper bounds are known. seems particularly interesting to study criteria that allow to identify instances of TBoxes and queries for which the complexity does not increase. Major contributions in this direction can be found in [ 19 ]. In particular, the authors propose safety criteria that ensure specific TBoxes have the convexity property, guaranteeing data tractability of queries. It seems that this criteria may also be useful for establishing the existence of a universal model for query answering, and when a suitable representation of such a model can be built in single exponential time, query answering is likely to be feasible in single exponential time. This seems a promising direction for further investigation. 23. M. Ortiz, S. Rudolph, and M. Sˇimkus. Query answering in the Horn fragments of the description logics SHOIQ and SROIQ. In Proc. of IJCAI 2011, pages 1039–1044. IJCAI/AAAI, 2011. 24. M. Ortiz, M. Sˇimkus, and T. Eiter. Worst-case optimal conjunctive query answering for an expressive description logic without inverses. In Proc. of AAAI 2008, pages 504–510. AAAI Press, 2008. 25. M. Ortiz and M. Sˇ imkus. Revisiting the hardness of query answering in expressive description logics. In Proc. of RR 2014, pages 216–223. Springer International Publishing, 2014. 26. R. Reiter. Equality and domain closure in first-order databases. J. ACM, 27(2):235–249, Apr.

1980. 27. R. Rosati. On conjunctive query answering in E L. In Proc. of DL 2007, volume 250 of CEUR

Electronic Workshop Proceedings, 2007. 28. S. Rudolph and B. Glimm. Nominals, inverses, counting, and conjunctive queries or: Why infinity is your friend! J. of Artificial Intelligence Research, 39:429–481, 2010. 29. K. Schild. A correspondence theory for terminological logics: Preliminary report. In Proc. of

IJCAI 1991, pages 466–471. Morgan Kaufmann, 1991. 30. I. Seylan, E. Franconi, and J. de Bruijn. Effective query rewriting with ontologies over

DBoxes. In Proc. of IJCAI 2009, pages 923–925, 2009. 31. S. Tobies. The complexity of reasoning with cardinality restrictions and nominals in expressive description logics. J. of Artificial Intelligence Research, 12:199–217, 2000. 32. S. Tobies. Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, LuFG Theoretical Computer Science, RWTH-Aachen, Germany, 2001.

References

1. F. Baader , S. Brand , and C. Lutz . Pushing the el envelope . In Proc. of IJCAI 2005 , pages 364 - 369 . Morgan-Kaufmann Publishers, 2005 .

2. F. Baader , S. Brandt , and C. Lutz . Pushing the el envelope further . In Proc. of OWLED 2008 , 2008 .

3. M. Cadoli , F. M. Donini , and M. Schaerf . Closed world reasoning in hybrid systems . In Proc. of ISMIS 1990 , pages 474 - 481 , 1990 .

4. D. Calvanese , T. Eiter , and M. Ortiz . Regular path queries in expressive description logics with nominals . In Proc. of IJCAI 2009 , pages 714 - 720 , 2009 .

5. T. Eiter , G. Gottlob, M. Ortiz , and M. Sˇ imkus. Query answering in the description logic HornSHIQ . In Proc. of JELIA 2008 , pages 166 - 179 , Berlin, Heidelberg, 2008 . Springer-Verlag.

6. T. Eiter , C. Lutz , M. Ortiz , and M. Sˇimkus . Query answering in description logics with transitive roles . In Proc. of IJCAI 2009 , volume 9 , pages 759 - 764 , 2009 .

7. E. Franconi , Y. A. Iba ´n˜ez-Garc´ıa, and I. Seylan. Query answering with DBoxes is hard . Electr. Notes Theor. Comput. Sci. , 278 : 71 - 84 , 2011 .

8. B. Glimm , I. Horrocks , and U. Sattler. Deciding SHOQ \ knowledge base consistency using alternating automata . In Proc. of DL 2008 , volume 353 of CEUR Workshop Proceedings , 2008 .

9. B. Glimm , I. Horrocks , and U. Sattler . Unions of conjunctive queries in SHOQ . In Proc. of KR 2008 , pages 252 - 262 . AAAI Press/The MIT Press, 2008 .

10. B. Glimm , Y. Kazakov , and C. Lutz. Status QIO : An update . In Proc. of DL 2009 , volume 745 of CEUR Workshop Proceedings , 2011 .

11. M. Haddad and D. Calvanese . Extending DL-Lite A with (singleton) nominals . In Proc. DL 2013 , volume 1014 of CEUR Workshop Proceedings , 2013 .

12. J. Hladik . A tableau system for the description logic SHIO . In U. Sattler, editor, IJCAR Doctoral Programme , volume 106 of CEUR Workshop Proceedings. CEUR-WS.org , 2004 .

13. Y. Kazakov . RIQ and SROIQ are harder than SHOIQ . In Proc. of KR 2008 , pages 274 - 284 . AAAI Press, 2008 .

14. M. Kr o¨tzsch and S. Rudolph . Conjunctive queries for E L with composition of roles . In Proc. of DL 2007 , volume 250 of CEUR Electronic Workshop Proceedings , 2007 .

15. M. Kr o¨tzsch, S. Rudolph, and P. Hitzler . Conjunctive queries for a tractable fragment of OWL 1.1 . In Proc. of ISWC 2007 + ASWC 2007 , volume 4825 of Lecture Notes in Computer Science, pages 310 - 323 . Springer, 2007 .

16. M. Kro¨tzsch, S. Rudolph, and P. Hitzler . Complexities of Horn description logics . ACM Trans. Comp . Log., 14 ( 1 ):2: 1 - 2 : 36 , 2013 .

17. C. Lutz . Inverse roles make conjunctive queries hard . In Proc. of DL 2007 , pages 100 - 111 , 2007 .

18. C. Lutz. The complexity of conjunctive query answering in expressive description logics . In Proc. of IJCAR 2008 , pages 179 - 193 . Springer, 2008 .

19. C. Lutz , I. Seylan , and F. Wolter . Ontology-based data access with closed predicates is inherently intractable(sometimes) . In Proc. of IJCAI 2013. IJCAI/AAAI , 2013 .

20. C. Lutz , I. Seylan , and F. Wolter . Ontology-mediated queries with closed predicates . In Proc. of IJCAI 2015. IJCAI/AAAI ,, 2015 .

21. M. Ortiz , D. Calvanese , and T. Eiter . Data complexity of query answering in expressive description logics via tableaux . 41 ( 1 ): 61 - 98 , 2008 .

22. M. Ortiz , S. Rudolph , and M. Sˇimkus . Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2 . In Proc. of KR 2010 . AAAI Press, 2010 .