Tuple Inconsistency Measures: Toward Explaining Query Answers

1 Introduction

In real-world applications, databases often violate semantic requirements, especially under rapid data growth and integration. These requirements are formalized as integrity constraints (e.g., functional dependencies, denial constraints) that encode domain knowledge. Constraint violations lead to data inconsistencies, yet fully repairing a database is often impractical due to the exponential number of possible repairs. To assess the severity of violations or guide repair selection, quantitative metrics known as inconsistency measures are employed [Livshits et al., 2021b; Issa et al., 2020].

Inconsistency measures, recently studied in the database literature, can be broadly categorized into three classes. The first quantifies conflicts of an entire database [Parisi and Grant, 2020; Livshits et al., 2021b; Parisi and Grant, 2023], providing a global data quality assessment that distinguishes data sources, but cannot capture how individual tuples contribute to overall inconsistency. The second, tuple measures, evaluates each tuple's participation in constraint violations [Issa et al., 2020; Livshits and Kimelfeld, 2022] and is particularly valuable for tasks such as tuple ranking and data cleaning. The third class, query answer measures, quantifies the inconsistency associated with individual query answers [Issa et al., 2020]. The first two classes of inconsistency measures have been extensively studied in knowledge representation [Hunter and Konieczny, 2010; Mu, 2018; Raddaoui et al., 2024; Kuhlmann et al., 2025; Straßer et al., 2025], and the third is specific for databases and applications, e.g., [Corea and Thimm, 2020; Ribeiro and Thimm, 2021; Corea et al., 2024].

This paper focuses on the second and third aforementioned classes. Our goal is to systematically analyze and compare different inconsistency measures, both theoretically and empirically. Based on existing and new desiderata, we show that current measures are either too coarse-grained or fail to meet some intuitive logical properties. To address these shortcomings, we propose a class of fine-grained inconsistency measures and ultimately identify a measure that satisfies all the axiomatic properties. Moreover, our answer inconsistency measures investigate how much query results inherit conflicts from the underlying database, which complements the only existing proposal in this category [Issa et al., 2020].

Our contributions are fourfold: We propose three novel tuple inconsistency measures and prove that one of them, IMPIM, satisfies all properties expected from a reasonable measure (Section 3). Building on these tuple measures, we develop an extensible framework to quantify the inconsistency of query answers using different answer explainability methods. We further show that a subset of these measures satisfies the proposed criteria for answer-level inconsistency (Section 4). We present a data complexity analysis of both tuple and answer measures, identifying tractable cases that facilitate practical deployment (Section 5). We perform a comparative experimental evaluation to show the feasibility of our tuple and answer inconsistency measures. In particular, we show that IMPIM and ICQA IM shap provide useful discrimination for tuples and answers, respectively, w.r.t. their inconsistency levels, while exhibiting promising scalability (Section 6).

2 Preliminaries

A database schema S defines the structural design of a database and it specifies a finite set of relation schemas. Each relation schema R is associated with a type type(R), a finite set of attributes {R.A1, . . . ,R.An}, where each attribute is prefixed by the relation name. The arity of a relation R is its type cardinality. A tuple t is a sequence of attribute-value pairs (A1 :a1, . . . , An :an).

A database instance (or database) I over a schema S maps each relation R ∈ S to a finite set of tuples of type(R), denoted I|R. We treat I as a set of tuples with possibly different types. We assume all attributes share a common domain dom, a countably infinite set of constants. The active domain of I, denoted dom(I), is the set of constants appearing in I. A valuation ν over I for a vector/tuple of variables ⃗x =(x1, . . . , xn) is a tuple (a1, . . . , an) such that each ν(xi) = ai∈dom(I). We use R(⃗x) to denote a relational atom, where ⃗x matches the arity of R.

A condition is a comparison f(⃗x) ⋆ g(⃗x), where f and g are functions (constant and string function included), and ⋆ is a classical comparator, for instance among =, ̸=,≤,≥,<,>. Conditions are used in denial constraints as follows:

Definition 1. A denial constraint δ has the form ∀⃗x ¬[R1( ⃗ u1) ∧ · · · ∧ Rk( ⃗ uk) ∧ ϕ(⃗x)] where ⃗ ui (1 ≤ i ≤ k) is a tuple of variables, ⃗x captures all the variables appearing in ⃗ u1, . . . , ⃗ uk, and ϕ(⃗x) = C1 ∧ . . . ∧ Cl (l ≥ 1) is a conjunction of conditions over ⃗x. Moreover, for any i,j s.t. 1 ≤ i ̸= j ≤ k, the tuples ⃗ ui and ⃗ uj do not share variables. We write ∆ for a set of denial constraints.

Given a database I and a set of denial constraints ∆, conjunctive queries can be used to check the consistency of I w.r.t. ∆, and more generally for posing queries over I.

