Conjunctive Query Answering in the Description Logic EL Using a Relational Database System

1 Introduction

One of the main applications of ontologies in computer science is in data access, where an ontology formalizes conceptual information about data that is stored in one or multiple data sources, and this information is used to derive answers to queries over such sources. This general setup plays a central role in, e.g., ontology-based information integration and peerto-peer data management. In these and similar applications, Description Logics (DLs) are popular ontology languages and conjunctive queries (CQs) are used as a fundamental querying tool. Hence, efficient and scalable approaches to CQ answering over DL ontologies are of great interest.

Calvanese et al. have argued that, in the short run, true scalability of conjunctive query answering over DL ontologies can only be achieved by making use of standard relational database management systems (RDBMSs) [2007b]. Alas, this is not straightforward as RDBMSs are unaware of TBoxes (the DL mechanism for storing conceptual information) and adopt the closed-world semantics. In contrast, ABoxes (the DL mechanism for storing data) and the associated ontologies employ the open-world semantics. Existing approaches to overcome these differences have serious limitations. For example, the approach of [Calvanese et al., 2007b] applies only to DLs with data complexity of CQ answering in LOGSPACE whereas for many DLs, this problem is complete for PTIME or co-NP. In particular, the above approach cannot be directly used for DLs that admit qualified existential restrictions, which play an important role in many ontologies. This limitation is shared by the rule-based approach presented in [Wu et al., 2008].

In this paper, we present a novel approach to using RDBMSs for CQ answering over DL ontologies that, in particular, accommodates qualified existential restrictions. We apply it to the EL family of DLs [Baader et al., 2008], whose members are widely used as ontology languages for largescale bio-medical ontologies such as SNOMED CT and (early versions of) NCI. Our main result shows that CQ answering in ELHdr ⊥ , the extension of basic EL with the bottom concept, role inclusions, and domain and range restrictions, can be implemented using an RDBMS. This result is of particular relevance as ELHdr ⊥ can be viewed as the core of the designated OWL-EL profile of the upcoming OWL Version 2 ontology language. We evaluate our approach using the IBM DB2 RDBMS and show that it scales to TBoxes with more than 50.000 axioms where answer times typically range from a fraction of a second to a few seconds.

The central idea of our approach is to incorporate the consequences of the TBox T into the relational instance corresponding to the given ABox A. To capture this formally, we introduce the notion of combined first-order (FO) rewritability. A DL enjoys combined FO rewritability if it is possible to effectively rewrite (i) A and T into an FO structure (independently of q) and (ii) q and (possibly) T into an FO query q∗ (independently of A) such that query answers are preserved, i.e, the answer to q∗ over the FO structure is the same as the answer to q over A and T . The connection to RDBMSs then relies on the well-known equivalence between FO structures and relational databases, and FO queries and SQL queries. The notion of combined FO rewritability generalizes the notion of FO reducibility, where the TBox is incorporated into the query q rather than into the ABox A while the ABox itself is used as a relational instance without any modification [Calvanese et al., 2007b]. Notable properties of our approach include:

1. It applies to DLs for which data complexity of CQ answering is PTIME-complete, such as ELHdr ⊥ .
2. For ELHdr ⊥ , both rewriting steps can be carried out in polynomial time and produce only a polynomial blowup; moreover, the query rewriting only depends on the input CQ and the role inclusions in T (usually only few), but not on T 's concept inclusions (usually very many).

In contrast and to the best of our knowledge, all existing approaches to (non-combined) FO reducibility generate a rewritten query of size mn , with m the number of symbols in the query and the TBox and n the size of the query.

In addition, we analyze the limitations of our approach and show that DLs with data complexity exceeding PTIME cannot enjoy polynomial combined FO rewritability, where the expansion of the ABox due to rewriting (but not necessarily of query rewriting) is bounded by a polynomial. We believe that this is a significant result as combined FO rewritability involving an exponential blowup of the data does not seem to be practical. In particular, the result implies that expressive DLs such as ALC cannot enjoy polynomial FO rewritability. The same holds even for EL enriched with negated ABox assertions and negated query atoms. For the latter case, we sketch an approach to query answering that involves only a polynomial blowup of the ABox, but is incomplete (in a way precisely characterized by an alternative semantics).

