Inconsistent databases and argumentation frameworks with collective attacks

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 do not conform to the imposed integrity constraints (ICs). A rich theory has been developed to deal with inconsistent databases.

Formally, ICs describe fundamental structural properties of data that 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 determines the whole record in the database table) and inclusion dependencies (which express that all values for a given attribute occur as values of another given attribute). Together, key constraints and inclusion dependencies (IDs) can express foreign key constraints. The literature for database dependencies considers a whole hierarchy of dependencies in increasing generality (see, e.g., Abiteboul^[1]). Within this hierarchy, key constraints are special cases of functional dependencies (FDs), which are special cases of equality-generating dependencies, which again generalize to denial constraints (DCs). Likewise, IDs generalize to local-as-view tuple-generating dependencies (LTGDs), which are special cases of tuple-generating dependencies (TGDs). All the aforementioned dependencies can be defined as particular syntactic fragments of first-order logic (see the section "Preliminaries" for formal definitions). In this paper, we examine expressive ICs, 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^[2,3], attribute-based repairs^[4], and cardinality-based repairs^[5].

Dung's abstract argumentation framework (AF)^[6] has been specifically designed to model conflicts and support relationships among arguments. An abstract AF represents arguments and their conflicts through directed graphs and allows for a convenient exploration of the conflicts at an abstract level. Furthermore, it is often necessary to consider conflicts not only between individual arguments but also between sets of arguments. This necessity has given rise to the so-called set-based AFs (SETAFs)^[7], which allow modeling of collective attacks.

