arXiv CSopen access

Inconsistent Databases and Argumentation Frameworks with Collective Attacks

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

artificial intelligence, reasoning, knowledge representation

Inconsistent Databases and Argumentation Frameworks with Collective Attacks Yasir Mahmood* 1 , Jonni Virtema†2,3 , Timon Barlag‡4 , Axel-Cyrille Ngonga Ngomo§1

arXiv:2605.03954v1 [cs.DB] 5 May 2026

Data Science Group, Heinz Nixdorf Institute, Paderborn University, Germany 2 School of Computing Science, University of Glasgow, United Kingdom 3 School of Computer Science, University of Sheffield, United Kingdom 4 Institut für Theoretische Informatik, Leibniz Universität Hannover, Germany 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.

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. * [email protected] †

[email protected] [email protected] § [email protected] ‡

Computing Database Repairs under Expressive ICs via Argumentation

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., [6, 7, 8, 45, 46, 14] 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 [14]. 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

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

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, 40] (see [12, 13] for an overview). The notions of conflict graphs and hypergraphs have been introduced before for certain families of ICs [30, 31, 41]. In particular, a correspondence between repairs and subset-maximal independent sets of the conflict graphs for FDs [4] and DCs [18] has been established. Moreover, a recent work defines conflict (hyper)graphs for a richer setting of universal constraints considering symmetric difference repairs [15]. Notice that the connection between repairs and independent sets also yields a correspondence between repairs and the naive extensions when the conflict graph is seen as an argumentation framework. Nevertheless, to the best of our knowledge, no work has considered a similar graph representation when LTGDs (or even IDs) are taken into account. Hannula and Wijsen [28] addressed the problem of consistent query answering with respect to primary and foreign keys. Their setting allows the insertion of new tuples to fulfill foreign key constraints rather than only deleting. The case of unirelational databases is also connected to the team-semantics literature [43]. Team semantics is a logical framework where formulae are evaluated over unirelational databases (teams in their terminology). In this setting, the complexity of finding maximal satisfying subteams has been studied by Hannula and Hella [27] for inclusion logic formulas and by Mahmood [35] for propositional dependence logic. In the teamsemantics literature, FDs are known as dependence atoms and IDs as inclusion atoms, denoted respectively as dep(x; y) and x ⊆ y. 1 Our work differs from the previous work, since it combines denial constraints (a subclass of universal constraints) and local-as-view tuple-generating dependencies (a subclass of tuple-generating dependencies). Moreover, one of our main contributions lies in connecting repairs under DCs (resp., FDs) and LTGDs (IDs) to the extensions of set-based (plain) argumentation frameworks in Dung’s setting [23]. A similar connection between (SET)AFs and preferred repairs has been explored in the context of prioritized description logic [14] and Datalog± knowledge bases [9, 20, 21, 29]. Employing abstract argumentation, we utilize facts in a database as arguments, aligning with the approach presented in [14]. In fact, the results for DCs and FDs regarding preferred and stable semantics follow as a corollary from the work by [14] since repairs in the prioritized setting generalize subset repairs. In contrast, Croitoru et al. [20, 21] take an orthogonal approach in the datalog setting, employing structured argumentation to construct arguments from a given KB. Regarding the expressivity comparison between various formalisms, [32] provided several translations between different argumentation formalisms, namely Assumption Based Argumentation (ABA) [17], ClaimAugmented Frameworks (CAF) [25], and Argumentation Frameworks with Collective Attacks (SETAF) [38]. This puts our work in a broader context by presenting novel translations from databases with expressive 1

We borrow this notation and write dep(x; y) and x ⊆ y for FDs and IDs, respectively.

Computing Database Repairs under Expressive ICs via Argumentation

Equivalence between DBs with expressive ICs and SETAFs, along with data complexity results. ICs

SETAF-equivalent semantics for repairs

DCs LTGDs DCs+LTGDs

σ ∈ {naive, pref, stab}⋆ pref (Thm. 14) pref (Thm. 18)

REPB

Complexity Results ∃-REPB ∀-REPB

(trivial) (trivial) ∈ P[2] ∈ P[2] NP (Thm. 19) NP (Thm. 19)

∈P ∈ P[2] ΠP2 (Thm. 20)

Equivalence between DBs with less expressive ICs and AFs, along with combined complexity results. ICs FDs IDs FDs+IDs

AF-equivalent semantics for repairs σ ∈ {naive, pref, stab}⋆ pref (Cor. 27) pref (Cor. 32)

REP

Complexity Results ∃-REP ∀-REP

(trivial) (trivial) ∈ P[2] ∈ P[2] NP (Thm. 33) NP (Thm. 33)

∈P ∈ P[2] ΠP2 (Thm. 36)

Table 1: Overview of our main contributions. The complexity results depict completeness, unless specified otherwise. The table at the top indicates results for expressive ICs involving a fixed set B of DCs and LTGDs, whereas the table at the bottom depicts results for less expressive ICs including FDs and IDs. The lower bounds for less expressive ICs also hold for data complexity since the involved reductions use fixed sets of constraints. The second column in each table indicates the (SET)AF-semantics corresponding to repairs for ICs in the first column, and the last three columns present the complexity of each problem. The P-results are already known in the literature, whereas the remaining results are new. Finally, the results marked by ⋆ follow from the earlier work by [14] and [18].

integrity constraints to SETAFs. Furthermore, recently [36] presented translations from AFs to inconsistent databases which is the converse direction to what we aimed to achieve in this paper. Their main findings indicate that one can translate argument interaction in an AF via functional and inclusion dependencies alone. Prior Work A preliminary version of this work was published in FoIKS 2024 [37]. The current paper expands the earlier work to more expressive integrity constraints. To be precise, we utilize SETAFs to simulate denial constraints and LTGDs using the same ideas as for functional and inclusion dependencies. The conference version focussed on functional and inclusion dependencies in connections to plain AFs. The results for DCs follow from the work of [14], thus the task is to extend them to LTGDs. The results of the conference version can now be derived as special cases from the more general results of this paper, when the involved ICs are FDs and IDs.

Preliminaries

We assume that the reader is familiar with basics of complexity theory and first-order logic. In particular, we will encounter (1) the complexity classes P, NP, and ΠP2 , and (2) closed first-order formulas having ∀.∃. as the quantifier prefixes. In the following, we shortly recall the necessary definitions from databases and argumentation. Databases A (relational) schema τ is a finite set of relation names. Each relation T ∈ τ is associated with a positive integer, called the arity of T . We consider a countable set C of constants to act as domain elements, from which the values can appear in a database. A term is either a constant from C or a variable.

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo E Emp ID Dept ID Location e1 E1 D1 Paderborn e2 E2 D2 Sheffield e3 E3 D2 Hanover

D Dept ID Dept Name Location d1 D1 Sales Paderborn d2 D2 Marketing Sheffield d3 D3 HR Hanover

Table 2: A database with two tables over the schema {E, D}. The first column indicates identifier for each fact/tuple.

Let t1 , . . . , tk be terms and T ∈ τ be a relation of arity k, the expression T (t1 , . . . , tk ) is called a relational atom. A relational atom composed of only constants is called a fact. Given a schema τ , a database T over τ is a finite set of facts using relation symbols from τ . The active domain of a database T is denoted as dom(T ) and defined as the collection of all the constant values from C that occur in facts of T . A fact can also be seen as a database tuple. In this notation, the fact T (a1 , . . . , ak ) corresponds to stating that the tuple (a1 , . . . , ak ) is a record in the (database) table T of arity k—which is a collection of such tuples, each with an associated unique identifier. For analogy, a table corresponds to a relation name T in a schema τ and can be seen as a grouping of facts together that use the same relation symbol (namely, T ). For a table T of arity k, the positions {1, . . . , k} in the columns of T are usually given explicit names, resulting in the set att(T ) of attributes of T . The active domain dom(T ) of T in the tabular view is the collection of all the values that occur in the tuples of T . We denote individual attributes (or variables) by small letters (e.g., x, y) and reserve boldface letters (e.g., x, y) for sequences of attributes. For an attribute x ∈ att(T ) and a tuple s ∈ T , s(x) denotes the value taken by s for the attribute x. For a sequence x = (x1 , . . . , xk ), s(x) denotes the sequence of values (s(x1 ), . . . , s(xk )). Given this tabular view, a database over schema τ = {T1 , . . . , Tm } is seen as a collection T = (T1 , . . . , Tm ) of tables corresponding to relation symbols in τ . Again, the active domain dom(T ) of a database T is the union of active domains of each table T ∈ T . We find it convenient to write a database without explicitly mentioning its schema and active domain always. We next present an example database. Example 1. Consider the schema {E, D}. The database tables over this schema (Figure 2) contain data about employees and departments, respectively. Here, E(E1, D1, Paderborn) is a fact and (E1, D1, Paderborn) is a tuple in E with identifier e1 . For presentation of examples, we refer to tuple identifiers also as facts. Hence, we write e1 for the fact E(E1, D1, Paderborn). ◁ Integrity Constraints. Integrity constraints are closed first-order formulas, i.e., all the variables are bound to quantification. In the following, we first specify different types of ICs. Let τ be a database schema. Recall that a database atom is an application of any relation name T ∈ τ over variables or constants. Let φ and ψi be conjunctions of database atoms and let β be a quantifier-free formula using only built-in predicates (e.g., equality or inequality). We call a formula of the form ∀x(φ(x) ∧ β(x) →

n _

∃yi ψi (x, yi ))

i=1

a generic first-order integrity constraint (FO). All other types of constraint languages arise from restrictions on the generic ICs, as we illustrate next. A generic IC is called full or a universal constraint (UC) if it contains no existential quantifiers. A denial constraint (DC) has the form ∀x¬(φ(x) ∧ β(x)), which can also be thought of as a UC with empty right hand side. An equality-generating dependency (EGD) has the form ∀x(φ(x) → xi = xj ), which can be thought of as a DC where β is a single inequality. Let T be an n-ary

Computing Database Repairs under Expressive ICs via Argumentation Generic ICs (FO) ∀x(φ(x) ∧ β(x) →

FO V-TGD

TGD LTGD ID

UC full V-TGD DC full TGD EGD FD key

6 Wn

i=1 ∃yi ψi (x, yi ))

V-TGD TGD LTGD ID

FO, where β is empty V-TGD, where n = 1 TGD, where φ is a single atom LTGD, where ψ1 is a single atom

UC DC EGD FD

FO with no existential quantifier UC, where ψi are empty (n = 0) DC, where β is a single inequality DC, where φ uses one relation symbol

Figure 1: Hierarchy of ICs and syntactic form for most commonly studied constraints [10].