Definition 2. A conjunctive query q(⃗y) is defined as an expression of the form R1( ⃗ u1) ∧ · · · ∧ Rk( ⃗ uk) ∧ ϕ(⃗x) subject to the same conditions as in Definition 1, where ⃗y is a subvector of variables in ⃗x. The result q(⃗y) over an instance I, i.e., the set of query answers, is: q(⃗y)(I) = {ν(⃗y) | ∀i ∈ [1, k], ν(ui) ∈ Ri, and ∀j ∈ [1, l], Cj(ν(⃗x)) is true} for valuations ν of ⃗x over I and conditions Cj in ϕ.

When used for finding conflicting tuples, Definition 2 is derived by negating the expression in Definition 1. For simplicity, we denote by q(I) the set of answers returned by the query q(⃗y) when evaluated over the instance I. The query q(⃗y) is called a boolean query when ⃗y is empty. Given a denial constraint δ ∈ ∆, we write qδ for the boolean query associated with δ in the obvious manner. I satisfies δ, denoted I |= δ, if qδ (I) is empty. We also write I |= ∆ if I satisfies all constraints in ∆. We now introduce two key concepts for reasoning about inconsistencies in Symbolic AI: minimal inconsistent sets and minimal correction sets [Reiter, 1987].

Definition 3. A subset I ′ ⊆ I is a minimal inconsistent set for I w.r.t. δ ∈ ∆ if I ′ ̸|= δ and ∀ I ′′ ⊂ I ′ , I ′′ |= δ. A subset I ′ ⊆ I is a minimal inconsistent set for I w.r.t. ∆ if I ′ ̸|=∆ and ∀I ′′ ⊂ I ′ , I ′′ |=∆.

Definition 4. A subset I ′ ⊆ I is a minimal correction set for I and ∆ if I \ I ′ |=∆ and ∀t ∈ I ′ , (I \ I ′ ) ∪ {t} ̸|=∆.

The set of all minimal correction sets for I w.r.t. ∆ is denoted by MIC(I,∆). The set of all minimal inconsistent sets for I w.r.t. δ (resp. ∆) is denoted by MIS(I, δ) (resp. MIS(I, ∆)). We write ⊎δ∈∆ MIS(I, δ) for the multiset union of all minimal inconsistent subsets for I w.r.t. δ ∈ ∆. Given a tuple t ∈ I, we define MIS(t, I,∆) = {M ∈ MIS(I,∆) | t ∈ M}, and MIC(t, I,∆) = {M ∈ MIC(I,∆) | t ∈ M}.

A tuple t ∈ I is called free w.r.t. ∆ if t does not belong to any set M ∈ MIS(I, δ) for any δ ∈ ∆. We write Free(I, ∆) for the set of free tuples in I given ∆.

Example 1. Consider a database with relations R1,R2,R3 containing PhD candidate information as given in Figure 1. Tuples are assigned unique identifiers, i.e., t1, . . . , t15. We consider the following denial constraints:

δ1 : ¬[R1(x1, y, z) ∧ R2(x2, v, u) ∧ x1 = x2 ∧ z ≥ u] δ2 : ¬[R1(x1, y, z) ∧ R2(x2, v, u) ∧ x1 = x2 ∧ u - z < 3 ∧ z > 2020] δ3 : ¬[R1(x1, y, z) ∧ R2(x2, w, r) ∧ R3(x3, v, u) ∧ x1 = x2 ∧ x1 = x3 ∧ y > v ∧ r - u < 1]

Intuitively, the constraint δ1 ensures that graduation must occur after admission; δ2 imposes a condition on students admitted after 2020, preventing them from graduating within three year; and δ3 disallows graduating the same year as candidacy when the qualification grade is lower than the admission grade. We have MIS(I,∆) = {{t1, t6}, {t2, t6}, {t5, t9}, {t5, t10}, {t4, t8, t13}}. Observe that {t5, t10, t14} ̸∈ MIS(I,∆), but {t5, t10, t14} ∈ ⊎δ∈∆MIS(I, δ) since it belongs to MIS(I, δ3), while its subset {t5, t10} already violates δ2. This shows that MIS(I,∆) is not always ⊎δ∈∆ MIS(I, δ) (see Proposition 1).

Proposition 1. MIS(I, ∆) ⊆ ⊎δ∈∆ MIS(I, δ).

Given a query q(⃗y), [Buneman et al., 2001] introduced the concept of why-provenance to formally explain the answers of q(⃗y) by tracing the lineage of the results.

Definition 5. The why-provenance of an answer tuple ans ∈ q(I), denoted by WhyP(I, q, ans), is the set of minimal (w.r.t. set inclusion) subsets I ′ ⊆ I such that ans ∈ q(I ′ ).

