Although there has been an extensive body of work on handling inconsistency in databases, little work has been done on measuring inconsistency. In this paper, we present inconsistency measures (IMs) for databases with denial constraints. Our database IMs are inspired by well-established methods to quantify inconsistency in propositional knowledge bases, but are tailored to the relational database context where data are generally the reason for inconsistency, not the integrity constraints. We investigate the complexity of some problems related to measuring inconsistency and briefly discuss other ideas concerning IMs.
There is a growing number of applications where inconsistent information arises, often because
data are obtained from multiple sources. This has led to an extensive body of work on handling
inconsistent data, and in particular inconsistent databases. Approaches for dealing with
inconsistent databases include consistent query answering frameworks [
Measuring the amount of inconsistency in a database can help in understanding the primary sources of conflicts as well as devising ways to deal with them. For instance, inconsistency measurement has recently been explored in [17] to quantify and understand inconsistency in bank holding company data w.r.t. four consistency rules (i.e., integrity constraints) specifically asserted for the considered domain. In general, quantifying and monitoring the amount of inconsistency helps to get information on the health status of data, whose quality is more and more important nowadays. Furthermore, measuring inconsistency makes it possible to compare the amount of inconsistency between various chunks of information. Indeed, inconsistency measures (IMs for short) are important for inconsistency-tolerant integrity checking [18], where one wants to accept an update only if the measure of inconsistency of the old state does not increase in the new state.
Although the idea of measuring inconsistency was introduced more than 40 years ago, in [19], at that time it did not seem to be an important issue. The problem became more noticeable in the 1990s when it became possible to store large amounts of information. It was only in the early 2000s when several AI researchers started to investigate this issue systematically [16]. The bulk of this work since then has been for propositional knowledge bases, that is, where the information is presented as a set of formulas in propositional logic. In the last couple of years the work has been extended to other frameworks. [14] surveys what has been done so far and gives some extensions.
There are few works addressing the problem of measuring inconsistency in relational databases. [20] first developed single-dependency axioms for dirtiness functions quantifying inconsistency w.r.t. one functional dependency (FD)—a simple type of denial constraint—considered in isolation, and proposed an IM that satisfies these axioms. Then a single axiom for dirtiness functions that can handle multiple FDs was proposed, although such functions are supposed to be built on top of dirtiness functions for single FDs. The approach in [21, 22, 23] shows how database IMs can be applied to integrity checking [24, 18], relaxing repairs, and repair checking, which are applications that perfectly fit within our framework. However, the degrees of inconsistency denfied in [ 23] form a partially ordered set; hence it is not always possible to compare the inconsistency of different databases. Finally, [25] proposes an IM based on an abstract repair semantics, where the degree of inconsistency depends on the distance between the database instance and the set of repairs, and an instantiation for cardinality-repairs that can be computed via answer-set programs [26].
Previous work has not investigated the problem of tailoring propositional IMs to relational data, as well as analysing postulates compliance and the complexity of the resulting IMs, which is the focus of our work [27]. We introduce new IMs for relational databases with denial constraints. These measures are inspired by IMs for propositional logic. However, we do not apply wellknown methods for propositional logic directly, as done for instance in [28, 29]; rather, we use these methods as inspiration to define (by analogy) new IMs for databases. In particular, we introduce the database counterpart, namely Ix with x ∈ {B, M, #, P, A, H,C, η}, of several propositional IMs Ix. Every database IM Ix measures the inconsistency by blaming database tuples only. This is different from measuring the inconsistency of a set of formulas, all of which have the same status, as is the case for propositional knowledge bases. This leads to some substantial differences between the two cases: for instance, some measures that are distinct for propositional knowledge bases become identical in our setting (namely IC and IH ). We investigate the complexity of the problems of deciding whether a given value is lower than (LV), greater than (UV), or equal to (EV) the inconsistency measured using a given IM Ix. A summary of the complexity results obtained for these problems, as well as for the problem of computing the actual value of an inconsistency measure (IM problem), is reported in Table 1 (Section 2.4). We conclude the paper by discussing rationality postulates for IMs and outlining some directions for future work.
We assume the reader is familiar with the standard concepts of relational database and integrity constraint, and with the complexity classes used in the paper (see e.g. [30] for a comprehensive overview).
We use D to denote the set of all database instances over a fixed but arbitrary database scheme D S . We say that a database instance D is consistent, meaning that D is consistent w.r.t. a fixed but arbitrary set C of denial constraints. A denial constraint is a first-order sentence of the form: ∀⃗x1, . . . ,⃗xk [¬R1(⃗x1) ∨ · · · ∨ ¬ Rk(⃗xk) ∨ ϕ(⃗x1, . . . ,⃗xk)] where: (i) ∀ i ∈ [1..k],⃗xi are tuples of variables and Ri(⃗xi) are atoms over D S ; and (ii) ϕ is a disjunction of built-in predicates of the form τi ◦ τ j where τi and τ j are variables in⃗x1, . . . ,⃗xk or constants, and ◦ ∈ { =, ̸=, >, <, ≥ , }≤ . We will write [¬R1(⃗x1) ∨ · · · ∨ ¬ Rk(⃗xk) ∨ ϕ(⃗x1, . . . ,⃗xk)] for a constraint (of arity k). For the sake of presentation, we will often omit the database scheme and the set of constraints in the terminology.
The idea of an inconsistency measure is to assign a nonnegative number to a knowledge base
that measures its inconsistency[
Consistency and Monotony are called (rationality) postulates. Postulates are desirable properties for IMs and we will mention additional ones in Section 3. However, we require that a function on databases must at least satisfy these two postulates in order to be called an IM. Consistency means that all and only consistent databases get measure 0. Monotony means that the enlargement of a database cannot decrease its measure.
A minimal inconsistent subset of D is a set of tuples X ⊆ D such that X is inconsistent (with respect to C ) and no proper subset of X is inconsistent. We denote by MI(D) the set of minimal inconsistent subsets of D. Similarly, a maximal consistent subset is a set of tuples Y that is consistent and no proper superset of Y is consistent. We write MC(D) for the set of maximal consistent subsets (of D). Any tuple that occurs in a minimal inconsistent subset is problematic; otherwise it is free. We use Problematic(D) and Free(D) to denote the sets of problematic and free tuples of D. A tuple t is contradictory if {t} is inconsistent w.r.t. C . We write Contradictory(D) for the set of contradictory tuples.
Example 1. Consider the database scheme D S ex consisting of the relation MealTicket(Number, Value, Holder, Date) whose instance contains the number, the value, the holder, and the issue date of meal tickets (one for each tuple) provided by a company to the employees. Cex consists of the following denial constraints: • c1 = [¬MealTicket(x1, x2, x3, x4) ∨ x2 > 0], stating that the value (i.e., the amount of the ticket) of every tuple of MealTicket must be a positive number. • c2 = [¬MealTicket(x1, x2, x3, x4) ∨ ¬MealTicket(x1, x5, x6, x7) ∨ x2 = x5], i.e., the functional dependency Number→Value, stating that there cannot be two distinct tickets with the same number and different values. • c3 = [¬MealTicket(x1, x2, x3, x4) ∨ ¬MealTicket(x1, x5, x6, x7) ∨ x3 = x6], i.e., the functional dependency Number→Holder. • c4 = [¬MealTicket(x1, x2, x3, x4)∨¬MealTicket(x5, x6, x3, x4)∨ ¬MealTicket(x7, x8, x3, x4)∨ x1 = x5 ∨ x1 = x7 ∨ x5 = x7], stating the numerical dependency (see [31]) Holder, Date →2Number whose meaning is that for every holder and date there can be at most 2 meal ticket numbers.
An instance Dex of D S ex consisting of 7 tuples⃗t1, . . . ,⃗t7 is shown below. Going through the integrity constraints we find that: 1) ⃗t5 is inconsistent with c1: it is a contradictory tuple; 2) no pair of tuples violates c2; 3) the two pairs of tuples,⃗t1,⃗t3, and⃗t2,⃗t3, are inconsistent with c3; 4) the three tuples⃗t5,⃗t6, and⃗t7 together are inconsistent with c4. Hence, MI(Dex) = {{⃗t5}, {⃗t1,⃗t3}, {⃗t2,⃗t3}}. Note that {⃗t5,⃗t6,⃗t7} is not included because it contains {⃗t5} (and thus it is not minimal). Thus there are 4 problematic tuples in Dex, and 3 free-tuples. Also, MC(D) = {{⃗t1,⃗t2,⃗t4,⃗t6,⃗t7}, {⃗t3,⃗t4,⃗t6,⃗t7}}.
We start with the measures that rely on minimal inconsistent subsets and the related concepts defined above. We give the rationale for each measure below.
Definition 2 (Database Inconsistency Measures). For a database D, the IMs IB, IM, I#, IP, IA, and IH are such that: • IB(D) = 1 if D is inconsistent and IB(D) = 0 if D is consistent. • IM(D) = |MI(D)|.
{︄ 0 • I#(D) = X∈M∑I(D) |X1| • IP(D) = |Problematic(D)|. • IA(D) = (|MC(D)| + |Contradictory(D)|) − 1. • IH (D) = min{|X | s.t. X ⊆ D and ∀M ∈ MI(D), X ∩ M ̸= 0/ }.
if D is consistent, otherwise.
IB is also called the drastic measure [15]: 0 means consistent; 1 means inconsistent. So this
measure simply distinguishes between consistent and inconsistent databases. IM counts the
number of minimal inconsistent subsets [15]. The rationale is that a minimal inconsistent subset
represents a minimal inconsistency for a set of database tuples; hence this measure counts the
number of such inconsistencies. I# also counts the number of minimal inconsistent subsets,
but it gives larger sets a smaller weight. The reason for I# in the propositional logic setting is
that when a minimal inconsistent set contains more formulas than another minimal inconsistent
set, the former is intuitively less inconsistent than the latter [15]. For instance, we can say that
intuitively {a, ¬a} is more inconsistent than {a, a → b, b → c, c → d, ¬d}. In the database setting,
this measure gives a higher value to the violations of constraints having smaller arity, that is, to
violations due to a smaller sets of tuples. It is a way to differentiate between constraints. For
instance, in Example 1 this measure gives a violation of c1 the highest value, a violation of c4
the lowest value, and a violation of c2 or c3 a middle value. IP counts the number of tuples that
are in one or more minimal inconsistencies [
Example 2. The values of IMs for the database of our running example are as follows. • IB(Dex) = 1 as the database is inconsistent. • IM(Dex) = 3 as there are 3 minimal inconsistent subsets as given above. • I#(Dex) = 1 + 12 + 12 = 2 as there is one minimal inconsistent subset of size 1 and two minimal inconsistent subsets of size 2. • IP(Dex) = 4 as there are 4 distinct tuples in MI(Dex). • IA(Dex) = 2 because there are 2 maximal consistent subsets.
• IH (Dex) = 2 as the set {⃗t3,⃗t5} intersects with each minimal inconsistent subset.
The contension measure IC [
Given a database D with a set C of integrity constraints, a 3VL interpretation is a 3VL model iff all the constraints are satisfied and no atom R(⃗t) ∈ D is assigned F. We use Models(D) to denote the set of 3VL models for a database D (with the integrity constraints in the background). Also, for a 3VL interpretation i we denfie Conflictbase(i) = {R(⃗t) | i(R(⃗t)) = B}, the tuples that have truth value B.
Definition 3 (Contension measure IC). For database D, measure IC is such that IC(D) = min{|Conflictbase(i)| | i ∈ Models(D)}.
Thus IC counts the minimal number of tuples that if we could consider them both true and false would resolve all inconsistencies. For the database of our running example, we have that IC(Dex) = 2 as the minimal number of B values for an interpretation occurs when i(⃗t1) = i(⃗t2) = i(⃗t4) = i(⃗t6) = i(⃗t7) = T and i(⃗t3) = i(⃗t5) = B.
In the propositional case, of the measures considered no 2 measures give the same result for all knowledge bases. But because of the special structure of databases, for database IMs there is an equality that does hold: IC(D) = IH (D). In fact, IC(D) counts the minimum number of tuples that need to be assigned B in order to get a 3VL model in Models(D). This is the same as the cardinality of the set X ⊆ D having a non-empty intersection with every minimal inconsistent subset of D. It can be shown that no other pair of IMs considered in this paper is identical [27].
Finally, we define the database counterpart of the probabilistic measure Iη that uses the PSAT
(probabilistic satisfiability) concept [16]. A PSAT instance is a set, Γ = {Pr(φi) ≥ pi | 1 ≤ i ≤
m}, that assigns probability lower bounds to a set {φ1, . . . , φm} of formulas; therefore 0 ≤ pi ≤ 1
for 1 ≤ i ≤ m. A probability function over a set X is a function π : X → [
Given a database D, a set of integrity constraints C , and a probability threshold η ∈ [
Thus, Iη (D) is one minus the maximum probability lower bound η that one can consistently assign to all tuples in D. For our running example, we have that Iη (Dex) = 1 because the maximum probability that can be assigned to (contradictory) tuple⃗t5 is 0.
We investigate the data-complexity of the three decision problems, which intuitively ask if a given rational value v is, respectively, lower than, greater than, or equal to the value returned by a given IM when applied to a given database. Observe that every IM returns a rational number, including Iη (as it can be shown by reasoning as in [16]). Definition 5 (Lower (LV), Upper (UV), and Exact Value (EV) problems). Let I be an IM. Given a database D over a fixed database scheme with a fixed set of denial constraints, and a value v ∈ Q>0, LVI (D, v) is the problem of deciding whether I (D) ≥ v. Given D and v′ ∈ Q≥ 0, UVI (D, v′) is the problem of deciding whether I (D) ≤ v′, and EVI (D, v′) is the problem of deciding whether I (D) = v′.
We also consider the problem of determining the IM value.
Definition 6 (Inconsistency Measurement (IM) problem). Let I be an IM. Given a database D over a fixed database scheme with a fixed set of denial constraints, IMI (D) is the problem of computing the value of I (D).
The complexity of LVI (D, v), UVI (D, v), EVI (D, v), and IMI (D) is as given in Table 1 [27]. Interestingly, while the measures IB, IM, I#, IP become tractable in the database setting and the complexity of IA decreases, the measures IH and Iη remain as hard as in the propositional case [33] even under data complexity.
We have introduced a framework for measuring inconsistency in databases. We believe that the definition and investigation of IMs for databases benefit from our approach to the problem, which stems from what has been done in the past by the AI community.
In [27] we also introduced the database counterparts of six rationality postulates defined for propositional knowledge bases (in addition to Consistency and Monotony, cf. Definition 1). For instance, Free-Tuple Independence states that deleting/adding a free tuple does not change the IM value, while Penalty states that deleting a problematic tuple decreases the measure. Thus, IMs satisfying these postulates allow us to check if deleting a given tuple makes a database less inconsistent or not. Super-Additivity deals with the union of two disjoint databases, and states that the measure of the union is at least as great as the sum of the measures of the two databases. Thus, an IM satisfying Super-Additivity is able to separately count the inconsistency arising from different sources. Other postulates considered in [27] help in describing the behavior of IMs.
Some postulates violated in the propositional case become satisfied in the database case. Specifically, IM satisfies all the postulates considered in [ 27]. One step down, we find I# which satisfies all the postulates but one. Next, IP satisfies all the postulates but two. IH which as said above coincides with IC in our setting also satisfies all the postulates but two, though it turns out to be computationally hard. Notably IM, I#, and IP can be evaluated by standard SQL, meaning that measuring inconsistency using these measures scales as far as the database can answer queries in reasonable time.
Many interesting issues concerning IMs in databases remain unexplored. We have dealt with denial constraints, a common type of integrity constraint which can express for instance equality generating dependencies (e.g., functional dependencies). We plan to extend our work to other types of integrity constraints, and in particular to inclusion dependencies. Also, we plan to identify tractable cases for the hard measures, possibly exploiting connections with work done on inconsistent databases (e.g., results in [34] help in characterizing the complexity of IA), and devise efficient algorithms and index structures for evaluating IMs. The IMs we have considered work at the tuple-level, without distinguishing inconsistency arising from different attributes, which is another issue we want to address in the future. Moreover, we plan to investigate methods for measuring the degree of inconsistency of query answers by leveraging on our IMs (an recent proposal in this direction is [35]). Finally, another interesting direction for future work is considering incomplete information (e.g., databases with null values). [13] J. Grant, A. Hunter, Distance-based measures of inconsistency, in: Proc. of ECSQARU, 2013, pp. 230–241. [14] J. Grant, M. V. Martinez, Measuring Inconsistency in Information, College Pub., 2018. [15] A. Hunter, S. Konieczny, Measuring inconsistency through minimal inconsistent sets, in:
Proc. of Principles of Knowledge Representation and Reasoning (KR), 2008, pp. 358–366. [16] K. Knight, Measuring inconsistency, J. Philosophical Logic 31 (2002) 77–98. [17] L. Fan, M. D. Flood, J. Grant, Measuring inconsistency in bank holding company data, in: Proc. of SIGMOD Workshop on Data Science for Macro-modeling with Financial and Economic Datasets (DSMM), 2019, pp. 5:1–5:5. [18] H. Decker, D. Martinenghi, Inconsistency-tolerant integrity checking, IEEE Trans. Knowl.
Data Eng. 23 (2011) 218–234. [19] J. Grant, Classifications for inconsistent theories, Notre Dame J. Formal Log. 19 (1978) 435–444. [20] M. V. Martinez, A. Pugliese, G. I. Simari, V. S. Subrahmanian, H. Prade, How dirty is your relational database? an axiomatic approach, in: Proc. of ECSQARU, 2007, pp. 103–114. [21] H. Decker, Inconsistency-tolerant database repairs and simplified repair checking by measure-based integrity checking, Trans. L. S. Data Knowl. Cent. Syst. 34 (2017) 153–183. [22] H. Decker, S. Misra, Database inconsistency measures and their applications, in: Proc. of
Int. Conf. on Information and Software Technologies (ICIST), 2017, pp. 254–265. [23] H. Decker, Measuring database inconsistency, in: J. Grant, M. V. Martinez (Eds.), Measuring
Inconsistency in Information, College Publications, 2018, pp. 271–311. [24] H. Decker, D. Martinenghi, Classifying integrity checking methods with regard to inconsistency tolerance, in: Proc. of Prin. and Pract. of Decl. Prog. (PPDP), 2008, pp. 195–204. [25] L. E. Bertossi, Measuring and computing database inconsistency via repairs, in: Proc. of
International Conference on Scalable Uncertainty Management (SUM), 2018, pp. 368–372. [26] L. E. Bertossi, Repair-based degrees of database inconsistency, in: Proc. of Logic Programming and Nonmonotonic Reasoning (LPNMR), 2019, pp. 195–209. [27] F. Parisi, J. Grant, On measuring inconsistency in relational databases with denial constraints, in: Proc. of European Conf. on Artificial Intelligence (ECAI), 2020, pp. 857–864. [28] J. Grant, F. Parisi, Measuring inconsistency in a general information space, in: Proc. of Int.
Symp. on Foundations of Information and Knowledge Systems (FoIKS), 2020, pp. 140–156. [29] J. Grant, F. Parisi, General information spaces: measuring inconsistency, rationality postulates, and complexity, Ann. Math. Artif. Intell. (2021). [30] C. H. Papadimitriou, Computational complexity, Addison-Wesley, 1994. [31] J. Grant, J. Minker, Inferences for numerical dependencies, TCS 41 (1985) 271–287. [32] S. Flesca, F. Furfaro, F. Parisi, Consistency checking and querying in probabilistic databases under integrity constraints, J. Comput. Syst. Sci. 80 (2014) 1448–1489. [33] M. Thimm, J. P. Wallner, Some complexity results on inconsistency measurement, in: Proc.
of Principles of Knowledge Representation and Reasoning (KR), 2016, pp. 114–124. [34] E. Livshits, B. Kimelfeld, Counting and enumerating (preferred) database repairs, in: Proc.
of Symposium on Principles of Database Systems (PODS), 2017, pp. 289–301. [35] O. Issa, A. Bonifati, F. Toumani, Evaluating top-k queries with inconsistency degrees, Proc.
VLDB Endow. 13 (2020) 2146–2158.