relation and I, J ⊆ {1, . . . , n} be two sets with pairwise distinct variables x1 , .V . . , xn , y1 , . . . , ynV. Then, a functional dependency (FD) over T is an EGD of the form ∀x∀y(T (x) ∧ T (y) ∧ i∈I xi = yi → j∈J xj = yj ). A key constraint is a special type of FD requiring I ∪ J = {1, . . . , n}. A disjunctive tuple-generating dependency (∨-TGD) is a generic IC that has empty β and an ordinary tuple-generating dependency (TGD) additionally requires n = 1. A local-as-view TGD (LTGD) is a TGD where φ is a single atom and an inclusion dependency (ID) is an LTGD where ψi is also a single atom. Figure 1 (adapted from [10]) presents an overview of the hierarchy of different ICs together with their syntactic forms. The semantics for ICs is defined similarly to first-order (FO) formulas. A database T over schema τ gives rise to an FO-structure A over the vocabulary τ . The domain of A is the active domain dom(T ) of T and each relation symbol T ∈ τ is interpreted as the corresponding database table T in T , i.e., it contains all the tuples of constants (a1 , . . . , ak ) over dom(T ) such that T (a1 , . . . , ak ) ∈ T . Then, for an IC α, we write T |= α iff A |= α under the classical Tarski semantics. Moreover, one often uses a more convenient notation for FDs and IDs as we illustrate next. Let T be an n-ary relation, I, J ⊆ {1, . . . , n} be two sets and let x1 , . . . , xn , y1 , . . . , yn be pairwise distinct variables. Then, for V sequences XV= (xi | i ∈ I) and Y = (yj | j ∈ J), the functional dependency ∀x∀y(T (x) ∧ T (y) ∧ i∈I xi = yi → j∈J xj = yj ) can be equivalently expressed as dep(X; Y ) or X → Y (as done usually in the DBs setting). Moreover, let Ti and Tj be two relations, and x1 , x2 , x3 be sequences of variables. The inclusion dependency ∀x1 ∀x2 (Ti (x1 , x2 ) → ∃x3 Tj (x2 , x3 )) can be equivalently expressed as Ti [Y ] ⊆ Tj [X] where X (respectively, Y ) is the set of attributes of Tj (Ti ) corresponding to x2 . We find it convenient to write Y ⊆ X instead of T [Y ] ⊆ T [X] for an ID involving a single relation T . We will use this notation throughout our paper. The following example depicts ICs over the database from Example 1. Example 2. Consider a DC dc and an LTGD lav, as given below. dc := ∀x1 , x2 , x3 , x4 , x5 ¬(E(x1 , x2 , x3 ) ∧ D(x2 , x4 , x5 ) ∧ x3 ̸= x5 ) lav := ∀x1 , x2 , x3 (D(x1 , x2 , x3 ) → ∃y1 , y2 E(y1 , x1 , y2 )) The denial constraint dc states that the database should not contain any employees that work at a different location than where their department is located and the LTGD lav requires that every department has at least one employee. Both dc and lav are violated in the database from Example 1. ◁ Let T be a database (a collection of facts) and B be a collection of ICs. Then T is consistent with respect to B, denoted as T |= B, if T |= b for each b ∈ B. Moreover, T is inconsistent with respect to B if there is

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

some b ∈ B such that T ̸|= b. A subset-repair of T with respect to B is a subset P ⊆ T that is consistent with respect to B, and maximal in the sense that no set P ′ exists such that it is consistent with respect to B and P ⊂ P ′ ⊆ T . In the tabular view, the subset of a DB T = (T1 , . . . , Tm ) is defined as P = (P1 , . . . , Pm ), where Pi ⊆ Ti for each i ≤ m. In the following, we simply speak of a repair when we intend to mean a subset-repair. Furthermore, we often consider a database T and a set B of ICs assuming that B only uses relation names from the schema of T . In that case, we call D = ⟨T , B⟩ a constrained database. For a constrained database D, repairs(D) denotes the set of all repairs for D. The first problem we are interested in (REP) asks whether there exists a repair for a constrained database D. Since the empty database (∅) satisfies each IC trivially, we are interested in the decision problem asking whether a non-empty repair exists. Problem:

REP

Input: a constrained database D = ⟨T , B⟩. Question: is there a repair R ∈ repairs(D) with R = ̸ ∅? Two further problems of interest are brave and cautious reasoning for a given fact s ∈ T , asking whether s belongs to some (every) repair for D. Problem:

∃-REP

Input: a constrained database D = ⟨T , B⟩ and a fact s ∈ T . Question: does s belong to some repair for D? Problem:

∀-REP

Input: a constrained database D = ⟨T , B⟩ and a fact s ∈ T . Question: does s belong to all repairs for D? We also consider the case when the set B of integrity constraints is fixed and the input only involves a database T (and a fact s). This gives rise to separate decision problems REPB , ∃-REPB and ∀-REPB , for each B. We can then define the of data complexity of REP, ∃-REP and ∀-REP, in the usual way. That is, for a complexity class C, the data complexity of REP is in C, if REPB is in C, for every B, and C-hard, if REPB is C-hard, for some B. Thus, the problems defined above (i.e., REP, ∃-REP and ∀-REP) then correspond to the setting of combined complexity. Observe that our focus in this work lies on inconsistent databases, i.e., we assume that T is inconsistent with respect to B in a constrained database D = ⟨T , B⟩. This is not a restriction since the considered questions about repairs are trivial if the database is consistent with respect to its constraints. Moreover, all our translations to (SET)AFs and the connection between repairs and extensions still apply to the consistent case, although they do not provide much insight. The following example presents a repair for the database from Example 1 with respect to the ICs from Example 2. Example 3. Reconsider the database from Example 1, which is inconsistent with the ICs from Example 2. Here, the fact d3 violates lav, and the only way to resolve this violation (in our subset-repair setting) is to remove d3 . Moreover, the set {e3 , d2 } also violate dc. This results in two ways to repair our database, by removing either of those facts. Thus, we have two subset-maximal repairs, namely {e1 , e2 , d1 , d2 } and {e1 , e2 , e3 , d1 }. ◁

Computing Database Repairs under Expressive ICs via Argumentation

Abstract Argumentation We use Dung’s argumentation framework [23] and consider only non-empty and finite sets of arguments A. An (argumentation) framework (AF) is a directed graph F = (A, R), where A is a set of arguments and the relation R ⊆ A × A represents direct attacks between arguments. If S ⊆ A, we say that an argument s ∈ A is defended by S in F, if for every (s′ , s) ∈ R there exists s′′ ∈ S such that (s′′ , s′ ) ∈ R. In abstract argumentation one is interested in computing the so-called extensions, which are subsets S ⊆ A of the arguments that have certain properties. The set S of arguments is called conflict-free in F if (S × S) ∩ R = ∅. Let S be conflict-free, then S is 1. naive in F if no S ′ ⊃ S is conflict-free in F; 2. admissible in F if every s ∈ S is defended by S in F. Further, let S be admissible. Then, S is 3. preferred in F, if there is no S ′ ⊃ S that is admissible in F; 4. stable in F if every s ∈ A \ S is attacked by some s′ ∈ S. We denote each of the mentioned semantics by abbreviations: conf, naive, adm, pref, and stab, respectively. For a semantics σ ∈ {conf, naive, adm, pref, stab}, we write σ(F) for the set of all extensions of semantics σ in F. Now, we are ready to define the corresponding decision problem asking for extension existence with respect to a semantics σ. Problem:

Extσ

Input: an argumentation framework F. Question: is it true that σ(F) ̸= ∅? Finally, for an AF F=(A, R) and a ∈ A, we define the problems Credσ and Skepσ , which ask whether a is in some σ-extension of F (“credulously accepted”) or every σ-extension of F (“skeptically accepted”), respectively. Problem:

Credσ

Input: an AF F = (A, R) and an argument a ∈ A. Question: is it true that a ∈ E for some E ∈ σ(F)? Problem:

Skepσ

Input: an AF F = (A, R) and an argument a ∈ A. Question: is it true that a ∈ E for all E ∈ σ(F)? Example 4. Consider the argumentation framework AF = {a, b, c, d} with the attack relation as depicted in Figure 2. Then extensions for F are also depicted in Figure 2 for the mentioned semantics. ◁ The complexity of reasoning in argumentation is well understood, see [24, Table 1] for an overview. In particular, Crednaive and Skepnaive are in P, whereas, Credpref and Skeppref are NP-complete and ΠP2 -complete, respectively. Moreover, the problem to decide whether there is a non-empty extension is in P for naive and NP-complete for pref-semantics. This makes naive-semantics somewhat easier and pref the hardest among the considered semantics in this work.

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

Naive: Admissible: Preferred: Stable:

{a, c}, {a, d}, {b, d} {a}, {a, c}, {b}, {b, d} {a, c}, {b, d} {a, c}, {b, d}

Figure 2: Framework F from Example 4 (Left) and extensions for given semantics (Right).

b a

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 ⊆ 2V × V . A set-based argumentation framework (SETAF) is a B-hypergraph F = (A, R) where A is the set of arguments and R ⊆ 2A × A represents the attacks from sets of arguments to individual arguments. A subset S ⊆ A of arguments is conflict-free, if (2S × S) ∩ R = ∅ and S defends an argument s ∈ A if for every (S ′ , s) ∈ R there exists S ′′ ⊆ S such that (S ′′ , s′ ) ∈ R for some s′ ∈ S ′ . For S = {s} a singleton set, we prefer denoting the attack ({s}, s′ ) by (s, s′ ). With this definition of conflict-freeness, the notions of naivety, admissibility, preferredness and stability are defined analogously to plain AFs. The corresponding decision problem for the extensions existence is defined as follows. Problem:

ExtSET σ

Input: a SETAF F. Question: is it true that σ(F) ̸= ∅? For a SETAF F and argument a ∈ A, we similarly define the problems Credσ and Skepσ asking whether a is in some σ-extension of F or every σ-extension of F, respectively. Example 5. Consider the SETAF S = (A, R), where A = {a, b, c, d, e} and R = {({a, b}, d), ({b, c}, e), ({e}, a)}. In S, the extension {a, b, c} is conflict-free, preferred and stable. Note that {b, c} defends a against {e}. This example is visualized in Figure 3. ◁

Translating Databases to Argumentation Frameworks

In this section, we prove that repairs under expressive families of integrity constraints (involving DCs and LTGDs) can be equivalently seen as extensions in SETAFs. In the first two subsections, we consider instances containing only one type of ICs to SETAFs and the third subsection combines both constraints (DCs and

Computing Database Repairs under Expressive ICs via Argumentation

LTGDs). Given an instance D = ⟨T , B⟩ comprising a database T and a set B of ICs, the goal is to capture all the subset-repairs for D by σ-extensions of the resulting SETAF SD for some semantics σ. In Section 3.1, we encode a constrained database D = ⟨T , D⟩ with database T and a collection D of DCs into a SETAF SD . This is achieved by letting each fact s ∈ T be an argument. Then the attack relation between arguments simulates the violation of some d ∈ D by sets of facts. This allows to establish a connection between repairs for D and the extensions for the resulting SETAF under preferred, stable and naive semantics. This construction for DCs is a special case of the results by [14]. In our case, we do not consider priorities among facts in the database which allows a weaker SETAF-semantics (naive extensions) to capture repairs. In Section 3.2, we simulate a constrained database D = ⟨T , L⟩ including a collection L of LTGDs via SETAFs. The first observation is that the semantics for LTGDs requires the notion of support or defense rather than conflict between facts. Then, we depict each fact as an argument as well as use auxiliary arguments to simulate the dependency ℓ ∈ L (i.e., to model the semantics for LTGDs). Further, we add self-attacks for these auxiliary arguments to prohibit them from appearing in any extension. Consequently, we establish a connection between repairs for D and the extensions for SETAFs under preferred semantics. Finally, we present a polynomial-time processing of the resulting SETAFs that computes its unique preferred extension, which also yields a unique repair for D. Interestingly, the computed preferred extension is also stable and naive, and hence coincides with the only repair for D. Our construction for LTGDs relies on self-attacking arguments. This allows us to avoid taking auxiliary arguments in any extension and establish a connection between repairs of a DB and extensions of the resulting SETAF. Towards the end of our paper, we discuss (Section 5.1) the role played by the self-attacking arguments and a possibility for a different translation from DBs to (SET)AFs. Having established that both DCs and LTGDs can be modeled in SETAFs via attacks, Section 3.3 generalizes this approach by allowing both types of constraints. We observe that no prior work has handled the case of tuple-generating dependencies (to our knowledge).

