Relative Inconsistency Measures for Indefinite Databases with Denial Constraints

1 Introduction

Handling conflicting information is an important challenge in AI. Data of poor quality can significantly limit the implementation of effective AI solutions [Levy, 1999; Jain et al., 2020]. So, having information on the quality of data used in machine learning and data-driven approaches is crucial, as poor quality data can have serious adverse consequences on the quality of decisions made using AI [Sarker, 2021]. Measuring inconsistency [Grant, 1978; Grant and Martinez, 2018] is a well-understood approach that can be used towards assessing data quality, as it provides ways to quantify the severity of inconsistency that help understanding the primary sources of conflicts and devising ways to deal with them. In this regard, inconsistency measurement has been extensively investigated for propositional knowledge bases (e.g., [Thimm, 2016; Mu, 2018; Bona et al., 2019; Thimm and Wallner, 2019; Besnard and Grant, 2020; Ulbricht et al., 2020]), and explored in other settings such as software specifications [Mu et al., 2005], databases [Martinez et al., 2007; Decker, 2017; Bertossi, 2019; Parisi and Grant, 2020; Grant et al., 2021], and ontologies [Zhou et al., 2009; Zhang et al., 2017], among others. However, most of the literature on inconsistency measures (IMs) focused on absolute measures, rather than relative measures. An absolute measure gives the total amount of inconsistency, while a relative measure computes, by some criteria, the proportion of the base that is inconsistent [Besnard and Grant, 2020]. The difference between the two types of measures and the motivation for considering relative measures can be explained as follows. Consider the case of a large database D with numerous inconsistencies and a much smaller database D′ that has almost as many inconsistencies as D. The absolute inconsistency of D D′ just because it has more inconsistencies. But we can consider D′ to be more inconsistent than D since relative to its size it has more inconsistencies than D. In fact, if the question is "How inconsistent is the database?" the answer would likely be something like "It's x% inconsistent", rather than "It has y inconsistencies". Relative inconsistency measures have been used in applications including [Zhou et al., 2009] for ontologies, [Costa and Martins, 2018] for a hospital admission system, and [Fan et al., 2019] for a financial system database.

In this paper, we explore relative inconsistency measures for indefinite databases. The relational model is arguably among the most common types of data models and relational databases (DBs) are often used to store real-world data consumed by AI applications. Classical relational DBs can store definite information only, while in practical situations much of the information is not precise. Indefinite DBs, also known as disjunctive DBs, represent disjunctive information in the form of indefinite tuples, i.e., disjunctive facts. They have been studied for a long time [Grant and Minker, 1986; Liu and Sunderraman, 1990; Imielinski et al., 1995; Minker and Seipel, 2002; Alviano et al., 2010], and their potential applications include e.g. data integration, extraction and cleaning [Benjelloun et al., 2008; Molinaro et al., 2009]. Classical relational DBs are a special case of indefinite DBs where the information is definite, i.e., there is no disjunction of tuples.

There are few interesting works addressing the problem of measuring inconsistency in relational DBs. [Martinez et al., 2007] first developed single-dependency axioms for dirtiness functions quantifying inconsistency w.r.t. one functional dependency (FD)-a simple type of denial constraint (DC)- considered in isolation, and proposed a measure that satisfies these axioms. Then a single axiom for dirtiness functions that handle multiple FDs was proposed, although such functions are supposed to be built on top of a dirtiness function for single FDs. The approach in [Decker, 2017; Decker and Misra, 2017; Decker, 2018] deals with relational databases from the point of view of first-order logic, as in logic programming. Its purpose is to show how database inconsistency measures (IMs) can be applied to integrity checking [Decker and Martinenghi, 2008; 2011], relaxing repairs, and repair checking, which are applications that also fit within our framework. However, the degrees of inconsistency defined in [Decker, 2018] form a partially ordered set; hence it is not always possible to compare the inconsistency of different DBs. An IM based on an abstract repair semantics is proposed in [Bertossi, 2018], where the degree of inconsistency depends on the distance between the database instance and the set of possible repairs under a given repair semantics; an instantiation for cardinality-repairs that can be computed via answer-set programs is proposed in [Bertossi, 2019]. Rationality postulate compliance and the complexity of some absolute measures for DBs inspired from those for propositional logic are investigated in [Parisi and Grant, 2020]. Provenance-informed annotations of the base tuples are used in [Issa et al., 2020; 2021] to characterize the level of inconsistency of data and query results. In particular, building upon the computed annotations, different measures of inconsistency which consider single and multiple violations of denial constraints are introduced. IMs have been considered as the basis of progress indicators for data-cleaning systems in [Livshits et al., 2021], where properties that account for operational aspects of repair systems are introduced as well as a measure satisfying such properties. Finally, the Shapley value [Hausken and Mohr, 2001] of DB tuples is investigated in [Livshits and Kimelfeld, 2021] to calculate the contribution of a tuple to inconsistency for inconsistent DBs w.r.t. FDs. All the abovementioned works focus on definite DBs. Absolute IMs for indefinite DBs have been explored in [Parisi and Grant, 2023].