Example 2 (Example 1 contd.). Consider the query qex(x) : R1(x, y, z) ∧ R2(x, y1, z1) ∧ R3(x, y2, z2). The last table in Table 1 lists the query result with its provenance.

3 Tuple InconsistencyMeasures

Tuple inconsistency measures quantify the degree to which an individual tuple contributes to denial constraint violations in a database instance. Existing approaches generally distinguish between absolute and relative measures [Besnard and Grant, 2020]; in this work we focus on absolute measures.

Let I denote the set of all database instances over a given schema S, and define I = {(t, I, ∆) | I ∈ I, t ∈ I}.

Definition 6. A tuple inconsistency measure is a function IM on I that associates a real value to each tuple t ∈ I w.r.t. a set of denial constraints ∆, i.e., IM : I →R+0 .

Intuitively, the more a tuple t participates in violations of denial constraints, the higher the value IM(t, I,∆) it receives. Usually, we expect IM to satisfy a few basic properties: IM(t, I,∆) = 0 if I |= ∆ or if t ∈ Free(I,∆), and that IM is always finite in all cases, i.e., IM(t, I,∆) < ∞. While these properties (also known as rationality postulates) are typically easy to satisfy, other intuitive criteria become challenging. We adapt to the database setting the following four important desiderata from [Raddaoui et al., 2024]:

Free Tuple Independence (FI): If t′ ∈ Free(I ∪ {t′ },∆), for any t ∈ I it holds that IM(t, I,∆) = IM(t, I ∪ {t′ },∆).

That is, adding a free tuple to the database instance does not change the inconsistency score of existing tuples.

Positivity (PO): If t ∈ MIS(I, δ) for some δ ∈ ∆, then IM(t, I,∆) > 0. This ensures that tuples involved in constraint violations receive a positive inconsistency score, in contrast to free tuples, whose inconsistency measure is zero. Centrality Conflict (CC): If t, t′ ∈ I such that I \ {t} |= ∆ and I \ {t′ } ̸|= ∆, then IM(t, I,∆) > IM(t′ , I,∆). If removing t resolves all inconsistencies but removing t′ does not, then t should have a higher inconsistency value. This property distinguishes tuples whose removal suffices to restore consistency from those whose removal does not.

Data Monotonicity (DM): For any t ∈ I ′ ⊆ I, it holds that IM(t, I ′ , ∆) ≤ IM(t, I, ∆). Adding tuples to a database cannot reduce the inconsistency value of a tuple. The rationale is that violations can only increase when database grows; hence, IM should be monotone w.r.t. instance extension.

Now, we show that these properties pose substantial challenges for the tuple measure IMCBM [Issa et al., 2020] as well as for several measures adapted from Symbolic AI [Hunter and Konieczny, 2010; Ribeiro and Thimm, 2021; Raddaoui et al., 2024].

Definition 7 (IMCBM[Issa et al., 2020]). The Constraint-based Bag Semantics tuple inconsistency measure (IMCBM) of a tuple t∈I is defined as IMCBM(t, I, ∆) = ∑δ∈∆ 1t∈⋃ MIS(I,δ), where 1A returns 1 if the logical assertion A holds, and 0 otherwise.

Proposition 2. IMCBM satisfies all the properties except CC. Definition 8 (KB Tuple Measure). The knowledge base (KB) tuple inconsistency measures of a tuple t ∈ I are defined as:

• IMd(t, I,∆) = 0 if MIS(t, I,∆) = ∅; and 1 otherwise.
• IMdr(t, I,∆) = max{1/|M| | M ∈ MIC(t, I,∆)} if MIC(t, I, ∆) ̸= ∅; and 0 otherwise.
• IM#(t, I,∆) = |MIS(t, I,∆)|
• IMP (t, I,∆) = | ⋃M∈MIS(t,I,∆) M|
• IMMIS(t, I,∆) = ∑M∈MIS(t,I,∆) 1 |M|

Proposition 3. All KB tuple measures satisfy FI, but not PO.

Next, we extend the Shapley tuple measure, originally proposed by [Livshits and Kimelfeld, 2022] in the context of functional dependencies, to the setting of denial constraints.

Definition 9. The Shapley tuple inconsistency measure of a tuple t ∈ I is defined as follows: IMhshap (t, I,∆) =

where h(I,∆) is an inconsistency measure for the database I w.r.t. ∆. We consider two variants of h: hMIS(I,∆) =

|MIS(I, ∆)| and hP (I, ∆) = | ∪M∈MIS(I,∆) M|, resulting in two Shapley tuple measures, denoted IM MIS shap and IMPshap .

Note that [Livshits and Kimelfeld, 2022] showed that these two choices of h yield tractable measures. The same tractability result also holds for denial constraints (see Section 5).

Proposition 4. IM MIS shap and IMPshap satisfy CC and DM, but violate PO and FI.