Due to space limitations, detailed proofs are given in the technical report [Lutz et al., 2009].

2 Preliminaries

In ELHdr ⊥ , concepts are built according to the syntax rule

where, here and in the remaining paper, A ranges over concept names taken from a countably infinite set NC, r ranges over role names taken from a countably infinite set NR, and C,D range over concepts. A TBox is a finite set of concept inclusions C ⊑ D, role inclusions r ⊑ s, domain restrictions dom(r) ⊑ C, and range restrictions ran(r) ⊑ C. An ABox is a finite set of concept assertions A(a) and role assertions r(a, b), where a, b range over a countably infinite set NI of individual names. A knowledge base is a pair (T , A) with T a TBox and A an ABox.

The semantics of concepts, inclusions, restrictions, and assertions is given as usual in terms of an interpretation I = (ΔI , ·I ); we refer to [Baader et al., 2008] for details. An interpretation I is a model of a TBox T (ABox A) if it satisfies all inclusions and restrictions in T (assertions in A). It is a model of a knowledge base K = (T , A) if it is a model of T and A. A knowledge base that has a model is consistent. For a concept inclusion, role inclusion, or assertion α, we write K |= α if α is satisfied in all models of K.

Let NV be a countably infinite set of variables. Together, the sets NV (of variables) and NI (of individual names) form the set NT of terms. A first-order (FO) query q is a first-order formula built from NT and the unary and binary predicates from NC and NR. We write q = ϕ(⃗v) to indicate that q is the FO formula ϕ whose free variables are among the variables ⃗v = v1, . . . , vk. Variables in ⃗v are the answer variables of q and q is k-ary if there are k answer variables. A conjunctive query is an FO query q of the form ∃⃗u.ψ(⃗u,⃗v), where ψ is a conjunction of concept atoms A(t) and role atoms r(t, t′ ). The variables in ⃗u are the quantified variables of q. We use var(q) to denote the set of all variables in ⃗u and ⃗v, qvar(q) for the set of quantified variables, avar(q) for the answer variables, and term(q) for the terms in q. Abusing notation, we write α ∈ q if the concept or role atom α occurs in q.

For I an interpretation, q = ϕ(⃗v) a k-ary FO query, and a1, . . . , ak ∈ NI, we write I |= q[a1, . . . , ak] if I satisfies q with vi assigned to aIi , 1 ≤ i ≤ k. A certain answer for a k-ary conjunctive query q and a knowledge base K is a tuple (a1, . . . , ak) such that a1, . . . , ak occur in K and I |= q[a1, . . . , ak] for each model I of K. We use cert(q, K) to denote the set of all certain answers for q and K. This defines the query answering problem studied in this paper: given an ELHdr ⊥ knowledge base K and a CQ q, to compute cert(q, K).

Note that CQ answering generalizes instance checking, the problem of deciding whether K |= C(a), for C an ELHdr ⊥ - concept: any such C can be easily unfolded into a conjunctive query qC such that a ∈ cert(qC, K) iff K |= C(a).

In the remainder of this paper we use the unique name assumption: aI ̸= bI for all interpretations I and all a, b ∈ NI with a ̸= b. It is not hard to see that this has no impact on certain answers. We also assume, w.l.o.g., that (i) queries contain only individual names that occur in the KB against which they are asked, (ii) TBoxes do not contain domain restrictions, (iii) TBoxes contain exactly one range restriction per role name, (iv) if K |= r ⊑ s and ran(r) ⊑ C, ran(s) ⊑ D are in T , then C ⊑T D, and (v) there are no r, s ∈ NR with r ̸= s, K |= r ⊑ s, and K |= s ⊑ r. Justifications for these assumptions are given in [Lutz et al., 2009].

3 ABox Rewriting / Canonical Models

The rewriting of the ABox consists of an extension of the ABox to a canonical model of the knowledge base. For the remainder of this section, we fix an ELHdr ⊥ -KB K = (T , A). We use sub(T ) to denote the set of all subconcepts of concepts that occur in T , rol(T ) for the set of role names that occur in T , and Ind(A) for the set of individual names that occur in A. We also use ranT (r) to denote the (unique) concept C with ran(r) ⊑ C ∈ T , and set

