=Paper=
{{Paper
|id=Vol-2663/paper-20
|storemode=property
|title=Logic-Based Ranking of Assertions in Inconsistent ABoxes
|pdfUrl=https://ceur-ws.org/Vol-2663/paper-20.pdf
|volume=Vol-2663
|authors=Horacio Tellez Perez,Jef Wijsen
|dblpUrl=https://dblp.org/rec/conf/dlog/PerezW20
}}
==Logic-Based Ranking of Assertions in Inconsistent ABoxes==
https://ceur-ws.org/Vol-2663/paper-20.pdf
Logic-Based Ranking of Assertions in
Inconsistent ABoxes
Horacio Tellez Perez and Jef Wijsen
University of Mons, Belgium
{horacio.tellezperez, jef.wijsen}@umons.ac.be
Abstract. This paper concerns the problem of inconsistency in knowl-
edge bases caused by ABox assertions. If such inconsistency occurs, users
may be asked to rate the truthfulness of one or more ABox assertions.
A potential difficulty is that users may not well understand how differ-
ent ABox assertions interact (and possibly conflict) with one another
through the TBox axioms. We therefore introduce a principled frame-
work that uses TBox axioms for inferring positive and negative support
for ABox assertions. This leads to a system of linear equations whose
solution enhances the user’s truthfulness rating by means of logical in-
formation from the TBox.
1 Motivation
Inconsistency is an important and recurrent problem in today’s database and
knowledge-base systems. Data errors are practically unavoidable in systems that
integrate data coming from different sources. Two approaches to tackle this prob-
lem are data cleaning and consistent query answering (CQA) [Wij19]. The latter
approach uses the notion of repair, which is a consistent knowledge base obtained
by making some minimal amount of data corrections. A repair is conceptually
not different from a cleaned knowledge base. However, whereas the process of
data cleaning is supposed to end in a single cleaned knowledge base, the CQA
approach allows for the possibility of multiple repairs (or possible worlds). In the
Description Logics framework, different repairs correspond to different ABoxes,
each one consistent with respect to a given fixed TBox. When we move from a
single-world perspective to a possible-worlds perspective, different semantics for
logical reasoning become possible [BR13,LLR+ 10,LB16,BBG14,GM12,CLP18].
Eventually, all these semantics address the following central problem: Given a
logical sentence ϕ, assign some degree of truthfulness to ϕ. Is ϕ true in some,
most, or all repairs? What is the probability of ϕ being true? Is there strong
support for—or resistance against—the sentence ϕ? Throughout this paper, we
use the term “truthfulness” in a loose and informal way; we could have used
other terms instead: credibility, veracity, accuracy. . .
Copyright © 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
2 H. Tellez Perez and J. Wijsen
In this paper, we present a new principled framework for evaluating the rel-
ative truthfulness of ABox assertions (i.e., the sentence ϕ is an ABox assertion
in our framework). By relative, we mean that we are merely interested in rank-
ing ABox assertions: Given two ABox assertions α and β, is α more, less, or
equally truthful than β? Our framework is different from CQA in that it does
not use the notion of repair. The framework assumes that there is some ini-
tial weight function over the ABox assertions, called credibility function, which
models the opinion of domain experts concerning the truthfulness of assertions.
In their assessments, however, experts may have difficulties to fully understand
and take into account the logic that is expressed by, possibly extensive, TBoxes.
To overcome this difficulty, we propose an automated mathematical method for
adjusting the experts’ initial credibility function by taking into account the onto-
logical logic of the TBox: strong logical support for an assertion α should increase
its credibility, while strong logical support for ¬α should decrease α’s credibil-
ity. Eventually, our method results in a ranking of ABox assertions in terms of
truthfulness, taking into account both the experts’ credibility function and the
TBox logic. In our framework, we assume that the TBox has been validated by
a multitude of experts and is therefore error-free.
This paper is organized as follows. Section 2 presents a guiding example.
Section 3 discusses related work. Section 4 introduces our general theoretical
framework, and Section 5 presents a particular instantiation of this framework.
Section 6 studies in more detail some theoretical questions and computational
tasks raised by this instantiation. Finally, Section 7 concludes the paper.
2 Motivating Example
Consider the following knowledge base K0 = hT0 , A0 i.
Professor v Person,
John : Professor
Student v Person,
Ava : Student
Person v ¬Course,
DB2 : Course
Student v ¬Professor,
KR : Course
T0 = A0 =
∃teaches v Professor,
(John, DB2) : teaches
∃attends v Student,
(John, KR) : attends
−
∃teaches v Course, (Ava, IA) : attends
−
∃attends v Course (Bob, KR) : attends
This knowledge base is inconsistent, because from (John, KR) : attends, we
can infer John : Student by means of the axiom ∃attends v Student. Then, by
means of the axiom Student v ¬Professor, we can infer John : ¬Professor, which
obviously contradicts the first assertion in A0 . In conclusion, (John, KR) : attends
and John : Professor contradict one another. The vertices in the directed graph
of Fig. 1 are the assertions of A0 . A red-colored edge from α to β means that α
refutes β. On the other hand, a green-colored edge from α to β means that α
supports β. For example, from (John, DB2) : teaches we can infer John : Professor
Logic-Based Ranking of Assertions in Inconsistent ABoxes 3
by means of the axiom ∃teaches v Professor. Therefore, (John, DB2) : teaches
supports John : Professor. In this example, we assumed that domain experts
esteemed that assertions in the ABox were equally credible, represented by a
value of 1. Then, our proposed method updates values by balancing the value
of each assertion α with respect to the values of α’s refuters and supporters.
Refuters and supporters of α, respectively, lower and increase α’s value by an
amount that is proportional to their own value. In Fig. 1, we see that John :
Professor is attributed a higher value than (John, KR) : attends because it has
more supporters and less refuters.
+
Fig. 1. ABox assessment obtained by a practical application of our framework.
Figure 2 shows the effect of adding Ava : Professor to A0 . One can observe
that the values of the assertions (Ava, IA) : attends and Ava : Student have gone
down because of conflicts with the new assertion.
Since supporters and refuters are single assertions in this simple example,
they can be represented in a directed graph. In our general framework, however,
supporters and refuters will be sets of assertions. For example, if A u B v ¬C
is a TBox assertion, then the set {(i, A), (i, B)} is a refuter of (i, C), but neither
(i, A) nor (i, B) is a refuter on its own.
3 Related Work
In Description Logics, different repairs correspond to different ABoxes, each
one consistent with respect to a given fixed TBox. When we move from a sin-
gle ABox to a set of possible ABoxes, different semantics for logical reasoning
4 H. Tellez Perez and J. Wijsen
Fig. 2. New ABox assessment after adding Ava : Professor.
become possible, including brave semantics [BR13], ABox Repair (AR) and In-
tersection ABox Repair (IAR) semantics [LLR+ 10]. These semantics can be en-
riched by taking into account notions of cardinality [LB16], preference [BBG14],
or probability [GM12,CLP18]. Some works [DQ15,TBB+ 17] in the Description
Logics community have already investigated the problems of finding the best
repairs according to some criteria, and of extracting consistent information that
best complies with specific needs. Sik Chun Lam et al. have proposed logic-based
methods for repairing TBox axioms of unsatisfiable ontologies [LPSV06a], as well
as numerical methods for rewriting and ranking problematic axioms [LPSV06b].
Ranking the nodes of some sort of knowledge graph in terms of interest,
quality, or preference is a recurrent problem in many disciplines. Solving these
problems requires to somehow quantify the nodes and their interactions. A quan-
titative approach, rather than a qualitative one, has been used in argumentation
frameworks [AB13,BDKM16,BCPR12,Rad18,HT17], belief revision [SSF16], the
Web [Kle99,PBMW99], and social networks [dKD08,TND10].
4 Theoretical Framework
Throughout this paper, we will assume that TBoxes are satisfiable. That is,
for every TBox T , the knowledge base hT , ∅i is consistent. If a knowledge base
hT , Ai is inconsistent, we will assume that the inconsistency is caused by one
or more assertions in A. When humans are faced with such an inconsistent
knowledge base hT , Ai, they may not be able to quickly pinpoint the “wrong”
assertion(s) in A, because the inconsistency may only become apparent after an
involved reasoning process that uses many axioms and assertions. We present
Logic-Based Ranking of Assertions in Inconsistent ABoxes 5
a method for ranking assertions such that higher-ranked assertions are more
“truthful” than lower-ranked assertions. Significantly, the ranking only requires
some superficial input from the user, who is modeled by the notion of a credibility
function, which is a mapping from A to R. Such a credibility function will be
combined with TBox assertions to result in the desired ranking. All definitions
that follow are relative to a fixed knowledge base hT , Ai in some fixed Description
Logic.
Refuters and supporters
We define what it means for a set B of assertions to support or refute an assertion
α not in B. In our framework, assertions will be higher ranked if they have strong
supporters and no strong refuters.
Definition 1. The following definitions are relative to a knowledge base hT , Ai,
and an assertion α ∈ A.
A refuter of α is an inclusion-minimal subset B of A with the property that
hT , Bi is consistent and hT , B ∪ {α}i is inconsistent.
A supporter of α is an inclusion-minimal subset B of A with the property
that hT , Bi is consistent, α 6∈ B, and hT , Bi |= α.
Example 1. Let T = {A v C, A v ¬D}. Let A = {a : A, a : D, a : C}. Then,
– {a : A} is a refuter of a : D, and a supporter of a : C.
– {a : C} is neither a refuter nor a supporter of a : A.
Proposition 1. Let hT , Ai be a knowledge base in a monotonic Description
Logic, and let α ∈ A. Then,
1. distinct refuters of α are not comparable by set inclusion;
2. distinct supporters of α are not comparable by set inclusion; and
3. if B is a refuter of α and B 0 is a supporter of α, then B and B 0 are not
comparable by set inclusion.
Proof. The proof of the first two items is straightforward. We next prove the
last item. Assume B is a refuter of α, and B 0 is a supporter of α. Consequently,
(a) hT , Bi is consistent;
(b) hT , B ∪ {α}i is inconsistent;
(c) hT , B 0 i is consistent; and
(d) hT , B 0 i |= α.
From (c) and (d), it follows hT , B 0 ∪ {α}i is consistent.
We first show B * B 0 . Assume for a contradiction that B ⊆ B 0 , hence
B∪{α} ⊆ B 0 ∪{α}. From (b) and our assumption that the underlying Description
Logic is monotonic, it follows that hT , B 0 ∪ {α}i is inconsistent, a contradiction.
Finally, we show B 0 * B. Assume for a contradiction B 0 ⊆ B. From (d) and
our assumption that the underlying Description Logic is monotonic, it follows
hT , Bi |= α. By (a), it follows hT , B ∪ {α}i is consistent, which contradicts (b).
t
u
From here on, we will assume that all Description Logics considered are
monotonic.
6 H. Tellez Perez and J. Wijsen
Aggregated credibility
As explained in the beginning of Section 4, we assume a credibility function
mapping every assertion α in A to a real number that can be thought of as the
truthfulness associated by an expert to the assertion α.
We will assume that the credibility function induces a function f from 2A to
R by means of some aggregation operator ⊕. Examples of ⊕ are min, max, avg,
sum. In the theoretical development, we will abstract away from the aggregation
operator ⊕ and treat f as a basic construct. To keep our framework flexible
and general, we do not impose any restrictions on the choice of the credibility
function, which can be instantiated and adapted later on to fit a particular
setting, for example, as a probability distribution.
ABox assessment
An ABox assessment for an ABox A is a total function ν : A → R. Informally,
our goal is to define ν such that if two ABox assertions are logically conflicting,
then the assertion with the higher ν-value is preferred.
Although credibility functions and ABox assessments are both mappings from
A to R, it is important to understand that they are conceptually distinct. In par-
ticular, ABox assessments improve credibility functions by taking into account
the axioms of the TBox, via the notions of refuter and supporter defined previ-
ously.
Informally, we want that for every α ∈ A, its value under ν is greater if α has
strong supporters, and smaller if α has strong refuters. Here, the strength of a
supporter or refuter is recursively determined by the aggregated ν-values of its
elements. This can be expressed as follows, where ∼ denotes some proportionality
that will be made explicit later on:
X X X X
ν(α) ∼ f (B) ∗ ν(β) − f (B) ∗ ν(β) . (1)
β∈B β∈B
B is a B is a
supporter refuter
of α of α
The expression at the righthand of ∼ will be abbreviated Σ ± (α). Informally,
Σ ± (α) sums over all supporters and refuters of α. The formulas for supporters
and refuters are signed positively and negatively respectively. The magnitude
of each supporter’s or refuter’s contribution is proportional to its aggregated
credibility and ABox assessment values. It is significant that (1) is recursive, in
the sense that ν appears at both the lefthand and righthand of ∼.
To shorten notations, we define mappings T : A → 2A and F : A → 2A , as
follows:
T (α) := {B ⊆ A | B is a supporter of α};
F (α) := {B ⊆ A | B is a refuter of α}.
Informally, one can think of T and F as True and False respectively. B ∈ T (α)
is shorthand for “B is a supporter of α,” and B ∈ F (α) is shorthand for “B is
Logic-Based Ranking of Assertions in Inconsistent ABoxes 7
a refuter of α”. Obviously, the complexity of computing T and F will depend
on the underlying Description Logic.
To have a more compact form for Σ ± (α), we define an indicator function I
from {T, F } × 2A × A × A to {0, 1}:
1 if β ∈ B and B ∈ L(α)
I(L, B, α, β) = (2)
0 otherwise
Thus, I(T, B, α, β) is one if B is a supporter of α that contains β, and is zero
otherwise. Likewise, I(F, B, α, β) is one if B is a refuter of α that contains β,
and is zero otherwise. Note incidentally that α = β implies I(L, B, α, β) = 0,
because α does not belong to a supporter or a refuter of itself. Then, for α ∈ A,
X X
Σ ± (α) = ν(β) ∗ f (B) ∗ (I(T, B, α, β) − I(F, B, α, β)) . (3)
β∈A B⊆A
Ranking of ABox assertions
An ABox assessment ν induces a ranking of an ABox, as follows: α is ranked
higher than β if ν(α) > ν(β); and α is ranked equal to β if ν(α) = ν(β). Two
•
ABox assessments ν1 and ν2 are rank-equivalent, denoted ν1 ∼ ν2 , if they rank
assertions in the same way, that is, if for all α, β ∈ A, ν1 (α) > ν1 (β) if and
•
only if ν2 (α) > ν2 (β). It is easily verified that if ν1 ∼ ν2 , then ν1 (α) = ν1 (β)
•
implies ν2 (α) = ν2 (β). Obviously, ∼ is an equivalence relation on the set of
all ABox assessments. In our study, we will be primarily interested in the set
•
of ABox assessments modulo ∼. That is, we are not so much interested in the
real numbers in the range of two different ABox assessments, but rather in their
induced rankings.
5 Framework Instantiation
We will assume A = {α1 , . . . , αN }. In this section, we elaborate an instantiation
of the framework in Section 4. With the previous abbreviations, Eq. (1) reads as
ν(αi ) ∼ Σ ± (αi ). We will instantiate ∼ as a linear proportionality, i.e., for some
numbers a, b, c with a 6= 0:
±
a ∗ ν(α1 ) = b ∗ Σ ± (α1 ) + c
a ∗ ν(α2 ) = b ∗ Σ (α2 ) + c
.. (4)
.
a ∗ ν(αN ) = b ∗ Σ ± (αN ) + c
A more natural formulation may introduce only two numbers d, e and impose
ν(αi ) = d ∗ Σ ± (αi ) + e for 1 ≤ i ≤ N . This is tantamount to fixing a = 1. The
choice for using three numbers was made for reasons of flexibility, but is not
fundamental.
8 H. Tellez Perez and J. Wijsen
Since we think of (1) as a positive proportionality, we require that a and b
have the same sign, say both positive. Let Af be the square N × N matrix such
that for 1 ≤ i, j ≤ N ,
Afi,j :=
X
f (B) ∗ (I(T, B, αi , αj ) − I(F, B, αi , αj )) . (5)
B⊆A
It is easily verified that for every i ∈ {1, . . . , N }, Afi,i = 0.
For i ∈ {1, . . . , N }, we
| introduce a variable xi for the unknown ν(αi ). We
define X = x1 x2 · · · xN . Then, using (3), the system of equations (4) can be
equivalently written as follows:
|
a · 1 − b · Af · X = c · · · c ,
(6)
where 1 is the square identity matrix. Equation (6) has a unique solution if and
only if the matrix a · 1 − b · Af (which does not depend on c) is non-singular (i.e.,
is invertible). In that case, the solution ABox assessment is given by:
−1 |
X = a · 1 − b · Af · c c ··· c (7)
We should pick c 6= 0 to avoid the all-zero solution. Indeed, if a · 1 − b · Af
is non-singular and c = 0, then the solution to (7) yields the ABox assessment
ν such that ν(α1 ) = ν(α2 ) = · · · = ν(αN ) = 0, which obviously is of no interest
for ranking ABox assertions.
Then, it is easily verified that for fixed values of a and b, different choices for
c lead to rank-equivalent solutions. Therefore, we can choose c = 1 without loss
of generality, in which case in the solution, xi is the sum of all elements in the
−1
ith row of a · 1 − b · Af . Two significant questions remain:
1. For which values of a and b is the square matrix a · 1 − b · Af non-singular,
such that (7) gives us a unique ABox assessment? Obviously, a · 1 − b · Af
is invertible if and only if 1 − ab · Af is invertible. Therefore, only the ratio
between a and b matters in our subsequent analysis.
2. Are ABox assessments obtained for different values of a, b rank-equivalent?
Graph-theoretical view
From a graph-theoretical viewpoint, Af can be interpreted as an edge-weighted
directed graph whose vertices are the assertions of the ABox. This view is used in
Figures 1 and 2. An edge from αj to αi (i 6= j) has weight Afi,j . The task is then
to assign a real number to each vertex such that the resulting graph satisfies the
sort of equilibrium expressed by (4). The ratio between a and b determines how
strongly a vertex is impacted (supported or refuted) by its incoming edges. The
question arising is whether an equilibrium (4) can be attained for some values of
a, b. It is equally important to examine the robustness of such an equilibrium (if
it exists) with respect to rank-equivalence. Ideally, different ABox assessments
obtained by small parameter changes should be close modulo rank-equivalence.
Logic-Based Ranking of Assertions in Inconsistent ABoxes 9
6 Solving the Instantiated Framework
In Section 5, we presented the matrix equation (6) whose unique solution, if it
exists, yields an ABox assessment. This matrix equation has parameters a, b. A
remaining problem is how to pick appropriate values for these parameters. One
solution could be to choose values for a, b in an empirical fashion, relying, for
instance, on information obtained from some learning experience. Although we
have conducted some experiments (cf. Figures 1 and 2), a thorough empirical or
experimental validation is left for future research. Instead, we will focus more on
theoretical aspects in the current paper. In Section 6.1, we will show a parame-
terization scheme for a, b that guarantees the existence of a solution for (6): pick
a b > 0. What is probably more important is that when the ratio a/b grows,
the ABox assessments obtained for different a, b become all rank-equivalent. In-
formally, the parameterization scheme converges to a unique ABox assessment
modulo rank-equivalence.
6.1 Solution Existence
Note that all diagonal elements in a · 1 − b · Af are equal to a. The invertibility of
a · 1 − b · Af can be guaranteed by (some form of) diagonal dominance, a concept
that is easily grasped and has turned out to be useful in applications [Var76].
An example is the Levy-Desplanques theorem recalled next.
Theorem 1 (Levy-Desplanques). A square N × N matrix A is invertible if
PN
for every i ∈ {1, . . . , N }, |aii | > j=1 |aij |.
j6=i
From Theorem 1, it immediately follows that (7) has a unique solution if for
all i ∈ {1, . . . , N }, we have |a| > |b|∗ j=1 Afi,j . This is illustrated by Example 2.
PN
Example 2. Assume four assertions α1 , α2 , α3 , α4 such that α1 and α2 support
one another, while α3 and α4 refute one another. Take b = 1. If we assume
f ({αi }) = 1 for 1 ≤ i ≤ 4, we obtain:
01 0 0
1 0 0 0
Af =
0 0 0 −1 .
0 0 −1 0
Then,
a −1 0 0
−1 a 0 0
a · 1 − b · Af =
0 0 a 1 .
0 0 1a
10 H. Tellez Perez and J. Wijsen
It follows from Theorem 1 that this matrix is invertible for a > 1, giving the
following solution: 1
a−1
1
X= a−1
1 .
a+1
1
a+1
Although distinct values for a lead to different ABox assessments, it is significant
1 1
to observe that a−1 > a+1 (a > 1), and therefore all these ABox assessments
ν are rank-equivalent: ν(α1 ) = ν(α2 ) > ν(α3 ) = ν(α4 ). It is intuitively correct
that the two assertions that mutually attack one another loose credibility. t
u
The invertibility of a · 1 − b · Af may also follow from Banach’s Lemma, which
is recalled next.
Theorem 2 (Banach’s Lemma). Let M be a square matrix with the property
that kM k < 1 for some operator norm k·k. Then the matrix 1 − M is invertible
and (1 − M ) = 1 + M + M 2 + M 3 + · · · .
−1
Therefore, if we fix a = 1 and pick b sufficiently small (which is analogous
to fixing b = 1 and picking a sufficiently large), then the matrix 1 − b · Af is
−1
invertible, and 1 − b · Af = 1 + Af + · · · . If we limit ourselves to the two
|
most significant terms in this expansion, we get X = 1 + Af · 1 1 · · · 1 as an
approximate solution for (7). The ranking obtained by this solution is intuitively
meaningful, because it ranks αi based on the sum of the elements in the ith row
of Af ; in this row, supporters have a positive sign, and refuters a negative sign.
6.2 Convergence Towards a Fixed Ranking
So it turns out that (6) has a unique solution with a, b ≥ 0 whenever the ratio
a/b is sufficiently large. A desirable property is that different solutions be rank-
equivalent, as was the case in Example 2. We now show that this property indeed
holds true beyond some threshold value for a/b.
The notion of rank-equivalence obviously extends to any two vectors of real
numbers: two such vectors A, B of the same length N are rank-equivalent if for
all 1 ≤ i, j ≤ N , ai < aj if and only if bi < bj . The proof of the following
theorem is in Appendix A. Since, as argued before, only the ratio between a
and b matters in our analysis, we can fix b and let a increase in the following
theorem.
Theorem 3 (Convergence). Let M be an N × N matrix whose diagonal el-
ements are zero. Let b, c ∈ R. Consider the following equation with real-number
parameter a: |
(a ∗ 1 − b ∗ M ) · X = c · · · c .
(8)
Then there exists a∗ ∈ R such that
– for every a ≥ a∗ , the equation (8) has a unique solution; and
Logic-Based Ranking of Assertions in Inconsistent ABoxes 11
– for all a1 , a2 ≥ a∗ , if X1 and X2 are solutions to (8) for parameters a1 and
a2 respectively, then X1 and X2 are rank-equivalent.
Moreover, such a bound a∗ can be computed in polynomial time in the size of N .
Informally, Theorem 3 tells us that for all choices of b and c, there is a
threshold value a∗ such that all choices of a satisfying a ≥ a∗ lead to the same
ABox assessment modulo rank-equivalence.
6.3 Computational Complexity
We discuss the computational complexity of solving (6). The main difficulty is
the computation of the non-diagonal elements in Af , which are defined by (5).
Given αi and βj , this requires finding every B ⊆ A such that βj ∈ B and B
is a supporter or refuter of αi . In general, the number of supporters or refuters
can be exponential in the size of A, because an ABox of size 2N can have 2N N
supporters or refuters not comparable by set inclusion. However, in practice, a
fixed upper bound on the size of supporters or refuters may be implied by the
TBox, in a way captured by the following definition.
Definition 2. We say that a TBox T is conflict-bounded if there exists a
polynomial-time computable positive integer m such that for every knowledge-
base hA, T i and α ∈ A, if B is a refuter or supporter of α, then |B| ≤ m.
Conflict-boundedness arises in practice. For example, for every DL-Lite TBox,
every supporter or refuter has cardinality ≤ 1 because each conflict in DL-Lite in-
volves at most two assertions. Conflict-boundedness is also guaranteed in EL⊥nr
(EL⊥ with non-recursive empty concepts) defined in [Ros11].
Theorem 4. Let T be a conflict-bounded TBox such that ABox consistency
with respect to T can be checked in polynomial time. Then, for every ABox A,
the matrix Af can be computed in polynomial time (in the size of A) if f is
polynomial-time computable.
Proof. Let N := |A|. Recall that Af is an N × N matrix given by (5). Since
T is conflict-bounded, say with bound m, for every B ⊆ A, if |B| > m,
then I(T, B, αi , αj ) = I(F, B, αi , αj ) = 0. Therefore, the sum in (5) must only
consider subsets B ⊆ A with |B| ≤ m, which are polynomially many and
polynomial-time computable. Furthermore, since ABox consistency checking is
in polynomial time by the hypothesis of the theorem, it can be tested in poly-
nomial time whether any such B containing αj is a supporter or a refuter of
αi (or neither of both). The computation of f (B) is also in polynomial time by
the hypothesis of the theorem. It is now obvious that any entry of Af can be
computed in polynomial time. t
u
An inspection of the preceding proof reveals that Theorem 4 remains valid if,
throughout its statement, we replace polynomial time by some higher complexity
upper bound (e.g., polynomial space or exponential time).
12 H. Tellez Perez and J. Wijsen
7 Summary and Future Work
In this work, we have proposed a novel framework to rank the assertions of an
inconsistent ABox in terms of their degree of truthfulness. This ranking takes
into account an expert’s credibility function as well as the logical axioms of the
TBox. The theoretical framework can work with any Description Logic, but to
gain computational tractability, restrictions have to be imposed.
The framework is implementable using existing libraries for matrix operations
and description logics. In the future, we aim to extend our prototype in order to
empirically evaluate our theory.
A next step is to use our framework for repairing database and knowledge-
base systems. Our ranking of ABox assertions can be extended in several ways
to a ranking of repairs, using some notion of Pareto optimality. For example, if
two facts α and β contradict one another and α is ranked higher than β, then a
repair containing α is preferred over a repair containing β (all other facts being
equal). This brings us in the realm of prioritized database repairing [Wij19],
which we see as a promising way to enrich existing DL repair semantics (like
IAR and AR). By narrowing the search space of possible repairs, we may also
hope to gain efficiency compared to existing repair semantics.
Acknowledgments We thank the anonymous reviewers for their helpful com-
ments.
References
[AB13] Leila Amgoud and Jonathan Ben-Naim. Ranking-based semantics for ar-
gumentation frameworks. In Weiru Liu, V. S. Subrahmanian, and Jef Wi-
jsen, editors, Scalable Uncertainty Management - 7th International Confer-
ence, SUM 2013, Washington, DC, USA, September 16-18, 2013. Proceed-
ings, volume 8078 of Lecture Notes in Computer Science, pages 134–147.
Springer, 2013.
[BBG14] Meghyn Bienvenu, Camille Bourgaux, and François Goasdoué. Querying
inconsistent description logic knowledge bases under preferred repair se-
mantics. In Carla E. Brodley and Peter Stone, editors, Proceedings of the
Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31,
2014, Québec City, Québec, Canada, pages 996–1002. AAAI Press, 2014.
[BCPR12] Richard Booth, Martin Caminada, Mikolaj Podlaszewski, and Iyad Rah-
wan. Quantifying disagreement in argument-based reasoning. In Wiebe
van der Hoek, Lin Padgham, Vincent Conitzer, and Michael Winikoff, edi-
tors, International Conference on Autonomous Agents and Multiagent Sys-
tems, AAMAS 2012, Valencia, Spain, June 4-8, 2012 (3 Volumes), pages
493–500. IFAAMAS, 2012.
[BDKM16] Elise Bonzon, Jérôme Delobelle, Sébastien Konieczny, and Nicolas Maudet.
A comparative study of ranking-based semantics for abstract argumenta-
tion. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of
the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17,
2016, Phoenix, Arizona, USA, pages 914–920. AAAI Press, 2016.
Logic-Based Ranking of Assertions in Inconsistent ABoxes 13
[BR13] Meghyn Bienvenu and Riccardo Rosati. Tractable approximations of con-
sistent query answering for robust ontology-based data access. In Francesca
Rossi, editor, IJCAI 2013, Proceedings of the 23rd International Joint Con-
ference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages
775–781. IJCAI/AAAI, 2013.
[CLP18] Marco Calautti, Leonid Libkin, and Andreas Pieris. An operational ap-
proach to consistent query answering. In Jan Van den Bussche and Marcelo
Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI
Symposium on Principles of Database Systems, Houston, TX, USA, June
10-15, 2018, pages 239–251. ACM, 2018.
[dKD08] Cristobald de Kerchove and Paul Van Dooren. The pagetrust algorithm:
How to rank web pages when negative links are allowed? In Proceedings
of the SIAM International Conference on Data Mining, SDM 2008, April
24-26, 2008, Atlanta, Georgia, USA, pages 346–352. SIAM, 2008.
[DQ15] Jianfeng Du and Guilin Qi. Tractable computation of representative ABox
repairs in description logic ontologies. In Songmao Zhang, Martin Wirsing,
and Zili Zhang, editors, Knowledge Science, Engineering and Management -
8th International Conference, KSEM 2015, Chongqing, China, October 28-
30, 2015, Proceedings, volume 9403 of Lecture Notes in Computer Science,
pages 28–39. Springer, 2015.
[GM12] Sergio Greco and Cristian Molinaro. Probabilistic query answering over
inconsistent databases. Ann. Math. Artif. Intell., 64(2-3):185–207, 2012.
[HT17] Anthony Hunter and Matthias Thimm. Probabilistic reasoning with ab-
stract argumentation frameworks. J. Artif. Intell. Res., 59:565–611, 2017.
[Kle99] Jon M. Kleinberg. Authoritative sources in a hyperlinked environment. J.
ACM, 46(5):604–632, 1999.
[LB16] Andrei Lopatenko and Leopoldo E. Bertossi. Complexity of consistent
query answering in databases under cardinality-based and incremental re-
pair semantics (extended version). CoRR, abs/1605.07159, 2016.
[LLR+ 10] Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and
Domenico Fabio Savo. Inconsistency-tolerant semantics for description
logics. In Pascal Hitzler and Thomas Lukasiewicz, editors, Web Reason-
ing and Rule Systems - Fourth International Conference, RR 2010, Bres-
sanone/Brixen, Italy, September 22-24, 2010. Proceedings, volume 6333 of
Lecture Notes in Computer Science, pages 103–117. Springer, 2010.
[LPSV06a] Sik Chun Lam, Jeff Z. Pan, Derek H. Sleeman, and Wamberto Weber
Vasconcelos. A fine-grained approach to resolving unsatisfiable ontologies.
In 2006 IEEE / WIC / ACM International Conference on Web Intelligence
(WI 2006), 18-22 December 2006, Hong Kong, China, pages 428–434. IEEE
Computer Society, 2006.
[LPSV06b] Sik Chun Lam, Jeff Z. Pan, Derek H. Sleeman, and Wamberto Weber Vas-
concelos. Ontology inconsistency handling : Ranking and rewriting axioms.
Technical report, University of Aberdeen, 2006.
[PBMW99] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The
pagerank citation ranking: Bringing order to the web. Technical Report
1999-66, Stanford InfoLab, November 1999. Previous number = SIDL-WP-
1999-0120.
[Rad18] Badran Raddaoui. On the measure of conflicts: an argumentation-based
framework. J. Appl. Non Class. Logics, 28(2-3):240–259, 2018.
14 H. Tellez Perez and J. Wijsen
[Ros11] Riccardo Rosati. On the complexity of dealing with inconsistency in
description logic ontologies. In Toby Walsh, editor, IJCAI 2011, Pro-
ceedings of the 22nd International Joint Conference on Artificial Intelli-
gence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 1057–1062.
IJCAI/AAAI, 2011.
[SSF16] Gerardo I. Simari, Paulo Shakarian, and Marcelo A. Falappa. A quantita-
tive approach to belief revision in structured probabilistic argumentation.
Ann. Math. Artif. Intell., 76(3-4):375–408, 2016.
[TBB+ 17] Abdelmoutia Telli, Salem Benferhat, Mustapha Bourahla, Zied Bouraoui,
and Karim Tabia. Polynomial algorithms for computing a single preferred
assertional-based repair. Künstliche Intell., 31(1):15–30, 2017.
[TND10] Vincent A. Traag, Yurii E. Nesterov, and Paul Van Dooren. Exponen-
tial ranking: Taking into account negative links. In Leonard Bolc, Marek
Makowski, and Adam Wierzbicki, editors, Social Informatics - Second In-
ternational Conference, SocInfo 2010, Laxenburg, Austria, October 27-29,
2010. Proceedings, volume 6430 of Lecture Notes in Computer Science,
pages 192–202. Springer, 2010.
[Var76] Richard S. Varga. On recurring theorems on diagonal dominance. Linear
Algebra and its Applications, 13(1):1 – 9, 1976.
[Wij19] Jef Wijsen. Foundations of query answering on inconsistent databases.
SIGMOD Rec., 48(3):6–16, 2019.
A Proof of Theorem 3
Proof (of Theorem 3). Clearly, if xc is the solution to
|
(a ∗ 1 − b ∗ M ) · X = c ∗ 1 1 · · · 1
with c > 0, and x1 is the solution to
|
(a ∗ 1 − b ∗ M ) · X = 1 1 · · · 1 ,
then xc = c ∗ x1 . Since xc and x1 are rank-equivalent, we can fix c = 1 without
loss of generality. Define a0 as follows:
a0 := 1 + |b| ∗ (N − 1) max |Mij | .
1≤i,j≤N
By the Levy-Desplanques theorem, for every a ≥ a0 , the matrix a ∗ 1 − b ∗ M is
invertible. For every a ≥ a0 , we write xa for the unique solution of the equation
|
(a ∗ 1 − b ∗ M ) · X = 1 1 · · · 1 .
For a ≥ a0 , define δij (a) := xai − xaj , where xai is the ith coordinate of xa .
We will show that there is a value a∗ ≥ a0 such that for all a1 , a2 ≥ a∗ , for
all 1 ≤ i < j ≤ N , δij (a1 ) and δij (a2 ) have the same sign, which implies that
xa1 and xa2 are rank-equivalent.
Logic-Based Ranking of Assertions in Inconsistent ABoxes 15
Define the following matrix S|i in function of a, for 1 ≤ i ≤ N :
(
(a ∗ 1 − b ∗ M )`k if k 6= i
(S|i (a))`k = (9)
1 if k = i
That is, S|i is obtained from a ∗ 1 − b ∗ M by replacing the ith column with
|
1 1 · · · 1 . By Cramer’s Rule, we have
a det S|i (a)
xi = , (10)
det (a ∗ 1 − b ∗ M )
and consequently
det S|i (a) − det S|j (a)
δij (a) = . (11)
det (a ∗ 1 − b ∗ M )
Since the determinants det (·) are polynomial expressions, the following are all
polynomials of degree at most N :
– pi (a) = det S|i (a) ;
– pj (a) = det S|j (a) ; and
– p(a) = det (a ∗ 1 − b ∗ M ).
If a ≥ a0 , then since the polynomial p(a) does not vanish, the sign of δij (a) is
fully determined by the expression
det S|i (a) − det S|j (a) . (12)
Let pij = pi − pj for 1 ≤ i < j ≤ N . We determine a∗ such that for all a ≥ a∗
and for all 1 ≤ i < j ≤ N , the sign of pij (a) does not change (i.e., is either
always positive or always negative). Note that the sign of pij not changing is
equivalent to the sign of pji not changing, so we can assume i < j without loss
of generality.
In the remainder of the proof, we show that the desired a∗ exists and can be
computed in polynomial time in N . Pick N +1 real numbers V = {a1 , . . . , aN +1 },
all greater than a0 . Compute
pij (ak ) = det S|i (ak ) − det S|j (ak ) (13)
for all ak ∈ V and 1 ≤ i < j ≤ N . The set
{pij (ak ) | 1 ≤ i < j ≤ N, 1 ≤ k ≤ N + 1}
can be computed in polynomial
time in N , because it involves N (N + 1) deter-
minants (i.e., det S|i (ak ) for 1 ≤ i ≤ N and 1 ≤ k ≤ N + 1), each of which can
be computed in polynomial time in N . For all 1 ≤ i < j ≤ N , the polynomial
pij can be computed from {(a1 , pij (a1 )), . . . , (aN +1 , pij (aN +1 ))} in polynomial
time using, for example, Lagrange interpolation. The number of polynomials to
compute is N (N2−1) (i.e., polynomially many), and each of them has at most
16 H. Tellez Perez and J. Wijsen
N coefficients. We will represent the polynomial pij by its coefficients, i.e., by
h(pij )0 , . . . , (pij )nij i where each (pij )` is the coefficient of degree `, and nij ≤ N
is the polynomial’s degree. We now define a∗ij as
−(pij )`
a∗ij := max a0 , 2 + max .
0≤`≤nij −1 |(pij )nij |
By Cauchy’s bound on positive real roots of polynomials, if x0 is a root of pij ,
then x0 < a∗ij . This implies that if a1 , a2 > a∗ij , then pij (a1 ) and pij (a2 ) have
the same sign (i.e., either both positive or both negative), and therefore, by
definition of δij , we have xai 1 < xaj 1 if and only if xai 2 < xaj 2 . Finally, let
a∗ = max a∗ij ,
1≤i a∗ , the solutions xa1 , xa2 exist and are rank-equivalent.
Finally, we incidentally note that a slightly better bound is obtained by
letting
∗ 0 −(pij )`
a = max a , 2 + max . (14)
1≤i