3.1

Simulating Denial Constraints via SETAFs

We first formalize the notion of conflicts for a DB with respect to a set of denial constraints. Intuitively, a conflict in a constrained database D is a minimal (under set inclusion) inconsistent set of facts from T with respect to some denial constraint in D. Definition 6. Let D = ⟨T , D⟩ be a constrained database with a set D of DCs. A collection C ⊆ T of facts is a conflict in D if there exists some d ∈ D such that (i) C ̸|= d, and (ii) C ′ |= d for each proper subset C ′ ⊊ C. Given D, then by Conf(D) we denote the set of all conflicts in D. It is known that Conf(D) can be represented as a conflict hypergraph [18] where the vertices are the facts in D and hyperedges are conflicts in T . We follow [14] and transform an instance D = ⟨T , D⟩ with database T and a collection D of DCs to a SETAF SD . Definition 7 ([14]). Let D = ⟨T , D⟩ be a constrained database including a database T and a collection D of DCs. Then, SD denotes the following SETAF. • A := T , i.e, each fact s ∈ T is seen as an argument. • R := {(C \ {t}, t) | C ∈ Conf(D), t ∈ C}. We call SD the SETAF generated by D.

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

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” is DP-complete even if T and T ′ are both fixed [10, Lemma 6]. The complexity of the repair checking problem drops to P if we consider a fixed set of denial constraints. As a result, one normally considers a fixed set D of DCs. In our encoding, this has the effect that one can construct the argumentation framework from a constrained database D in polynomial time. Furthermore, given the conflict hypergraph GD for a constrained database D, the framework SD can still be constructed in polynomial time in the size of GD . ′

Example 8. Consider the following database tables C and O, containing the data about customers and orders, respectively. C Cus ID Location s1 C1 Paderborn C2 Sheffield s2 s3 C3 Hanover

O Ord ID Cus ID t1 O1 C1 O2 C2 t2 O3 C2 t3 t4 O5 C1

Prod ID P1 P2 P1 P1

Ship ID S1 S2 S1 S4

Here, Cus ID, Ord ID, Prod ID and Ship ID are the IDs of individual customers, orders, products and shipments, respectively. Let D = {dc1 , dc2 } be a set of denial constraints where dc1 := ∀x1 , . . . , x6 ¬(O(x1 , x2 , x3 , x4 ) ∧ O(x5 , x2 , x3 , x6 ) ∧ x1 ̸= x5 ) and dc2 := ∀x1 , . . . , x9 ¬(O(x1 , x2 , x3 , x4 ) ∧ O(x5 , x6 , x7 , x4 ) ∧ C(x2 , x8 ) ∧ C(x6 , x9 ) ∧ x8 ̸= x9 ). The denial constraint dc1 essentially says that no customer should have more than one order for the same product and dc2 requires that no orders to different locations can be transported in the same shipment. Both constraints are violated in the tables C and D. The conflicts in the DB include {t1 , t4 }, {t1 , t3 , s1 , s2 }. The respective SETAF S⟨{C,O},D⟩ is depicted in Figure 4. ◁ It is known that the repairs for D correspond precisely to the independent sets of its conflict hypergraph GD . Observe that the independent sets in GD are exactly the naive extensions of SD . Moreover, using the

Computing Database Repairs under Expressive ICs via Argumentation

observations from [14, Theorem 28], it is easy to see that every naive extension is also preferred as well as stable. Therefore, we have the following equivalence between the extensions and repairs. The equivalence regarding the stable and preferred semantics is a direct consequence of the results in [14]. Theorem 9. Let D = ⟨T , D⟩ be a constrained database where D is a set of DCs and let SD denote the SETAF generated by D. Then for every P ⊆ T , P ∈ repairs(D) iff P ∈ σ(SD ) for σ ∈ {naive, stab, pref}. Proof. Given a repair P ⊆ T , then P |= d for every d ∈ D and hence there is no C ∈ Conf(D) with C ⊆ P. So, the set of arguments in P is conflict-free since every attack in R has the form (E \ {t}, t) where E ∪ {t} ∈ Conf(D). The converse holds similarly. A naive extension P ⊆ A does not contain all the arguments in any attack (E, t). Thus, for every conflict C ∈ Conf(D), such that C = E ∪ {t}, we have that C ̸⊆ P and therefore P (seen as a subset of T ) is a repair for D. Finally, the subset-maximality remains the same for both cases since each fact is seen as an argument and vice versa. This establishes the correctness of our theorem. It is worth remarking that the presence of DCs with a single database atom yields singleton conflicts which results in self-contradictory facts (or self-attacking arguments in the translation). However, such self-contradictory facts do not occur in any repair and can be removed using existing reasoning algorithms, as highlighted by Bienvenu and Bourgaux [14]. Therefore, a usual assumption is that every denial constraint contains at least two database atoms. This has the effect that each conflict contains at least two argument. Consequently, in the presence of DCs, every fact in a conflict belongs to at least one repair and no fact in any conflict belongs to every repair. This holds because for each conflict C ∈ Conf(D), there is a repair containing facts in C \ {t} as well as another one containing t. As a result, we have the following observation regarding the acceptability of facts with respect to D. Specifically, we can decide if a given fact s ∈ T is in some (or all) repairs, in polynomial time for a fixed set of DCs. Remark 10. Let D be a set of DCs over the schema τ . Then, for every constrained database D = ⟨T , D⟩ involving a database T over τ : ∃-REP is true for every s ∈ T and ∀-REP is true iff s ̸∈ C for any C ∈ Conf(D). Moreover, both problems are decidable in polynomial time in data complexity.

3.2

Simulating LTGDs via SETAFs

Let D = ⟨T , L⟩ be a constrained database with a collection T of facts and a collection L of LTGDs. We recall the semantics for LTGDs via variable assignments. For a set V of variables, an assignment of V into a database T is a mapping h : V → dom(T ). For a relational atom T (t) with terms t = (t1 , . . . , tk ), we denote by h(T (t)) the result of substituting every ti in T (t) by h(ti ), where we set h(ti ) = ti when ti is a constant. In other words, an assignment maps a relational atom T (t) to a candidate fact h(T (t)), which may or may not be present in the database T . The notation extends to a conjunction of atoms by considering them V := as a set. Precisely, for a conjunction ϕ(x) 1≤i≤n Ti (xi ) with xi ⊆ x and Ti ∈ τ , and an assignment h : x → dom(T ), we define h(ϕ(x)) = {h(T (x V i i )) | 1 ≤ i ≤ n}. Recall that every LTGD ℓ ∈ L has the form ∀x(T (x) → ∃yψ(x, y)) where ψ := 1≤i≤nℓ ψi (zi ) is a conjunction of relational atoms over variables zi ⊆ x ∪ y using relation names ψi ∈ τ . Then, T |= ℓ if for each assignment h such that h(T (x)) ∈ T , there exists an assignment h′ : x ∪ y → dom(T ) such that h′ ↾x = h ↾x and h′ (ψ(x, y)) ⊆ T , where h ↾x is the restriction of h on x. If h(T (x)) ∈ T is true and there indeed exists such an assignment h′ then we say that the set of facts h′ (ψ(x, y)) supports the fact h(T (x)) for the LTGD ℓ. For such an LTGD ℓ, we call T the source of ℓ, denoted as source(ℓ). For a source(ℓ)-fact s, we denote by Sℓ (s) the collection of all the sets

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

supporting s for the LTGD ℓ. It is worth remarking that, for a constrained database D = ⟨T , L⟩ and ℓ ∈ L, D |= ℓ if and only if Sℓ (s) ̸= ∅ for each source(ℓ)-fact s. Interestingly, we can encode the sets supporting a fact by using SETAFs, as formalized next. Definition 11. Let D = ⟨T , L⟩ be a constrained database including a database T and a collection L of LTGDs. Then SD is the following SETAF. • A := {s | s ∈ T } ∪ {sℓ | s is a source(ℓ)-fact for ℓ ∈ L}, • R := {(sℓ , s), (sℓ , sℓ ) | s is a source(ℓ)-fact for ℓ ∈ L} ∪ {(S, sℓ ) | S ∈ Sℓ (s), ℓ ∈ L}. Intuitively, for each ℓ ∈ L and a source(ℓ)-fact s, the attack (sℓ , s) models that the LTGD ℓ ∈ L must be satisfied for the fact s. Moreover, the self-attacks (sℓ , sℓ ) enforce that the extensions only contain arguments corresponding to facts in the database. Then, each S ∈ Sℓ (s) attacks sℓ and consequently, defends V s against sℓ . The whole idea captured in this translation is that for each ℓ ∈ L of the form ∀x(T (x) → ∃y 1≤i≤nℓ ψi (zi )) where zi ⊆ x ∪ y: a T -fact s is in a repair P of D if and only if there are ψi -facts ti for 1 ≤ i ≤ nℓ , such that {t1 , . . . , tnℓ } ∈ Sℓ (s) if and only if the set S = {t1 , . . . , tnℓ } attacks sℓ in SD if and only if the argument s ∈ A is defended against sℓ in SD . Example 12. The database tables E, D and P contain data about employees, departments and projects, respectively, and are defined as follows: E Emp ID Dept ID s1 E1 D1 s2 E2 D2 s3 E3 D3

D Dept ID Dept Name t1 D1 Accounting t2 D3 Sales

P Prod ID Dept ID u1 P1 D1 u2 P2 D3

Here, Emp ID, Dept ID and Prod ID are the IDs of individual employees, departments and products, respectively. Let L = {lav1 , lav2 } be a set of LTGDs where lav1 := ∀x1 , x2 (E(x1 , x2 ) → ∃y, z(D(x2 , y) ∧ P (z, x2 ))) and lav2 := ∀x1 , x2 (D(x1 , x2 ) → ∃y, z(E(y, x1 ) ∧ P (z, x1 ))). The constraint lav1 essentially says that if an employee is in a department, then the department must exist and be associated with a project. The constraint lav2 says that each department has at least one employee and at least one project associated with it. In the tables E, D and P , lav1 is violated while lav2 is satisfied. The source of each TGD ℓ, and the supporting facts for source(ℓ)-fact s are presented as follows: • source(lav1 ) = E, • source(lav2 ) = D, • {t1 , u1 } supports s1 for lav1 , • s2 does not have any supporter for lav1 • {t2 , u2 } supports s3 for lav1 ,