assuming NI ∩NIaux = ∅. The canonical model IK of K is defined in Figure 1. It is standard to show the following (similar to proofs in [Baader et al., 2005b; Lutz and Wolter, 2007]):

Proposition 1. If K is consistent, then IK is a model of K.

Note that the cardinality of ΔIK is only quadratic in the size of K, and linear if T does not contain range restrictions. The model IK can be computed in polynomial time since subsumption and instance checking in ELHdr ⊥ can be decided in poly-time [Baader et al., 2008]. In fact, there is an easy rulebased procedure for computing the canonical model and the rules can be implemented as standard database operations; see the workshop publication [Lutz et al., 2008] for details. Consistency of K can also be checked in polynomial time [Baader et al., 2008]. IK can be used for instance checking: it can be shown that K |= C(a) iff IK |= C(a), for K consistent, C an ELHdr ⊥ -concept, and a ∈ Ind(A). Unfortunately, an analogous statement for conjunctive queries, namely (a1, . . . , ak) ∈ cert(q,K) iff IK |= q[a1, . . . , qk],

ΔIK := Ind(A) ⊎NIaux and aIK := a for all a ∈ Ind(A) AIK := {a ∈ Ind(A) | K |= A(a)} ∪ {xC,D ∈ NIaux | K |= C ⊓D ⊑ A} rIK := {(a, b) ∈ Ind(A) × Ind(A) | s(a, b) ∈ A and K |= s ⊑ r} ∪ {(a, xC,D) ∈ Ind(A) × NIaux | K |= ∃s.D(a), ranT (s) = C, and K |= s ⊑ r} ∪ {(xC,D, xC′ ,D′) ∈ NIaux ×NIaux | K |= C ⊓D ⊑ ∃r.D′ , ranT (s) = C′ , and K |= s ⊑ r}

does not hold. This is due to two reasons, the first one being that IK may contain unnecessary elements:

Example 2. Take K1 = (T1,A1) with T1 = {A ⊑ A} and A1 = {B(a)}, and q1 = ∃u.(B(v) ∧ A(u)) . Then x⊤,A ∈ AIK1 and so IK1 |= q1[a], but clearly a ̸∈ cert(q1,K1).

This deficiency of IK is easily repaired by restricting it to elements reachable from some aIK with a ∈ Ind(A). Formally, we define Ind(A)I = {aI | a ∈ Ind(A)} for each interpretation I. A path in I is a finite sequence d0r1d1 · · · rndn, n ≥ 0, where d0 ∈ Ind(A)I and (di, di+1) ∈ rI i+1 for all i < n. We use pathsA(I) to denote the set of all paths in I and for all p ∈ pathsA(I), tail(p) to denote the last element dn in p.

Now I rK denotes the restriction of IK to those d ∈ ΔIK for which there exists a p ∈ pathsA(IK) such that d = tail(p). Then I rK provides the correct certain answers to the query q1 from Example 2. A much more severe deficiency of IK (and I rK) is the following:

Example 3. Take K2 = (T2,A2) with T2 = {A ⊑ ∃r.B ⊓ ∃s.B} and A2 = {A(a)}, and q2 = ∃u.(r(v, u) ∧ s(v, u)). Then (a, x⊤,B) ∈ rIK2 and (a, x⊤,B) ∈ sIK2 and therefore IK2 |= q2[a], but clearly a /∈ cert(q2,K2).

In principle, this problem can be overcome by replacing I rK with its unraveling into a less constrained, tree-like model. In the following, we introduce unraveling as a general operation on models. Let R be the set of role inclusions in K. The (A,R)-unraveling J of I is defined as follows:

where "·" denotes concatenation. Denote by UK the (A,R)- unraveling of I rK. Notice that the construction of UK from I rK does not depend on the concept inclusions in T , but only on R. The following result is proved similarly to the analogous result for the DL ELI f in [Krisnadhi and Lutz, 2007].

Proposition 4. If K is consistent, then for all k-ary conjunctive queries q and all a1, . . . , ak ∈ Ind(A), we have (a1, . . . , ak) ∈ cert(q, K) iff UK |= q[a1, . . . , ak].

