On queries with inequalities in DL-Lite6= R

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=;bs, where inequalities involve only distinguished variables or individuals. In particular, we tackle the problem of answering CQ6=;bs and unions thereof (UCQ6=;bs) over DL-Lite6= ontologies, where R DL-Lite6= corresponds to DL-LiteR without the Unique Name Assumption, and R with the possibility of asserting inequalities between individuals, as in OWL 2 QL. As a first contribution, we show that answering CQ6=;bs over DL-Lite6= ontologies R has the same computational complexity as the UCQ case over DL-LiteR, i.e., it is in AC0 in data complexity, in PTIME in TBox complexity, and NP-complete in combined complexity. We then deal with the UCQ6=;b case, and prove that answering UCQ6=;bs over DL-Lite6= ontologies is still in AC0 in data complexity and in PTIME in TBox complexiRty, but is 2p-hard in combined complexity.

-

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 optimisation 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: – For subclasses of CQ6=s and UCQ6=s, named local CQ6=s and local UCQ6=s, respectively, query answering over DL-LiteR ontologies is decidable, but with a high CONEXPTIME upper bound in data complexity. Furthermore, it is provably intractable (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 inequalities involve only individuals or distinguished variables, query answering over DL-LiteR ontologies is in PTIME in data complexity and in EXPTIME in combined complexity [ 17 ].

Observe that all the above results hold regardless of whether the Unique Name Assumption (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=;bs and unions thereof (UCQ6=;bs) 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=;bs, as shown in following example. Example 1. Consider the DL-LiteR ontology O = hT ; Ai, where T = ; and A = fP (a; b)g. For the CQ6=;b q = f(x; y) j P (x; y) ^ x 6= yg, 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 = f(e; e)g, that does not respect the UNA, we have that qM = ;. tu

Notice, however, that answering UCQ6=;bs over DL-LiteR ontologies under the UNA is a straightforward generalisation of the UCQ case.

Proposition 1. Answering UCQ6=;bs over DL-LiteR ontologies under the UNA is in AC0 in data complexity, in PTIME 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= , which extends DL-LiteR with R the possibility of asserting inequalities between individuals, as in OWL 2 QL, and we present the following results: – Answering CQ6=;bs over DL-Lite6= ontologies has the same computational complexity of the UCQ case, i.e., it isRin AC0 in data complexity, in PTIME in TBox complexity, and NP-complete in combined complexity (cf. Theorem 2). – iAtyns(wcfe.rTinhgeoUreCmQ6=3);.bs over DL-Lite6=R ontologies is 2p-hard in combined complex– Answering UCQ6=;bs over DL-Lite6= ontologies is in AC0 in data complexity, in

R PTIME in TBox complexity, and in EXPTIME in combined complexity (cf. Theorem 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 undecidable. 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 PTIME in data complexity, and in EXPTIME in combined complexity. As already mentioned, in [ 17 ] the author shows that the same results hold also for CQ6=;bs 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= , and some related technical results. In Section 4 and Section 5

R we present our results on CQ6=;bs and UCQ6=;bs, 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= , and R 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 individuals, atomic concepts, and atomic roles, that includes the binary relation symbol 6=, a DL-Lite6= ontology, or simply an ontology, is a pair O = hT ; Ai, such that T , called TBox, andRA, called ABox, are sets of axioms, that have, respectively, the following forms:

T : B1 v B2

B1 v :B2 A : A(a)

R1 v R2 R1 v :R2 P (a; b) a 6= b (concept/role inclusion) (concept/role disjointness) (concept/role membership) (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, 9P , or 9P , and R1 and R2 are basic roles, i.e., expressions of the form P , or P .

The semantics of a DL-Lite6= ontology O is specified through the notion of interpretation. An interpretation forRO 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 function I assigns to each individual a a domain object aI 2 I , to each atomic concept A a set of domain objects AI I , to each atomic role a set of pairs of domain objects P I I I , and to the special predicate “6=” the set of all pairs of distinct domain objects, i.e., 6=I = f(o1; o2) j o1; o2 2 I ^ o1 6= o2g. The interpretation function extends to the other basic concepts and the other other basic roles as follows: (i) (9P )I = fo j 9o0:(o; o0) 2 P I g, (ii) (9P )I = fo j 9o0:(o0; o) 2 P I g, and (iii) (P )I = f(o; o0) j (o0; o) 2 P I g.

An interpretation I satisfies a concept inclusion B1 v B2 (respectively, role inclusion 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 satisfies every axiom in T . An interpretation I satisfies a DL-Lite6= ABox A if (i) aI 2 AI R for every A(a) 2 A, (ii) (aI ; bI ) 2 P I for every P (a; b) 2 A, and (iii) aI 6=I bI for every a 6= b 2 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= ontolR ogy O is an expression of the form q = fx j (x; y)g, 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= ABox assertions with variR 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). Specifically, a CQ6=;b q = fx j (x; y)g 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= ontology O, denoted by R cert (q; O), is the set of n-tuples t of individuals such that tI 2 qI for every model I of O, where tI = ht1I ; : : : ; tIni for t = ht1; : : : ; tni, and qI denotes the evaluation of q over I seen as a relational database [ 1 ]. When q is a boolean query, we write O j= q if qI = fhig (i.e., q is true in I, also denoted by I j= 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 2 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 disjointness axioms, and VO is the O-violation query, i.e., the boolean UCQ obtained by including a CQ of the form f() j A1(x) ^ A2(x)g (resp., f() j A1(x) ^ R(x; y)g, f() j R1(x; y) ^ R2(x; z)g, and f() j R1(x; y) ^ R2(x; y)g) for each disjointness axiom A1 v :A2 (resp., A1 v :9R or 9R v :A1, 9R1 v :9R2, 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.

The chase for DL-Lite6=

R The conceptual tool that we use for addressing the problem of answering UCQ6=;bs over DL-Lite6= ontologies is a modification of the chase used for DL-LiteR [ 6 ]. Specifically,

R given a DL-Lite6= ontology O = hT ; Ai, we build a (possibly infinite) structure, starting

R from Chase0(O) = A, and repeatedly computing Chasej+1(O) from Chasej (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 a rule is applicable then it will be eventually applied. Finally, we set Chase(O) = Si2N Chasei(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 9P 2 T , A1(a) is in Chasej (O), and there does not exist any b such that P (a; b) is in Chasej (O), then we set Chasej+1(O) = Chasej (O) [ fP (a; s)g, where s 2 V does not appear in Chasej (O). There are, however, crucial additions related to the ineq predicate. In what follows, when we say that B(a) is in Chasej (O), where B is a basic concept, we mean A(a) 2 Chasej (O) if B = A, P (a; b) 2 Chasej (O) for some b, if B = 9P , or P (b; a) 2 Chasej (O) for some b, if B = 9P . Also, when we say R(a; b) is in Chasej (O), where R is a basic role, we mean P (a; b) 2 Chasej (O), if R = P , or P (b; a) 2 Chasej (O), if R = P . The additional rules are as follows: – If a 6= b is in Chasej (O), and ineq(a; b) is not in Chasej (O), then

Chasej+1(O) = Chasej (O) [ fineq(a; b)g; – ICfhinaesqe(ja+;1b()Ois) i=n CChhaasseejj((OO)),[anfdinienqe(qb(;ba;a)g);is not in Chasej (O), then – if B1 v :B2 2 T , B1(a); B2(b) are in Chasej (O), and ineq(a; b) is not in

Chasej (O), then Chasej+1(O) = Chasej (O) [ fineq(a; b)g; – if R1 v :R2 2 T , R1(c; a); R2(c; b) are in Chasej (O), and ineq(a; b) is not in Chasej (O) then Chasej+1(O) = Chasej (O) [ fineq(a; b)g.

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 2 IO ; – AIO = fe j A(e) occurs in Chase(O)g for every atomic concept A; – P IO = f(e1; e2) j P (e1; e2) occurs in Chase(O)g for every atomic role P ; – ineqIO = f(e1; e2) j ineq(e1; e2) occurs in Chase(O)g.

Note that, by definition, 6=IO is the set of all pairs of distinct individuals in (VO [V ), i.e. 6=IO = f(e1; e2) j e1; e2 2 (VO [ V ) ^ e1 6= e2g.

The next proposition shows that the interpretation IO plays a crucial role in DL-Lite6= . R Proposition 2. If M = h exists a function from

M; Mi is a model of a DL-Lite6= ontology O, then there

IO = VO [ V to M such that: R

1. for every e 2

IO , if e 2 AIO , then (e) 2 AM;

2. for every pair e1; e2 2

3. for every pair e1; e2 2 IO , if (e1; e2) 2 P IO , then ( (e1); (e2)) 2 P M; IO , if (e1; e2) 2 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 2 VO, (a; b) 2 ineqIO if and only if for every model M of O, aM 6= bM. tu

The above proposition shows the role of predicate ineq, and the importance of distinguishing 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= ontology O. Also, checking R the satisfiability of a DL-Lite6= ontology O = hT ; Ai can be done in AC0 in the size of

R A and in PTIME in the size of T , exactly lime in DL-LiteR.

In what follows we implicitly assume to deal only with satisfiable DL-Lite6= onR 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=;bs over DL-Lite6= ontologies.

R Theorem 1. If O is a DL-Lite6= ontology, and q is a CQ6=;b over O, then cert(q; O) =

R (q)IO .

Proof (Sketch). If t 2 (q)IO , then, based on Proposition 2, we can show that t 2 qM, for every model M of O.

If t 62 (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 62 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 62 qM, thus showing that t 62 cert(q; O). tu 4

Answering CQ6=;bs over DL-Lite6= ontologies

R In this section, we study the problem of answering CQ6=;bs over DL-Lite6= ontologies. R 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 :9R) = (x1 6= x2; 9R v :A) = A(x1) ^ R(x2; z), where z is a fresh variable, – (x1 6= x2; 9R1 v :9R2) = 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)) i2T

Finally, we denote by (q; T ) the query obtained from q by substituting every inequality 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 answers to a CQ6=;b q over a DL-Lite6= ontology O = hT ; Ai.

R

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 dbineq(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= ontology O = hT ; Ai

R Output: a set of n-tuples of individuals of O begin

P R := (q; T ) P R := PerfectRef(P R; T ) return P Rdbineq(A) end

Fig. 1: The algorithm AnsCQ6=;b(q; O) Example 2. Consider the DL-Lite6= ontology O = hT ; Ai with T = fP1 v P2; A1 v

R :A2g, and the CQ6=;b

q = f(x1; x2) j P2(x1; x2) ^ x1 6= cg 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 ) = f(x1; x2) j 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)g. Finally, PerfectRef( (q; T ); T ) is f(x1; x2) j 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). tu Proposition 3. If O = hT ; Ai is a DL-Lite6= ontology, and q is a CQ6=;b over O, then R AnsCQ6=;b(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=;bs over DL-Lite6= ontologies has the same data R and combined complexity as answering UCQs over DL-LiteR ontologies. Theorem 2. Answering CQ6=s over DL-Lite6= is in AC0 in data complexity, in PTIME R in TBox complexity, and NP-complete in combined complexity. 5

Answering UCQ6=;bs over DL-Lite6= ontologies

R In this section, we study the problem of answering UCQ6=;bs over DL-Lite6= ontologies. R

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=;bs. Example 3. Consider the DL-LiteR ontology O = hT ; Ai, where T = ; and A = fP (a; b)g. For the boolean UCQ6=;b Q = q1 [ q2, where q1 = f() j P (a; a)g and q2 = f() j a 6= bg, it is easy to see that O j= Q. Indeed, for any model M of O, if aM = bM, then M j= q1, otherwise aM 6= bM, then M j= q2. Notice, however, that both O 6j= q1 and O 6j= 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 = f(e; e)g. tu

The next theorem implies that, unless the polynomial hierarchy collapses to the first level, answering UCQ6=;bs over DL-LiteR ontologies does not have the same combined complexity of the UCQ and CQ6=;b cases.

Theorem 3. Answering UCQ6=;bs over DL-LiteR ontologies is complexity. 2p-hard in combined Proof (Sketch). The proof of 2p-hardness is by a LOGSPACE reduction from the 89CNF problem, which is 2p-complete [ 20 ]. tu

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) 2 e. Moreover, we denote by Oe = hT ; Aei the DL-Lite6= ontology obtained from O by adding e to the signature of

R 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= ontology, e be an equivalence relation on

R 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 2 C, we have that c1I = c2I 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 computational complexity of checking the satisfiability.

Proposition 4. Let O = hT ; Ai be a DL-Lite6= ontology, and let e be an equivalence R 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 PTIME in the size of T .

Proof (Sketch). Let VO6=;e be the Oe-violation query obtained by extending the boolean UCQ VO with the following CQs over the signature of Oe: – f() j A1(x1) ^ A2(x2) ^ e(x1; x2)g for each axiom of the form A1 v :A2, – f() j A(x1) ^ R(x2; y) ^ e(x1; x2)g for each axiom of the form A v :9R or of the form 9R v :A, – f() j R1(x1; y) ^ R2(x2; z) ^ e(x1; x2)g for each axiom of the form 9R1 v :9R2, – f() j R1(x1; y1) ^ R2(x2; y2) ^ e(x1; x2) ^ e(y1; y2)g 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= ontology O is e-satisfiable if and only if

R cert (VO6=;e; 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 checking whether O is e-satisfiable can be done by evaluating a suitable query over dbineq(A), and therefore the problem is in AC0 in the size of the ABox A and in PTIME in the size of the TBox T , as required. tu

Based on the above result, in Fig. 2 we provide the algorithm AnsUCQ6=;b(Q; O) for the problem of answering UCQ6=;bs over DL-LiteR ontologies. Observe that it is enough to consider only boolean UCQ6=;bs. Indeed, given a UCQ6=;b Q, a DL-Lite6= ontology R O = hT ; Ai, and an n-tuple t of individuals of O of the same arity of Q, checking whether t 2 cert (Q; O) is equivalent to checking whether O j= Q(t), where Q(t) denotes the boolean UCQ6=;b obtained by replacing appropriately the distinguished variables of each CQ q in Q with the individuals of t.

Moreover, note that every boolean UCQ6=;b Q is such that every inequality appearing 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 existential 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 6j= 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= ontology O = hT ; Ai

R 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 2 Q and inequality atom c1 6= c2 2 q: if c1 e c2 then

q = q n fc1 6= c2g else

Q = Q n fqg Q0 = Q for each q in Q0, Y ej(q), and y 2 Y: let y1; : : : ; ymy denote the different occurrences of y in q replace each occurrence yj of the variable y with a fresh existential variable zj for each pair of newly introduced variables zk; zl with k 6= l: q = q [ fe(zik; zi)g

l

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 [ fe(yc; c)g if Oe 6j= 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 UCQ6=;b over O, then AnsUCQ6=;b(q; O) terminates and returns true if and only if O j= 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 EXPTIME 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 PTIME in the size of T . Also, since Q0e is an UCQ, checking whether Oe 6j= Q0e can be obviously done in AC0 in the size of A, in PTIME in the size of T , and in EXPTIME in the size of Q. From Proposition 5 and the above considerations, we easily get the following result.

Theorem 4. Answering UCQ6=;bs over DL-Lite6= ontologies is in AC0 in data complexR ity, in PTIME in TBox complexity, and in EXPTIME in combined complexity. 6

Conclusion

In this paper we have singled out a specific class of queries, namely UCQ6=;bs, for which query answering over DL-Lite6= ontologies is still in AC0 in data complexity and

R in PTIME in TBox complexity. The algorithm is EXPTIME 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 complexity 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 inequalities is decidable/tractable.

Acknowlegments References

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. RodriguezMuro, 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. Gutie´rrez- Basulto , Y. A. Iba ´n˜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. Zakharyaschev . Ontology-based data access: A survey . In Proc. of the 27th Int. Joint Conf. on Artificial Intelligence (IJCAI) , pages 5511 - 5519 , 2018 .