Answering Metaqueries over Hi (OWL 2 QL) Ontologies

1 Introduction

The interest in extending ontology languages with metamodeling (i.e., metaclasses and metaproperties) and metaquerying is growing considerably [de Carvalho et al., 2015]. Roughly speaking, a metaclass is a class (unary predicate) whose instances can be themselves classes, a metaproperty is a relationship (binary predicate) between metaclasses, and a metaquery is a query where variables can appear in both predicate and object position. As pointed out, for example in [Guizzardi et al., 2015], these features are important in many scenarios, such as modeling provenance of data, biological taxonomy (where the notion of species is crucial), product manufacturing (where product types have properties to be described and retrieved), or, in general, in ontology-based data access and integration, where data sources often contain not only objects, but also information about the classes which objects belong to, and such classes are to be modeled also as individuals in the ontology.

Unfortunately, the treatment of the above features in OWL2, which is the de-facto ontology language, is unsatisfactory. As a simple example, suppose we want to retrieve all individual animals which live in Central Park Zoo (CPZ), and are instances of a class corresponding to an endangered species

(ES). The natural formulation of the corresponding metaquery is Q = ¶ (y) ♣ 9x ES(x) ^ x(y) ^ lives(y↪ CPZ) ♦. However, this query is not legal under the OWL2 Direct Semantics (DS), which is the formal semantics adopted for interpreting the logical theories corresponding to OWL2 ontologies. In particular, Q violates the so-called typing constraint, which, intuitively, rules out the possibility of using the same variable in incompatible positions (for example, in individual and in class position). The reason for such a limitation is that under DS no element can simultaneously be an individual and a class, which severely hampers the possibility of using metamodeling and metaquerying in OWL2. To remedy this situation new semantics (e.g., [Motik, 2007; De Giacomo et al., 2011; Lenzerini et al., 2016]) have been proposed, mostly based on HiLog [Chen et al., 1993], which is a logic with a higher order syntax based on a Henkin-style semantics. We refer, in particular, to the semantics presented in [Lenzerini et al., 2016], specifically defined for Hi(OWL2QL) but generalizable to all Description Logics. In this semantics, each object in an interpretation can simultaneuosly be an individual object, a class, an object property (or, relationship), a data property (or, attribute), and a datatype, and therefore fully supports the kinds of metaqueries discussed above. Moreover, since classes and properties are first-order citizens, this semantics naturally pushes towards full metaqueries, i.e., queries where ABox atoms, i.e., instance assertions, and TBox atoms, such as ISA (e.g., every eagle is a bird, Eagle v Bird) or disjointness (e.g., every eagle is not a condor) assertions coexist. An example of such queries is the one obtained from Q by requiring that the endangered species is a subclass of Bird: ¶ (y) ♣ 9x ES(x) ^ x(y) ^ x v Bird ^ lives(y↪ CPZ) ♦.

The goal of our work is to study algorithms for, and complexity of full metaquerying. We are especially interested in analyzing the case of OWL2QL, the tractable fragment of OWL2, that is the most popular language used in the context of ontology-based data access, and checking whether the nice computational characteristics of the logic are kept when we move to full metaquering.

Several papers are relevant for our work. [Motik, 2007] studies the complexity of the inference problem in OWL Full, and suggests a HiLog-style semantics, further investigated in [De Giacomo et al., 2011], which presents an algorithm based on the metagrounding technique for answering a specific class of queries, called guarded. [Glimm et al., 2010] and [Pan and Horrocks, 2006] present techniques for metamodeling by axiomatizing higher-order knowledge into first order assertions, and introducing the stratification of class constructors and axioms, respectively. Other papers with focus on ontology languages with metamodeling capabilities are [Jekjantuk et al., 2010; Homola et al., 2013; 2014; Kubincov´a et al., 2015], but none of them face the problem of query answering in such context. Relevant to our work are recent papers aiming at devising efficient techniques to answer SPARQL queries posed over OWL2QL ontologies [Arenas et al., 2014; Kontchakov et al., 2014; Kollia and Glimm, 2013]. However, such papers concentrate on DS, and therefore do not aim at the full power of metamodeling and metaquerying. The conclusion is that none of the above papers provide results for full metaquerying. Indeed, to our knowledge, it is unknown whether the problem of answering full metaqueries is decidable, even for the case of lighweight ontology languages such as OWL2QL.