Violating some of these four desiderata may lead to counter-intuitive behavior, as illustrated in the next example.

Example 3 (Example 1 contd.). Given I = {R1,R2,R3}, one can observe that I is inconsistent w.r.t. δi (1 ≤ i ≤ 3) with MIS(I, δ1) = {{t1, t6}, {t2, t6}}, MIS(I, δ2) = {{t5, t9}, {t5, t10}}, and MIS(I, δ3) = {{t4, t8, t13}, {t5, t9, t14}, {t5, t9, t15}, {t5, t10, t14}, {t5, t10, t15}}. We have IMCBM(t5, I, δ2) = IMCBM(t9, I, δ2) = IMCBM(t10, I, δ2) = 2, indicating that t5, t9, and t10 have the same contribution to the violation of δ2 according to IMCBM. However, removing t5 makes I consistent with δ2, whereas removing t9 (or t10) does not. The same situation arises for t1, t2, and t6 w.r.t. δ1, illustrating the impact of the failure of CC for IMCBM. Moreover, we have IM(t14, I,∆) = IM(t15, I,∆) = 0 for any measure IM defined in Definitions 8 and 9, in violation of PO.

In what follows, we introduce new tuple inconsistency measures to investigate whether the four postulates are compatible, i.e., jointly satisfiable by a tuple measure.

3.1 Fine-Grained Tuple InconsistencyMeasures

To address the limitations of existing tuple inconsistency measures, we introduce a novel family of measures that employ the internal structure of denial constraints to more accurately assess each tuple's contribution to constraint violations.

Condition-based Inconsistency Measure

Our first tuple inconsistency measure is designed to capture both the frequency with which a tuple appears in minimal inconsistent subsets of the database and the number of distinct constraint conditions it violates within each such subset.

Definition 10 (IMCIM). The condition-based inconsistency measure of t w.r.t. ∆ is defined as:

Before evaluating IMCIM, we require every denial constraint to be in a reduced form, obtained by grouping the conditions of a constraint into one condition for "equal" variables (e.g., x1=x2 ∧ x2=x3 is rewritten as x1=x2=x3), to ensure that syntactically different but logically equivalent constraints induce the same IMCIM value.

Example 4 shows that IMCIM effectively addresses the issue highlighted in Example 3. However, this observation does not hold in general, as shown by Proposition 5.

Example 4 (Examples 1 and 3 contd.). Let us focus on Column 2 and 3 of Table 2. Tuple t5 receives the highest IMCIM score 14, as it is involved in multiple violations of both δ2 and δ3, and it contributes to a greater number of violated conditions than any other tuple. In contrast, t9 and t10 make weaker overall contributions to inconsistency, despite their participation in violation of both δ2 and δ3. This behavior cannot be captured by IMCBM, since IMCBM(t5, I,∆) = IMCBM(t9, I, ∆) = IMCBM(t10, I, ∆) = 2.

Proposition 5. IMCIM satisfies FI, PO and DM, but fails CC.

Responsibility-based Inconsistency Measure

Proposition 5 shows that condition-level granularity is insufficient to distinguish tuples whose removal restores consistency from those that do not, as required by the CC property. To address this limitation, we introduce a novel measure inspired by causality theory [Meliou et al., 2010], enabling a more precise individual tuple inconsistency quantification.

Given a denial constraint δ and its corresponding boolean query qδ , we consider the responsibility measure as defined in the context of query explainability [Meliou et al., 2010]. We first recall some additional concepts. A tuple t ∈ I is a counterfactual cause for an answer ans to a query q if ans ∈ q(I) and ans ̸∈ q(I \ {t}). A set Γ ⊆ I is a contingency set for t if t becomes a counterfactual cause for ans in I \ Γ. Using these notions, we define the responsibility of a tuple t ∈ I for violating δ as: ρ(t, δ) = (1 + minΓ(t,qδ ) |Γ(t, qδ )|)-1 , where Γ(t, qδ ) ranges over all contingency sets for which t is a counterfactual cause of the true answer to qδ . Notice that, if a tuple t does not violate a constraint δ, there is no contingency set for t, and we set ρ(t, δ) = 0.

Using the notion of responsibility, we now define our tuple inconsistency measure that accounts for both how frequently a tuple is involved in denial constraint violations and the strength of its contribution to each such violation.

Definition 11 (IMRIM). The responsibility-based inconsistency measure of t w.r.t. ∆ is defined as: IMRIM(t, I,∆) = ∑δ∈∆ ρ′ (t, δ) × |MIS(I, δ)| where ρ′ (t, δ) = ρ(t,δ)/∑t′∈⋃ MIS(I,δ) ρ(t′ ,δ).

