Inconsistent Databases and Argumentation Frameworks with Collective Attacks
Yasir Mahmood, Jonni Virtema, Timon Barlag, Axel-Cyrille Ngonga Ngomo · 2026
Read Inconsistent Databases and Argumentation Frameworks with Collective Attacks by Yasir Mahmood, Jonni Virtema, Timon Barlag, Axel-Cyrille Ngonga Ngomo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03954.txt.
Introduction
Yasir Mahmood, Jonni Virtema, Timon Barlag, and Axel-Cyrille Ngonga Ngomo connect two ways of resolving conflict: subset-maximal repairs of inconsistent databases, and acceptable sets of arguments in abstract argumentation frameworks. Recent work linked repairs under various integrity constraints to such extensions. The authors extend the connection to constraints combining denial constraints with local-as-view tuple-generating dependencies.
Set-based argumentation frameworks, which allow joint attacks by groups of arguments, turn out to be necessary. Repairs under denial constraints alone match the naive extensions, which coincide with preferred and stable ones in the resulting framework. For the tuple-generating fragment, the authors show repairs correspond to preferred extensions, and preprocessing can yield a unique extension that is both stable and naive. Mixing both constraint types breaks the pattern.
Catalog record
| CREATOR | Yasir Mahmood, Jonni Virtema, Timon Barlag, Axel-Cyrille Ngonga Ngomo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.03954
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Inconsistent Databases and Argumentation Frameworks with Collective Attacks Yasir Mahmood, Jonni Virtema, Timon Barlag, Axel-Cyrille Ngonga Ngomo 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, is 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, an additional pre-processing allows to compute 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. Keywords: complexity theory, database repairs, integrity constraints, denial constraints, functional and inclusion dependencies, abstract argumentation, collective attacks. 1 Introduction In real-world applications, the provenance of data can be very diverse and include non-trustworthy sources. Thus, databases are often inconsistent in practice when the data does not conform to the imposed integrity constraints. A rich theory has been developed to deal with inconsistent databases. Formally, integrity constraints (ICs) describe fundamental structural properties of data which should be satisfied for a database to be considered consistent. ICs are often formulated in some logic; most notably in fragments of first-order logic. Two of the most fundamental classes of ICs are key constraints (indicating that the value of a given collection of attributes uniquely determine the whole record in the database table) and inclusion dependencies (that express that all values for a given attribute occur as values of another given attribute). Together key constraints and inclusion dependencies can express foreign key constraints. The literature for database dependencies considers a whole hierarchy of dependencies in increasing generality (see e.g., [ 1 ] ). Key dependencies are special cases of functional dependencies (FDs), which are special cases of equality-generating dependencies, which again generalize to denial constraints (DCs). Likewise, inclusion dependencies generalize to local-as-view tuple-generating dependencies (LTGDs), which are special cases of tuple-generating dependencies. All of the aforementioned dependencies can be defined as particular syntactic fragments of first-order logic (see Section 2 for formal definitions). In this paper, we examine expressive integrity constraints, specifically DCs and LTGDs, alongside their less expressive counterparts, FDs and IDs. One of the main approaches for handling inconsistency is database repairing . The goal is to identify and repair inconsistencies in data to obtain a consistent database that satisfies the imposed constraints. In the usual approaches, one would search for a database that satisfies the given constraints and differs minimally from the original database; the obtained database is called a repair of the original. Some of the most prominent notions of repairs are set-based repairs [ 42 , 11 ] , attribute-based repairs [ 44 ] , and cardinality-based repairs [ 34 ] . Dung’s abstract argumentation framework [ 23 ] has been specifically designed to model conflicts and support relationships among arguments. An abstract argumentation framework (AF) represents arguments and their conflicts through directed graphs and allows for a convenient exploration of the conflicts at an abstract level. Furthermore, often it is necessary to consider conflicts not only between individual arguments, but between sets of arguments. This necessity has given rise to the so-called set-based argumentation frameworks (SETAFs) [ 38 ] , which allow modelling of collective attacks. Argumentation frameworks have been explored extensively for representing, and reasoning with, inconsistent knowledge bases (KBs), covering Datalog ± and description logics (see e.g., [ 7 , 6 , 9 , 45 , 46 , 15 ] and [ 5 ] for an overview). The common goal in each of these works is to formally establish a connection between inconsistent KBs and AFs such that the argumentation machinery then outputs extensions equivalent to the set of repairs of the KB. Nevertheless, in the setting of relational databases and integrity constraints, there is still a gap with respect to how or whether a connection between inconsistent databases and AFs can be established. To the best of our knowledge, only functional dependencies (or their generalization, denial constraints) have been investigated in the context of AFs (resp., SETAFs) in [ 15 ] . We expand this area of research by establishing further connections between repairs and abstract argumentation frameworks when further ICs are allowed. In this paper, we focus on subset repairs of relational databases when the ICs are denial constraints and local-as-view tuple-generating dependencies. The first problem of interest to us is establishing a connection between repairs for the inconsistent DBs and extensions in SETAFs. We show how subset-maximal repairs under a set of DCs and LTGDs can be obtained by computing the naive, preferred, or stable extensions (see Section 2 for definitions) in the related SETAFs. Repairs under DCs correspond to the naive extensions, which also coincide with the preferred and stable extensions in the resulting SETAFs. For LTGDs, the correspondence requires preferred semantics. However, a polynomial time pre-processing on the resulting SETAFs results in its unique extension that is also stable and naive. Allowing both types of ICs breaks this relationship between extensions and only preferred semantics captures the repairs. Our second contribution highlights that when one restricts DCs to FDs and LTGDs to IDs, respectively, a similar connection as for the expressive ICs hold, however, now the resulting SETAFs are in fact AFs (with attacks only between arguments, rather than collective attacks). We are also interested in the computational problems of deciding the existence of a repair, and determining whether a given fact belongs to some (or every) repair and consider their complexity. See Table 1 for the complexity results. By employing Dung’s AFs (and their generalizations, SETAFs) to model repairs of a relational database, one can effectively abstract away from the detailed content of individual entries in the database and focus solely on their relationships with other entries. This approach provides a clearer understanding of why specific records either appear or do not appear in a repair, as well as the reasons certain values may be absent from query answers. Furthermore, this modeling approach allows for the incorporation of additional information about records, such as priorities among them, directly at an abstract level. Related Work The problem of computing subset-maximal repairs and its complexity has been explored extensively in the database setting [ 2 , 4 , 18 , 28 , 33 , 41 ] (see [ 12 , 13 ] for an overview). The notions of conflict graphs and hypergraphs have been introduced before for certain families of ICs [ 30 , 31 , 40 ] . In particular, a correspondence between repairs and subset-maximal independent sets of the