pith. machine review for the scientific record. sign in

arxiv: 2605.03954 · v1 · submitted 2026-05-05 · 💻 cs.DB · cs.AI

Recognition: unknown

Inconsistent Databases and Argumentation Frameworks with Collective Attacks

Yasir Mahmood , Jonni Virtema , Timon Barlag , Axel-Cyrille Ngonga Ngomo
Authors on Pith no claims yet

Pith reviewed 2026-05-09 15:29 UTC · model grok-4.3

classification 💻 cs.DB cs.AI
keywords inconsistent databasesdatabase repairsargumentation frameworksSETAFtuple-generating dependenciesdenial constraintsintegrity constraintspreferred extensions
0
0 comments X

The pith

Repairs to inconsistent databases under denial constraints and local-as-view TGDs correspond to preferred extensions in SETAFs.

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

The paper establishes a direct mapping between subset-maximal repairs of inconsistent databases and acceptable argument sets in argumentation frameworks. For databases constrained by denial constraints together with a fragment of local-as-view tuple-generating dependencies, the repairs align with the preferred extensions of a SETAF built from the instance and constraints. When only the tuple-generating dependencies are present, a preprocessing step produces a single extension that is both stable and naive. The full combination of both constraint types requires preferred semantics exclusively, while denial constraints alone make naive, preferred, and stable extensions coincide. Inclusion dependencies and functional dependencies reduce to ordinary argumentation frameworks that use only pairwise attacks.

Core claim

Subset-maximal repairs under the considered fragment of tuple-generating dependencies correspond to the preferred extensions of the associated SETAF. For these dependencies, additional preprocessing allows computing a unique extension that is stable and naive. It is known that subset-maximal repairs under denial constraints correspond to the naive extensions, which coincide with the preferred and stable extensions in the resulting SETAFs. Allowing both types of constraints breaks this relationship, and even the pre-processing does not help as only preferred semantics captures these repairs. Functional dependencies do not require set-based attacks, and the same holds for inclusion dependency.

What carries the argument

The translation of a database instance and its denial constraints plus local-as-view TGDs into a SETAF, where arguments represent tuples and collective attacks encode constraint violations, so that repairs become the preferred extensions.

Load-bearing premise

The chosen local-as-view form of the tuple-generating dependencies and the denial constraints creates an exact one-to-one match between repairs and extensions without extra semantic restrictions.

What would settle it

A concrete database instance containing a local-as-view TGD whose subset-maximal repairs are not exactly the preferred extensions of the constructed SETAF would show the claimed correspondence does not hold.

Figures

Figures reproduced from arXiv: 2605.03954 by Axel-Cyrille Ngonga Ngomo, Jonni Virtema, Timon Barlag, Yasir Mahmood.

