=Paper=
{{Paper
|id=None
|storemode=property
|title=Inconsistency-Tolerant First-Order Rewritability of DL-Lite with Identification and Denial Assertions
|pdfUrl=https://ceur-ws.org/Vol-846/paper_59.pdf
|volume=Vol-846
|dblpUrl=https://dblp.org/rec/conf/dlog/LemboLRRS12
}}
==Inconsistency-Tolerant First-Order Rewritability of DL-Lite with Identification and Denial Assertions==
https://ceur-ws.org/Vol-846/paper_59.pdf
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)