In this paper we present several results about answering full metaqueries in Hi(OWL2QL).

• ÷ We identify a class of ontologies satisfying a certain completeness condition (TBox-completeness), and show that answering full metaqueries over ontologies within such a class has the same complexity as answering queries with ABox atoms only, over OWL2QL ontologies under DS.
• ÷ We show that query answering over general ontologies is decidable. In particular, we present a query answering algorithm that is in AC0 w.r.t. ABox complexity, in coNP w.r.t. ontology complexity and in ⇧p2 w.r.t. combined complexity. This is the first decidability (actually, tractability w.r.t. ABox complexity) result for full metaqueries over OWL 2.
• ÷ We provide complexity lower bounds for answering conjunctive metaqueries, showing that the problem is coNPcomplete w.r.t. ontology complexity, and ⇧p2 -complete w.r.t. combined complexity, thus sharpening the intractability results in [De Giacomo et al., 2011] for queries in the presence of union.
• ÷ Motivated by the fact that, in practice, TBox-complete ontologies may be automatically obtained by applying specific ontology design methodologies, we focus on them and present an optimized algorithm for answering queries over TBox-complete ontologies. Experiments show that the optimized algorithm outperforms the one based on blind metagrounding.

2 Preliminaries

In this section we briefly recall the Hi(OWL2QL) ontology, the metaquery language, and the metaquery answering technique based on metagrounding. For details, please refer to [Lenzerini et al., 2016].

Ontology language The syntax of Hi(OWL2QL) is the same as the one of OWL2QL. In this work, we express ontologies and queries in the extended functional style syntax [Glimm, 2011]. Axioms are classified into (i) positive TBox axioms, i.e., SubClassOf, SubObjectPropertyOf, SubDataPropertyOf, ReflexiveObjectProperty, and DataPropertyRange, (ii) negative TBox axioms, i.e., DisjointClasses, DisjointObjectProperties, DisjointDataProperties, and IrreflexiveObjectProperty, and (iii) ABox axioms, i.e., ClassAssertion, ObjectPropertyAssertion, and DataPropertyAssertion.

The vocabulary VO of an Hi(OWL2QL) ontology O is defined as (V O N , V O C , V O OP , V O DP , V O DT , LOQL ), where (i) V O N is the set of IRIs occurring in O extended with the OWL2QL reserved vocabulary, (ii) V O C is the subset of V O N consisting of the IRIs appearing in class positions in O (i.e., in a SubClassOf or DisjointClasses axiom, or in a Declaration(Class) axiom, or in the first position of a ClassAssertion axiom), or are reserved IRIs denoting classes, (iii) V O OP , V O DP , V O DT are defined similarly for object properties, data properties, and datatypes, and (iv) LOQL is the set of literals occurring in some logical axiom of O. Note that, by virtue of OWL2 punning, the same entity name can in fact appear in positions of different types (e.g., as an argument of a SubClassOf axiom and as the argument of an ReflexiveObjectProperty axiom). Thus, V O C ↪ V O OP , V O DP and V O DT may not be disjoint. Also, we denote with ExpO the finite set of all well-formed expressions that denote elements of the ontology, and can be built on the basis of VO. For example, if e1↪ e2 are well-formed expressions, then ObjectSomeValuesFrom(e1e2) is a well-formed expression too. Note that ExpO is actually partitioned into class expressions (ExpOC ), object property expressions (ExpOOP ), V O DP , and V O DT . For example, ObjectSomeValuesFrom(e1e2) is a class expression in ExpOC .

The semantics of Hi(OWL2QL), called Higher-Order Semantics (HOS), is based on the notion of interpretation structure, which plays the same role as the "interpretation domain" in classical first-order logic. Specifically, an interpretation structure is a tuple ⌃ = h∆o↪ ∆v↪ ·I ↪ ·E ↪ ·R↪ ·A↪ ·T i where:

• ÷ the object domain ∆o and the value domain ∆v are two disjoint non-empty sets;
• ÷ ·E : ∆o !P(∆o) is a partial function;
• ÷ ·A : ∆o !P(∆o ⇥∆v) is a partial function;
• ÷ ·R : ∆o !P(∆o ⇥∆o) is a partial function;
• ÷ ·T : ∆o !P(∆v) is a partial function;
• ÷ ·I : ∆o ! ¶T↪ F♦ is a total function such that for each d 2 ∆o, if ·E ↪ ·R↪ ·A↪ ·T are all undefined for d, then dI = T.

