OWL 2 QL is the profile of OWL 2 targeted to Ontology-Based Data Access (OBDA) scenarios, where large amount of data are to be accessed and thus query answering is required to be especially efficient in the size of such data, namely AC0 in data complexity. On the other hand, the syntax and the semantics of the SPARQL query language for OWL 2 is defined by means of the Direct Semantics Entailment Regime (DSER), which considers queries including any assertion expressible in the language of the queried ontology, i.e., both ABox atoms, TBox atoms and inequalities expressed by means of DifferentIndividuals atoms. Thus, in this paper, we investigate query answering over OWL 2 QL under DSER. In particular, we show that, by virtue of the restricted meaning assigned to existential variables and union, query answering can be reduced to the evaluation of a Datalog program. Finally, we investigate query answering under a new SPARQL entailment regime, called Direct Semantics Answering Regime (DSAR), obtained by modifying DSER in such a way that existentially quantified variables are assigned the classical logical meaning, and provide an algorithm for answering queries over OWL 2 QL ontologies under DSAR, that is AC0 in data complexity, for a class of queries comprising both TBox atoms, ABox atoms and inequalities.
OWL 2 QL is the OWL 2 profile especially designed to provide efficient query answering over Ontology-Based Data Access (OBDA) scenarios. In particular, in such a context, the aim is to access through an ontology a typically huge amount of data residing in external data sources. Hence, OWL 2 QL is based on DL-LiteR, that is a logic for which answering unions of conjunctive queries can be reduced to answering first-order queries, and thus is AC0 with respect to the size of the data. We point out that OWL 2 QL does not impose the Unique Name Assumption (UNA). Though, it allows specifying inequalities between IRIs, by means of
e2) imposing that e1 and e2 denote distinct objects of the domain.
SPARQL 1.1 is the W3C query language that is considered as the de-facto
standard query language for OWL 2. In particular, the syntax and the semantics
of SPARQL queries over OWL 2 QL ontologies are defined by means of the so-called
Direct Semantics Entailment Regime (DSER) [
In this paper, we investigate the problem of answering queries OWL 2 QL ontologies under DSER. Therefore, queries may contain both OWL 2 QL TBox atoms, e.g., of the form SubClassOf(x1 x2), and ABox atoms, e.g., of the form ClassAssertion(x1 x2). Furthermore, queries may comprise inequalities, expressed by means of DifferentIndividuals atoms. It is worth noting that the presence of inequalities within queries deserves special attention. Indeed, inequalities between ontology entities can be logically implied by an OWL 2 QL ontology. As a simple example consider the ontology consisting of the following axioms:
ClassAssertion(:Female :petra).
SubClassOf(:Female :Person).SubClassOf(:Male :Person).
and suppose that we want to retrieve all classes that contain at least two distinct instances. The formulation of this query in SPARQL is the following: select $x wheref SubClassOf($x owl:Thing).
DifferentIndividuals($y $z)g
Note that this query is legal under DSER. Also, it is easy to see that, since :Male and :Female are disjoint, at least two individuals among :p, :petra and :peter denote distinct domain objects in every model. Hence, the answer to the query is {:Person,owl:Thing}. This example clearly shows that inequalities can be inferred and hence the presence of inequalities within queries requires to reason about them.
The goal of our work is to investigate query answering over OWL 2 QL
ontologies under DSER, considering the whole class of queries considered legal under
DSER. Note that, as far as we know, this is the first work that considers queries
comprising, in particular, DifferentIndividuals atoms. Furthermore, since as
already observed in [
The main contributions of this paper can be summarized as follows:
– We show that it is possible to reduce query answering over OWL 2 QL
ontologies under DSER to the evaluation of a Datalog program, which provides a
practical algorithm that can benefit of commercial highly optimized Datalog
engines (e.g., [
Related work. The problem of answering unions of conjunctive queries over
Description Logics ontologies under the classical first-order semantics, was
extensively studied in the literature (e.g. [
Few recent works [
was proposed for answering queries over OWL 2 RL ontologies under DSER, that considers queries possibly containing TBox and DifferentIndividuals atoms.
The paper is organized as follows. After providing, in Section 2, some preliminaries on the languages considered in the paper, in Section 3 we investigate query answering under DSER. Then, in Section 4, we introduce DSAR and study query answering under DSAR. Finally, in Section 5, we conclude the paper and discuss future work. 2
In this section we briefly recall the OWL 2 QL ontology language and the query
language. We express ontologies and queries in the extended functional style
syntax [
Ontology entities, such as individuals, classes, object properties, etc., are denoted by expressions. Atomic expressions are denoted simply by a name, where the set of names coincides with the set IRI of Internationalized Resource Identifiers. Complex expressions are built on atomic expressions using the OWL 2 QL constructors, such as ObjectSomeValuesFrom, ObjectInverseOf, etc. For example, if e1, e2 are expressions, then ObjectSomeValuesFrom(e1 e2) is a complex expression. Values are denoted by literals where a literal (l, d) consists of a lexical value l and a datatype d. Let D = {rdfs:Literal} ∪ D0 denote the set of datatypes admitted in OWL 2 QL and Lql = {(l, d) | d ∈ D0} the set of literals admitted in OWL 2 QL.
An OWL 2 QL ontology (simply ontology in the following) is a finite set of OWL 2 QL logical axioms. Logical axioms are classified into (i) TBox axioms, i.e.,
Assertion, and DifferentIndividuals axioms. Axioms not in the above list can be expressed by appropriate combinations of the ones listed.
Given an ontology O we denote with VNO the set of atomic expressions occurring in O extended with the OWL 2 QL reserved vocabulary. An expression is said to appear in class position in O if it appears in a SubClassOf or DisjointClasses axiom, or in the first position of a ClassAssertion axiom. Similarly, we can define the notions of object property, data property, data type, individual, and value position. Without loss of generality, we assume that an expression cannot appear in positions of different types within the same ontology2. Finally, 2 Note that even though OWL 2 punning allows the same entity to occur in positions of different types, here we adopt the Direct Semantics for OWL 2, which interprets as distinct names each such occurrence. That is why, without loss of generality, we can assume that an expression cannot appear in positions of different types. – If e occurs in individual position in O, then eI ∈ ΔOI ; – If e occurs in class position in O, then eI ⊆ ΔOI ; in particular: • owl:ThingI = ΔOI ; • owl:NothingI = ∅; • ObjectSomeValuesFrom(e1 e2)I = {d1 | hd1, d2i ∈ eI1, d2 ∈ eI2}; • DataSomeValuesFrom(e1 e2)I = {d1 | hd1, d2i ∈ eI1, d2 ∈ eI2}; – if e occurs in object property position in O, then eI ⊆ (ΔOI × ΔOI ); in particular: • owl:topObjectPropertyI = (ΔOI × ΔOI ); •• Oobwjle:cbtoItntvoemrOsbejOefc(teP)rIo=pe(retIy)I−=1; ∅; – if e occurs in data property position in O, then eI ⊆ (ΔOI × ΔV I ); in particular: • owl:topDataPropertyI = (ΔOI × ΔV I ); • owl:bottomDataPropertyI = ∅; – if e occurs in datatype position in O, then eI ⊆ (ΔV I ); in particular: • rdfs:LiteralI = Δv; • D1I = D1DT , for every D1 ∈ D0, where the function ·DT is the function defined in the OWL 2 QL datatype map, that assigns to each d ∈ D0 the set of data values represented by d in all OWL 2 ontologies; – If (l, d) in LQL, then (l, d)I = (l, d)LS, where ·LS is the function defined in the OWL 2 QL datatype map, that specifies, for each literal (l, d) admitted in OWL 2 QL which is the data value in dDT denoted by such literal. we denote with ExpO the finite set of all well-formed expressions that can be built on the basis of VNO. For example, if e1, e2 are well-formed expressions, then ObjectSomeValuesFrom(e1e2) is a well-formed expression too.
In this paper we are interested in interpreting OWL 2 QL ontologies according to the Direct Semantics (DS)3. Hence, the semantics of OWL 2 QL is given by means of the usual notion of interpretation. Specifically, an interpretation for O is a pair I = (ΔI , ·I ), where: – ΔI is the disjoint union of the non-empty set ΔOI , i.e., the object domain, and of the non-empty set Δv, i.e., the value domain consisting of all data values that, according to the OWL 2 QL datatype map4, can be represented by literals in OWL 2 QL, and – ·I is the interpretation function, i.e., a function that maps every expression in ExpO and every literal in LQL according to the set of conditions specified in Table 1.
The semantics of logical axioms is based on the usual notion of satisfaction of an axiom with respect to an interpretation I. Thus, for example,
I |= SubClassOf(e1 e2) if eI1 ⊆ eI2, and I |= DifferentIndividuals(e1 e2) if eI1 6= eI . Also, we say that an interpretation is a model of O if it satisfies all 2 axioms in O and we say that O is satisfiable if there exists at least an interpretation that is a model of O. Finally, if α is an axiom, we say that α is logically implied by an ontology O, written O |= α, if M |= α for every model M of O.
As for the query language, we rely on the notion of SPARQL entailment regime, as defined in the W3C standard specification5. Specifically, a SPARQL entailment regime defines (i) the syntax and the semantics of axioms constituting the queried ontology, (ii) the syntax of conjunctive queries considered legal for the regime, and (iii) the semantics of queries, i.e., what are the answers to a query. In this paper, we are interested in the OWL 2 QL Direct Semantics Entailment Regime (DSER). Thus, as for (i), as already discussed above, we assume to deal with OWL 2 QL ontologies interpreted according to DS. As for (ii), legal queries are conjunctive queries, called Basic Graph Patterns in the SPARQL jargon, where a conjunctive query q is an expression of the form
select $x1 . . . $xn where B where x1, . . . , xn are variables, called target variables, belonging to an alphabet V disjoint from VNO, n is the arity of q, and B, called query body, denoted body(q), is a conjunction of atoms including all variables xi, for i ∈ {1, n}, and possibly including entities in VNO and variables in V, distinct from xi, called existential variables of q. More precisely, atoms can be classified into TBox and ABox atoms, having the form of legal OWL 2 QL TBox and ABox axioms respectively, and possibly including variables in object or predicate position6. Finally, as for (iii), DSER defines the answers to a query as follows. Given a tuple of variables z = (z1, . . . , zn), a tuple of IRIs w = (w1, . . . , wn), and a conjunction of atoms B, we denote by σ[z → w](B) the conjunction of atoms obtained from B by substituting each zi in z with wi in w, for i ∈ {1, . . . , n}. Now, let O be an ontology and q a conjunctive query such that x is the n-tuple of target variables of q and y is the m-tuple of existential variables of q. We say that an n-tuple of IRIs t is an answer to q over O under DSER if there exists an m-tuple of IRIs v such that
O |= σ[(x, y) → (t, v)](body(q)).
Since in this paper we investigate query answering under DSER where queries are unions of conjunctive queries, we still have to specify what are the answers to such queries. Specifically, given a query Q = q1 ∪ q2 ∪ . . . qm, the answers to Q under DSER are defined as the union of the set of answers to each qi in Q.
In the next sections, we will denote by AnsDSER(Q, O) the set of answers to the query Q over the ontology O under DSER. Finally, we point out that, from 5 https://www.w3.org/TR/sparql11-entailment/ 6 Since we assumed that the same entity name cannot occur in positions of different types within the ontology, without loss of generality, we ignore here the so-called typing constraint, preventing the same variable to occur in positions of different types within queries. now on, we implicitly assume to deal with a satisfiable OWL 2 QL ontology O that does not contain any data property 7. 3
In this section, we investigate query answering under DSER. In particular we present the algorithm AnsByDat that reduces query answering under DSER to the evaluation of a Datalog program.
First of all, let us introduce the database schema Sql. Sql is defined as the union of the following sets of predicates (where p/n indicates that the predicate p has arity n): – Sql,T = {isacCC/2, isacCR/3, isacCI/3, isacRC/2, isacRR/3, isacRI/3, isacIC/2, isacIR/3, isacII/3, isarRR/2, isarRI/2, isarIR/2, isarII/2, disjcCC/2, disjcCR/2, disjcCI/2, disjcRC/2, disjcRR/2, disjcRI/2, disjcIC/2, disjcIR/2, disjcII/2, disjrRR/2, disjrRI/2, disjrIR/2, disjrII/2, irref/1, refl/1}. – Sql,A = {instc/2, instr/3, existR/2, existI/2, diff/2}
Also, we introduce a function allowing to encode OWL 2 QL assertions into assertions over Sql. Thus, let τ be the encoding function from the set of OWL 2 QL logical assertions, possibly including variables in V, to the set of logical assertions over the alphabet Sql, possibly including constants in IRIs and variables in V. τ is defined in Table 2, where, for brevity, we have used the usual Description Logic notation for OWL 2 QL assertions α. Intuitively, each predicate p in Sql (Sql,T , Sql,A) encodes a specific form of OWL 2 QL (TBox, ABox, respectively) axiom, and for each such assertion that is either an axiom or an atom, the function τ returns respectively an instance of p or an atom with predicate p.
We are now ready to present the algorithm AnsByDat. Specifically, given a query Q over an ontology O the algorithm proceeds as follows: 1. it constructs a database DO that is an instance of Sql and represents the axioms of O, 2. it builds a set Pql of Datalog rules encoding the semantics of OWL 2 QL axioms, thus allowing to reason about them, 3. it builds a set PQ of Datalog rules encoding Q whose head predicate is Ans, and 4. it evaluates the Datalog program P = (Pql ∪ PQ) over DO and returns the extension of Ans.
More in details, the database DO is simply obtained by applying τ to each axiom of O. As for the program Pql, it is the union of the two sets of rules, 7 The whole approach can be extended to capture data properties too. Pql,T and Pql,A, which, intuitively, are obtained by translating by means of τ the set of inference rules that are needed to compute the closure of the TBox and the saturation of the ABox, respectively. For the lack of space, we cannot report here the whole set of rules of Pql. Thus, in the following, we illustrate Pql, by considering two specific rules, namely: isacCI(c1, r2, c2) :- isacCC(c1, c3), isacCI(c3, r2, c2). (*) instr(r1, x, y) :- instr(r2, y, x), isarRI(r2, r1). (**)
It is not hard to see that the above rules encode the following inference rules: (*)∀c1, r2, c2 if O |= c1 v c3 and O |= c3 v ∃r2.c2, then O |= c1 v ∃r2.c2, and (**)∀r1, x, y if O |= r2(y, x) and O |= r2 v r1−, then O |= r1(x, y).
Let us now show how the algorithm constructs the set PQ. If Q has target variables x and is the union of the conjunctive queries q1, . . . , qp, then PQ is the set of rules {Ans(x):-τ (body(qi)) | i = 1, . . . , p} where, by an abuse of notation, we denote by τ (body(qi)) the conjunction of the assertions obtained by applying τ to each atom in body(qi).
Theorem 1. If O is an ontology and Q is a union of conjunctive queries that is legal under the OWL 2 QL DSER, AnsDSER(Q, O) = AnsByDat(Q, O). Proof (sketch). Let Can(O) be the canonical model of O. Can(O) contains both elements belonging to VNO and elements belonging to a set of variables Vsk. Furthermore, let H be the minimum Herbrand model H of P containing DO. Finally, let Dif f O be the subset of VIO × VIO (where VIO denotes the subset of elements of VNO that occur in individual position in O) such that every pair (a, b) ∈ Dif f O is such that a and b are interpreted as distinct domain elements in every model of O. The proof relies on the following properties. First, H is such that a tuple belongs to a predicate in Sql,A \{diff} if and only if a corresponding extensional property is satisfied in Can(O), over elements of VNO. For example, for every (c, x) that belongs to instc in H, x ∈ cCan(O), where x ∈ VNO. Also, for every (r, x) that belongs to existR in H, there exists y ∈ Vsk such that (x, y) ∈ rCan(O), where x ∈ VNO. Second, H is such that a tuple belongs to a predicate of Sql,T if and only if the corresponding intensional property is satisfied by Can(O). Thus, for example, for every (c1, c2) that belongs to isacCC in H, we have that for every x, if x ∈ c1Can(O), then x ∈ c2Can(O). Also, for every (c, r) that belongs to isacCR in H, we have that for every x, if x ∈ c1Can(O), then there exists y such that (x, y) ∈ rCan(O). Third, H is such that for every (x, y) that belongs to diff in H, (x, y) ∈ Dif f O, where x, y ∈ VNO. It can be shown that, by virtue of the above properties, since a tuple t is an answer to a query Q over O under DSER if and only if t is an answer to Q over the restriction of Can(O) to the elements of VNO, and since t is an answer to PQ if and only if Ans(t) belongs to H, then t is an answer to a query Q over O under DSER if and only if Ans(t) belongs to H.
It is worth noting that the AnsByDat algorithm works for all queries that are legal under DSER. Hence, in particular, it allows to answer queries comprising
As for complexity, we remark that the algorithm above is obviously PTime in both data and ontology complexity, since the evaluation of a Datalog program is PTime in data complexity. 4
In this section we investigate query answering over OWL 2 QL ontologies, under a SPARQL entailment regime, called Direct Semantics Answering Regime (DSAR), obtained from DSER by defining answers to conjunctive queries as in classical first-order semantics. In particular, based on previous results, we show that query answering under DSAR is undecidable, we identify a specific class of queries with DifferentIndividuals, for which the problem is tractable and provide an algorithm for answering queries within such class that is AC0 in data complexity.
We first formally introduce the (OWL 2 QL) DSAR. Specifically, DSAR is such that (i) it adopts the same syntax and semantics of DSER for the queried ontology, i.e., it considers OWL 2 QL ontologies interpreted according to DS, (ii) it considers as legal the same set of queries that are legal under DSER, i.e., any query that is a conjunction of OWL 2 QL assertions, and (iii) it defines the set of answers to a conjunctive query as follows. Let t be an n-tuple of IRIs and q a conjunctive query over O. t is an answer to q over O under DSAR, and we write t ∈ AnsDSAR(q, O), if
O |= ∃y σ[x → t](body(q)), where x are the target variables of q and y are the existential variables of q. Note that, in contrast to DSER, DSAR assigns to existentially quantified variables the classical logical meaning. Finally, answers to unions of conjunctive queries under DSAR are defined as under DSER, i.e. as the result of computing the union to the answers to each conjunctive query in the union.
The following lemma immediately follows from the fact OWL 2 QL is based
on DL-LiteR and from results of [
Inspired by results of the previous section, in order to identify a class of queries for which query answering under DSAR is decidable, we introduce the notion of query with bound inequalities. Specifically, given a query Q we say that Q is with bound inequalities if for every variable x, if x occurs within a DifferentIndividuals atom of Q, then x is a target variable of Q. Intuitively, a query with bound inequalities is such that if it requires two objects to be distinct, such objects are to be distinct in every model of O. Obviously, all queries that do not involve inequalities are queries with bound inequalities.
We now present the algorithm AnsByRew for answering queries over OWL 2 QL
ontologies under DSAR. Given an ontology O and a query Q with bound
inequalities that is a union of conjunctive queries q1, . . . , qp, the algorithm AnsByRew
proceeds as follows:
1. it constructs an instance BO of the schema Sql by applying τ to every axiom
of O, thus storing into BO a relational representation of O;
2. it evaluates the program Pql,T over BO;
3. it rewrites Q into a query Q0 by applying the rewriting technique proposed
in [
Theorem 2. If O is an ontology and Q is a query with bound inequalities legal under DSER, then AnsDSAR(Q, O) = AnsByRew(Q, O).
Proof (sketch). The proof relies on two crucial properties. First, the evaluation of the program PQL,T computes the closure of the TBox of O. Thus, the instances of the predicates in Sql,T in BO represent all TBox axioms logically implied by O, and logical implication of TBox atoms can be checked by evaluating their encoding through τ on BO. Second, since Q is such that its DifferentIndividuals atoms involve only target variables, any tuple t that is a certain answer to Q is such that there exists ti, tj ∈ t such that DifferentIndividuals(ti, tj) belongs to the minimum model of P that contains BO.
Clearly, the above theorem shows that query answering under DSAR is AC0 in data complexity, for the class of queries with bound inequalities, while it is PTime in ontology complexity.
Also, it is easy to see that query answering under DSER can be reduced to query answering under DSAR. Hence, it follows that one can use AnsByRew to solve query answering under DSER, which in particular shows that the complexity of the algorithm AnsByDat is not optimal. Still, we argue that AnsByDat may be useful and its usage may be sometimes convenient since it allows to exploit commercial highly optimized Datalog engines. 5
In this work we have investigated query answering in OWL 2 QL under the SPARQL DSER, taking into account specific aspects arising from a careful adherence to all the standards in play. In particular, we have shown that despite the set of legal queries for DSER comprise queries with inequalities, query answering under DSER can be reduced to the evaluation of a Datalog program. Furthermore, we have introduced a SPARQL entailment regime that defines answers to conjunctive queries as in classical first-order semantics, and have provided a query answering algorithm for answering queries under such regime, for a restricted class of queries with inequalities, that is AC0 in data complexity.
We plan to continue our work along several directions. In particular, we plan to consider query answering for other more general classes of queries with inequalities that are legal under DSER, aiming at finding what is the boundary between decidable (tractable) and undecidable (untractable) query answering. Also, we plan to carry out an experimental comparison of the perfomance of query answering under DSER using Datalog rewriting with that of query answering under DSER using the rewriting technique proposed in Section 4. Acknowledgements We gratefully acknowledge support by the MIUR under the SIR project MODEUS (RBSI14TQHQ), and by Regione Lazio under the project MAGISTER.