When using ontologies to access instance data, it can be useful to make a closed world assumption (CWA) for some predicates and an open world assumption (OWA) for others. The main problem with such a setup is that conjunctive query (CQ) answering becomes intractable already for inexpressive description logics such as DL-Lite and EL. We take a closer look at this situation and carry out a fine-grained complexity analysis by considering the complexity of CQ answering w.r.t. individual TBoxes. Our main results are a dichotomy between AC0 and CONP for TBoxes formulated in DL-Lite and a dichotomy between PTIME and CONP for EL-TBoxes. In each tractable case, CQ answering coincides with CQ answering under pure OWA; the CWA might still be useful as it allows queries that are more expressive than CQs.
Description logics (DLs) increasingly find application in ontology-based data access
(OBDA), where an ontology is used to enrich instance data and the chief aim is to
provide efficient query answering services. In this context, it is common to make the open
world assumption (OWA). Indeed, there are applications where the data is inherently
incomplete and the OWA is semantically adequate, for example when the data is
extracted from the web. In other applications, however, it is more reasonable to make a
closed world assumption (CWA) for some predicates in the data. In particular, when
the instance data is taken from a relational database, then the CWA can be
appropriate for the data predicates while additional predicates in the ontology should always
be interpreted under the OWA (this is the very idea of OBDA). As a concrete example,
consider geographical databases such as OpenStreetMap which contain pure
geographical data as well as rich annotations, stating for example that a certain polygon describes
a ‘popular Thai restaurant’. As argued in [
In the DL literature, there are a variety of approaches to adopting the CWA, often
based on epistemic operators or rules [
A major problem in admitting closed predicates is that query answering easily
becomes intractable regarding data complexity (where the TBox and query are assumed
to be fixed and thus of constant size). In fact, this is true already for instance queries
(IQs), when only closed predicates are admitted in the data, and for TBoxes formulated
in inexpressive DLs such as the core dialect of DL-Lite [
Our main results are a dichotomy between AC0 and CONP for TBoxes formulated in
DL-Lite and a dichotomy between PTIME and CONP for E L-TBoxes. In each case, we
provide a transparent characterization that separates the easy cases from the hard cases.
These results are interesting when contrasted with query answering w.r.t. TBoxes that
are formulated in the expressive DLs ALC and ALCI, where the data complexity is
also between AC0 and CONP, but where the existence of a dichotomy between PTIME
and CONP is a deep open question that is equivalent to the Feder-Vardi conjecture
for the existence of a dichotomy between PTIME and NP in non-uniform constraint
satisfaction problems [
While this sounds discouraging, there is still a potential benefit of closed predicates in tractable cases: for the ‘closed part’ of the signature, we can go beyond conjunctive queries and admit (almost) full first-order queries without becoming undecidable and, indeed, without any negative impact on data complexity. We propose a concrete query language that implements this idea and show that AC0 data complexity is preserved for DL-Lite TBoxes and PTIME data complexity is preserved for E L-TBoxes when CQs are replaced with queries formulated in the extended language.
Most proofs in this paper are deferred to the (appendix of the) long version, which is available at http://www.csc.liv.ac.uk/ frank/publ/publ.html. 2
We use standard notation from description logic [
Every ABox A corresponds to an interpretation IA whose domain is Ind(A) and in which a 2 AIA iff A(a) 2 A, for all A 2 NC and a 2 Ind(A) and similarly for role names. Conversely, every interpretation I corresponds to a (possibly infinite) ABox AI whose individual names are I .
A predicate is a concept or role name. A signature is a finite set of predicates. The signature sig(C) of a concept C, sig(T ) of a TBox T , and sig(A) of an ABox A, is the set of predicates occurring in C, T , and A, respectively. For being able to declare predicates as closed, we add an additional component to TBoxes. A pair (T ; ) with T a TBox T and a signature is a TBox with closed predicates. For any ABox A, a model I of (T ; ) and A is an interpretation I with Ind(A) Ind(I) that satisfies T and A and such that
AI = fa j A(a) 2 Ag
rI = f(a; b) j r(a; b) 2 Ag
for all A 2
for all r 2
\ NC
\ NR:
Note that TBox statements that only involve closed predicates are effectively integrity
constraints in the standard database sense [
A first-order query (FOQ) q(x) is a first-order formula constructed from atoms A(t), r(t; t0), and t = t0, where t; t0 range over individual names and variables and x = x1; : : : ; xk contains all free variables of q. We call x the answer variables of q(x). A conjunctive query (CQ) q(x) is a FOQ using conjunction and existential quantification, only. A tuple a = a1; : : : ; ak Ind(A) is a certain answer to q(x) in A given (T ; ), in symbols T ; A j=c( ) q(a), if I j= q[a1; : : : ; ak] for all models I of (T ; ) and A. When computing certain answers we assume that all individual names in the query occur in the ABox. If = ;, then we simply omit and write T ; A j= q(a) instead of T ; A j=c( ) q(a). If C is an E LI-concept, then the CQ corresponding to C(a) is defined in the usual way and called an E LI-instance query. E L-instance queries are defined analogously.
The following definition generalizes the definition of non-uniform data complexity
introduced in [
– CQ answering w.r.t. (T ; ) is in PTIME if for every CQ q(x) there is a polytime algorithm that computes, for a given ABox A, all a Ind(A) with T ; A j=c( ) q(a); – CQ answering w.r.t. (T ; ) is CONP-hard if there is a Boolean CQ q such that it is
CONP-hard to decide, given an ABox A, whether T ; A j=c( ) q.
For other classes of queries such as FOQs and E LI-instance queries, analogous notions
can be defined. It is known that for = ;, CQ answering is in PTIME for E L-TBoxes
[
The following property, plays a central role in our analysis; see [
We first formulate the dichotomy result for DL-Lite. The next definition introduces a class of TBoxes with closed predicates that turn out to be exactly the TBoxes for which query answering is in AC0.
Lite-concepts B1; B2 and role r such that
2. T j= B1 v 9r:> and T j= 9r :> v B2; and
is safe if there are no
DL3. B1 6= 9r:>, sig(B2)
, and sig(r) \
= ;.3
Note that it is easy to check in PTIME whether a given DL-Lite TBox is safe since
subsumption in DL-Lite can be decided in PTime [
cates. Then the following holds:
instance query C(a) such that answering C(a) w.r.t. (T ; ) is coNP-hard. 2. If (T ; ) is safe, then (a) CQ answering w.r.t. (T ; ) coincides with CQ answering w.r.t. (T ; ;) for all
Ind(A), we have T ; A j=c( ) q(a) iff T ; A j= q(a): (b) CQ answering w.r.t. (T ; ) is in AC0 and (T ; ) has the disjunction property. The following example illustrates Theorem 1.
Example 1. (a) Let T = fA v 9r:>; 9r :> v Bg and = fBg. (T ; ) is not safe. The disjunction property can be refuted as follows. Let A = fA(a); B(b1); A1(b1), B(b2), A2(b2)g, where A1; A2 are fresh concept names. Then 1. T ; A j=c( ) 9r:(A1 u B)(a) _ 9r:(A2 u B)(a); 2. T ; A 6j=c( ) 9r:(Ai u B)(a) for i = 1; 2.
Point 1 should be clear since in any model I of (T ; ) and A one has to link a with r to b1 or to b2 to satisfy T . For Point 2 and i 2 f1; 2g, consider the model Ii that corresponds to A expanded with r(a; bi). Then Ii is a model of (T ; ) and A (note that r 62 ) but a 62 (9r:(Ai u B))Ii where 1 = 2 and 2 = 1. Thus T ; A 6j=c( ) 9r:(Ai u B)(a). When we add any of A; A1; A2 to , all statements are still true.
(b) The failure of the disjunction property for the ABox A and TBox T results
in a choice that enables a coNP-hardness proof by reduction of 2+2-SAT, a variant of
propositional satisfiability where each clause contains precisely two positive literals and
two negative literals [
The proof of Theorem 1 is given in the next section. We now come to the case of TBoxes formulated in E L, where we start with examples. Observe that we can find an E L-TBox without the disjunction property by a reformulation of the DL-Lite TBox from Example 1. Let T 0 = fA v 9r:Bg with = fBg. Then, in the same way as for (T ; ) one can show that the disjunction property fails for (T 0; ) and that CQ answering is coNP-hard. In E L, however, there is an additional (and more subtle) cause for non-tractability, which we discuss in the following example.
Example 2. Consider again T 0 = fA v 9r:Bg, but now set 0 = frg. We first show that (T 0; 0) does not have the disjunction property. Let A0 = fA(a); r(a; b1), A1(b1), r(a; b2); A2(b2)g, where A1; A2 are fresh concept names. Then one can easily show that the disjunction property fails:
or r = s for a role name s 62 . – T 0; A0 j=c( 0) 9r:(A1 u B)(a) _ 9r:(A2 u B)(a); – T 0; A0 6j=c( 0) 9r:(Ai u B)(a), for i = 1; 2.
It is crucial that B 62 0. The proof of CONP-hardness is very similar to the proof mentioned in Example 1.
Observe that one cannot reproduce this example in DL-Lite: for the TBox T = fA v 9r:>; 9r :> v Bg with 0 = frg, we have T ; A0 j=c( 0) B(bi) for i = 1; 2 and, therefore, T ; A0 j=c( 0) 9r:(Ai u B)(a), for i = 1; 2. Thus, the disjunction property is not violated.
We now identify a class of E L-TBoxes with closed predicates that turn out to be exactly the TBoxes for which CQ answering is in PTIME. We call a concept E a top-level conjunct (tlc) of C if C is of the form D1 u u Dn with n 1 and E = Di for some i.
Definition 4. Let (T ; ) be an E L-TBox with closed predicates. (T ; ) is safe if there exists no E L-inclusion C v 9r:D such that 1. T j= C v 9r:D; 2. there does not exist a tlc 9r:C0 of C with T j= C0 v D; 3. one of the following is true: (s1) r 62 and sig(D) \ 6= ;; (s2) r 2 , sig(D) 6 and there is no
T j= E v D.
-concept E with T j= C v 9r:E and Note that Condition 3(s1) of Definition 4 is similar to the definition of safety for DLLite. Example 2 shows why Condition 3(s2) is needed. The following example illustrates the additional requirement of 3(s2) that no “interpolating” -concept E exists. Example 3. Let T = fA v 9r:E; E v Bg and first assume that = frg. Then the inclusion A v 9r:B satisfies Condition 3(s2) and thus (T ; ) is not safe. Now assume = fr; Eg. Then, the inclusion A v 9r:B does not violate safety because E can be used as a ‘ -interpolant’. Note that the ABox A0 from Example 2, which we used to refute the disjunction property in a very similar situation, is simply unsatisfiable w.r.t. (T ; ) because E has to interpreted as the empty set. Indeed, it can be shown that (T ; ) is safe.
Note that, unlike the DL-Lite case, the definition of safety of E L-TBoxes with closed predicates does not immediately suggest a decision procedure since there are infinitely many candidates for the concepts C, D, and E. We conjecture that safety is decidable in PTIME, but pursuing this further is left for future work.
the following holds:
instance query C(a) such that answering C(a) w.r.t. (T ; ) is coNP-hard. 2. If (T ; ) is safe, then (a) CQ answering w.r.t. (T ; ) coincides with CQ answering w.r.t. (T ; ;) for all
(b) CQ answering w.r.t. (T ; ) is in PTIME and (T ; ) has the disjunction property.
As noted in the introduction, Theorems 1 and 2 essentially show that CQ answering with closed predicates is inherently intractable. Note, though, that Points 2(a) of these theorems refer only to satisfiable ABoxes. In fact, TBox statements that refer only to closed predicates act as integrity constraints also in the tractable cases. Moreover, safe TBoxes admit any integrity constraint that can be formulated in the DL at hand, i.e., if a TBox T formulated in DL-Lite or E L is safe, then it is still safe after adding any concept inclusions that refers only to closed predicates. In the appendix of the long version, we show that checking satisfiability of ABoxes w.r.t. safe TBoxes is in AC0 for DL-Lite and in PTIME for E L (for data complexity).
Another way of taking advantage of closed predicates without losing tractability is to admit more expressive query languages. Indeed, mixing open and closed predicates seems particularly useful when large parts of the data stem from a relational database, as in the geographical database application mentioned in the introduction. In such a setup, one would typically not want to give up FOQs (SQL queries) available in the relational system to accomodate open world predicates. We propose a query language that combines, in a straightforward way, FOQs for closed predicates with CQs for open (and closed) predicates. We then show that, for safe TBoxes with closed predicates, such queries can be answered as efficiently as CQs both in the case of DL-Lite and of E L.
As in the relational database setting, we allow only FOQs that are domain-independent and thus correspond to expressions of relational algebra (and SQL queries). Formally, a FOQ q(x) is domain-independent if for all interpretations I and J such that P I = P J for all P 2 sig(q(x)), we have I j= q[d] iff J j= q[d] for all tuples d I [ J . Intuitively, the truth value of a domain-independent FOQ depends only on the interpretation of the data predicates, but not on the actual domain of the interpretation. For example, :A(x), is not domain-independent whereas B(x) ^ :A(x) is domain-independent. In our query language, we allow domain-independent FOQs over closed predicates as atoms in CQs.
Definition 5. Let be a signature that declares closed predicates. A conjunctive query with FO( ) plugins (abbreviated CQFO( )) is of the form 9x1 9xn('1 ^ : : : ^ 'm), where n 0, m 1, and each 'i is either a CQ or a domain-independent FOQ whose signature is included in .
The subsequent theorem shows that switching from CQs to CQFO( )s does not increase data complexity.
Theorem 3. 1. CQFO( )-answering w.r.t. safe DL-Lite-TBoxes with closed predicates is in AC0.
More precisely, for every such TBox (T ; ) and CQFO( ) q(x), there exists a FOQ q0(x) such that for all A and a Ind(A): T ; A j=c( ) q(a) iff IA j= q0(a). 2. CQFO( )-answering w.r.t. safe E L-TBoxes is in PTIME.
Query languages between CQs and FOQs have been studied before. In the standard
setup where all predicates are open, it was shown in [
We sketch proofs of Theorems 1 and 2. We begin with the first part of Theorem 1.
Proof. Assume that B1 v 9r:>; 9r :> v B2 satisfy the conditions of Definition 3. Take a finite model I of T with a0 2 B1I ; such a model exists since B1 is satisfiable w.r.t. T and DL-Lite has the finite model property. Let S = fb 2 I j (a0; b) 2 rI g. Since B1 6= 9r:>, we have a0 2 BIS for the interpretation IS obtained from I by 1 removing all pairs (a0; b) with b 2 S from rI . Take the ABox AS corresponding to IS and let A be the disjoint union of two copies of AS . We denote the individual names of the first copy by (b; 1), b 2 I , and the elements of the second copy by (b; 2), b 2 I . Let
A0 = A [ fA1(b; 1) j b 2 B2I g [ fA2(b; 2) j b 2 B2I g; where A1 and A2 are fresh concept names. Now one can show that the disjunction property fails: (T ; A0) j=c( ) 9r:(A1 uB2)(a0; 1)_9r:(A2 uB2)(a0; 1) and (T ; A0) 6j=c( ) 9r:(Ai u B2)(a0; 1) for i = 1; 2.
The CONP-hardness proof is now similar to the proof for Example 1 given in the appendix of the long version. o For the second part of Theorem 1, we first prove (a):
Proof. Let (T ; ) be safe and assume that A is satisfiable w.r.t. (T ; ). We remind
the reader of the construction of a canonical model I of T and A (without closed
predicates!) [
Ai 6j= B2(a), then sig(B2) \ = ;.
Claim 1 holds for all Ai, i 0, and all a 2 Ind(A): otherwise, Ai+1 is unsatisfiable, in contradiction to Point 1. It follows that Claim 1 holds for i = 0. We proceed by induction, assuming that Claim 1 has been proved for Ai, but that to the contrary of what is to be shown there are B1 v B2 2 T with Ai+1 j= B1(a), Ai+1 6j= B2(a), and sig(B2) \ 6= ;, i.e., sig(B2) . By what was said above, we have a 62 Ind(A) and thus a was introduced as a witness for some 9s:>. By IH, sig(s) \ = ; and there exists B1 6= 9s:> with B1 v 9s:> 2 T . Point 2 yields T j= 9s :> v B2, in contrary to (T ; ) being safe. This finishes the proof of Claim 1.
It follows from Claim 1 that J is a model of (T ; ) and A. Thus, we have for CQs q(x) and a Ind(A): if T ; A 6j= q(a), then J 6j= q[a], and so T ; A 6j=c( ) q(a), as required. o
To obtain a proof of Part 2 of Theorem 1, it remains to show that, for safe (T ; ), it is in AC0 to decide whether an ABox is satisfiable w.r.t. (T ; ). To this end, it is readily checked that an ABox A which is satisfiable w.r.t. T is satisfiable w.r.t. a safe (T ; ) iff T ; A j= B(a) implies A j= B(a) for all DL-Lite concepts B over . To see that this condition is in AC0, let 'B(x) be an FO query with T ; A j= B(a) iff IA j= 'B(a), where IA is the interpretation corresponding to A. Then A is not satisfiable w.r.t. (T ; ) iff IA j= 9x WB2X ('B(x) ^ :B(x)) where X denotes the set of all DL-Lite concepts over .
We now come to Theorem 2. With the exception of proof steps involving
Condition 3(s2) of Definition 4, the proof technique for Theorem 2 extends the proof
technique introduced for DL-Lite. We therefore focus on 3(s2). We require a certain
interpolation property. This interpolation property has been studied before for ALC and several
of its extensions in the context of query rewriting for DBoxes and Beth definability [
Lemma 3 (Interpolation). Let T1; T2 be E L-TBoxes, T1 [ T2 j= D0 v D1 with sig(T1; D0) \ sig(T2; D1) . Then there exists a -concept F such that T1 [ T2 j= D0 v F and T1 [ T2 j= F v D1.
The following lemma is the crucial step for proving Part 1 of Theorem 2 if 3(s2) applies.
Proof. Assume C v 9r:D is given. Take the canonical model IT ;C of T and C as
defined in [
S = faG 2
K = fG j 9r:G 2 sub(T ); T j= C v 9r:Gg:
Since there is no tlc C0 of C with T j= C0 v D, by a result of [
Introduce copies X0 and X1 of any non- -predicate X. Denote by E0 and E1 the resulting concept if each non- predicate X in E is replaced by X0 and, respectively, X1. Similarly, denote by T 0 and T 1 the TBoxes obtained from T by replacing all concepts E in T by E0 and E1, respectively. The following can be proved using Lemma 3: Fact. For all G 2 K: T 0 [ T 1 6j= G0 v D1.
Now one can take the canonical models JG := IT 0[T 1;G0 for any G 2 K and obtain for aG := aG0 that aG 62 (D1)JG . Let AG; be the -reduct of the ABox corresponding to JG and assume that the Ind(AG; ) are mutually disjoint, for G 2 K, and that aG 2 Ind(AG; ), for all G 2 K. Introduce two copies A1G; and A2G; of AG; , for G 2 K. We denote the elements of the first copy by (a; 1), for a 2 Ind(AG; ) and the elements of the second copy by (a; 2), for a 2 Ind(AG; ). Define the ABox A by taking two fresh concept names A1 and A2 and the union of AS [ SG2K A1G; [ A2G; and the assertions r(aC ; (aG; 1)); r(aC ; (aG; 2)), A1(aG; 1), and A2(aG; 2), for every G 2 K and A1(aD0 ), for every tlc 9r:D0 of C. One can show that the disjunction property is violated: T ; A j=c( ) 9r:(A1 u D)(aC ) _ 9r:(A2 u D)(aC ) and T ; A 6j=c( ) 9r:(Ai u D)(aC ), for i = 1; 2. o 5
We have presented first results regarding the non-uniform complexity of query answering in the presence of open and closed world predicates. We expect the proposed extension of CQs with FO-plugins to be useful in practical applications where closed predicates are important and safe TBoxes suffice. As future work, we plan to extend our investigation to more expressive DLs. For example, we conjecture that transparent dichotomy results can still be obtained for the extensions of DL-Litecore and E L with role hierarchies.
Acknowledgments. Carsten Lutz and I˙nanc¸ Seylan were supported by the DFG SFB/TR 8 “Spatial Cognition”.