On queries with inequalities in DL-Lite6= R Gianluca Cima1 , Federico Croce1 , Maurizio Lenzerini1 , Antonella Poggi2,1 , Elian Toccacieli1 1 Dipartimento di Ingegneria Informatica, Automatica e Gestionale “Antonio Ruberti” 2 Dipartimento di Lettere e Culture Moderne Sapienza Università di Roma lastname@diag.uniroma1.it Abstract. It is well-known that answering conjunctive queries with inequalities (CQ6= s) over DL-LiteR ontologies is in general undecidable. In this paper we consider the subclass of CQ6= s, called CQ6=,b s, where inequalities involve only distinguished variables or individuals. In particular, we tackle the problem of an- swering CQ6=,b s and unions thereof (UCQ6=,b s) over DL-Lite6= R ontologies, where DL-Lite6=R corresponds to DL-LiteR without the Unique Name Assumption, and with the possibility of asserting inequalities between individuals, as in OWL 2 QL. As a first contribution, we show that answering CQ6=,b s over DL-Lite6=R ontologies has the same computational complexity as the UCQ case over DL-LiteR , i.e., it is in AC0 in data complexity, in PT IME in TBox complexity, and NP-complete in combined complexity. We then deal with the UCQ6=,b case, and prove that an- swering UCQ6=,b s over DL-Lite6= 0 R ontologies is still in AC in data complexity p and in PT IME in TBox complexity, but is Π2 -hard in combined complexity. 1 Introduction DL-LiteR is the Description Logic (DL) of the DL-Lite family [6] which underpins the OWL 2 profile OWL 2 QL [16]. It is arguably one of the most important formalisms of choice for representing ontologies in Ontology-based Data Access (OBDA) [18, 22] scenarios, where the aim is to access a typically huge amount of data residing in external data sources. In particular, DL-LiteR has been designed so that answering unions of conjunctive queries (UCQs) can be reduced to evaluating first-order logic queries over the database storing the ABox assertions, and therefore is in AC0 with respect to the size of the ABox, i.e., in the so-called data complexity [21]. While answering UCQs over DL-LiteR ontologies has been extensively studied in recent years (e.g., by establishing bound on the size of rewritings [10], developing opti- misation algorithms [19], and implementing systems for real-world applications [4, 5]), we argue that not much is known about the problem of answering conjunctive queries with inequalities (CQ6= s) and unions thereof (UCQ6= s). To the best of our knowledge, the basic facts that are known about these latter cases can be summarised as follows: – In stark contrast to the UCQ case, answering CQ6= s over DL-LiteR ontologies is in general undecidable [12]. – For subclasses of CQ6= s and UCQ6= s, named local CQ6= s and local UCQ6= s, re- spectively, query answering over DL-LiteR ontologies is decidable, but with a high CO NE XP T IME upper bound in data complexity. Furthermore, it is provably in- tractable (in general coNP-hard in data complexity) already for local CQ6= s [12]. – For the subclass of CQ6= with bounded inequalities (called CQ6=,b ), where inequali- ties involve only individuals or distinguished variables, query answering over DL-LiteR ontologies is in PT IME in data complexity and in E XP T IME in combined complex- ity [17]. Observe that all the above results hold regardless of whether the Unique Name As- sumption (UNA) is enforced or not. Also, it is immediate to see that, for DL-LiteR , they do not provide the answer to the question whether answering CQ6=,b s and unions thereof (UCQ6=,b s) has the same complexity as the UCQ case. As a first consideration on these classes of queries, we observe that, differently from the UCQ case [3], query answering over DL-LiteR ontologies is sensitive to the adoption of the UNA, even for CQ6=,b s, as shown in following example. Example 1. Consider the DL-LiteR ontology O = hT , Ai, where T = ∅ and A = {P (a, b)}. For the CQ6=,b q = {(x, y) | P (x, y) ∧ x 6= y}, it is easy to see that the tuple ha, bi is in the certain answers of q over O under the UNA, while it is not if the UNA is not enforced. Indeed, for the model M of O with aM = bM = e and P M = {(e, e)}, that does not respect the UNA, we have that q M = ∅. t u Notice, however, that answering UCQ6=,b s over DL-LiteR ontologies under the UNA is a straightforward generalisation of the UCQ case. Proposition 1. Answering UCQ6=,b s over DL-LiteR ontologies under the UNA is in AC0 in data complexity, in PT IME in TBox complexity, and NP-complete in combined complexity. Therefore, in what follows, we implicitly assume that the UNA is not enforced. In particular, in this paper we consider the DL DL-Lite6=R , which extends DL-LiteR with the possibility of asserting inequalities between individuals, as in OWL 2 QL, and we present the following results: – Answering CQ6=,b s over DL-Lite6= R ontologies has the same computational com- plexity of the UCQ case, i.e., it is in AC0 in data complexity, in PT IME in TBox complexity, and NP-complete in combined complexity (cf. Theorem 2). – Answering UCQ6=,b s over DL-Lite6= p R ontologies is Π2 -hard in combined complex- ity (cf. Theorem 3). – Answering UCQ6=,b s over DL-Lite6= 0 R ontologies is in AC in data complexity, in PT IME in TBox complexity, and in E XP T IME in combined complexity (cf. Theo- rem 4). Several recent works investigate the problem of answering UCQs over DL-LiteR ontologies [3, 6, 13], and answering SPARQL queries over OWL 2 QL ontologies [2, 11, 14, 15]. However, none of them deal with queries containing inequalities. Conversely, inequality is considered in [7,8,12,17]. As we said before, a crucial result in [12] shows that answering queries with inequalities over DL-LiteR ontologies is in general unde- cidable. In [7, 8] the authors prove that answering UCQ6= s over OWL 2 QL ontologies under the Direct Semantics Entailment Regime [9] (i.e., the regime usually adopted for SPARQL queries) can be polynomially reduced to the evaluation of a Datalog program, and therefore is in PT IME in data complexity, and in E XP T IME in combined complex- ity. As already mentioned, in [17] the author shows that the same results hold also for CQ6=,b s under the standard semantics. The paper is organized as follows. In Section 2 we provide some preliminaries on the languages considered in the paper. In Section 3 we illustrate the notion of chase that we use for DL-Lite6= R , and some related technical results. In Section 4 and Section 5 we present our results on CQ6=,b s and UCQ6=,b s, respectively. Finally, in Section 6 we conclude the paper with a discussion on future work. 2 Preliminaries In this section, we first formally define the syntax and the semantics of DL-Lite6= R , and then we present the query languages considered in this paper. Ontology language. Essentially, DL-Lite6= R extends DL-LiteR with the possibility of asserting inequalities between individuals. Formally, starting with an alphabet of indi- viduals, atomic concepts, and atomic roles, that includes the binary relation symbol 6=, a DL-Lite6= R ontology, or simply an ontology, is a pair O = hT , Ai, such that T , called TBox, and A, called ABox, are sets of axioms, that have, respectively, the following forms: T : B1 v B2 R1 v R2 (concept/role inclusion) B1 v ¬B2 R1 v ¬R2 (concept/role disjointness) A : A(a) P (a, b) (concept/role membership) a 6= b (inequality) where a, b denote individuals, A and P denote an atomic concept and an atomic role, respectively, B1 , B2 are basic concepts, i.e., expressions of the form A, ∃P , or ∃P − , and R1 and R2 are basic roles, i.e., expressions of the form P , or P − . The semantics of a DL-Lite6= R ontology O is specified through the notion of inter- pretation. An interpretation for O is a pair I = h∆I , ·I i, where the interpretation domain ∆I is a non-empty, possibly infinite set of objects, and the interpretation func- tion ·I assigns to each individual a a domain object aI ∈ ∆I , to each atomic concept A a set of domain objects AI ⊆ ∆I , to each atomic role a set of pairs of domain ob- jects P I ⊆ ∆I × ∆I , and to the special predicate “6=” the set of all pairs of distinct domain objects, i.e., 6=I = {(o1 , o2 ) | o1 , o2 ∈ ∆I ∧ o1 6= o2 }. The interpretation function extends to the other basic concepts and the other other basic roles as follows: (i) (∃P )I = {o | ∃o0 .(o, o0 ) ∈ P I }, (ii) (∃P − )I = {o | ∃o0 .(o0 , o) ∈ P I }, and (iii) (P − )I = {(o, o0 ) | (o0 , o) ∈ P I }. An interpretation I satisfies a concept inclusion B1 v B2 (respectively, role in- clusion R1 v R2 ) if B1I ⊆ B2I (respectively, R1I ⊆ R2I ), and it satisfies a concept disjointness B1 v ¬B2 (respectively, role disjointness R1 v ¬R2 ) if B1I ∩ B2I = ∅ (respectively, R1I ∩R2I = ∅). An interpretation I satisfies a DL-LiteR TBox T if it satis- fies every axiom in T . An interpretation I satisfies a DL-Lite6= R ABox A if (i) a ∈ A I I for every A(a) ∈ A, (ii) (aI , bI ) ∈ P I for every P (a, b) ∈ A, and (iii) aI 6=I bI for every a 6= b ∈ A. Finally, a DL-Lite6= R ontology O = hT , Ai is satisfiable if it has a model, where a model is an interpretation I for O that satisfies both the TBox T and the ABox A. Query language. A conjunctive query with inequalities (CQ6= ) over a DL-Lite6= R ontol- ogy O is an expression of the form q = {x | φ(x, y)}, where x and y are tuples of variables, called distinguished and existential variables of q, respectively, and φ(x, y), called the body of q, is a finite conjunction of DL-Lite6= R ABox assertions with vari- ables that can appear in predicate arguments, i.e., atoms of the form A(t1 ), P (t1 , t2 ), or t1 6= t2 , where each tj is either an individual of O, or a variable in x or y. We impose that every variable in x or y appears in some atom of φ(x, y). If x is empty, then the query is called boolean. A CQ6= q without atoms of the form x1 6= x2 in its body is called a conjunctive query (CQ). An intermediate class of queries that lies between CQs and CQ6= s is the class of conjunctive queries with bound inequalities (CQ6=,b ). Specifi- cally, a CQ6=,b q = {x | φ(x, y)} is a CQ6= whose inequalities involve only individuals or distinguished variables, i.e., for every atom z1 6= z2 appearing in φ(x, y), both z1 and z2 are not in y. An UCQ (resp., UCQ6=,b , UCQ6= ) is a union of a finite set of CQs (resp., CQ6=,b , CQ6= ) with same arity. The set of certain answers of an UCQ6= q over a DL-Lite6= R ontology O, denoted by cert(q, O), is the set of n-tuples t of individuals such that tI ∈ q I for every model I of O, where tI = htI1 , . . . , tIn i for t = ht1 , . . . , tn i, and q I denotes the evaluation of q over I seen as a relational database [1]. When q is a boolean query, we write O |= q if q I = {hi} (i.e., q is true in I, also denoted by I |= q) for every model I of O. Observe that, if O is unsatisfiable, then cert(q, O) is trivially the set of all possible n-tuples of individuals, where n is the arity of q (ex falso quodlibet). When we talk about the problem of answering a class of queries Q over a class of DL ontologies L, in fact we implicitly refer to the following decision problem (also known as the recognition problem): Given a query q in the class Q, an L-ontology O, and an n-tuple of t of individuals of O, check whether t ∈ cert(q, O). DL-LiteR . It is well-known (see e.g., [6]) that a DL-LiteR ontology O is satisfiable if and only if cert(VO , Op ) = ∅, where Op is obtained from O by removing the dis- jointness axioms, and VO is the O-violation query, i.e., the boolean UCQ obtained by including a CQ of the form {() | A1 (x) ∧ A2 (x)} (resp., {() | A1 (x) ∧ R(x, y)}, {() | R1 (x, y) ∧ R2 (x, z)}, and {() | R1 (x, y) ∧ R2 (x, y)}) for each disjointness axiom A1 v ¬A2 (resp., A1 v ¬∃R or ∃R v ¬A1 , ∃R1 v ¬∃R2 , and R1 v ¬R2 ), where an atom of the form R(x, y) stands for either P (x, y) if R denotes an atomic role P , or P (y, x) if R denotes the inverse of an atomic role, i.e., R = P − . It is also well-known that if q is an UCQ over a satisfiable DL-LiteR ontology O = hT , Ai, then PerfectRef(q, T ) (where PerfectRef is the algorithm described in [6]) computes an UCQ whose evaluation over db(A) (i.e., the ABox A seen as a relational database) returns exactly cert(q, O), that is, (PerfectRef(q, T ))db(A) = cert(q, O). Note that the algorithm PerfectRef ignores the disjointness axioms in O. 3 The chase for DL-Lite6= R The conceptual tool that we use for addressing the problem of answering UCQ6=,b s over DL-Lite6=R ontologies is a modification of the chase used for DL-LiteR [6]. Specifically, given a DL-Lite6= R ontology O = hT , Ai, we build a (possibly infinite) structure, starting from Chase 0 (O) = A, and repeatedly computing Chase j+1 (O) from Chase j (O) by applying suitable rules, where each rule can be applied only if certain conditions hold. In doing so, we make use of a new infinite alphabet V of variables for introducing fresh unknown individuals, and we follow a deterministic strategy that is fair, i.e., it is such that if at some point S a rule is applicable then it will be eventually applied. Finally, we set Chase(O) = i∈N Chase i (O). Observe that we make use of the additional binary predicate symbol ineq, which is used to record all inequalities logically implied by O. The rules we use include all the ones illustrated in [6]. For example, if A1 v ∃P ∈ T , A1 (a) is in Chase j (O), and there does not exist any b such that P (a, b) is in Chase j (O), then we set Chase j+1 (O) = Chase j (O) ∪ {P (a, s)}, where s ∈ V does not appear in Chase j (O). There are, however, crucial additions related to the ineq predicate. In what follows, when we say that B(a) is in Chase j (O), where B is a basic concept, we mean A(a) ∈ Chase j (O) if B = A, P (a, b) ∈ Chase j (O) for some b, if B = ∃P , or P (b, a) ∈ Chase j (O) for some b, if B = ∃P − . Also, when we say R(a, b) is in Chase j (O), where R is a basic role, we mean P (a, b) ∈ Chase j (O), if R = P , or P (b, a) ∈ Chase j (O), if R = P − . The additional rules are as follows: – If a 6= b is in Chase j (O), and ineq(a, b) is not in Chase j (O), then Chase j+1 (O) = Chase j (O) ∪ {ineq(a, b)}; – If ineq(a, b) is in Chase j (O), and ineq(b, a) is not in Chase j (O), then Chase j+1 (O) = Chase j (O) ∪ {ineq(b, a)}; – if B1 v ¬B2 ∈ T , B1 (a), B2 (b) are in Chase j (O), and ineq(a, b) is not in Chase j (O), then Chase j+1 (O) = Chase j (O) ∪ {ineq(a, b)}; – if R1 v ¬R2 ∈ T , R1 (c, a), R2 (c, b) are in Chase j (O), and ineq(a, b) is not in Chase j (O) then Chase j+1 (O) = Chase j (O) ∪ {ineq(a, b)}. From Chase(O) it is immediate to define an interpretation IO for O, extended in order to deal with predicate ineq, as follows: – ∆IO = VO ∪ V , where VO is the set of individuals occurring in O; – eIO = e for every individual o ∈ ∆IO ; – AIO = {e | A(e) occurs in Chase(O)} for every atomic concept A; – P IO = {(e1 , e2 ) | P (e1 , e2 ) occurs in Chase(O)} for every atomic role P ; – ineqIO = {(e1 , e2 ) | ineq(e1 , e2 ) occurs in Chase(O)}. Note that, by definition, 6=IO is the set of all pairs of distinct individuals in (VO ∪V ), i.e. 6=IO = {(e1 , e2 ) | e1 , e2 ∈ (VO ∪ V ) ∧ e1 6= e2 }. The next proposition shows that the interpretation IO plays a crucial role in DL-Lite6= R. Proposition 2. If M = h∆M , ·M i is a model of a DL-Lite6= R ontology O, then there exists a function Ψ from ∆IO = VO ∪ V to ∆M such that: 1. for every e ∈ ∆IO , if e ∈ AIO , then Ψ (e) ∈ AM ; 2. for every pair e1 , e2 ∈ ∆IO , if (e1 , e2 ) ∈ P IO , then (Ψ (e1 ), Ψ (e2 )) ∈ P M ; 3. for every pair e1 , e2 ∈ ∆IO , if (e1 , e2 ) ∈ ineqIO , then Ψ (e1 ) 6= Ψ (e2 ). Proof (Sketch). The proofs of 1. and 2. are similar to that of Lemma 28 of [6]. The proof of 3. is based on showing that the interpretation IO enjoys the following crucial property: for every pair of individuals a, b ∈ VO , (a, b) ∈ ineqIO if and only if for every model M of O, aM 6= bM . t u The above proposition shows the role of predicate ineq, and the importance of distin- guishing between 6= and ineq. Indeed, since in IO two different elements e1 , e2 satisfy e1 6= e2 , condition 3 in Proposition 2 does not hold with 6= in place of ineq. Note that if IO satisfies all the axioms of O, then it is a model of O, and therefore O is satisfiable. Otherwise, it can be seen that IO violates at least one disjointness or one inequality axiom of O. Note in particular that IO violates a disjointness axiom if and only if (VO )IO 6= ∅, where VO is the O-violation query (cf. Section 2). On the other hand, by construction, IO violates an inequality axiom if and only if there exists e in (VO ∪ V ) such that e 6= e occurs in O. In both cases, by Proposition 2, there exists no interpretation that can be a model for O, and hence O is unsatisfiable. Intuitively, this shows that similarly to the “canonical interpretation” of a DL-LiteR ontology, IO is instrumental for checking the satisfiability of a DL-Lite6= R ontology O. Also, checking the satisfiability of a DL-Lite6= R ontology O = hT , Ai can be done in AC0 in the size of A and in PT IME in the size of T , exactly lime in DL-LiteR . In what follows we implicitly assume to deal only with satisfiable DL-Lite6= R on- tologies. Also, we denote by δ(q) the query obtained by replacing each inequality atom t1 6= t2 in q with the atom ineq(t1 , t2 ). The next theorem states that IO is instrumental also for answering CQ6=,b s over DL-Lite6= R ontologies. Theorem 1. If O is a DL-Lite6= R ontology, and q is a CQ 6=,b over O, then cert(q, O) = IO δ(q) . Proof (Sketch). If t ∈ δ(q)IO , then, based on Proposition 2, we can show that t ∈ q M , for every model M of O. If t 6∈ δ(q)IO , and t does not satisfy in IO all atoms of δ(q) different from ineq atoms, then IO is itself a model of O showing that t 6∈ cert(q, O). On the other hand, if t satisfies in IO all atoms of δ(q) different from ineq atoms, then there is at least one atom of the form ineq(a, b) in δ(q) that is false in IO . What we do in this case is to compute an interpretation J from IO , where aJ and bJ coincide, and then we show that J is a model M of O such that t 6∈ q M , thus showing that t 6∈ cert(q, O). t u 4 Answering CQ6=,b s over DL-Lite6= R ontologies In this section, we study the problem of answering CQ6=,b s over DL-Lite6= R ontologies. To this aim, we start by introducing some preliminary notation. Given an inequality atom x1 6= x2 and a disjointness axiom γ, ρ(x1 6= x2 , γ), denotes the formula defined as follows: – ρ(x1 6= x2 , A1 v ¬A2 ) = A1 (x1 ) ∧ A2 (x2 ), – ρ(x1 6= x2 , A v ¬∃R) = ρ(x1 6= x2 , ∃R v ¬A) = A(x1 ) ∧ R(x2 , z), where z is a fresh variable, – ρ(x1 6= x2 , ∃R1 v ¬∃R2 ) = R1 (x1 , z) ∧ R2 (x2 , w), where z and w are fresh variables, and – ρ(x1 6= x2 , R1 v ¬R2 ) = R1 (x1 , z) ∧ R2 (x2 , z) ∨ R1 (z, x1 ) ∧ R2 (z, x2 ). where an atom of the form R(x, y) stands for either P (x, y) if R denotes an atomic role P , or P (y, x) if R denotes the inverse of an atomic role, i.e., R = P − . Given an inequality atom x1 6= x2 and a TBox T with disjointness axioms γ1 , . . . , γm , we denote by σ(x1 6= x2 , T ) the disjunction _ ineq(x1 , x2 ) ∨ ineq(x2 , x1 ) ∨ (ρ(x1 6= x2 , γi ) ∨ ρ(x2 6= x1 , γi )) γi ∈T Finally, we denote by τ (q, T ) the query obtained from q by substituting every in- equality x1 6= x2 by σ(x1 6= x2 , T ), and then turning the resulting query into an equivalent union of CQs. In Fig. 1, we present the algorithm AnsCQ6=,b (q, O) for computing the certain an- swers to a CQ6=,b q over a DL-Lite6=R ontology O = hT , Ai. Informally, the algorithm rewrites q into the UCQ τ (q, T ), applies the algorithm PerfectRef described in [6] to τ (q, T ), and then evaluates the resulting UCQ over the database db ineq (A). Such database stores the object c (resp. the tuple c1 , c2 ) in the table A (resp. R), for each assertion A(c) (resp. R(c1 , c2 )) in A, and stores the pair (c1 , c2 ) in the table ineq for each assertion c1 6= c2 in A. Algorithm AnsCQ6=,b (q, O) Input: n-ary CQ6=,b q, DL-Lite6=R ontology O = hT , Ai Output: a set of n-tuples of individuals of O begin P R := τ (q, T ) P R := PerfectRef(P R, T ) ineq return P Rdb (A) end Fig. 1: The algorithm AnsCQ6=,b (q, O) Example 2. Consider the DL-Lite6= R ontology O = hT , Ai with T = {P1 v P2 , A1 v ¬A2 }, and the CQ6=,b q = {(x1 , x2 ) | P2 (x1 , x2 ) ∧ x1 6= c} over O. It is easy to see that σ(x1 6= c, T ) is the formula ineq(x1 , c) ∨ ineq(c, x1 ) ∨ A1 (x1 ) ∧ A2 (c) ∨ A2 (x1 ) ∧ A1 (c) and τ (q, T ) = {(x1 , x2 ) | P2 (x1 , x2 ) ∧ ineq(x, c) ∨ P2 (x1 , x2 ) ∧ ineq(c, x1 ) ∨ P2 (x1 , x2 ) ∧ A1 (x1 ) ∧ A2 (c) ∨ P2 (x1 , x2 ) ∧ A1 (c) ∧ A2 (x)}. Finally, PerfectRef(τ (q, T ), T ) is {(x1 , x2 ) | P2 (x1 , x2 ) ∧ ineq(x, c) ∨ P2 (x1 , x2 ) ∧ ineq(c, x1 ) ∨ P2 (x1 , x2 ) ∧ A1 (x1 ) ∧ A2 (c) ∨ P2 (x1 , x2 ) ∧ A1 (c) ∧ A2 (x) ∨ P1 (x1 , x2 ) ∧ ineq(x, c) ∨ P1 (x1 , x2 ) ∧ ineq(c, x1 ) ∨ P1 (x1 , x2 ) ∧ A1 (x1 ) ∧ A2 (c) ∨ P1 (x1 , x2 ) ∧ A1 (c) ∧ A2 (x). t u Proposition 3. If O = hT , Ai is a DL-Lite6= R ontology, and q is a CQ 6=,b over O, then 6=,b AnsCQ (q, O) terminates and computes exactly cert(q, O). Taking into account the computational complexity of algorithm AnsCQ6=,b , the above proposition implies that answering CQ6=,b s over DL-Lite6= R ontologies has the same data and combined complexity as answering UCQs over DL-LiteR ontologies. Theorem 2. Answering CQ6= s over DL-Lite6= 0 R is in AC in data complexity, in PT IME in TBox complexity, and NP-complete in combined complexity. 5 Answering UCQ6=,b s over DL-Lite6= R ontologies In this section, we study the problem of answering UCQ6=,b s over DL-Lite6= R ontologies. Observe that, differently from the UCQ case where for any UCQ Q = q1 ∪ . . . ∪ qn and any DL-LiteR ontology O we have that cert(Q, O) = cert(q1 , O)∪. . .∪cert(qn , O) [6], the next example shows that this is not the case if we consider UCQ6=,b s. Example 3. Consider the DL-LiteR ontology O = hT , Ai, where T = ∅ and A = {P (a, b)}. For the boolean UCQ6=,b Q = q1 ∪ q2 , where q1 = {() | P (a, a)} and q2 = {() | a 6= b}, it is easy to see that O |= Q. Indeed, for any model M of O, if aM = bM , then M |= q1 , otherwise aM 6= bM , then M |= q2 . Notice, however, that both O 6|= q1 and O 6|= q2 hold. For the former, it is sufficient to simply consider a model M1 of O in which aM1 6= bM1 . For the latter, it is sufficient to consider a model M2 of O in which aM2 = bM2 = e and P M2 = {(e, e)}. t u The next theorem implies that, unless the polynomial hierarchy collapses to the first level, answering UCQ6=,b s over DL-LiteR ontologies does not have the same combined complexity of the UCQ and CQ6=,b cases. Theorem 3. Answering UCQ6=,b s over DL-LiteR ontologies is Π2p -hard in combined complexity. Proof (Sketch). The proof of Π2p -hardness is by a L OG S PACE reduction from the ∀∃- CNF problem, which is Π2p -complete [20]. t u In order to present our positive results for the UCQ6=,b case, next we introduce the notion of e-satisfiability for an equivalence relation e. An equivalence relation e on a set of individuals C is a binary relation over C that is reflexive, symmetric, and transitive. In what follows, we write c1 ∼e c2 to denote (c1 , c2 ) ∈ e. Moreover, we denote by Oe = hT , Ae i the DL-Lite6= R ontology obtained from O by adding e to the signature of O as a new atomic role, and with Ae being the ABox obtained from A by adding the extension of the relation e, i.e., Ae = A ∪ e. Definition 1. Let O = hT , Ai be a DL-Lite6= R ontology, e be an equivalence relation on a set C of individuals of O, and I be a model of O. Then, we say that I is an e-model of O if, for any pair of constants c1 , c2 ∈ C, we have that cI1 = cI2 if and only if c1 ∼e c2 . Also, we say that O is e-satisfiable if it has an e-model. The next proposition states that checking for the e-satisfiability has the same com- putational complexity of checking the satisfiability. Proposition 4. Let O = hT , Ai be a DL-Lite6= R ontology, and let e be an equivalence relation on a set of constants C of O. Checking whether O is e-satisfiable can be done in AC0 in the size of A and in PT IME in the size of T . 6=,e Proof (Sketch). Let VO be the Oe -violation query obtained by extending the boolean UCQ VO with the following CQs over the signature of Oe : – {() | A1 (x1 ) ∧ A2 (x2 ) ∧ e(x1 , x2 )} for each axiom of the form A1 v ¬A2 , – {() | A(x1 ) ∧ R(x2 , y) ∧ e(x1 , x2 )} for each axiom of the form A v ¬∃R or of the form ∃R v ¬A, – {() | R1 (x1 , y) ∧ R2 (x2 , z) ∧ e(x1 , x2 )} for each axiom of the form ∃R1 v ¬∃R2 , – {() | R1 (x1 , y1 ) ∧ R2 (x2 , y2 ) ∧ e(x1 , x2 ) ∧ e(y1 , y2 )} for each axiom of the form R1 v ¬R2 , where an atom of the form R(x, y) stands for either P (x, y) if R denotes an atomic role P , or P (y, x) if R denotes the inverse of an atomic role, i.e., R = P − . It can be readily seen that a DL-Lite6= R ontology O is e-satisfiable if and only if 6=,e cert(VO , Oep ) = ∅ and there exists no a 6= b occurring in A such that a ∼e b. Intuitively, for checking e-satisfiability we check whether the equivalence relation e contradicts a disjointness, or an inequality axiom. This also directly implies that check- ing whether O is e-satisfiable can be done by evaluating a suitable query over db ineq (A), and therefore the problem is in AC0 in the size of the ABox A and in PT IME in the size of the TBox T , as required. t u Based on the above result, in Fig. 2 we provide the algorithm AnsUCQ6=,b (Q, O) for the problem of answering UCQ6=,b s over DL-LiteR ontologies. Observe that it is enough to consider only boolean UCQ6=,b s. Indeed, given a UCQ6=,b Q, a DL-Lite6= R ontology O = hT , Ai, and an n-tuple t of individuals of O of the same arity of Q, checking whether t ∈ cert(Q, O) is equivalent to checking whether O |= Q(t), where Q(t) de- notes the boolean UCQ6=,b obtained by replacing appropriately the distinguished vari- ables of each CQ q in Q with the individuals of t. Moreover, note that every boolean UCQ6=,b Q is such that every inequality appear- ing in its body is of the form a 6= b, where both a and b are individuals of O. In the algorithm, we denote by ej(q) the function that, given a CQ q, returns the set of existen- tial variables that appears more than two times in the body of q, i.e., the set of existential variables that are in join. Intuitively, to say that O 6|= Q, the algorithm seeks for a relation ψ between the individuals appearing in Q for which (i) the ontology O is e-satisfiable, where e is the equivalence relation induced by ψ, and (ii) the reformulated UCQ Q is not entailed by Oe . In particular, Q is first reformulated by evaluating every inequality based on the Algorithm AnsUCQ6=,b (Q, O) Input: a boolean UCQ6=,b Q, and a DL-Lite6= R ontology O = hT , Ai Output: true or false begin let CQ be the set of all individuals appearing in Q for each ψ ⊆ (CQ × CQ ): let e be the reflexive, symmetric, and transitive closure of ψ if O is e-satisfiable then for each q ∈ Q and inequality atom c1 6= c2 ∈ q: if c1 ∼e c2 then q = q \ {c1 6= c2 } else Q = Q \ {q} Q0 = Q for each q in Q0 , Y ⊆ ej(q), and y ∈ Y: let y 1 , . . . , y my denote the different occurrences of y in q replace each occurrence y j of the variable y with a fresh existential variable z j for each pair of newly introduced variables z k , z l with k 6= l: q = q ∪ {e(zik , zil )} Q=Q∪q for each q in Q and individual c in q: replace all the occurrences of c with a fresh existential variable yc q = q ∪ {e(yc , c)} if Oe 6|= Q then return false return true end Fig. 2: The algorithm AnsUCQ6=,b (Q, O) equivalence relation e. Then, Q is further reformulated by allowing that in each CQ q of Q, and for some of the existential variables y1 , . . . , yn appearing in q, different occurrences of each yi may be mapped to distinct individuals of the set CQ , provided that these distinct individuals are in the same equivalence class of e. An analogous consideration is for the individuals appearing in the query, where the last step of the reformulation of Q allows that an existential variable yc may match an individual c0 that is not necessarily the individual c, but it is such that c0 ∼e c, i.e., it is in the same equivalence class of c. Proposition 5. If O = hT , Ai is a DL-Lite6= R ontology, and Q is a boolean UCQ 6=,b 6=,b over O, then AnsUCQ (q, O) terminates and returns true if and only if O |= Q. With regard to the cost of the algorithm AnsUCQ6=,b (Q, O), observe that all the for-loops of the algorithm depend only on Q, and can be done in E XP T IME in its size. As for the e-satisfiability check, from Proposition 4, it can be done in AC0 in the size of A, and in PT IME in the size of T . Also, since Q0e is an UCQ, checking whether Oe 6|= Q0e can be obviously done in AC0 in the size of A, in PT IME in the size of T , and in E XP T IME in the size of Q. From Proposition 5 and the above considerations, we easily get the following result. Theorem 4. Answering UCQ6=,b s over DL-Lite6= 0 R ontologies is in AC in data complex- ity, in PT IME in TBox complexity, and in E XP T IME in combined complexity. 6 Conclusion In this paper we have singled out a specific class of queries, namely UCQ6=,b s, for which query answering over DL-Lite6= 0 R ontologies is still in AC in data complexity and in PT IME in TBox complexity. The algorithm is E XP T IME in combined complexity, and we have shown that the problem is Π2p -hard. There are several problems to consider for continuing the work presented here, the most obvious being trying to derive a matching Π2p upper bound in combined complex- ity of the above problem. Another interesting topic is to look for more subclasses of queries, or even more ontology languages for which answering queries with inequali- ties is decidable/tractable. Acknowlegments Work supported by MIUR under the SIR project “MODEUS” – grant n. RBSI14TQHQ, and by Sapienza under the research project “PRE-O-PRE”. References 1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley Publ. Co., 1995. 2. M. Arenas, G. Gottlob, and A. Pieris. Expressive languages for querying the semantic web. ACM Trans. on Database Systems, 43(3):13:1–13:45, 2018. 3. A. Artale, D. Calvanese, R. Kontchakov, and M. Zakharyaschev. The DL-Lite family and relations. J. of Artificial Intelligence Research, 36:1–69, 2009. 4. D. Calvanese, B. Cogrel, S. Komla-Ebri, R. Kontchakov, D. Lanti, M. Rezk, M. Rodriguez- Muro, and G. Xiao. Ontop: Answering SPARQL queries over relational databases. Semantic Web J., 8(3):471–487, 2017. 5. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, M. Rodriguez-Muro, R. Rosati, M. Ruzzi, and D. F. Savo. The Mastro system for ontology-based data access. Semantic Web J., 2(1):43–53, 2011. 6. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning, 39(3):385–429, 2007. 7. G. Cima, G. De Giacomo, M. Lenzerini, and A. Poggi. On the SPARQL metamodeling semantics entailment regime for OWL 2 QL ontologies. In Proc. of the 7th Int. Conf. on Web Intelligence, Mining and Semantics (WIMS), pages 10:1–10:6, 2017. 8. G. Cima, G. De Giacomo, M. Lenzerini, and A. Poggi. Querying OWL 2 QL under the SPARQL metamodeling semantics entailment regime. In Proc. of the 25th Ital. Symp. on Advanced Database Systems (SEBD), volume 2037, page 165, 2017. 9. B. Glimm. Using SPARQL with RDFS and OWL entailment. In Reasoning Web. Semantic Technologies for the Web of Data – 7th Int. Summer School Tutorial Lectures (RW), pages 137–201. 2011. 10. G. Gottlob, S. Kikot, R. Kontchakov, V. V. Podolskii, T. Schwentick, and M. Zakharyaschev. The price of query rewriting in ontology-based data access. Artificial Intelligence, 213:42– 59, 2014. 11. G. Gottlob and A. Pieris. Beyond SPARQL under OWL 2 QL entailment regime: Rules to the rescue. In Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 2999–3007, 2015. 12. V. Gutiérrez-Basulto, Y. A. Ibáñez-Garcı́a, R. Kontchakov, and E. V. Kostylev. Queries with negation and inequalities over lightweight ontologies. J. of Web Semantics, 35:184–202, 2015. 13. S. Kikot, R. Kontchakov, and M. Zakharyaschev. Conjunctive query answering with OWL 2 QL. In Proc. of the 13th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR), 2012. 14. R. Kontchakov, M. Rezk, M. Rodriguez-Muro, G. Xiao, and M. Zakharyaschev. Answering SPARQL queries over databases under OWL 2 QL entailment regime. In Proc. of the 13th Int. Semantic Web Conf. (ISWC), pages 552–567, 2014. 15. M. Lenzerini, L. Lepore, and A. Poggi. A higher-order semantics for metaquerying in OWL 2 QL. In Proc. of the 15th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR), pages 577–580, 2016. 16. B. Motik, B. Cuenca Grau, I. Horrocks, Z. Wu, A. Fokoue, and C. Lutz. OWL 2 Web Ontology Language profiles (second edition). W3C Recommendation, World Wide Web Consortium, Dec. 2012. Available at http://www.w3.org/TR/owl2-profiles/. 17. A. Poggi. On the SPARQL direct semantics entailment regime for OWL 2 QL. In Proc. of the 29th Int. Workshop on Description Logic (DL), 2016. 18. A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati. Linking data to ontologies. J. on Data Semantics, X:133–173, 2008. 19. R. Rosati and A. Almatelli. Improving query answering over DL-Lite ontologies. In Proc. of the 12th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR), pages 290–300, 2010. 20. L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1–22, 1976. 21. M. Y. Vardi. The complexity of relational query languages. In Proc. of the 14th ACM SIGACT Symp. on Theory of Computing (STOC), pages 137–146, 1982. 22. G. Xiao, D. Calvanese, R. Kontchakov, D. Lembo, A. Poggi, R. Rosati, and M. Za- kharyaschev. Ontology-based data access: A survey. In Proc. of the 27th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 5511–5519, 2018.