Measuring inconsistency is an approach that provides ways to quantify the severity of inconsistency and helps understanding the primary sources of conflicts. In this paper, we discuss inconsistency measures for indefinite databases, which allow for indefinite or partial information which is formally expressed by means of disjunctive tuples. We introduce inconsistency measures for indefinite databases with denial constraints, and explore the complexity of the problem of computing the value of the proposed inconsistency measures as well as of the problems of deciding whether the inconsistency value is lower than, greater than, or equal to a given threshold for indefinite and definite databases.
Handling conflicting information is an important challenge. In fact, data of poor quality can
significantly limit the implementation of effective AI solutions [
In this paper, we explore inconsistency measures for definite and indefinite databases (DBs).
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 [
There are few interesting works addressing the problem of measuring inconsistency in
relational DBs. [23] 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 [24, 25, 26] 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 [27, 28], relaxing repairs, and repair checking, which are applications that also fit within
our framework. However, the degrees of inconsistency defined in [ 26] 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 [29], 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 [30]. Provenance-informed annotations of the base tuples are used in [31, 32] 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 DCs are introduced. IMs have been considered as the basis of progress indicators
for data-cleaning systems in [33], where properties that account for operational aspects of repair
systems are introduced as well as a measure satisfying such properties. Finally, the Shapley
value [34] of tuples is investigated in [35] to calculate the contribution of a tuple to inconsistency
for inconsistent DBs w.r.t. FDs. The work in [36], which is an early version of [
We explore the problem of tailoring propositional inconsistency measures to indefinite (and
definite) DBs, and in particular analyze the computational complexity of the resulting
inconsistency measures for both the general case of indefinite DBs and the special case of definite DBs [
We assume that the reader is familiar with the relational model and the basic concept of definite DBs [39]. An indefinite tuple over relational scheme (1, . . . , ) is a set of (definite) tuples over (1, . . . , ). 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 [ 40] (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 consists of a set of definite DBs called possible worlds. A possible world for is a set of (definite) tuples that contains a tuple from each element of and is minimal w.r.t. set inclusion. More formally, let Def() be the set of all the definite DBs that can be obtained from an indefinite DB by selecting a (definite) tuple from each indefinite one in . The meaning of is given by the set of possible worlds () = { | ∈ Def(), ∄ ′ such that ′ ∈ Def() and ′ ⊂ }.
We use the terminology element to refer to an indefinite tuple of a database . 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, () = {}.
Example 1. Consider a genealogical DB whose scheme 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 of consisting of 7 elements (obtained from 9 different definite tuples) is shown in Table 1. A possible world for is {1, 3, 5, 6, 7, 8}, which is obtained from by selecting the tuple 1 from the elements 1 and 3, the tuples 3, 5, 6, and 7 from the singleton elements 2, 4, 5, and 6, respectively, and 8 from element 7. Let = {3, 5, 6, 7}, the set of possible worlds for is () = { ∪ {1, 8}, ∪ {1, 9}, ∪ {2, 4, 8}, ∪ {2, 4, 9}}.
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 {{(1, 1), (1, 2)}, {(1, 1)}} is equivalent to {{(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 {{(1, 1), (1, 2)}, {(1, 1), (1, 3)}, {(1, 2), (1, 3)}}, a possible world is {(1, 1), (1, 2)}, which is obtained from the DB by selecting the definite tuple (1, 1) from the first two indefinite tuples and (1, 2) from the third one.
A denial constraint (DC) over a database scheme is a first-order sentence of the form: ∀ ⃗1, . . . , ⃗ [¬1(⃗1) ∨ · · · ∨ ¬ (⃗) ∨ (⃗1, . . . , ⃗)] where: (i) ∀ ∈ [1..], ⃗ are tuples of variables and (⃗) are atoms over ; and (ii) is a disjunction of built-in predicates of the form ∘ where and are variables in ⃗1, . . . , ⃗ or constants, and ∘ ∈ { = , ̸=, >, <, ≥ , ≤} . In the following, we will omit the prefix of universal quantifiers and write [¬1(⃗1) ∨ · · · ∨ ¬ (⃗) ∨ (⃗1, . . . , ⃗)] for a denial constraint.
A functional dependency (FD) is a DC of the form [¬(⃗, , ⃗) ∨ ¬(⃗, , ⃗) ∨ ( = )] where ⃗, ⃗, ⃗ are tuples of variables. It is written as : → (or simply → ), where is the set of attributes of corresponding to ⃗ and is the attribute corresponding to (and ).
For a DB scheme and a set of integrity constraints over , an indefinite DB instance of is said to be consistent w.r.t. (denoted as |= ) iff there is at least one possible world of which is consistent w.r.t. (in the standard model-theoretic sense), that is, { | ∈ (), |= } ̸= ∅; otherwise, is said to be inconsistent (w.r.t. ).
Example 2. Continuing from Example 1, let be the set of the following DCs: ∙ 1 = [¬Ancestor(1, 2, 3, 4, 5) ∨ 5 > 3], stating that the death year must be greater than the birth year. ∙ 2 = [¬Ancestor(1, 2, 3, 4, 5) ∨ ¬Ancestor(1, 6, 7, 8, 9) ∨ 2 = 6], that is the FD Id→Name. ∙ 3 = [¬Ancestor(1, 2, 3, 4, 5) ∨ ¬Ancestor(6, 2, 7, 8, 9) ∨ ¬Ancestor(10, 2, 11, 12, 13) ∨ 4 = 8 ∨ 4 = 12 ∨ 8 = 12], that is the numerical dependency [41] Name→2Parent stating that for every person there can be at most 2 parents.
We have that is inconsistent w.r.t. . In particular, going through the constraints we find that 1) 2 ̸|= 1, while e.g. 3 |= 1 as one of its two tuples (disjuncts) satisfies the constraint; 2) the pairs of elements 1, 2 and 2, 3 are inconsistent with 2 (notice that {1, 3} |= 2 as there is a world consisting of their common tuple 1 which is consistent); 3) the three elements 5, 6, and 7 together are inconsistent with 3. None of the possible worlds for is consistent w.r.t. , as each one violates one or more constraints (e.g., 1 is violated by all of them).
The idea of an inconsistency measure is to assign a nonnegative number to a knowledge base that measures its inconsistency [42]. We introduce inconsistency measures (IMs) for indefinite DBs with denial constraints. We use D to denote the set of all indefinite database instances over a ifxed but arbitrary database scheme . In general, we will omit the database scheme and the set of integrity constraints in the terminology.
Definition 1 (Inconsistency Measure). A function ℐ : D → R≥ 0 is an inconsistency measure iff ∞ the following two conditions hold for all , ′ ∈ D: 1) Consistency ℐ() = 0 iff is consistent; 2) Monotony If ⊆ ′, then ℐ() ≤ ℐ (′).
Consistency and Monotony are called (rationality) postulates. 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 DBs get measure 0. Monotony means that the enlargement of a
DB cannot decrease its measure. Note that we are limiting the integrity constraints to DCs. This
means that inconsistencies cannot be resolved by insertions. This is not the case in the presence
of existential constraints, such as inclusion dependencies, where Monotony is not appropriate.
Additional postulates are given in [
We now give some basic definitions needed to define IMs. A minimal inconsistent subset (MIS) of is a set of elements ⊆ such that is inconsistent (w.r.t. ) and no proper subset of is inconsistent. We denote by MI() the set of minimal inconsistent subsets of . Similarly, a maximal consistent subset is a set of elements that is consistent and no proper superset of is consistent. We write MC() for the set of maximal consistent subsets (of ). Any element that occurs in a MIS is problematic; otherwise it is free. We use Problematic() and Free() to denote the sets of problematic and free elements of . An element is contradictory if {} is inconsistent w.r.t. . We write Contradictory() for the set of contradictory elements.
We start with the measures that rely on MISs and the related concepts defined above. Definition 2 (Database IMs). For any DB , the IMs ℐ , ℐ , ℐ , ℐ, and ℐ are such that • ℐ () = 1 if is inconsistent and ℐ () = 0 if is consistent. • ℐ () = |MI()|. • ℐ () = |Problematic()|. • ℐ() = (|MC()| + |Contradictory()|) − 1.
• ℐ () = min{|| .. ⊆ and ∀ ∈ MI(), ∩ ̸= ∅}.
We explain the measures as follows. ℐ is also called the drastic measure [43]: 0 means consistent; 1 means inconsistent. ℐ counts the number of MISs [43]. The rationale is that a MIS represents a minimal inconsistency for a set of database elements; hence this measure counts the number of such inconsistencies. ℐ counts the number of elements that are in one or more minimal inconsistencies [44]. ℐ uses the cardinality of the set of maximal consistent subsets [44] (corresponding to repairs for DBs [45]). Intuitively, the larger this set, the larger is the space of different ways to get consistency, the higher the degree of inconsistency. Contradictory elements are added as they do not appear in any way in a maximal consistent set; then 1 must be subtracted to obtain ℐ() = 0 for a consistent because every consistent DB has a maximal consistent subset, namely itself. ℐ counts the minimal number of elements whose deletion makes the DB consistent [46]. Hence ℐ can be written as ℐ = min{|| .. ∖ is consistent }. In fact, both ℐ and ℐ link the inconsistency measurement to the ways of restoring consistency, an idea explored for definite DBs in [ 29, 30] where the degree of inconsistency depends on the distance between the DB and the set of possible repairs under a given repair semantics. Example 3. Continuing with our running example, MI() = {{2}, {5, 6, 7}}. Note that {1, 2} as well as {2, 3} are not included because they contain {2}. Thus there are 4 problematic elements in , and 3 free elements. Also, MC() = {{1, 3, 4, 5, 6}, {1, 3, 4, 5, 7}, {1, 3, 4, 6, 7}}. Therefore, the values of the IMs for are as follows. ℐ() = 1 as the database is inconsistent. ℐ () = 2 as there are 2 MISs. ℐ () = 4 as 4 elements are in MI(). ℐ() = 3 as there are 3 maximal consistent subsets and one contradictory element (that is, 2). Finally, ℐ () = 2 as no less than 2 elements intersect with each MIS.
We now consider the Contension measure [44], which uses a three-valued (3VL) logic. A 3VL interpretation is a function that assigns to each atom (⃗) in one of the three truth values: (true), (false), or (both). The logical connectives are extended to 3VL interpretations using Priest’s three-valued logic, the Logic of Paradox [47]. This interpretation uses an ordering on the truth values where < < and ∧ computes the minimum value while ∨ computes the maximum value; also ¬() = . So, for example, ∧ = and ∨ = . In classical two-valued logic, an interpretation is a model for a set of formulas if every formula gets the value (the unique designated value). But in 3VL there are two designated values, and . This means that for a given DB with a set of constraints, a 3VL interpretation is a 3VL model iff all the integrity constraints and elements get the value or . We use Models() to denote the set of 3VL models for (with the constraints in the background). Also, for a 3VL interpretation we define Conflictbase() = {(⃗) | ((⃗)) = }, the atoms that have truth value . Definition 3 (Contension measure ℐ ). For any database , ℐ is such that ℐ () = min{|Conflictbase()| | ∈ Models()}.
For our running example, we have that ℐ () = 2 as the minimal number of values for an interpretation occurs when assigning to the tuple in 2 and a tuple in either 5 or 6.
For definite DBs, it can be shown that ℐ () = ℐ (). No other pair of measures considered in this paper is identical for definite DBs. For indefinite DBs, ℐ and ℐ need not give the same result. For instance, ′ = {{(− 1), (− 2)}, {(− 1), (− 3)}} and ′ = {¬() ∨ > 0}., we have that ℐ (′) = 2 > ℐ (′) = 1 because both elements in ′ are self-contradictions, while for 3VL it suffices to assign (− 1) the value and both (− 2) and (− 3) the value to eliminate the inconsistency. In general, ℐ () ≤ ℐ () holds for all indefinite DBs because assigning to one of the disjuncts in an element that needs removal for ℐ suffices to eliminate the inconsistency for ℐ as well.
Finally, we define the database counterpart of the probabilistic measure that uses the PSAT
(probabilistic satisfiability) concept [48]. A PSAT instance is a set, Γ = { () ≥ | 1 ≤ ≤
}, that assigns probability lower bounds to a set {1, . . . , } of formulas; hence 0 ≤ ≤ 1
for 1 ≤ ≤ . A probability distribution over a set is a function : → [
finds the maximum probability lower bound that one can consistently assign to all
formulas in a knowledge base; if is equal to 1 then the knowledge base is consistent. In our
setting, it means interpreting a DB as a PSAT instance, where every element in the DB is assigned
probability , and every (ground) integrity constraint is assigned a probability 1. Thus, given
a DB , a set of integrity constraints , and a probability threshold ∈ [
Definition 4 (Probabilistic measure ℐ ). Given any DB and a set of integrity constraints , the
inconsistency measure ℐ is such that ℐ () = 1 − max {︀ ∈ [
Thus, ℐ () is one minus the maximum probability lower bound one can consistently assign to all elements in . For the database of our running example we have that ℐ () = 1 because the maximum probability that can be assigned to (the contradictory) element 2 is zero.
We investigate the data-complexity of the following three decision problems, which intuitively ask if a given rational value 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 ℐ (as shown in [48]).
Definition 5 (Lower (LV), Upper (UV), and Exact Value (EV) problems). Let ℐ be an IM. Given a DB over a fixed database scheme with a fixed set of constraints, and a positive value ∈ Q>0, LVℐ (, ) is the problem of deciding whether ℐ() ≥ . Given and a non-negative value ′ ∈ Q≥ 0, UVℐ (, ′) is the problem of deciding whether ℐ() ≤ ′, and EVℐ (, ′) is the problem of deciding whether ℐ() = ′.
We also consider the problem of determining the IM value.
Definition 6 (Inconsistency Measurement (IM) problem). Let ℐ be an inconsistency measure. Given a DB over a fixed database scheme with a fixed set of constraints, IMℐ () is the problem of computing the value of ℐ().
ℐ ℐ ℐ ℐ ℐ ℐ ℐ def.
LVℐ (, ) indefinite -c -h, Σ2-c -c -c -c def.
UVℐ (, ) indefinite
-c -h, Π2-c -c -c -c def.
EVℐ (, ) indefinite
-h, =
2-c =ℬ( ) -c -c def. # -c
IMℐ () indefinite
#· Σ2[] # -h, # · [ ]-c [ ]-c
A summary of the complexity results obtained for the above-mentioned problems is given
in Table 2. We found that while ℐ , ℐ , and ℐ become tractable for definite DBs and the
complexity of ℐ decreases, ℐ , ℐ and ℐ remain as hard as in the propositional case [
It is worth noting that almost all the results in Table 2 hold even if the set of integrity constraints
consists of FDs only. On the one hand, all the membership results trivially hold for FDs since
they have been shown to hold for DCs. On the other hand, all the hardness results except the
2-hardness for EVℐ , the -hardness for EVℐ , and the [ ]-hardness for IMℐ
can be shown to hold for FDs [
We have introduced a framework for measuring inconsistency in DBs that relies on absolute IMs,
measuring by some criteria the total amount of inconsistency. In contrast, relative IMs recently
explored in [53] provide a ratio of the amount of inconsistency w.r.t. some parameter, e.g. the
size of the DB. Many interesting issues concerning IMs in DBs remain unexplored. 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 DBs, and devise efficient algorithms for evaluating IMs. In this
regard, a dichotomy for FDs for the problem of computing the cost of a cardinality repair (that is
equivalent to computing the value of measure ℐ ) for definite DBs has been recently presented
in [54]. In fact, the polynomial-time 2-approximation given in [54] entails an approximability
result for the problem IMℐ . The IMs we have considered work at the tuple-level, without
distinguishing inconsistencies arising from different (sets of) attributes, which is another issue
we want to address in the future by following the idea of dimensional inconsistency measures
proposed in [55] for spatio-temporal databases, where the dimensions considered are those
concerning space, time, and (moving) objects [56, 57]. Finally, as indefinite DBs considered in
this paper allow the representation of a form of incomplete information (disjunctive information),
another interesting direction for future work is considering other forms of incomplete information
such as maybe information [
The classical classes Σ , Π and ∆ , with ≥ 0, are defined as follows [ 49]: i) Σ 0 = Π 0 = ∆ 0 = ; ii) Σ 1 = and Π 1 = ; iii) ∆ = Σ− 1 , Σ = Σ− 1 , and Π = Σ , ∀ > 0. Thus, (resp., ) denotes the class of the decision problems that can be solved in polynomial tMimoereboyveurs,inagdeacnisoiroanclperionbtlheemc ilΣsasisn+1b⊆yiaffdiettiesrmthiencisotnicju(nrecstpio.,nnoofna-dpertoebrmleimnΠ isinti +cΣ)1T⊆ uanridnga mpraocbhlienme. It holds that Σ ⊆ ∆ +1 ⊆ and Π ⊆ ∆ +1 ⊆ . in Π . 1 is also denoted as . It holds that ⊆ ∆ 2.
We also use the classes [59] and from the counting polynomial hierarchy defined in [50]. These classes rely on a counting quantifier defined as follows. Given a predicate (, ) with free variables and , (, ) holds iff |{ : (, ) is true}| ≥ , i.e., the counting quantifier is true for predicate and bound iff the number of values of such that (, ) holds is at least . The polynomially bounded version of the counting quantifier is defined as follows. Given a class of decision problems, we say that a problem is in iff there is a problem ∈ , a polynomial-time computable function , and a polynomial such that is a positive instance of iff ,(|)|≤ ()(, ) ∈ . That is, instance ∈ iff there are at least () many ’s whose size is polynomially bounded by that of such that a predicate for (, ) holds, with checking the predicate being in . The class coincides with the class of the decision problems that can be solved in polynomial time by a probabilistic Turing machine [59, 50]. The relationships between the classes , and are as follows: ⊆ and ⊆ . Differently from that is closed under union and intersection and is not known to be closed under complement, the class is closed under complement. Like , is closed under union and intersection, though this question remained open for several years [60]. Like , is closed under complement. It holds that ⊆ . Moreover, = ℬ( ), where ℬ( ) is the Boolean closure of [50], that implies that ⊆ ℬ ( ) and = . The class = is defined exactly as except that the counting quantifier holds iff it is satisfied by equality.
(resp., ) is the class of the function problems that can be solved by a deterministic (resp., non-deterministic) Turing machine in polynomial time. is the class of functions computableby a deterministic polynomial-time Turing machine using a -oracle. Thus, FP NP (resp., FP Σ2 ) 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 oracle (resp., Σ 2 oracle). If a logarithmic number of queries is asked by the machine, then we have the class FP NP[log ] (resp., FP Σ2[log ]).
Finally, given a class of decision problems, # · is the class of the counting problems defined by means of witness functions that assign to a given input a set () of witnesses. Herein, a counting problem returns the cardinality |()| of a set of witnesses. For the witness function , (i) for every input , the size of every witness ∈ () is polynomially bounded by that of ; and (ii) given and , deciding whether ∈ () is in class . A canonical problem for # · is counting the satisfying assignments of a SAT formula. This problem is in # [52], which coincides with # · . It holds that # · ⊆ # · and # · = # · ∆ 2.
The fist author acknowledges financial support from PNRR MUR project PE0000013-FAIR. Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A.
Kowalski, Part I, 2002, pp. 472–511. [20] M. Alviano, W. Faber, N. Leone, S. Perri, G. Pfeifer, G. Terracina, The disjunctive datalog system DLV, in: Proc. of International Workshop on Datalog, 2010, pp. 282–301. [21] O. Benjelloun, A. D. Sarma, A. Y. Halevy, M. Theobald, J. Widom, Databases with uncertainty and lineage, VLDB J. 17 (2008) 243–264. [22] C. Molinaro, J. Chomicki, J. Marcinkowski, Disjunctive databases for representing repairs,
Ann. Math. Artif. Intell. 57 (2009) 103–124. [23] 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 European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), 2007, pp. 103–114. [24] H. Decker, Inconsistency-tolerant database repairs and simplified repair checking by measure-based integrity checking, T. Large-Scale Data- and Knowledge-Centered Systems 34 (2017) 153–183. [25] H. Decker, S. Misra, Database inconsistency measures and their applications, in: Proc. of International Conference on Information and Software Technologies (ICIST), 2017, pp. 254–265. [26] H. Decker, Measuring database inconsistency, in: J. Grant, M. V. Martinez (Eds.), Measuring
Inconsistency in Information, College Publications, 2018, pp. 271–311. [27] H. Decker, D. Martinenghi, Classifying integrity checking methods with regard to inconsistency tolerance, in: Proc. of International Conference on Principles and Practice of Declarative Programming (PPDP), 2008, pp. 195–204. [28] H. Decker, D. Martinenghi, Inconsistency-tolerant integrity checking, IEEE Trans. Knowl.
Data Eng. 23 (2011) 218–234. [29] L. E. Bertossi, Measuring and computing database inconsistency via repairs, in: Proc. of
International Conference on Scalable Uncertainty Management (SUM), 2018, pp. 368–372. [30] L. E. Bertossi, Repair-based degrees of database inconsistency, in: Proc. of Logic Programming and Nonmonotonic Reasoning (LPNMR), 2019, pp. 195–209. [31] O. Issa, A. Bonifati, F. Toumani, Evaluating top-k queries with inconsistency degrees, Proc.
VLDB Endow. 13 (2020) 2146–2158. [32] O. Issa, A. Bonifati, F. Toumani, INCA: inconsistency-aware data profiling and querying, in: Proc. of International Conference on Management of Data (SIGMOD), 2021, pp. 2745– 2749. [33] E. Livshits, R. Kochirgan, S. Tsur, I. F. Ilyas, B. Kimelfeld, S. Roy, Properties of inconsistency measures for databases, in: Proc. of International Conference on Management of Data (SIGMOD), 2021, pp. 1182–1194. [34] K. Hausken, M. Mohr, The value of a player in n-person games, Soc. Choice Welf. 18 (2001) 465–483. [35] E. Livshits, B. Kimelfeld, The shapley value of inconsistency measures for functional dependencies, in: Proc. of International Conference on Database Theory (ICDT), volume 186, 2021, pp. 15:1–15:19. [36] F. Parisi, J. Grant, On measuring inconsistency in relational databases with denial constraints, in: Proc. of European Conference on Artificial Intelligence (ECAI), 2020, pp. 857–864. [37] J. Grant, F. Parisi, Measuring inconsistency in a general information space, in: Proc. of International Symposium on Foundations of Information and Knowledge Systems (FoIKS), 2020, pp. 140–156. [38] J. Grant, F. Parisi, General information spaces: measuring inconsistency, rationality postulates, and complexity, Ann. Math. Artif. Intell. 90 (2022) 235–269. [39] S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison-Wesley, 1995. [40] J. Minker, On indefinite databases and the closed world assumption, in: Proc. of the 6th
Conference on Automated Deduction, 1982, pp. 292–308. [41] J. Grant, J. Minker, Inferences for numerical dependencies, Theoretical Computer Science 41 (1985) 271–287. [42] M. Thimm, On the evaluation of inconsistency measures, in: J. Grant, M. V. Martinez (Eds.), Measuring Inconsistency in Information, College Publications, 2018, pp. 19–60. [43] A. Hunter, S. Konieczny, Measuring inconsistency through minimal inconsistent sets, in: Proc. of International Conference on Principles of Knowledge Representation and Reasoning (KR), 2008, pp. 358–366. [44] J. Grant, A. Hunter, Measuring consistency gain and information loss in stepwise inconsistency resolution, in: Proc. of European Conference Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), 2011, pp. 362–373. [45] M. Arenas, L. E. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases, in: Proc. of Symposium on Principles of Database Systems (PODS), 1999, pp. 68–79. [46] J. Grant, A. Hunter, Distance-based measures of inconsistency, in: Proc. of European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), 2013, pp. 230–241. [47] G. Priest, Logic of paradox, Journal of Philosophical Logic 8 (1979) 219–241. [48] K. Knight, Measuring inconsistency, J. Philosophical Logic 31 (2002) 77–98. [49] C. H. Papadimitriou, Computational complexity, Addison-Wesley, Reading, Massachusetts, 1994. [50] K. W. Wagner, The complexity of combinatorial problems with succinct input representation,
Acta Inf. 23 (1986) 325–356. [51] L. A. Hemaspaandra, H. Vollmer, The satanic notations: counting classes beyond #P and other definitional adventures, SIGACT News 26 (1995) 2–13. [52] L. G. Valiant, The complexity of computing the permanent, Theor. Comput. Sci. 8 (1979) 189–201. [53] F. Parisi, J. Grant, Relative inconsistency measures for indefinite databases with denial constraints, in: Proc. of International Joint Conference on Artificial Intelligence (IJCAI), 2023. [54] E. Livshits, B. Kimelfeld, S. Roy, Computing optimal repairs for functional dependencies,
ACM Trans. Database Syst. 45 (2020) 4:1–4:46. [55] J. Grant, M. V. Martinez, C. Molinaro, F. Parisi, Dimensional inconsistency measures and postulates in spatio-temporal databases, J. Artif. Intell. Res. 71 (2021) 733–780. [56] J. Grant, F. Parisi, A. Parker, V. S. Subrahmanian, An agm-style belief revision mechanism for probabilistic spatio-temporal logics, Artif. Intell. 174 (2010) 72–104. [57] F. Parisi, J. Grant, On repairing and querying inconsistent probabilistic spatio-temporal databases, Int. J. Approx. Reason. 84 (2017) 41–74. [58] R. van der Meyden, Logical approaches to incomplete information: A survey, in: Logics for Databases and Information Systems (the book grow out of the Dagstuhl Seminar 9529: Role of Logics in Information Systems, 1995), 1998, pp. 307–356. [59] J. Simon, On the difference between one and many (preliminary version), in: Proceedings of Fourth Colloquium on Automata, Languages and Programming (ICALP), 1977, pp. 480–491. [60] R. Beigel, N. Reingold, D. A. Spielman, PP is closed under intersection, J. Comput. Syst.
Sci. 50 (1995) 191–202.