Contribution. Our main contributions are as follows.

• We introduce four postulates and a postulate-based definition of the concept of relative inconsistency measure (IM) for indefinite DBs with denial constraints, a class of integrity constraints that includes, for instance, equality generating dependencies [Beeri and Vardi, 1984] and numerical dependencies [Grant and Minker, 1985]. We consider five relative IMs, namely Imv, I rM , I rP , I rH , and I rC (which are formally defined in Section 3), corresponding to different methods of quantifying inconsistency in indefinite DBs.
• Analyzing the compliance of IMs w.r.t. rationality postulates is an important way to evaluate a measure, and is one of the main problems investigated in the area of inconsistency measurement, even though the set of desirable postulates is not universally accepted [Besnard, 2014; Thimm, 2016; 2018] (some postulates proposed in the literature are even incompatible, as they express alternative properties that may be required in different contexts). Given the importance of postulate satisfaction, in addition to the postulates considered in

the definition of relative IM, we examine the compliance of definite and indefinite DBs w.r.t. additional rationality postulates (Section 4). Our results are shown in Table 2. Two of the measures (I rP and I rH ) satisfy 7 of the 8 postulates even for indefinite DBs. As two of the considered postulates are incompatible (MI-Normalization and Contradiction can be satisfied together only for a very specific form of integrity constraints), I rP and I rH satisfy as many postulates in the list as possible. For another two measures (Imv and I rC ), the satisfaction results are better for the definite case (in which case Imv and I rC satisfy as many postulates as possible), but in all cases the majority of the postulates are satisfied.

• We investigate the data 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 relative IM for indefinite and definite DBs (Section 5). The complexity results obtained for these decision problems and for the function problem of computing the value of a relative IM (IM problem) are given in Table 3. It turns out that, for indefinite DBs, the considered relative IMs exhibit different levels of intractability. Specifically, for the decision problems (LV, UV, and EV), the complexity ranges from the first level of the polynomial hierarchy [Papadimitriou, 1994] for I rH and I rC , to the second level of the hierarchy for Imv and I rP , and up to classes from the counting polynomial hierarchy [Wagner, 1986] for I rM . However, three measures (Imv, I rP , and I rM ) turn out to be tractable in the case of definite DBs, while for the other two measures (I rH and I rC ) restricting to the definite case has no impact on the complexity. Finally, the complexity of the function problem IM ranges from being in FP for Imv, I rP , and I rM for definite DBs; in FP NP[logn] for I rH and I rC for both definite and indefinite DBs; in FP Σp2 [logn] for Imv and I rP for indefinite DBs; and in the counting class # · coNP [Hemaspaandra and Vollmer, 1995] for I rM and indefinite DBs.

2 Preliminaries

We recall indefinite DBs and some complexity classes.

2.1 Indefinite Databases

We assume that the reader is familiar with the relational model and the basic concept of definite DBs. An indefinite tuple over relational scheme R(A1, . . . ,An) is a set of (definite) tuples over R(A1, . . . ,An). An indefinite relation instance (or simply relation) is a finite set of indefinite tuples over a given relation scheme, and an indefinite DB instance (database) is a set of indefinite relations over a given DB scheme. Under the model-theoretic approach to relational DBs, an indefinite DB is a set of minimal models [Minker, 1982] (instead of a unique model of the underlying firstorder theory as for the case of definite DBs). Under the proof-theoretic approach, an indefinite tuple corresponds to a logical formula with inclusive disjunctions. The information content of an indefinite DB D consists of a set of definite DBs called possible worlds. A possible world for D is a set of (definite) tuples that contains a tuple from each element of D and is minimal w.r.t. set inclusion. More formally, let Def(D) be the set of all the definite DBs that can e1

e2

e3

e4

e5

e6

e7

be obtained from an indefinite DB D by selecting a (definite) tuple from each indefinite one in D. The meaning of D is given by the set of possible worlds W(D) = {W | W ∈ Def(D), ∄W ′ such that W ′ ∈ Def(D) and W ′ ⊂ W}.

