=Paper=
{{Paper
|id=Vol-188/paper-7
|storemode=property
|title=Tailoring OWL for data intensive ontologies
|pdfUrl=https://ceur-ws.org/Vol-188/sub13.pdf
|volume=Vol-188
|authors=Giuseppe De Giacomo,Domenico Lembo,Maurizio Lenzerini and Riccardo Rosati
|dblpUrl=https://dblp.org/rec/conf/owled/GiacomoLLR05
}}
==Tailoring OWL for data intensive ontologies==
https://ceur-ws.org/Vol-188/sub13.pdf
Tailoring OWL for Data Intensive Ontologies
Diego Calvanese1 , Giuseppe De Giacomo2 , Domenico Lembo2 ,
Maurizio Lenzerini2 , Riccardo Rosati2
1 2
Faculty of Computer Science Dip. di Informatica e Sistemistica
Free University of Bozen-Bolzano Università di Roma “La Sapienza”
Piazza Domenicani 3 Via Salaria 113
I-39100 Bolzano, Italy I-00198 Roma, Italy
calvanese@inf.unibz.it lastname@dis.uniroma1.it
Abstract. The idea of using ontologies as a conceptual view over data reposi-
tories is becoming more and more popular. In these contexts, data are typically
very large (much larger than the intentional level of the ontologies), and query
answering becomes the basic reasoning services. In these contexts query answer-
ing should be very efficient on the data, and currently the only technology that is
available to deal with large amounts of data is the one provided by relational data
management systems (RDBMS). In this paper we advocate that for such contexts
a suitable fragment of OWL-DL should be devised. Such a fragment must allow
forms of query answering that exploit RDBMS when reasoning on the data, while
it must include the main modeling features of conceptual models like UML class
diagrams and ER diagrams. In particular it must include cyclic assertions, ISA
on concepts, inverses of roles, role typing, mandatory participation to roles, and
functional restrictions on roles. Also the query language should go beyond the
expressive capabilities of concept expressions in description logics, and include
at least conjunctive queries (corresponding to the select-project-join fragment of
SQL). We discuss this issues by exhibiting a fragment of OWL-DL that includes
all such features, namely DL-Lite, and showing that such a fragment is essentially
maximal.
1 Introduction
The idea of using ontologies as a conceptual view over data repositories is becoming
more and more popular. For example, in Enterprise Application Integration Systems,
Data Integration Systems [16], and the Semantic Web [13], data become instances of
concepts in ontologies. In these contexts, data are typically very large and dominate
the intentional level of the ontologies. Hence, when measuring the computational com-
plexity of reasoning, the most important parameter is the size of the data, i.e., one is
interested in data complexity [20]. While in all the above mentioned contexts one could
still accept reasoning that is exponential on the intentional part, it is mandatory that
reasoning is polynomial (actually less – see later) in the data. A second fundamental
requirement is the possibility to answer queries over an ontology that are more com-
plex than the simple queries (i.e., concepts and roles) usually considered in Description
Logics (DLs) research.
Traditionally, research carried out in DLs has not paid much attention to data com-
plexity (see Section 4 for a detailed discussion), and only recently efficient management
of large amounts of data has become a primary concern in ontology reasoning sys-
tems [14, 10]. Unfortunately, research on the trade-off between expressive power and
computational complexity of reasoning has shown that many DLs with efficient, i.e.,
worst-case polynomial time, reasoning algorithms lack the modeling power required
for capturing conceptual models (such as UML class diagrams and Entity-Relationship
diagrams) and basic ontology languages. On the other hand, whenever the complexity
of reasoning is exponential in the size of the instances (as for example for OWL-DL,
in Racer1 , and in [9]), there is little hope for effective instance management. Indeed,
the only technology that is currently available to deal with complex queries over large
amounts of data is the one provided by relational data management systems (RDBMS),
and it cannot be directly exploited in these cases.
In this paper we advocate that for those contexts where ontologies are used to access
large amounts of data, a suitable fragment of OWL-DL should be devised, specifically
tailored to capture conceptual modeling constructs, while keeping query answering effi-
cient. Specifically, efficiency of query answering should be achieved by delegating data
storage and query answering to an RDBMS. The fragment should include the main
modeling features of conceptual models, which are also at the base of most ontology
languages. These features include cyclic assertions, ISA on concepts, inverses on roles,
role typing, mandatory participation to roles, and functional restrictions of roles. Also,
the query language should go beyond the expressive capabilities of concept expressions
in DLs, and include at least conjunctive queries (corresponding to the select-project-join
fragment of SQL).
We present a DL, called DL-Lite, that exhibits all the above characteristics [8]. The
distinguishing features of DL-Lite are that the extensional component of a knowledge
base, the ABox, is maintained by an RDBMS in secondary storage, and that query
answering can be performed as a two step process: in the first step, a query posed
over the knowledge base is reformulated, taking into account the intensional component
(the TBox) only, obtaining a union of conjunctive queries; in the second step such a
union is directly evaluated over the ABox, and the evaluation can be carried out by an
SQL engine, taking advantage of well established query optimization strategies. Since
the first step does not depend on the data, and the second step is the evaluation of a
relational query over a databases, the whole query answering process is in L OG S PACE
in the data [1].
We show also that DL-Lite is essentially the maximal fragment exhibiting such a
desirable property, and allowing one to delegate query evaluation to a relational en-
gine [8]. Indeed, even slight extensions of DL-Lite make query answering (actually
already instance checking, i.e., answering atomic queries) at least NL OG S PACE in data
complexity, ruling out the possibility that query evaluation could be performed by a
relational engine.
2 DL-Lite
As usual in DLs, DL-Lite allows for representing the domain of interest in terms of
concepts, denoting sets of objects, and roles, denoting binary relations between objects.
1
http://www.sts.tu-harburg.de/˜r.f.moeller/racer/
In DL-Lite2 , concepts and roles are defined as follows:
C ::= A | ⊥ | ∃R | C1 u C2
R ::= P | P −
where A denotes an atomic concept and P denotes an atomic role; R denotes a (generic)
role, which can either be an atomic role or its inverse; C (possibly with subscript)
denotes a (generic) concept that can be either an atomic concept, the empty concept
⊥, a concept of the form ∃R, i.e., the standard DL construct of unqualified existential
quantification on roles, or the conjunction of two concepts. Note that we allow for a
limited form of negation through ⊥ (sufficient to capture disjointness of concepts), but
we do not allow for disjunction.
A DL-Lite knowledge base (KB) K = hT , Ai is constituted by two components: a
TBox T , used to represent intensional knowledge, and an ABox A, used to represent
extensional information. DL-Lite TBox assertions are of the form
C1 v C2 inclusion assertion
(funct R) functionality assertion
An inclusion assertion expresses that a concept C1 is subsumed by a concept C2 , while a
functionality assertion expresses the (global) functionality of a role (atomic or inverse).
As for the ABox, DL-Lite allows for assertions of the form:
C(a), R(a, b) membership assertions
where a and b are constants. These assertions state respectively that the object denoted
by a is an instance of the concept C, and that the pair of objects denoted by (a, b) is an
instance of the role R.
Although DL-Lite is quite simple from the language point of view, it allows for
querying the extensional knowledge of a KB in a much more powerful way than usual
DLs, in which only membership to a concept or to a role can be asked. Specifically, DL-
Lite allows for using conjunctive queries of arbitrary complexity. A conjunctive query
(CQ) q over a knowledge base K is an expression of the form q(x) ← ∃y.conj (x, y),
where x are the so-called distinguished variables, y are existentially quantified vari-
ables called the non-distinguished variables, and conj (x, y) is a conjunction of atoms
of the form C(z), or R(z1 , z2 ), where C and R are respectively a concept and a role in
K, and z, z1 , z2 are constants of a fixed infinite domain ∆ (see later) or variables in x
or y.
The semantics of DL-Lite is given in terms of interpretations over a fixed infinite
domain ∆3 . We assume to have one constant for each object, denoting exactly that ob-
ject. In other words, we have standard names [17], and we will not distinguish between
the alphabet of constants and ∆.
2
The variant of DL-Lite presented here is a slight extension of the language presented in [8, 7],
since it allows for conjunction of concepts in the left-hand side of inclusion assertions.
3
The assumption of having a fixed interpretation domain is done for convenience in the defini-
tion of query answering (see later).
An interpretation I = (∆, ·I ) consists of a first order structure over ∆ with an
interpretation function ·I such that:
AI ⊆ ∆ ⊥I = ∅
(∃R)I = {c | ∃c0 . (c, c0 ) ∈ RI } (C1 u C2 )I = C1I ∩ C2I
PI ⊆ ∆ × ∆ (P − )I = {(c, c0 ) | (c0 , c) ∈ P I }
An interpretation I is a model of an inclusion assertion C1 v C2 if and only if
C1I ⊆ C2I ; I is a model of a functionality assertion (funct R) if (c, c0 ) ∈ RI and
(c, c00 ) ∈ RI implies c0 = c00 ; I is a model of a membership assertion C(a) (resp.,
R(a, b)) if a ∈ C I (resp., (a, b) ∈ RI ). A model of a KB K is an interpretation I that
is a model of all assertions in K. A KB is satisfiable if it has at least one model. A KB
K logically implies an assertion α if all the models of K are also models of α. A query
q(x) ← ∃y.conj (x, y) is interpreted in I as the set q I of tuples c ∈ ∆ × · · · × ∆ such
that, when we substitute the variables x with the constants c, the formula ∃y.conj (x, y)
evaluates to true in I.
Since DL-Lite deals with conjunctive queries, the basic reasoning services that are
of interest are:
– Query answering: given a query q with distinguished variables x and a KB K, re-
turn the set ans(q, K) of tuples c of constants of K such that c ∈ q I , for every
model I of K. Note that this task generalizes instance checking in DLs, i.e., check-
ing whether a given object is an instance of a specified concept in every model of
the knowledge base.
– Query containment: given two queries q1 and q2 and a KB K, verify whether q1I ⊆
q2I , for every model I of K. Note that this task generalizes logical implication of
inclusion assertions in DLs.
– KB satisfiability: verify whether a KB is satisfiable.
Although equipped with advanced reasoning services, at first sight DL-Lite might
seem rather weak in modeling intensional knowledge, and hence of limited use in prac-
tice. In fact, this is not the case. Despite the simplicity of its language and the spe-
cific form of inclusion assertions allowed, DL-Lite is able to capture the main notions
(though not all, obviously) of both ontologies, and of conceptual modeling formalisms
used in databases and software engineering, such as Entity-Relationship diagrams and
UML class diagrams. In particular, DL-Lite assertions allow us to specify: ISA, e.g.,
stating that a concept A1 is subsumed by a concept A2 , using A1 v A2 ; disjointness,
e.g., between concepts A1 and A2 , using A1 u A2 v ⊥; role-typing, e.g., stating that
the first (resp., second) component of the role P is an instance of A, using ∃P v A
(resp., ∃P − v A); participation constraints, e.g., stating that all instances of a concept
A participate to a role P as the first (resp., second) component, using A v ∃P (resp.,
A v ∃P − ); non-participation constraints, using Au∃R v ⊥; functionality restrictions
on roles, using (funct R).
Observe that DL-Lite does allow for cyclic assertions without falling into intractabil-
ity. Indeed, we can enforce the cyclic propagation of the existence of a P -successor
using the two DL-Lite inclusion assertions A v ∃P and ∃P − v A. The constraint
imposed on a model is similar to the one imposed by the ALN cyclic assertion A v
q Perfect rq,T
T reformulation
Query
A evaluation ans(q, hT , Ai)
Fig. 1. Query aswering via query evaluation
∃P u ∀P .A, though stronger, since it additionally enforces the second component of P
to be typed by A. In order to keep tractability even in the presence of cycles, DL-Lite
imposes restrictions on the use of the ∀R.C construct, which, if used together with in-
clusion assertions, immediately would lead to intractability of TBox reasoning [6] and
of query answering (cf. Table 1).
Finally, notice that DL-Lite is a strict subset of OWL-Lite, the least expressive vari-
ant of OWL4 , which presents some constructs (e.g., some kinds of role restrictions) that
cannot be expressed in DL-Lite, and that make reasoning in OWL-Lite non-tractable in
general.
3 Reasoning in DL-Lite
We discuss now reasoning in DL-Lite, and concentrate on the basic reasoning task in the
context of using ontologies to access large data repositories, namely that of answering
(conjunctive) queries over a DL-Lite knowledge base. The other forms of reasoning can
be reduced to query answering [8]. For example, to check whether K is unsatisfiable,
we can simply add the inclusion A1 u A2 v ⊥ to the TBox and the assertion A1 (a) to
the ABox (where A1 , A2 are new atomic concepts and a is new constant), and check
whether a is in the answer to the query q(x) ← A2 (x). Similarly, to check whether K
implies A v C, we can simply add the assertion A(a) to the Abox (where a is new
constant), and check whether a is in the answer to the query q(x) ← C 0 (x), where C 0
is the conjunction of atoms corresponding to the concept C.
Given the limited expressive power of DL-Lite TBoxes, it might seem that in order
to answer a query q over a KB K, we could simply build a finite first-order structure
on the basis of K, and then evaluate the query itself as an expression over this first-
order structure. Actually, it is possible to show that this is not the case. In particular, it
can be shown that, in general, given a DL-Lite KB K, there exists no finite structure S
such that, for every conjunctive query q, the set of answers to q over K is the result of
evaluating q itself over S (see [5]). This property demonstrates that answering queries
in DL-Lite goes beyond both propositional logic and relational databases.
Instead, in order to exploit query evaluation for query answering, and also properly
take into account that the size of the ABox (i.e., the data) largely dominates the size
of the TBox, we consider the query answering process as divided in two steps (cf. Fig-
ure 1):
4
http://www.w3.org/TR/owl-features/
1. First, considering the TBox T only, the user query q is reformulated into a new
query rq,T (expressed in a suitable query language LQ ).
2. Then, the reformulated query rq,T is evaluated over the ABox A only (consid-
ered as a first-order structure, i.e., a database), producing the requested answer
ans(q, hT , Ai).
Notice that, in principle, such a two steps query answering process is always pos-
sible for arbitrary TBoxes and user queries, provided we do not impose any restriction
on the query language LQ in which the reformulation rq,T is expressed. Indeed, in or-
der to ensure that the evaluation of rq,T over the ABox A produces the correct answer
ans(q, hT , Ai) (i.e., that rq,T is a perfect reformulation of q given T ), we may have
to allow for LQ to be completely general. In other words, we may need to be able to
specify in rq,T an arbitrary Turing Machine computation, possibly one that performs
full inferences over the TBox and the query. However, if we pose no restriction on LQ ,
and hence on the form of T and q, we have no guarantee that the evaluation of rq,T
over the ABox A can be performed efficiently, and hence that the separation between
query reformulation (using the TBox only) and query evaluation (over the ABox only)
makes sense from a computational complexity point of view.
As shown in [8, 7], one of the distinguishing features of DL-Lite is that the above
described two steps query answering process makes sense, and allows us to be efficient
in the size of the data. Indeed, the perfect reformulation rq,T of a conjunctive query q
over a DL-Lite KB K = hT , Ai can be expressed as a union of conjunctive queries,
i.e., a set of select-project-join SQL queries, and hence the query evaluation step can be
performed in L OG S PACE in the size of the ABox A [1]. Since the size of rq,T does not
depend on A, the data complexity (i.e., the complexity measured as a function of the
size of the ABox only) of the whole query answering algorithm is L OG S PACE.
Moreover, by storing the ABox under the control of an RDBMS, which can man-
age effectively large numbers (i.e., millions) of objects in the knowledge base, we can
delegate the query evaluation step to an SQL database engine. More precisely, we can
construct a relational database that faithfully represents an ABox A as follows. First of
all, we assume that A does not contain conjunction and ⊥. If this is not the case, we can
easily pre-process it and bring it in such a form in linear time (actually, in L OG S PACE
in the number of objects in the ABox). Let further A0 be the ABox obtained from A by
adding for each assertion R(a, b) ∈ A the implied assertions ∃R(a) and ∃R− (b). Then,
for each concept C in K that is either atomic or of the form ∃R, we define a relational
table tab C of arity 1, such that hai ∈ tab C if and only if C(a) ∈ A0 . Similarly, for each
atomic role P in K, we define a relational table tab P of arity 2, such that ha, bi ∈ tab P
if and only if P (a, b) ∈ A or P − (b, a) ∈ A. Let us call DB (A) the resulting database.
The fact that the ABox A is managed in secondary storage by an RDBMS, together with
the fact that in DL-Lite the perfect reformulation of a select-project-join SQL query can
be expressed as a set of select-project-join SQL queries that can be directly evaluated
over DB (A), allows us to completely delegate the query evaluation process to the SQL
engine of the RDBMS, and to take advantage of well established query optimization
strategies.
We have developed a prototype tool, called Q U O NTO [2] (see Figure 2), that imple-
ments the DL-Lite query answering algorithm and delegates to an RDBMS the ABox
Fig. 2. Screenshot of the Q U O NTO query answering tool
storage and the query evaluation step. Q U O NTO is able to answer queries over ABoxes
containing millions of assertions, and the limitations actually depend on the underlying
DBMS engine (currently we use MySQL).
Notice that, as soon as we extend the expressive power of DL-Lite even slightly,
we lose the possibility of delegating query evaluation to an RDBMS. Indeed, Table 1,
drawn from [7], shows bounds on the data complexity of query answering for vari-
ous DLs obtained from DL-Lite by adding various constructs (and possibly removing
some). To give a more precise account of the complexity, we distinguish between the
constructs allowed in concepts on the left-hand side of inclusion assertions (denoted by
B), and those allowed in concepts on the right-hand side of inclusion assertions (de-
noted by C). The language L1 is DL-Lite, and L2 is obtained from DL-Lite by allowing
for qualified existential quantification in C while forbidding the use of functionality as-
sertions. Similarly to DL-Lite, query answering in L2 can be performed in L OG S PACE
via query reformulation. Instead, in languages L3 , L4 , L5 , one can encode reachability
in directed graphs (essentially through the use of qualified existentials in B). Hence
query answering (actually, already instance checking) becomes NL OG S PACE-hard in
data-complexity. By further allowing for the use of conjunction in B, one can encode
Path System Accessibility (a non-linear form of reachability), and instance checking
becomes PT IME-hard (L6 , L7 , L8 ). Finally, by allowing to denote two concepts that
together cover the whole domain, conjunctive query answering becomes even coNP-
hard in data-complexity (L9 , L10 , L11 ).
The fact that the data-complexity goes beyond L OG S PACE, means actually that
query answering (resp., instance checking) requires more powerful engines than those
available in standard relational database technology. Essentially NL OG S PACE-hardness
Table 1. Data complexity of query answering in extensions of DL-Lite
Li B C R (funct R) Complexity
−
L1 A | ⊥ | ∃R | B1 u B2 A | ⊥ | ∃R | C1 u C2 P | P allowed in L OG S PACE
L2 A | ⊥ | ∃R | B1 u B2 A | ⊥ | ∃R.C | C1 u C2 P | P − not all. in L OG S PACE
L3 A | ∃P .A A P not all. NL OG S PACE-hard
L4 A A | ∀P .A P not all. NL OG S PACE-hard
L5 A A | ∃P .A P allowed NL OG S PACE-hard
L6 A | ∃P .A | A1 u A2 A P not all. PT IME-hard
L7 A | A1 u A2 A | ∀P .A P not all. PT IME-hard
L8 A | A1 u A2 A | ∃P .A P allowed PT IME-hard
L9 A | ¬A A P not all. coNP-hard
L10 A A | A1 t A2 P not all. coNP-hard
L11 A | ∀P .A A P not all. coNP-hard
Legend: A (possibly with subscript)= atomic concept, P = atomic role,
B (possibly with subscript) = left-hand side of TBox inclusion assertions,
C = right-hand side of TBox inclusion assertions, R = arbitrary role.
means that at least the power to compute transitive closure (i.e., linear recursion) is re-
quired, while PT IME-hardness essentially requires the power of Datalog. For the coNP-
hard cases a technology based on Disjunctive Datalog could be adopted. An immediate
consequence of this fact is that, as soon as we go beyond DL-Lite, we lose the possibility
of delegating query answering to data management tools and we cannot take advantage
of query optimization techniques of current industrial strength RDBMSs.
4 Discussion and related work
DL-Lite is a fragment of expressive DLs with assertions and inverses studied in the 90’s
(see [4] for an overview), which are at the base of current ontology languages such as
OWL, and for which optimized automated reasoning systems such as Fact5 , Racer, and
Pellet6 have been developed. Indeed, one could use, off-the-shelf, a system like Racer
or Pellet to perform KB satisfiability, instance checking (of concepts), and logical im-
plication of inclusion assertions in DL-Lite. Also, reasoning with conjunctive queries in
these DLs has been studied (see e.g., [9]), although not yet implemented in systems. Un-
fortunately, the reasoning procedures for these DLs are all E XP T IME-hard, and more
importantly they are not tailored towards obtaining tight bounds with respect to data
complexity. Alternative reasoning procedures that allow for clearly isolating data com-
plexity have recently been proposed, how they will work in practice still needs to be
understood: a coNP upper bound for data complexity of instance checking in an ex-
pressive DL has been shown, and a polynomial fragment has been isolated [15], though
it is open whether the technique can be extended to deal efficiently with conjunctive
queries; building on the technique in [18], coNP-completeness of answering conjunc-
5
http://www.cs.man.ac.uk/˜horrocks/FaCT/
6
http://www.mindswap.org/2003/pellet/
tive queries for an expressive DL with assertions, inverse roles, and number restrictions
(that generalize functionality) has been shown [19].
DL-Lite can also capture (the DL-subset of) RDFS7 , except for role hierarchies. In
fact, the query answering technique for DL-Lite works also for full RDFS extended
with participation constraints (i.e., inclusion assertions with ∃R on the right-hand side),
and one can show that in this case query answering is indeed L OG S PACE. However,
if we further extend RDFS with functionality assertions, it can be shown that query
answering becomes NL OG S PACE-hard. Finally, if we move from RDFS to DLP [12],
query answering becomes PT IME-hard, since DLP is a superset of L6 in Table 1.
There has been a lot of work in DLs on the boundary between polynomial and expo-
nential reasoning. This work first concentrated on DLs without the TBox component of
the KB, and led to the development of simple DLs, such as ALN , that admit polynomial
instance checking. However, for minor variants of ALN , such as ALE (where we intro-
duce qualified existential and drop number restrictions), FLE − (where we additionally
drop negated atomic concept), and ALU (where we introduce union and drop number
restrictions), conjunctive query answering is coNP-hard in data complexity [11]. If we
allow for cyclic inclusion assertions in the KB, then even subsumption in CLASSIC
and ALN becomes intractable [6]8 .
More recently languages equipped with qualified existential restrictions but no uni-
versal restrictions (even expressed in a disguised way, as in DL-Lite, through inverse
roles) have been studied. In particular, in [3] it has been shown that for the basic
language EL instance checking is polynomial even in the presence of general (i.e.,
cyclic) inclusion assertions, while extensions of the language lead easily to intractabil-
ity (cf. Table 1). Conjunctive query answering in EL has not been studied yet, however
the results in Table 1 show us that such a service is PT IME-hard in data complexity and
hence cannot be delegated to a relational DBMS (actually such a lower bound holds
already for instance checking).
5 Conclusions
For the management of data intensive ontologies, we have advocated the use of DL-Lite,
a subset of OWL-Lite that (i) is specifically tailored to capture conceptual data models
and basic ontology languages, and (ii) keeps the worst-case data complexity of sound
and complete reasoning in L OG S PACE. This allows one to effectively exploit current
industrial strength relational technology for query answering.
We have also argued that by extending DL-Lite, we lose this possibility, and in
order to allow for the separation of TBox and ABox reasoning, we have to rely on more
powerful query evaluation engines, such as one for Datalog. Hence, the possibility of
efficient implementations and optimization strategies for query evaluation engines that
go beyond relational ones is worth investigating.
7
http://www.w3.org/TR/rdf-schema/
8
Note that a TBox with only acyclic inclusion assertions can always be transformed into an
empty TBox.
Acknowledgments This research has been partially supported by the IST Specific
Targeted Research Project “Thinking ONtologies (TONES) – IST-007603 funded by
the European Union under the 6th Framework Programme.
References
1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley Publ. Co.,
1995.
2. A. Acciarri, D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, M. Palmieri, and
R. Rosati. Q U O NTO: Q Uerying ONTOlogies. In Proc. of AAAI 2005, pages 1670–1671,
2005.
3. F. Baader, S. Brandt, and K. Lutz. Pushing the EL envelope. In Proc. of IJCAI 2005, 2005.
4. F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors. The
Description Logic Handbook: Theory, Implementation and Applications. Cambridge Uni-
versity Press, 2003.
5. A. Calı̀, D. Lembo, and R. Rosati. Query rewriting and answering under constraints in data
integration systems. In Proc. of IJCAI 2003, pages 16–21, 2003.
6. D. Calvanese. Reasoning with inclusion axioms in description logics: Algorithms and com-
plexity. In Proc. of ECAI’96, pages 303–307. John Wiley & Sons, 1996.
7. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Data complexity
of query answering in description logics. In Proc. of DL 2005. CEUR Electronic Workshop
Proceedings, http://ceur-ws.org/, 2005.
8. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. DL-Lite: Tractable
description logics for ontologies. In Proc. of AAAI 2005, pages 602–607, 2005.
9. D. Calvanese, G. De Giacomo, and M. Lenzerini. Answering queries using views over
description logics knowledge bases. In Proc. of AAAI 2000, pages 386–391, 2000.
10. C. Chen, V. Haarslev, and J. Wang. LAS: Extending Racer by a Large ABox Store. In Proc.
of DL 2005. CEUR Electronic Workshop Proceedings, http://ceur-ws.org/, 2005.
11. F. M. Donini, M. Lenzerini, D. Nardi, and A. Schaerf. Deduction in concept languages: From
subsumption to instance checking. J. of Log. and Comp., 4(4):423–452, 1994.
12. B. N. Grosof, I. Horrocks, R. Volz, and S. Decker. Description logic programs: Combining
logic programs with description logic. In Proc. of WWW 2003, pages 48–57, 2003.
13. J. Heflin and J. Hendler. A portrait of the semantic web in action. IEEE Intelligent Systems,
16(2):54–59, 2001.
14. I. Horrocks, L. Li, D. Turi, and S. Bechhofer. The Instance Store: DL reasoning with large
numbers of individuals. In Proc. of DL 2004. CEUR Electronic Workshop Proceedings,
http://ceur-ws.org/Vol-104/, 2004.
15. U. Hustadt, B. Motik, and U. Sattler. Data complexity of reasoning in very expressive de-
scription logics. In Proc. of IJCAI 2005, 2005.
16. M. Lenzerini. Data integration: A theoretical perspective. In Proc. of PODS 2002, pages
233–246, 2002.
17. H. J. Levesque and G. Lakemeyer. The Logic of Knowledge Bases. The MIT Press, 2001.
18. A. Y. Levy and M.-C. Rousset. Combining Horn rules and description logics in CARIN.
Artificial Intelligence, 104(1–2):165–209, 1998.
19. M. M. Ortiz de la Fuente, D. Calvanese, T. Eiter, and E. Franconi. Data complexity of answer-
ing conjunctive queries over SHIQ knowledge bases. Technical report, Fac. of Computer
Science, Free Univ. of Bozen-Bolzano, July 2005. Also available as CORR technical report
at http://arxiv.org/abs/cs.LO/0507059/.
20. M. Y. Vardi. The complexity of relational query languages. In Proc. of STOC’82, pages
137–146, 1982.