=Paper=
{{Paper
|id=None
|storemode=property
|title=Repairing Incomplete Reasoners
|pdfUrl=https://ceur-ws.org/Vol-745/paper_13.pdf
|volume=Vol-745
|dblpUrl=https://dblp.org/rec/conf/dlog/StoilosG11
}}
==Repairing Incomplete Reasoners==
https://ceur-ws.org/Vol-745/paper_13.pdf
Repairing Incomplete Reasoners
Giorgos Stoilos and Bernardo Cuenca Grau
Oxford University Computing Laboratory
Wolfson Building, Parks Road, OX1 3QD, Oxford
Abstract. The pressing need for scalable query answering has moti-
vated the development of many incomplete ontology-based reasoners.
Improving the completeness of such systems without sacrificing their
favourable performance would be beneficial to many applications. In this
paper, we address the following problem: given a query q, a TBox T and
an incomplete reasoner ans (i.e., one that accepts q and T as valid inputs
but fails to return all query answers to q w.r.t. T and some dataset), we
aim at computing a (hopefully small) TBox R (a repair ) which logically
follows from T and such that ans is provably complete w.r.t. q and T ∪ R,
regardless of the input data. We identify conditions on q, T and ans that
are sufficient to ensure the existence of such repair and present a practi-
cal repair generation algorithm. Our experiments suggest that repairs of
small size can be computed for well-known ontologies and reasoners.
1 Introduction
In Semantic Web applications, a description logic TBox is frequently used for
describing the meaning of data stored in various sources. A query language
(based on conjunctive queries) is then used for data access [13]. Unfortunately,
when using an expressive ontology language, computing query answers can be
costly, and in a Semantic Web setting, datasets may be extremely large.
Motivated by the need for scalable query answering, there has been a growing
interest in the development of incomplete ontology-based reasoning systems,
which are not guaranteed to compute all query answers for some combinations
of queries, TBoxes and datasets accepted as valid inputs. Many such systems
(e.g., Jena, OWLim, and Oracle’s Semantic Store) are based on rule technologies;
others are based on approximate reasoning techniques [7, 11, 1].
Incomplete query answers, however, may not be acceptable in some cases, and
even if some incompleteness is acceptable, computing as many answers as possi-
ble without affecting performance would be beneficial to many applications. Not
surprisingly, many techniques for improving the completeness of (incomplete)
reasoning systems have been proposed in recent years. A widely use approach
relies on the materialisation of certain kinds of TBox consequences, prior to
accessing the data. TBox materialisation is indeed a convenient and low-cost
solution, as it does not rely on modifying the internals of the reasoning sys-
tem at hand: it can either be included by reasoning systems’ implementors as
a pre-processing step (e.g., DLEJena [3], PelletDB, TrOWL [11], Minerva [10]
and DLDB [6]), or it can be performed by application designers, who have little
knowledge of and/or control over the reasoner. This approach, however, exhibits
several limitations:
1. TBox materialisation is done blindfold, without taking into account neither
the capabilities of the incomplete reasoner under consideration, nor the pre-
cise sources of its incompleteness for the application at hand.
2. In order to avoid a blowup in the size of the TBox, materialisation involves
only simple atomic subsumption relations, and relevant entailments describ-
ing more complex dependencies are typically ignored.
3. It is often difficult, or even infeasible, to estimate the extent to which mate-
rialisation has improved the system’s completeness for the given application
at hand, especially if the data is very large, unknown, or frequently changing.
In this paper, we present a novel approach to TBox materialisation that attempts
to address many of these limitations. Given a TBox T expressed in a language
L, a conjunctive query (CQ) q, and a reasoning system ans satisfying certain
properties known in advance (e.g., soundness), we aim at computing a (hopefully
small) set of TBox axioms R, called a (q, T )-repair for ans, such that R logically
follows from T and the system is guaranteed to compute all answers to q w.r.t.
T ∪ R (and hence also w.r.t. T ), regardless of the input data.
Our TBox materialisation techniques are “guided” by both the input query
and TBox and the capabilities of the reasoner at hand, thus limiting the number
of materialised consequences. Furthermore, our approach provides a provable
completeness guarantee: after extending T with a (q, T )-repair, the incomplete
reasoner at hand is indistinguishable from a complete one w.r.t. q and T , and
regardless of the data (which is often unknown or frequently changing). Finally,
if a (q, T )-repair does not exist for the given reasoner, we also provide means
for quantifying the extent to which the reasoner’s completeness improved upon
materialisation of a given set of TBox consequences.
Our main contributions can be summarised as follows:
– We formalise the notion of a repair for a given CQ, TBox and reasoner.
– We identify sufficient conditions for the existence of a repair. Our conditions
establish a bridge between the framework of completeness evaluation [16, 15]
and the notion of interpolation in the context of DLs [8, 14, 9].
– We then present a practical algorithm that is guaranteed to compute a repair
under certain assumptions. Our algorithm extends well-known query rewrit-
ing techniques for DLs [12, 2] with means for computing suitable interpolants
for each query in the rewriting.
– Although the assumptions required by our algorithm may seem somewhat
strict, we provide empirical evidence that repairs can be computed for well-
known ontologies and incomplete reasoners. Furthermore, the size of such
repairs is surprisingly small and preliminary evaluation has shown that their
impact on performance is negligible. Finally, for reasoner which are complete
only for a very weak description logic, we show that our techniques can
provide “partial repairs”, whose impact can be quantified.
2
Although our main focus is on repairing rule-based reasoners, we feel that our
techniques are also highly relevant to recent DL approximation frameworks [11,
1], and provide new insights into the process of approximation.
Proofs for all lemmas and theorems can be found online.1
2 Preliminaries
We use DLs that do not allow for nominals and we also assume that only atomic
assertions are allowed in ABoxes.
Let C, R, and I be countable, pairwise disjoint sets of atomic concepts,
atomic roles, and individuals. An ELHI-role is either an atomic role P or its
inverse P − . The set of ELHI-concepts is defined inductively by the following
grammar, where A ∈ C, R is an ELHI-role, and C(i) are ELHI-concepts:
C := ⊤ | ⊥ | A | C1 ⊓ C2 | ∃R.C
An ELHI-TBox T is a finite set of GCIs C1 ⊑ C2 with Ci ELHI-concepts
and RIAs R1 ⊑ R2 with Ri ELHI-roles. An ABox A is a finite set of assertions
A(a) or P (a, b), for A ∈ C, P ∈ R, and a, b ∈ I. An ELHI-ontology O = T ∪ A
consists of an ELHI-TBox T and an ABox A.
Moreover, the DLP fragment of ELHI [5] (DLP-ELHI) is obtained from
ELHI by disallowing concepts of the form ∃R.C on the right-hand side of GCIs.
A conjunctive query (CQ) q is an expression of the form
q(x1 , . . . , xn ) ← α1 , . . . , αm
where each αi is a concept or role atom of the form A(t) or R(t, t0 ) (for t, t0
function-free terms and A, R atomic) and each xj is a distinguished variable
occurring in some αi . The remaining variables are called undistinguished. We
use the standard notion of a certain answer to q w.r.t. O = T ∪ A, and we
denote with cert(q, O) the set of all certain answers to q w.r.t. O. Given q1 , q2
with the same distinguished variables ~x we say that q1 subsumes q2 w.r.t. T ,
written q2 ⊑T q1 , if the FO-entailment T |= ∀~x.(Bq2 → Bq1 ) holds, with Bqi the
formula obtained from the conjunction of all body atoms in qi by existentially
quantifying over all undistinguished variables.
Finally, a UCQ rewriting u for a CQ q and TBox T is a union of conjunctive
queries (a set of CQs with the same distinguished variables) that satisfies the
following properties for each ABox A such that O = T∪∪ A is consistent [2]:
cert(q 0 , A) ⊆ cert(q, O) for each q 0 ∈ u, and cert(q, O) ⊆ q0 ∈u cert(q 0 , A).
3 Completeness Repairs
We start by recalling from [16, 15] the notions of a CQ answering algorithm, and
of completeness for a query q and TBox T .
1
https://rapidshare.com/files/460900188/main.pdf
3
Definition 1. A CQ answering algorithm ans for a DL L is a procedure that,
for each L-ontology O and CQ q computes in a finite number of steps a set
ans(q, O) of tuples of constants. It is sound if ans(q, O) ⊆ cert(q, O) for each O
and q. It is complete if cert(q, O) ⊆ ans(q, O) for each O and q. It is monotonic
if ans(q, O) ⊆ ans(q, O0 ) for each O, O0 and q with O ⊆ O0 . It is invariant under
renamings if, for each q, O = T ∪ A, O0 = T ∪ A0 and isomorphism ν between A
and A0 we have ~a ∈ ans(q, O) if and only if ν(~a) ∈ ans(q, O0 ). It is well-behaved
if it is sound, monotonic and invariant under renamings. We denote with C L
the class of all well-behaved CQ answering algorithms for L.
Finally, we say that ans is (q, T )-complete for a query q and TBox T if for
each ABox A s.t. O = T ∪ A is consistent, we have that cert(q, O) ⊆ ans(q, O).
This general definition allow us to abstract from the specifics of implemented
systems. All incomplete reasoning algorithms known to us are well-behaved: they
are sound, query answers can only grow if we add axioms to the ontology, and
they do not depend on trivial renamings of ABox individuals. Furthermore, a
(q, T )-complete algorithm, even if incomplete in general, behaves exactly like
a complete one w.r.t. the given query q and TBox T , regardless of the data.
Consider, as a running example, the following ELHI-TBox T0 and query q0 :
T0 = {∃takes.Course ⊑ Student, GradCo ⊑ Course,
GradSt ⊑ ∃takes.GradCo, PhDSt ⊑ GradSt, Student ⊓ Course ⊑ ⊥}
q0 (x) ← Student(x)
Consider an algorithm ans0 that first translates DLP-ELHI GCIs in T0 into a
datalog program using standard transformations (and discarding the remaining
GCIs), then saturates the input ABox w.r.t. the program, and finally answers
q0 w.r.t. the saturated ABox. Clearly, ans0 is not (q0 , T0 )-complete: it returns
the empty set for A = {GradSt(a)}, whereas cert(q0 , T0 ∪ A) = {a}. Computing
the missing answer requires axiom GradSt ⊑ ∃takes.GradCo, which is discarded.
Note, however, that one could dispense with the discarded axiom and still recover
the missing answer by extending T0 with the following DLP-ELHI TBox R0 :
R0 = {GradSt ⊑ Student} (1)
Since T0 |= R0 , extending T0 with R0 does not change the meaning of T0 . The
behaviour of ans0 w.r.t. T0 ∪R0 , however, is now different because ans0 translates
R0 into a datalog clause and hence ans0 (q0 , T0 ∪ R0 ∪ A) = {a}.
Note also that adding R0 allows us to recover missing answers w.r.t. many
other ABoxes different from A. For example, given A0 = {PhDSt(b)} and T0 ∪A0 ,
we have that b is a certain answer to q0 that is computed by ans0 only after
extending T0 with R0 .
Our example suggests that given q, T and an algorithm ans that is incomplete
for q and T , it may be possible to recover all missing answers to q (w.r.t. all
possible ABoxes) by “repairing” T for ans—that is, by materialising a (hopefully
small) number of T -consequences that ans can process.
4
Definition 2. Let L be a DL, q a CQ, T an L-TBox, A an ABox, and ans a
CQ answering algorithm for L. A (q, T , A)-repair R for ans is an L-TBox such
that
1. T |= R; and
2. cert(q, T ∪ A) ⊆ ans(q, T ∪ R ∪ A).
Given a set A of ABoxes, we say that R is a (q, T , A)-repair for ans if it is a
(q, T , A)-repair for ans for each A ∈ A. Finally, we say that R is a (q, T )-repair
for ans if it is a (q, T , A)-repair for ans for every ABox A s.t. T ∪A is consistent.
Unfortunately, deciding, on the one hand, whether ans is (q, T )-complete and,
on the other hand, whether R is a (q, T )-repair for ans may involve computing
query answers w.r.t. an unlimited number of ABoxes. In [16, 15], however, it was
shown that under certain conditions on q and T it is possible to decide (q, T )-
completeness by computing query answers only w.r.t. a finite (and hopefully
small) number of ABoxes. Such finite set of ABoxes is called a testing base.
Definition 3. Let L be a description logic, let C be a class of CQ answering
algorithms for L, let T be an L-TBox, and let q be a CQ. A (q, T )-testing base
B for C is a finite set of ABoxes A such that the following property holds for
each algorithm ans in C: if cert(q, T ∪ A) ⊆ ans(q, T ∪ A) for each A ∈ B, then
cert(q, T ∪ A0 ) ⊆ ans(q, T ∪ A0 ) for each ABox A0 consistent with T .
In our previous work [16, 15] we have shown how to compute a (q, T )-testing
base (if one exists) for the class C L of well-behaved algorithms.
Consider our running example. The set of ABoxes B0 = {A1 , . . . , A5 } defined
as follows is a (q0 , T0 )-testing base for the class of all well-behaved algorithms:
A1 = {Student(a)}, A2 = {takes(a, b), Course(b)},
A3 = {GradSt(a)}, A4 = {takes(a, b), GradCo(b)}, A5 = {PhDSt(a)}
Intuitively, in order to compute a (q, T )-repair, we only need to consider the
(finitely many) ABoxes in a (q, T )-testing base instead of all (infinitely many)
possible ABoxes.
Theorem 1. Let L be a DL, q a CQ, T an L-TBox, and B a (q, T )-testing base
for C L . The following property holds for each ans ∈ C L : If R is a (q, T , B)-repair
for ans, then R is also a (q, T )-repair for ans.
In our running example, clearly, ans0 only fails to compute certain answers w.r.t.
A3 and A5 . Furthermore, R0 is a (q0 , T0 , B0 )-repair for ans0 . But then, Theorem
1 ensures that R0 is also a (q0 , T0 )-repair. Thus, by simply adding R0 to T0 , we
can guarantee that ans0 will compute all certain answers, regardless of the data.
4 Computing Repairs
Theorem 1 provides a sufficient condition for the existence of a (q, T )-repair for
a well-behaved algorithm ans. To apply the theorem, however, we first need to
compute a (q, T )-testing base B and then a (q, T , B)-repair R for ans.
5
As shown in [15, 16], a (q, T )-testing base B for C L can always be computed
from a UCQ rewriting u for q and T . UCQ rewritings are guaranteed to exist
if T is expressed in the DL underpinning the OWL 2 QL profile and they may
also exist even if T is expressed in the DLs underpinning the OWL 2 EL profile;
this is often the case in many real-world ontologies. Hence, in this paper we will
restrict ourselves to TBoxes and queries for which a UCQ rewriting exists.2
Given a (q, T )-testing base B, however, the existence of a (q, T , B)-repair
may also depend on the capabilities of the algorithm under consideration. For
instance, in the case of our running example, no (q0 , T0 , B0 )-repair exists for an
algorithm that ignores the TBox and simply matches the query to the data (even
though such algorithm is well-behaved).
Our techniques for computing repairs rely on a particular form of interpo-
lation [8, 14]. We next make the connection between repairs and interpolation
precise, and describe an algorithm for computing interpolants.
4.1 Completeness Repairs and Interpolation
As already discussed, algorithm ans0 from our running example misses answers
w.r.t. A3 , A5 ∈ B0 , and R0 from (1) is a (q0 , T0 , B0 )-repair for ans0 . Furthermore,
B0 can be obtained by “instantiating” queries from the following UCQ rewriting
u = {q1 , . . . , q5 } for q0 and T0 :
q1 (x) ← Student(x), q2 (x) ← takes(x, y), Course(y),
q3 (x) ← GradSt(x), q4 (x) ← takes(x, y), GradCo(y), q5 (x) ← PhDSt(x)
In particular, A3 = {GradSt(a)} is obtained by instantiating q3 . We then say
that q3 is “relevant” to ans0 . Formal definitions of instantiation and relevance
are given next.
Definition 4. Let q be a CQ, Bq the body atoms in q, and π a mapping from
all variables of q to individuals. The following ABox is an instantiation of q:
Aqπ := {A(π(x)) | A(x) ∈ Bq } ∪ {R(π(x), π(y)) | R(x, y) ∈ Bq }
Definition 5. Let u be a UCQ rewriting for q and an L-TBox T , let ans be well-
behaved and let B be a (q, T )-testing base. We say that qi ∈ u is relevant to ans if
an instantiation Ai of qi exists s.t. Ai ∈ B and cert(q, T ∪ Ai ) 6⊆ ans(q, T ∪ Ai ).
Note also that q3 is subsumed by q0 w.r.t. T0 . We can then identify R0 as an
interpolant for the subsumption q3 ⊑T0 q0 since T0 |= R0 , q3 ⊑R0 q0 and R0
only mentions symbols occurring in either q0 or q3 .
Definition 6. Let T be an L-TBox and let q, q 0 be CQs such that q 0 ⊑T q. A
TBox = expressed in fragment L0 of L and using only symbols occurring in q or
q 0 is an L0 -interpolant for q 0 ⊑T q if T |= = and q 0 ⊑= q.
2
The notion of a testing base can be extended, and such (extended) testing bases can
be computed from Datalog rewritings. The study of such extensions is ongoing work.
6
The following theorem establishes which are the relevant interpolants for com-
puting a repair. Furthermore, if each such interpolants can be expressed in a
weak enough language, for which ans is provably complete, we can easily obtain
a repair from the union of such interpolants.
Theorem 2. Let u be a UCQ rewriting for q and an L-TBox T . Let ans ∈ C L
be an algorithm that is complete for a fragment L0 of L. Let q1 , . . . , qn be those
0
∪ for each 1 ≤ i ≤ n let =i be an L -
queries in u relevant to ans. Finally,
interpolant for qi ⊑T q. Then, = = 1≤i≤n =i is a (q, T )-repair for ans.
4.2 Computing Interpolants
Assumptions First, we restrict ourselves to TBoxes expressed in ELHI. Sys-
tems such as REQUIEM can compute a UCQ rewriting w.r.t. an ELHI-TBox,
provided that one exists [12].
Second, we observe that most state-of-the-art incomplete systems are based
on deductive database and rule technologies. Given O = T ∪ A and q as input,
the ABox A is deterministically saturated with new assertions using axioms
in T , and then q is answered directly w.r.t. the saturated ABox. Furthermore
existing systems rarely extend the input ABox with “fresh” individuals and hence
cannot handle existential quantification on the right-hand-side of TBox axioms.
In fact, many such systems are complete for DLs of the DLP family. Thus, we
will consider DLP-ELHI as our target language for computing interpolants.
In this setting, we also need to restrict the kinds of queries we are considering
to guarantee the existence of the relevant interpolants. It is rather straightfor-
ward to find ELHI-TBoxes and queries q for which a UCQ rewriting does exist,
but the DLP-ELHI interpolants required by Theorem 2 do not. For example,
let T = {A ⊑ ∃R.C} and consider the following queries
q(x) ← R(x, y), C(y) q 0 (x) ← A(x)
Clearly, {q, q 0 } is a UCQ rewriting for q and T . There is, however, no DLP-ELHI
interpolant for q 0 ⊑T q since such interpolant would need to contain existential
quantification on the right-hand-side of GCIs.
Consequently, from now onwards we focus on queries with only distinguished
variables. This restriction is not unreasonable in practice since the standard
language for querying ontologies on the Web (SPARQL) treats undistinguished
variables as if they were distinguished [4].
The Algorithm Algorithm 1 computes a UCQ rewriting u (if one exists) for an
ELHI-TBox T and a query q with no undistinguished variables. Furthermore,
for each q 0 ∈ u, it computes a DLP-ELHI interpolant for q 0 ⊑T q.
Our algorithm extends the rewriting algorithm implemented in the RE-
QUIEM system [12], which first transforms T and q into a set of clauses (Lines
1, 2 in Algorithm 1) and then uses a resolution calculus to compute u.
7
Algorithm 1 Extended Resolution-based algorithm
Algorithm: extendedUCQRewriting(q, T )
Input: T ∈ ELHI and q with no undistinguished vars.
1: T := clausify(T )
2: q := clausify(q)
3: σ(q) := ∅
4: for all α ∈ T do σ(α) := {α}
5: u := T ∪ {q}
6: repeat
7: Pick clauses C1 , C2 from u with C1 6= C2
8: C := resolve(C1 , C2 )
9: u := u ∪ {C}
10: RC := σ(C1 ) ∪ σ(C2 )
11: repeat
12: Pick clauses D1 , D2 from RC with D1 6= D2
13: RC := RC ∪ {resolve(D1 , D2 )}
14: until RC is saturated
15: σ(C) := prune(RC )
16: until u is saturated
17: (u, σ) := ff(u, σ)
18: (u, σ) := unfold(u, σ)
19: if u is not a UCQ, return failure
20: return (u, σ)
Interpolants are tracked down during resolution by means of a mapping σ
from clauses to sets of clauses. Initially, σ maps q to the empty set (since q ⊑∅ q),
and each clause from T to itself (Lines 3, 4). The rules in the resolution-based
calculus from [12] are exhaustively applied in Lines 6–16, and new clauses are
generated in Lines 7–9 exactly as in [12]. Then, for each new clause C produced as
a resolvent of C1 and C2 our algorithm computes its corresponding interpolant
σ(C). This is done by first saturating σ(C1 ) ∪ σ(C2 ) (Lines 11–14) and then
removing all clauses mentioning a symbol that is neither in C nor in q (Line
15). After u is saturated, the algorithm removes all clauses that contain function
symbols (Line 16). Then, at this point, both rewriting and interpolants are given
as sets of function-free clauses, so the procedure unfold transforms each C ∈ u
into a datalog rule and “rolls-up” σ(C) into a DLP-ELHI GCI. Finally, the
algorithm rejects the input if u is not a UCQ (e.g., a datalog program) and
returns both the UCQ rewriting and the interpolant for each query otherwise.
Lemma 1. If u computed by Algorithm 1 is a UCQ, then u is a UCQ rewriting
for q and T . Furthermore, for each q 0 ∈ u, σ(q 0 ) is a DLP-ELHI interpolant
for q 0 ⊑T q.
Algorithm 2 computes a repair by considering only those queries and ABoxes
for which ans fails. Correctness follows from Theorem 2 and Lemma 1.
Theorem 3. Algorithm 2 computes a (q, T )-repair for an algorithm ans that is
complete for DLP-ELHI.
8
Algorithm 2 Computing a Repair
Algorithm: computeRepair(ans, q, T )
Input: T , q as in Algorithm 1, ans well-behaved.
1: (u, σ) := extendedUCQRewriting(q, T )
2: B := computeTestingBase(u)
3: Repair := ∅
4: for all A ∈ B do
5: if cert(q, T ∪ A) 6⊆ ans(q, T ∪ A) then
6: q 0 := query in u that generated A
7: Repair := Repair ∪ σ(q 0 )
8: end if
9: end for
10: return Repair
If ans is not complete for DLP-ELHI (e.g., if it is an RDFS-reasoner), then the
TBox R computed by Algorithm 2 may not be a repair; however, adding R may
still have the desired effect of “mitigating” the reasoner’s incompleteness.
5 Evaluation
We have developed a prototype tool based on Algorithms 1 and 2. Our imple-
mentation uses REQUIEM [12] and the system described in [16, 15] for comput-
ing (q, T )-testing bases and relevant queries. Additionally, our tool implements
optimisations to eliminate redundancy in the computed repairs.
We have evaluated our techniques first using LUBM’s TBox and its 14 test
queries (all of which contain only distinguished variables) and then a version
of the GALEN TBox together with 4 sample queries for which a UCQ rewrit-
ing can be computed using REQUIEM. In each case, we have evaluated the
following systems: Sesame 2.3-prl,3 OWLim,4 Jena v2.6.35 and DLEJena.6 Our
experiments consisted of the following steps:
1. For each TBox T and test query q we computed a (q, T )-testing base and
measured the proportion of certain answers that each system is able to com-
pute w.r.t. the ABoxes in the (q, T )-testing base (δini ) [16].
2. For each system and each q for which it was found incomplete (i.e., δini < 1),
we computed a repair R (which might be only “partial” for some systems).
3. For each case in Step 2 we have extended T with the corresponding R,
computed a (q, T ∪ R)-testing base and obtained a new completeness degree
value δf in .
4. To evaluate the effects that adding TBox axioms had on systems’ perfor-
mance in the LUBM scenario, we used the LUBM performance evaluation
3
http://www.openrdf.org/
4
http://www.ontotext.com/owlim/
5
http://jena.sourceforge.net/
6
http://lpis.csd.auth.gr/systems/DLEJena/
9
LUBM
Sesame OWLim/Jena
Q2 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q12 Q13 Q6 Q8 Q10
♯urel 1 4 4 166 34 27 1 166 2 4 1 4 1
♯R 0 0 4 1 1 1 0 1 0 4 1 1 1
δini .75 .68 0 .003 .04 .04 0 .001 .25 .2 .99 .98 .99
δf in .75 .68 .75 .004 .05 .05 0 .002 .25 .2 1 1 1
GALEN
OWLim Jena DLEJena
Q1 Q2 Q3 Q4 Q1 Q2 Q3 Q4 Q1 Q2 Q3 Q4
♯urel 36 72 72 12 24 48 48 6 36 72 72 6
♯R 2 2 2 2 2 2 2 1 2 2 2 1
δini .84 .83 .84 .77 .94 .94 .94 .92 .84 .83 .84 .84
δf in 1 1 1 1 1 1 1 1 1 1 1 1
Table 1. Experiments for LUBM & GALEN
tool [6] and measured the loading and query answering times using the orig-
inal and the repaired TBox.
Our results for LUBM are summarised in the upper part of Table 1, where ♯urel
represents the number of relevant queries in the UCQ rewriting (see Definition
5), and ♯R the number of axioms in the computed repair. The only system not
included in the table is DLEJena, which was already complete for all queries
(w.r.t. the original TBox). OWLim and Jena were found incomplete for three
queries and Sesame for 10 of them. As shown in the table, we were able to repair
both OWLim and Jena for all queries. This was a reasonable result, since these
systems are considered to be complete for DLP-ELHI. Furthermore, all repairs
consisted of the same, unique axiom. In contrast, no query could be fully repaired
for Sesame. A slight increase in the completeness degree can be observed in 4
queries and a more significant one only in Q5. Again, this is unsurprising, since
Sesame is essentially an RDFS reasoner. No measurable performance changes
were observed for any system after repair, which suggests that completeness
can be improved (at least in this scenario) without affecting scalability. Finally,
repairs were computed in times ranging between a second and 3 minutes.
Results for GALEN are given in the lower part of the table. As shown in
the table, we were able to fully repair OWLim, Jena and DLEJena, and repairs
contained at most two axioms in each case (a relatively small number compared
to the number of queries in urel ). All repairs could be computed in less than a
minute. Finally, Sesame hasn’t been included in the table because no improve-
ment could be measured for any query.
6 Conclusions
In this paper, we have studied the problem of repairing an incomplete reasoning
systems given a query and a TBox. An important feature of our repairs is that
10
they provide data independent completeness guarantees: once an incomplete sys-
tem has been repaired, we can ensure that its output answers will be the same
as those of a complete one for the given q and T , regardless of how large and
complex the dataset is. Furthermore, our preliminary experiments suggest that
repairs can indeed be very small and their effect on systems’ performance may
even be negligible in some applications. Our results will allow application de-
signers to use highly scalable reasoning systems in their application with the
guarantee that they will behave as if they were complete, thus bringing together
“the best of both worlds”. The extension of our techniques to more expressive
DLs and a more extensive evaluation are ongoing work.
Acknowledgments Research supported by project SEALS (FP7-ICT-238975).
B. Cuenca Grau is supported by a Royal Society University Research Fellowship.
References
1. Botoeva, E., Calvanese, D., Rodriguez-Muro, M.: Expressive approximations in
DL-Lite ontologies. In: AIMSA. pp. 21–31 (2010)
2. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable
reasoning and efficient query answering in description logics: The DL-Lite family.
Journal of Automated Reasoning 39(3), 385–429 (2007)
3. G. Meditskos and N. Bassiliades: Combining a DL reasoner and a rule engine for
improving entailment-based OWL reasoning. In: Proc. ISWC. pp. 277–292 (2008)
4. Glimm, B., Krötzsch, M.: SPARQL beyond subgraph matching. In: Proc. of ISWC
2010. pp. 241–256 (2010)
5. Grosof, B.N., Horrocks, I., Volz, R., Decker, S.: Description logic programs: Com-
bining logic programs with description logic. In: Proc. of WWW. pp. 48–57 (2003)
6. Guo, Y., Pan, Z., Heflin, J.: LUBM: A Benchmark for OWL Knowledge Base
Systems. Journal of Web Semantics 3(2), 158–182 (2005)
7. Hitzler, P., Vrandecic, D.: Resolution-based approximate reasoning for OWL DL.
In: Proc. of ISWC 2005). pp. 383–397 (2005)
8. Konev, B., Walther, D., Wolter, F.: Forgetting and uniform interpolation in large-
scale description logic terminologies. In: Proc. of IJCAI 09. pp. 830–835 (2009)
9. Lutz, C., Wolter, F.: Deciding inseparability and conservative extensions in the
description logic EL. Journal of Symbolic Computation 45, 194–228 (2010)
10. Ma, L., Yang, Y., Qiu, Z., Xie, G.T., Pan, Y., Liu, S.: Towards a complete OWL
ontology benchmark. In: Proc. of ESWC 2006. pp. 125–139 (2006)
11. Pan, J.Z., Thomas, E.: Approximating OWL-DL Ontologies. In: Proc. of AAAI-07.
pp. 1434–1439 (2007)
12. Pérez-Urbina, H., Motik, B., Horrocks, I.: Tractable query answering and rewriting
under description logic constraints. Journal of Applied Logic 8(2), 186–209 (2010)
13. Poggi, A., Lembo, D., Calvanese, D., Giacomo, G.D., Lenzerini, M., Rosati, R.:
Linking data to ontologies. Journal of Data Semantics X, 133–173 (2008)
14. Seylan, I., Franconi, E., de Bruijn, J.: Effective query rewriting with ontologies
over dboxes. In: Proc. of IJCAI 09. pp. 923–925 (2009)
15. Stoilos, G., Cuenca Grau, B., Horrocks, I.: Completeness guarantees for incomplete
reasoners. In: Proc. of ISWC 2010. LNCS, Springer (2010)
16. Stoilos, G., Cuenca Grau, B., Horrocks, I.: How incomplete is your semantic web
reasoner? In: Proc. of AAAI-10. pp. 1431–1436 (2010)
11