We use the terminology element to refer to an indefinite tuple of a database D. Note that a definite DB is a special case of an indefinite DB, where each element is a definite tuple and only one possible world exists, that is, W(D) = {D}.

Example 1. Consider a genealogical DB whose scheme DSex consists of the relation scheme Ancestor (Id, Name, Birth Year, Parent, Death Year), where every record has an id and contains the name, the birth and death year of a person as well as the name of her/his parent. An instance Dex of DSex consisting of 7 elements (obtained from 9 different definite tuples) is shown in Table 1. A possible world for Dex is {t1, t3, t5, t6, t7, t8}, which is obtained fromDex by selecting the tuple t1 from the elements e1 and e3, the tuples t3, t5, t6, and t7 from the singleton elements e2, e4, e5, and e6, respectively, and t8 from element e7. Let T = {t3, t5, t6, t7}, the set of possible worlds for Dex is W(Dex) = {T ∪ {t1, t8}, T ∪ {t1, t9}, T ∪ {t2, t4, t8}, T ∪ {t2, t4, t9}}.

It is worth noting that an indefinite DB may contain redundant information because an indefinite tuple is part of another one. For instance, the database {{R(1, 1),R(1, 2)}, {R(1, 1)}} is equivalent to {{R(1, 1)}}, that is, they have the same set of possible worlds. Redundancy can be removed by deleting redundant tuples, that is, indefinite tuples that subsume other tuples. This is polynomial in the number of indefinite tuples, assuming that the size of the largest indefinite tuple is a constant (usually a small integer). In the following, we assume that the given DB is not redundant. It is also worth noting that since each indefinite tuple corresponds to a logical formula with inclusive disjunctions, it is possible for more than one tuple within an indefinite tuple to be the real world truth. For instance, for the database {{R(1, 1), R(1, 2)}, {R(1, 1), R(1, 3)}, {R(1, 2), R(1, 3)}}, a possible world is {R(1, 1),R(1, 2)}, which is obtained from the DB by selecting the definite tuple R(1, 1) from the first two indefinite tuples and R(1, 2) from the third one.

A denial constraint (DC) over a database scheme DS 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 DS; 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 ◦ ∈ {=, ̸=,>,<,≥,≤}. In the following, we will omit the prefix of universal quantifiers and write [¬R1(⃗x1) ∨ · · · ∨ ¬Rk(⃗xk) ∨ ϕ(⃗x1, . . . , ⃗xk)] for a denial constraint.

A functional dependency (FD) is a DC of the form [¬R(⃗x, y, ⃗z) ∨ ¬R(⃗x, u, ⃗w) ∨ (y = u)] where ⃗x, ⃗z, ⃗w are tuples of variables. It is written as R : X → Y (or simply X → Y ), where X is the set of attributes of R corresponding to ⃗x and Y is the attribute corresponding to y (and u).

For a DB scheme DS and a set IC of integrity constraints over DS, an indefinite DB instance D of DS is said to be consistent w.r.t. IC (denoted as D |= IC) iff there is at least one possible world of D which is consistent w.r.t. IC (in the standard model-theoretic sense), that is, {W | W ∈ W(D),W |= IC} ̸= ∅; otherwise, D is said to be inconsistent (w.r.t. IC).

Example 2. Continuing from Example 1, let the set ICex of integrity constraints consist of the following DCs:

• c1 = [¬Ancestor(x1, x2, x3, x4, x5) ∨ x5 > x3], stating that the death year must be greater than the birth year.
• c2 = [¬Ancestor(x1, x2, x3, x4, x5) ∨ ¬Ancestor(x1, x6, x7, x8, x9) ∨ x2 = x6], that is the FD Id→Name.
• c3 = [¬Ancestor(x1, x2, x3, x4, x5) ∨ ¬Ancestor(x6, x2, x7, x8, x9) ∨ ¬Ancestor(x10, x2, x11, x12, x13) ∨ x4 = x8 ∨ x4 = x12 ∨ x8 = x12], that is the numerical dependency [Grant and Minker, 1985] Name→2Parent stating that for every person there can be at most 2 parents.