Computing Database Repairs under Expressive ICs via Argumentation

s11

s12

s13

t21

t22

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 Figure 5.

◁

Similar to the case of DCs, the repair checking problem under LTGDs is DP-complete if the set L of ICs is considered as input [10, Table 3]. Therefore, we consider a fixed set L of LTGDs as the complexity drops to P in this case. Then, for a constrained database D = ⟨T , L⟩, the framework SD can be constructed in polynomial time. An algorithm basically goes through every ℓ ∈ L in turn: for each source(ℓ)-fact s, it computes the set Sℓ (s) in polynomial time since the size of each LTGD in L is constant. For a set L of LTGDs, a minimal violation of ℓ ∈ L is caused by a single source(ℓ)-fact s for which Sℓ (s) = ∅. Since we only allow subset repairs (deleting facts), the only way to eliminate a violation is to remove such a fact s. However, this removal of facts may trigger other violations for facts, all of whose supporting sets contained some deleted facts. This triggers a chain reaction and the repair process iteratively removes any fact that has no remaining supporting set. Since the database is finite, this process eventually terminates (in the worst case there are no facts remaining and ∅ is the only repair). The remaining facts are exactly those that have at least one full support left, so no violations remain. The key observation is that this process always leads to the same final set of facts, no matter in which order we remove unsupported facts. Therefore, the final set of facts is consistent and subset-maximal. Observe that in some cases ∅ might be the only repair for a database D involving LTGDs. Remark 13. A constrained database D = ⟨T , L⟩ involving a set L of LTGDs admits a unique repair. Now we prove that the repair of an instance D actually corresponds to the unique preferred extension of the resulting SETAF SD . Theorem 14. Let D = ⟨T , L⟩ be a constrained database where L is a set of LTGDs and let SD denote the SETAF generated by D. Then for P ⊆ T , P ∈ repairs(D) iff P ∈ pref(SD ). Moreover, SD has exactly one preferred extension. Proof. We first prove the reverse direction. Let P ⊆ A be a preferred extension in SD , then P must not contain an auxiliary argument sℓ corresponding to any LTGD ℓ ∈ L since P is conflict-free. This implies

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

that P ⊆ T , which together with the fact that P is admissible (hence every s ∈ P is defended against each sℓ ∈ A) and maximal under set inclusion yields the proof of the claim. Conversely, let P ⊆ T denote a repair for D = ⟨T , L⟩. Then P is conflict-free in SD since each attack in R contains at least one argument among the auxiliary arguments (sℓ ) which are not in P (as P ⊆ T ). Moreover, for each s ∈ P and ℓ ∈ L, there are t1 , . . . , tnℓ ∈ P, such that {s, t1 , . . . , tnℓ } |= ℓ. This implies that each s ∈ P is defended against the attack sℓ ∈ A since ({t1 , . . . , tnℓ }, sℓ ) ∈ R. Consequently, P is admissible. To prove that P is also preferred in SD , assume to the contrary that there is an admissible P ′ ⊃ P in SD . Since P ′ is also conflict-free, using the same argument as for P we notice that P ′ ⊆ T . Now, P ′ being admissible (together with the claim in reverse direction) implies that P ′ is a repair for D contradicting the fact that P is a subset-maximal repair for D. As a consequence, P is preferred in SD . This proves the correctness of the theorem. The uniqueness of the extension follows due to Remark 13. Notice that a framework SD may not have stable extensions for certain constrained databases D including databases T and LTGDs L. This holds because some arguments can neither be accepted in an extension (e.g., when Sℓ (s) = ∅ for some source(ℓ)-fact s and ℓ ∈ L), nor attacked by arguments in an extension (since arguments in A only attack auxiliary arguments). Mahmood et al. [37] presented a pre-processing over the argumentation framework generated by a constrained database D involving inclusion dependencies, which computes its unique preferred extension which is also naive and stable. It is easy to observe that a similar pre-processing can be implemented for the case of LTGDs. This pre-processing also allows us to answer credulous and skeptical acceptance for a fact s ∈ T in polynomial time considering the data complexity. A pre-processing algorithm for SD . Observe that an undefended argument in a SETAF S = (A, R) cannot belong to any preferred extension of S. The intuition behind pre-processing is to remove such arguments, which are not defended against some of their attacks in SD . This corresponds to (recursively) removing those facts s ∈ T , for which there is ℓ ∈ L such that s is a source(ℓ)-fact and Sℓ (s) = ∅. The pre-processing (denoted PRE(SD )) applies the following procedure as long as possible. * For each sℓ ∈ A such that sℓ is not attacked by any S ⊆ A \ {sℓ }: remove s, sj for each j ∈ L, as well as each attack to and from s and sj . We repeat this procedure until convergence. Once a fixed point has been reached, the remaining arguments in A are all defended. Interestingly, after the pre-processing, removing the arguments with self-attacks results in a unique naive extension which is also stable and preferred. In fact, this naive extension corresponds to the unique repair of the instance D (see Remark 13). In the following, we also denote by PRE(SD ) the SETAF obtained after applying the pre-processing on SD . Notice that PRE is basically an adaptation to the SETAFs of the previously presented procedure for AFs and originates from the well-known algorithm for finding a maximal satisfying subteam for inclusion logic formulas [27, Lem. 12]. Lemma 15. Let L be a fixed set of LTGDs, D = ⟨T , L⟩ be a constrained database, and SD denote the SETAF generated by D. Then PRE(SD ) can be computed from SD in polynomial time. Moreover, PRE(SD ) has a unique naive extension which is also stable and preferred. Proof. The procedure PRE(SD ) removes recursively all the arguments corresponding to facts s such that Sℓ (s) = ∅ for some ℓ ∈ L and s is a source(ℓ)-fact. Notice that Sℓ (s) can be computed for each ℓ ∈ L and source(ℓ)-fact s in polynomial time for a fixed set L of LTGDs. Then, PRE stores in a data structure (such as a queue) all the arguments s for which Sℓ (s) = ∅. Finally, each argument s in this queue can be processed

Computing Database Repairs under Expressive ICs via Argumentation

turn by turn, adding possibly new arguments when PRE triggers the removal of certain arguments from A and hence from Sℓ (t) for some t ∈ A. A fixed-point is reached when every element in the queue has been processed, this gives the size of A as the total number of iterations. Consequently, PRE runs in polynomial time in the size of SD . Let PRE(SD ) = (A′ , R′ ) denote the SETAF generated by the pre-processing. To prove the equivalence between extensions, notice that the set of arguments S without self-attacks in A′ forms a naive extension since S is conflict-free and every argument in A′ \ S contains self-attacks. Moreover, S is also admissible since Sℓ (s) ̸= ∅ for every argument s ∈ S corresponding to a source(ℓ)-fact s. Furthermore, since A′ \ S only includes auxiliary arguments, those are all attacked by S and therefore S is stable. Finally, S is the only naive extension in the reduced AF since S is the maximal conflict-free in PRE(SD ) and arguments in A′ \ S contain self-attacks. This establishes the correctness of the lemma together with Theorem 14. As a consequence of Lemma 15, we can also determine ∃-REP and ∀-REP for each s ∈ T , once the pre-processing has terminated resulting in PRE(SD ). Remark 16. Let D = ⟨T , L⟩ be a constrained database involving a set L of LTGDs and SD denote the SETAF generated by D. Then, ∃-REP and ∀-REP is true for every s ∈ T iff s ∈ PRE(SD ). As a consequence, both problems are decidable in polynomial time in data complexity.

3.3

Simulating DCs and LTGDs via SETAFs

Consider an instance D = ⟨T , B⟩ with a database T and a collection B = D ∪ L of DCs (D) and LTGDs (L). We first understand the role of applying pre-processing in the presence of both ICs. Removing those facts from T failing some LTGD reduces the number of arguments in the resulting SETAF without affecting the connection between extensions and repairs. The removed facts are limited to those that cannot belong to any repair since we are in the setting of subset-repairs. However, one still cannot directly answer ∃-REP or ∀-REP (as done in Remark 16) for all facts s ∈ T even after applying this pre-processing. Moreover, in the presence of both types of ICs, one may want to see the effect of the failure of LTGDs and DCs separately for certain facts. In other words, one can distinguish a fact violating an LTGD since it does not have a supporting fact in T from another fact violating an LTGD since all of its supporting facts also violate some DCs. In this case, the pre-processing allows to distinguish these facts even if they are not removed from the resulting SETAF. In the following, we do not apply pre-processing and instead consider all the arguments for facts in the database. The framework SD := (A, RD ∪ RL ) generated by D is specified as below. Definition 17. Let D = ⟨T , B⟩ be a constrained database including a database T and a collection B = D∪L of DCs D and LTGDs L. Then, we construct the SETAF SD = (A, RD ∪ RL ) as follows. • A := {s | s ∈ T } ∪ {sℓ | s is a source(ℓ)-fact for ℓ ∈ L}, • RD := {(C \ {t}, t) | C ∈ Conf(D), t ∈ C}, • RL := {(sℓ , s), (sℓ , sℓ ) | s is a source(ℓ)-fact for ℓ ∈ L} ∪ {(S, sℓ ) | S ∈ Sℓ (s) for ℓ ∈ L}. As before, we call SD the SETAF generated by D.

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

