pith. sign in

arxiv: 2511.15623 · v2 · pith:IGUFRTDEnew · submitted 2025-11-19 · 💻 cs.DB · cs.AI· cs.LO

Sufficient Explanations in Databases and their Connections to Database Repairs

Leopoldo Bertossi , Nina Pardal This is my paper

Pith reviewed 2026-05-21 18:09 UTC · model grok-4.3

classification 💻 cs.DB cs.AIcs.LO
keywords sufficient explanationssufficiency degreedatabase repairsanswer set programmingcausality in databasesquery answeringinconsistent databasesattribution scores
0
0 comments X

The pith

Answer-set programs can specify sufficient explanations for why database queries return particular results and compute how sufficient each tuple is.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines sufficient explanations for individual database tuples relative to a query answer and introduces a numerical sufficiency-degree to measure their strength. It shows that these notions connect directly to the well-studied concept of database repairs used to restore consistency, as well as to causality-based necessary explanations. By encoding the definitions inside answer-set programs the authors obtain both a declarative specification and new algorithmic results for computing explanations. A reader would care because such explanations make opaque query outcomes interpretable and give a principled way to attribute responsibility when data are inconsistent or incomplete.

Core claim

We investigate the notion of sufficient explanation, and a sufficiency-degree as attribution score for database tuples in relation to query answering. We also investigate and exploit connections with database repairs as used for dealing with inconsistent databases; and with causality-based necessary explanations, obtaining new computational results. We show how to use answer-set programs to specify sufficient explanations and compute sufficiency-degrees.

What carries the argument

Sufficient explanations and sufficiency-degrees for tuples, encoded as answer-set programs and linked to minimal repairs of inconsistent databases.

If this is right

  • Explanations for query answers can be obtained by running standard answer-set solvers on an encoding of the database and query.
  • Connections to repairs yield new polynomial-time or fixed-parameter results for computing sufficiency-degrees in certain classes of queries.
  • Causality-based necessary explanations and sufficiency-degrees can be computed uniformly within the same logical framework.
  • Database repairs can be re-interpreted as explanations that minimize the change needed to support or refute a query result.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach could be extended to produce human-readable explanations by post-processing the answer sets returned by the solver.
  • Similar encodings might apply to provenance or lineage tracking in data workflows beyond classical relational queries.
  • If repairs and sufficient explanations coincide on many instances, existing repair algorithms could be reused for explanation tasks without new implementations.

Load-bearing premise

The formal definitions of sufficient explanation and sufficiency-degree translate directly into answer-set programs while preserving their intended meaning and remaining computationally feasible for the query classes considered.

What would settle it

A concrete database instance, query, and tuple for which an answer-set program either returns a sufficiency-degree that contradicts the paper's definition or fails to terminate on a small inconsistent database that admits a clear repair-based explanation.

read the original abstract

We investigate the notion of sufficient explanation, and a sufficiency-degree as attribution score for database tuples in relation to query answering. We also investigate and exploit connections with database repairs as used for dealing with inconsistent databases; and with causality-based necessary explanations, obtaining new computational results. We show how to use answer-set programs to specify sufficient explanations and compute sufficiency-degrees.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper defines sufficient explanations for database query answers along with a sufficiency-degree as an attribution score for tuples. It establishes formal connections between these notions and database repairs (for inconsistent databases) as well as causality-based necessary explanations, yielding new computational results. The authors further show how to encode sufficient explanations and compute sufficiency-degrees via answer-set programs.

Significance. If the claimed connections and ASP encodings hold with preserved semantics, the work would usefully link explanation mechanisms in databases to the mature repair and causality literatures, enabling new complexity results and practical computation via ASP solvers. The explicit ASP encodings constitute a strength for reproducibility and implementation.

major comments (1)
  1. [ASP encoding section] The section on ASP encodings of sufficient explanations and sufficiency-degrees: the claimed equivalence between stable models and the repair-based definition of sufficiency may fail to hold for queries involving negation-as-failure or aggregation, because stable-model semantics can admit spurious models or alter minimality conditions relative to the database-repair characterization. This would invalidate the derived complexity results and the central computational claim.