We have that Dex is inconsistent w.r.t. ICex. In particular, going through the integrity constraints we find that 1) e2 ̸|= c1, while e.g. e3 |= c1 as one of its two tuples (disjuncts) satisfies the constraint; 2) the pairs of elements e1, e2 and e2, e3 are inconsistent with c2 (it is worth noting that {e1, e3} |= c2 as there is a world consisting of their common tuple t1 which is consistent); 3) the three elements e5, e6, and e7 together are inconsistent with c3. None of the possible worlds for Dex is consistent w.r.t. ICex, as each one violates one or more constraints (e.g., c1 is violated by all of them).

2.2 Complexity Classes

The complexity classes Σpk , Πpk and ∆pk , with k ≥ 0, are defined as follows [Papadimitriou, 1994]:

i) Σp0 = Πp0 = ∆p0 = P ;

ii) Σp1 = NP and Πp1 = coNP ;

iii) ∆pk = P Σpk-1 , Σpk = NP Σpk-1 , and Πpk = coΣpk , ∀k > 0. Thus, P C (resp., NP C ) denotes the class of the decision problems that can be solved in polynomial time by using an oracle in the class C by a deterministic (resp., non-deterministic) Turing machine. It holds that Σpk ⊆ ∆pk+1 ⊆ Σpk+1 ⊆ PSPACE and Πpk ⊆ ∆pk+1 ⊆ Πpk+1 ⊆ PSPACE.

A decision problem is in Dp k iff it is the conjunction of a problem in Σpk and a problem in Πpk . Dp 1 is also denoted as Dp . It holds that Dp ⊆∆p2 .

We will also use the class CNP from the counting polynomial hierarchy defined in [Wagner, 1986]. This class relies on a counting quantifier C defined as follows. Given a predicate H(x, y) with free variables x and y, C k y H(x, y) holds iff |{y : H(x, y) is true}| ≥ k, i.e., the counting quantifier is true for predicate H and bound k iff the number of values of y such that H(x, y) holds is at least k. The polynomially bounded version of the counting quantifier is defined as follows. Given a class C of decision problems, we say that a problem A is in CC iff there is a problem B ∈ C, a polynomial-time computable function f, and a polynomial p such that x is a positive instance of A iff C f(x) y, |y|≤p(x) (x, y) ∈ B. That is, instance x ∈ A iff there are at least f(x) many y's whose size is polynomially bounded by that of x such that a predicate for (x, y) holds, with checking the predicate being in B. A canonical problem for CNP is deciding whether an open quantified boolean formula ∀YΦ(X, Y ) has at least k many satisfying assignments (for the variables X in the open part). CNP is closed under complement. It holds that CP ⊆ CNP. Moreover, CNP = CB(NP), where B(NP) is the Boolean closure of NP [Wagner, 1986], that implies that Dp ⊆ B(NP) and CNP = CDp . The class C=C is defined exactly as CC except that the counting quantifier holds iff it is satisfied by equality. We will focus on C=Dp . To the best of our knowledge, it is not known whether C=NP coincides with C=Dp , neither whether C=NP coincides with C=B(NP ).

FP is the class of the function problems that can be solved by a deterministic Turing machine in polynomial time. For a class C, FP C is the class of functions computable by a deterministic polynomial-time Turing machine using a C-oracle. Thus, FP NP (resp., FP Σp2 ) is the class of problems that can be solved by a polynomial-time Turing machine that can ask a polynomial number of queries to an NP oracle (resp., Σp2 oracle). If a logarithmic number of queries is asked by the machine, then we have the class FP NP[log n] (resp., FP Σp2 [log n] ).

We also use the class # · coNP [Hemaspaandra and Vollmer, 1995]. Given a class C of decision problems, #· C is the class of the counting problems defined by means of witness functions w that assign to a given input x a set w(x) of witnesses. Herein, a counting problem returns the cardinality |w(x)| of a set of witnesses. For the witness function w, (i) for every input x, the size of every witness y ∈ w(x) is polynomially bounded by that of x; and (ii) given x and y, deciding whether y ∈ w(x) is in class C. A canonical problem for #·P is counting the satisfying assignments of a SAT formula. This problem is in #P [Valiant, 1979], which coincides with #·P . It holds that # · P ⊆ # · coNP and # · coNP = # · ∆p2 .

3 Relative InconsistencyMeasures

