Dung's Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases

Axel-Cyrille Ngonga Ngomo; Markus Hecher; Yasir Mahmood

REVIEW 1 major objections 5 minor 12 references

Dung's Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases

T0 review · 1 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every abstract argumentation framework can be rewritten as an inconsistent database whose repairs are exactly its extensions.

desk verdict Solid constructive encoding of AFs into inconsistent databases with FDs+IDs; one definitional bug in the defense database needs a small fix before publication. read the letter →

arxiv 2412.11617 v1 pith:G4UIHJTK submitted 2024-12-16 cs.LO cs.DB

Yasir Mahmood , Markus Hecher , Axel-Cyrille Ngonga Ngomo This is my paper · ORCID

classification cs.LOcs.DB

keywords AbstractargumentationInconsistentdatabasesFunctionaldependenciesInclusionSubset-repairsCoveringrepairsDungsemanticsExpressivepower

open problems P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that Dung's abstract argumentation frameworks—graphs whose nodes are arguments and whose edges are attacks—are exactly as expressive as inconsistent relational databases controlled by functional and inclusion dependencies. It gives a polynomial-time translation of any AF into one database table with FDs and IDs, and shows that the standard extension semantics of argumentation correspond to the standard repair semantics of databases: conflict-free and naive sets match (maximal) repairs of a conflict table, admissible and preferred sets match (maximal) repairs of a combined AF-database, and stable, stage, and semi-stable sets match the new fully or maximally covering repairs. Earlier work had translated databases into argumentation frameworks; this paper supplies the converse, so the two formalisms are mutually representable. The authors also introduce covering repairs as a repair family of independent interest, motivated by the range-maximizing behaviour of stable, stage, and semi-stable semantics. The result matters because it transfers algorithms, complexity upper and lower bounds, and query-answering machinery between the two fields.

What carries the argument