By Proposition 4, UK gives the correct answers to conjunctive queries, but in contrast to I rK, it is typically infinite. Thus, we do not use it as a target for ABox rewriting and work with I rK. To overcome the problem indicated in Example 3 and similar ones (see [Lutz et al., 2008]), we use query rewriting.

4 Query Rewriting

Our aim is to rewrite the original CQ q into an FO query q∗R such that UK |= q[a1, . . . , ak] iff I rK |= q∗R[a1, . . . , ak] for all a1, . . . , ak ∈ Ind(A). By Proposition 4, we obtain the desired answers cert(q,K) by using I rK (the rewriting of A) as a relational database instance and replacing q with q∗R. We now formulate the main result of this paper.

Theorem 5. For every finite set of role inclusions R and kary CQ q, one can construct in polynomial time a k-ary FO query q∗R such that for all ELHdr ⊥ -KBs K = (T , A) with R the set of role inclusions in T and all a1, . . . , ak ∈ Ind(A), we have I rK |= q∗R[a1, . . . , ak] iff UK |= q[a1, . . . , ak].

In the remainder of this section, we show how to construct q∗R. The query q∗R contains one additional unary predicate Aux(x); we assume that Aux is always interpreted as ΔIrK \ Ind(A)IrK in I rK. Fix a finite set R of role inclusions and a k-ary conjunctive query q. To construct q∗R, we use several auxiliary definitions. Let ∼q denote the smallest relation on term(q) that includes the identity relation, is transitive, and satisfies the following closure condition:

The relation ∼q is central to our rewriting procedure. To see this, let K = (T ,A) be such that the role inclusions of T coincide with R. Intuitively, UK is produced from I rK by keeping the Ind(A)-part intact and relaxing the Aux-part into a collection of trees. To understand (∗), first assume t = t′ . Then (∗) describes a non-tree situation in the query since t = t′ has two predecessors s and s′ . Therefore, any match of the query in I rK that maps t to the Aux-part should map s and s′ to the same element; otherwise such a match cannot be reproduced in UK. The case where t ∼q t′ instead of t = t′ can be understood inductively.

It is not hard to verify that ∼q is an equivalence relation and can be computed in time polynomial in the size of q. For t ∈ term(q), we use [t] to denote the equivalence class of t w.r.t. ∼q and define, for any equivalence class ζ of ∼q, the sets:

For R ⊆ NR and r ∈ NR, r is called an implicant of R if R |= r ⊑ s for all s ∈ R. It is called a prime implicant if, additionally, R ̸|= r ⊑ r′ for all implicants r′ of R with r ̸= r′ . By assumption (v) in Section 2, there is a prime implicant for any set R ⊆ NR for which there is an implicant. We define:

• Fork= is the set of pairs (pre(ζ), ζ) with pre(ζ) of cardinality at least two;

• Fork̸= is the set of variables v ∈ qvar(q) such that there is no implicant of in([v]);
• ForkH is the set of of pairs (I, ζ) such that pre(ζ) ̸= ∅, there is a prime implicant of in(ζ) that is not contained in in(ζ), and I is the set of all prime implicants of in(ζ);
• Cyc is the set of variables v ∈ qvar(q) such that there are r0(t0, t′0 ), . . . , rm(tm, t′m), . . . , rn(tn, t′n ) ∈ q, n,m ≥ 0, with v ∼q ti for some i ≤ n, t′i ∼q ti+1 for all i < n, and t′n ∼q tm.

It is not hard to see that Fork=, Fork̸=, ForkH, and Cyc can be computed in time polynomial in the size of q. For each equivalence class ζ of ∼q, choose a representative tζ ∈ ζ and if pre(ζ) ̸= ∅, choose a tpre ζ ∈ pre(ζ). For q = ∃⃗u.ψ, the rewritten query q∗R is now defined as ∃⃗u.(ψ ∧ ϕ1 ∧ ϕ2 ∧ ϕ3), where ϕ1, ϕ2, and ϕ3 are as follows:

We can show that q∗R is as required [Lutz et al., 2009]. The following examples illustrate the definition of q∗R. Since ϕ3 is simply true when R = ∅, we omit it in this case.