minor comments (1)
  1. [Abstract] The abstract could explicitly state the query classes (e.g., conjunctive queries with or without negation) for which the encodings and complexity results are claimed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive feedback on the ASP encoding section. We address the major comment below and will make the corresponding revisions to strengthen the presentation.

read point-by-point responses

  1. Referee: [ASP encoding section] The section on ASP encodings of sufficient explanations and sufficiency-degrees: the claimed equivalence between stable models and the repair-based definition of sufficiency may fail to hold for queries involving negation-as-failure or aggregation, because stable-model semantics can admit spurious models or alter minimality conditions relative to the database-repair characterization. This would invalidate the derived complexity results and the central computational claim.

    Authors: We appreciate the referee raising this point about the scope of the ASP encodings. The manuscript develops the repair-based definitions and the corresponding ASP programs primarily for conjunctive queries without negation-as-failure or aggregation; these are the query classes for which the standard database-repair semantics (minimal repairs) are directly characterized and for which our stable-model encodings are shown to preserve the required minimality conditions. For queries involving negation-as-failure or aggregation, additional safeguards would indeed be needed to prevent spurious models. We will revise the ASP section to explicitly state the query class under consideration, add a clarifying remark on the conditions under which the equivalence holds, and note that extensions to richer query languages are left for future work. This clarification will also be reflected in the statements of the complexity results. revision: yes

Circularity Check

0 steps flagged

No significant circularity: definitions and encodings are introduced independently before connections are derived

full rationale

The paper first defines sufficient explanations and the sufficiency-degree as new attribution scores for tuples relative to query answers, then separately encodes them in answer-set programs and links them to existing database repair and causality notions. No equation or central claim reduces by construction to a fitted parameter, self-referential definition, or load-bearing self-citation chain; the ASP encoding is presented as a computational vehicle for the independently stated database-theoretic concepts, and the derived complexity results rest on those external connections rather than on renaming or re-deriving the input definitions themselves. The work is therefore self-contained against standard database repair and ASP semantics benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on formal definitions of sufficient explanation and sufficiency-degree that are introduced in the paper, plus standard assumptions from database theory and answer-set programming semantics.

axioms (2)
  • domain assumption Standard semantics of answer-set programming can faithfully encode the notions of sufficient explanation and sufficiency-degree for the query classes considered.
    Invoked when the paper states that ASP can be used to specify and compute the explanations.
  • domain assumption Database repairs provide a meaningful connection to sufficient explanations for inconsistent data.
    The paper investigates and exploits this connection to obtain new computational results.