The construction rests on two encodings plus one new repair family. The conflict database represents each attack {a,b} by giving both corresponding tuples the same value on an attribute x_r while their name attributes differ; the FD x_r→n is then violated exactly when both tuples are kept, so repairs are exactly conflict-free sets, and an edge-coloring argument (Vizing's theorem) compresses the number of attributes to the graph degree plus one. The defense database represents, for each argument a, an inclusion dependency u_a⊆v_a over two columns; a tuple b under attack by a satisfies the ID only if some tuple c with c[v_a]=a is present, which is precisely the condition that b has a defender in the selected set. Combining these, with one extra ID for self-attacking arguments, yields the AF-database whose repairs are admissible sets and whose subset-maximal repairs are preferred extensions. The new mechanism for the remaining semantics is a covering repair: a repair that preserves all values of a designated attribute set X (fully covering), or as many as any other repair (maximally covering), where X_r = {v_x | x∈A} ∪ {n} encodes the range of a set of arguments.

What would settle it

Run the translation from Theorem 17 on a small AF, enumerate all repairs of the resulting AF-database, and compare them with all admissible and preferred extensions; a single repair that is not admissible, or an admissible set whose tuples do not form a repair, refutes the main equivalence. For the separation half, a polynomial-time algorithm that decides non-empty admissible extensions using only FDs or only IDs would refute the claimed lower bound (and would imply P=NP).

Watch

Extended reading notes

Core claim

The central discovery is that the attack relation of an AF can be simulated by functional dependencies and the defense relation by inclusion dependencies, and that the two can be merged into one table so that database repairs coincide with argumentation extensions. Concretely, a set S of arguments is conflict-free in F exactly when the corresponding tuples form a repair of the conflict database, which encodes each attack as a pair of tuples agreeing on an attribute x and disagreeing on the name attribute n, violating the FD x→n; with subset-maximality this becomes naive semantics. Admissible and preferred extensions are captured by the AF-database, which adds for every argument a an inclusion dependency u_a⊆v_a that forces any repair to contain a defender against every attack; subset-maximal repairs are preferred extensions. For the range-based semantics, the paper defines covering repairs—repairs that maximize the set of attribute values taken from a designated set X_r of range attributes—and proves that stable extensions are exactly fully covering repairs, while stage and semi-stable extensions are exactly maximally covering repairs. The translation uses O(|A|) FDs and O(|A|) IDs and runs in polynomial time, from which the paper concludes that Dung's theory is, in expressive power, the theory of inconsistent databases with FDs and IDs.

Load-bearing premise

The paper's claim that neither FDs alone nor IDs alone can simulate AFs is conditional on P being different from NP, and the defense encoding depends on a specific zero-filling convention for missing values; if either gives way the exact-expressive-power claim needs revision, although the positive encodings survive.

Editorial extensions

If this is right

Every algorithm or system that computes repairs under FDs and IDs can now be used to compute argumentation extensions, and conversely every AF reasoner can be viewed as a repair engine.
Conjunctive queries over the AF-database give a way to ask questions about argumentation frameworks that go beyond extension existence and credulous or skeptical acceptance.
Complexity bounds transfer in both directions: lower bounds for AF reasoning apply to repair checking for FDs and IDs, and tractability results for such databases apply to AF reasoning.
For symmetric AFs, stable, preferred, and naive extensions collapse to subset-maximal repairs of the conflict database using FDs alone (Corollary 19).
The new covering repairs give a natural database meaning to range-maximizing semantics: stable sets are fully covering repairs and stage/semi-stable sets are maximally covering repairs of the appropriate database.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The zero-filling convention in Definition 10 is doing real logical work; swapping it for a SQL-style NULL with Codd semantics, or for the same-as-name convention the authors explicitly reject, would break Lemmas 12 and 13 and deserves a stress test before the translation is used as a general-purpose bridge.
The equivalence suggests a two-way transfer of parameterized and decomposition-guided techniques: treewidth-based algorithms for argumentation could become decomposition-guided repair algorithms for FDs and IDs, and data-dependent measures on the database side could yield new structural parameters for AFs.
Complete and grounded semantics, which the paper leaves out, might find a repair analogue not in subset-deletion but in closure operators on repairs—for example, a repair closed under adding all defended tuples—though the authors are explicit that no natural subset-repair counterpart is known.
Because covering repairs depend on a designated attribute set X, they parametrize database repair by a notion of 'content worth preserving'; one could test whether different choices of X recover known repair families such as cardinality repairs or prioritized repairs.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Good paper, worth taking seriously. The main new thing is the AF-to-database direction: they build a polynomial encoding of any Dung framework into a single table with functional and inclusion dependencies, and prove exact correspondences between conflict-free/naive/admissible/preferred extensions and (maximal) subset-repairs. The converse direction (DBs to AFs) was already out there [38]; this paper closes the circle. The compact edge-coloring trick to compress the conflict database is a nice touch, and the new covering-repair semantics (fully and maximally covering) that line up with stable, stage, and semi-stable extensions is a genuine contribution, independent of the AF connection.

The main proofs are constructive and mostly check out. Theorem 17 and Theorem 22 are the load-bearing results, and the lemmas underneath are correct. I also like that the authors are upfront about what they cannot express (complete and grounded semantics) and about the P≠NP assumption behind the claim that FDs alone or IDs alone will not do.

Now the soft spots.

First, Definition 10 as written is not well-defined for mutual attacks. For r=(a,b) they set b[va]=0, and for r=(b,a) they set b[va]=a, so a symmetric pair overwrites the same cell inconsistently. The intended reading is clear from the explanatory paragraph—a[vb] should be b iff a attacks b, and a[ub] should be b iff a interacts with b—and with that reading the proofs go through. But as printed, the definition and the lemmas that rely on it (Lemma 12, Lemma 13, and hence Theorem 17 and 22) are technically unsupported for symmetric AFs. This is a small fix, not a deep flaw, but it has to be made.

Second, the paper leans on a known result for the lower bound: deciding whether an AF has a non-empty admissible extension is NP-complete, while repair existence for FDs-only or IDs-only databases is in P. That is fine, but it only gives a separation under P≠NP. The authors flag it, so it is not a hidden assumption.

Third, there are minor presentational issues: the notation F is overloaded (framework vs. FD set), and the proof of Lemma 6's Claim 7 is compressed—the induction generalizing from two edges to a full edge-coloring is only sketched. These are minor.

Is there anything that fails? No. The central construction is correct once the defense database definition is patched. The literature scan looks reasonable; the novelty claim depends on there being no prior AF-to-DB encoding, and I did not find one.

Who is this for? Anyone working in abstract argumentation, database repairs, or consistent query answering. It gives transfer of complexity results and repair semantics across two fields. It deserves a serious referee; the definitional bug and the sketchiness in Lemma 6 should be fixed in revision.

Recommendation: engage with it—send to peer review. I would not desk-reject.

Referee Report

1 major / 5 minor

Summary. The paper establishes a database translation of Dung's abstract argumentation frameworks, showing that an AF can be represented as an inconsistent database instance with functional dependencies (FDs) and inclusion dependencies (IDs). The authors construct a conflict database whose subset-repairs correspond to conflict-free and naive extensions, a defense database whose repairs correspond to self-defending sets, and combine them to match admissible and preferred extensions with repairs and maximal repairs. They further introduce a new family of attribute-based covering repairs (maximally and fully covering) and prove that stable, stage, and semi-stable extensions correspond to fully or maximally covering repairs with respect to range attributes. All translations are claimed to be polynomial-time, with explicit size bounds for the resulting tables.

Significance. The positive direction (AFs as inconsistent databases) closes a previously open direction: earlier work has translated databases with FDs/IDs into AFs, but not the converse. The constructed encodings are explicit, parameter-free, and come with concrete size bounds, and the main equivalences are proven rather than assumed. The new family of covering repairs is an original concept that is likely of independent interest for database repair semantics. The paper also correctly flags that the lower-bound separation between FDs-only and IDs-only relies on P ≠ NP, and the positive results are unconditional.

major comments (1)

[§3.2, Definition 10] The defense database is not well-defined for AFs containing mutual attacks. For two attacks r=(a,b) and r'=(b,a), Definition 10's iterative assignment yields conflicting values: r sets a[vb]=b and b[va]=0, while r' sets a[vb]=0 and b[va]=a. The definition gives no rule for resolving such conflicts, so the construction is ambiguous for symmetric frameworks, including the running example (Example 1, Table 3). This directly affects Lemma 12 and Lemma 13, and therefore the main equivalences in Theorem 17 and Theorem 22. The intended semantics is clear from the surrounding text (a[vb]=b iff (a,b)∈R, and a[ub]=b iff a interacts with b), so the fix is straightforward: define each attribute value directly by these conditions rather than by iterating over attack edges. The authors should correct the definition and re-verify the proofs of Lemma 12/13 and Theorems 17/22 under the corrected definition.

minor comments (5)

[§3.1, Lemma 6 proof] Claim 7 proves that two conflicts that do not share endpoints can be merged into one attribute while preserving repair satisfaction, but the generalization to a full edge-coloring where several edges share a color is only asserted. An explicit induction or a uniform argument for merging multiple pairwise disjoint conflicts would make the proof rigorous.
[§3.3 and throughout] The notation is overloaded: F denotes both an argumentation framework and the set of FDs, and D denotes both a database instance and the set of dependencies (e.g., in "D = ⟨T,D⟩"). Renaming the dependency set, for instance to Σ, would improve readability.
[End of §3 and Abstract] The phrase "exact expressive power" in the abstract and introduction should be qualified, since the separation result for FDs-only or IDs-only is conditional on P ≠ NP, as the paper itself notes at the end of Section 3. Without that assumption the positive encodings remain valid, but the inexpressibility claim is complexity-theoretic rather than unconditional.
[§4, Theorem 22 statement] The statement of Theorem 22 writes AF = ⟨T,F∪I⟩ but does not explicitly say whether I includes the self-attacking ID is. Since the proof uses is, the statement should clarify that I ∪ {is} is meant.
[Minor production issues] There is a typo "AFF" in Example 1, the hyphenation of "Full-covering" and "Max-covering" in Table 1 is inconsistent, and the remark after Lemma 13 that conflict-freeness cannot be modeled by IDs alone is stated without proof; a short justification or reference would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the AF-to-database translations are constructive and the equivalence theorems are proven from standard definitions.

full rationale

The paper's main claims are translations, not predictions from fitted inputs. Definition 3 (conflict database), Definition 10 (defense database), and the combined AF-database are explicit encodings using only standard functional and inclusion dependencies; Theorems 5, 17, and 22 are proved by direct satisfaction arguments from the standard definitions of conflict-free, admissible, preferred, stable, stage, and semi-stable semantics. The newly introduced covering repairs in Section 4 are defined independently as database repairs that maximize or fully cover the active domain of selected attributes, and the correspondence to range-maximizing AF semantics is established through Lemma 21 and Theorem 22, so the equivalence is a theorem rather than a definitional identity. The only external results invoked are standard complexity facts, including [38] for tractability of FDs-only/IDs-only repair existence; although [38] shares authors with this paper, it is used as a cited prior complexity result to support the lower-bound observation under P ≠ NP, and the paper's positive encodings do not depend on it. Therefore no load-bearing step reduces by construction to its own input. The well-definedness issue in Definition 10 for mutually attacking arguments is a correctness concern, not a circularity pattern, and does not affect this verdict.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The central claim rests on standard database theory (FD/ID semantics), standard graph theory (Vizing's theorem), and the explicitly flagged P≠NP assumption for the lower-bound side. No fitted parameters are present.

assumptions (4)

standard math Vizing's theorem: any undirected graph of maximum degree γ has a proper edge-coloring with at most γ+1 colors.
Invoked in Lemma 6 to bound the number of FDs needed in the compact conflict database.
domain assumption P ≠ NP
Used at the end of Section 3 to argue that neither FDs alone nor IDs alone can simulate AFs (else non-empty repair existence would be NP-complete). Explicitly stated.
standard math Standard definitions of functional dependencies, inclusion dependencies, and subset-repairs
Background definitions from relational database theory, used throughout the constructions.
domain assumption Finite, non-empty set of arguments in an AF
Stated in Section 2: AFs are directed graphs over non-empty finite sets of arguments. All constructions rely on this.

invented entities (1)

Maximally covering (mc) and fully covering (fc) repair semantics
purpose: A new family of subset-repairs selecting repairs by maximal preservation of the active domain over specified attributes; connected to stable, semi-stable, and stage semantics.
A mathematical definition introduced by the authors, not an empirical entity; no external falsifiable handle applies.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Dung's Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases." pith.science (2026). https://pith.science/paper/G4UIHJTK

@misc{pith2026241211617,
  author       = {Pith},
  title        = {Pith review of: Dung's Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G4UIHJTK}},
  note         = {Machine review of arXiv:2412.11617}
}

read the original abstract

The connection between inconsistent databases and Dung's abstract argumentation framework has recently drawn growing interest. Specifically, an inconsistent database, involving certain types of integrity constraints such as functional and inclusion dependencies, can be viewed as an argumentation framework in Dung's setting. Nevertheless, no prior work has explored the exact expressive power of Dung's theory of argumentation when compared to inconsistent databases and integrity constraints. In this paper, we close this gap by arguing that an argumentation framework can also be viewed as an inconsistent database. We first establish a connection between subset-repairs for databases and extensions for AFs, considering conflict-free, naive, admissible, and preferred semantics. Further, we define a new family of attribute-based repairs based on the principle of maximal content preservation. The effectiveness of these repairs is then highlighted by connecting them to stable, semi-stable, and stage semantics. Our main contributions include translating an argumentation framework into a database together with integrity constraints. Moreover, this translation can be achieved in polynomial time, which is essential in transferring complexity results between the two formalisms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages

[4]

17 Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis

doi:10.1007/11518655\_28. 17 Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis. Constrained argumentation frameworks. In KR’06, pages 112–122,

doi:10.1007/11518655
[12]

doi:10.3233/FAIA200526

work page doi:10.3233/faia200526
[1992]

40 Søren Holbech Nielsen and Simon Parsons

URL: https://www.sciencedirect.com/science/article/pii/002001909290041S, doi: https://doi.org/10.1016/0020-0190(92)90041-S. 40 Søren Holbech Nielsen and Simon Parsons. A generalization of dung’s abstract framework for argumenta- tion: Arguing with sets of attacking arguments. In Nicolas Maudet, Simon Parsons, and Iyad Rahwan, editors, Argumentation in Mul...

arXiv
[2002]

Sets of attacking arguments for inconsistent datalog knowledge bases

46 Bruno Yun, Srdjan Vesic, and Madalina Croitoru. Sets of attacking arguments for inconsistent datalog knowledge bases. In Henry Prakken, Stefano Bistarelli, Francesco Santini, and Carlo Taticchi, editors, Computational Models of Argument - Proceedings of COMMA 2020, Perugia, Italy, September 4-11, 2020, volume 326 of Frontiers in Artificial Intelligence...

work page 2020
[2005]

18 Expressivity Comparison between Dung’s AFs and Inconsistent DBs 16 Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis

URL: https://www.sciencedirect.com/science/article/ pii/S0890540105000179, doi:https://doi.org/10.1016/j.ic.2004.04.007. 18 Expressivity Comparison between Dung’s AFs and Inconsistent DBs 16 Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis. Symmetric argumentation frameworks. In Lluís Godo, editor, Symbolic and Quantitative Approaches to Reasonin...

doi:10.1016/j.ic.2004.04.007 2004
[2006]

41 Sławek Staworko, Jan Chomicki, and Jerzy Marcinkowski

doi:10.1007/978-3-540-75526-5\_4 . 41 Sławek Staworko, Jan Chomicki, and Jerzy Marcinkowski. Prioritized repairing and consistent query answering in relational databases. Annals of Mathematics and Artificial Intelligence, 64(2-3):209–246,

work page doi:10.1007/978-3-540-75526-5
[2011]

Consistent query answers in inconsistent probabilistic databases

35 Xiang Lian, Lei Chen, and Shaoxu Song. Consistent query answers in inconsistent probabilistic databases. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data , pages 303–314,

work page 2010
[2013]

A sat-based system for consistent query answering

19 Akhil A Dixit and Phokion G Kolaitis. A sat-based system for consistent query answering. In Theory and Applications of Satisfiability Testing–SAT 2019: 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9–12, 2019, Proceedings 22, pages 117–135. Springer,

work page 2019

Show all 12 references

[2014]

Complexity of repair checking and consistent query answering

7 Sebastian Arming, Reinhard Pichler, and Emanuel Sallinger. Complexity of repair checking and consistent query answering. LIPIcs, 48(2016),

2016
[2015]

Query failure explanation in inconsistent knowledge bases using argumentation

6 Abdallah Arioua, Nouredine Tamani, Madalina Croitoru, and Patrice Buche. Query failure explanation in inconsistent knowledge bases using argumentation. Computational Models of Argument: Proceedings of COMMA 2014, 266:101,

2014
[2018]

Detecting ambiguity in prioritized database repairing

30 Benny Kimelfeld, Ester Livshits, and Liat Peterfreund. Detecting ambiguity in prioritized database repairing. In 20th International Conference on Database Theory (ICDT 2017). Schloss-Dagstuhl-Leibniz Zentrum für Informatik,

2017
[2020]

Mahmood, M

Y. Mahmood, M. Hecher, and A-C. Ngonga Ngomo 19 37 Andrei Lopatenko and Leopoldo E. Bertossi. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In Proceedings ICDT-2007, volume 4353 of LNCS, pages 179–193. Springer,

2007

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [4]

17 Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis

doi:10.1007/11518655\_28. 17 Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis. Constrained argumentation frameworks. In KR’06, pages 112–122,

doi:10.1007/11518655

[2] [12]

doi:10.3233/FAIA200526

work page doi:10.3233/faia200526

[3] [1992]

40 Søren Holbech Nielsen and Simon Parsons

URL: https://www.sciencedirect.com/science/article/pii/002001909290041S, doi: https://doi.org/10.1016/0020-0190(92)90041-S. 40 Søren Holbech Nielsen and Simon Parsons. A generalization of dung’s abstract framework for argumenta- tion: Arguing with sets of attacking arguments. In Nicolas Maudet, Simon Parsons, and Iyad Rahwan, editors, Argumentation in Mul...

arXiv

[4] [2002]

Sets of attacking arguments for inconsistent datalog knowledge bases

46 Bruno Yun, Srdjan Vesic, and Madalina Croitoru. Sets of attacking arguments for inconsistent datalog knowledge bases. In Henry Prakken, Stefano Bistarelli, Francesco Santini, and Carlo Taticchi, editors, Computational Models of Argument - Proceedings of COMMA 2020, Perugia, Italy, September 4-11, 2020, volume 326 of Frontiers in Artificial Intelligence...

work page 2020

[5] [2005]

18 Expressivity Comparison between Dung’s AFs and Inconsistent DBs 16 Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis

URL: https://www.sciencedirect.com/science/article/ pii/S0890540105000179, doi:https://doi.org/10.1016/j.ic.2004.04.007. 18 Expressivity Comparison between Dung’s AFs and Inconsistent DBs 16 Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis. Symmetric argumentation frameworks. In Lluís Godo, editor, Symbolic and Quantitative Approaches to Reasonin...

doi:10.1016/j.ic.2004.04.007 2004

[6] [2006]

41 Sławek Staworko, Jan Chomicki, and Jerzy Marcinkowski

doi:10.1007/978-3-540-75526-5\_4 . 41 Sławek Staworko, Jan Chomicki, and Jerzy Marcinkowski. Prioritized repairing and consistent query answering in relational databases. Annals of Mathematics and Artificial Intelligence, 64(2-3):209–246,

work page doi:10.1007/978-3-540-75526-5

[7] [2011]

Consistent query answers in inconsistent probabilistic databases

35 Xiang Lian, Lei Chen, and Shaoxu Song. Consistent query answers in inconsistent probabilistic databases. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data , pages 303–314,

work page 2010

[8] [2013]

A sat-based system for consistent query answering

19 Akhil A Dixit and Phokion G Kolaitis. A sat-based system for consistent query answering. In Theory and Applications of Satisfiability Testing–SAT 2019: 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9–12, 2019, Proceedings 22, pages 117–135. Springer,

work page 2019