1. Let R = ∅ and consider q = ∃u.ψ with ψ = r(v, u) ∧ r(v′ , u). This query illustrates the role of Fork=. ∼q consists of the equivalence classes {v, v′ } and {u}. We have pre({u}) = {v, v′ } and in({u}) = {r}. Hence Fork= = {({v, v′ }, {u})} and Fork̸= = ForkH = Cyc = ∅. We obtain q∗R = ∃u.(ψ ∧ ¬Aux(v) ∧ ¬Aux(v′ ) ∧ (Aux(u) → v = v′ )).

(2) Let R = ∅ and consider q = ∃u.(r(v, u) ∧ s(u, u)). This query illustrates the role of Cyc. We have u ∈ Cyc and so

(3) Let R = ∅ and consider q = ∃u.(r(v, u) ∧ s(v, u)) from Example 3. This query illustrates the role of Fork̸=. We have in({u}) = {r, s}. There is no implicant of in({u}) in in({u}) and thus u ∈ Fork̸=. We obtain

For R = {s ⊑ r} and the same query q, s is an implicant of in({u}) in in({u}). Thus u ̸∈ Fork̸=. Observe that ForkH = ∅ as the prime implicant s of in({u}) is contained in in({u}).

Finally, assume R = {r0 ⊑ r, r0 ⊑ s}. Again u ̸∈ Fork̸=, but now the prime implicant r0 of in({u}) is not contained in in({u}). Thus, ForkH = {({r0}, {u})} and we obtain

(4) For queries qC = ∃⃗v.ψ that result from the unfolding of an EL-concept C or have no quantified variables almost no query rewriting is needed: in both cases we have

(5) Let R = ∅ and let q = ∃v0, . . . , v7.ψ be the query shown in Figure 2, where all variables are quantified. Then ∼q consists of the equivalence classes {v0, v1, v2}, {v3, v4, v5}, {v6}, and {v7}. Assume that the chosen representative for {v3, v4, v5} is v3. Then, we have

In the following, we comment on certain relevant properties of q∗R and on consequences of our approach regarding the computational complexity of query answering in ELHdr ⊥ . Firstly, the size of q∗R is bounded by O(nm), where n is the size of q and m is max{1, |R|}. To see this, note that the number of conjuncts in of ϕ1 is bounded by the number of variables in q. For ϕ2, let Fork= = {(T1, ζ1), . . . , (Tℓ, ζℓ)}. Then |T1|+· · ·+|Tℓ| is bounded by the number of role atoms in q, and thus the size of ϕ2 is O(n). Finally, the number of conjuncts in ϕ3 is bounded by the number of quantified variables in q and each conjunct has at most m disjuncts. Note that q∗R is thus of size O(n) when R = ∅.

Secondly, since ψ is a conjunct of the body of q∗R it is readily checked that q∗R is domain independent, and thus can be expressed as an SQL query. Moreover it is of the form ∃⃗u.ψ with ψ quantifier-free. Thus, we obtain that the combined complexity of deciding whether K |= q[a1, . . . , ak] is in NP: construct (in poly-time) I rK and q∗R = ∃⃗u.ψ, then check whether I rK |= ∃⃗u.ψ[a1, . . . , ak] using the obvious NP algorithm for model checking this class of formulas. Since an NP lower bound is trivial, we obtain NP-completeness. See [Kr¨otzsch et al., 2007; Rosati, 2007] for similar results regarding other variants of EL.

5 Implementation and Experiments

To validate the value of the proposed approach, we have conducted a series of experiments based on the NCI thesaurus (version 08.08d), which is a well-known ontology from the bio-medical domain [Sioutos et al., 2006]. We have extracted an EL-TBox that contains approximately 65 thousand (65K) primitive concept names, 70 primitive roles, and over 70K concept inclusions and concept definitions. The auxiliary part of canonical models, which is independent of the ABox, consists of 702K concept assertions and 171K role assertions (tuples). For the experiments reported below, we used the IBM DB2 DBMS (version 9.5.0 running on SUN Fire-280R server with two UltraSPARC III 1.2GHz CPUs, 4GB memory, and 1TB storage under Solaris 5.10).