Figure 1
Figure 1. Figure 1: Hierarchy of ICs and syntactic form for most commonly studied constraints [10]. view at source ↗
Figure 2
Figure 2. Figure 2: Then extensions for F are also depicted in view at source ↗
Figure 2
Figure 2. Figure 2: Framework F from Example 4 (Left) and extensions for given semantics (Right). a b c e d view at source ↗
Figure 3
Figure 3. Figure 3: The SETAF S from Example 5. Set-Based Argumentation. Dung’s AFs can be generalized by allowing attacks not only from single arguments, but from collections of arguments [38]. A B-hypergraph (backwards hypergraph) is a directed hypergraph (V, E) where each edge goes from a set of nodes to a single node, i.e., E ⊆ 2 V × V . A set-based argumentation framework (SETAF) is a B-hypergraph F = (A, R) where A is t… view at source ↗
Figure 4
Figure 4. Figure 4: SETAF S⟨{C,O},D⟩ for Example 8. The attacker in each set-attack is depicted as a triangle of different color (for better presentation) and the attack is presented in the same color. E.g., the red triangle and the arrow depicts the attack ({t1, s1, s2}, t3). It is worth highlighting that given a set D of denial constraints as input, then checking whether “a database T ′ is a repair of a database T w.r.t. D”… view at source ↗
Figure 5
Figure 5. Figure 5: SETAF S⟨{E,D,P},L⟩ for Example 12. For brevity, we rename the LTGDs {lav1, lav2} to be {1, 2}. Moreover, the auxiliary arguments for source(1)-facts si are renamed to s1i and those for source(2)-facts tj to t2j . • {s1, u1} supports t1 for lav2, • {s3, u2} supports t2 for lav2. The respective SETAF S⟨{E,D,P},L⟩ is depicted in view at source ↗
Figure 6
Figure 6. Figure 6: Argumentation framework for modelling FDs in Example 22. view at source ↗
Figure 7
Figure 7. Figure 7: The AF FI modelling I in Example 26: the red self-loops together with blue arcs depict the attacks for each fact w ∈ T due to IDs i ∈ I and the black arcs model the attacks due to the support set Si(w). Definition 25. Let D = ⟨T , I⟩ be a constrained database including a database T and a collection I of IDs. Then FD is the following AF. • A := T ∪ {si | s is a source(i)-fact for i ∈ I}, • R := {(si , s),(s… view at source ↗
Figure 8
Figure 8. Figure 8: Argumentation framework without self-attacks for modelling IDs in Example 29. The auxiliary arguments are view at source ↗
Figure 9
Figure 9. Figure 9: Argumentation framework for modelling dependencies in Example 30. Black arcs depict conflicts due to view at source ↗
read the original abstract

The connection between subset-maximal repairs for inconsistent databases involving various integrity constraints and acceptable sets of arguments within argumentation frameworks has recently drawn growing interest. In this paper, we contribute to this domain by establishing a new connection when integrity constraints (ICs) include denial constraints and local-as-view tuple-generating dependencies. It turns out that SET-based Argumentation Frameworks (SETAFs), an extension of Dung's argumentation frameworks (AFs) allowing collective attacks, are needed. It is known that subset-maximal repairs under denial constraints correspond to the naive extensions, which also coincide with the preferred and stable extensions in the resulting SETAFs. Our main findings establish that repairs under the considered fragment of tuple-generating dependencies correspond to the preferred extensions. Moreover, for these dependencies, additional preprocessing allows computing a unique extension that is stable and naive. Allowing both types of constraints breaks this relationship, and even the pre-processing does not help as only preferred semantics captures these repairs. Finally, while it is known that functional dependencies do not require set-based attacks, we prove the same regarding inclusion dependencies. Thus, one can translate inconsistent databases under these restricted classes of ICs to plain AFs with attacks only between arguments.

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

0 major / 2 minor

Summary. The paper establishes new correspondences between subset-maximal repairs of inconsistent databases under denial constraints and local-as-view tuple-generating dependencies (TGDs) and the extensions of SET-based Argumentation Frameworks (SETAFs). For denial constraints, repairs correspond to naive extensions, which coincide with preferred and stable extensions. For the TGD fragment, repairs correspond to preferred extensions, and with additional preprocessing, to a unique stable and naive extension. Combining both constraint types requires preferred semantics to capture the repairs. The paper also proves that functional dependencies and inclusion dependencies can be handled using standard argumentation frameworks without collective attacks.

Significance. This work is significant as it extends the known connections between database repairs and argumentation to require SETAFs for TGDs, while showing standard AFs suffice for FDs and IDs. The explicit constructions and proofs of the correspondences, along with the observation that preprocessing can yield unique extensions, provide a solid foundation for using argumentation semantics to compute or characterize database repairs. This bridges two fields and clarifies the role of collective attacks in modeling certain integrity constraints.

minor comments (2)
  1. [Abstract] The abstract refers to 'the considered fragment of tuple-generating dependencies' without a self-contained definition; ensure §2 or §3 provides an explicit syntactic characterization of this fragment with an example before the main theorems.
  2. The claim that 'additional preprocessing allows computing a unique extension' would benefit from a short complexity remark or pseudocode sketch in the relevant section to clarify the overhead.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our paper, the accurate summary of its contributions, and the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper provides explicit constructions and proofs establishing correspondences between subset-maximal repairs under a fragment of local-as-view TGDs and preferred extensions in SETAFs, plus a preprocessing step yielding unique stable/naive extensions. It cites prior literature for the denial-constraint case but does not reduce its new claims to those inputs or to any fitted parameters; the TGD and inclusion-dependency results are shown via direct translation to collective attacks and maximality arguments. No self-definitional steps, renamed predictions, or load-bearing self-citations appear in the derivation chain. The work is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard definitions of subset-maximal repairs, naive/preferred/stable extensions, and the construction of SETAFs from integrity constraints; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (2)
  • standard math Standard definitions of subset-maximal repairs for denial constraints and local-as-view tuple-generating dependencies
    The paper invokes established notions from database theory without re-deriving them.
  • standard math Standard definitions of naive, preferred, and stable extensions in Dung AFs and SETAFs
    The paper relies on prior formalizations of argumentation semantics.

pith-pipeline@v0.9.0 · 5517 in / 1349 out tokens · 31843 ms · 2026-05-09T15:29:33.210026+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

46 extracted references · 1 canonical work pages

  1. [1]

    Abiteboul, R

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

    1995

  2. [2]

    F. N. Afrati and P. G. Kolaitis. Repair checking in inconsistent databases: algorithms and complexity. In R. Fagin, editor, Database Theory - ICDT 2009, 12th International Conference, St. Petersburg, Russia, March 23-25, 2009, Proceedings, volume 361 of ACM International Conference Proceeding Series, pages 31–41. ACM, 2009

    2009

  3. [3]

    Amgoud, C

    L. Amgoud, C. Cayrol, M. Lagasquie-Schiex, and P. Livet. On bipolarity in argumentation frameworks. Int. J. Intell. Syst., 23(10):1062–1093, 2008

    2008

  4. [4]

    Arenas, L

    M. Arenas, L. E. Bertossi, and J. Chomicki. Scalar aggregation in fd-inconsistent databases. In J. V . den Bussche and V . Vianu, editors,Database Theory - ICDT 2001, 8th International Conference, London, UK, January 4-6, 2001, Proceedings, volume 1973 of Lecture Notes in Computer Science, pages 39–53. Springer, 2001

    2001

  5. [5]

    Arieli, A

    O. Arieli, A. Borg, and J. Heyninck. A review of the relations between logical argumentation and reasoning with maximal consistency. Ann. Math. Artif. Intell., 87(3):187–226, 2019

    2019

  6. [6]

    Arioua and M

    A. Arioua and M. Croitoru. Dialectical characterization of consistent query explanation with existential rules. In Z. Markov and I. Russell, editors, Proceedings of the Twenty-Ninth International Florida Artificial Intelligence Research Society Conference, FLAIRS 2016, Key Largo, Florida, USA, May 16-18, 2016, pages 621–625. AAAI Press, 2016

    2016

  7. [7]

    Arioua, M

    A. Arioua, M. Croitoru, and S. Vesic. Logic-based argumentation with existential rules. Int. J. Approx. Reason., 90:76–106, 2017. Computing Database Repairs under Expressive ICs via Argumentation 30

    2017

  8. [8]

    Arioua, N

    A. Arioua, N. Tamani, and M. Croitoru. Query answering explanation in inconsistent datalog +/- knowledge bases. In Q. Chen, A. Hameurlain, F. Toumani, R. R. Wagner, and H. Decker, editors, Database and Expert Systems Applications - 26th International Conference, DEXA 2015, Valencia, Spain, September 1-4, 2015, Proceedings, Part I, volume 9261 of Lecture N...

    2015

  9. [9]

    Arioua, N

    A. Arioua, N. Tamani, M. Croitoru, and P. Buche. Query failure explanation in inconsistent knowledge bases using argumentation. In S. Parsons, N. Oren, C. Reed, and F. Cerutti, editors, Computational Models of Argument - Proceedings of COMMA 2014, Atholl Palace Hotel, Scottish Highlands, UK, September 9-12, 2014 , volume 266 of Frontiers in Artificial Int...

    2014

  10. [10]

    Arming, R

    S. Arming, R. Pichler, and E. Sallinger. Complexity of repair checking and consistent query answering. LIPIcs, 48(2016), 2016

    2016

  11. [11]

    Barcel´o and G

    P. Barcel´o and G. Fontaine. On the data complexity of consistent query answering over graph databases. Journal of Computer and System Sciences, 88:164–194, 2017

    2017

  12. [12]

    L. E. Bertossi. Consistent query answering in databases. SIGMOD Rec., 35(2):68–76, 2006

    2006

  13. [13]

    L. E. Bertossi. Database repairs and consistent query answering: Origins and further developments. In D. Suciu, S. Skritek, and C. Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 48–58. ACM, 2019

    2019

  14. [14]

    Bienvenu and C

    M. Bienvenu and C. Bourgaux. Querying and repairing inconsistent prioritized knowledge bases: Complexity analysis and links with abstract argumentation. In D. Calvanese, E. Erdem, and M. Thielscher, editors, Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12-18, 2...

    2020

  15. [15]

    Bienvenu and C

    M. Bienvenu and C. Bourgaux. Inconsistency Handling in Prioritized Databases with Universal Con- straints: Complexity Analysis and Links with Active Integrity Constraints. In Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, pages 97–106, 8 2023

    2023

  16. [16]

    Bienvenu, C

    M. Bienvenu, C. Bourgaux, and F. Goasdou´e. Computing and explaining query answers over inconsistent dl-lite knowledge bases. Journal of Artificial Intelligence Research, 64:563–644, 2019

    2019

  17. [17]

    Bondarenko, P

    A. Bondarenko, P. M. Dung, R. A. Kowalski, and F. Toni. An abstract, argumentation-theoretic approach to default reasoning. Artificial intelligence, 93(1-2):63–101, 1997

    1997

  18. [18]

    Chomicki and J

    J. Chomicki and J. Marcinkowski. Minimal-change integrity maintenance using tuple deletions. Infor- mation and Computation, 197(1):90–121, 2005

    2005

  19. [19]

    Coste-Marquis, C

    S. Coste-Marquis, C. Devred, and P. Marquis. Symmetric argumentation frameworks. In L. Godo, editor, Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 8th European Conference, ECSQARU 2005, Barcelona, Spain, July 6-8, 2005, Proceedings , volume 3571 of Lecture Notes in Computer Science, pages 317–328. Springer, 2005. Y. Mahmood, J. Virte...

    2005

  20. [20]

    Croitoru, R

    M. Croitoru, R. Thomopoulos, and S. Vesic. Introducing preference-based argumentation to inconsistent ontological knowledge bases. In Q. Chen, P. Torroni, S. Villata, J. Y . Hsu, and A. Omicini, editors, PRIMA 2015: Principles and Practice of Multi-Agent Systems - 18th International Conference, Bertinoro, Italy, October 26-30, 2015, Proceedings, volume 93...

    2015

  21. [21]

    Croitoru and S

    M. Croitoru and S. Vesic. What can argumentation do for inconsistent ontology query answering? In W. Liu, V . S. Subrahmanian, and J. Wijsen, editors,Scalable Uncertainty Management - 7th International Conference, SUM 2013, Washington, DC, USA, September 16-18, 2013. Proceedings, volume 8078 of Lecture Notes in Computer Science, pages 15–29. Springer, 2013

    2013

  22. [22]

    Dimopoulos, W

    Y . Dimopoulos, W. Dvor´ak, M. K¨onig, A. Rapberger, M. Ulbricht, and S. Woltran. Sets attacking sets in abstract argumentation. In NMR, pages 22–31, 2023

    2023

  23. [23]

    P. M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. ai, 77(2):321–357, 1995

    1995

  24. [24]

    Dvor´ak and P

    W. Dvor´ak and P. E. Dunne. Computational problems in formal argumentation and their complexity. FLAP, 4(8), 2017

    2017

  25. [25]

    Dvoˇr´ak and S

    W. Dvoˇr´ak and S. Woltran. Complexity of abstract argumentation under a claim-centric view. Artificial Intelligence, 285:103290, 2020

    2020

  26. [26]

    Fagin, B

    R. Fagin, B. Kimelfeld, and P. G. Kolaitis. Dichotomies in the complexity of preferred repairs. In T. Milo and D. Calvanese, editors, Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 3–15. ACM, 2015

    2015

  27. [27]

    Hannula and L

    M. Hannula and L. Hella. Complexity thresholds in inclusion logic. Inf. Comput., 287:104759, 2022

    2022

  28. [28]

    Hannula and J

    M. Hannula and J. Wijsen. A dichotomy in consistent query answering for primary keys and unary foreign keys. In L. Libkin and P. Barcel´o, editors, PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 437–449. ACM, 2022

    2022

  29. [29]

    L. Ho, S. Arch-int, E. Acar, S. Schlobach, and N. Arch-int. An argumentative approach for handling inconsistency in prioritized datalog± ontologies. AI Commun., 35(3):243–267, 2022

    2022

  30. [30]

    Kimelfeld, E

    B. Kimelfeld, E. Livshits, and L. Peterfreund. Detecting Ambiguity in Prioritized Database Repairing. In M. Benedikt and G. Orsi, editors, 20th International Conference on Database Theory (ICDT 2017), volume 68 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:20, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik

    2017

  31. [31]

    Kimelfeld, E

    B. Kimelfeld, E. Livshits, and L. Peterfreund. Counting and enumerating preferred database repairs. Theor. Comput. Sci., 837:115–157, 2020

    2020

  32. [32]

    K¨onig, A

    M. K¨onig, A. Rapberger, and M. Ulbricht. Just a matter of perspective. In Computational Models of Argument, pages 212–223. IOS Press, 2022

    2022

  33. [33]

    Livshits, B

    E. Livshits, B. Kimelfeld, and S. Roy. Computing optimal repairs for functional dependencies. ACM Trans. Database Syst., 45(1):4:1–4:46, 2020. Computing Database Repairs under Expressive ICs via Argumentation 32

    2020

  34. [34]

    Lopatenko and L

    A. Lopatenko and L. E. Bertossi. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In T. Schwentick and D. Suciu, editors, Database Theory - ICDT 2007, 11th International Conference, Barcelona, Spain, January 10-12, 2007, Proceed- ings, volume 4353 of Lecture Notes in Computer Science, pages 17...

    2007

  35. [35]

    Y . Mahmood. Parameterized aspects of team-based formalisms and logical inference, 2022

    2022

  36. [36]

    Mahmood, M

    Y . Mahmood, M. Hecher, and A. N. Ngomo. Dung’s argumentation framework: Unveiling the expressive power with inconsistent databases. In T. Walsh, J. Shah, and Z. Kolter, editors, AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Philadelphia, PA, USA, pages 15058–15066. AAAI Press, 2025

    2025

  37. [37]

    Mahmood, J

    Y . Mahmood, J. Virtema, T. Barlag, and A.-C. N. Ngomo. Computing repairs under functional and inclusion dependencies via argumentation. In International Symposium on Foundations of Information and Knowledge Systems, pages 23–42. Springer, 2024

    2024

  38. [38]

    S. H. Nielsen and S. Parsons. A generalization of dung’s abstract framework for argumentation: Arguing with sets of attacking arguments. In N. Maudet, S. Parsons, and I. Rahwan, editors, Argumentation in Multi-Agent Systems, Third International Workshop, ArgMAS 2006, Hakodate, Japan, May 8, 2006, Revised Selected and Invited Papers, volume 4766 of Lecture...

    2006

  39. [39]

    Nouioua and V

    F. Nouioua and V . Risch. Argumentation frameworks with necessities. In S. Benferhat and J. Grant, editors, Scalable Uncertainty Management - 5th International Conference, SUM 2011, Dayton, OH, USA, October 10-13, 2011. Proceedings, volume 6929 of Lecture Notes in Computer Science, pages 163–176. Springer, 2011

    2011

  40. [40]

    Staworko and J

    S. Staworko and J. Chomicki. Consistent query answers in the presence of universal constraints. Inf. Syst., 35(1):1–22, 2010

    2010

  41. [41]

    Staworko, J

    S. Staworko, J. Chomicki, and J. Marcinkowski. Prioritized repairing and consistent query answering in relational databases. Ann. Math. Artif. Intell., 64(2-3):209–246, 2012

    2012

  42. [42]

    ten Cate, G

    B. ten Cate, G. Fontaine, and P. G. Kolaitis. On the data complexity of consistent query answering. In Proceedings of the 15th International Conference on Database Theory, ICDT’12, pages 22–33, 2012

    2012

  43. [43]

    V ¨a¨an¨anen

    J. V ¨a¨an¨anen. Dependence Logic. Cambridge University Press, 2007

    2007

  44. [44]

    J. Wijsen. Condensed representation of database repairs for consistent query answering. In Proceedings of the 9th International Conference on Database Theory, ICDT ’03, pages 378–393. Springer-Verlag, 2002

    2002

  45. [45]

    A. P. Young, S. Modgil, and O. Rodrigues. Prioritised default logic as argumentation with partial order default priorities. CoRR, abs/1609.05224, 2016

    work page arXiv 2016

  46. [46]

    B. Yun, S. Vesic, and M. Croitoru. Sets of attacking arguments for inconsistent datalog knowledge bases. In H. Prakken, S. Bistarelli, F. Santini, and C. Taticchi, editors, Computational Models of Argument - Proceedings of COMMA 2020, Perugia, Italy, September 4-11, 2020 , volume 326 of Frontiers in Artificial Intelligence and Applications, pages 419–430....

    2020