A consequence of allowing both types of ICs (DCs and LTGDs) is that the preferred and naive extensions do not coincide in general. Moreover, both ∃-REP and ∀-REP are non-trivial and distinct (cf. Remarks 10 and 16). Furthermore, in the presence of both types of ICs, the repairs correspond to somewhat costly (that is, preferred) SETAF-semantics. Theorem 18. Let D = ⟨T , B⟩ be a constrained database where B includes DCs and LTGDs. Further, let SD denote the SETAF generated by D. Then for every subset P ⊆ T , P ∈ repairs(D) iff P ∈ pref(SD ). Proof. The correctness follows from the proofs of Theorem 9 and 14. The conflict-freeness and admissibility of P implies that each DC and LTGD in B, respectively, is true in P. The converse follows the same line of argument. Finally, the maximality of repairs in D corresponds to the maximality of extensions in the resulting SETAF SD . Next we establish that allowing DCs and LTGDs renders the data complexity for repair existence (REP), as well as credulous (∃-REP) and skeptical (∀-REP) reasoning for facts, same as, respectively, the existence, credulous and skeptical reasoning for preferred semantics for AFs. These lower bounds are proven for the case of FDs and IDs (see Theorem 33 and 36). Here we prove that the upper bounds hold even if we extend FDs to DCs and IDs to LTGDs, respectively. However, the set of ICs has to be fixed. Theorem 19. The problems REP and ∃-REP are both NP-complete in the data complexity for DCs and LTGDs. Proof. We prove that REPB and ∃-REPB are both in NP for any fixed set B of DCs and LTGDs. Let D = ⟨T , B⟩ be a constrained database involving a database T . For membership, one needs to guess a repair for D that is non-empty, respectively contains s. The verification can be done in P since B is a fixed set [10]. Notice that we do not need to check the maximality, since if there is a non-empty subset of T satisfying every IC in B (resp., a subset containing s) then there is also a non-empty repair for D (containing s). Hardness follows from the case of FDs and IDs proved in Theorem 33. To be precise, we construct a fixed set B (resp., B ′ ) of FDs and IDs for which the problem REPB (∃-REPB′ ) is NP-hard. Theorem 20. The data complexity of ∀-REP is ΠP2 -complete for DCs and LTGDs. Proof. For membership, we prove that ∀-REPB is in ΠP2 for any fixed set B of DCs and LTGDs. To this aim, we present the following Σ2P procedure for the complement of ∀-REPB . Let D = ⟨T , B⟩ be a constrained database involving a database T . One can guess a set P of facts in T satisfying each IC in B as a counterexample for s, that is, s ̸∈ P and P is a (candidate) repair for D, which can be decided in P since B is fixed [10]. However, one has to use oracle calls to determine whether P is a repair (hence maximal). Then, ∀-REP is true for s if there exists no P ⊆ T such that (i) P satisfies each IC in B, (ii) s ̸∈ P, and (iii) P is a repair. This gives the stated upper bound of ΠP2 . For hardness, we prove that there exists a set B of DCs and LTGDs such that the problem ∀-REPB is ΠP2 -hard. We prove this claim for the case of FDs and IDs in Theorem 36. We conclude this section by noting that the combined complexity of REP, ∃-REP, and ∀-REP remains open for now, although the hardness transfer from the data complexity.

Computing Database Repairs under Expressive ICs via Argumentation

The Case of Less Expressive ICs

In this section, we consider FDs and IDs, which are restricted classes of ICs inside DCs and LTGDs, respectively. The two sub-cases are interesting due to the fact that one only requires binary conflicts/supports. As a result, the classical Dung’s AFs with binary attacks suffice for encoding repairs into extensions. Following the same theme as in Section 3.3, the first two subsections translate instances containing only one type of ICs to AFs. Then, we combine both (functional and inclusion) dependencies in the third subsection. As before, we adopt the construction for FDs from [14], but without fact priorities, thus resulting in the need for a weaker AF-semantics to capture repairs Having established that both FDs and IDs can be modeled in AFs via binary attacks, Section 4.3 generalizes this approach by allowing both types of dependencies. The primary result of this section is noteworthy: it demonstrates that the integrity constraints can be restricted from (1) DCs to FDs and (2) LTGDs to IDs, while the corresponding encoding into argumentation frameworks preserves the exact semantics, modulo the transition from SETAFs to AFs.

4.1

Simulating Functional Dependencies via AFs

We transform an instance D = ⟨T , D⟩ with database T and a collection D of FDs to an AF FD . In the case of FDs, each conflict involves two facts failing some functional dependency d ∈ D. As a result, this conflict can be modeled in an AF by drawing a bi-directional attack between the two corresponding arguments. For this reason, we adhere to AFs rather than SETAFs. Recall that each FD is defined over a single relation T in the schema of D. Definition 21. Let D = ⟨T , D⟩ be a constrained database including a database T and a collection D of FDs. Then, FD denotes the following AF. • A := T , that is, each s ∈ T is seen as an argument, • R := {(s, t), (t, s) | s, t ∈ T and {s, t} ̸|= d for some d ∈ D}. We call FD the argumentation framework generated by D and call R the conflict graph for D. Note that, for a given constrained database D, the framework FD can be generated in polynomial time. The attack relation R is constructed for each d ∈ D over T in the schema of D by taking each pair s, t of T -facts in turn and checking whether {s, t} |= d or not. Moreover, the set D of FDs does not have to be fixed, as in the case of DCs. Example 22. Consider D = ⟨T, D⟩ with database T = {s, t, u, v} as depicted inside table in Figure 6 and FDs {dep(Emp ID; Dept), dep(Sup ID; Building)} over T . Informally, each employee is associated with a unique department and employees supervised by the same supervisor work in the same building. Observe that, {s, t} ̸|= dep(Emp ID; Dept), {u, v} ̸|= dep(Emp ID; Dept), and {t, v} ̸|= dep(Sup ID; Building). The resulting AF FD is depicted on the right side of Figure 6. The preferred (as well as naive and stable) extensions of FD include {s, v}, {t, u} and {s, u}. Clearly, these three are the only repairs for D. ◁ It is easy to observe that any subset P ⊆ T that satisfies each d ∈ D contains precisely those facts in T that are not pairwise conflicting. As a result, such subsets correspond to the naive extensions (maximal

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

T s t u v

Emp ID Sup ID Dept. TimX3 JonX1 Marketing TimX3 AxeK4 Sales JonX1 JonX1 Production JonX1 AxeK4 Distribution

Building B1 B2 B1 B4

Figure 6: Argumentation framework for modelling FDs in Example 22.

conflict-free sets) of FD . Moreover, since the attack relation in FD is symmetric, i.e., (s, t) ∈ R iff (t, s) ∈ R, the preferred, stable and naive extensions coincide [19, Prop. 4 & 5]. Observe that every FD is also a DC and hence the AF FD coincides with the SETAF SF for the constrained database D. As a consequence, we have the following corollary due to Theorem 9. In particular, each conflict set C (see proof of Theorem 9) has size two for FDs. Corollary 23. Let D = ⟨T , D⟩ be a constrained database where D is a set of FDs and let FD denote the argumentation framework generated by D. Then for every subset P ⊆ T , P ∈ repairs(D) iff P ∈ σ(FD ) for σ ∈ {naive, stab, pref}. Corollary 23 reproves that a subset-repair for D can be computed in polynomial time [24]. Moreover, similar to the case of DCs, we can decide if a given fact s ∈ T is in some (or all) repairs, in polynomial time. In fact, it follows from the basic properties of functional dependencies that ∃-REP is true for every s ∈ T , and ∀-REP is true for a fact s ∈ T iff {s, t} |= d for each t ∈ T and d ∈ D. Furthermore, the latter problem can be decided in polynomial time for an input D where the set D of FDs does not have to be fixed (see Remark 10). We conclude this section by observing that adding a size restriction on repairs renders the REP problem NP-hard. Observe that the hardness follows due to a one-to-one correspondence between repairs and maximal independent sets of the conflict graph [34]. However, we strengthen this result and note that the hardness already holds for propositional databases involving a single relation, that is, for a database T with dom(T ) = {0, 1}. The following result was proven in the context of team-semantics and maximal satisfying subteams for propositional dependence logic. Proposition 24. [35, Theorem 3.32] There is a constrained database D including a propositional database T and FDs D, such that given k ∈ N, the problem to decide whether there is a repair P ⊆ T for D such that |P | ≥ k is NP-complete.

4.2

Simulating Inclusion Dependencies via AFs

Let D = ⟨T , I⟩ be a constrained database with a database T and collection I of IDs. Similar to the case of LTGDs, for an ID i ∈ I (say, i := T [x] ⊆ T ′ [y]), we call T the source of i. Moreover, we call T ′ the target of i. For i ∈ I and a source(i)-fact s, let t be target(i)-fact such that {s, t} |= i. Then we say that t supports s for the ID i ∈ I, and Si (s) denotes the set of all such supporting facts for s and an ID i. Notice that for each i ∈ I and source(i)-fact s, we have that Si (s) ⊆ target(i). Thus, the elements in Si (s) are facts instead of sets of facts as in the case of LTGDs. Clearly, D |= i if and only if Si (s) ̸= ∅ for each source(i)-fact s. As for LTGDs, we create auxiliary argument si for each source(i)-fact s, which can be attacked by arguments corresponding to target(i)-facts in Si (s). In the following, we formalize this notion and simulate the semantics for IDs via AFs.

Computing Database Repairs under Expressive ICs via Argumentation

T s t u v

Emp ID Sup ID Dept. JonX1 AxeK4 Production AxeK4 AxeK4 Marketing TimX3 JonX1 Marketing JonX1 AxeK4 Distribution

Covers For Marketing Production Distribution R&D

S1 S2 t t,u t s s,v v t -

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), (si , si ) | s is a source(i)-fact for i ∈ I} ∪ {(t, si ) | t ∈ Si (s) for i ∈ I}. The intuition behind our encoding remains the same as for the case of LTGDs. That is, the attack (si , s) models that the ID i ∈ I must be satisfied for the source(i)-fact s and the self-attacks (si , si ) enforce extensions to only contain arguments corresponding to facts. However, we only need attacks between arguments (instead of attacks from sets of arguments) as Si (s) ⊆ target(i) for each i ∈ I and source(i)-fact s. Example 26. Consider D = ⟨T, I⟩ with database T = {s, t, u, v} and IDs I := {Sup ID ⊆ Emp ID, Covers For ⊆ Dept}. For brevity, we denote IDs by I = {1, 2}. The database and the supporting facts Si (w) for each i ∈ I, w ∈ T are depicted in the table inside Figure 7. Informally, a supervisor is also an employee and each employee is assigned a department to cover if that department is short on employees. For example, s(Sup ID) = t(Emp ID), s(Covers For) = t(Dept) = u(Dept), and therefore S1 (s) = {t}, S2 (s) = {t, u}. Then we have the AF FD as depicted in Figure 7. The AF FD has a unique preferred extension, given by {s, t}. Clearly, this is also the only repair for D. ◁ It is worth mentioning that {s, t, u, v} constitutes a naive extension for FD in Example 26, although this is not a repair for D. Clearly, the semantics for IDs in FD requires admissibility (defending against attacking arguments). Similar to the case of FDs, we observe that every ID is also an LTGD and hence the AF FD coincides with the SETAF SD for the constrained database D. As a consequence, the results for LTGDs transfer to IDs, modulo a translation from SETAFs to AFs. In particular, this allows us to apply Theorem 14 which establishes the following claim.

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

T s t u v

x y b a b b d c e e

S1 t t v

Figure 8: Argumentation framework without self-attacks for modelling IDs in Example 29. The auxiliary arguments are highlighted in red for convenience.