Note that domain objects are polymorphic: each of them can simultaneuosly be an individual object (this is the case where function ·I is T), a class (·E is defined), an object property (·R is defined), a data property (·A is defined), and a datatype (·T is defined). A crucial aspect of such interpretation structure, which distinguishes it from the one proposed in [De Giacomo et al., 2011], is that the functions ·E , ·R, ·A, and ·T are partial, so that, for example, an object can be both an individual and an object property without being a class. The importance of this feature for metaquerying will be clear later in the paper. An interpretation J for O is a pair, h⌃J ↪ Io J i, where ⌃J = h∆Jo ↪ ∆Jv ↪ ·IJ ↪ ·EJ ↪ ·RJ ↪ ·AJ ↪ ·TJ i is an interpretation structure and Io J is the interpretation function for J, i.e., a function that maps every expression in ExpO into an object in ∆Jo , and every literal in LQL into a value in ∆Jv , according to a set of suitable conditions. The semantics of logical axioms is based on the usual notion of satisfaction of an axiom with respect to an interpretation J. Also, the notions of model and satisfiability of an ontology are the usual ones. Finally, if ↵ is an axiom, we say that ↵ is logically implied by an ontology O if it is satisfied in every model of O, while ↵ is violated by O if O [ ¶↵♦ is unsatisfiable.

Query language. As for the query language, we concentrate on unions of boolean conjunctive queries (simply called queries in the following). A boolean conjunctive query q over an ontology O is an expression of the form ask where B, where B, called query body 1 , is a conjunction of atoms over VO. Thus, an atom has the same form of a logical axiom and involves, besides symbols in VO, variables in an alphabet V disjoint from VO. We call metavariable of a query a variable that occurs in predicate position (i.e., class position, object property position, dataproperty position or datatype position) in the query, and we say that an atom is (meta)ground if no (meta)variable occurs in it. A query is ground (resp. metaground) if all its atoms are ground (resp. metaground), and is an instance query if it includes ABox atoms only.

The semantics of queries resorts to (↵) interpreting the queried ontology according to HOS, (β) extending the class of legal queries for the SPARQL DS entailment regime, by relaxing the so-called typing constraint, and (γ) defining the answers to a query as the usual notion of certain answers, where both union, and existentially quantified variables are assigned the classical logical meaning.

Query answering through metagrounding. Given a query Q, an n-tuple ~x of variables of Q, and an n-tuple ~t of expressions and literals, the ~x-instantiation of Q with ~t, denoted INST(Q↪ ~x ~t), is the query obtained fromQ by first substituting each xi in ~x with ti in ~t, for i 2 ¶1↪ ▷ ▷ ▷ ↪ n♦, and then replacing non Hi(OWL2QL) atoms, if any, with equivalent Hi(OWL 2 QL) atoms involving new variables 2 .

A metagrounding of Q with respect to O is an ~xinstantiation of Q with any n-tuple ~t, where x1↪ x2↪ ▷ ▷ ▷ ↪ xn are the metavariables in Q, and for every i 2 ¶1↪ ▷ ▷ ▷ ↪ n♦, if xi occurs in class (object property, data property, datatype) position in Q, then ti is any expression in ExpOC (resp. ExpOOP , V O DP , V O DT ) that occurs in O. We denote by MG(Q↪ ExpO ) the metaground query that is the union of all metagroundings of Qw.r.t. O. As reported in [Lenzerini et al., 2016], it can be shown that answering a union of conjunctive instance queries Q over an Hi(OWL2QL) O can be reduced to answering MG(Q↪ ExpO ), for which one can use the well-known rewriting approach, typical of the DL-Lite family (see, for instance, [Calvanese et al., 2007]). In other words, instance metaqueries in Hi(OWL 2 QL) can be dealt with the so-called metagrounding technique. A similar observation holds for the problem of checking satisfiability of a Hi(OWL 2 QL) ontology.

In the next sections, we study the complexity of query answering: given a Hi(OWL2QL) satisfiable ontology O, and a full metaquery Q over O, is the certain answer of Q w.r.t. O true (i.e., O ♣= Q)? In particular, we refer to different assumptions: (i) T ↪ ExpO and Q are fixed (ABox complexity), (ii) Q is fixed (ontology complexity), (iii) A and Q are fixed (TBox complexity), and (iv) no component of the input is fixed (combined complexity).

1 In SPARQL jargon, a query body is a basic graph pattern.

2 E.g., ClassAssertion(ObjectSomeValuesFrom(e1e2)e3) is replaced by the conjunction of ObjectPropertyAssertion(e1e3w) and ClassAssertion(e2w), where w is a new variable.

We finally point out that, from now on, we implicitly assume to deal with a satisfiable Hi(OWL2QL) ontology O and a query Q over O, and we assume that O does not contain any data property 3 .

3 TBox-complete ontologies

We start with an example highlighting a source of complexity in answering metaqueries over general ontologies.

Example 1 Let O1 be the following ontology:

ClassAssertion(:B :F), ClassAssertion(:C :F), DisjointClasses(:A :C), ObjectPropertyAssertion(:R :E :E), ObjectPropertyAssertion(:R :C :A), ObjectPropertyAssertion(:R :B :C).

and let Q be the query: ask ¶DisjointClasses(:A $x). ClassAssertion(:B $y). ObjectPropertyAssertion(:R $x $z).ClassAssertion($z $y)♦ .

It is not hard to see that there exists no substitution θ of the metavariables of Q1 for which θ(Q1) is true in every model of O1. So, metagrounding does not suffice in this case. On the other hand, suppose to partition the sets of models of O1 into the set M1 of models in which :A and :B are interpreted as non-disjoint classes, and the set M2 of models in which :A and :B are interpreted as disjoint classes. Then, consider the metagroudings of Q1 with the following substitutions: θ1 : ¶x :C, z :A♦, and θ2 : ¶x :B, z :C♦. Clearly, θ1(Q1) is satisfied in every model of M1, while θ2(Q1) is not. On the other hand, θ2(Q1) is satisfied in every model ofM2, while θ1(Q1) is not. Therefore, for every every model there exists a substitution of variables that makes Q1 evaluate to true, which proves that O1 ♣= Q1. 2

The example shows that, in the presence of TBox atoms in the query, query answering requires to reason by cases, originating from negative TBox axioms which are neither logically implied by O nor violated by O. Motivated by the latter observation, in this section we investigate query answering for a class of ontologies, called TBox-complete, for which such a possibility does not exist.

Let U O denote the set of negative axioms that can be constructed over V O N . If ↵ is an axiom in U O , ↵ is said to be certain if either O ♣= ↵, or ↵ is violated by O; otherwise, we say that ↵ is uncertain. Thus, if every negative axiom in U O is certain, then we say that O is TBox-complete. Note that every unsatisfiable ontology is trivially TBox-complete.

Example 2 The ontology O1 presented in Example 1 is not TBox-complete. Indeed, both the axioms DisjointClasses(:A :B) and DisjointClasses(:B :A) are neither logically implied nor violated by O1. 2

3 The whole approach can be extended to capture data properties too.

The conceptual tool we use for addressing query answering in a TBox-complete ontology O is a variant of the chase used for DL-Lite [Calvanese et al., 2007]. We build a (possibly infinite) structure, starting from an initial structure Chase0 (O), and then repeatedly computing Chasej+1 (O) from Chasej (O) by applying suitable rules. In doing so, we make use of an infinite alphabet So of variables, disjoint from ExpO and LOQL , for introducing new unknown individuals, when needed. The initial structure Chase0 (O) is defined as the set of axioms obtained from O by adding, for every class C that is nonempty in O (i.e., such that the TBox does not logically imply DisjointClasses(C C)), an axiom asserting that C contains a new unknown individual in So, that is specific for C, and doing a similar addition for non-empty object properties. Intuitively, the new individual for C will be an instance of only those classes that are superclasses of C in O (similarly, for object properties), and therefore will be used in the chase to falsify all subset and disjointness relations that are not implied by O. Then, to compute Chasej+1 (O) from Chasej (O) we apply one of the chase rules, where each rule can be applied only if suitable conditions hold. For example, if ClassAssertion(c1 e)2 Chasej (O), SubClassOf(c1 ObjectSomeValuesFrom(p c)) 2 O, and 8e0 such that ObjectPropertyAssertion(p e e0 ) 2 Chasej (O), we have that ClassAssertion(c e0 )◁2 Chasej (O), then we set Chasej+1 (O)=Chasej (O)[¶ClassAssertion(c s), ObjectPropertyAssertion(p e s♦, where s 2 So does not appear in Chasej (O). Finally, we set Chase(O) = Si2N Chasei (O). Note that Chase(O) is a (possibly infinite) set of ABox axioms.

• ÷ ⌃Can(O) is an interpretation structure such that (i) ∆Can(O) o = (ExpO [So), (ii) ∆Can(O) v = D, where D is the set data values admitted in OWL2QL, (iii) if e occurs in individual position in Chase(O), then eICan(O) = T otherwise eICan(O) = F, and (iv) the various functions ·ICan(O) ↪ ·ECan(O) ↪ ·RCan(O) ↪ ·ACan(O) ↪ ·TCan(O) are derived from Chase(O); e.g., if e ◁2 ExpOC then ·ECan(O) is undefined for e; otherwise, if e 2 V O C , then eECan(O) = ¶e1 ♣ ClassAssertion(e e1) 2 Chase(O)♦, and similarly for the other cases of e 2 ExpOC .

Based on Chase(O), we define the model (called canonical) Can(O) of O as follows:

• ÷ IoCan(O) is such that (i) it maps every expression into itself, i.e., for every e 2 ExpO , eIo Can(O) = e, and (ii) it maps every literal according to the OWL2QL datatype map.

Let us now show that Can(O) plays a crucial role in representing the set of all models of O. To this aim, we need to introduce the notion of extended homomorphism. If M is a model of O, we say that a function from∆Can(O) o to ∆Mo and from∆Can(O) v to∆Mv is an extended homomorphism from Can(O) to M if for every e 2 ExpO , (e) = eIoM , for every v 2 D, (v) = v, and all the semantic properties that are expressible in terms of Hi(OWL2QL) axioms and hold in Can(O), are preserved inM under . For example, for every e1↪ e2 2 ∆Can(O) o such that eECan(O) 1 ✓ eECan(O) 2 ,

(e1)EM ✓ (e2)EM .

Proposition 3 If O is TBox-complete, then for everymodelM of O, there exists an extended homomorphism from Can(O) to M.

Two aspects are essential for the proof of the above theorem. First, the functions ·ECan(O) ↪ ·RCan(O) ↪ ·ACan(O) ↪ ·TCan(O) are undefined for each newly introduced unknown individual taken from So. This is possible with HOS because, unlike in other semantics, such functions are partial. Indeed, when the above functions are total, each newly introduced unknown individual is a class, that either (i) is empty, in which case it represents a subset of every class in the ontology, or (ii) has at least one instance. Both cases prevent the existence of an extended homomorphism from Can(O) to every model of the ontology. Second, it is crucial that for every class C that is non-empty in O, we have added a new instance for C in Chase(O) (all similar additions for non-empty object properties are also essential). Such new instances are harmless for ABox atoms, but are crucial for TBox axioms, because they prevent TBox axioms that are not implied by O to be satisfied by Can(O). Based on Proposition 3, one can show the following.

Proposition 4 If O is TBox-complete, then O ♣= Q if and only if Can(O) ♣=MG(Q↪ExpO ).

We finally address the problem of checking whether Can(O) ♣= MG(Q↪ExpO ). First notice that Can(O) ♣= MG(Q↪ ExpO ) if and only if Can(O) ♣= Q0 for some ground conjunctive query Q0 which is a disjunct of MG(Q↪ ExpO ). So, it remains to illustrate a method for checking whether Can(O) satisfies a metaground conjunctive query.

Proposition 5 If O is TBox-complete and Q is a metaground conjunctive query, then Can(O) ♣= Q if and only if O ♣= int(Q) and Can(O) ♣= ext(Q), where ext(Q) and int(Q) denote the conjunctions of ABox and TBox atoms of Q, respectively.

Propositions 4 and 5 suggest an algorithm, based on blind metagrounding, that we call NAIVE. Given a TBox-complete ontology O, the set ExpO , and a query Q, NAIVE computes MG(Q↪ExpO ) and answers "true" if and only if for some conjunctive query Q0 that is a disjunct of MG(Q↪ExpO ), it holds that: (i) all the atoms in int(Q0 ) are logically implied by O, and (ii) O ♣= ext(Q0 ). Hence, query answering over TBox-complete ontologies can be done by using any off-theshelf OWL 2 QL reasoner. The following theorem characterizes the complexity of the problem.

Theorem 6 Query answering over TBox-complete ontologies is in AC0 w.r.t. ABox complexity, PTIME w.r.t. ontology complexity, and NP-complete w.r.t. combined complexity.

4 General ontologies

In this section, we address query answering over general ontologies, by first providing a non-deterministic algorithm, and then studying the complexity of the problem.

Let us first introduce the notions of violation set and ontology completion, both crucial to characterize the sets of models of O under HOS. If ↵ is a negative axiom in U O , we call violation set of ↵ w.r.t. O, a minimal set of ABox axioms V↵↪O, whose entities in predicate position belong to V O N , and entities in individual position are IRIs not in V O N , specific for ↵, and such that ↵ [ V↵↪O is unsatisfiable. For example, a violation set of ↵1 =DisjointClasses(C1 C2) is the set ¶ClassAssertion(C1 s↵1 ), ClassAssertion(C2 s↵1 )♦ where s↵1 is an IRI not in V O N . Also, if σ is a subset of U O , the σ-completion of O, denoted Oσ , is the ontology O[σ[C U O ∩σ , where C U O ∩σ is the union of the violation sets of axioms in U O that are not in σ. Intuitively, Oσ is obtained from O by adding all axioms in σ and suitable axioms in such a way that all axioms in U O but not in σ are violated. Note that Oσ may not be satisfiable, and is TBox-complete. The following theorem shows the importance of ontology completion.

Theorem 7 O 2 Q if and only if there exists a subset σ of U O such that Oσ 2 Q.

From Theorem 7 it is easy to derive a nondeterministic algorithm for checking whether the certain answer to Q is false: non deterministically guess a subset σ of U O , and then check whether Oσ 2 Q. The following characterizes query answering complexity over general ontologies.

Theorem 8 Query answering is coNP-complete w.r.t. TBox complexity, ⇧p2 -complete w.r.t. combined complexity, and AC0 w.r.t. ABox complexity.

Proof (Sketch) The ontology and the combined complexity upper bounds can be easily derived by considering the above nondeterministic algorithm and Theorem 6. As for the ABox complexity, one can show that given an ontology O, for every query Q, answering Q over O can be reduced to the problem of answering a first-order query Q0 over an ontology O0 , where the size of Q0 does not depend on the ABox and the size of O0 is linear in the size of the ABox. In a nutshell, O0 is built as follows. First, for every subset σ of U O , we compute the ontology (Oσ )0 by substituting in Oσ every occurrence of an entity E that is not an individual with Eσ, and by adding the axiom SubClassOf(E Eσ) if E is a class, and SubObjectPropertyOf(E Eσ) if E is an object property. Then, O0 is defined as the union of the ABox of O with (Oσ )0 , for every σ. As for Q0 , we define, for every σ, the query (Qσ)0 that is the rewriting of Qσ [ Qunsat↪σ w.r.t. O0 , where Qσ is obtained by renaming the entities occurring in Q accordingly to (Oσ )0 , and Qunsat↪σ is the query that checks whether (Oσ )0 is unsatisfiable (such query can be easily derived from the TBox of (Oσ )0 ). We then obtain Q0 as the union of all (Qσ)0 . It can be shown that (Qσ)0 is a first-order query such that O 6♣= Q iff (Qσ)0 is false when evaluated over the ABox of O.

As for the TBox complexity lower bound, the proof is by reduction from 3-SAT. Given a 3-CNF formula F, we define an ontology OF with an individual g, one class ci for each clause ci, classes dj↪ pj↪ pj for each letter pj, classes B↪D, object properties R1↪ ▷ ▷ ▷ ↪R5. The axioms of OF are D(g)↪ DisjointClasses(B D), plus suitable axioms representing the literals in the various clauses (e.g., a clause c1 with literals p2↪ ≻p4↪ p5, is represented by R1(c1↪ p2)↪R2(c1↪ p4)↪R3(c1↪ p5) plus R4(c1↪D)↪R5(c1↪D)), and suitable axioms representing complementary literals (e.g., R4(d2↪ p2)↪R5(d2↪ p2) plus R1(d2↪B)↪R2(d2↪B)↪R3(d2↪B) for literals on the letter p2). The idea is that there is a one-to-one correspondence between each model M of F and the models of OF where each class pi (or pi) is disjoint from D iff pi (or pi) is false in M. We then define a query QF simply asking whether there exists a class ci such that all classes corresponding to the literals in the clause ci are disjoint fromD, or a class dj such that both pj and pj are not disjoint from D. It can be shown that F is satisfiable iff the certain answer to QF w.r.t. OF is false. coNP-completeness follows from the fact that the size of OF is polynomial w.r.t. to the size of F, and the size of QF is constant.

Finally, to show the combined complexity lower-bound, the proof is by reduction from the problem of checking the satisfiability of a Quantified Boolean Formula of the form 8x1↪ ▷ ▷ ▷ ↪ xn9y1↪ ▷ ▷ ▷ ↪ ymc1 ^ · · · ^ ck to query answering in Hi(OWL2QL), in such a way that both the TBox of the resulting ontology and the query have polynomial size with respect to the size of the formula. 2

5 Optimization

In this section we present an optimized algorithm, called LAZY METAGROUNDING (LMG), for query answering over TBoxcomplete ontologies. LMG generalizes the idea of the algorithm proposed in [Lenzerini et al., 2014] that was targeted to instance queries over Hi(DL-Lite) ontologies. We then conclude the section by presenting a set of experiments showing that LMG outperforms the NAIVE algorithm, based on blind metagrounding.We point out that assuming to deal with TBoxcomplete ontologies is reasonable in practice. Indeed, once the domain analysis has highlighted the set of negative axioms that are certain, an automated procedure can be devised, that adds suitable facts to make the remaining negative axioms violated. We argue that, in most cases, such an addition achieves TBox-completeness without changing the intended models of the ontology.

Similarly to the NAIVE algorithm, LMG aims at exploiting existing OWL2QL reasoners as blackboxes computing answers to instance queries without metavariables. However, LMG improves NAIVE by significantly reducing the number of queries to be evaluated, by adopting an optimization strategy targeted to a scenario where the ABox is stored in a relational database ATB (this corresponds to the OBDM scenario, where the so-called "virtual ABox" is expressed by mappings [Lenzerini, 2011]), and additional relations in such database store the logical closure of the TBox (e.g., the table SubClassOf stores all pairs C1↪ C2 such that O ♣= SubClassOf(C1C2)).

The BUILDQUERYPLAN function. First, based on Q( ~Xd), the

While presenting LMG, we go beyond boolean queries, and deal with queries with distinguished variables. Coherently with SPARQL we sanction that in the answers to a query Q( ~X), the distinguished variables ~X are bound to IRIs. Given an ontology O and a query Q(Xd), LMG applies two functions: (i) BUILDQUERYPLAN, computing a sequence S of annotated queries encoding a query plan, (ii) and EXECUTEQUERYPLAN, executing S over O.

function constructs a graph G as follows. The nodes of G are the atoms of Q and there is an edge from a1 to a2 if and only if at least one of the following occurs: (i) a1 is a TBox atom, a2 is an ABox atom and a1 involves a variable occurring in a2; (ii) a1 and a2 are ABox atoms and a1 involves a variable in individual position that occurs in predicate position in a2; (iii) there is a variable x of Q that is not a metavariable, is not in Xd, and occurs in individual position both in a1 and a2 (in this case, there will be an edge also from a2 to a1). Intuitively, the function defines an edge from a1 to a2 to indicate that a1 has to be evaluated before a2, according to the following observations: (1) in order to exploit an OWL2QL reasoner one needs to instantiate the metavariables (see condition), (2) since the number of TBox axioms logically implied is typically less than the number of ABox axioms logically implied, to minimize the instantiations of the metavariables, it is preferable to evaluate the TBox atoms first (see condition (i)), and (3) in order to provide correct answers, atoms sharing existential variables in individual positions should be evaluated together (see condition (iii)).

Second, BUILDQUERYPLAN annotates each atom a of G with an integer d(a) indicating its depth, by using the following strategy: (a) assign 0 to each TBox atom and set k 1; (b) do the following until the graph is empty: (b.1) remove from G atoms with depth k - 1 together with their incoming edges; (b.2) assign k to each atom n occurring in a strongly connected component C; (b.3) k k +1.

Third, the function computes a sequence of queries S = (q0↪ ▷ ▷ ▷ ↪ qm), where m is the maximal depth of atoms in G, and qi is such that its body is the conjunction of all atoms at depth i and its distinguished variables are all variables in its body that are in ~Xd or are metavariables in Q. Intuitively, BUILDQUERYPLAN aims at minimizing the number of conjunctive queries to be evaluated by an OWL2QL reasoner, by maximizing the number of atoms of the original query that can be evaluated within the same conjunctive query, based on the ordering induced by the edges of G.

The EXECUTEQUERYPLAN function. Based on S, the function progressively builds the answers to Q by storing into an intermediate relation Ai the result of executing the join operator of relational algebra between Ai-1 and the answers to qi. The goal of Ai is twofold: on one hand it maintains a projection of the answers to Q (if any) computed so far by evaluating the portion of Q consisting of the subqueries q0↪ ▷ ▷ ▷ qi; on the other hand, it provides bindings for the metavariables of qi+1 to obtain a metaground query evaluable using standard OWL 2 QL reasoners. Given the query plan S = (q0( ~wo)↪ ▷ ▷ ▷ ↪ qm( ~wm)), EXECUTEQUERYPLAN proceeds as follows.

• ÷ It evaluates q0 over the ATB database, and stores its answers into A0.
• ÷ For every i = 1↪ ▷ ▷ ▷ ↪m, let ~vi be the tuple of variables appearing in ~wi or ~vi-1 that are input variables of qi+1 (i < m), or are in ~Xd of Q (~v0 is assumed to be simply ~w0). The function first builds the query q00 i as the union of the various INST(qi↪ ~w0i ~t), where ~w0i are the input variables of qi, and ~t is a tuple in the projection of Ai-1 onto such input variables. Then, to cope with metavariables in q00 i that are not input variable of qi,
• it computes the metagrounding of q00 i , evaluates it and stores its answers in Gi. Finally, the function computes Ai by executing the join between Ai-1(~vi-1) and Gi.
• ÷ The function returns the set of tuples of IRIs in Am disregarding possible complex expressions in Am.

Theorem 9 Given a TBox-complete ontology O and a query Q, LMG terminates and computes the certain answers to Q over O.

Clearly, LMG is in PTIME w.r.t. data and ontology complexity, and in NP w.r.t. combined complexity.

Experiments. To test the practical applicability of LMG, we have conducted a set of experiments on query answering using both LMG, and NAIVE. In particular, we compared the evaluation time of 8 queries, over an ontology containing about 100000 ABox axioms, and 260 TBox axioms.

The tests have been performed using Mastro [Calvanese et al., 2011] as OWL 2 QL reasoner with java 7 on a Dell computer equipped with an Intel i7 2.70GHz processor, assigning 2GB memory to Java. The results of the experiments, reported in Table 1, show that, except for query Q1(x↪ y) (which is the query select $x $y ¶ClassAssertion($x $y)♦, for which LMG and NAIVE resort to evaluate the same set of queries over Mastro), LMG outperforms NAIVE in terms of evaluation time, thanks to the smarter instantiation of the metavariables performed by LMG. We point out that such a speed up increases with the number of variables occurring both in individual and predicate positions.

6 Conclusion

We plan to continue our work along several directions. We aim at studying interesting subclasses of queries, and characterize their complexity. For example, we already know that answering queries whose TBox atoms are ground is PTIME in ontology complexity, exactly like in [De Giacomo et al., 2011]. Furthermore, we plan to increase the expressive power of Hi(OWL2QL) by extending both the ontology language (for example, with mechanisms for expressing integrity constraints), and the query language (for example, by allowing the use of atoms with data types as predicates), while keeping the same computational complexity of metaquerying. Also, we aim at studying further optimization techniques for query answering, targeted towards storage structures for the ABox different from the one considered here.

Acknowlegments

Work supported by the EU under the FP7 project "Optique" - grant n. FP7-318338, by MIUR under the SIR project "MODEUS" - grant n. RBSI14TQHQ, and by Regione Lazio under the project "MAGISTER".