Example 5 (Example 1 contd.). As illustrated in Table 2, the measure IMCIM assigns identical inconsistency values to tuples t2 and t4, i.e., IMCIM(t2, I,∆) = IMCIM(t4, I,∆) = 2. However, by IMRIM we have IMRIM(t2, I,∆) = 1/2 < 3/4 = IMRIM(t4, I,∆), thereby providing a more nuanced and informative differentiation.

Proposition 6. IMRIM satisfies FI, PO, and CC, but fails DM.

Proposition 6 highlights a key advantage of IMRIM over IMCBM and IMCIM measures, namely that it satisfies CC. However, it still fails to satisfy DM.

Provenance-based Inconsistency Measure

In this section, we present a tuple measure that satisfies all the properties studied in this paper (see Table 3). The intuition behind this new measure is that it quantifies the violation of a tuple with each constraint δ by using the sizes of minimal inconsistent sets containing it. More formally:

Definition 12 (IMPIM). The provenance-based inconsistency measure of t w.r.t. ∆ is defined as: IMPIM(t, I,∆) = ∑M∈⊎δ∈∆MIS(I,δ) 1 |M| · 1t∈M.

Example 6. By Table 2, IMPIM(t2, I,∆) = 1/2 and IMPIM(t14, I,∆)=2/3, even though these two tuples receive the same IMRIM value. Specifically, t2 violates δ1 and t14 violates δ3; however, t2 appears in only one set in MIS(I, δ1), whereas t14 occurs in two sets in MIS(I, δ3). This difference explains the discrepancy in their IMPIM values. Tuple t5, which violates two constraints and occurs in 6 sets in ⊎δ∈∆MIS(I, δ), receives the highest inconsistency value.

It is important to highlight the key distinction between IMPIM and IMMIS (Definition 8) is that IMMIS overlooks certain "iceberg" violations that cannot be detected in MIS(I, ∆) (see Example 1). This limitation prevents IMMIS from ensuring PO, a requirement that IMPIM does meet.

Proposition 7. IMPIM satisfies FI, PO, CC, and DM.

4 Application: Explaining Query Answers

Building on tuple inconsistency measures, we propose a formal framework that quantifies the InConsistency of a Query Answer (ICQA) by systematically aggregating the inconsistencies of its contributing tuples. This aggregation is parameterized by a tuple inconsistency measure, and (ii) an answer explainability method, for a versatile family of instantiations. Our framework generalizes the only existing proposal for quantifying inconsistency of query answers [Issa et al., 2020].

Given a conjunctive query q and ans ∈ q(I) over a database I subject to a set of denial constraints ∆, our generic inconsistency measurement for query answers is denoted by ICQA IM X (q, ans, I,∆), where X specifies the answer explanation method and IM denotes the tuple inconsistency measure. Below, we define several instantiations of this framework. For ease of notation, we denote ICQA IM X (q, ans, I,∆) simply as ICQA IM X whenever the context allows. We start by our first instantiation of ICQA, based on provenance.

Definition 13. The provenance based ICQA for an answer ans to a query q over the database I, denoted ICQA IM Prov , is: ICQA IM Prov = ∑M∈WhyP(I,q,ans) ∑t∈M IM(t, I, ∆).

In Definition 13, the outer summation over M ∈ WhyP(I, q, ans) explicitly aggregates across all the derivations of the answer ans. Using summation rather than a max-operator ensures that the measure reflects the cumulative inconsistency contributions of all supporting derivations, instead of being dominated by a single most inconsistent derivation. In this way, ICQA IM Prov captures a more complete provenance picture and enables finer discrimination among answers. Note that the inconsistency measure proposed by [Issa et al., 2020] is a special case of Definition 13 by instantiating the tuple measure with IMCBM, as detailed below.

Proposition 8. Let CBM be the answer measure defined in [Issa et al., 2020] (Definition 4). It holds CBM = ICQA IMCBM Prov .

Shapley values [Shapley, 1953] are useful in various settings, including knowledge representation and databases [Hunter and Konieczny, 2010; Livshits and Kimelfeld, 2022]. As a second instantiation of our ICQA framework, we adapt Shapley values for inconsistent query answers.

Definition 14. The Shapley based ICQA for an answer ans to a query q over the database I, denoted ICQA IM shap , is:

where πI\{t} denotes all permutations of tuples in I\{t}, the marginal ∇v = v(I ′ ∪ {t}) - v(I ′ ) with the wealth function v(·) returns 1 if ans ∈ q(·), and 0 otherwise.

Notably, unlike the formulation of [Livshits et al., 2021a], our value function v(·) is defined w.r.t. each individual answer rather than the complete query result set.

The final ICQA instantiation combines responsibility with tuple measures to quantify answer inconsistency.

Definition 15. The responsibility based ICQA for an answer ans to a query q over the database I, denoted ICQA IM Resp , is: ICQA IM Resp = ∑t∈⋃ WhyP(I,q,ans) ρ(t) · IM(t, I,∆), where

