Databases where relations have arity at most two, often called graph databases, play a prominent role in many elds. Ontology languages based on Description Logics (DLs) have been advocated to enrich such repositories (known as ABoxes in DL jargon) with ontological information. Then, in Ontology Based Query Answering (OBQA), one is interested in answering user queries over the data while taking into account the ontology. However, the ontological layer has a signi cant effect on the query answering problem, and OBQA algorithms are usually more involved than their counterparts in plain (graph) databases. The development of OBQA algorithms and their implementation has been the goal of signi cant research e orts in the DL community in the last decade. Here we review some of the achieved results. We discuss the main challenges to be overcome when the ontological knowledge is expressed in di erent DLs, and when di erent query languages are considered. We give an overview of some of the algorithms developed so far, and the computational complexity of the problem for the di erent combinations of DLs and query languages.
In many application areas, data can be naturally modeled and stored using
only unary and binary relations. Indeed, graph databases, which can be seen as
databases where only relations of these arities occur, have gained much attention
in the last years and are being applied in popular elds like the Semantic Web.
Description Logics are a family of languages for knowledge representation and
reasoning whose vocabulary is based on unary and binary relations, known as
concepts and roles in DL jargon [
MathSubj
Computer Sience worksIn
Alberto
Mendelzon
Person Person Je rey Ullman
hasAdvisor worksIn wroteThesis Thesis University
o mittedT sb u wroteThesis Thesis ThesisAM80
A DL ontology describing this domain is given in Figure 2. The rst axiom introduces the term CompScientist and ensures that everyone who works on the CompScience eld is a CompScientist . Axiom (2) states that every PhD holder must have an advisor who is himself a PhD holder. Axioms (3,4) together ensure that PhD holders are exactly those people that have written and submitted a (PhD) thesis. Finally, axioms (5,6) together de ne the term SubmittedThesis as the class of all thesis submitted to somela university.
(1) 9worksOn.fCompScig v CompScientist (2) PhD v 9hasAdvisor.PhD (3) PhD v 9wroteThesis.SubmittedThesis (4) 9wroteThesis.SubmittedThesis v PhD (5) T hesis u 9submittedTo.University v SubmittedThesis (6) SubmittedThesis v T hesis u 9submittedTo.University
Now consider the following conjunctive queries: q1(x; y) =ComputerScientist (x); ComputerScientist (y); hasAdvisor (x; y); wroteThesis (x; z); wroteThesis (y; z0); submittedTo(z; w); submittedTo(z0; w) q2(x) =ComputerScientist (x); hasAdvisor (x; y);
wroteThesis (y; z); submittedTo(z; w); University (z0; w)
The query q1 asks for pairs (x; y) of computer scientists that submitted their thesis to the same university w. The pair (Je reyUllman; AlbertoMendelzon) is one such pair. They both submitted their thesis to Princeton and they are both instances of ComputerScientist . Note that the data does not explicitely state the latter, but it is implied by axiom (1) and the fact that they both work on the CompScience eld.
The query q2 asks for computer scientists whose advisor submitted his thesis to a university. The answer includes both AlbertoMendelzon and Je reyUllman. Even though the data contains nothing about the PhD advisor of Je reyUllman, the ontology implies that he must have one, who is a PhD holder and hence must have submitted a thesis to some university.
In the absence of an ontology, OBQA coincides with standard query evaluation over plain (graph) databases, but in general, the presence of the ontology makes query answering more involved. As we have seen, to answer a query one may need to take into account instances of concepts and roles not given in the data, like for the concept CompScientist in query q1. More interestingly, we may even need to consider variable assignments that map query variables to unknown objects that are not named constants in the database: to obtain Je reyUllman as an answer to q2, we must map variables y, z, and w to objects we known nothing about, but whose existence is implied by the axioms.
As we will see in the next section, the actual impact of the ontology on (the computational complexity of) the query answering problem depends on the speci c description logic in which the ontology is written, and on the kind of query that is to be answered. In this paper, we brie y discuss some of the main challenges to be tackled when solving the OBQA problem, for di erent DLs and query languages, and survey the complexity results obtained so far.
The rest of the paper is organized as follows. In the next section, we give some
DL and OBQA preliminaries. They are rather technical and given for the sake
of completeness, but it is not necessary to read them in detail for understanding
the rest of the material. Finally, section 3 is the core of the paper, where we
discuss the challenges that arise in the OBQA setting and complexity results.
The interested reader may refer to [
Preliminaries We brie y recall of some popular DLs. We start giving the syntax and semantics of concepts and roles, and then describe how they can be used to write ABoxes and ontologies in di erent DLs.
A DL vocabulary consists of three in nite, countable, disjoint sets NC, NR, and NI of concept names, role names, and individuals. Di erent DLs provide di erent concept and role constructors, which can be used to combine the terms in the vocabulary into complex concepts and roles. The only role constructor we consider here is the inverse: for r 2 NR, its inverse r is also a role. We use NR to refer to the set NR [ fr j r 2 NRg of all roles, and if R 2 NR, we use R to mean r if R = r and r if R = r . The most popular concept constructors are summarized in Table 1.
Constructor
negation conjunction disjunction universal restriction existential restriction
nominal quali ed number restrictions
Syntax Semantics
:C I n CI C u C0 CI \ C0I C t C0 CI [ C0I 8R:C fc j 8d; (c; d) 2 RI ! d 2 CIg 9R:C fc j 9d:(c; d) 2 RI ^ d 2 CIg fag aI > n R.C fc j card (fd j (c; d) 2 RI ^ d 2 CIg) 6 n R.C fc j card (fd j (c; d) 2 RI ^ d 2 CIg) ng ng Semantics. As usual, the semantics of DLs is de ned in terms of interpretations of the form I = ( I ; I ), where the domain I is a non-empty set and I is an interpretation function mapping each a 2 NI to an object aI 2 I , each A 2 NC to a set AI I , and each r 2 NR to a binary relation rI I I . The function I is inductively extended to general concepts and roles. For inverse roles, we have (r )I = f(d; c) j (c; d) 2 rI g. The semantics of the concept constructors in Table 1 is summarized in the last column. A DL knowledge base consists of an ABox, and a TBox or ontology.2 In all the DLs we consider, an ABox is de ned a set of assertions which may take the form A(b) or r(a; b) with A 2 NC, r 2 NR, and a; b 2 NI.
a synonym of TBox.
The ontology is a set of axioms, whose form depends on the DL in question.
In this paper we mention the following DLs:
The DL-Lite family [
R v S and R v :S, which is very closely related to OWL 2 QL.
{ DL-LiteRDFS, a fragment of DL-LiteR that is probably less known, but
quite interesting for comparison purposes. It disables negation and
existential quanti cation in the right hand side of axioms, and it is roughly
equivalent to RDF(S), the schema language for RDF [
The interested reader can nd the full syntax of these languages in the rst block of Table 2. As usual for DL-Lite, we use unquali ed existentials and write 9R rather than 9R:>, where > is a shortcut for A t :A.
The E L family [
Expressive DLs that fully support Boolean concept constructors and both
kinds of quanti ers have traditionally been the main focus of attention of
the DL community. Here we recall the well-known languages SHIQ and
SHOIQ, which roughly correspond the the OWL Lite and OWL DL pro les
of the rst generation of OWL standards. Their syntax is de ned in Table 2;
there is an additional syntactic requirement that disallows non-simple roles
(i.e., roles that have a transitive subrole) from occurring in number
restrictions. The full OWL 2 is based on a logic called SROIQ, but we do not
include it in the table since its syntax is quite cumbersome to de ne.
Horn DLs that are obtained from expressive DLs by fully disallowing
disjunction. The syntax of Horn-SHIQ and Horn-SHOIQ, in normal form [
Semantics of ABoxes and Ontologies An interpretation I satis es an assertion A(a) (resp. r(a; b)) if aI 2 AI (resp. (aI ; bI ) 2 rI ), and I is a model of an ABox A if it satis es all assertions in A. For the TBox axioms, we have that I satis es an inclusion G v H (where G and H are either two concepts, or two roles) if GI HI ; it satis es trans(R) if RI is a transitive relation. I is a model of an ontology T if it satis es all axioms in T , and I is a model of K = (T ; A) if I satis es all inclusions in T and all assertions in A.
DL-Litecore B v C DL-LiteR B v C, R v S DL-LiteRDFS B v A, R v S EL ELH SHIQ SHOIQ
C v D C v D; r v s C v D; R v S
trans(R) C v D; R v S trans(R)
TBox axioms B ::= A j 9R C ::= B j :B R ::= r j r B ::= A j 9R C ::= B j :B R ::= r j r B ::= A j 9R R; S ::= r j r C; D ::= A j C u D j 9r.C C; D ::= A j C u D j 9r.C C; D ::= A j :C j C u D j C t D j 9R.C j 8R:C j
> n R.C j 6 n R.C R; S ::= r j r C; D ::= A j fag j :C j C u D j C t D j 9R.C j 8R:C j
> n R.C j 6 n R.C R; S ::= r j r
S ::= R j :R
Horn-SHOIQ
B u B0 v C; 9R.B v C; C v 8R.B; C v 9R.B
C v > n R.B; C v 6 1 R.B; R v S; trans(R) B u B0 v C; 9R.B v C; C v 8R.B; C v 9R.B
C v > n R.B; C v 6 1 R.B; R v S; trans(R) B; B0; C ::= A R; S ::= r j r B; B0; C ::= Ajfag R; S ::= r j r Most work on OBQA and OBDA so far has considered conjunctive queries and their unions as query languages. We also de ne instance queries, which are CQs with only one atom.
De nition 1 (IQs,CQs,UCQs). Let NV denote a countably in nite set of variables. A conjunctive query (CQ) (with answer variables x) is an expression q(x) = 9y.', where x and y are tuples of variables from NV, and ' is a conjunction of atoms of the forms (i) A(t), where A 2 NC is a concept name and t 2 NI [ x [ y, and (ii) r(t; t0), where r 2 NR is a role name and t; t0 2 NI [ x [ y.
A query with x = hi, that is, where all variables in ' are existentially quanti ed, is called Boolean. If in a CQ q(x) = 9y.' we have that ' consists of only one atom, we call it an instance query (IQ).
A union of conjunctive queries (UCQ) is a disjunction of CQs with the same answer variables, that is, an expression q(x) = 9y1'1 _ _ 9yn'n where each 'i is a conjunction of atoms as above, with arguments from NI [ x [ yi.
One of the fundamental di erences between query answering with DL
ontologies in contrast to plain graph databases, is that in the former setting researchers
have focused on CQs and UCQs, while for the latter setting the basic querying
mechanism are regular path queries (RPQs) and their extensions. These queries
enable the sophisticated navigation of paths that has long been considered
crucial for querying data on the web. Recent work has aimed at bridging this gap,
by developing OBQA algorithms for answering di erent forms of RPQs [
De nition 2 ((C)(2)RPQs). A conjunctive two-way regular path query (C2RPQ) (with answer variables x) has the form q(x) = 9y.' where x and y are tuples of variables from NV, and ' is a conjunction of atoms of the form (i) above, and of the following form: (ii') (t; t0), where is a regular expression over the alphabet NR [ fA? j A 2
NCg, and t; t0 2 NI [ x [ y.
Conjunctive (one-way) regular path queries (CRPQs) are obtained by disallowing inverse roles from NR n NR in atoms of type (ii). Two-way regular path queries (2RPQs) consist of a single atom of type (ii), and regular path queries (RPQs) further disallow inverse roles. 2.3
Query Answering We now de ne formally the OBQA problem we discuss. In what follows, we use the term query to refer to a query of any of the kinds de ned above. De nition 3 (Query match, (certain) answers). Let I be an interpretation. A match for a query q(x) = 9y:' in I is a mapping form the terms occurring in q to the domain I of I such that (a) = aI for every individual a occurring in q, and that satis es: (i) (t) 2 AI for every atom A(t) in ', (ii) ( (t); (t0)) 2 rI for every atom r(t; t0) in ', and (ii') (t0) is a -successor of (t) for every atom (t; t0) in '; where an element d 2 I is called a -successor of c 2 I in I if there is some chain c1; : : : ; cn of objects from I and a chain R1; : : : ; Rn 1 of roles in the language of such that c1 = c, cn = d, and (ci; ci+1) 2 RiI for 1 i < n. Let x = x1; : : : ; xm. The answers to q in I are the tuples a1; : : : ; am such that there is a match for q in I with (xi) = ai for 1 i m.
Finally, let A be an ABox and T an ontology. The (certain) answers to q over I are the tuples of individuals that are an answer to q in every model I of (A; T ).
We are interested in the decision problem associated to query answering, sometimes called query output tuple (QOT) problem, which consists on deciding whether a given tuple of individuals is a certain answer to a given query. For Boolean queries, whose only possible answer is the empty tuple, one usually talks about query entailment. Deciding query entailment amounts to deciding whether there exists a query match in every model of the ABox and the ontology. It is well known that the query output tuple problem for an arbitrary query reduces linearly to the entailment problem of a Boolean query. We summarize the main OBQA problems that we discuss in this paper in Table 3.
Problem
QueryAnswer QueryEntailment
QueryAnswer QueryEntailment
Varying input Fixed input Problem de nition
Data complexity
Is there a match for q
Combined complexity q, T , A, a Is a in the answers of q over (T ; A)?
Is there a match for q q0, T , A in every model of (T ; A)?
Data and combined complexity We are interested in two measures of complexity. First, since the size of the data repositories usually dominates over the size of the ontology and the query, we are interested in measuring the complexity in terms of the ABox only. This measure of complexity is called data complexity, and like for traditional databases, for OBQA and OBDA it is considered the most relevant in practice. The other notion is called combined complexity and it takes all components as an input: the query, the ontology, the ABox, and possibly the tuple of constants. 3
The challenges of OBQA Recall that in OBQA we view the ABox as a database that may be incomplete in at least two ways: 1. The existing objects may be instances of concepts and roles that do not show up in the data. 2. The ontology may imply the existence of more objects, beyond the named individuals that explicitely appear in the data. While these objects do not participate in query answers, they do participate in query matches.
A nave way to approach the problem would be to complete the data as prescribed by the ontology, and then evaluate the query over the resulting structure. However, this strategy may not work. We are interested in the certain answers over all models, that is, over all ways to complete the data to satisfy the ontology. But there may be too many ways to do this completion, and the completed structures (models) may be too large, and are often in nite. We discuss below how these two problems make OBQA, in general, a computationally harder problem that query answering over plain databases, as Table 4 shows. We remark that, for all DLs, the complexity of IQs coincides with the complexity of standard reasoning tasks (like subsumption and satis ability).
Before discussing the results in the table in more detail, we want to point out that most DLs are fragments of rst order logic (FOL), and an ontology can Plain databases
EL, ELH Plain databases DL-LiteRDFS
EL, ELH
Horn-SHOIQ
SHIQ SHOIQ
Combined complexity
IQs CQs in AC0 NP-c NL-c NP-c
P-c NP-c (2)RPQs C(2)RPQs
NP-c
IQs in AC0 in AC0
P-c (2)RPQs
Data complexity
CQs in AC0 in AC0
P-c
C(2)RPQs NL-c
NL-c NL-c P-cy
P-c IQs,(2)RPQs ExpTime-c
ExpTime-c co-NExpTime-c
PSpace-c NL-c NL-c
PSpace-c P-c P-c CQs,C(2)RPQs IQs,(2)RPQs CQs, C(2)RPQs
ExpTime-c 2ExpTime-c open
P-c coNP-c coNP-c
P-c
coNP-c
open
be rewritten as a FOL formula in a straightforward way [
Multiple Models Query answering algorithms from databases usually evaluate the query over one single input structure, the database. In the presence of DL ontologies, however, the query has to be evaluated over all the structures that are models of the data and the ontology. A knowledge base (T ; A) has, in principle, in nitely many models. A trivial reason for this is that we can use arbitrary sets as domains in interpretations, and we can add additional, possibly irrelevant information to any model in a way that it is still a model. But even if we disregard these trivial reasons and consider only the `meaningful' di erences between models, resulting from di erent ways in which the data may be completed to satisfy all constraints given by the ontology, we can still end up with a very large number of models.
To develop query answering techniques it is usually possible to show that a nite subset of all the models su ces. In the case of Horn DLs, and in particular for the lightweight DLs of the DL-Lite and E L families, we can go even further and show the following key property:
Canonical model property: given a satis able knowledge base (T ; A), one can construct a canonical model I(T ;A) such that, for every query q, the answers to q over (T ; A) coincide with the answers to q in I(T ;A). That is, the canonical model I(T ;A) su ces for answering all queries. This property plays a central role in the data complexity of query answering. In fact, all tractability results in the Table 4 ( rst two blocks and rst row of the last block) are for logics that have the canonical model property.
In contrast, the presence of any kind of disjunction in the ontology results in the existence of models that di er in the queries they entail, and makes the query entailment problem coNP hard in data complexity, even for the simplest instance queries. This applies to SHIQ and SHOIQ, which support full Booleans (see the last two rows of Table 4). It also applies to all other expressive DLs, like SROIQ which underlies OWL 2. The need to consider several models also has a big impact on the combined complexity of CQ answering: it makes the problem exponentially harder than standard reasoning for SHIQ and most expressive DLs (for SHOIQ, decidability of the problem remains open). 3.2
Large and In nite Models Unfortunately, identifying one model, or one set of models, that is su cient for deciding query entailment, is not enough to make query answering easy. Usually we must overcome an additional di culty: (the domain of) models can be, in general, in nite. This is caused by existential concepts in the right hand side of axioms, a feature that is considered fundamental in DLs and allowed in all the logics we have mentioned, except for DL-LiteRDFS.
Many DLs enjoy the nite model property. That is, every satis able KB has a model where the domain is a nite set. For lightweight DLs like DL-Lite and E L, there is even a model where the domain's cardinality is polynomially bounded in the size of the KB. However, these positive properties are of limited use for query answering. Small and nite models are usually built by `reusing' domain elements to satisfy existential restrictions. This creates cycles in models that may not a ect KB satis ability, but often result in spurious query matches that are not really implied by the KB. For example, one can avoid generating an in nite R-chain of objects for satisfying an axiom A v 9R.A by simply `reusing' one element e and making it an R-successor of itself. However, this would cause the query 9x.R(x; x) to be erroneously entailed.
Researchers have come up with a number of di erent query answering
techniques, which overcome the challenges above in di erent ways. We brie y discuss
some of them below, and refer to [
FOL Rewritability: Given a DL-Lite ontology T and a CQ q, one can compute a FOL query qT such that, for every ABox A, the answers of q over (A; T ) coincides with the answers of qT over A.
This means we can reduce the problem of answering a CQ over a DL-Lite knowledge base to simply evaluating a FOL query, or equivalently, an SQL query, over a standard database, a well understood problem for which e cient solutions are readily available. Since the rewriting of q into qT does not depend on the ABox A, this also implies that the data complexity of CQ answering over DLLite KBs is not higher than the data complexity of evaluating FOL queries over standard databases, namely in the class AC0 (see Table 4, rst and second rows).
FOL Rewritability was rst exploited to develop OBQA algorithms for
DLLite in [
Query rewriting beyond DL-Lite It is well known that CQ answering in practically all DLs outside the DL-Lite family is at least LogSpace hard in data complexity, and hence FO rewritability is the lost. This applies, in particular, to the E L family and to all its extensions, like Horn-SHIQ and Horn-SHOIQ. However, this kind of logics still have the canonical model property, and other rewriting techniques have been proposed that rewrite the query and the ontology into more expressive languages, like Datalog.
One such approach, developed for Horn-SHIQ in [
A similar approach had already been proposed for E L in [
Answering RPQs and their extensions in lightweight DLs As we have
mentioned, until recently most work on OBQA focused on CQs and UCQs. RPQs
and their extensions had only been explored for very expressive DLs, where they
have the same complexity as CQs (see Table 4), and can be answered using
techniques like the automata one described below [
Techniques for expressive DLs Expressive DLs lack the canonical model
property. All algorithms developed so far focus on deciding the existence of a
countermodel, that is, a model where the query has no match. They also build
on the fact that one can restrict the search to interpretations that have a regular,
forest like structure. Techniques to nd such a counterexample include automata
theoretic ones (which in fact work for C2RPQs) [