Inconsistency-Tolerant First-Order Rewritability of DL-Lite with Identification and Denial Assertions Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo Dipartimento di Ingegneria Informatica, Automatica e Gestionale Antonio Ruberti Sapienza Università di Roma lembo,lenzerini,rosati,ruzzi,savo@dis.uniroma1.it Abstract. This paper is motivated by two requirements arising in practical ap- plications of ontology-based data access (OBDA): the need of inconsistency- tolerant semantics, which allow for dealing with classically inconsistent speci- fications; and the need of expressing assertions which go beyond the expressive abilities of traditional Description Logics, namely identification and denial asser- tions. We consider an extension of DL-Lite (the most used DL in OBDA) which allows for the presence of both the aforementioned kinds of assertions in the TBox. We adopt an inconsistency-tolerant semantics for such a DL, specifically the so-called Intersection ABox Repair (IAR) semantics, and we study query answering in this setting. Our main contribution is a query rewriting technique which is able to take into account both identification and denial assertions. By virtue of this technique, we prove that conjunctive query answering under such semantics is first-order rewritable in the considered extension of DL-Lite. 1 Introduction Ontology-based data access (OBDA) is a computing paradigm which considers the problem of accessing data stored in autonomous databases through the use of an on- tology, which provides a conceptual and shared representation of the domain of inter- est [10]. The main components of an OBDA system are the ontology, the set of data sources to be accessed, and the mapping, which specifies the relationship between the ontology and the data sources. The reasoning service of main interest is query answer- ing, which amounts to process a query expressed in terms of the ontology alphabet, and to compute its answer on the basis of the knowledge specified by the ontology, the map- ping, and the data stored at the sources. Various languages for specifying the ontology in this context have been recently proposed [3,2,7], which are designed in order to allow for tractable query answering w.r.t. the size of the data (data complexity). Among these, the members of the DL-Lite family of light-weight Description Logics (DLs) present the distinguishing feature of first-order rewritable query answering for unions of con- junctive queries (UCQs), which means that such a reasoning service can be reduced to the evaluation of a first-order query (directly translatable into SQL) over a database. This turns out to be a crucial aspect in OBDA, where data are in general not moved from the sources, and are usually managed by a Relational Database Management System. In the last years we have experimented (see, e.g., [11]) that two important require- ments arise in OBDA applications: (i) the need of declarative mechanisms for dealing with data that are inconsistent with respect to the intensional knowledge specified by the ontology, and (ii) the need of expressing assertions which go beyond the expressive abilities of traditional DLs, namely identification assertions and denial assertions. Solu- tions aiming at fulfilling these two requirements should of course still guarantee enough efficiency. Ideally, they should allow for inconsistency-tolerant first-order rewritable query answering of UCQs. Devising one such solution is the goal of the present paper. Motivated by the first mentioned requirement, we have recently proposed various inconsistency-tolerant semantics [8], inspired by the studies on inconsistency handling in belief revision [6] and by the work on consistent query answering in databases [5]. Later works [9,1] have then shown that answering UCQs under the so-called Inter- section ABox Repair (IAR) semantics is first-order rewritable for ontologies specified in DL-LiteA , a member of the DL-Lite family [9]. In the present paper we extend the above result, and show that first-order rewritability of conjunctive query answering still holds if we enrich DL-LiteA with identification and denial assertions. Identification assertions (IdAs) are mechanisms for specifying a set of properties that can be used to identify instances of concepts. IdAs we study here have been origi- nally presented in [4]. Such assertions allow for sophisticated forms of object identifica- tion, which may include paths realized through the chaining of roles, their inverses, and attributes. Roughly speaking, when we say that instances of a concept C are identified by a path π, we impose that no two instances of C with overlapping sets of π-fillers ex- ist, i.e., in every interpretation I, no two instances o and o0 of C exist with a non-empty intersection of the set of objects reachable by o and by o0 in I. This naturally extends to IdAs involving more than one path. Identification assertions are very useful in prac- tice and are essential to represent n-relations and attributes of roles through reification. Indeed, reification is the only way to model n-relations and role attributes in ontology languages, such as OWL, which do not natively allow for such constructs. Denial Assertions (DAs) are instead used to impose that the answer to a certain boolean conjunctive query over the ontology is false, analogous to negative constraints in [2]. This is particularly useful to specify general forms of disjointness, which is again not supported in traditional ontology languages. The query rewriting algorithm given in this paper elegantly deals with all forms of inconsistency that can arise in DL-LiteA enriched with IdAs and DAs, thus it represents an alternative to the rewriting algorithm given in [9] for DL-LiteA only. Moreover, it properly manages all the inconsistencies caused by erroneous assignments of values to attributes, i.e., arising when a value of type Ti is assigned to an attribute of value-type Tj disjoint from Ti . This kind of inconsistency has not been considered in [9]. In this paper, for the sake of simplicity, we consider the setting of a single ontology constituted by a TBox and an ABox. However, our technique can be easily extended to the OBDA setting, where mapping assertions relate the TBox to the data sources [10]. The paper is organized as follows. In section 2 we provide some preliminaries. In Section 3 we provide some general properties of the IAR-semantics, useful for the rest of the paper. In Section 4, we show first-order rewritability of query answering of UCQs under the IAR-semantics. In Section 5 we conclude the paper. 2 Preliminaries Let Σ be a signature partitioned into ΣP , containing symbols for predicates, i.e., atomic concepts, atomic roles, attributes and value-domains, and ΣC , containing sym- bols for individual (object and value) constants. Given a DL language L, an L-ontology O = hT , Ai over Σ consists of a TBox T , i.e., a set of intensional assertions over Σ expressed in L, and an ABox A, i.e., a set of extensional assertions over Σ expressed in L. We assume that ABox assertions are always atomic, i.e., they correspond to ground atoms, and therefore we omit to refer to L when we talk about ABox assertions. The semantics of a DL ontology O is given in terms of first-order (FOL) inter- pretations. We denote with Mod (O) the set of models of O, i.e., the set of FOL- interpretations that satisfy all the assertions in T and A, where the definition of satisfac- tion depends on the DL language in which O is specified. An ontology O is satisfiable if Mod (O) 6= ∅, and O entails a FOL-sentence φ, denoted O |= φ, if φ is satisfied by every I ∈ Mod (O). The above definitions naturally apply to a TBox alone. In the following, we consider DL ontologies hT , Ai in which the TBox T is always satisfiable, whereas the ABox A may contradict T . When this happens, we say that A is T -inconsistent, T -consistent otherwise. For ontologies of this kind, the Intersection ABox Repair (IAR) semantics introduced in [8] allows for meaningful reasoning in the presence of inconsistency, which is instead trivialized under the FOL-semantics. The IAR-semantics is defined in terms of A-repairs: given an ontology O = hT , Ai, an A- repair for O is a set A0 ⊆ A such that Mod (hT , A0 i) 6= ∅, and there does not exist A00 such that A0 ⊂ A00 ⊆ A and Mod (hT , A00 i) 6= ∅. In other terms, an A-repair for O is a maximal T -consistent subset of A. The set of A-repairs for O is denoted by AR-Set(O). The IAR-semantics is then given in terms of IAR-models, as follows. Definition 1. Let O = hT , Ai be a possibly inconsistent DL ontology. The set of Intersection T ABox Repair (IAR)-models of O is defined as ModIAR (O) = M od(hT , Ai ∈AR-Set(O) Ai i) Notice that if O is satisfiable under FOL-semantics, then Mod (O) = ModIAR (O). The notion of consistent entailment is then the natural extension of classical entail- ment to IAR-semantics: a FOL-sentence φ is IAR-consistently entailed, or simply IAR- entailed, by O, written O |=IAR φ, if I |= φ for every I ∈ ModIAR (O). We focus now on DL-LiteA,id , a DL of the DL-Lite family [3] equipped with iden- tification assertions [4]. Since DL-LiteA,id distinguishes between object and value con- stants, we partition the set ΣC into two disjoint sets ΣO , which is the set of constants denoting objects, and ΣV , which is the set of constants denoting values. Basic DL-LiteA,id expressions are defined as follows: B −→ A | ∃Q | δ(U ) Q −→ P | P− E −→ ρ(U ) C −→ B | ¬B R −→ Q | ¬Q F −→ T1 | · · · | Tn V −→ U | ¬U A, P , and P − denote an atomic concept, an atomic role, and the inverse of an atomic role; δ(U ) (resp. ρ(U )) denotes the domain (resp. the range) of an attribute U , i.e., the set of objects (resp. values) that U relates to values (resp. objects); T1 , . . . , Tn are unbounded pairwise disjoint predefined value-domains; B is called basic concept. A DL-LiteA,id TBox is a finite set of the following assertions: BvC QvR U vV EvF (funct Q) (funct U ) (id B π1 , . . . , πn ) The assertions above, from left to right, respectively denote inclusions between con- cepts, roles, attributes, and value-domains, global functionality on roles and on at- tributes, and identification assertions (IdAs). In IdAs, πi is a path, which is an ex- pression built according to the following syntax: π −→ S | D? | π1 ◦ π2 , where S denotes an atomic role, the inverse of an atomic role, an attribute, or the inverse of an attribute, π1 ◦ π2 denotes the composition of paths π1 and π2 , and D?, called test relation, represents the identity relation on instances of D, which can be a basic con- cept or a value-domain. Test relations are used to impose that a path involves instances of a certain concept or value-domain. In our logic, IdAs are local, i.e., at least one πi ∈ {π1 , ..., πn } has length 1, i.e., it is an atomic role, the inverse of an atomic role, or an attribute. Intuitively, an IdA of the above form asserts that for any two different instances o, o0 of B, there is at least one πi such that o and o0 differ in the set of their πi -fillers, that is the set of objects that are reachable from o by means of πi . For exam- ple, the IdA (id Match homeTeam, visitorTeam) says that there are not two different matches with the same home team and host team (which is indeed what happens, for instance, in a season schedule of a football league). Inclusion assertions that do not contain (resp. contain) the symbols ’¬’ in the right- hand side are called positive inclusions (resp. negative inclusions). The set of positive (resp., negative) inclusions in T will be denoted by T + (resp., T − ). A DL-LiteA,id ABox is a finite set of assertions of the form A(a), P (a, b), and U (a, v), where A is an atomic concept, P is an atomic role, U is an attribute, a and b are constants of ΣO , and v is a constant of ΣV . In a DL-LiteA,id ontology O = hT , Ai, the following condition holds: each role or attribute that either is functional in T or appears (in either direct or inverse direction) in a path of an IdA in T is not specialized, i.e., it does not appear in the right-hand side of assertions of the form Q v Q0 or U v U 0. The semantics of DL-LiteA,id is given in [4]. We only recall here that each value- domain Ti is interpreted by means of the same function, denoted val (Ti ), in every interpretation, and each constant ci ∈ ΣV is interpreted as one specific value, denoted val (ci ). Also, the Unique Name Assumption is adopted. A boolean conjunctive query (BCQ) over a DL-LiteA ontology is an expression of the form q = ∃~y .conj(~t) where ~y is a set of variables and ~t is a set of terms (i.e., con- stants or variables) such that each variable in ~t is also in ~y , and conj(~t) is a conjunction of atoms of the form A(z), T (z 0 ), P (z, z 0 ) U (z, z 0 ) where A is an atomic concept, T is a value-domain, P is an atomic role and U is an attribute, and z, z 0 are terms. In the following, we will mainly consider boolean Wn unions of conjunctive queries (BUCQs), i.e., first order sentences of the form Q = i=1 qi where qi = ∃~ yi .conji (t~i ) is a BCQ. A BCQ q is satisfied by an ABox A (denoted by h∅, Ai |= q) if there exists a sub- stitution σ from the variables in q to constants of ΣC such that the formula σ(q) is satisfied in the FOL-interpretation structure where the ABox A determines the exten- sion of concepts, roles and attributes and the function val determines the extension of the value-domains. With a little abuse of notation we sometimes use σ(q) to indicate the set of the atoms in σ(q). When query q is satisfied by A, we say that σA (q) = σ(q) ∩ A Wn is the image of q in A. A BUCQ Q = i=1 qi is satisfied by an ABox A if there exists i ∈ {1, . . . n} such that qi is satisfied by A. All the results of the present work can be straightforwardly extended to non-boolean UCQs, by imposing the (natural) condition that every free variable in the query appears in at least one atom not involving value-domains. With the notion of query in place we introduce now denial assertions (DAs). A DA is an expression of the form ∀~y .conj(~t) → ⊥ where conj(~t) is defined as for BCQs. A DA is satisfied by an interpretation I if the formula ∃~y .conj(~t) evaluates to false in I. DAs are used to impose general forms of disjointness. For example, the denial ∀x, y.Match(x)∧homeTeam(x, y)∧visitorTeam(x, y) → ⊥ says that a match cannot have the same team as both home and visitor team. In the following we will consider DL-LiteA,id ontologies whose TBoxes are enriched with DAs, and call them DL-LiteA,id,den ontologies. 3 Properties of the IAR-Semantics We discuss here some properties of the IAR-semantics that will be used in the rest of the paper. We recall that the IAR-semantics is defined for DL ontologies composed by a consistent TBox and an ABox comprising only atomic assertions, therefore we consider below only this kind of ontologies. We start with the notion of inconsistent set. Definition 2. Let T be a TBox and let A be an ABox. A is a minimal T -inconsistent set if A is T -inconsistent, i.e., the ontology hT , Ai is unsatisfiable, and there is no A0 ⊂ A such that A0 is T -inconsistent. Let O = hT , Ai be a possibly inconsistent DL ontology. We denote with minIncSets(O) the set of minimal T -inconsistent sets contained in A. Notice that O is satisfiable iff minIncSets(O) = ∅. Then, the following property holds. Proposition 1. Let O = hT , Ai be a DL ontology such that minIncSets(O) 6= ∅, and let α be an ABox assertion in A. An A-repair A0 of O such that α 6∈ A0 exists iff there exists V ∈ minIncSets(O) such that α ∈ V . Let now AR-Set(O) = {A1 , . . . An } be the set of A-repairs of an ontology O = hT , Ai, and let q be a BCQ. From Definition 1, we derive that O |=IAR q iff there exists a subset A0 of A such that A0 ⊆ Ai for every 1 ≤ i ≤ n and hT , A0 i |= q. From the observation above, we derive the following theorem, which characterizes the notion of IAR-entailment of BCQs. Theorem 1. Let O = hT , Ai be a DL ontology such that minIncSets(O) 6= ∅, and let q be a BCQ. O |=IAR q iff there exists A0 ⊆ A such that: (i) A0 is T -consistent; (ii) hT , A0 i |= q; (iii) A0 ∩ V = ∅ for every V ∈ minIncSets(O). 4 Query Rewriting under IAR-Semantics in DL-LiteA,id,den In this section, we focus on DL-LiteA,id,den ontologies, and provide our technique for computing FOL-rewritings of BUCQs under the IAR-semantics. The notion of FOL- rewritability is essentially the same used under FOL-semantics [3]. More precisely, BUCQs in DL-LiteA,id,den are FOL-rewritable under the IAR-semantics if, for each BUCQs q and each DL-LiteA,id,den TBox T , there exists a FOL-query qr such that, for any ABox A hT , Ai, |=IAR q iff h∅, Ai |= qr . Such qr is called the IAR-perfect reformulation of q w.r.t. T . To come up with our reformulation method, we exploit Theorem 1. Roughly speak- ing, in the reformulation of a BUCQ q over a DL-LiteA,id,den TBox T , we encode into a FOL-formula all violations that can involve assertions belonging to images of q in any ABox A. Indeed, this can be done by reasoning only on the TBox, and considering each query atom separately. Intuitively, we deal with inconsistency by rewriting each atom α of q into a FOL-formula αr in such a way that h∅, Ai |= αr only if there exists a substitution σ of the variables in q to constants of ΣC such that q is satisfied by A, and σ(α) does not belong to any minimal T -inconsistent set. This inconsistency-driven rewriting is then suitably casted into the final reformula- tion, which takes into account also positive knowledge of the TBox, i.e., the inclusion assertions in T + . As we will show later in this section, this can be done by means of a slight variation of the algorithm PerfectRef of [3,10]. To formalize the above idea, we need to introduce some preliminary definitions. We consider Boolean queries corresponding to FOL-sentences of the form: n ^ m ^ ` ^ h ^ ∃z1 , . . . , zk . Hi (t1i ) ∧ ¬Ti (t2i ) ∧ Si (t3i , t4i ) ∧ t5i 6= t6i (1) i=1 i=1 i=1 i=1 where every Hi is an unary predicate, which is either an atomic concept or a value- domain, every Ti is a value-domain, every Si is a binary predicate, which is either an atomic role or an attribute, every tji is a term (i.e., either a constant or a variable), and z1 , . . . , zk are all the variables of the query. Notice that sentences of the form (1) are BCQs enriched with limited forms of inequalities and negation. Given a DL-LiteA,id,den TBox T , we denote with contr(T ) the set of all negative inclusions, functionalities, identifications, denials, and value-domain inclusions occur- ring in T . Intuitively, the set contr(T ) contains all those assertions in T which can be contradicted by assertions in the ABox. Now, to each assertion τ ∈ contr(T ), we associate a Boolean query, denoted ϕ(τ ), which encodes the violation of τ , i.e., it looks for images of the negation of τ . Below we provide some of such encodings. Missing cases are can be obtained in a similar way. - ϕ((funct P )) : ∃x, x1 , x2 .P (x, x1 ) ∧ P (x, x2 ) ∧ x1 6= x2 - ϕ(A1 v ¬A2 ) : ∃x.A1 (x) ∧ A2 (x) - ϕ(ρ(U ) v T ) : ∃x1 , x2 .U (x1 , x2 ) ∧ ¬T (x2 ) - ϕ(∀~x.conj(~t) → ⊥) : ∃~x.conj(~t) For example, ϕ((id Match homeTeam, visitorTeam)) = ∃x, x0 , y, z.Match(x) ∧ homeTeam(x, y) ∧ visitorTeam(x, z) ∧ Match(x0 ) ∧ homeTeam(x0 , y) ∧ visitorTeam(x0 , z) ∧ x 6= x0 , and ϕ(∀x, y.Match(x) ∧ homeTeam(x, y) ∧ visitorTeam(x, y) → ⊥) = ∃x, y.Match(x) ∧ homeTeam(x, y) ∧ visitorTeam(x, y). Then, the algorithm unsatQueries(T ) computes the first-order reformulation un- der FOL-semantics of ϕ(τ ) for each τ ∈ contr(T ), and returns the union of all such reformulations. To this aim, unsatQueries(T ) makes use of the algorithm PerfectRef6= (T + , ϕ(τ )), which is a slight variation of the algorithm PerfectRef given in [3]. In this modified version, inequality is considered as a primitive role and negated value-domains are considered as primitive concepts, thus inequality and negated atoms are never rewritten by the algorithm, and the algorithm does not unify query atoms if this causes a violation of an inequality. Note that the result of PerfectRef6= is a union of boolean queries of the form (1), represented as a set of queries, as usual. For example, assume to have a TBox containing the above mentioned IdA τ1 : (id Match homeTeam, visitorTeam) and the inclusion assertion playedMatch v Match. The algorithm PerfectRef6= (T + , ϕ(τ1 )) returns, among others, the query: ∃ x, x0 , y, z. playedMatch(x) ∧ homeTeam(x, y) ∧ visitorTeam(x, z) ∧ playedMatch(x0 )∧ homeTeam(x0 , y) ∧ visitorTeam(x0 , z) ∧ x 6= x0 Notice that the query ϕ(τ1 ) cannot be rewritten by unifying Match(x) and Match(x0 ) because of the inequality x 6= x0 . Such an inequality actually causes that in this example the algorithm can never rewrite queries through unification. Let O = hT , Ai be a DL-LiteA,id,den ontology. Since O is satisfiable iff there are no T -inconsistent sets in A, the following theorem states that the query produced by the algorithm unsatQueries(T ) can be used to check satisfiability of O. Theorem 2. Let O = hT , Ai be a DL-LiteA,id,den ontology. A T -inconsistent set V ⊆ A exists iff h∅, Ai |= unsatQueries(T ). If h∅, Ai |= unsatQueries(T ), then there exists q ∈ unsatQueries(T ) such that h∅, Ai |= q. This implies that there exists a substitution σ from the variables in q to constants of ΣC such that σ(q) projected over its positive atoms is contained in A. Similar to BCQs, we call this set the image of q in A, denoted σA (q). It is possible to show that σA (q) is a T -inconsistent set contained in A (in fact, this is part of the proof of Theorem 2). In order to exploit Theorem 1 towards the definition of a FOL- rewriting procedure, we need however to identify those assertions in A that participate to a minimal T -inconsistent set. From the definition of minimal T -inconsistent set, and from Theorem 2 it follows that σA (q) is a minimal T -inconsistent set iff for every V ⊂ σA (q) and every query q 0 ∈ unsatQueries(T ), we have that h∅, V i 6|= q 0 . Based on the above observations, we introduce the algorithm minUnsatQueries(T ) which, starting from the set unsatQueries(T ), computes a new set Qmin of queries, which enjoys the following properties: (i) For each query q ∈ Qmin , h∅, Ai |= q iff there exists in unsatQueries(T ) a query q 0 such that h∅, Ai |= q 0 . This guarantees that Theorem 2 also holds with minUnsatQueries(T ) in place of unsatQueries(T ). (ii) For each query q ∈ Qmin , if h∅, Ai |= q, then for every image σA (q) of q in A, h∅, V i 6|= q 0 , where V ⊂ σA (q) and q 0 ∈ Qmin . This guarantees that if a query q ∈ Qmin is such that h∅, Ai |= q, then every image of q in A is a minimal T -inconsistent set. Before presenting the algorithm minUnsatQueries(T ), we need to introduce some preliminary notions. Given a query q, we say that a term t occurs in an object position of q if q contains an atom of the form A(t), P (t, t0 ), P (t0 , t), U (t, t0 ), whereas we say that t occurs in a value position of q if q contains an atom of the form T (t), U (t0 , t), where A, P , U , and T have the usual meaning. Given two terms t1 and t2 occurring in a query q, we say that t1 and t2 are compatible in q if either both t1 and t2 appear only in object positions of q or both t1 and t2 appear only in value positions of q. Moreover, let q and q 0 be two boolean queries. We say that q is a proper syntactical subset of q 0 , written q ≺Rn q 0 if there exists a renaming function Rn(q, q 0 ) of the variables in q to the variables in q 0 , such that every atom S(~t) occurring in Rn(q, q 0 ) occurs also in q 0 and an analogous renaming from q 0 to q does not exists. The algorithm minUnsatQueries(T ) is given below. Algorithm: minUnsatQueries(T ) Input: a DL-LiteA,id,den TBox T Output: a set of queries 0 1 Q ← unsatQueries(T ); 00 0 2 Q ← saturate(Q ); 000 3 Q ← ∅; 000 4 while Q 6= Q00 do 5 Q ← Q00 ; 000 6 foreach q ∈ Q00 do 7 foreach atom U (t, t0 ) in q do 8 if there exist no atoms T (t0 ) and ¬T (t0 ) in q then 9 foreach value-domain T in {T1 , . . . Tn } do 10 Q00 ← Q00 \ {q}; 11 Q00 ← Q00 ∪ {q ∧ T (t0 )}; 12 Q00 ← Q00 ∪ {q ∧ ¬T (t0 )}; 000 13 foreach q ∈ Q do 14 foreach term t occurring in q do 15 if both Ti (t) and Tj (t) occur in q, with i 6= j then Q000 ← Q000 \ {q}; 0 000 16 foreach q and q in Q do 17 if q ≺Rn q then Q000 ← Q000 \ {q 0 }; 0 000 18 return Q The algorithm proceeds as follows. Step 1 (line 1): the algorithm initializes Q0 to the set unsatQueries(T ). Step 2 (line 2): the algorithm computes the set Q00 through the algorithm saturate. Starting from each query q ∈ Q0 , such an algorithm first unifies pairs of compatible terms in q in all passible ways; then, for any query q 0 computed in this way, for each pair of terms t1 and t2 occurring in q 0 that are syntactically different, it adds the in- equality atom t1 6= t2 to q 0 ; finally it returns the union of Q0 with this new set of queries. Notice that such an operation is sound and complete with respect to the set of queries in Q0 : in particular, no answer to the set of queries is lost by this transforma- tion, since, for every pair of compatible terms t1 , t2 which are forced to be not equal in q, there is a query q 0 in Q0 where the same terms have been unified. For instance, assume that Q0 contains only the query q : ∃x, y.Match(x) ∧ homeTeam(x, y) ∧ visitorTeam(x, y). Then, the algorithm saturate returns a set constituted by the queries q1 : ∃x, y.Match(x) ∧ homeTeam(x, y) ∧ visitorTeam(x, y) ∧ x 6= y and q2 : ∃x.Match(x) ∧ homeTeam(x, x) ∧ visitorTeam(x, x). Step 3 (lines 3-12): let {T1 . . . Tn } be the set of value-domains. The algorithm com- putes the set Q000 by producing from each query q ∈ Q00 the following queries: for each atom U (x, y), where U is an attribute name, if no atoms T (y) appears in q, where T is a value-domain, then the algorithm builds 2n new queries by substituting the atom U (x, y) with either the conjunction of atoms U (x, y) ∧ Ti (y) or U (x, y) ∧ ¬Ti (y), for each 1 ≤ i ≤ n. In this way, every possible combination is computed. It is easy to verify that such a transformation is also sound and complete. Step 3 is motivated by the need to provide a complete comparison in Step 5, as explained below. Step 4 (lines 13-15): the algorithm removes from Q000 every query q in which a term t occurs in two atoms of the form T1 (t) and T2 (t) (T1 and T2 are disjoint, and therefore for each constant c in ΣV , T1 (c) ∧ T2 (c) is a contradiction). Step 5 (lines 16-17): the algorithm removes from the set Q000 each query q 0 such that there is in Q000 a different query q whose atoms form, up to renaming of the variables in q, a proper subset of the atoms appearing in q 0 . This simplified form of query contain- ment guarantees that for every ABox A and every query q in Q000 , there does not exist a query q 0 in Q000 , such that for every image σ(q) of q in A, h∅, V i |= q 0 where V ⊂ σ(q). Step 6 (line 18): the algorithm terminates by returning the set Q000 . Let us now continue the example given at Step 2. Assume that Q0 contains also the query q3 : ∃x.homeTeam(x, x) which is associate to the denial assertion ∀x.homeTeam(x, x) → ⊥. Obviously, besides query q1 and q2 , Q00 contains also q3 , which is natively in a “saturated” form. Step 3 and Step 4 have no effect in this ex- ample, since none of the queries in Q00 has atoms with attributes or value-domains as predicate. Therefore, Q000 = Q00 , and Step 5 eliminates query q2 from Q000 , since q3 ≺Rn q2 . Notice that this step is crucial to ensure that every image of a query in Q000 in any ABox A is a minimal T -inconsistent set. Indeed, let us, for instance, pose A = {Match(a), homeTeam(a, a), visitorTeam(a, a)}; q2 has an image in A, which is A itself, which is also a T -inconsistent set, but not minimal: indeed, the set {homeTeam(a, a)} ⊂ A is a also T -inconsistent set, since it violates the DA ∀x.homeTeam(x, x) → ⊥. This set is also minimal, and is indeed an image in A of the query q3 . The following lemma states that the algorithm minUnsatQueries(T ) can be used to check if a DL-LiteA,id,den ontology O = hT , Ai is consistent. Lemma 1. Let O = hT , Ai be a possibly inconsistent DL-LiteA,id,den ontology. Then, h∅, Ai |= minUnsatQueries(T ) iff h∅, Ai |= unsatQueries(T ). The following crucial lemma guarantees instead that one can use the queries pro- duced by the algorithm minUnsatQueries(T ) in order to compute every minimal T - inconsistent set in A. Lemma 2. Let O = hT , Ai be a possibly inconsistent DL-LiteA,id,den ontology, and let q be a query in minUnsatQueries(T ). If h∅, Ai |= q, then every image of q in A is a minimal T -inconsistent set. Let α, β be two atoms. We say that β is compatible with α if there exists a mapping µ of the variables occurring in β to the terms occurring in α such that µ(β) = α (and in this case we denote the above mapping µ with the symbol µα/β ). Given an atom α and a query q, we denote by CompSet(α, q) the set of atoms of q which are compatible with α. Then, let T be a DL-LiteA,id,den TBox and let α be an atom, we define MinIncSet T (α) as follows.   T _ _ MinIncSet (α) =  µα/β (q) q∈minUnsatQueries(T )∧CompSet(α,q)6=∅ β∈CompSet(α,q) The following key property holds. Theorem 3. Let hT , Ai be a possibly inconsistent DL-LiteA,id,den ontology, and let α be an ABox assertion. There exists a minimal T -inconsistent set V in A such that α ∈ V iff h∅, Ai |= MinIncSet T (α). Let T be a DL-LiteA,id,den TBox and let q be a BCQ of the form n ^ m ^ ` ^ ∃z1 , . . . , zk . Ai (t1i ) ∧ Pi (t2i , t3i ) ∧ Ui (t4i , t5i ) (2) i=1 i=1 i=1 where all symbols have the usual meaning. We denote by IncRewr IAR (q, T ) the fol- lowing FOL-sentence: n ^ IncRewr IAR (q, T ) = ∃z1 , . . . , zk . Ai (t1i ) ∧ ¬MinIncSet T (Ai (t1i ))∧ i=1 m ^ ` ^ Pi (t2i , t3i ) ∧ ¬MinIncSet T (Pi (t2i , t3i )) ∧ Ui (t4i , t5i ) ∧ ¬MinIncSet T (Ui (t4i , t5i )) i=1 i=1 Let W Q be a set of CQs, we define IncRewrUCQ IAR (Q, T ) = qi ∈Q IncRewr (q IAR i , T ). We are then able to give our final results on refor- mulation of UCQs under the IAR-semantics. Theorem 4. Let T be a DL-LiteA,id,den TBox and let Q be a UCQ. For every ABox A, hT , Ai |=IAR Q iff h∅, Ai |= IncRewrUCQ IAR (saturate(PerfectRef(T + , Q)), T ). In the above theorem, PerfectRef coincides with the algorithm of [10]. This algorithm takes as input the set of positive inclusions T + and the query Q, and computes the perfect reformulation under FOL-semantics of Q w.r.t. T + . PerfectRef(T + , Q) re- turns a set of CQs specified over T . Through this reformulation we first preprocess each query according to “positive” knowledge of the TBox, and then manage it to deal with possible inconsistency. Then, the algorithm saturate previously described is ap- plied to the query thus obtained: this step is necessary for technical reasons (roughly speaking, it is needed in order to exactly identify, for every query atom α, the queries from minUnsatQueries(T ) which correspond to inconsistent sets to which an image of α might belong). This query is finally reformulated according to the definition of IncRewrUCQ IAR . The following complexity result is a direct consequence of Theorem 4, since estab- lishing whether h∅, Ai |= IncRewrUCQ IAR (saturate(PerfectRef(T + , Q)), T ) sim- ply amounts to evaluating a FOL-query over the ABox A, which is in AC 0 in data complexity. Corollary 1. Let O be a DL-LiteA,id,den ontology and let Q be a UCQ. Deciding whether O |=IAR Q is in AC 0 in data complexity. We finally notice that the above results directly imply that query answering of UCQs in DL-LiteA,id,den under standard semantics is FOL-rewritable, and therefore in AC 0 in data complexity, i.e., it has the same computational behavior of all DLs of the DL-Lite family. 5 Conclusion Motivated by the requirements arising in applications of ontology-based data access, we have presented a new algorithm for inconsistency-tolerant query answering in a DL obtained by extending DL-LiteA with identification and denial assertions. The algorithm is based on a rewriting technique, and shows that query answering under the considered inconsistency-tolerant semantics in DL-Lite remains first-order rewritable, even when identification and denial assertions are added to the TBox. We will soon experiment our new technique in the context of several ongoing OBDA projects. Our main goal is to devise optimization techniques that allow for simplifying the rewritten query as much as possible, so that the performance of the query answering process remains acceptable even under the inconsistency-tolerant semantics. References 1. Bienvenu, M.: First-order expressibility results for queries over inconsistent DL-Lite knowl- edge bases. In: Proc. of DL 2011. CEUR, ceur-ws.org, vol. 745 (2011) 2. Calı̀, A., Gottlob, G., Lukasiewicz, T.: A general Datalog-based framework for tractable query answering over ontologies. In: Proc. of PODS 2009. pp. 77–86 (2009) 3. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning 39(3), 385–429 (2007) 4. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Path-based identifi- cation constraints in description logics. In: Proc. of KR 2008. pp. 231–241 (2008) 5. Chomicki, J.: Consistent query answering: Five easy pieces. In: Proc. of ICDT 2007. LNCS, vol. 4353, pp. 1–17. Springer (2007) 6. Gärdenfors, P., Rott, H.: Belief revision. In: Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 4, pp. 35–132. Oxford University Press (1995) 7. Kontchakov, R., Lutz, C., Toman, D., Wolter, F., Zakharyaschev, M.: The combined approach to query answering in DL-Lite. In: Proc. of KR 2010. pp. 247–257 (2010) 8. Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Inconsistency-tolerant seman- tics for description logics. In: Proc. of RR 2010 (2010) 9. Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Query rewriting for inconsistent DL-Lite ontologies. In: Proc. of RR 2011 (2011) 10. Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. on Data Semantics X, 133–173 (2008) 11. Savo, D.F., Lembo, D., Lenzerini, M., Poggi, A., Rodrı́guez-Muro, M., Romagnoli, V., Ruzzi, M., Stella, G.: M ASTRO at work: Experiences on ontology-based data access. In: Proc. of DL 2010. CEUR, ceur-ws.org, vol. 573, pp. 20–31 (2010)