In this section, we develop relative IMs for indefinite DBs in analogy with relative IMs for propositional knowledge bases [Besnard and Grant, 2020]. Although these methods are inspired by IMs for propositional logic we do not apply them directly as done e.g. in [Grant and Parisi, 2020; 2022] where a general information space, which encompasses definite databases, is translated into an inconsistency equivalent propositional knowledge base (KB), and then propositional IMs are applied to find the inconsistency. This approach makes no distinction between DB tuples and integrity constraints, i.e., IMs blame simultaneously tuples and constraints without considering that inconsistency in DBs typically refers to the tuples rather than the integrity constraints. Rather, we use well-known methods as inspiration to define (by analogy) IMs that are applicable to indefinite DBs. Every IMmeasures the inconsistency by blaming (indefinite) 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 of propositional KBs. This leads to some substantial differences between the two cases, e.g. some measures that are distinct for KBs become identical in our setting (cf. Proposition 1).

We use D to denote the set of all indefinite DB instances over a fixed but arbitrary DB scheme DS. In general, we will omit the DB scheme and the set IC of integrity constraints in the terminology. Aminimal inconsistent subset (MIS) of DB D is a set of elements X ⊆ D such that X is inconsistent (w.r.t. IC) and no proper subset of X is inconsistent. We denote by MI(D) the set of MISs of D. Any element that occurs in a MIS is problematic; otherwise it is free. We use Problematic(D) and Free(D) to denote the sets of problematic and free elements of D. We use Tuples(D) to denote the set of definite tuples of a DB D, that is Tuples(D) = ⋃e∈D e. To define relative IMs, we use the following postulates.

Definition 1 (Basic Postulates). Let D,D′ be DBs, and I : D → R≥0 ∞ a function. The basic postulates are as follows:

Consistency I(D) = 0 iff D is consistent.

Normalization 0 ≤ I(D) ≤ 1.

Free-Element Reduction For e ̸∈ D, if e ∈ Free(D ∪ {e}) and I(D) ̸= 0, then I(D ∪ {e}) < I(D).

Relative Separability If MI(D ∪ D′ ) = MI(D) ∪ MI(D′ ), Tuples(D) ∩ Tuples(D′ ) = ∅, I(D) ̸= 0, I(D′ ) ̸= 0, and I(D) ≾ I(D′ ), then I(D) ≾ I(D ∪D′ ) ≾ I(D′ ), where either ≾ is < in every instance or ≾ is = in every instance.

Assuming that I is a function measuring inconsistency, Consistency means that all and only consistent databases get measure 0. Consistency is the only postulate that is required to be satisfied by every IM. In some cases, the satisfaction of a postulate called Monotony is also required for absolute IMs. Monotony means that the enlargement of a database cannot decrease its measure. However, Monotony is not appropriate for relative IMs where the ratio of inconsistency may decrease with the addition of consistent information. In contrast, Normalization is appropriate for relative IMs; it states that an IM cannot have value greater than 1.

Free-Element Reduction requires that adding a free element to an inconsistent DB (that is, adding an element that does not introduce a new conflict) reduces the IM. The reason is that while the numerator remains the same, the denominator decreases. But Free-Element Reduction may not hold for indefinite DBs because while the element is new, it may contain tuples already in the DB. Relative Separability deals with the case where a DB can be split into two inconsistent parts. If ≾ is =, then the DB has the same IM as the two parts. Otherwise, the DB has an inconsistency value in between the inconsistency values of the two parts. Thus under the specified conditions the relative measure of the union sort of averages out the relative measures of the components; however, the result need not be the exact average.

We are now ready to define the concept of relative IM. The definition is inspired by that in [Besnard and Grant, 2020], where it is shown that all IMs that are intuitively relative measures satisfy both Consistency and Normalization and any IM

that satisfies neither Free-Formula Independence nor Relative Separability does not satisfy our intuitive notion of a relative measure. This way we restrict what we may consider as a relative measure without making the definition so strict that some reasonable relative IMs would be excluded.

Definition 2 (Relative IM). A function I : D → R≥0 ∞ is a relative inconsistency measure iff it satisfies the postulates Consistency, Normalization, and either Free-Formula Reduction or Relative Separability (or both).

In the following subsections we will define five IMs that will be shown to satisfy Definition 2 in Section 4. It is worth noting that, in general, normalizing an absolute IM may not result in a relative IM (as Definition 2 may not be satisfied).

3.1 Relative Measures UsingMISs

We introduce relative IMs that rely on MISs and on the related concepts defined earlier. In the following definition we assume that D ̸= ∅ and set I(∅) = 0 in all cases.

Definition 3 (Relative Inconsistency Measures). For any DB D, the IMs Imv I rM , I rP , and I rH are such that

• Imv(D) = |Tuples(⋃X∈MI(D) X)| |Tuples(D)|
• I rM (D) = |MI(D)| ( |D| ⌊|D|/2⌋)
• I rP (D) = |Problematic(D)| |D|

