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