To assess the suitability of measures for quantifying queryanswer inconsistency, we introduce the following properties. Blamelessness: ICQA IM X (q, ans, I,∆) = 0 if and only if ⋃M∈WhyP(q,ans,I) M ∩ ⋃M′∈⊎δ∈∆MIS(I,δ) M ′ = ∅. Only answers with violation-free provenance are blameless (i.e., score 0). Otherwise, they have a positive ICQA IM X score.

Additivity: For two queries q1(⃗y), q2(⃗y) of the same arity, if ans ∈ q1(I) ∩ q2(I), then ICQA IM X (q1 ∨ q2, ans, I,∆) ≤ ICQA IM X (q1, ans, I,∆) + ICQA IM X (q2, ans, I,∆). Combining queries should not increase the inconsistency of an answer beyond the sum of individual inconsistencies. Indeed, the provenance of q1 ∨ q2 is the union of the provenances of q1 and q2, introducing no additional sources of inconsistency.

In particular, additivity ensures that answers with a score 0 for both queries retain a score 0 under their disjunction.

Monotonicity: For any I ′⊆I, ICQA IM X (q, ans, I ′ ,∆) ≤ICQA IM X (q, ans, I,∆). Intuitively, monotonicity ensures that an answer cannot become more inconsistent after removing tuples from I. This is desired because inconsistency stems from constraint violations, and removing data from the database can only eliminate or reduce such violations.

Proposition 9. ICQA IM X satisfies Blamelessness for any explainability method X and tuple inconsistency measure IM. Moreover, ICQA IM Prov satisfies Additivity for any IM, and Monotonicity if IM satisfies Data Monotonicity.

5 Computational Complexity Analysis

We study the following complexity problems, given k ≥ 0: TUPLE-MEASURE: is IM(t, I,∆) > k?

ANSWER-MEASURE: is ICQA IM

X (q, ans, I,∆) > k?

For each denial constraint δ ∈ ∆, we assume that MIS(I, δ) is given; it can be computed efficiently by evaluating the conjunctive query qδ associated to δ.

To facilitate our analysis, we introduce the following terms:

(I) MisConstant: |MIS(I,∆)| < c for some constant c, (II) FixedSize-Disj: for eachMi ̸=Mj ∈ MIS(I,∆), |Mi| = |Mj| and |Mi ∩Mj| ≤ 1.

5.1 Complexity of Tuple Measures

[Livshits and Kimelfeld, 2022] prove that IMPshap and IM MIS shap are in PTime for functional dependencies. Our next result extends this to denial constraints for which either MisConstant or FixedSize-Disj holds. Indeed, if ∆ contains only functional dependencies, then MIS(I,∆) satisfies FixedSize-Disj as |Mi| = 2, which implies |Mi ∩Mj| ≤ 1.

Proposition 10. IMPshap and IM MIS shap are PTime if MIS(I,∆) satisfies MisConstant. Moreover, IM MIS shap is PTime if FixedSize-Disj holds.

The case of IMPshap follows analogously to [Livshits and Kimelfeld, 2022]. For IM MIS shap , the minimal inconsistent subsets contributing to its value are of size two for functional dependencies, whereas they can be of arbitrary size for denial constraints. We can prove that deciding such subsets remains polynomial under MisConstant and FixedSize-Disj.