For rewriting ABoxes into canonical models, we have used a rule-based approach implemented via iterated querying; see [Lutz et al., 2008] for more details. As relational systems are not optimized to handle tens of thousands of relatively small relations, one for each concept and role name in the ontology, we have used only two relations to represent I rK:

acbox(conceptid,indid)and arbox(roleid,domain-indid,range-indid),

where conceptid and roleid are numerical identifiers for concept names and roles names, indid, domain-indid, and range-indid are numerical identifiers for individuals from NI ∪ NIaux, acbox represents concept memberships, and arbox role memberships. Indexes were generated on the attributes conceptid,indid and on roleid,domain-indid and roleid,range-indid, using B+trees. We distinguish individuals from NI and NIaux by positive and negative identifiers, and thus need not store Aux as a relation. As an example for this representation, take the query q = Nerve(x)∧¬Aux(x), which translates into the SQL statement

select indid from acbox where conceptid=141723 and indid > 0

Data sets (ABox instances) for our experiments were generated randomly. When generating concept assertions, we have focused on most specific concept names, i.e., concept names without any subsumees in the TBox. The generation of role assertions was guided by the domain and range restrictions in NCI. The numbers of concept and role assertions in the initial and rewritten ABoxes used in our experiments are reported in Figure 3 in thousands/millions. Due to implementation particularities of existing DB systems, ABox rewriting took up to several hours. We point out that (i) this high time consumption is not inherent to our approach and (ii) ABox rewriting can be implemented as an offline task in typical applications such as online analytical processing (OLAP) and data warehousing.

Figure 3 summarizes the running times (in seconds) for each of the test queries for varying sizes of data; for each query we list the number of concept and role atoms in parentheses; the structure of the queries ranges from simple chains (Q1) and star queries (Q2,Q3,Q4) to queries with cycles in their bodies (Q5). We show only a few representative samples here.

The experimental results can be interpreted as follows. Firstly, the rewriting of moderately-sized ABoxes into the canonical model I rK is well within the storage and query capabilities of existing relational technology. Secondly, query performance scales well even when the naive physical design described above is used. Thirdly, query rewriting does not increase the query processing times; the performance of rewritten queries is almost identical to the performance of the original queries over the completed ABox.

6 Limitations / Negation

Recall from Section 1 that a DL enjoys polynomial combined FO rewritability if it has combined FO rewritability such that the blowup of ABox rewriting (but not necessarily of query rewriting) is at most polynomial. Since ABoxes in realistic applications are large, combined FO rewritability that is not polynomial in this sense does not seem to be of much use. The following result gives a fundamental limitation of polynomial combined FO rewritability. Note that ground CQ answering, where a CQ may contain only individual names but not variables, is the decisional variant of CQ answering.

1 This time is solely due to a large size of the result (60M tuples).

Theorem 6. If the data complexity of ground CQ answering in a DL L is not in PTIME, then L does not enjoy polynomial combined FO rewritability.

Proof. We show the contrapositive. Assume that L enjoys polynomial combined FO rewritability, i.e., there are effectively computable mappings δ that takes each L-TBox K = (T ,A) to a first-order structure δ(K) and γ that takes each pair (q, T ), with q a k-ary conjunctive query and T an L-TBox, to a first-order formula γ(q, T ) with k free variables such that δ can be computed in polynomial time, the size of δ(K) is polynomial in the size of K for all K, and the following condition holds: for all combined L-KBs K = (T , A), all k-ary conjunctive queries q, and all tuples (a1, . . . , ak) ∈ NI, K |= q[a1, . . . , ak] iff δ(K) |= γ(q, T )[a1, . . . , ak].

Then the data complexity of ground CQ answering in L is in PTIME: to check whether K |= q with q ground, we can compute δ(K) in polynomial time and γ(q, T ) in constant time (as the size of q and T is constant), and then use FO model checking to decide whether δ(K) |= γ(q, T ). The latter can be done in LOGSPACE. ❏

For expressive DLs such as ALC and SHIQ, the data complexity of ground CQ answering is co-NP-hard, thus Theorem 6 implies that these DLs do not enjoy polynomial combined FO rewritability unless PTIME = co-NP.