Corollary 27. Let D = ⟨T , I⟩ be a constrained database where I is a set of IDs and let FD denote the argumentation framework generated by D. Then for P ⊆ T , P ∈ repairs(D) iff P ∈ pref(FD ). Moreover, FD has exactly one preferred extension. The observation for LTGDs that some frameworks may not have any stable extension also applies to the special case of IDs and their corresponding AFs. As before, this holds because some arguments can neither be accepted in an extension, nor attacked by arguments in an extension. The argument corresponding to the fact v in Example 26 depicts such an argument. Regarding the pre-processing, we still obtain the unique preferred extension which is also naive and stable. Importantly, the set I of IDs does not have to be fixed to require the polynomial time pre-processing. Following Remark 16, ∃-REP and ∀-REP is true for every s ∈ T such that s ∈ PRE(FD ). Example 28 (Continued). Reconsider the constrained database D = ⟨T, I⟩ from Example 26. Observe that the argument v is not defended against v2 and therefore cannot be in a repair. The pre-processing removes {v, v1 , v2 } and all the edges to/from arguments in this set. This has the consequence that all the arguments which are only defended by v are no longer defended (e.g., u). Consequently, the arguments {u, u1 , u2 } have to be removed as well. After repeating the same process for u, we notice that no further argument needs to be removed. Hence, the set {s, t} yields a repair for D as well as a σ-extension in the reduced AF for σ ∈ {naive, stab, pref}. ◁ Our construction of AFs for IDs relies on self-attacking arguments. However, these self-attacks are restricted to only auxiliary arguments and allow us to avoid taking these arguments in any extension. This results in obtaining a precise connection between repairs of a DB and extensions of the resulting AF. Without self-attacking arguments, one gets extensions which may contain auxiliary arguments and thus a precise connection between repairs and extensions might be lost. This is further highlighted in the following example. Example 29. Consider a single binary relation T (x, y) in the schema, a constrained database D = ⟨T, I⟩ with database T = {s, t, u, v} and a single ID T [x] ⊆ T [y]. The database table as well as its resulting AF FD (without self-attacks for auxiliary arguments) is depicted in Figure 8. Observe that FD admits the following four preferred extensions: {{s, t, u1 , v}, {s, t, u1 , v1 }, {s1 , t1 , u1 , v}, {s1 , t1 , u1 , v1 }}. However, there is a unique repair for D given as {s, t, v}. ◁ Towards the end of our paper (Section 5.1), we will discuss how and whether we can model IDs via another translation that avoids self-attacking arguments.

Computing Database Repairs under Expressive ICs via Argumentation

T s t u

Emp ID Sup ID Dept. JonX1 AxeK4 Production TimX3 AxeK4 Sales AxeK4 AxeK4 Marketing s t

Building Covers for B4 Sales B2 Sales B4 Production u

Si t t s

Figure 9: Argumentation framework for modelling dependencies in Example 30. Black arcs depict conflicts due to functional, and blue ones due to inclusion dependency.

4.3

Simulating Functional and Inclusion Dependencies via AFs

Consider an instance D = ⟨T , B⟩ of a database T and a collection B = D ∪ I of FDs D and IDs I. We construct the AF FD = (A, RD ∪ RI ) as follows. • A := {s | s ∈ T } ∪ {si | s is a source(i)-fact for i ∈ I}, • RD := {(s, t), (t, s) | s, t ∈ T and {s, t} ̸|= d for some d ∈ D}, • RI := {(si , s), (si , si ) | s is a source(i)-fact for i ∈ I} ∪ {(t, si ) | t ∈ Si (s) for i ∈ I}. As before, one may apply the pre-processing as a first step, thereby removing those facts from T failing some i ∈ I. However, the discussion as for the case of LTGDs still applies for IDs. The following example illustrates that even if we apply pre-processing, some facts may not be accepted in combination with each other due to the presence of FDs. Example 30. Consider D = ⟨T, B⟩ with database T = {s, t, u} and ICs B = D ∪ I where D = {dep(Sup ID; Building)} and I = {Covers For ⊆ Dept}. Moreover, the database T and the support SCovers For⊆Dept (w) for each w ∈ T is depicted in the table inside Figure 9. Then, {s, t} ̸|= dep(Sup ID; Building), and {t, u} ̸|= dep(Sup ID; Building). The resulting AF FD is shown in Figure 9, where the edges due to the IDs are depicted in red and blue. The only preferred extension for FD is {t}. Also, the only repair for D is {t}. Further, although {s, u} is preferred for FD′ where D′ = ⟨T, D⟩ (ignoring red and blue arcs), and {s, t, u} is preferred for FD′′ where D′′ = ⟨T, I⟩ (ignoring black arcs), none of them is preferred for FD . ◁ Similar to their expressive counterparts, allowing both types of ICs (FDs and IDs) has the effect that the preferred and naive extensions do not coincide in general. Moreover, the repairs correspond to preferred semantics for AFs. Example 31 (Cont.). Reconsider the constrained database D from Example 30. Then, {s, u} is a naive extension for FD but not preferred. Moreover, t is the only fact for which ∃-REP and ∀-REP is true. ◁ Corollary 32. Let D = ⟨T , B⟩ be a constrained database where B includes FDs and IDs. Further, let FD denote the argumentation framework generated by D. Then for every subset P ⊆ T , P ∈ repairs(D) iff P ∈ pref(FD ).

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

Next we establish the data and combined complexity results for REP, ∃-REP and ∀-REP. Observe that a fixed collection of integrity constraints suffice for establishing the hardness results (see Table 1). Whereas, the membership in each case also applies to the case when the set of constraints is given as input (hence not fixed). Theorem 33. The problems REP and ∃-REP are in NP for constraints that consist of FDs and IDs. Moreover, there exists a set B of FDs and IDs such that the problems REPB and ∃-REPB are both NP-hard. Proof. The membership follows analogous to the proof of Theorem 19 in both cases. Let D = ⟨T , B⟩ be a constrained database where B consists of FDs and IDs. Further, let s ∈ T be a fact. Observe that for constraints involving FDs and IDs, the verification that a guessed set of facts satisfies B can be performed in polynomial time given D as input. Therefore, the NP-membership applies to REP and ∃-REP. For hardness, we reduce from SAT to ∃-REPB and REPB simultaneously for a fixed set B of constraints. Let φ := {ci | i ≤ m} be a propositional formula in conjunctive normal form over propositions X = {p1 , . . . , pn }. We construct a database with two relations2 : (i) a 4-ary relation F (t0 , u0 , t1 , u1 ), and (ii) a binary relation C(t2 , u2 ). Intuitively, F encodes the positive and negative participation of propositions in the clauses of φ. Precisely, a fact F (x, v, ci , sat) encodes that the proposition x appears positively in clause ci when v = 1, and negatively when v = 0. The value “sat” appears in each fact to enforce a non-empty set of facts in a repair. The relation C is used to encode the set of clauses. With the help of IDs, we aim to enforce that if any C-fact belong to a repair, then all of the C-facts (a “chain”) must belong to such a repair, which in turn forces (via further IDs) a repair of T to include F -facts in such a way that their corresponding literals satisfy every clause. Formally, we will define F and G such that dom(F ) ⊆ {ci | i ≤ m} ∪ {p1 , . . . , pn } ∪ {0, 1, sat} and dom(C) = {ci | i ≤ m} ∪ {sat}. Our database consists of the following facts: T = {F (x, 1, ci , sat) | x ∈ ci , ci ∈ φ} ∪ {F (x, 0, ci , sat) | ¬x ∈ ci , ci ∈ φ} ∪ {F (sat, sat, sat, sat)} ∪ {C(sat, c1 ), C(cm , sat)} ∪ {C(ci , ci+1 ) | 1 ≤ i < m}. As ICs, we consider a collection B of FDs and IDs over the schema {F, C} using V := {tj , uj | 0 ≤ j ≤ 2} as the set of attributes3 . Precisely, we let B = {dep(t0 ; u0 )} ∪ {F [u1 ] ⊆ C[u2 ], C[u2 ] ⊆ C[t2 ], C[t2 ] ⊆ F [t1 ], F [u1 ] ⊆ F [t1 ]}. The FD dep(t0 ; u0 ) over F ensures that each proposition (corresponding to facts in a repair) takes at most one value in {0, 1}. The IDs in B ensure that each clause ci ∈ φ is satisfied by modeling the following intuition. (I) The ID F [u1 ] ⊆ C[u2 ] together with a dummy fact F (sat, sat, sat, sat) (referred to as sd ) encodes that any repair for T containing sd triggers a non-empty subset of C-facts in a repair. (II) The ID C[u2 ] ⊆ C[t2 ] triggers a chain of C-facts in a repair and thus enforces that either ∅, or all C-facts are considered in a repair. (III) The ID C[t2 ] ⊆ F [t1 ] encodes that all clauses must be satisfied if a repair contains any C-fact. Moreover, (IV) the ID F [u1 ] ⊆ F [t1 ] is used in the reduction for REPB to enforce that a valid repair must contain the dummy fact sd . Notice that the collection B does not depend on the formula φ, hence it is fixed. We next highlight some observations before delving into the correctness proof. Clearly, D is inconsistent due to the presence of at least one pair of facts F (x, 1, ci , sat), F (x, 0, cj , sat) and the FD dep(t0 ; u0 ) (based 2

We find it convenient to write explicit attribute names for each relation. Recall that our notation for FDs and IDs uses attributes as names for the corresponding argument positions of the relation (here F (t0 , u0 , t1 , u1 ) and C(t2 , u2 )). 3

Computing Database Repairs under Expressive ICs via Argumentation

on the fact that at least one variable x appears positively in one clause ci and negatively in another clause cj , since otherwise φ is trivially satisfiable). Then, a set PX of F -facts satisfies dep(t0 ; u0 ) if for each proposition x ∈ X: PX contains facts of the form either F (x, 1, ∗, sat) or F (x, 0, ∗, sat) but not both (here ∗ indicates the occurrence of any value in a fact). For PX to be a candidate repair among F -facts, it additionally has to contain facts of the form F (x, ∗, ∗, ∗) for each x ∈ X. Moreover, a set Pc of C-facts satisfies the ID C[u2 ] ⊆ C[t2 ] iff either Pc = ∅ or Pc contains all C-facts. Next, we consider a set PX of F -facts containing the fact sd and let P = PX ∪ Pc . It follows that P |= F [u1 ] ⊆ C[u2 ] iff Pc ̸= ∅ and hence we let Pc contain all C-facts. Finally, P |= C[t2 ] ⊆ F [t1 ] iff for each ci ∈ φ, PX contains at least one fact F (x, v, ci , sat) such that v = 1 if x ∈ ci and v = 0 if ¬x ∈ ci . This is guaranteed since P contains facts of the form C(∗, c) for each clause c ∈ φ and thus there must exists F -facts in P also of the form F (∗, ∗, c, ∗) for each clause c ∈ φ. We prove the correctness via the following claim. Claim 34. φ is satisfiable if and only if ∃-REP is true for the fact sd . Proof of Claim “=⇒”. Suppose φ is satisfiable and let θ be a satisfying assignment. We let P := {F (x, 1, ci , sat) | θ(x) = 1, for x ∈ X and i ≤ m} ∪ {F (x, 0, ci , sat) | θ(x) = 0, for x ∈ X and i ≤ m} ∪ {sd } ∪ Pc where Pc contains all C-facts in T . Then P |= dep(t0 ; u0 ) because for any x ∈ X: P contains either facts of the form F (x, 1, ∗, ∗) or F (x, 0, ∗, ∗), since θ is an assignment over X. Next, we have that (I) P |= F [u1 ] ⊆ C[u2 ] since Pc ̸= ∅, and (II) P |= C[u2 ] ⊆ C[t2 ] since P contains all C-facts. Finally, P contains at least one fact of the form F (∗, ∗, c, ∗) for each clause c ∈ φ since θ(ℓ) = 1 for at least one literal ℓ ∈ c in each c ∈ φ. This holds because for every clause c ∈ φ, P contains a fact F (x, v, c, sat) for some variable x appearing in c. The value v in this fact depends on how the assignment θ satisfies c, that is, v = 1 if θ(x) = 1 makes c true, and v = 0 if θ(x) = 0 does. As a consequence, P |= C[t2 ] ⊆ F [t1 ]. Observe that P |= F [u1 ] ⊆ F [t1 ] follows due to the fact sd ∈ P. To see why P is a repair (i.e., subset-maximal), we note that the only facts not in P are of the form F (x, v, c, sat) for some v ∈ {0, 1} and c ∈ φ such that F (x, 1 − v, c, sat) ∈ P due to the way P is defined. However, adding such a fact would violate the FD. Therefore, P is indeed a repair. We conclude by observing that sd ∈ P. “⇐=”. Let P be a repair and sd ∈ P. From P |= F [u1 ] ⊆ C[u2 ], it follows that P must contain at least one C-fact as sd ∈ P, and from P |= F [u1 ] ⊆ C[u2 ], it follows that P actually contains all C-facts. We define an assignment θ over X by setting θ(x) = 1 if P contains F (x, 1, ∗, ∗) and θ(x) = 0 if it contains F (x, 0, ∗, ∗). Since P |= dep(t0 ; u0 ), the assignment θ is well-defined, i.e., there is no x ∈ X for which we assign both θ(x) = 1 and θ(x) = 0. Now, θ is defined for all the propositions in X since P is subset-maximal (hence, it contains fact of the form either F (x, 0, ∗, ∗) or F (x, 1, ∗, ∗) for each x ∈ X). Now, we prove that θ |= φ. To this aim, let c ∈ φ be any clause. Since P |= C[t2 ] ⊆ F [t1 ], P contains at least one fact of the form F (x, v, c, sat) for some variable x and v ∈ {0, 1}, such that v = 1 if x ∈ c and v = 0 if ¬x ∈ c (by definition of how F -facts are constructed). Therefore, we must have set θ(x) = 1 if v = 1 (hence x ∈ c) and θ(x) = 0 if v = 0 (¬x ∈ c). As a result, θ |= c for each c ∈ φ. This proves θ |= φ and our claim follows. ■ To reduce SAT into REPB , we observe that P |= F [u1 ] ⊆ F [t1 ] iff either P contains no F -fact, or it contains the fact sd . However, there cannot be a repair for D without any F -fact but still containing C-facts, since it violates the ID C[t2 ] ⊆ F [t1 ]. As a result, one cannot construct a non-empty repair for D by excluding sd . Therefore, every repair P for D necessarily contains sd , thereby proving the equivalence as before. In other words, there is a non-empty repair for D iff φ is satisfiable. This completes the proof for both cases. We provide an example for better understanding of the reductions from the proof of Theorem 33.

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo F t0 sd sat x1 x x̄2 x x̄3 x y1 y ȳ2 y y3 y