AFs have been explored extensively for representing and reasoning with inconsistent knowledge bases (KBs), covering Datalog^± and description logics (see, e.g., studies^[8−13] and Arieli^[14] 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 ICs, 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 FDs (or their generalization, denial constraints) have been investigated in the context of AFs (resp., SETAFs) in Bienvenu & Bourgaux^[13]. 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 DCs and LTGDs. The first problem of interest to us is establishing a connection between repairs for the inconsistent databases (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 the section "Preliminaries" for definitions) in the related SETAFs. Repairs under DCs correspond to the naive extensions, which also coincide with the preferred and stable extensions in the resulting SETAFs. For LTGDs, the correspondence requires preferred semantics. However, a polynomial-time pre-processing on the resulting SETAFs results in its unique extension that is also stable and naive. Allowing both types of ICs breaks this relationship between extensions, and only preferred semantics captures the repairs. Our second contribution highlights that when one restricts DCs to FDs and LTGDs to IDs, respectively, a similar connection as for the expressive ICs holds; 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 of 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^[15−20] (see studies^[21,22] for an overview). The notions of conflict graphs and hypergraphs have been introduced before for certain families of ICs^[23−25]. In particular, a correspondence between repairs and subset-maximal independent sets of the conflict graphs for FDs^[16] and DCs^[17] has been established. Moreover, a recent work defines conflict (hyper)graphs for a richer setting of universal constraints considering symmetric difference repairs^[26]. 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 AF. 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^[18] 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^[27]. 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 & Hella^[28] for inclusion logic formulas and by Mahmood^[29] for propositional dependence logic. In the team-semantics literature, FDs are known as dependence atoms and IDs as inclusion atoms, denoted, respectively, as $ \text{dep}({\boldsymbol{x}} ; {\boldsymbol{y}}) $ and $ {\boldsymbol{x}} \subseteq {\boldsymbol{y}} $ (We borrow this notation and write $ \text{dep}({\boldsymbol{x}} ; {\boldsymbol{y}}) $ and $ {\boldsymbol{x}} \subseteq {\boldsymbol{y}} $ for FDs and IDs, respectively).

Our work differs from the previous work, since it combines denial constraints (a subclass of universal constraints) and LTGDs (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) AFs in Dung's setting^[6]. A similar connection between (SET)AFs and preferred repairs has been explored in the context of prioritized description logic^[13] and Datalog^± KBs^[30−33]. Employing abstract argumentation, we utilize facts in a database as arguments, aligning with the approach presented in Bienvenu & Bourgaux^[13]. In fact, the results for DCs and FDs regarding preferred and stable semantics follow as a corollary from the work by Bienvenu & Bourgaux^[13] since repairs in the prioritized setting generalize subset repairs. In contrast, Croitoru et al.^[31,32] 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, König el al.^[34] provided several translations between different argumentation formalisms, namely assumption-based argumentation (ABA)^[35], claim-augmented frameworks (CAF)^[36], and argumentation frameworks with collective attacks (SETAF)^[7]. This puts our work in a broader context by presenting novel translations from databases with expressive ICs to SETAFs. Furthermore, recently, Mahmood et al.^[37] 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 FDs and IDs alone.

Prior work A preliminary version of this work was published in FoIKS 2024^[38]. The current paper expands the earlier work to more expressive ICs. To be precise, we utilize SETAFs to simulate denial constraints and LTGDs using the same ideas as for FDs and IDs. The conference version focused on FDs and IDs in connection to plain AFs. The results for DCs follow from the work by Bienvenu & Bourgaux^[13]; 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.

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 $ {\bf{P}}, {\bf{NP}} $, and $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $, and (2) closed first-order formulas having $ \forall.\exists. $ as the quantifier prefixes. In the following, we shortly recall the necessary definitions from databases and argumentation.

Databases A (relational) schema $ \tau $ is a finite set of relation names. Each relation $ T\in\tau $ 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. Let $ t_1,\dots,t_k $ be terms and $ T\in\tau $ be a relation of arity $ k $, the expression $ T(t_1,\dots,t_k) $ is called a relational atom. A relational atom composed of only constants is called a fact. Given a schema $ \tau $, a database $ {\cal{T}} $ over $ \tau $ is a finite set of facts using relation symbols from $ \tau $. The active domain of a database $ {\cal{T}} $ is denoted as $ \text{dom}({\cal{T}}) $ and defined as the collection of all the constant values from $ C $ that occur in facts of $ {\cal{T}} $.

A fact can also be seen as a database tuple. In this notation, the fact $ T(a_1,\dots,a_k) $ corresponds to stating that the tuple $ (a_1,\dots,a_k) $ 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 $ \tau $ 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,\dots,k\} $ in the columns of $ T $ are usually given explicit names, resulting in the set $ \text{att}(T) $ of attributes of $ T $. The active domain $ \text{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., $ {\boldsymbol{x}}, {\boldsymbol{y}} $) for sequences of attributes. For an attribute $ x\in\text{att}(T) $ and a tuple $ s\in T $, $ s(x) $ denotes the value taken by $ s $ for the attribute $ x $. For a sequence $ {\boldsymbol{x}} =(x_1,\ldots,x_k) $, $ s({\boldsymbol{x}}) $ denotes the sequence of values $ (s(x_1),\ldots, s(x_k)) $. Given this tabular view, a database over schema $ \tau = \{T_1,\ldots, T_m \} $ is seen as a collection $ {\cal{T}}=(T_1,\dots, T_m) $ of tables corresponding to relation symbols in $ \tau $. Again, the active domain $ \text{dom}({\cal{T}}) $ of a database $ {\cal{T}} $ is the union of active domains of each table $ T\in{\cal{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 2.1 Consider the schema $ \{E,D\} $. The database tables over this schema (Table 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 $ e_1 $. For presentation of examples, we refer to tuple identifiers also as facts. Hence, we write $ e_1 $ for the fact E(E1, D1, Paderborn). ◁

Integrity constraints. ICs 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 $ \tau $ be a database schema. Recall that a database atom is an application of any relation name $ T\in\tau $ over variables or constants. Let $ \varphi $ and $ \psi_i $ be conjunctions of database atoms and let $ \beta $ be a quantifier-free formula using only built-in predicates (e.g., equality or inequality). We call a formula of the form

a generic first-order IC (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 DC has the form $ \forall {\boldsymbol{x}} \neg (\varphi({\boldsymbol{x}})\land \beta ({\boldsymbol{x}})) $, which can also be thought of as a UC with empty right hand side. An equality-generating dependency (EGD) has the form $ \forall {\boldsymbol{x}} (\varphi({\boldsymbol{x}})\rightarrow x_i=x_j) $, which can be thought of as a DC where $ \beta $ is a single inequality. Let $ T $ be an $ n $-ary relation and $ I,J\subseteq \{1,\dots,n\} $ be two sets with pairwise distinct variables $ x_1,\dots,x_n,y_1,\dots,y_n $. Then, an FD over $ T $ is an EGD of the form $ \forall {\boldsymbol{x}} \forall {\boldsymbol{y}} (T({\boldsymbol{x}}) \land T({\boldsymbol{y}}) \land \bigwedge_{i\in I}x_i =y_i \rightarrow \bigwedge_{j\in J}x_j=y_j) $. A key constraint is a special type of FD requiring $ I\cup J = \{1,\dots,n\} $.

A disjunctive tuple-generating dependency ($ \vee $-TGD) is a generic IC that has empty $ \beta $ and an ordinary tuple-generating dependency (TGD) additionally requires $ n=1 $. An LTGD is a TGD where $ \varphi $ is a single atom and an ID is an LTGD where $ \psi_i $ is also a single atom. Figure 1 (adapted from study by Arming^[39]) presents an overview of the hierarchy of different ICs together with their syntactic forms.

Figure 1. 

Hierarchy of ICs and syntactic form for the most commonly studied constraints^[39].

The semantics for ICs is defined similarly to first-order (FO) formulas. A database $ {\cal{T}} $ over schema $ \tau $ gives rise to an FO-structure $ \mathcal A $ over the vocabulary $ \tau $. The domain of $ \mathcal A $ is the active domain $ \text{dom}({\cal{T}}) $ of $ {\cal{T}} $ and each relation symbol $ T\in \tau $ is interpreted as the corresponding database table $ T $ in $ {\cal{T}} $, i.e., it contains all the tuples of constants $ (a_1,\dots,a_k) $ over $ \text{dom}({\cal{T}}) $ such that $ T(a_1,\dots,a_k)\in {\cal{T}} $. Then, for an IC $ \alpha $, we write $ {\cal{T}}\models \alpha $ iff $ \mathcal A\models \alpha $ 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\subseteq \{1,\dots,n\} $ be two sets and let $ x_1,\dots,x_n,y_1,\dots,y_n $ be pairwise distinct variables. Then, for sequences $ {\boldsymbol{X}} = (x_i \mid i\in I) $ and $ {\boldsymbol{Y}} = (y_j \mid j\in J) $, the FD $ \forall {\boldsymbol{x}} \forall {\boldsymbol{y}} (T({\boldsymbol{x}}) \land T({\boldsymbol{y}}) \land \bigwedge_{i\in I}x_i =y_i \rightarrow \bigwedge_{j\in J}x_j=y_j) $ can be equivalently expressed as $ \text{dep}({\boldsymbol{X}} ; {\boldsymbol{Y}}) $ or $ {\boldsymbol{X}} \rightarrow {\boldsymbol{Y}} $ (as done usually in the DBs setting). Moreover, let $ T_i $ and $ T_j $ be two relations, and $ {\boldsymbol{x}}_1, {\boldsymbol{x}}_2, {\boldsymbol{x}}_3 $ be sequences of variables. The ID $ \forall {\boldsymbol{x}}_1 \forall {\boldsymbol{x}}_2 (T_i({\boldsymbol{x}}_1,{\boldsymbol{x}}_2) \rightarrow \exists {\boldsymbol{x}}_3 T_j({\boldsymbol{x}}_2,{\boldsymbol{x}}_3)) $ can be equivalently expressed as $ T_i[{\boldsymbol{Y}}] \subseteq T_j[{\boldsymbol{X}}] $ where $ {\boldsymbol{X}} $ (respectively, $ {\boldsymbol{Y}} $) is the set of attributes of $ T_j $ ($ T_i $) corresponding to $ {\boldsymbol{x}}_2 $. We find it convenient to write $ {\boldsymbol{Y}}\subseteq {\boldsymbol{X}} $ instead of $ T[{\boldsymbol{Y}}]\subseteq T[{\boldsymbol{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 2.1.

Example 2.2 Consider a DC $ {\rm{dc}} $ and an LTGD $ {\rm{lav}} $, as given below.

The DC $ {\rm{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 $ {\rm{lav}} $ requires that every department has at least one employee. Both $ {\rm{dc}} $ and $ {\rm{lav}} $ are violated in the database from Example 2.1. ◁

Let $ {\cal{T}} $ be a database (a collection of facts) and $ B $ be a collection of ICs. Then $ {\cal{T}} $ is consistent with respect to $ B $, denoted as $ {\cal{T}}\models B $, if $ {\cal{T}}\models b $ for each $ b\in B $. Moreover, $ {\cal{T}} $ is inconsistent with respect to $ B $ if there is some $ b\in B $ such that $ {\cal{T}}\not \models b $. A subset-repair of $ {\cal{T}} $ with respect to $ B $ is a subset $ {\cal{P}}\subseteq {\cal{T}} $ that is consistent with respect to $ B $, and maximal in the sense that no set $ {\cal{P}}' $ exists such that it is consistent with respect to $ B $ and $ {\cal{P}} \subset {\cal{P}}' \subseteq T $. In the tabular view, the subset of a DB $ {\cal{T}} = (T_1,\dots,T_m) $ is defined as $ {\cal{P}} = (P_1,\dots,P_m) $, where $ P_i\subseteq T_i $ for each $ i\leq m $. In the following, we simply speak of a repair when we intend to mean a subset-repair. Furthermore, we often consider a database $ {\cal{T}} $ and a set $ B $ of ICs assuming that $ B $ only uses relation names from the schema of $ {\cal{T}} $. In that case, we call $ {\cal{D}} = \langle {\cal{T}}, B \rangle $ a constrained database. For a constrained database $ {\cal{D}} $, $ \text{repairs}({\cal{D}}) $ denotes the set of all repairs for $ {\cal{D}} $.

The first problem we are interested in ($ {\rm{REP}} $) asks whether there exists a repair for a constrained database $ {\cal{D}} $. Since the empty database ($ \emptyset $) satisfies each IC trivially, we are interested in the decision problem asking whether a non-empty repair exists.

Two further problems of interest are brave and cautious reasoning for a given fact $ s\in {\cal{T}} $, asking whether $ s $ belongs to some (every) repair for $ {\cal{D}} $.

We also consider the case when the set $ B $ of ICs is fixed and the input only involves a database $ {\cal{T}} $ (and a fact $ s $). This gives rise to separate decision problems $ {\rm{REP}}_{{\rm{B}}} $, $ \exists {\text{-}}{\rm{REP}}_{{\rm{B}}} $ and $ \forall {\text{-}}{\rm{REP}}_{{\rm{B}}} $, for each $ B $. We can then define the data complexity of $ {\rm{REP}} $, $ \exists {\text{-}}{\rm{REP}} $ and $ \forall {\text{-}}{\rm{REP}} $, in the usual way. That is, for a complexity class $ {\cal{C}} $, the data complexity of $ {\rm{REP}} $ is in $ {\cal{C}} $, if $ {\rm{REP}}_{{\rm{B}}} $ is in $ {\cal{C}} $, for every $ B $, and $ {\cal{C}} $-hard, if $ {\rm{REP}}_{{\rm{B}}} $ is $ {\cal{C}} $-hard, for some $ B $. Thus, the problems defined above (i.e., $ {\rm{REP}} $, $ \exists {\text{-}}{\rm{REP}} $ and $ \forall {\text{-}}{\rm{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 $ {\cal{T}} $ is inconsistent with respect to $ B $ in a constrained database $ {\cal{D}}=\langle {\cal{T}}, B\rangle $. 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 2.1 with respect to the ICs from Example 2.2.

Example 2.3 Reconsider the database from Example 2.1, which is inconsistent with the ICs from Example 2.2. Here, the fact $ d_3 $ violates $ {\rm{lav}} $, and the only way to resolve this violation (in our subset-repair setting) is to remove $ d_3 $. Moreover, the set $ \{e_3, d_2\} $ also violate $ {\rm{dc}} $. This results in two ways to repair our database, by removing either of those facts. Thus, we have two subset-maximal repairs, namely $ \{e_1, e_2, d_1, d_2\} $ and $ \{e_1, e_2, e_3, d_1\} $. ◁

Abstract argumentation We use Dung's argumentation framework^[6] and consider only non-empty and finite sets of arguments $ A $. An (argumentation) framework (AF) is a directed graph $ {\cal{F}}=(A, R) $, where $ A $ is a set of arguments and the relation $ R \subseteq A\times A $ represents direct attacks between arguments. If $ S\subseteq A $, we say that an argument $ s \in A $ is defended by $ S $ in $ {\cal{F}} $, if for every $ (s', s) \in R $ there exists $ s''\in S $ such that $ (s'',s')\in R $.

In abstract argumentation, one is interested in computing the so-called extensions, which are subsets $ S \subseteq A $ of the arguments that have certain properties. The set $ S $ of arguments is called conflict-free in $ {\cal{F}} $ if $ (S\times S) \cap R = \emptyset $. Let $ S $ be conflict-free, then $ S $ is

1. naive in $ {\cal{F}} $ if no $ S' \supset S $ is conflict-free in $ {\cal{F}} $;

2. admissible in $ {\cal{F}} $ if every $ s \in S $ is defended by $ S $ in $ {\cal{F}} $.

Further, let $ S $ be admissible. Then, $ S $ is

3. preferred in $ {\cal{F}} $, if there is no $ S' \supset S $ that is admissible in $ {\cal{F}} $;

4. stable in $ {\cal{F}} $ if every $ s \in A \setminus S $ is attacked by some $ s' \in S $.

We denote each of the mentioned semantics by abbreviations: $ \text{conf},\text{ naive},\ \mathrm{adm},\ \mathrm{pref} $ and $ \text{stab} $, respectively. For a semantics $ \sigma \in \{\text{conf}, \text{naive}, \text{adm}, \text{pref}, \text{stab}\} $, we write $ \sigma({\cal{F}}) $ for the set of all extensions of semantics $ \sigma $ in $ {\cal{F}} $. Now, we are ready to define the corresponding decision problem asking for extension existence with respect to a semantics $ \sigma $.

Finally, for an AF $ {\cal{F}}{=}(A,R) $ and $ a\in A $, we define the problems $ {\rm{Cred}}_{\sigma} $ and $ {\rm{Skep}}_{\sigma} $, which ask whether $ a $ is in some $ \sigma $-extension of $ {\cal{F}} $ ("credulously accepted") or every $ \sigma $-extension of $ {\cal{F}} $ ("skeptically accepted"), respectively.

Example 2.4 Consider the argumentation framework $ \mathcal{AF} = \{a,b,c,d\} $ with the attack relation as depicted in Fig. 2. Then extensions for $ {\cal{F}} $ are also depicted in Fig. 2 for the mentioned semantics. ◁

Figure 2. 

Framework $ {\cal{F}} $ from Example 2.4 (left) and extensions for given semantics (right).

The complexity of reasoning in argumentation is well understood, see Table 1 in Dvorák & Dunne^[40] for an overview. In particular, $ {\rm{Cred}}_{\text{naive}} $ and $ {\rm{Skep}}_{\text{naive}} $ are in P, whereas, $ {\rm{Cred}}_{\text{pref}} $ and $ {\rm{Skep}}_{\text{pref}} $ are $ {\bf{NP}} $-complete and $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $-complete, respectively. Moreover, the problem to decide whether there is a non-empty extension is in P for $ \text{naive} $ and $ {\bf{NP}} $-complete for $ \text{pref} $-semantics. This makes $ \text{naive} $-semantics somewhat easier and $ \text{pref} $ the hardest among the considered semantics in this work.

Set-based argumentation. Dung's AFs can be generalized by allowing attacks not only from single arguments, but from collections of arguments^[7]. 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 \subseteq 2^V \times V $. A set-based argumentation framework (SETAF) is a B-hypergraph $ {\cal{F}} = (A, R) $ where $ A $ is the set of arguments and $ R \subseteq 2^A \times A $ represents the attacks from sets of arguments to individual arguments. A subset $ S \subseteq A $ of arguments is conflict-free, if $ (2^S \times S) \cap R = \emptyset $ and $ S $ defends an argument $ s \in A $ if for every $ (S', s) \in R $ there exists $ S" \subseteq S $ such that $ (S'',s')\in R $ for some $ s' \in 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.

For a SETAF $ {\cal{F}} $ and argument $ a\in A $, we similarly define the problems $ {\rm{Cred}}_{\sigma} $ and $ {\rm{Skep}}_{\sigma} $ asking whether $ a $ is in some $ \sigma $-extension of $ {\cal{F}} $ or every $ \sigma $-extension of $ {\cal{F}} $, respectively.

Example 2.5 Consider the SETAF $ {\cal{S}} = (A, R) $, where $ A = \{a, b, c, d, e\} $ and $ R = \{(\{a, b\}, d), (\{b, c\}, e), (\{e\}, a)\} $. In $ {\cal{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 Fig. 3. ◁

Figure 3. 

The SETAF $ {\cal{S}} $ from Example 2.5.

The corresponding decision problem for the extensions existence is defined as follows.

In this section, we prove that repairs under expressive families of ICs (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 LTGDs). Given an instance $ {\cal{D}} = \langle {\cal{T}},B\rangle $ comprising a database $ {\cal{T}} $ and a set $ B $ of ICs, the goal is to capture all the subset-repairs for $ {\cal{D}} $ by $ \sigma $-extensions of the resulting SETAF $ {\cal{S}}_{\cal{D}} $ for some semantics $ \sigma $.

In the section "Simulating DCs via SETAFs", we encode a constrained database $ {\cal{D}} = \langle {\cal{T}},D \rangle $ with database $ {\cal{T}} $ and a collection $ D $ of DCs into a SETAF $ {\cal{S}}_{\cal{D}} $. This is achieved by letting each fact $ s\in {\cal{T}} $ be an argument. Then the attack relation between arguments simulates the violation of some $ d \in D $ by sets of facts. This allows to establish a connection between repairs for $ {\cal{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 in Bienvenu & Bourgaux^[13]. 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 the section "Simulating LTGDs via SETAFs", we simulate a constrained database $ {\cal{D}}= \langle {\cal{T}}, L\rangle $ 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 $ \ell \in 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 $ {\cal{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 $ {\cal{D}} $. Interestingly, the computed preferred extension is also stable and naive, and hence coincides with the only repair for $ {\cal{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. Toward the end of our paper, in the section "Simulating FDs and IDs via AFs", we discuss 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, the section "Simulating DCs and LTGDs via SETAFs" 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).

We first formalize the notion of conflicts for a DB with respect to a set of DCs. Intuitively, a conflict in a constrained database $ {\cal{D}} $ is a minimal (under set inclusion) inconsistent set of facts from $ {\cal{T}} $ with respect to some DC in $ {\cal{D}} $.

Definition 3.1 Let $ {\cal{D}}=\langle{\cal{T}}, D \rangle $ be a constrained database with a set $ D $ of DCs. A collection $ C\subseteq {\cal{T}} $ of facts is a conflict in $ {\cal{D}} $ if there exists some $ d\in D $ such that (i) $ C\not\models d $, and (ii) $ C'\models d $ for each proper subset $ C'\subsetneq C $.

Given $ {\cal{D}} $, then by $ {\rm{Conf}}({\cal{D}}) $ we denote the set of all conflicts in $ {\cal{D}} $. It is known that $ {\rm{Conf}}({\cal{D}}) $ can be represented as a conflict hypergraph^[20], where the vertices are the facts in $ {\cal{D}} $ and hyperedges are conflicts in $ {\cal{T}} $. We follow Bienvenu & Bourgaux^[13] and transform an instance $ {\cal{D}} = \langle {\cal{T}}, D\rangle $ with database $ {\cal{T}} $ and a collection $ D $ of DCs to a SETAF $ {\cal{S}}_{\cal{D}} $.

Definition 3.2 (Bienvenu & Bourgaux^[13]) Let $ {\cal{D}} = \langle {\cal{T}}, D\rangle $ be a constrained database including a database $ {\cal{T}} $ and a collection $ D $ of DCs. Then, $ {\cal{S}}_{\cal{D}} $ denotes the following SETAF.

● $ A := {\cal{T}} $, i.e, each fact $ s\in {\cal{T}} $ is seen as an argument.

● $ R := \{(C\setminus\{t\}, t) \mid C\in{\rm{Conf}}({\cal{D}}), t\in C\} $.

We call $ {\cal{S}}_{\cal{D}} $ the SETAF generated by $ {\cal{D}} $.

It is worth highlighting that given a set $ D $ of DCs as input, then checking whether "a database $ {\cal{T}}' $ is a repair of a database $ {\cal{T}} $ w.r.t. $ D $" is $ {\bf{DP}} $-complete even if $ {\cal{T}} $ and $ {\cal{T}}' $ are both fixed^[39], Lemma 6. The complexity of the repair checking problem drops to P if we consider a fixed set of DCs. 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 $ {\cal{D}} $ in polynomial time. Furthermore, given the conflict hypergraph $ {\cal{G}}_{\cal{D}} $ for a constrained database $ {\cal{D}} $, the framework $ {\cal{S}}_{\cal{D}} $ can still be constructed in polynomial time in the size of $ {\cal{G}}_{\cal{D}} $.

Example 3.3 Consider the following database tables $ C $ and $ O $, containing the data about customers and orders, respectively.

Here, Cus_ID, Ord_ID, Prod_ID and Ship_ID are the IDs of individual customers, orders, products and shipments, respectively. Let $ D = \{{\rm{dc}}_1, {\rm{dc}}_2\} $ be a set of DCs where

and

The DC $ {\rm{dc}}_1 $ essentially says that no customer should have more than one order for the same product and $ {\rm{dc}}_2 $ 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 $ \{t_1,t_4\},\{t_1,t_3,s_1,s_2\} $. The respective SETAF $ {\cal{S}}_{\langle \{C, O\}, D \rangle} $ is depicted in Fig. 4. ◁

Figure 4. 

SETAF $ {\cal{S}}_{\langle \{C, O\}, D \rangle} $ for Example 3.3. 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. For example, the red triangle and the arrow depict the attack $ (\{t_1,s_1,s_2\},t_3) $.

It is known that the repairs for $ {\cal{D}} $ correspond precisely to the independent sets of its conflict hypergraph $ {\cal{G}}_{\cal{D}} $. Observe that the independent sets in $ {\cal{G}}_{\cal{D}} $ are exactly the naive extensions of $ {\cal{S}}_{\cal{D}} $. Moreover, using the observations from Bienvenu & Bourgaux^[13], 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 Bienvenu & Bourgaux^[13].

Theorem 3.4. Let $ {\cal{D}} = \langle {\cal{T}}, D \rangle $ be a constrained database where $ D $ is a set of DCs and let $ {\cal{S}}_{\cal{D}} $ denote the SETAF generated by $ {\cal{D}} $. Then for every $ {\cal{P}}\subseteq {\cal{T}} $, $ {\cal{P}} \in \text{repairs}({\cal{D}}) $ iff $ {\cal{P}}\in \sigma({\cal{S}}_{\cal{D}}) $ for $ \sigma \in \{\text{naive}, \text{stab}, \text{pref}\} $.

Proof Given a repair $ {\cal{P}}\subseteq {\cal{T}} $, then $ {\cal{P}}\models d $ for every $ d\in D $ and hence there is no $ C\in{\rm{Conf}}({\cal{D}}) $ with $ C\subseteq {\cal{P}} $. So, the set of arguments in $ {\cal{P}} $ is conflict-free since every attack in $ R $ has the form $ (E\setminus\{t\},t) $ where $ E\cup \{t\} \in {\rm{Conf}}({\cal{D}}) $.

The converse holds similarly. A naive extension $ P\subseteq A $ does not contain all the arguments in any attack $ (E,t) $. Thus, for every conflict $ C\in {\rm{Conf}}({\cal{D}}) $, such that $ C=E\cup\{t\} $, we have that $ C\not\subseteq P $ and therefore $ P $ (seen as a subset of $ {\cal{T}} $) is a repair for $ {\cal{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 & Bourgaux^[13]. Therefore, a usual assumption is that every DC contains at least two database atoms. This has the effect that each conflict contains at least two arguments. 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\in{\rm{Conf}}({\cal{D}}) $, there is a repair containing facts in $ C\setminus \{t\} $ as well as another one containing $ t $. As a result, we have the following observation regarding the acceptability of facts with respect to $ {\cal{D}} $. Specifically, we can decide if a given fact $ s \in {\cal{T}} $ is in some (or all) repairs, in polynomial time for a fixed set of DCs.

Remark 3.5 Let $ D $ be a set of DCs over the schema $ \tau $. Then, for every constrained database $ {\cal{D}} = \langle {\cal{T}},D \rangle $ involving a database $ {\cal{T}} $ over $ \tau $: $ \exists {\text{-}}{\rm{REP}} $ is true for every $ s\in{\cal{T}} $ and $ \forall {\text{-}}{\rm{REP}} $ is true iff $ s\not\in C $ for any $ C\in {\rm{Conf}}({{\cal{D}}}) $. Moreover, both problems are decidable in polynomial time in data complexity.

3.2.   Simulating LTGDs via SETAFs

Let $ {\cal{D}} =\langle {\cal{T}}, L\rangle $ be a constrained database with a collection $ {\cal{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 $ {\cal{T}} $ is a mapping $ h\colon V\rightarrow \text{dom}({\cal{T}}) $. For a relational atom $ T({\boldsymbol{t}}) $ with terms $ {\boldsymbol{t}}=(t_1,\dots,t_k) $, we denote by $ h(T({\boldsymbol{t}})) $ the result of substituting every $ t_i $ in $ T({\boldsymbol{t}}) $ by $ h(t_i) $, where we set $ h(t_i)=t_i $ when $ t_i $ is a constant. In other words, an assignment maps a relational atom $ T({\boldsymbol{t}}) $ to a candidate fact $ h(T({\boldsymbol{t}})) $, which may or may not be present in the database $ {\cal{T}} $. The notation extends to a conjunction of atoms by considering them as a set. Precisely, for a conjunction $ \phi({\boldsymbol{x}}) :=\bigwedge_{1\leq i\leq n} T_i({\boldsymbol{x}}_i) $ with $ {\boldsymbol{x}}_i\subseteq {\boldsymbol{x}} $ and $ T_i\in \tau $, and an assignment $ h\colon {\boldsymbol{x}}\rightarrow \text{dom}({\cal{T}}) $, we define $ h(\phi({\boldsymbol{x}}))=\{h(T_i({\boldsymbol{x}}_i))\mid 1\leq i\leq n\} $. Recall that every LTGD $ \ell\in L $ has the form $ \forall {\boldsymbol{x}} (T({\boldsymbol{x}}) \rightarrow \exists {\boldsymbol{y}} \psi({\boldsymbol{x}},{\boldsymbol{y}})) $ where $ \psi := \bigwedge_{1\leq i\leq n_\ell}\psi_i({\boldsymbol{z}}_i) $ is a conjunction of relational atoms over variables $ {\boldsymbol{z}}_i \subseteq {\boldsymbol{x}}\cup{\boldsymbol{y}} $ using relation names $ \psi_i\in\tau $. Then, $ {\cal{T}}\models \ell $ if for each assignment $ h $ such that $ h(T({\boldsymbol{x}}))\in {\cal{T}} $, there exists an assignment $ h'\colon {\boldsymbol{x}}\cup\mathbf y\rightarrow \text{dom}({\cal{T}}) $ such that $ h'\upharpoonright_{{\boldsymbol{x}}}=h\upharpoonright_{{\boldsymbol{x}}} $ and $ h'(\psi({\boldsymbol{x}}, {\boldsymbol{y}})) \subseteq {\cal{T}} $, where $ h\upharpoonright_{{\boldsymbol{x}}} $ is the restriction of $ h $ on $ {\boldsymbol{x}} $. If $ h(T({\boldsymbol{x}}))\in {\cal{T}} $ is true and there indeed exists such an assignment $ h' $ then we say that the set of facts $ h'(\psi({\boldsymbol{x}}, {\boldsymbol{y}})) $ supports the fact $ h(T({\boldsymbol{x}})) $ for the LTGD $ \ell $. For such an LTGD $ \ell $, we call $ T $ the source of $ \ell $, denoted as $ \text{source}(\ell) $. For a $ \text{source}(\ell) $-fact $ s $, we denote by $ {\boldsymbol{S}}_{\ell}({s}) $ the collection of all the sets supporting $ s $ for the LTGD $ \ell $. It is worth remarking that, for a constrained database $ {\cal{D}}=\langle{\cal{T}},L\rangle $ and $ \ell\in L $, $ {\cal{D}}\models \ell $ if and only if $ {\boldsymbol{S}}_{\ell}({s})\neq\emptyset $ for each $ \text{source}(\ell) $-fact $ s $.

Interestingly, we can encode the sets supporting a fact by using SETAFs, as formalized next.

Definition 3.6 Let $ {\cal{D}} =\langle {\cal{T}},L \rangle $ be a constrained database including a database $ {\cal{T}} $ and a collection $ L $ of LTGDs. Then $ {\cal{S}}_{\cal{D}} $ is the following SETAF.

● $ A := \{s \mid s\in {\cal{T}} \} \cup \{s_\ell \mid s{{\ is\ a }}\ \text{source}(\ell)-{\rm{fact\ for }}\ \ell\in L\} $,

● $ R := \{(s_\ell,s), (s_\ell,s_\ell) \mid s{{\ is\ a }}\ \text{source}(\ell)-{\rm{fact\ for }}\ \ell\in L \}\cup \{(S,s_\ell)\mid S\in {\boldsymbol{S}}_{\ell}({s}), \ell\in L\} $.

Intuitively, for each $ \ell\in L $ and {a $ \text{source}(\ell) $-fact $ s $}, the attack $ (s_\ell,s) $ models that the LTGD $ \ell\in L $ must be satisfied for the fact $ s $. Moreover, the self-attacks $ (s_\ell,s_\ell) $ enforce that the extensions only contain arguments corresponding to facts in the database. Then, each $ S\in {\boldsymbol{S}}_{\ell}({s}) $ attacks $ s_\ell $ and consequently, defends $ s $ against $ s_\ell $. The whole idea captured in this translation is that for each $ \ell \in L $ of the form $ \forall {\boldsymbol{x}} (T({\boldsymbol{x}}) \rightarrow \exists {\boldsymbol{y}} \bigwedge_{1\leq i\leq n_\ell}\psi_i({\boldsymbol{z}}_i)) $ where $ {\boldsymbol{z}}_i \subseteq {\boldsymbol{x}}\cup{\boldsymbol{y}} $: a $ T $-fact $ s $ is in a repair $ \mathcal P $ of $ {\cal{D}} $ if and only if there are $ \psi_i $-facts $ t_i $ for $ 1\leq i\leq n_\ell $, such that $ \{t_1,\dots,t_{n_\ell}\}\in {\boldsymbol{S}}_{\ell}({s}) $ if and only if the set $ S=\{t_1,\dots,t_{n_\ell}\} $ attacks $ s_\ell $ in $ {\cal{S}}_{\cal{D}} $ if and only if the argument $ s\in A $ is defended against $ s_\ell $ in $ {\cal{S}}_{\cal{D}} $.

Example 3.7. The database tables $ E $, $ D $ and $ P $ contain data about employees, departments and projects, respectively, and are defined as follows:

Here, Emp_ID, Dept_ID and Prod_ID are the IDs of individual employees, departments and products, respectively. Let $ L = \{{\rm{lav}}_1, {\rm{lav}}_2\} $ be a set of LTGDs where

and

The constraint $ {\rm{lav}}_1 $ essentially says that if an employee is in a department, then the department must exist and be associated with a project. The constraint $ {\rm{lav}}_2 $ says that each department has at least one employee and at least one project associated with it.

In the tables $ E $, $ D $ and $ P $, $ {\rm{lav}}_1 $ is violated while $ {\rm{lav}}_2 $ is satisfied. The source of each TGD $ \ell $, and the supporting facts for $ \text{source}(\ell) $-fact $ s $ are presented as follows:

● $ \text{source}({\rm{lav}}_1) = E, $

● $ \text{source}({\rm{lav}}_2) = D, $

● $ \{t_1,u_1\} $ supports $ s_1 $ for $ {\rm{lav}}_1 $,

● $ s_2 $ does not have any supporter for $ {\rm{lav}}_1 $

● $ \{t_2,u_2\} $ supports $ s_3 $ for $ {\rm{lav}}_1 $,

● $ \{s_1, u_1\} $ supports $ t_1 $ for $ {\rm{lav}}_2 $,

● $ \{s_3, u_2\} $ supports $ t_2 $ for $ {\rm{lav}}_2 $.

The respective SETAF $ {\cal{S}}_{\langle \{E, D, P\}, L \rangle} $ is depicted in Fig. 5. ◁

Figure 5. 

SETAF $ {\cal{S}}_{\langle \{E, D, P\}, L \rangle} $ for Example 3.7. For brevity, we rename the LTGDs $ \{{\rm{lav}}_1,{\rm{lav}}_2\} $ to be $ \{1,2\} $. Moreover, the auxiliary arguments for $ \text{source}(1) $-facts $ s_i $ are renamed to $ s_{1i} $ and those for $ \text{source}(2) $-facts $ t_j $ to $ t_{2j} $.

Similar to the case of DCs, the repair checking problem under LTGDs is $ {\bf{DP}} $-complete if the set $ L $ of ICs is considered as input (see Table 3 in Arming et al.^[39]). Therefore, we consider a fixed set $ L $ of LTGDs as the complexity drops to P in this case. Then, for a constrained database $ {\cal{D}}=\langle{\cal{T}},L \rangle $, the framework $ {\cal{S}}_{\cal{D}} $ can be constructed in polynomial time. An algorithm basically goes through every $ \ell\in L $ in turn: for each $ \text{source}(\ell) $-fact $ s $, it computes the set $ {\boldsymbol{S}}_{\ell}({s}) $ in polynomial time since the size of each LTGD in $ L $ is constant.

For a set $ L $ of LTGDs, a minimal violation of $ \ell\in L $ is caused by a single $ \text{source}(\ell) $-fact $ s $ for which $ {\boldsymbol{S}}_{\ell}({s})=\emptyset $. 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 $ \emptyset $ 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 $ \emptyset $ might be the only repair for a database $ {\cal{D}} $ involving LTGDs.

Remark 3.8 A constrained database $ {\cal{D}} = \langle {\cal{T}}, L \rangle $ involving a set $ L $ of LTGDs admits a unique repair.

Now we prove that the repair of an instance $ {\cal{D}} $ actually corresponds to the unique preferred extension of the resulting SETAF $ {\cal{S}}_{\cal{D}} $.

Theorem 3.9. Let $ {\cal{D}} = \langle {\cal{T}}, L \rangle $ be a constrained database where $ L $ is a set of LTGDs and let $ {\cal{S}}_{\cal{D}} $ denote the SETAF generated by $ {\cal{D}} $. Then for $ {\cal{P}}\subseteq {\cal{T}} $, $ {\cal{P}} \in \text{repairs}({\cal{D}}) $ iff $ {\cal{P}}\in \text{pref}({\cal{S}}_{\cal{D}}) $. Moreover, $ {\cal{S}}_{\cal{D}} $ has exactly one preferred extension.

Proof We first prove the reverse direction. Let $ P\subseteq A $ be a preferred extension in $ {\cal{S}}_{\cal{D}} $, then $ P $ must not contain an auxiliary argument $ s_\ell $ corresponding to any LTGD $ \ell\in L $ since $ P $ is conflict-free. This implies that $ P\subseteq {\cal{T}} $, which, together with the fact that $ P $ is admissible (hence every $ s\in P $ is defended against each $ s_\ell\in A $) and maximal under set inclusion, yields the proof of the claim.

Conversely, let $ {\cal{P}}\subseteq {\cal{T}} $ denote a repair for $ {\cal{D}} = \langle {\cal{T}}, L \rangle $. Then $ {\cal{P}} $ is conflict-free in $ {\cal{S}}_{\cal{D}} $ since each attack in $ R $ contains at least one argument among the auxiliary arguments ($ s_\ell $) which are not in $ {\cal{P}} $ (as $ {\cal{P}}\subseteq {\cal{T}} $). Moreover, for each $ s\in {\cal{P}} $ and $ \ell\in L $, there are $ t_1,\dots,t_{n_\ell}\in {\cal{P}} $, such that $ \{s, t_1,\dots, t_{n_\ell}\}\models \ell $. This implies that each $ s\in {\cal{P}} $ is defended against the attack $ s_\ell\in A $ since $ (\{t_1,\dots,t_{n_\ell}\}, s_\ell)\in R $. Consequently, $ {\cal{P}} $ is admissible. To prove that $ {\cal{P}} $ is also preferred in $ {\cal{S}}_{\cal{D}} $, assume the contrary that there is an admissible $ {\cal{P}}'\supset {\cal{P}} $ in $ {\cal{S}}_{\cal{D}} $. Since $ {\cal{P}}' $ is also conflict-free, using the same argument as for $ {\cal{P}} $ we notice that $ {\cal{P}}'\subseteq {\cal{T}} $. Now, $ {\cal{P}}' $ being admissible (together with the claim in reverse direction) implies that $ {\cal{P}}' $ is a repair for $ {\cal{D}} $ contradicting the fact that $ {\cal{P}} $ is a subset-maximal repair for $ {\cal{D}} $. As a consequence, $ {\cal{P}} $ is preferred in $ {\cal{S}}_{\cal{D}} $.

This proves the correctness of the theorem. The uniqueness of the extension follows due to Remark 3.8. □

Notice that a framework $ {\cal{S}}_{\cal{D}} $ may not have stable extensions for certain constrained databases $ {\cal{D}} $ including databases $ {\cal{T}} $ and LTGDs $ L $. This holds because some arguments can neither be accepted in an extension (e.g., when $ {\boldsymbol{S}}_{\ell}({s})=\emptyset $ for some $ \text{source}(\ell) $-fact $ s $ and $ \ell\in L $), nor attacked by arguments in an extension (since arguments in $ A $ only attack auxiliary arguments). Mahmood et al.^[38] presented a pre-processing over the argumentation framework generated by a constrained database $ {\cal{D}} $ involving IDs, 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\in{\cal{T}} $ in polynomial time considering the data complexity.

A pre-processing algorithm for $ {\cal{S}}_{\cal{D}} $. Observe that an undefended argument in a SETAF $ {\cal{S}}=(A,R) $ cannot belong to any preferred extension of $ {\cal{S}} $. The intuition behind pre-processing is to remove such arguments, which are not defended against some of their attacks in $ {\cal{S}}_{\cal{D}} $. This corresponds to (recursively) removing those facts $ s\in {\cal{T}} $, for which there is $ \ell\in L $ such that $ s $ is a $ \text{source}(\ell) $-fact and $ {\boldsymbol{S}}_{\ell}({s})=\emptyset $. The pre-processing (denoted $ \text{PRE}({\cal{S}}_{\cal{D}}) $) applies the following procedure as long as possible.

$ * $ For each $ s_\ell\in A $ such that $ s_\ell $ is not attacked by any $ S\subseteq A\setminus \{s_\ell\} $: remove $ s $, $ s_j $ for each $ j\in L $, as well as each attack to and from $ s $ and $ s_j $.

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 $ {\cal{D}} $ (see Remark 3.8). In the following, we also denote by $ \text{PRE}({\cal{S}}_{\cal{D}}) $ the SETAF obtained after applying the pre-processing on $ {\cal{S}}_{\cal{D}} $. Notice that $ \text{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^[28], Lem. 12.

Lemma 3.10. Let $ L $ be a fixed set of LTGDs, $ {\cal{D}}=\langle{\cal{T}}, L\rangle $ be a constrained database, and $ {\cal{S}}_{\cal{D}} $ denote the SETAF generated by $ {\cal{D}} $. Then $ \text{PRE}({\cal{S}}_{\cal{D}}) $ can be computed from $ {\cal{S}}_{\cal{D}} $ in polynomial time. Moreover, $ \text{PRE}({\cal{S}}_{\cal{D}}) $ has a unique naive extension which is also stable and preferred.

Proof The procedure $ \text{PRE}({\cal{S}}_{\cal{D}}) $ removes recursively all the arguments corresponding to facts $ s $ such that $ {\boldsymbol{S}}_{\ell}({s})=\emptyset $ for some $ \ell\in L $ and $ s $ is a $ \text{source}(\ell) $-fact. Notice that $ {\boldsymbol{S}}_{\ell}({s}) $ can be computed for each $ \ell\in L $ and $ \text{source}(\ell) $-fact $ s $ in polynomial time for a fixed set $ L $ of LTGDs. Then, $ \text{PRE} $ stores in a data structure (such as a queue) all the arguments $ s $ for which $ {\boldsymbol{S}}_{\ell}({s})=\emptyset $. Finally, each argument $ s $ in this queue can be processed turn by turn, adding possibly new arguments when $ \text{PRE} $ triggers the removal of certain arguments from $ A $ and hence from $ {\boldsymbol{S}}_{\ell}({t}) $ for some $ t\in 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, $ \text{PRE} $ runs in polynomial time in the size of $ {\cal{S}}_{\cal{D}} $.

Let $ \text{PRE}({\cal{S}}_{\cal{D}}) = (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'\setminus S $ contains self-attacks. Moreover, $ S $ is also admissible since $ {\boldsymbol{S}}_{\ell}({s})\neq \emptyset $ for every argument $ s\in S $ corresponding to a $ \text{source}(\ell) $-fact $ s $. Furthermore, since $ A'\setminus 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 $ \text{PRE}({\cal{S}}_{\cal{D}}) $ and arguments in $ A'\setminus S $ contain self-attacks.

This establishes the correctness of the lemma together with Theorem 3.9. □

As a consequence of Lemma 3.10, we can also determine $ \exists {\text{-}}{\rm{REP}} $ and $ \forall {\text{-}}{\rm{REP}} $ for each $ s\in {\cal{T}} $, once the pre-processing has terminated, resulting in $ \text{PRE}({\cal{S}}_{\cal{D}}) $.

Remark 3.11 Let $ {\cal{D}}=\langle{\cal{T}},L\rangle $ be a constrained database involving a set $ L $ of LTGDs and $ {\cal{S}}_{\cal{D}} $ denote the SETAF generated by $ {\cal{D}} $. Then, $ \exists {\text{-}}{\rm{REP}} $ and $ \forall {\text{-}}{\rm{REP}} $ is true for every $ s\in {\cal{T}} $ iff $ s\in \text{PRE}({\cal{S}}_{\cal{D}}) $. As a consequence, both problems are decidable in polynomial time in data complexity.

3.3.   Simulating DCs and LTGDs via SETAFs

Consider an instance $ {\cal{D}}= \langle {\cal{T}},B \rangle $ with a database $ {\cal{T}} $ and a collection $ B= D\cup 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 $ {\cal{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 $ \exists {\text{-}}{\rm{REP}} $ or $ \forall {\text{-}}{\rm{REP}} $ (as done in Remark 3.11) for all facts $ s\in{\cal{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 $ {\cal{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 $ {\cal{S}}_{\cal{D}} := (A,R_{{\rm{D}}}\cup R_{{\rm{L}}}) $ generated by $ {\cal{D}} $ is specified as below.

Definition 3.12 Let $ {\cal{D}} = \langle {\cal{T}}, B\rangle $ be a constrained database including a database $ {\cal{T}} $ and a collection $ B=D\cup L $ of DCs $ D $ and LTGDs $ L $. Then, we construct the SETAF $ {\cal{S}}_{\cal{D}} = (A,R_D\cup R_L) $ as follows.

● $ A := \{s \mid s\in {\cal{T}} \} \cup \{s_\ell \mid s{{\ is\ a }}\ \text{source}(\ell)-{\rm{fact\ for }}\ \ell\in L\} $,

● $ R_D := \{(C\setminus\{t\}, t) \mid C\in{\rm{Conf}}({\cal{D}}), t\in C\} $,

● $ R_L := \{(s_\ell,s), (s_\ell,s_\ell) \mid s{{\ is\ a }}\ \text{source}(\ell)-{\rm{fact\ for }}\ \ell\in L \}\cup \{(S,s_\ell) \mid S \in {\boldsymbol{S}}_{\ell}({s}) \ {\rm{for }}\ \ell\in L\} $.

As before, we call $ {\cal{S}}_{\cal{D}} $ the SETAF generated by $ {\cal{D}} $.

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 $ \exists {\text{-}}{\rm{REP}} $ and $ \forall {\text{-}}{\rm{REP}} $ are non-trivial and distinct (cf. Remarks 3.5 and 3.11). Furthermore, in the presence of both types of ICs, the repairs correspond to somewhat costly (that is, preferred) SETAF-semantics.

Theorem 3.13. Let $ {\cal{D}} = \langle {\cal{T}}, B \rangle $ be a constrained database where $ B $ includes DCs and LTGDs. Further, let $ {\cal{S}}_{\cal{D}} $ denote the SETAF generated by $ {\cal{D}} $. Then for every subset $ {\cal{P}}\subseteq {\cal{T}} $, $ {\cal{P}} \in \text{repairs}({\cal{D}}) $ iff $ {\cal{P}} \in \text{pref}({\cal{S}}_{\cal{D}}) $.

Proof The correctness follows from the proofs of Theorems 3.4 and 3.9. The conflict-freeness and admissibility of $ {\cal{P}} $ implies that each DC and LTGD in $ B $, respectively, is true in $ {\cal{P}} $. The converse follows the same line of argument. Finally, the maximality of repairs in $ {\cal{D}} $ corresponds to the maximality of extensions in the resulting SETAF $ {\cal{S}}_{\cal{D}} $. □

Next, we establish that allowing DCs and LTGDs renders the data complexity for repair existence ($ {\rm{REP}} $), as well as credulous ($ \exists {\text{-}}{\rm{REP}} $) and skeptical ($ \forall {\text{-}}{\rm{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 Theorems 4.13 and 4.16). 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 3.14. The problems $ {\rm{REP}} $ and $ \exists {\text{-}}{\rm{REP}} $ are both NP-complete in the data complexity for DCs and LTGDs.

Proof We prove that $ {\rm{REP}}_{{\rm{B}}} $ and $ \exists {\text{-}}{\rm{REP}}_{{\rm{B}}} $ are both in $ {\bf{NP}} $ for any fixed set $ B $ of DCs and LTGDs. Let $ {\cal{D}} = \langle {\cal{T}}, B \rangle $ be a constrained database involving a database $ {\cal{T}} $. For membership, one needs to guess a repair for $ {\cal{D}} $ that is non-empty, respectively contains $ s $. The verification can be done in P since $ B $ is a fixed set^[39]. Notice that we do not need to check the maximality, since if there is a non-empty subset of $ {\cal{T}} $ satisfying every IC in $ B $ (resp., a subset containing $ s $) then there is also a non-empty repair for $ {\cal{D}} $ (containing $ s $).

Hardness follows from the case of FDs and IDs proved in Theorem 4.13. To be precise, we construct a fixed set $ B $ (resp., $ B' $) of FDs and IDs for which the problem $ {\rm{REP}}_{{\rm{B}}} $ ($ \exists {\text{-}}{\rm{REP}}_{{{\rm{B}}}'} $) is $ {\bf{NP}} $-hard. □

Theorem 3.15. The data complexity of $ \forall {\text{-}}{\rm{REP}} $ is $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $-complete for DCs and LTGDs.

Proof For membership, we prove that $ \forall {\text{-}}{\rm{REP}}_{{\rm{B}}} $ is in $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $ for any fixed set $ B $ of DCs and LTGDs. To this aim, we present the following $ {\boldsymbol{\Sigma}}_2^{\rm{P}} $ procedure for the complement of $ \forall {\text{-}}{\rm{REP}}_{{\rm{B}}} $. Let $ {\cal{D}} = \langle {\cal{T}}, B \rangle $ be a constrained database involving a database $ {\cal{T}} $. One can guess a set $ {\cal{P}} $ of facts in $ {\cal{T}} $ satisfying each IC in $ B $ as a counter-example for $ s $, that is, $ s\not\in {\cal{P}} $ and $ {\cal{P}} $ is a (candidate) repair for $ {\cal{D}} $, which can be decided in P since $ B $ is fixed^[39]. However, one has to use oracle calls to determine whether $ {\cal{P}} $ is a repair (hence maximal). Then, $ \forall {\text{-}}{\rm{REP}} $ is true for $ s $ if there exists no $ {\cal{P}}\subseteq {\cal{T}} $ such that (i) $ {\cal{P}} $ satisfies each IC in $ B $, (ii) $ s\not\in {\cal{P}} $, and (iii) $ {\cal{P}} $ is a repair. This gives the stated upper bound of $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $.

For hardness, we prove that there exists a set $ B $ of DCs and LTGDs such that the problem $ \forall {\text{-}}{\rm{REP}}_{{\rm{B}}} $ is $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $-hard. We prove this claim for the case of FDs and IDs in Theorem 4.16. □

We conclude this section by noting that the combined complexity of $ {\rm{REP}} $, $ \exists {\text{-}}{\rm{REP}} $, and $ \forall {\text{-}}{\rm{REP}} $ remains open for now, although the hardness transfer from the data complexity.

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 the section "Simulating DCs and LTGDs via SETAFs", the first two subsections translate instances containing only one type of ICs to AFs. Then, we combine both FDs and IDs in the third subsection. As before, we adopt the construction for FDs from Bienvenu & Bourgaux^[13], 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, the section "The role of self-attacking arguments" 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 FDs via AFs

We transform an instance $ {\cal{D}} = \langle {\cal{T}},D \rangle $ with database $ {\cal{T}} $ and a collection $ D $ of FDs to an AF $ {\cal{F}}_{\cal{D}} $. In the case of FDs, each conflict involves two facts failing some FD $ d\in 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 $ {\cal{D}} $.

Definition 4.1 Let $ {\cal{D}} =\langle {\cal{T}}, D\rangle $ be a constrained database including a database $ {\cal{T}} $ and a collection $ D $ of FDs. Then, $ {\cal{F}}_{{\cal{D}}} $ denotes the following AF.

● $ A := {\cal{T}} $, that is, each $ s\in {\cal{T}} $ is seen as an argument,

● $ R := \{(s,t),(t,s) \mid s,t \in {\cal{T}} \ {\rm{and }}\ \{s,t\}\not\models d {{\ for\ some}}\ d \in D\} $.

We call $ {\cal{F}}_{\cal{D}} $ the argumentation framework generated by $ {\cal{D}} $ and call $ R $ the conflict graph for $ {\cal{D}} $.

Note that, for a given constrained database $ {\cal{D}} $, the framework $ {\cal{F}}_{\cal{D}} $ can be generated in polynomial time. The attack relation $ R $ is constructed for each $ d\in D $ over $ T $ in the schema of $ {\cal{D}} $ by taking each pair $ s,t $ of $ T $-facts in turn and checking whether $ \{s,t\}\models d $ or not. Moreover, the set $ D $ of FDs does not have to be fixed, as in the case of DCs.

Example 4.2 Consider $ {\cal{D}} = \langle T,D \rangle $ with database $ T=\{s,t,u,v\} $ as depicted inside table in Fig. 6 and FDs $ \{\text{dep}({{Emp\_ID}}; {{Dept}}) $, $ \text{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\}\not\models \text{dep}({{Emp\_ID}}; {{Dept}}) $, $ \{u,v\}\not\models \text{dep}({{Emp\_ID}}; {{Dept}}) $, and $ \{t,v\}\not\models \text{dep}({{Sup\_ID}}; {{Building}}) $. The resulting AF $ {\cal{F}}_{\cal{D}} $ is depicted on the right side of Fig. 6. The preferred (as well as naive and stable) extensions of $ {\cal{F}}_{\cal{D}} $ include $ \{s,v\}, \{t,u\} $ and $ \{s,u\} $. Clearly, these three are the only repairs for $ {\cal{D}} $. ◁

Figure 6. 

Argumentation framework for modeling the FDs in Example 4.2.

It is easy to observe that any subset $ {\cal{P}} \subseteq {\cal{T}} $ that satisfies each $ d \in D $ contains precisely those facts in $ {\cal{T}} $ that are not pairwise conflicting. As a result, such subsets correspond to the naive extensions (maximal conflict-free sets) of $ {\cal{F}}_{\cal{D}} $. Moreover, since the attack relation in $ {\cal{F}}_{\cal{D}} $ is symmetric, i.e., $ (s,t)\in R $ iff $ (t,s) \in R $, the preferred, stable and naive extensions coincide^[41], Prop. 4 & 5.

Observe that every FD is also a DC and hence the AF $ {\cal{F}}_{\cal{D}} $ coincides with the SETAF $ {\cal{S}}_{\cal{F}} $ for the constrained database $ {\cal{D}} $. As a consequence, we have the following corollary due to Theorem 3.4. In particular, each conflict set $ C $ (see proof of Theorem 3.4) has size two for FDs.

Corollary 4.3. Let $ {\cal{D}} = \langle {\cal{T}}, D \rangle $ be a constrained database where $ D $ is a set of FDs and let $ {\cal{F}}_{\cal{D}} $ denote the argumentation framework generated by $ {\cal{D}} $. Then for every subset $ {\cal{P}}\subseteq {\cal{T}} $, $ {\cal{P}} \in \text{repairs}({\cal{D}}) $ iff $ {\cal{P}}\in \sigma({\cal{F}}_{\cal{D}}) $ for $ \sigma \in \{\text{naive}, \text{stab}, \text{pref}\} $.

Corollary 4.3 reproves that a subset-repair for $ {\cal{D}} $ can be computed in polynomial time^[40]. Moreover, similar to the case of DCs, we can decide if a given fact $ s\in {\cal{T}} $ is in some (or all) repairs, in polynomial time. In fact, it follows from the basic properties of FDs that $ \exists {\text{-}}{\rm{REP}} $ is true for every $ s\in {\cal{T}} $, and $ \forall {\text{-}}{\rm{REP}} $ is true for a fact $ s\in {\cal{T}} $ iff $ \{s,t\} \models d $ for each $ t\in {\cal{T}} $ and $ d\in D $. Furthermore, the latter problem can be decided in polynomial time for an input $ {\cal{D}} $ where the set $ D $ of FDs does not have to be fixed (see Remark 3.5).

We conclude this section by observing that adding a size restriction on repairs renders the $ {\rm{REP}} $ problem $ {\bf{NP}} $-hard. Observe that the hardness follows due to a one-to-one correspondence between repairs and maximal independent sets of the conflict graph^[5]. 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 $ \text{dom}(T)=\{0,1\} $. The following result was proven in the context of team-semantics and maximal satisfying subteams for propositional dependence logic.

Proposition 4.4. Mahmood^[29], Theorem 3.32. There is a constrained database $ {\cal{D}} $ including a propositional database $ T $ and FDs $ D $, such that given $ k\in \mathbb N $, the problem to decide whether there is a repair $ P\subseteq T $ for $ {\cal{D}} $ such that $ |P|\geq k $ is $ {\bf{NP}} $-complete.

4.2.   Simulating IDs via AFs

Let $ {\cal{D}} = \langle {\cal{T}},I\rangle $ be a constrained database with a database $ {\cal{T}} $ and collection $ I $ of IDs. Similar to the case of LTGDs, for an ID $ i\in I $ (say, $ i := T[{\boldsymbol{x}}]\subseteq T'[{\boldsymbol{y}}] $), we call $ T $ the source of $ i $. Moreover, we call $ T' $ the target of $ i $. For $ i \in I $ and a $ \text{source}(i) $-fact $ s $, let $ t $ be $ \text{target}(i) $-fact such that $ \{s,t\}\models i $. Then we say that $ t $ supports $ s $ for the ID $ i\in I $, and $ {\boldsymbol{S}}_{i}({s}) $ denotes the set of all such supporting facts for $ s $ and an ID $ i $. Notice that for each $ i\in I $ and $ \text{source}(i) $-fact $ s $, we have that $ {\boldsymbol{S}}_{i}({s})\subseteq \text{target}(i) $. Thus, the elements in $ {\boldsymbol{S}}_{i}({s}) $ are facts instead of sets of facts as in the case of LTGDs. Clearly, $ {\cal{D}}\models i $ if and only if $ {\boldsymbol{S}}_{i}({s})\neq\emptyset $ for each $ \text{source}(i) $-fact $ s $. As for LTGDs, we create auxiliary argument $ s_i $ for each $ \text{source}(i) $-fact $ s $, which can be attacked by arguments corresponding to $ \text{target}(i) $-facts in $ {\boldsymbol{S}}_{i}({s}) $. In the following, we formalize this notion and simulate the semantics for IDs via AFs.

Definition 4.5 Let $ {\cal{D}} =\langle {\cal{T}},I \rangle $ be a constrained database including a database $ {\cal{T}} $ and a collection $ I $ of IDs. Then $ {\cal{F}}_{\cal{D}} $ is the following AF.

● $ A := {\cal{T}} \cup \{s_i \mid s {{\ is\ a }}\ \text{source}(i)-{\rm{fact\ for }}\ i\in I\} $,

● $ R := \{(s_i,s), (s_i,s_i) \mid s {{\ is\ a }}\ \text{source}(i)-{\rm{fact\ for }}\ i\in I \} \cup \{(t,s_i)\mid t\in {\boldsymbol{S}}_{i}({s}) \ {\rm{for }}\ i\in I\} $.

The intuition behind our encoding remains the same as for the case of LTGDs. That is, the attack $ (s_i,s) $ models that the ID $ i\in I $ must be satisfied for the $ \text{source}(i) $-fact $ s $ and the self-attacks $ (s_i,s_i) $ enforce extensions to only contain arguments corresponding to facts. However, we only need attacks between arguments (instead of attacks from sets of arguments) as $ {\boldsymbol{S}}_{i}({s})\subseteq \text{target}(i) $ for each $ i\in I $ and $ \text{source}(i) $-fact $ s $.

Example 4.6 Consider $ {\cal{D}} = \langle T,I \rangle $ with database $ T=\{s,t,u,v\} $ and IDs $ I := \{{{Sup\_ID}\subseteq {Emp\_ID}}, {{Covers\_For}\subseteq {Dept}}\} $. For brevity, we denote IDs by $ I= \{1,2\} $. The database and the supporting facts $ {\boldsymbol{S}}{i}{w} $ for each $ i\in I, w\in T $ are depicted in the table inside Fig. 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 $ {\boldsymbol{S}}_{1}({s})=\{t\} $, $ {\boldsymbol{S}}_{2}({s})=\{t,u\} $. Then we have the AF $ {\cal{F}}_{\cal{D}} $ as depicted in Fig. 7. The AF $ {\cal{F}}_{\cal{D}} $ has a unique preferred extension, given by $ \{s,t\} $. Clearly, this is also the only repair for $ {\cal{D}} $. ◁

Figure 7. 

The AF $ {\cal{F}}_{\cal{I}} $ modelling $ {\cal{I}} $ in Example 4.6: the red self-loops together with blue arcs depict the attacks for each fact $ w\in T $ due to IDs $ i\in I $ and the black arcs model the attacks due to the support set $ {\boldsymbol{S}}_i(w) $.

It is worth mentioning that $ \{s,t,u,v\} $ constitutes a naive extension for $ {\cal{F}}_{\cal{D}} $ in Example 4.6, although this is not a repair for $ {\cal{D}} $. Clearly, the semantics for IDs in $ {\cal{F}}_{\cal{D}} $ 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 $ {\cal{F}}_{\cal{D}} $ coincides with the SETAF $ {\cal{S}}_{\cal{D}} $ for the constrained database $ {\cal{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 3.9, which establishes the following claim.

Corollary 4.7. Let $ {\cal{D}} = \langle {\cal{T}}, I \rangle $ be a constrained database where $ I $ is a set of IDs and let $ {\cal{F}}_{\cal{D}} $ denote the argumentation framework generated by $ {\cal{D}} $. Then for $ {\cal{P}}\subseteq {\cal{T}} $, $ {\cal{P}} \in \text{repairs}({\cal{D}}) $ iff $ {\cal{P}}\in \text{pref}({\cal{F}}_{\cal{D}}) $. Moreover, $ {\cal{F}}_{\cal{D}} $ 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 4.6 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 3.11, $ \exists {\text{-}}{\rm{REP}} $ and $ \forall {\text{-}}{\rm{REP}} $ is true for every $ s\in {\cal{T}} $ such that $ s\in \text{PRE}({\cal{F}}_{\cal{D}}) $.

Example 4.8 (Continued) Reconsider the constrained database $ {\cal{D}}= \langle T, I\rangle $ from Example 4.6. Observe that the argument $ v $ is not defended against $ v_2 $ and therefore cannot be in a repair. The pre-processing removes $ \{v,v_1,v_2\} $ 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,u_1,u_2\} $ 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 $ {\cal{D}} $ as well as a $ \sigma $-extension in the reduced AF for $ \sigma\in\{\text{naive},\text{stab},\text{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 that 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 4.9 Consider a single binary relation $ T(x,y) $ in the schema, a constrained database $ {\cal{D}} = \langle T, I\rangle $ with database $ T=\{s, t, u, v\} $ and a single ID $ T[x] \subseteq T[y] $. The database table, as well as its resulting AF $ {\cal{F}}_{\cal{D}} $ (without self-attacks for auxiliary arguments), is depicted in Fig. 8. Observe that $ {\cal{F}}_{\cal{D}} $ admits the following four preferred extensions: $ \{\{s,t, u_1, v\}, \{s,t, u_1, v_1\}, \{s_1,t_1, u_1, v\}, \{s_1,t_1, u_1, v_1\}\} $. However, there is a unique repair for $ {\cal{D}} $ given as $ \{s, t, v\} $.

Figure 8. 

Argumentation framework without self-attacks for modelling IDs in Example 4.9. The auxiliary arguments are highlighted in red for convenience.

Toward the end of our paper, in the next section, we will discuss how and whether we can model IDs via another translation that avoids self-attacking arguments.

4.3.   Simulating FDs and IDs via AFs

Consider an instance $ {\cal{D}} = \langle {\cal{T}}, B\rangle $ of a database $ {\cal{T}} $ and a collection $ B = D\cup I $ of FDs $ D $ and IDs $ I $. We construct the AF $ {\cal{F}}_{\cal{D}}=(A,R_{\rm{D}}\cup R_{\rm{I}}) $ as follows.

● $ A := \{s \mid s\in {\cal{T}} \} \cup \{s_i \mid s {\rm{\ is\ a }}\ \text{source}(i)-{\rm{fact\ for }}\ i\in I\} $,

● $ R_{\rm{D}} := \{(s,t),(t,s) \mid s,t \in {\cal{T}} \ {\rm{and }}\ \{s,t\}\not\models d {\rm{\ for\ some}}\ d \in D\} $,

● $ R_{{\rm{I}}} := \{(s_i,s), (s_i,s_i) \mid s {\rm{\ is\ a }}\ \text{source}(i)-{\rm{fact\ for }}\ i\in I \}\cup \{(t,s_i)\mid t\in {\boldsymbol{S}}_{i}({s}) \ {\rm{for }}\ i\in I\} $.

As before, one may apply the pre-processing as a first step, thereby removing those facts from $ {\cal{T}} $ failing some $ i\in I $. However, the discussion regarding 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 4.10 Consider $ {\cal{D}} = \langle T,B \rangle $ with database $ T=\{s,t,u\} $ and ICs $ B= D\cup I $ where $ D= \{\text{dep}({{S up\_ID}}; {{Building}})\} $ and $ I=\{{{Covers\_For}\subseteq {{Dept}}}\} $. Moreover, the database $ T $ and the support $ {\boldsymbol{S}}_{{{Covers\_For}}\subseteq{{{Dept}}}}({w}) $ for each $ w\in T $ is depicted in the table inside Fig. 9. Then, $ \{s,t\}\not\models \text{dep}({{S up\_ID}}; {{Building}}) $, and $ \{t,u\}\not\models \text{dep}({{S up\_ID}}; $ $ {{Building}})$. The resulting AF $ {\cal{F}}_{\cal{D}} $ is shown in Fig. 9, where the edges due to the IDs are depicted in red and blue. The only preferred extension for $ {\cal{F}}_{\cal{D}} $ is $ \{t\} $. Also, the only repair for $ {\cal{D}} $ is $ \{t\} $. Further, although $ \{s,u\} $ is preferred for $ {\cal{F}}_{{\cal{D}}^{\prime}} $ where $ {\cal{D}}' =\langle T,D\rangle $ (ignoring red and blue arcs), and $ \{s,t, u\} $ is preferred for $ {\cal{F}}_{{\cal{D}}^{"}} $ where $ {\cal{D}}" =\langle T,I\rangle $ (ignoring black arcs), none of them is preferred for $ {\cal{F}}_{\cal{D}} $. ◁

Figure 9. 

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

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 4.11 (Cont.) Reconsider the constrained database $ {\cal{D}} $ from Example 4.10. Then, $ \{s,u\} $ is a naive extension for $ {\cal{F}}_{\cal{D}} $ but not preferred. Moreover, $ t $ is the only fact for which $ \exists {\text{-}}{\rm{REP}} $ and $ \forall {\text{-}}{\rm{REP}} $ is true. ◁

Corollary 4.12. Let $ {\cal{D}} = \langle {\cal{T}}, B \rangle $ be a constrained database where $ B $ includes FDs and IDs. Further, let $ {\cal{F}}_{\cal{D}} $ denote the argumentation framework generated by $ {\cal{D}} $. Then for every subset $ {\cal{P}}\subseteq {\cal{T}} $, $ {\cal{P}} \in \text{repairs}({\cal{D}}) $ iff $ {\cal{P}} \in \text{pref}({\cal{F}}_{\cal{D}}) $.

Next, we establish the data and combined complexity results for $ {\rm{REP}}, \exists {\text{-}}{\rm{REP}} $ and $ \forall {\text{-}}{\rm{REP}} $. Observe that a fixed collection of integrity constraints suffices 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 4.13. The problems $ {\rm{REP}} $ and $ \exists {\text{-}}{\rm{REP}} $ are in $ {\bf{NP}} $ for constraints that consist of FDs and IDs. Moreover, there exists a set $ B $ of FDs and IDs such that the problems $ {\rm{REP}}_{{\rm{B}}} $ and $ \exists {\text{-}}{\rm{REP}}_{{\rm{B}}} $ are both NP-hard.

Proof The membership follows analogous to the proof of Theorem 3.14 in both cases. Let $ {\cal{D}} = \langle {\cal{T}}, B \rangle $ be a constrained database where $ B $ consists of FDs and IDs. Further, let $ s\in {\cal{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 $ {\cal{D}} $ as input. Therefore, the $ {\bf{NP}} $-membership applies to $ {\rm{REP}} $ and $ \exists {\text{-}}{\rm{REP}} $.

For hardness, we reduce from $ {\rm{SAT}} $ to $ \exists {\text{-}}{\rm{REP}}_{{\rm{B}}} $ and $ {\rm{REP}}_{{\rm{B}}} $ simultaneously for a fixed set $ B $ of constraints. Let $ \varphi := \{c_i\mid {i\leq m}\} $ be a propositional formula in conjunctive normal form over propositions $ X= \{p_1,\ldots, p_n\} $. We construct a database with two relations (We find it convenient to write explicit attribute names for each relation.): (i) a $ 4 $-ary relation $ F(t_0,u_0,t_1,u_1) $, and (ii) a binary relation $ C(t_2,u_2) $. Intuitively, $ F $ encodes the positive and negative participation of propositions in the clauses of $ \varphi $. Precisely, a fact $ F(x,v,c_i,{\rm{sat}}) $ encodes that the proposition $ x $ appears positively in clause $ c_i $ 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 $ {\cal{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 $ \text{dom}(F)\subseteq\{c_i \mid i\leq m\}\cup\{p_1,\ldots, p_n\}\cup\{0,1,{\rm{sat}}\} $ and $ \text{dom}(C)=\{c_i \mid i\leq m\}\cup\{{\rm{sat}}\} $. Our database consists of the following facts:

As ICs, we consider a collection $ B $ of FDs and IDs over the schema $ \{F,C\} $ using $ V := \{t_j,u_j \mid 0\leq j \leq 2\} $ as the set of attributes (Recall that our notation for FDs and IDs uses attributes as names for the corresponding argument positions of the relation (here $ F(t_0,u_0,t_1,u_1) $ and $ C(t_2,u_2) $)). Precisely, we let

The FD $ \text{dep}({t_0};{u_0}) $ 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 $ c_i\in\varphi $ is satisfied by modeling the following intuition. (I) The ID $ F[u_1]\subseteq C[u_2] $, together with a dummy fact $ F({\rm{sat}}, {\rm{sat}}, {\rm{sat}}, {\rm{sat}}) $ (referred to as $ s_d $), encodes that any repair for $ {\cal{T}} $ containing $ s_d $ triggers a non-empty subset of $ C $-facts in a repair. (II) The ID $ C[u_2]\subseteq C[t_2] $ triggers a chain of $ C $-facts in a repair and thus enforces that either $ \emptyset $, or all $ C $-facts are considered in a repair. (III) The ID $ C[t_2]\subseteq F[t_1] $ encodes that all clauses must be satisfied if a repair contains any $ C $-fact. Moreover, (IV) the ID $ F[u_1]\subseteq F[t_1] $ is used in the reduction for $ {\rm{REP}}_{{\rm{B}}} $ to enforce that a valid repair must contain the dummy fact $ s_d $. Notice that the collection $ B $ does not depend on the formula $ \varphi $, hence it is fixed.

We next highlight some observations before delving into the correctness proof. Clearly, $ {\cal{D}} $ is inconsistent due to the presence of at least one pair of facts $ F(x,1,c_i,{\rm{sat}}), F(x,0,c_j,{\rm{sat}}) $ and the FD $ \text{dep}({t_0};{u_0}) $ (based on the fact that at least one variable $ x $ appears positively in one clause $ c_i $ and negatively in another clause $ c_j $, since otherwise $ \varphi $ is trivially satisfiable). Then, a set $ P_X $ of $ F $-facts satisfies $ \text{dep}({t_0};{u_0}) $ if for each proposition $ x\in X $: $ P_X $ contains facts of the form either $ F(x,1,*,{\rm{sat}}) $ or $ F(x,0,*,{\rm{sat}}) $ but not both (here $ * $ indicates the occurrence of any value in a fact). For $ P_X $ to be a candidate repair among $ F $-facts, it additionally has to contain facts of the form $ F(x,*,*,*) $ for each $ x\in X $. Moreover, a set $ P_c $ of $ C $-facts satisfies the ID $ C[u_2]\subseteq C[t_2] $ iff either $ P_c=\emptyset $ or $ P_c $ contains all $ C $-facts. Next, we consider a set $ P_X $ of $ F $-facts containing the fact $ s_d $ and let $ {\cal{P}}= P_X \cup P_c $. It follows that $ {\cal{P}}\models F[u_1]\subseteq C[u_2] $ iff $ P_c\neq \emptyset $ and hence we let $ P_c $ contain all $ C $-facts. Finally, $ {\cal{P}}\models C[t_2]\subseteq F[t_1] $ iff for each $ c_i\in\varphi $, $ P_X $ contains at least one fact $ F(x,v,c_i,{\rm{sat}}) $ such that $ v=1 $ if $ x\in c_i $ and $ v=0 $ if $ \neg x\in c_i $. This is guaranteed since $ {\cal{P}} $ contains facts of the form $ C(*, c ) $ for each clause $ c\in\varphi $ and thus there must exist $ F $-facts in $ {\cal{P}} $ also of the form $ F(*,*,c,*) $ for each clause $ c\in \varphi $. We prove the correctness via the following claim.

Claim 4.14. $ \varphi $ is satisfiable if and only if $ \exists {\text{-}}{\rm{REP}} $ is true for the fact $ s_d $.

Proof of claim "$ \Longrightarrow $". Suppose $ \varphi $ is satisfiable and let $ \theta $ be a satisfying assignment. We let $ {\cal{P}} := \{F(x,1,c_i,{\rm{sat}}) \mid \theta(x)=1, \ {\rm{for }}\ x\in X \ {\rm{and }}\ i\leq m\} \cup \{F(x,0,c_i,{\rm{sat}}) \mid \theta(x)=0, \ {\rm{for }}\ x\in X \ {\rm{and }}\ i\leq m\} \cup \{s_d\} \cup P_c $ where $ P_c $ contains all $ C $-facts in $ {\cal{T}} $. Then $ {\cal{P}}\models \text{dep}({t_0};{u_0}) $ because for any $ x\in X $: $ {\cal{P}} $ contains either facts of the form $ F(x,1,*,*) $ or $ F(x,0,*,*) $, since $ \theta $ is an assignment over $ X $. Next, we have that (I) $ {\cal{P}}\models F[u_1]\subseteq C[u_2] $ since $ P_c \neq \emptyset $, and (II) $ {\cal{P}}\models C[u_2]\subseteq C[t_2] $ since $ {\cal{P}} $ contains all $ C $-facts. Finally, $ {\cal{P}} $ contains at least one fact of the form $ F(*,*,c,*) $ for each clause $ c\in \varphi $ since $ \theta(\ell)=1 $ for at least one literal $ \ell\in c $ in each $ c\in \varphi $. This holds because for every clause $ c\in \varphi $, $ {\cal{P}} $ contains a fact $ F(x,v, c, {\rm{sat}}) $ for some variable $ x $ appearing in $ c $. The value $ v $ in this fact depends on how the assignment $ \theta $ satisfies $ c $, that is, $ v=1 $ if $ \theta(x)=1 $ makes $ c $ true, and $ v=0 $ if $ \theta(x)=0 $ does. As a consequence, $ {\cal{P}}\models C[t_2]\subseteq F[t_1] $. Observe that $ {\cal{P}}\models F[u_1]\subseteq F[t_1] $ follows due to the fact $ s_d\in {\cal{P}} $. To see why $ {\cal{P}} $ is a repair (i.e., subset-maximal), we note that the only facts not in $ {\cal{P}} $ are of the form $ F(x,v,c,{\rm{sat}}) $ for some $ v\in\{0,1\} $ and $ c\in\varphi $ such that $ F(x,1-v,c,{\rm{sat}})\in {\cal{P}} $ due to the way $ {\cal{P}} $ is defined. However, adding such a fact would violate the FD. Therefore, $ {\cal{P}} $ is indeed a repair. We conclude by observing that $ s_d \in {\cal{P}} $.

"$ \Longleftarrow $". Let $ {\cal{P}} $ be a repair and $ s_d \in {\cal{P}} $. From $ {\cal{P}}\models F[u_1]\subseteq C[u_2] $, it follows that $ {\cal{P}} $ must contain at least one $ C $-fact as $ s_d\in{\cal{P}} $, and from $ {\cal{P}}\models F[u_1]\subseteq C[u_2] $, it follows that $ {\cal{P}} $ actually contains all $ C $-facts. We define an assignment $ \theta $ over $ X $ by setting $ \theta(x)= 1 $ if $ {\cal{P}} $ contains $ F(x,1,*,*) $ and $ \theta(x)= 0 $ if it contains $ F(x,0,*,*) $. Since $ {\cal{P}}\models \text{dep}({t_0};{u_0}) $, the assignment $ \theta $ is well-defined, i.e., there is no $ x\in X $ for which we assign both $ \theta(x)=1 $ and $ \theta(x)=0 $. Now, $ \theta $ is defined for all the propositions in $ X $ since $ {\cal{P}} $ is subset-maximal (hence, it contains fact of the form either $ F(x,0,*,*) $ or $ F(x,1,*,*) $ for each $ x\in X $). Now, we prove that $ \theta\models\varphi $. To this aim, let $ c\in\varphi $ be any clause. Since $ {\cal{P}}\models C[t_2]\subseteq F[t_1] $, $ {\cal{P}} $ contains at least one fact of the form $ F(x,v,c,{\rm{sat}}) $ for some variable $ x $ and $ v\in\{0,1\} $, such that $ v=1 $ if $ x\in c $ and $ v=0 $ if $ \neg x\in c $ (by definition of how $ F $-facts are constructed). Therefore, we must have set $ \theta(x)=1 $ if $ v=1 $ (hence $ x\in c $) and $ \theta(x)=0 $ if $ v=0 $ ($ \neg x\in c $). As a result, $ \theta\models c $ for each $ c\in\varphi $. This proves that $ \theta\models \varphi $ and our claim follows. ■

To reduce $ {\rm{SAT}} $ into $ {\rm{REP}}_{{\rm{B}}} $, we observe that $ {\cal{P}}\models F[u_1]\subseteq F[t_1] $ iff either $ {\cal{P}} $ contains no $ F $-fact, or it contains the fact $ s_d $. However, there cannot be a repair for $ {\cal{D}} $ without any $ F $-fact but still containing $ C $-facts, since it violates the ID $ C[t_2]\subseteq F[t_1] $. As a result, one cannot construct a non-empty repair for $ {\cal{D}} $ by excluding $ s_d $. Therefore, every repair $ {\cal{P}} $ for $ {\cal{D}} $ necessarily contains $ s_d $, thereby proving the equivalence as before. In other words, there is a non-empty repair for $ {\cal{D}} $ iff $ \varphi $ is satisfiable.

This completes the proof for both cases. □

We provide an example for a better understanding of the reductions from the proof of Theorem 4.13.

Example 4.15 (Example with fixed ICs) Let $ \varphi := \{x \lor y, \neg x \lor \neg y, \neg x \lor y\} $ be a propositional formula. Our reduction for $ \exists {\text{-}}{\rm{REP}} $ gives a database $ {\cal{T}} $ with two tables $ F $ and $ C $ for the collection $ B := \{\text{dep}({t_0};{u_0})\}\cup \{F[u_1]\subseteq C[u_2], C[u_2]\subseteq C[t_2], C[t_2]\subseteq F[t_1]\} $ of dependencies.

Observe that the only satisfying assignment for $ \varphi $ is given by $ \{x\mapsto 0, y\mapsto 1\} $, which corresponds to the repair $ \{S, \bar{x}_2, \bar{x}_3, y_1, y_3\}\cup \{s_c,s_1,s_2,s_3\} $ for $ {\cal{D}} $ containing $ S $. Consequently $ \exists {\text{-}}{\rm{REP}} $ is true for the fact $ s_d $. ◁

Next, we prove that $ \forall {\text{-}}{\rm{REP}} $ is even harder and $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $-complete.

Theorem 4.16. The problem $ \forall {\text{-}}{\rm{REP}} $ is contained in $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $ for FDs and IDs. Moreover, there exists a set $ B $ of FDs and IDs such that the problem $ \forall {\text{-}}{\rm{REP}}_{{\rm{B}}} $ is $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $-hard.

Proof The membership follows analogously to the proof of Theorem 3.15. 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 $ \forall {\text{-}}{\rm{REP}} $ (i.e., in the combined complexity).

For hardness, we build on the same idea as in the proof of Theorem 4.13. Here, we reduce from an instance $ \Phi $ of the $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $-complete problem $ {\rm { 2QBF }} $. The problem $ {\rm { 2QBF }} $ is defined as follows: given a propositional formula $ \Phi = \forall Y \exists Z \varphi(Y,Z) $ where $ \varphi := \{c_i \mid 1\leq i\leq m\} $ is a CNF formula, determine whether $ \Phi $ is true (i.e., whether for every assignment to the variables in $ Y $, there exists an assignment to the variables in $ Z $ that satisfies $ \varphi $). We let $ X=Y\cup Z $ and construct a constrained database $ {\cal{D}} $ with three relations: (i) a $ 4 $-ary relation $ F(t_0,u_0,t_1,t_\exists) $, (ii) a binary relation $ S(u_1,u_\exists) $, and another (iii) binary-relation $ C(t_2,u_2) $. Moreover, we consider a collection $ B $ of FDs and IDs over the schema of $ {\cal{T}} $ using a set $ V := \{t_j,u_j \mid 0\leq j\leq 2 \}\cup \{t_\exists,u_\exists\} $ of attributes. $ B $ contains one FD $ \text{dep}({t_0};{u_0}) $ similar to the proof of Theorem 4.13. Due to the change in database relations, we adapt the collection of IDs and consider the set $ \{S[u_1]\subseteq C[u_2], C[u_2]\subseteq C[t_2], C[t_2]\subseteq F[t_1]\} $ to encode whether each clause $ c_i\in \varphi $ is satisfied. Moreover, we require an additional ID $ F[t_{\exists}]\subseteq S[u_{\exists}] $ to encode the existentially quantified variables $ Z $. As a result, we obtain $ B= \{\text{dep}({t_0};{u_0})\} \cup \{ S[u_1]\subseteq C[u_2], C[u_2]\subseteq C[t_2], C[t_2]\subseteq F[t_1], F[t_{\exists}]\subseteq S[u_{\exists}]\} $ as our fixed collection of ICs.

For the database relations, we let $ \text{dom}(F)\subseteq\{c_i \mid i\leq m\}\cup X\cup \{0,1, {\rm{exists}}, d\} $, $ \text{dom}(C)=\{c_i \mid i\leq m\}\cup\{d\} $ and $ \text{dom}(S)=\{c_1, {\rm{exists}}, d\} $. Then our encoding works mostly similar to that in the proof of Theorem 4.13, 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(c_1, {\rm{exists}}) $ together with the fact $ C(c_{m}, c_1) $. Here, we do not need the fact $ C({\rm{sat}},c_1) $ as in the proof of Theorem 4.13. The remaining $ C $-facts $ \{C(c_i, c_{i+1})\mid i< m\} $ are added as before.

2. We use $ s^d := S(d,d), y^d := F(d,d,d,d) $ and $ c^d := C(d,d) $ as dummy facts to simulate the effect that any assignment over $ Y $ yields a collection of facts in $ {\cal{T}} $ that trivially satisfies all the ICs. This is required to simulate the $ \forall $ quantification over $ Y $.

3. If a literal $ \ell \in {\rm {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 $ \ell $: we add $ F(y, 1, d, d) $ if $ \ell =y $ and $ F(y, 0, d, d) $ if $ \ell = \neg y $. Moreover, the dummy value $ d $ in this case encodes that $ \ell $ 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 $ \ell \in c_0 $ for a literal over $ Y $ that does not appear in any clause.

4. The attributes $ \{t_{\exists}, u_{\exists}\} $ encode that the $ S $-fact $ s_{{\rm{sat}}} := S(c_1,{\rm{exists}}) $ supports facts involving propositions $ z\in Z $ via the inclusion dependency $ F[t_{\exists}] \subseteq S[u_{\exists}] $. This is achieved by letting facts $ F(z,*,*,{\rm{exists}}) $ for each $ z \in Z $ together with the fact $ s_{{\rm{sat}}} $. However, all facts corresponding to variables $ y\in 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:

For correctness, notice that every assignment $ I_Y $ over $ Y $ (seen as a subset of $ Y $) corresponds to a set $ P_Y =\{ F(y,1,c_i, d) \mid y\in I_Y \ {\rm{and }}\ y\in c_i \ {\rm{for }}\ 0\leq i\leq m \} \cup \{F(y,0,c_i, d) \mid y \not \in I_Y \ {\rm{and }}\ \neg y\in c_i \ {\rm{for }}\ 0\leq i\leq m\} $ of $ F $-facts in $ {\cal{T}} $. Moreover, $ P_Y\models \text{dep}({t_0};{u_0}) $ since $ I_Y $ is an assignment over $ Y $ and thus for each $ i\neq j\leq m $, $ P_Y $ includes facts of the form either $ F(y,1,c_i, d) $ or $ F(y,0,c_j, d) $ but not both, for each variable $ y\in Y $ and clause $ c_i, c_j $. Furthermore, it is easy to observe that taking the dummy facts, i.e., $ P_D = \{y^d, s^d, c^d\} $ the collection $ P_Y\cup P_D $ satisfies the IDs $ S[u_1]\subseteq C[u_2] $ and $ C[u_2]\subseteq C[t_2] $. Now, we let $ {\cal{P}}_Y = P_Y\cup P_D $. We have that $ s_{{\rm{sat}}} \not \in {\cal{P}}_Y $. In order to extend $ {\cal{P}}_Y $ by adding $ F(z,1,c_i, {\rm{exists}}) $ or $ F(z,0,c_i, {\rm{exists}}) $ for any $ z\in Z $ and $ i\leq m $, $ s_{{\rm{sat}}} $ must be added as well due to the ID $ F[t_{\exists}]\subseteq S[{u_{\exists}}] $. However, in order to include $ s_{{\rm{sat}}} $ in any repair, we have to find $ I_Y $ and $ I_Z $ that together satisfy $ \varphi $ due to the remaining IDs, in particular due to $ C[t_2]\subseteq F[t_1] $. As a result, for any interpretation $ I_Y $ over $ Y $, there is an interpretation $ I_Z $ over $ Z $ such that: $ I_Y \cup I_Z \models \varphi $ if and only if $ {\cal{P}}_Y $ is not a repair for $ {\cal{D}} $ (since it can be extended by adding facts $ P_Z =\{ F(z,1,c_i, d) \mid z\in I_Z \ {\rm{and }}\ z\in c_i \ {\rm{for }}\ 0\leq i\leq m \} \cup \{F(z,0,c_i, d) \mid z \not \in I_Z \ {\rm{and }}\ \neg z\in c_i \ {\rm{for }}\ 0\leq i\leq m\} $ for such an interpretation $ I_Z $ in this case). Equivalently, there is a repair for $ {\cal{D}} $ not containing $ s_{{\rm{sat}}} $ if and only if the formula $ \Phi $ is false. We conclude by observing that $ \Phi $ is true if and only if every repair for $ {\cal{D}} $ contains $ s_{{\rm{sat}}} $ if and only if $ \forall {\text{-}}{\rm{REP}} $ is true for $ s_{{\rm{sat}}} $. □

We provide an example for a better understanding of the reduction from the proof of Theorem 4.16.

Example 4.17 Let $ \Phi = \forall x\forall y \exists z\exists w((x \lor y \lor z) \land (y \lor \neg z \lor \neg w) \land (y \lor z \lor w)) $ be a $ {\rm { 2QBF }} $. Then, our reduction yields a database $ {\cal{T}} $ with three database tables as depicted in Table 4 and the (fixed) collection $ B := \{\text{dep}({t_0};{u_0})\}\cup \{ S[u_1]\subseteq C[u_2], C[u_2]\subseteq C[t_2], C[t_2]\subseteq F[t_1], F[t_{\exists}]\subseteq S[u_{\exists}]\} $ of dependencies. The reader can verify that the formula $ \Phi $ is true and that for $ s_{\rm{sat}} $, $ \forall {\text{-}}{\rm{REP}} $ is true as well. For instance, the assignment $ \{x\mapsto0, y\mapsto 0\} $ results in $ I_Y=\emptyset $ and thus $ P_Y= \{\bar{x}_0, \bar{y}_0\} $. Then, although $ P_Y\cup\{y^d, s^d, c^d\} $ 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 $ \{z_1,z_3, \bar{w}_2\}\cup \{S,s_1,s_2,s_3\} $. ◁

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 subset-maximal repairs correspond to naive extensions when only one type of dependency is 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 this yields a unique preferred extension that 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 the 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 Example 4.9).

We find it worth highlighting that considerable thought has been given to 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^[42,43,37]. If a DB instance contains only one inclusion dependency ($ i $) per relation, we can simply model the set of supporting facts in $ {\boldsymbol{S}}_{i}({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 $ {\cal{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 $ {\boldsymbol{S}}_{i}({s}) $ and $ {\boldsymbol{S}}_{j}({s}) $ for IDs $ i\neq 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 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^[13], 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 in ref.^[37], 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^[38] to certain expressive ICs toward both sides of Fig. 1. Currently, the authors believe that to model arbitrary (or full) tuple-generating dependencies, one needs the so-called hyper argumentation frameworks^[44], allowing attacks between two sets of arguments. Furthermore, one can also target the richer setting of universal constraints and the symmetric difference repairs^[26]. 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^[23,24,45]. Here, ref.^[13] 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^[8,10,46]. Given an instance $ {\cal{D}} $ including a database $ {\cal{T}} $ and a collection $ B $ of dependencies, then the proposed AF $ {\cal{F}}_{\cal{D}} $ lets one determine the causes why some tuples are not in some repair (or all repairs). We note that, for IDs, the auxiliary arguments modeling each dependency in $ B $ can serve this purpose. For FDs, we believe that annotating arguments (or the attack relation between a pair of arguments) by the FDs involved in the conflict can achieve the goal. As a result, one can look at the AF $ {\cal{F}}_{\cal{D}} $ and read from it the FDs or IDs that a tuple $ s $ failing $ \exists {\text{-}}{\rm{REP}} $ or $ \forall {\text{-}}{\rm{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.