In many applications, it is natural to admit also negated concept assertions in the ABox and to extend conjunctive queries with negated concept atoms in order to query the resulting ABoxes, see e.g. [Patel et al., 2007]. Let us call ABoxes, queries, and KBs of this form literal. The result stated in Theorem 6 also applies to literal KBs and literal queries. Since the data complexity of literal CQ answering over literal EL-KBs (where EL is ELHdr ⊥ without ⊥, role hierarchies, and domain and range restrictions) is co-NP-hard [Schaerf, 1993], it follows that even this mild extension of EL does not enjoy polynomial combined FO rewritability.

However, there is still a (pragmatic, yet formal) way to add negation to our approach. In the following, we sketch an incomplete approach to literal CQ answering over literal ELHdr ⊥ -KBs. Its incompleteness can be precisely characterized in terms of an epistemic semantics for negated concept atoms in literal CQs, inspired by [Calvanese et al., 2007a].

As a preliminary, we assume standard names, i.e., interpretation domains ΔI have to be a subset of the (countably infinite) set NI of individual names and aI = a for all I and all a ∈ NI. For a literal ELHdr ⊥ -KB K, an interpretation I, and a literal CQ q = ∃⃗u.ψ(⃗u, ⃗v) with ⃗v = v1, . . . , vk, we set I |=e q[a1, . . . , ak] iff there exists a variable assignment π with π(vi) = ai for 1 ≤ i ≤ k and

• I |=π α for all positive atoms α in ψ,
• K |= ¬A(a) for all ¬A(a) in ψ with a ∈ NI, and
• K |= ¬A(π(v)) for all ¬A(v) in ψ with v ∈ NV.

Now set K |=e q[a1, . . . , ak] iff I |=e q[a1, . . . , ak] for all models I of K with standard names. Thus, answers to negated atoms do not depend on a concrete interpretation I, but only on deducibility. Epistemic semantics is sound: every answer is also an answer under the standard semantics (but not vice versa); it is also conservative: it yields the same answers as standard semantics when either the KB or the query does not contain negation. An example for which the epistemic semantics is different from the standard semantics is given by A = {A′ (a), ¬A(a)}, T = {A′ ⊑ ∃r.⊤, ∃r.B ⊑ A}, and q = ∃u.r(a, u) ∧ ¬B(u). Then K |= q but K ̸|=e q.

We give a simple (and poly-time) reduction of epistemic literal CQ answering over literal ELHdr ⊥ -KBs to standard CQ answering over ELHdr ⊥ -KBs. Via the rewritings presented in the main part of this paper, the reduction enables the use of RDBMSs also for the case of ELHdr ⊥ with negation (under the epistemic semantics).

Given a consistent literal ELHdr ⊥ -KB K = (T ,A) and a literal query q, replace every literal ¬A in q with a fresh concept name A. Additionally, add ⊤ ⊑ A to T whenever T |= A ⊑ ⊥, and A(a) to A for all a ∈ Ind(A) with K |= ¬A(a), and then remove all negated assertions from A. Call the result K′ = (T ′ ,A′ ) and q′ .

Theorem 7. Let K be a consistent literal ELHdr ⊥ -KB. Then K′ can be computed in polynomial time and K |=e q[a1, . . . , ak] iff K′ |= q′ [a1, . . . , ak] for all literal CQs q and all a1, . . . , ak ∈ Ind(A).

7 Conclusion

We have proposed a novel approach to CQ answering in DLs using RDBMSs. Unlike previous approaches, it can be used also for DLs for which the data complexity is between LOGSPACE and PTIME. In particular, this includes DLs that fully admit existential restrictions (both on the left- and righthand side of concept inclusions; see [Calvanese et al., 2006]) and paves the way to using RDBMSs for CQ answering in the EL family of DLs. Our experiments exhibit a promising performance even without a sophisticated physical design. One drawback of our approach is the blowup of the data, which is polynomial but still considerable on large data sets. As future work, it might be interesting to reduce this blowup by incorporating the TBox partly into the data and partly into the query. We will also develop effective approaches to update the canonical model/auxiliary data when assertions are added to or deleted from the ABox.