Thus, Imv(D) is the number of definite tuples occurring in some MIS divided by the amount of all such tuples in the DB (observe that |Tuples(D)| can be greater than, lower than, or equal to |D| depending on how definite tuples are combined to form indefinite ones). The proportion of propositional variables is considered by this measure in propositional logic [Xiao and Ma, 2012]. I rM is the ratio of the number of MISs to the maximum possible number of such subsets. The rationale is that a MIS represents a minimal inconsistency for a set of database elements; hence this measure is proportional the number of such inconsistencies [Hunter and Konieczny, 2008]. The denominator of I rM is the maximum number of MISs that can occur in a database of size D. As MI(D) is a Sperner family over D, its size is maximized if its elements have size ⌊|D|/2⌋ [Thimm, 2016]. We use superscript 'r' for relative IMs whose criterion for quantifying inconsistency is obtained by relativizing some absolute IM. Next, I rP is the ratio of the number of elements that are in one or more MISs to the size of the database. This is the relativized version of the so-called problematic measure [Grant and Hunter, 2011]. The numerator of I rH corresponds to the minimal number of elements whose deletion makes the database consistent [Grant and Hunter, 2013]. Hence I rH can be written as I rH = min{|X| s.t. D \ X is consistent }/|D|.

Example 3. Continuing with our running example, we have that MI(Dex) = {{e2}, {e5, e6, e7}}. Note that {e1, e2} as well as {e2, e3} are not included because they contains {e2}.

Thus there are 4 problematic elements in Dex, and 3 free elements. The values of the IMs for Dex are as follow.

• Imv(Dex) = 59 as 5 of the 9 tuples in Dex are in MISs.
• I rM (Dex) = 2 35 as there are 2 MISs as given above while 35 is the maximum number of MIS that can occur in a database consisting of 7 elements.
• I rP (Dex) = 47 as 4 of the 7 elements are in MI(Dex).
• I rH (Dex) = 27 as no less than 2 of the 7 elements intersect with each MIS.

3.2 ARelative Measure Using 3VL

We now consider the Contension measure [Grant and Hunter, 2011], which uses a three-valued (3VL) logic. In our setting, a 3VL interpretation is a function i that assigns to each atom R(⃗t) in D one of the three truth values: T (true), F (false), or B (both). The logical connectives are extended to 3VL interpretations using Priest's three-valued logic, the Logic of Paradox [Priest, 1979]. This interpretation uses an ordering on the truth values where F < B < T and ∧ computes the minimum value while ∨ computes the maximum value; also ¬(B) = B. So, for example, B ∧ F = F and B ∨ F = B. The 3VL semantics extends to first-order logic in our case as we consider the grounded versions of the constraints. In classical two-valued logic, an interpretation is a model for a set of formulas if every formula gets the value T (the unique designated value). But in 3VL there are two designated values, T and B. In the DB context this means that for a given D with a set IC of constraints, a 3VL interpretation is a 3VL model iff all the integrity constraints and elements get the value T or B. We use Models(D) to denote the set of 3VL models for D (with the constraints in the background). Also, for a 3VL interpretation i we define Conflictbase(i) = {R(⃗t) | i(R(⃗t)) = B}, the atoms that have truth value B.

We now introduce the IM I rC . As before, I rC (∅) = 0.

Hence, I rC is the minimal number of definite tuples that if we could consider them both true and false would resolve all inconsistencies divided by the size of the DB. For our running example, we have I rC (Dex) = 2 9 as the minimal number of B values for an interpretation occurs when assigning B to the tuple in e2 and a tuple in either e5 or e6.

3.3 Measures Coinciding for Definite DBs

In the propositional case, of the IMs considered in this paper no two give the same result for all KBs. But because of the structure of DBs, for definite DBs two equalities hold: 1) Imv(D) = I rP (D), and 2) I rC (D) = I rH (D). The first follows from the fact that, for a definite DB, every element is a definite tuple, and thus Tuples(D) = D and the problematic elements are exactly the tuples in the MISs. The second equality follows from the fact that the minimum number of tuples that need to be assigned B in order to get a 3VL model in Models(D) is the same as the cardinality of the set X ⊆ D having a non-empty intersection with every MIS of D.

Proposition 1. For any definite database D, Imv(D) = I rP (D) and I rC (D) = I rH (D).

As will be noted after Theorem 1, no other pair of considered measures is identical for definite or indefinite DBs.

