Figures (9)  Tables (11)

    • Figure 1. 

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

    • Figure 2. 

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

    • Figure 3. 

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

    • 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) $.

    • 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} $.

    • Figure 6. 

      Argumentation framework for modeling the FDs in Example 4.2.

    • 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) $.

    • Figure 8. 

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

    • 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.

    • Equivalence between DBs with expressive ICs and SETAFs, along with data complexity results.
      ICs SETAF-equivalent semantics for repairs Complexity results
      $ {\rm{REP}}_{{\rm{B}}} $ $ \exists {\text{-}}{\rm{REP}}_{{\rm{B}}} $ $ \forall {\text{-}}{\rm{REP}}_{{\rm{B}}} $
      DCs $ \sigma \in \{\text{naive},\text{pref},\text{stab}\}^\star $ (trivial) (trivial) $ \in{\bf{P}} $
      LTGDs $ \text{pref} $ (Thm. 3.9) $ \in{\bf{P}} $[15] $ \in{\bf{P}} $[15] $ \in{\bf{P}} $[15]
      DCs+LTGDs $ \text{pref} $ (Thm. 3.13) $ {\bf{NP}} $ (Thm. 3.14) $ {\bf{NP}} $ (Thm. 3.14) $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $ (Thm. 3.15)
      Equivalence between DBs with less expressive ICs and AFs, along with combined complexity results.
      ICs AF-equivalent semantics for repairs Complexity Results
      $ {\rm{REP}} $ $ \exists {\text{-}}{\rm{REP}} $ $ \forall {\text{-}}{\rm{REP}} $
      FDs $ \sigma \in \{\text{naive},\text{pref},\text{stab}\}^\star $ (trivial) (trivial) $ \in{\bf{P}} $
      IDs $ \text{pref} $ (Cor. 4.7) $ \in{\bf{P}} $[15] $ \in{\bf{P}} $[15] $ \in{\bf{P}} $[15]
      FDs+IDs $ \text{pref} $ (Cor. 4.12) $ {\bf{NP}} $ (Thm. 4.13) $ {\bf{NP}} $ (Thm. 4.13) $ {\boldsymbol{\Pi}}_2^{{\bf{P}}} $ (Thm. 4.16)
      The table at the top indicates results for expressive ICs involving a fixed set $ B $ of DCs and LTGDs, whereas the table at the bottom depicts results for less expressive ICs including FDs and IDs. The lower bounds for less expressive ICs also hold for data complexity since the involved reductions use fixed sets of constraints. The second column in each table indicates the (SET)AF-semantics corresponding to repairs for ICs in the first column, and the last three columns present the complexity of each problem. The P-results are already known in the literature, whereas the remaining results are new. Finally, the results marked by * follow from the earlier work in studies[13,17].

      Table 1. 

      Overview of our main contributions.

    • E Emp_ID Dept_ID Location D Dept_ID Dept_NAME Location
      e1 E1 D1 Paderborn d1 D1 Sales Paderborn
      e2 E2 D2 Sheffield d2 D2 Marketing Sheffield
      e3 E3 D2 Hanover d3 D3 HR Hanover
      The first column indicates identifier for each fact/tuple.

      Table 2. 

      A database with two tables over the schema {E,D}.

    • Problem: REP
      Input: a constrained database $ {\cal{D}}=\langle {\cal{T}}, B\rangle $
      Question: is there a repair $ \mathcal R\in \text{repairs}({\cal{D}}) $ with $ \mathcal R\neq \emptyset $
    • Problem: $ \exists {\text{-}}{\rm{REP}} $
      Input: a constrained database $ {\cal{D}}=\langle {\cal{T}}, B\rangle $ and a fact $ s\in {\cal{T}} $
      Question: does $ s $ belong to some repair for $ {\cal{D}} $
    • Problem: $ \forall {\text{-}}{\rm{REP}} $
      Input: a constrained database $ {\cal{D}}=\langle {\cal{T}}, B\rangle $ and a fact $ s\in {\cal{T}} $
      Question: does $ s $ belong to all repairs for $ {\cal{D}} $
    • Problem: $ {\rm{Ext}}\sigma $
      Input: an argumentation framework $ {\cal{F}} $
      Question: is it true that $ \sigma({\cal{F}})\neq\emptyset $
    • Problem: $ {\rm{Cred}}_\sigma $
      Input: an AF $ {\cal{F}} = (A, R) $ and an argument $ a \in A $
      Question: is it true that $ a \in E $ for some $ E \in \sigma({\cal{F}}) $
    • Problem: $ {\rm{Skep}}_\sigma $
      Input: an AF $ {\cal{F}} = (A, R) $ and an argument $ a \in A $
      Question: is it true that $ a \in E $ for all $ E \in \sigma({\cal{F}}) $
    • Problem: $ {\rm{Ext}}\sigma^{SET} $
      Input: a SETAF $ {\cal{F}} $
      Question: is it true that $ \sigma({\cal{F}}) \neq \emptyset $
    • $ F $$ t_0 $$ u_0 $$ t_1 $$ u_1 $$ \begin{array}{c|cc}C & t_2 & u_2 \\\hline s_c & \text { sat } & c_1 \\s_1 & c_1 & c_2 \\s_2 & c_2 & c_3 \\s_3 & c_3 & \text { sat }\end{array} $
      $ s_d $satsatsatsat
      $ x_1 $$ x $1$ c_1 $sat
      $ {\bar{x}_2} $$ x $0$ c_2 $sat
      $ {\bar{x}_3} $$ x $0$ c_3 $sat
      $ y_1 $$ y $1$ c_1 $sat
      $ {\bar{y}_2} $$ y $0$ c_2 $sat
      $ y_3 $$ y $1$ c_3 $sat

      Table 3. 

      The database corresponding to the formula $ \varphi $ from Example 4.15.

    • $\begin{array}{l|c|c} S & u_1 & u_{\exists} \\\hline s_{{\rm{sat}}} & c_1 & \text { exists } \\ s^d & d & d \end{array} $ $\begin{array}{l|cc|c|c} F & t_0 & u_0 & t_1 & t_{\exists} \\\hline y^d & d & d & d & d \\\hline x_1 & x & 1 & c_1 & d \\\bar{x}_0 & x & 0 & d & d \\\hline y_1 & y & 1 & c_1 & d \\ y_2 & y & 1 & c_2 & d \\ y_3 & y & 1 & c_3 & d \\\bar{y}_0 & y & 0 & d & d \\\hline z_1 & z & 1 & c_1 & \text { exists } \\\bar{z}_2 & z & 0 & c_2 & \text { exists } \\ z_3 & z & 1 & c_3 & \text { exists } \\\hline \bar{w}_2 & w & 0 & c_2 & \text { exists } \\ w_3 & w & 1 & c_3 & \text { exists }\end{array} $ $\begin{array}{c|c|c} C & t_2 & u_2 \\\hline s_1 & c_1 & c_2 \\ s_2 & c_2 & c_3 \\ s_3 & c_3 & c_1 \\ c^d & d & d \end{array} $

      Table 4. 

      The database corresponding to the $ {\rm { 2QBF }} $ instance $ \Phi $ from Example 4.17.