pith-pipeline@v0.9.0 · 5574 in / 1268 out tokens · 54685 ms · 2026-05-21T18:09:58.786827+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations

    cs.AI 2026-05 unverdicted novelty 5.0

    Establishes conceptual connections between consistency-based diagnosis and actual causality to advance explainable AI.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    and Vianu, V .Foundations of Databases

    Abiteboul, S., Hull, R. and Vianu, V .Foundations of Databases. Addison-Wesley, 1995

    work page 1995

  2. [2]

    and Capelli, F

    Amarilli, A. and Capelli, F. Tractable Circuits in Database Theory.SIGMOD Rec., 2024

    work page 2024

  3. [3]

    and Bertossi, L

    Azua, F. and Bertossi, L. The Causal-Effect Score in Data Management. Proc. 4th Con- ference on Causal Learning and Reasoning (CLeaR). Proc. Machine Learning Research 275:874–893, 2025

    work page 2025

  4. [4]

    Causality-Based Scores Alignment in Explainable Data Management

    Azua, F. and Bertossi, L. Causality-Based Scores Alignment in Explainable Data Manage- ment. arXiv Paper 2503.14469, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  5. [5]

    and Schwind, C

    Bertossi, L. and Schwind, C. Database Repairs and Analytic Tableaux.Annals of Mathe- matics and Artificial Intelligence, 2004, 40(1-2): 5-35

    work page 2004

  6. [6]

    Synthesis Lectures in Data Management

    Bertossi, L.Database Repairing and Consistent Query Answering. Synthesis Lectures in Data Management. Morgan & Claypool, 2011

    work page 2011

  7. [7]

    and Salimi, B

    Bertossi, L. and Salimi, B. From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back.Theory of Computing Systems, 2017, 61(1):191-232

    work page 2017

  8. [8]

    and Salimi, B

    Bertossi, L. and Salimi, B. Causes for Query Answers from Databases: Datalog Abduction, View-Updates, and Integrity Constraints.Int. J. of Approximate Reasoning, 2017, 90

    work page 2017

  9. [9]

    Database Repairs and Consistent Query Answering: Origins and Further De- velopments

    Bertossi, L. Database Repairs and Consistent Query Answering: Origins and Further De- velopments. Gems of PODS paper. In Proc. PODS 2019

    work page 2019

  10. [10]

    Second-Order Specifications and Quantifier Elimination for Consistent Query Answering in Databases

    Bertossi, L. Second-Order Specifications and Quantifier Elimination for Consistent Query Answering in Databases. Proc. SOQE WS, 2021, CEUR Proceedings V ol-3009, pp. 28-36

    work page 2021

  11. [11]

    Specifying and Computing Causes for Query Answers in Databases via Database Repairs and Repair Programs.Know

    Bertossi, L. Specifying and Computing Causes for Query Answers in Databases via Database Repairs and Repair Programs.Know. and Inf. Systems, 2021, 63(1):199-231

    work page 2021

  12. [12]

    and Lafourcade, P

    Bienvenu, M., Figueira, D. and Lafourcade, P. Shapley Revisited: Tractable Responsibility Measures for Query Answers. Proc. ACM on Management of Data, 2025, 3(2)112:1-26

    work page 2025

  13. [13]

    and Zick, Y

    Biradar, G., Izza, Y ., Lobo, E., Viswanathan, V . and Zick, Y . Axiomatic Aggregations of Abductive Explanations. Proc. AAAI 2024

    work page 2024

  14. [14]

    and Tan, W

    Buneman, P., Khanna, S. and Tan, W. C. Why and Where: A Characterization of Data Provenance.Proc. ICDT, 2001, pp. 316-330. 11

    work page 2001

  15. [15]

    and Schneider, M

    Calautti, M., Livshits, E., Pieris, A. and Schneider, M. The Complexity of Why-Provenance for Datalog Queries. Proc. ACM Manag. Data, 2024a, 2(2):83

    work page

  16. [16]

    and Schneider, M

    Calautti, M., Livshits, E., Pieris, A. and Schneider, M. Below and Above Why-Provenance for Datalog Queries. Proc. ACM Manag. Data 2024b, 2(5):211:1-211:21

    work page

  17. [17]

    and Schneider, M

    Calautti, M., Livshits, E., Pieris, A. and Schneider, M. Computing the Why-Provenance for Datalog Queries via SAT Solvers. Proc. AAAI, 2024c, pp. 10459-10466

    work page

  18. [18]

    and Meliou A

    Cibele, F., Gatterbauer, W., Immerman, N. and Meliou A. A Characterization of the Com- plexity of Resilience and Responsibility for Conjunctive Queries.PVLDB, 2016, 9(3)

    work page 2016

  19. [19]

    and Halpern, J

    Chockler, H. and Halpern, J. Y . Responsibility and Blame: A Structural-Model Approach. Journal of Artificial Intelligence Research (JAIR), 2004, 22:93-115

    work page 2004

  20. [20]

    and Pfeifer, G

    Eiter, T., Faber, W., Leone, N. and Pfeifer, G. The Diagnosis Frontend of the DLV System. AI Commun., 1999, 12(1-2):99-111

    work page 1999

  21. [21]

    Halpern, J. Y . and Pearl, J. Causes and Explanations: A Structural-Model Approach: Part 1.The British Journal for the Philosophy of Science, 2005, 56:843-887

    work page 2005

  22. [22]

    and Sintos, S

    Hu, X. and Sintos, S. Finding Smallest Witnesses for Conjunctive Queries. ICDT 2024

    work page 2024

  23. [23]

    and Marques-Silva, J

    Ignatiev, A., Narodytska, N. and Marques-Silva, J. Abduction-Based Explanations for Ma- chine Learning Models. Proc. AAAI, 2019, pp. 1511-1519

    work page 2019

  24. [24]

    and Kolaitis, Ph

    Kirousis, L. and Kolaitis, Ph. A Dichotomy in the Complexity of Propositional Circum- scription.Theory of Computer Systems, 2004, 37:695–715

    work page 2004

  25. [25]

    and Suciu, D

    Kumar Jha, A. and Suciu, D. Knowledge Compilation Meets Database Theory: Compiling Queries to Decision Diagrams.Theory Comput. Syst., 2013, 52(3): 403-440

    work page 2013

  26. [26]

    and Savo, D

    Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M. and Savo, D. F. Inconsistency-Tolerant Query Answering in Ontology-Based Data Access.J. Web Semant., 2015, 33:3-29

    work page 2015

  27. [27]

    Circumscription

    Lifschitz, V . Circumscription. InHandbook of Logic in Artificial Intelligence and Logic Programming, vol. 3, Oxford Science Publications, 1994, pp. 297-346

    work page 1994

  28. [28]

    Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics (extended version)

    Lopatenko, A. and Bertossi, L. Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics. Proc. ICDT, 2007, Springer LNCS 4353, pp. 179-193. Proofs of results can be found in arXiv paper 1605.07159

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  29. [29]

    Logic-Based Explainability in Machine Learning

    Marques-Silva, J. Logic-Based Explainability in Machine Learning. InReasoning Web. Causality, Explanations and Declarative Knowledge, Springer LNCS 13759, 2022

    work page 2022

  30. [30]

    and Suciu, D

    Meliou, A., Gatterbauer, W. and Suciu, D. Bringing Provenance to its Full Potential Using Causal Reasoning.Proc. Theory and Practice of Provenance (TaPP), 2011

    work page 2011

  31. [31]

    Moore, K

    Meliou, A., Gatterbauer, W. Moore, K. F. and Suciu, D. The Complexity of Causality and Responsibility for Query Answers and Non-Answers.Proc. VLDB, 2010, pp. 34-41

    work page 2010

  32. [32]

    Query-Answer Causality in Databases and its Connections with Reverse Rea- soning Tasks in Data and Knowledge Management

    Salimi, B. Query-Answer Causality in Databases and its Connections with Reverse Rea- soning Tasks in Data and Knowledge Management. PhD Thesis in Comp. Sci., Carleton Univ., 2015

    work page 2015

  33. [33]

    and Van den Broeck, G

    Salimi, B., Bertossi, L., Suciu, D. and Van den Broeck, G. Quantifying Causal Effects on Query Answering in Databases. Proc. 8th WS on the Theory And Practice of Provenance (TaPP), 2016

    work page 2016

  34. [34]

    and Porter, B.Handbook of Knowledge Representation

    van Harmelen, F., Lifschitz, V . and Porter, B.Handbook of Knowledge Representation. Elsevier, 2008

    work page 2008

  35. [35]

    and Koch, C.Probabilistic Databases

    Suciu, D., Olteanu, D., Re, C. and Koch, C.Probabilistic Databases. Synthesis Lectures on Data Management, Morgan & Claypool, 2011. 12 A Proofs of Results Proof of Proposition 1.(⇒) Assume thatMSS={S 1, . . . , Sm}contains all MSSs for¯a, and there existsS∈MSSwitht∈S. Consider an arbitraryΓ⊆D n such that, for everyS i ∈ SwhereS i ̸=S, it holdsΓ∩S i ̸=∅and...

    work page 2011