For indefinite DBs, Imv and I rP need not give the same result. For instance, considering D′ = {{R(-1),R(-2)}, {R(-1), R(3)}} and IC ′ = {¬R(x) ∨ x > 0}, we have that Imv(D′ ) = 2/3 > I rP (D′ ) = 1/2 since there are three tuples in D′ forming two elements, and there are two tuples in the first element which is a self-contradiction. Similarly, I rH and I rC need not give the same result. For instance, we have that I rH (D′ ) = 1/2 > I rC (D′ ) = 1/3 because one of the two elements is a self-contradiction and for 3VL it suffices to assign R(-1) the value B, R(-2) the value F, and R(3) the value T to eliminate the inconsistency. In general, I rC (D) ≤ I rH (D) holds for all indefinite DBs because assigning B to one of the disjuncts in an element that needs removal for I rH suffices to eliminate the inconsistency for I rC as well, and the denominator of I rC is greater than or equal to that of I rH . Although our interest is in relative measures, we wish to point out that even the absolute versions, IH and IC are not the same. They happen to have the same value, 1 for D′ but consider D′′ , the same as D′ except that R(3) is replaced by R(-3). As now both elements are contradictions, IH(D′′ ) = 2, while IC(D′′ ) = 1 as it suffices to assign R(-1) the value B and both R(-2) and R(-3) the value F .

4 Postulate Satisfaction for Relative IMs

In the previous section we formulated four important postulates relevant for relative IMs. In this section we introduce four additional postulates for indefinite DBs that relative IMs may or may not satisfy. We avoid postulates that were shown in [Besnard and Grant, 2020] not to hold for relative IMs. Then, we show which of the eight postulates are satisfied by the five IMs defined previously.

Definition 5 (Additional Postulates Relevant for Relative IMs). Let D be an indefinite DB and I : D → R≥0 ∞ a function. The additional postulates are as follows:

Safe-Element Reduction If e∩Tuples(D) = ∅ and I(D) ̸= 0, then I(D ∪ {e}) < I(D).

MI-Normalization If MI(D) =D, then I(D) = 1.

Contradiction I(D) = 1 iff for all ∅ ̸= D′⊆D, I(D′ ) > 0.

Safe-Element Reduction is a weak version of Free-Element Reduction where we require that e contain no tuple in D. In fact, Free-Element Reduction implies Safe-Element Reduction. MI-Normalization and Equal Conflict deal specifically with MISs. MI-Normalization requires every database coinciding with a MIS to have measure 1. Equal Conflict requires MISs of the same size to have the same measure, thus stating a similarity between MISs of the same size. MI-Normalization implies Equal Conflict but the converse does not hold. Finally, Contradiction requires that the highest relative inconsistency measure, 1, be reserved for DBs all of whose nonempty subsets are inconsistent. The intuition is that a DB that has a consistent portion should not be considered 100% inconsistent.

It is useful to note that MI-Normalization and Contradiction are incompatible postulates because if a database D that is its own MIS is such that |D| > 1 then Contradiction fails. We would have to restrict the constraints to ones that contain only a single relation symbol to gain compatibility. Importantly, this also means that no IM can satisfy all 8 postulates; hence the ones that satisfy 7 satisfy as many as possible in the list.

Theorem 1. For definite and indefinite DBs the satisfaction of postulates for relative IMs is as given in Table 2.

Thus, the functions defined in the previous section are relative IMs according to Definition 2, as each of them satisfies Consistency, Normalization, and Free-Formula Reduction or Relative Separability. The other four postulates are not mandatory; they simply allow us to better understand the behavior of relative IMs in some circumstances. For instance, if Contradiction is satisfied and the inconsistency value is 100%, then the DB is 'totally inconsistent', in the sense that each of its subset is inconsistent. On the other hand, if MI-Normalization is satisfied and the inconsistency value is 100%, then we should be aware that there is a chance that the inconsistency could be ascribed to a single MIS coinciding with the DB. Overall, the results of Theorem 1 allow us to compare the IMs in terms of the satisfied postulates. Both I rP and I rH satisfy as many postulates as possible, though with alternative behavior w.r.t. the two incompatible postulates, and this holds also for I rmv and I rC for definite DBs.

Finally, as a consequence of Theorem 1, we have that, except for the equalities given in Proposition 1 for the case of definite DBs, no other pair of IMs in Table 2 are identical since they do not satisfy exactly the same set of postulates.

5 Complexity of Relative IMs

We investigate the data-complexity of the following 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 DB.