u0 t1 u1 sat sat sat 1 c1 sat 0 c2 sat 0 c3 sat 1 c1 sat 0 c2 sat 1 c3 sat

C t2 u2 sc sat c1 s 1 c1 c2 s 2 c2 c3 s3 c3 sat

Table 3: The database corresponding to the formula φ from Example 35.

Example 35 (Example with Fixed ICs). Let φ := {x ∨ y, ¬x ∨ ¬y, ¬x ∨ y} be a propositional formula. Our reduction for ∃-REP gives a database T with two tables F and C for the collection B := {dep(t0 ; u0 )} ∪ {F [u1 ] ⊆ C[u2 ], C[u2 ] ⊆ C[t2 ], C[t2 ] ⊆ F [t1 ]} of dependencies. Observe that the only satisfying assignment for φ is given by {x 7→ 0, y 7→ 1}, which corresponds to the repair {S, x̄2 , x̄3 , y1 , y3 } ∪ {sc , s1 , s2 , s3 } for D containing S. Consequently ∃-REP is true for the fact sd . ◁ Next, we prove that ∀-REP is even harder and ΠP2 -complete. Theorem 36. The problem ∀-REP is contained in ΠP2 for FDs and IDs. Moreover, there exists a set B of FDs and IDs such that the problem ∀-REPB is ΠP2 -hard. Proof. The membership follows analogous to the proof of Theorem 20. The only difference here is that one can check in polynomial time whether a set of facts satisfies each IC in the input. As a result, the membership holds for ∀-REP (i.e., in the combined complexity). For hardness, we build on the same idea as in the proof of Theorem 33. Here, we reduce from an instance Φ of the ΠP2 -complete problem 2QBF. The problem 2QBF is defined as follows: given a propositional formula Φ = ∀Y ∃Zφ(Y, Z) where φ := {ci | 1 ≤ i ≤ m} is a CNF formula, determine whether Φ is true (i.e., whether for every assignment to the variables in Y , there exists an assignment to the variables in Z that satisfies φ). We let X = Y ∪ Z and construct a constrained database D with three relations: (i) a 4-ary relation F (t0 , u0 , t1 , t∃ ), (ii) a binary relation S(u1 , u∃ ), and another (iii) binary-relation C(t2 , u2 ). Moreover, we consider a collection B of FDs and IDs over the schema of T using a set V := {tj , uj | 0 ≤ j ≤ 2} ∪ {t∃ , u∃ } of attributes. B contains one FD dep(t0 ; u0 ) similar to the proof of Theorem 33. Due to the change in database relations, we adapt the collection of IDs and consider the set {S[u1 ] ⊆ C[u2 ], C[u2 ] ⊆ C[t2 ], C[t2 ] ⊆ F [t1 ]} to encode whether each clause ci ∈ φ is satisfied. Moreover, we require an additional ID F [t∃ ] ⊆ S[u∃ ] to encode the existentially quantified variables Z. As a result, we obtain B = {dep(t0 ; u0 )} ∪ {S[u1 ] ⊆ C[u2 ], C[u2 ] ⊆ C[t2 ], C[t2 ] ⊆ F [t1 ], F [t∃ ] ⊆ S[u∃ ]} as our fixed collection of ICs. For the database relations, we let dom(F ) ⊆ {ci | i ≤ m} ∪ X ∪ {0, 1, exists, d}, dom(C) = {ci | i ≤ m} ∪ {d} and dom(S) = {c1 , exists, d}. Then our encoding works mostly similar to that in the proof of Theorem 33, except for the minor differences outlined below. 1. We include an S-fact to trigger a non-empty set of C-facts in any repair. We obtain this by adding the fact S(c1 , exists) together with the fact C(cm , c1 ). Here, we do not need the fact C(sat, c1 ) as in the proof of Theorem 33. The remaining C-facts {C(ci , ci+1 ) | i < m} are added as before.

Computing Database Repairs under Expressive ICs via Argumentation

2. We use sd := S(d, d), y d := F (d, d, d, d) and cd := C(d, d) as dummy facts to simulate the effect that any assignment over Y yields a collection of facts in T that trivially satisfies all the ICs. This is required to simulate the ∀ quantification over Y . 3. If a literal ℓ ∈ Lit(Y ) does not appear in even a single clause, we still add its corresponding F -fact following the same intuition as before, i.e., for such a literal ℓ: we add F (y, 1, d, d) if ℓ = y and F (y, 0, d, d) if ℓ = ¬y. Moreover, the dummy value d in this case encodes that ℓ does not satisfy any clause. As a result of this, we can connect repairs to all assignments over universally quantified variables in Y . For the ease of notation, we write ℓ ∈ c0 for a literal over Y that does not appear in any clause. 4. The attributes {t∃ , u∃ } encode that the S-fact ssat := S(c1 , exists) supports facts involving propositions z ∈ Z via the inclusion dependency F [t∃ ] ⊆ S[u∃ ]. This is achieved by letting facts F (z, ∗, ∗, exists) for each z ∈ Z together with the fact ssat . However, all facts corresponding to variables y ∈ Y take the form F (y, ∗, ∗, d) for the dummy value d. Observe that the construction in (3) and (4) requires us to distinguish facts based on variables in Y and Z. Formally, our database consists of the following facts: T = {F (y, 1, ci , d) | y ∈ Y ∩ ci , ci ∈ φ} ∪ {F (y, 0, ci , d) | y ∈ Y, ¬y ∈ ci , ci ∈ φ} ∪ {F (y, 1, d, d) | no clause in φ contains the literal y ∈ Y } ∪ {F (y, 0, d, d) | no clause in φ contains the literal ¬y for y ∈ Y } ∪ {F (z, 1, ci , exists) | z ∈ Z ∩ ci , ci ∈ φ} ∪ {F (z, 0, ci , exists) | z ∈ Z, ¬z ∈ ci , ci ∈ φ} ∪ {F (d, d, d, d)} ∪ {S(c1 , exists), S(d, d))} ∪ {C(ci , ci+1 ) | 1 ≤ i < m} ∪ {C(cm , c1 ), C(d, d)}. For correctness, notice that every assignment IY over Y (seen as a subset of Y ) corresponds to a set PY = {F (y, 1, ci , d) | y ∈ IY and y ∈ ci for 0 ≤ i ≤ m} ∪ {F (y, 0, ci , d) | y ̸∈ IY and ¬y ∈ ci for 0 ≤ i ≤ m} of F -facts in T . Moreover, PY |= dep(t0 ; u0 ) since IY is an assignment over Y and thus for each i ̸= j ≤ m, PY includes facts of the form either F (y, 1, ci , d) or F (y, 0, cj , d) but not both, for each variable y ∈ Y and clause ci , cj . Furthermore, it is easy to observe that taking the dummy facts, i.e., PD = {y d , sd , cd } the collection PY ∪ PD satisfies the IDs S[u1 ] ⊆ C[u2 ] and C[u2 ] ⊆ C[t2 ]. Now, we let PY = PY ∪ PD . We have that ssat ̸∈ PY . In order to extend PY by adding F (z, 1, ci , exists) or F (z, 0, ci , exists) for any z ∈ Z and i ≤ m, ssat must be added as well due to the ID F [t∃ ] ⊆ S[u∃ ]. However, in order to include ssat in any repair, we have to find IY and IZ that together satisfy φ due to the remaining IDs, in particular due to C[t2 ] ⊆ F [t1 ]. As a result, for any interpretation IY over Y , there is an interpretation IZ over Z such that: IY ∪ IZ |= φ if and only if PY is not a repair for D (since it can be extended by adding facts PZ = {F (z, 1, ci , d) | z ∈ IZ and z ∈ ci for 0 ≤ i ≤ m} ∪ {F (z, 0, ci , d) | z ̸∈ IZ and ¬z ∈ ci for 0 ≤ i ≤ m} for such an interpretation IZ in this case). Equivalently, there is a repair for D not containing ssat if and only if the formula Φ is false. We conclude by observing that Φ is true if and only if every repair for D contains ssat if and only if ∀-REP is true for ssat . We provide an example for better understanding of the reduction from the proof of Theorem 36. Example 37. Let Φ = ∀x∀y∃z∃w((x ∨ y ∨ z) ∧ (y ∨ ¬z ∨ ¬w) ∧ (y ∨ z ∨ w)) be a 2QBF. Then, our reduction yields a database T with three database tables as depicted in Table 4 and the (fixed) collection B := {dep(t0 ; u0 )} ∪ {S[u1 ] ⊆ C[u2 ], C[u2 ] ⊆ C[t2 ], C[t2 ] ⊆ F [t1 ], F [t∃ ] ⊆ S[u∃ ]} of dependencies. The

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