Proposition 11. IM is in PTime for IM ∈ {IMd, IM#, IMP , IMMIS}, and coNP-Complete for IMdr unless |MIC(I,∆)| < c for a constant c.

Given MIS(I,∆), IMd, IM#, IMP and IMMIS are computed by scanning the set MIS. For IMdr, MIC corresponds to minimal hitting sets of MIS(t, I,∆); deciding the existence of a bounded one is NP-complete, yielding coNP-completeness. If |MIC| is bounded, enumeration is polynomial.

Proposition 12. IMCIM and IMPIM are PTime, and IMRIM is NP-hard.

IMCIM and IMPIM are computable by polynomial scans on violation sets. NP-hardness of IMRIM follows from the causal responsibility for conjunctive queries [Meliou et al., 2010].

5.2 Complexity of Answer Measures

Recall that an ICQA measure depends on the tuple measure and on the aggregation method of each tuple contribution to the query answer. For conjunctive queries with equality comparisons only, the following tractability result holds.

Proposition 13. ICQA IM Prov has the same complexity as IM. In particular, ICQAyProv are in PTime for y ∈ {IM MIS shap , IMPshap }.

ICQA IM Prov aggregates tuple scores over WhyP(I, q, ans), which is PTime computable. Since aggregation is linear, the complexity matches that of IM.

Proposition 14. For a hierarchical boolean conjunctive query without self-joins (see [Livshits et al., 2021a]), the complexity of ICQA IM shap matches that of the underlying measure IM. Otherwise, it is FP#P-complete.

The computation reduces to the Shapley value of a Boolean query q′ induced by ans. By [Livshits and Kimelfeld, 2022], this is PTime for hierarchical queries without self-joins and FP#P-complete otherwise; the overall complexity follows.

Proposition 15. ICQA IM Resp is NP-hard in general, regardless IM. It becomes PTime for linear queries when combined with tractable IM (see Propositions 10,11,12).

This result follows from [Meliou et al., 2010], where responsibility is NP-hard in general and tractable for linear queries; combining with tractable IM yields the result.

6 Experimental Evaluation

The experiments are designed to assess three aspects of the proposed inconsistency measures. First, we examine their ability to discriminate among tuples w.r.t. their involvement in violations under varying inconsistency ratios and different sets of constraints. Second, we analyze the propagation of tuple inconsistency to query answers under multiple aggregation methods, assessing whether the resulting ICQA scores remain meaningful and stable. Third, we investigate the computational efficiency and scalability of the different measures.

All experiments are conducted on macOS 15.6.1 (M1 Max, 32GB RAM) with Python 3.11.14, DuckDB 1.4.3 as a DBMS, and TPC-H (https://www.tpc.org/tpch/) dbgen v3.0.1 for datasets generation. The source code of our experiments is available at https://github.com/yrGnote/tuple-measure-icqa.

Datasets. First, we generate database instances with scale factors SF ∈ {0.01, 0.05, 0.1}, yielding 'clean' datasets with 86.8k, 432.8k and 866.6k tuples, respectively. Second, we define two sets of denial constraints over the TPC-H schema, namely ∆1={δ1, δ2} and ∆2={δ1, δ2, δ3, δ4}, where:

δ1 :¬(L(ko, kp, ks, dship, dreceipt, dcmt, sl)∧dreceipt<dship )

δ2 :¬(L(k′o, kp, ks, dship, dreceipt, dcommit, sl)∧

O(ko, dorder, so) ∧ ko = k′o ∧ dcommit < dorder )

δ3 :¬(O(ko, dorder, so) ∧L(k′o, kp, ks, dship, drecp, dcmt, sl) ∧ ko = k′o ∧ so = 'F' ∧ sl ̸= 'F')

δ4 :¬(L(ko, kp, ks, dship, drecpt, dcmt, sl) ∧PS(k′p, k′s, qavl) ∧ P (k′′ p ) ∧ kp = k′p = k′′ p ∧ ks = k′s ∧ qavl < 0)

Starting from the three clean TPC-H instances, we inject synthetic violations of ∆1 and ∆2, choosing to modify each time, a single attribute appearing in the condition of each δ as follows: for δ1, we decrease the receipt date to enforce dreceipt < dship; for δ2 we set dcommit = dorder - 1; for δ3, we flip the lineitem status attribute sl from F to O and for δ4, we assign a negative available quantity qavl. Violations are injected on a sampled subset of tuples with ratios in {0.01%, 0.05%, 0.1%}, and sampling is repeated using 10 random seeds (affecting only tuple selection). Combining the 3 database scale factors (SF∈{0.01, 0.05, 0.1}), the 2 constraint subsets (∆1,∆2), the 3 inconsistency ratios (0.01%, 0.05%, 0.1%), and the 10 random sampling seeds, we finally obtain 180 test databases. We compute MIS for each δ by executing the SQL query qδ (see Section 2).

6.1 Evaluation of Tuple InconsistencyMeasures

We evaluate our three tuple inconsistency measures introduced in Section 3.1 and the competitor IMCBM over all 180 databases. While IMCIM, IMPIM, and IMCBM are obtained by direct computation over the set of MIS, for IMRIM the contingency set for each tuple t and each constraint equals to a minimum hitting set problem over the set of MIS that does not contain t. We use the CP-SAT solver for computing minimum hitting sets [Perron et al., 2023]. Time-limited solving gives a feasible solution and thus an approximate IMRIM value.

Measure Value Distribution. Figure 1 compares the distributions of all non-zero scored tuples from all databases w.r.t. the different tuple measures. The values of IMCBM are highly concentrated at 1, with a small fraction at 2. In contrast, IMCIM has a distribution with high density near the origin with a wide dynamic range, resulting from multiplying the number of violated conditions with the number of MIS the tuple participates in. The measures IMPIM and IMRIM lie between IMCBM and IMCIM: both retain variation in the scores (as opposed to IMCBM), while avoiding the heavy heads of IMCIM. Among the four measures, IMPIM shows the most balanced distributional footprint (frequency and CDF). IMRIM also has a smooth CDF, but is not as efficient as IMPIM.

To further quantify a measure's discrimination ability, we compute its (Gini coef/std) over all non-zero tuples across 180 databases. The results are: IMCBM (0.001/0.03), IMCIM (0.25/2.81), IMRIM (0.16/0.21), and IMPIM (0.23/0.42). The measure IMCBM is not very informative, IMCIM is quite unstable, and IMRIM is conservative. Interestingly, IMPIM provides the best balance between discrimination and dispersion.

Ranking Comparison. We further compare the four tuple measures through their induced inconsistent tuple rankings. For this, we use the Spearman's correlation ρ between two rankings. On the database with the setting sf0.1-∆10.1%-seed01, IMPIM and IMRIM are almost rank-equivalent (ρ ≈ 0.99), IMCBM is nearly independent from the other measures (ρ ≈ 0.07), and IMCIM induces an almost reversed ordering w.r.t. IMPIM and IMRIM (ρ ≈ -0.98). Only two tuples appear in all four rankings, suggesting that they are consistently identified as central contributors to inconsistency. The variation in the rankings of the other tuples reflects their different modes of involvement in inconsistencies.

Efficiency. Across the 180 databases, the average runtimes (std) are 0.0017s (0.0020) for IMCBM, 0.0032s (0.0026) for IMCIM, 0.0019s (0.0028) for IMPIM, and 15.1653s (32.6909) for IMRIM. IMCBM, IMCIM, and IMPIM are consistently fast and scalable, in contrast to IMRIM . Overall, IMPIM has the best quality-versus-efficiency trade-off.

6.2 Evaluation of ICQAMeasures

Our goal now is to assess whether the answer level ICQA scores constitute an indicator for distinguishing inconsistent answers, and how different aggregations and tuple measures jointly affect the distributional footprint, score resolution, and ranking of answers. Note that for Shapley-based ICQA, exact values are computed by enumerating all coalitions when |I ′ | ≤ 12; otherwise, they are approximated via Monte Carlo sampling with 10,000 permutations using a fixed seed.

We evaluate 5 SPJ queries over the TPC-H schema, with increasing structural complexity, ranging from single-table selections to multi-way joins involving up to 5 relations. For each query, 12 instantiated answer measures are computed over all 180 databases. Each instantiation yields a distribution over query answers, reflecting both the degree of inconsistency in the data and the selectivity of the measure.

Figure 2 presents normalized ICQA distributions (histograms and CDFs) for different aggregations combined with IMPIM, our most successful tuple inconsistency measure, based also on the previous experiments. Similar patterns are observed for the other three tuple measures. We observe that the explainability methods Prov and Resp concentrate ICQA mass on a few discrete values, resulting in steep CDF jumps and poor ranking discrimination. In contrast, shap yields high density near the origin distributions but with gradual CDF growth, thereby enabling more fine-grained differentiation.

The total time for computing all four tuple inconsistency measures for all tuples is 2730.98 seconds. Given the values for the tuple measures, the total time for computing ICQA over all answers for the five queries is: 17.13s for ICQAProv, 25.12s for ICQAshap, and 1118.77s for ICQAResp. Thus, ICQAProv and ICQAshap are quite fast, given the precomputed tuple measures. Considering both efficiency and discrimination, shap is the best aggregation method for ICQA.

7 RelatedWork and Conclusions

For tuple measures, both the Shapley-based approach [Livshits et al., 2021a] and the KB measures [Raddaoui et al., 2024] compute a tuple's average marginal contribution to constraint violations, providing finer granularity than IMCBM [Issa et al., 2020]. However, they still treat all tuples and constraints uniformly. Our approach advances this line of work by introducing provenance- and responsibility-based measures capturing nuanced violation weights at the tuple level, for more precise inconsistency scores. In particular, IMPIM satisfies all the desired properties, admits PTime computation, and shows promising empirical performance. Moreover, unlike [Ribeiro and Thimm, 2021], which reveals implicit inconsistencies via logical reasoning, our IMCIM measure focuses on explicit inconsistencies, a design that aligns with the absence of implicit derivations in typical databases.

For query answer measures, Shapley-based approaches have been applied to evaluate tuples' marginal contributions to query results, ranging from basic expectation of query answer counts [Reshef et al., 2020; Livshits et al., 2021a] to generalized weighted expected sums of minimal supports [Bienvenu et al., 2025]. Moreover, [Meliou et al., 2010] proposes to explain query (non)-answers based on actual causes and responsibility of tuples. In contrast, measuring inconsistency in an answer remains largely unaddressed. The closest approach ranks answers by inconsistency [Issa et al., 2020], which we include as a specific instance of our ICQA framework. Notably, our framework yields tractable measures (e.g. ICQA PIM Prov ) that fulfill desirable criteria. Our experiments show that the IMPIM and ICQA IM shap measures provide useful discrimination for tuples and answers, respectively, while showing promising scalability.

Acknowledgments

This work is supported by the National French Agency, under the EXPIDA-ANR-22-CE23-0017 project.