Definition 6 (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 integrity constraints, and a value v ∈ Q(0,1] ,

• LVI(D, v) is the problem of deciding whether I(D) ≥ v. Given D and a value v′ ∈ Q[0,1] ,
• UVI(D, v′ ) is the problem of deciding whether I(D) ≤ v′ ,
• EVI(D, v′ ) is the problem of deciding whether I(D) = v′ .

We avoid considering values for which the considered problems are trivial, e.g. LVI(D, 0) is true for any IM.

We also consider the problem of determining the IM value.

Definition 7 (Inconsistency Measurement (IM) problem). Let I be an IM. Given a database D over a fixed database scheme with a fixed set of integrity constraints, IMI(D) is the problem of computing the value of I(D).

The following proposition states the complexity of the above-mentioned problems for the case of definite DBs.

Proposition 2. For any definite DB and IM I ∈ {Imv, I rM , I rP , I rH , I rC }, the complexity of LVI, UVI, EVI, and IMI is as given in Table 3.

Thus, I rM and Imv (and I rP which coincides with Imv for definite DBs) are tractable for definite databases. As we show next, the presence of disjunction entails that the measures Imv, I rM , and I rP are no longer tractable. Indeed, for indefinite DBs, depending on the considered IM, the complexity of the considered problems reaches the first level of the polynomial hierarchy or beyond (even under data-complexity). However, the results obtained for the measures I rH and I rC in the case of definite DBs still hold for indefinite DBs.

Theorem 2. For any indefinite DB and IM I ∈ {Imv, I rM , I rP , I rH , I rC }, the complexity of LVI, UVI, EVI, and IMI is as given in Table 3.

Most of the results in Table 3 hold even if the set of constraints consists of FDs only. In fact, all the membership results trivially hold for FDs as they hold for the more general class of DCs. Moreover, we can show the following result.

Proposition 3. All the hardness results in Table 3 for LV and UV still hold if the set of constraints consists of FDs only.

In particular, the NP-hardness results for I rH and I rC can be shown in cases where the set of constraints consists of two FDs only. Moreover, the results for I rM hold even if the constraint is a single FD. Finally, we can show that also the Σp2 /Πp2 -hardness results for Imv and I rP (for the case of indefinite DBs) hold even in the presence of a single FD.

6 Conclusions and FutureWork

We have introduced relative IMs for indefinite DBs and analyzed postulate compliance as well as their complexity for both indefinite and definite DBs. Our work contributes to understanding how the database counterpart of some methods to quantify inconsistency in propositional logic behaves in the DB context, where data are generally the reason for inconsistency, not the integrity constraints. The results in Tables 2 and 3 give insights on the behavior of relative IMs, helping to figure out which measure could be appropriate for specific applications. We do not believe that there is a "best" IM. An IM gives information about a DB that can be used in different ways depending on the circumstance. For instance, maintaining an IM-based progress bar during database repair involving deletions [Livshits et al., 2021] has different requirements than measuring inconsistency for bank holding companies [Fan et al., 2019] where the information cannot be deleted even if it is inconsistent. For this situation, if interested to the proportion of potential issues (i.e., MISs) to be resolved, I rM could be a good candidate unless other criteria take precedence. The computational cost is also relevant. For definite DBs, I rM and Imv, which coincides with I rP , can be computed in polynomial time by standard SQL. For indefinite DBs, I rH and I rC look to be the cheaper measures. In this regard, a dichotomy for FDs for the problem of computing the cost of a cardinality repair (that is equivalent to computing the numerator of I rH ) for definite DBs has been presented in [Livshits et al., 2020]. This entails that there are cases where computing I rH is polynomial, but also cases where it is APX-complete (it cannot be approximated better than some constant) and it has a polynomial-time 2-approximation.

We envisage several interesting directions for future work. They include: i) considering other forms of incomplete information (not just disjunctive tuples) such as maybe information [Liu and Sunderraman, 1990] and dealing with DBs with null values; ii) extending our work to other types of integrity constraints, particularly to inclusion dependencies; iii) devising IMs working at the attribute-level and able to distinguish inconsistencies arising from different (sets of) attributes (by following the idea of dimensional inconsistency measures proposed in [Grant et al., 2021]); and finally iv) developing an ASP-based implementation by exploiting e.g. the DB-oriented features of DLVDB [Alviano et al., 2010] in order to evaluate relative IMs.

Acknowledgments

We thank the reviewers for their valuable comments and suggestions. The fist author acknowledges financial support from PNRR MUR project PE0000013-FAIR.