S u1 u∃ ssat c1 exists sd d d

F t0 yd d x1 x x̄0 x y1 y y2 y y3 y ȳ0 y z1 z z̄2 z z3 z w̄2 w w3 w

u0 d 1 0 1 1 1 0 1 0 1 0 1

t1 d c1 d c1 c2 c3 d c1 c2 c3 c2 c3

27 t∃ d d d d d d d exists exists exists exists exists

C s1 s2 s3 cd

t2 c1 c2 c3 d

u2 c2 c3 c1 d

Table 4: The database corresponding to the 2QBF instance Φ from Example 37.

reader can verify that the formula Φ is true and that for ssat , ∀-REP is true as well. For instance, the assignment {x 7→ 0, y 7→ 0} results in IY = ∅ and thus PY = {x̄0 , ȳ0 }. Then, although PY ∪ {y d , sd , cd } satisfies each dependency in B, it is not a repair since it is not subset-maximal. A repair is obtained by adding further the facts {z1 , z3 , w̄2 } ∪ {S, s1 , s2 , s3 }. ◁

Concluding Remarks

Overview. We simulated the problem of finding repairs of an inconsistent database under various families of ICs by Dung’s (set-based) argumentation frameworks. Our main results (see Table 1) indicate that subsetmaximal repairs correspond to naive extensions when only one type of dependencies are allowed, whereas only preferred extensions yield all the repairs when both types are allowed. Note that the case of LTGDs (or IDs) requires a polynomial time pre-processing to eliminate all the non-accepted arguments from the resulting (SET)AFs. The result of which yields a unique preferred extension which is also stable and naive. Moreover, the following interesting facts can be derived: “FDs can be modeled via AFs” in a similar way in which “DCs can be modeled via SETAFs”. Analogous results hold when we replace FDs and DCs by (1) IDs and LTGDs, respectively, or (2) FDs + IDs and DCs + LTGDs, respectively. Furthermore, for the problem to determine whether a tuple is in some (resp., every) repair, we establish the same complexity bounds as the complexity of credulous (skeptical) reasoning for preferred semantics in AFs. Interestingly, the combined complexity with FDs+IDs remains the same as the data complexity with DCs+LTGDs for considered problems.

5.1

The Role of Self-attacking Arguments

Observe that our construction of (SET)AFs for LTGDs and IDs relies on self-attacking auxiliary arguments. Our motivation lies in avoiding those arguments in any extension of the resulting (SET)AF and connecting repairs to extensions directly. In the absence of self-attacking arguments, extensions may contain auxiliary arguments and therefore a precise connection between repairs and extensions cannot be established (see

Computing Database Repairs under Expressive ICs via Argumentation

Example 29). We find it worth highlighting that a considerable thought has been given on how LTGDs/IDs can be modeled in an argumentation framework. Intuitively, the semantics of inclusion dependencies closely resemble the notion of “necessary support” in the argumentation literature [3, 39, 36]. If a DB instance contains only one inclusion dependency (i) per relation, we can simply model the set of supporting facts in Si (s) for a fact s via the support relation between arguments. However, we observed that this does not apply to the case when an instance D contains multiple IDs with the same relation as their source. Modeling this requires as many (distinct) support relations as the number of IDs. This holds since for each fact s, one would have to distinguish the satisfaction of individual IDs (i.e., the sets Si (s) and Sj (s) for IDs i ̸= j) which a single support relation cannot offer. Our translation captures the same essence of supporting arguments via auxiliary attackers, with the benefit that one can distinguish supporters and attackers corresponding to each inclusion dependency. As a future work, we aim to think further in this direction and explore ideas that might lead to improved translations for IDs and LTGDs.

5.2

Discussion and Future Work

We would like to point out that, although a correspondence between subset-maximal repairs in the presence of functional dependencies (resp., denial constraints) and extensions for (SET)AFs is known [14], the main contributions of our work establish the correspondence when inclusion dependencies or LTGDs are also allowed. This novel contribution opens up several directions for future work. First and foremost, the authors believe that the connection between repairs in the setting of inconsistent databases and extensions in AFs is stronger than what is established here. Intuitively, one can model the attack relationship via functional dependencies and defense/support via inclusion dependencies. A transformation based on this intuition was recently presented by [36], showing that AFs can be simulated via inconsistent databases considering FDs and IDs. Further future work may consider whether the connection between inconsistent databases and argumentation can be generalized to other well-known types of expressive ICs. This is particularly interesting keeping in mind that the current paper extends an earlier work for FDs and IDs [37] to certain expressive ICs towards the both side of Figure 1. Currently, the authors believe that to model arbitrary (or full) tuple-generating dependencies, one needs the so-called hyper argumentation frameworks [22], allowing attacks between two sets of arguments. Furthermore, one can also target the richer setting of universal constraints and the symmetric difference repairs [15]. Another interesting question is to explore whether the lower bounds for complexity also apply to the sub-classes of FDs and IDs, namely keys and foreign keys as well as the particular case of acyclic dependencies. Moreover, we would like to explore whether consistent query answering (CQA) under inconsistency-tolerant semantics can also be tackled via the argumentation approach. Finally, one can consider incorporating information about priorities among tuples into the resulting AFs, that is, extending the translations presented in this work to the setting of prioritized repairing and consistent query answering [26, 30, 31]. Here, [14] has already considered FDs and DCs, thus the question remains open only for the case of IDs and LTGDs. Another promising direction to consider next is the exploration of an explainability dimension, similar to that in the setting of ontological KBs [6, 8, 16]. Given an instance D including a database T and a collection B of dependencies, then the proposed AF FD lets one determine the causes why some tuples are not in some repair (or all repairs). We note that, for IDs, the auxiliary arguments modelling each dependency in B can serve this purpose. For FDs, we believe that annotating arguments (or the attack relation between a pair of

Y. Mahmood, J. Virtema, T. Barlag, A-C. Ngonga Ngomo

arguments) by the FDs involved in the conflict can achieve the goal. As a result, one can look at the AF FD and read from it the FDs or IDs which a tuple s failing ∃-REP or ∀-REP participates in. Then, subsets of the atoms and/or possibly tuples in a database can be considered as explanations. Such explanations seem interesting in modeling scenarios where the data (database) has higher confidence than the dependencies; for example, if dependencies are mined over some part of the existing data. An explanation then informs that the data (and hence tuples therein) should be kept, whereas dependencies need to be screened and further analyzed.

Acknowledgments This is a pre-print to the paper accepted at the Knowledge Engineering Review journal. Research was funded by the German Research Foundation (DFG), grant TRR 318/3 2026 – 438445824 and VI 1045-1/1 432788559, the Ministry of Culture and Science of North Rhine-Westphalia (MKW NRW) within projects WHALE (LFN 1-04) funded under the Lamarr Fellow Network programme and project SAIL, grant NW21059D, and by the German Federal Ministry of Research, Technology and Space (BMFTR) within the project KI-Akademie OWL under the grant no 16IS24057B.

References [1] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. [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. [3] L. Amgoud, C. Cayrol, M. Lagasquie-Schiex, and P. Livet. On bipolarity in argumentation frameworks. Int. J. Intell. Syst., 23(10):1062–1093, 2008. [4] 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. [5] 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. [6] 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. [7] 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

[8] 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 Notes in Computer Science, pages 203–219. Springer, 2015. [9] 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 Intelligence and Applications, pages 101–108. IOS Press, 2014. [10] S. Arming, R. Pichler, and E. Sallinger. Complexity of repair checking and consistent query answering. LIPIcs, 48(2016), 2016. [11] P. Barceló and G. Fontaine. On the data complexity of consistent query answering over graph databases. Journal of Computer and System Sciences, 88:164–194, 2017. [12] L. E. Bertossi. Consistent query answering in databases. SIGMOD Rec., 35(2):68–76, 2006. [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. [14] 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, 2020, pages 141–151, 2020. [15] M. Bienvenu and C. Bourgaux. Inconsistency Handling in Prioritized Databases with Universal Constraints: 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. [16] M. Bienvenu, C. Bourgaux, and F. Goasdoué. Computing and explaining query answers over inconsistent dl-lite knowledge bases. Journal of Artificial Intelligence Research, 64:563–644, 2019. [17] 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. [18] J. Chomicki and J. Marcinkowski. Minimal-change integrity maintenance using tuple deletions. Information and Computation, 197(1):90–121, 2005. [19] 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. Virtema, T. Barlag, A-C. Ngonga Ngomo

[20] 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 9387 of Lecture Notes in Computer Science, pages 594–602. Springer, 2015. [21] 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. [22] Y. Dimopoulos, W. Dvorák, M. König, A. Rapberger, M. Ulbricht, and S. Woltran. Sets attacking sets in abstract argumentation. In NMR, pages 22–31, 2023. [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. [24] W. Dvorák and P. E. Dunne. Computational problems in formal argumentation and their complexity. FLAP, 4(8), 2017. [25] W. Dvořák and S. Woltran. Complexity of abstract argumentation under a claim-centric view. Artificial Intelligence, 285:103290, 2020. [26] 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. [27] M. Hannula and L. Hella. Complexity thresholds in inclusion logic. Inf. Comput., 287:104759, 2022. [28] M. Hannula and J. Wijsen. A dichotomy in consistent query answering for primary keys and unary foreign keys. In L. Libkin and P. Barceló, editors, PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 437–449. ACM, 2022. [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. [30] 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. [31] B. Kimelfeld, E. Livshits, and L. Peterfreund. Counting and enumerating preferred database repairs. Theor. Comput. Sci., 837:115–157, 2020. [32] M. König, A. Rapberger, and M. Ulbricht. Just a matter of perspective. In Computational Models of Argument, pages 212–223. IOS Press, 2022. [33] 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

[34] 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, Proceedings, volume 4353 of Lecture Notes in Computer Science, pages 179–193. Springer, 2007. [35] Y. Mahmood. Parameterized aspects of team-based formalisms and logical inference, 2022. [36] 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. [37] 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. [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 Notes in Computer Science, pages 54–73. Springer, 2006. [39] 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. [40] S. Staworko and J. Chomicki. Consistent query answers in the presence of universal constraints. Inf. Syst., 35(1):1–22, 2010. [41] 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. [42] 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. [43] J. Väänänen. Dependence Logic. Cambridge University Press, 2007. [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. [45] A. P. Young, S. Modgil, and O. Rodrigues. Prioritised default logic as argumentation with partial order default priorities. CoRR, abs/1609.05224, 2016. [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. IOS Press, 2020.

Record · ID 155326 · SHA-256 9d7b1e048a55eda6
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.