This paper is motivated by two requirements arising in practical applications of ontology-based data access (OBDA): the need of inconsistencytolerant semantics, which allow for dealing with classically inconsistent specifications; and the need of expressing assertions which go beyond the expressive abilities of traditional Description Logics, namely identification and denial assertions. 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.
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
ontology, which provides a conceptual and shared representation of the domain of
interest [
In the last years we have experimented (see, e.g., [
Motivated by the first mentioned requirement, we have recently proposed various
inconsistency-tolerant semantics [
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
originally presented in [
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 [
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 [
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 [
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.
Let be a signature partitioned into P , containing symbols for predicates, i.e., atomic concepts, atomic roles, attributes and value-domains, and C , containing symbols 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) interpretations. We denote with Mod (O) the set of models of O, i.e., the set of FOLinterpretations that satisfy all the assertions in T and A, where the definition of satisfaction 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 j= , if is satisfied by every I 2 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 [
Definition 1. Let O = hT ; Ai be a possibly inconsistent DL ontology. The set of Intersection ABox Repair (IAR)-models of O is defined as ModIAR(O) = M od(hT ; TAi2AR-Set(O) Aii)
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 entailment to IAR-semantics: a FOL-sentence is IAR-consistently entailed, or simply IARentailed, by O, written O j=IAR , if I j= for every I 2 ModIAR(O).
We focus now on DL-LiteA;id, a DL of the DL-Lite family [
Basic DL-LiteA;id expressions are defined as follows: B C ! !
A j 9Q j B j :B (U )
Q R ! !
P j P Q j :Q
E F V ! ! !
(U ) T1 j U j :U j Tn 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: B v C
Q v R
U v V
E v F (funct Q) (funct U ) (id B 1; : : : ; n) The assertions above, from left to right, respectively denote inclusions between concepts, roles, attributes, and value-domains, global functionality on roles and on attributes, and identification assertions (IdAs). In IdAs, i is a path, which is an expression built according to the following syntax: ! S j D? j 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 concept 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 2 f 1; :::; ng 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 example, 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 righthand 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 [
A boolean conjunctive query (BCQ) over a DL-LiteA ontology is an expression of the form q = 9~y.conj(~t) where ~y is a set of variables and ~t is a set of terms (i.e., constants 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 (z0), P (z; z0) U (z; z0) where A is an atomic concept, T is a value-domain, P is an atomic role and U is an attribute, and z, z0 are terms. In the following, we will mainly consider boolean unions of conjunctive queries (BUCQs), i.e., first order sentences of the form Q = Wn i=1 qi where qi = 9y~i.conji(t~i) is a BCQ.
A BCQ q is satisfied by an ABox A (denoted by h;; Ai j= q) if there exists a substitution 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 extension 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 is the image of q in A. A BUCQ Q = Wn
i=1 qi is satisfied by an ABox A if there exists i 2 f1; : : : ng 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 8~y.conj(~t) ! ? where conj(~t) is defined as for BCQs. A DA is satisfied by an interpretation I if the formula 9~y.conj(~t) evaluates to false in I. DAs are used to impose general forms of disjointness. For example, the denial 8x; 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
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 62 A0 exists iff there exists V 2 minIncSets (O) such that 2 V .
Let now AR-Set(O) = fA1; : : : Ang 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 j=IAR q iff there exists a subset A0 of A such that A0 Ai for every 1 i n and hT ; A0i j= 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 j=IAR q iff there exists A0 A such that: (i) A0 is T -consistent; (ii) hT ; A0i j= q; (iii) A0 \ V = ; for every V 2 minIncSets (O). 4
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
FOLrewritability is essentially the same used under FOL-semantics [
To come up with our reformulation method, we exploit Theorem 1. Roughly speaking, 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 j= 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
reformulation, 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 [
We consider Boolean queries corresponding to FOL-sentences of the form: n m 9z1; : : : ; zk: ^ Hi(ti1) ^ ^ :Ti(ti2) ^ i=1 i=1 ` ^ Si(ti3; ti4) ^ i=1 h ^ ti5 6= ti6 i=1 (1) where every Hi is an unary predicate, which is either an atomic concept or a valuedomain, every Ti is a value-domain, every Si is a binary predicate, which is either an atomic role or an attribute, every tij 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 occurring 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 2 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 )) : - '(A1 v :A2) : - '( (U ) v T ) : - '(8~x.conj(~t) ! ?) : 9x; x1; x2.P (x; x1) ^ P (x; x2) ^ x1 6= x2 9x.A1(x) ^ A2(x) 9x1; x2.U (x1; x2) ^ :T (x2) 9~x.conj(~t) For example, '((id Match homeTeam; visitorTeam)) = 9x; x0; y; z.Match(x) ^ homeTeam(x; y) ^ visitorTeam(x; z) ^ Match(x0) ^ homeTeam(x0; y) ^ visitorTeam(x0; z) ^ x 6= x0, and '(8x; y.Match(x) ^ homeTeam(x; y) ^ visitorTeam(x; y) ! ?) = 9x; y.Match(x) ^ homeTeam(x; y) ^ visitorTeam(x; y).
Then, the algorithm unsatQueries(T ) computes the first-order reformulation
under FOL-semantics of '( ) for each 2 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 [
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: 9 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 j= unsatQueries(T ).
If h;; Ai j= unsatQueries(T ), then there exists q 2 unsatQueries(T ) such that h;; Ai j= 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 FOLrewriting 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 q0 2 unsatQueries(T ), we have that h;; V i 6j= q0.
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 2 Qmin, h;; Ai j= q iff there exists in unsatQueries(T ) a query q0 such that h;; Ai j= q0. This guarantees that Theorem 2 also holds with minUnsatQueries(T ) in place of unsatQueries(T ). (ii) For each query q 2 Qmin, if h;; Ai j= q, then for every image A(q) of q in A, h;; V i 6j= q0, where V A(q) and q0 2 Qmin. This guarantees that if a query q 2 Qmin is such that h;; Ai j= 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 q0 be two boolean queries. We say that q is a proper syntactical subset of q0, written q Rn q0 if there exists a renaming function Rn(q; q0) of the variables in q to the variables in q0, such that every atom S(~t) occurring in Rn(q; q0) occurs also in q0 and an analogous renaming from q0 to q does not exists. The algorithm minUnsatQueries(T ) is given below. 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 2 Q0, such an algorithm first unifies pairs of compatible terms in q in all passible ways; then, for any query q0 computed in this way, for each pair of terms t1 and t2 occurring in q0 that are syntactically different, it adds the inequality atom t1 6= t2 to q0; 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 transformation, since, for every pair of compatible terms t1; t2 which are forced to be not equal in q, there is a query q0 in Q0 where the same terms have been unified. For instance, assume that Q0 contains only the query q : 9x; y.Match(x) ^ homeTeam(x; y) ^ visitorTeam(x; y). Then, the algorithm saturate returns a set constituted by the queries q1 : 9x; y.Match(x) ^ homeTeam(x; y) ^ visitorTeam(x; y) ^ x 6= y and q2 : 9x.Match(x) ^ homeTeam(x; x) ^ visitorTeam(x; x).
Step 3 (lines 3-12): let fT1 : : : Tng be the set of value-domains. The algorithm computes the set Q000 by producing from each query q 2 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 q0 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 q0. This simplified form of query containment guarantees that for every ABox A and every query q in Q000, there does not exist a query q0 in Q000, such that for every image (q) of q in A, h;; V i j= q0 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 : 9x.homeTeam(x; x) which is associate to the denial assertion 8x.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 example, 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 = fMatch(a); homeTeam(a; a); visitorTeam(a; a)g; q2 has an image in A, which is A itself, which is also a T -inconsistent set, but not minimal: indeed, the set fhomeTeam(a; a)g A is a also T -inconsistent set, since it violates the DA 8x.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 j= minUnsatQueries(T ) iff h;; Ai j= unsatQueries(T ).
The following crucial lemma guarantees instead that one can use the queries produced 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 j= 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.
MinIncSet T ( ) = _ 0 = (q)A q2minUnsatQueries(T )^CompSet( ;q)6=;
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 2 V iff h;; Ai j= MinIncSet T ( ).
Let T be a DL-LiteA;id;den TBox and let q be a BCQ of the form
n 9z1; : : : ; zk: ^ Ai(ti1) ^ i=1 m ^ Pi(ti2; ti3) ^ i=1 ` ^ Ui(ti4; ti5) i=1 (2) where all symbols have the usual meaning. We denote by IncRewr IAR(q; T ) the following FOL-sentence:
n IncRewr IAR(q; T ) = 9z1; : : : ; zk: ^ Ai(ti1) ^ :MinIncSet T (Ai(ti1))^ i=1 m ^ Pi(ti2; ti3) ^ :MinIncSet T (Pi(ti2; ti3)) ^ i=1 ` ^ Ui(ti4; ti5) ^ :MinIncSet T (Ui(ti4; ti5)) i=1 Let Q be a set of CQs, we define IncRewrUCQ IAR(Q; T ) = Wqi2Q IncRewr IAR(qi; T ). We are then able to give our final results on reformulation 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 j=IAR Q iff h;; Ai j= IncRewrUCQ IAR(saturate(PerfectRef(T +; Q)); T ).
In the above theorem, PerfectRef coincides with the algorithm of [
The following complexity result is a direct consequence of Theorem 4, since establishing whether h;; Ai j= IncRewrUCQ IAR(saturate(PerfectRef(T +; Q)); T ) simply 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 j=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.
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.