The Complexity of Finding Missing Answer Repairs

The missing answer repair problem has applications to the view update problem [19]: if $Q$ defines a view, then the missing answer repair problem is to find an update to the input database instance so that a given tuple is inserted in the view defined by $Q$ on the updated instance. To the best knowledge of the present authors, most complexity studies of updating views have focused so far on the problem of finding instance updates in order to delete a tuple from a view. This previous work was restricted to monotonic queries, and so updates were limited to deletions of tuples from the input database (see the work on deletion propagation [8, 16, 32, 31, 43] and on resilience [22, 23, 37]). In contrast, we focus on view insertions, rather than view deletions, and we consider more general (non-monotonic) queries. Consequently, our updates are comprised of both insertions and deletions. Furthermore, our results are much more optimistic than those for deleting tuples from queries. In contrast to resilience, whose data complexity is $\mathrm{𝐍𝐏}$-hard even for some conjunctive queries, we show here that the missing answer repair problem is solvable in polynomial time, in data complexity, for all semi-positive datalog programs.

Work has also been done on insertion propagation, which seeks to add tuples to views, and annotation propagation, which seeks to modify an annotation of a tuple in the source database in order to modify the annotation of a target tuple in the view [8, 52, 15, 16]. Previous work on these problems differs in important ways from the missing answer problem studied here. To understand these differences, note that, in general, updates to a database instance with the goal of updating a view are not unique. As a result, the work on view updates has always emphasized finding instance updates which satisfy some desired criteria [19]. As mentioned previously, we focus on making insertions of tuples to query results while minimizing the size of the update applied to the database. In our later discussion of related work, we outline alternative criteria for updates that have been considered.

The notion of a database repair originates in the literature on consistent query answering (CQA) [3]. In that context, given a set $\mathrm{𝐈𝐂}$ of integrity constraints and an inconsistent database instance $𝐈$ (one not satisfying $\mathrm{𝐈𝐂}$), a repair is a minimally-modified consistent database instance ${𝐈}^{\prime }$. The goal of CQA is to identify whether or not a given tuple is a certain answer, i.e., in the result of a given query $Q$ for all repairs ${𝐈}^{\prime }$. There are a number of ways to define what it means for ${𝐈}^{\prime }$ to be “minimally-modified” from $𝐈$. Most similar to the notion used here are the cardinality repair semantics [3, 36]. Given an inconsistent database instance $𝐈$ and consistent database instances ${𝐈}^{\prime }$ and ${𝐈}^{\prime \prime }$, write ${𝐈}^{\prime }{\le }_C^{𝐈}{𝐈}^{\prime \prime }$ if $|𝐈\oplus {𝐈}^{\prime }|\le |𝐈\oplus {𝐈}^{\prime \prime }|$ (where $S\oplus T$ denotes the symmetric difference of sets $S$ and $T$). In CQA with cardinality repairs, the goal is to find tuples which appear in $Q({𝐈}^{\prime })$ for all ${\le }_C^{𝐈}$-minimal consistent databases ${𝐈}^{\prime }$. In other words, minimality for cardinality repairs is defined by the size of the symmetric difference between the input database and the modified database.

CQA under cardinality repair semantics is different from the missing answer repair problem in a number of important ways. A repair in CQA is a ${\le }_C^{𝐈}$-minimal database which is consistent with the integrity constraints $\mathrm{𝐈𝐂}$ in the input. In contrast, a repair for us is any update which places the input tuple in the answer to the input query on the updated database. This means that, given an input database and input query, the minimal repair size depends on the input tuple as well. Intuitively, rather than fixing the repair size and looking for tuples appearing in the answer to the query on all repairs, we fix the tuple and look for the smallest repair. Due to these differences, it is not immediately clear how to relate the computational complexity of these two problems.

Another context in which database repairs appear is data cleaning [21]. One of the aspects of cleaning data collected, for example, from the Web, requires restoring expected integrity constraints, and hence repairing inconsistent database instances (e.g. [33, 57, 5, 10, 25]). This is similar to CQA, except that the priority is only to restore consistency. If we consider a query language capable of expressing certain integrity constraints (typically as the truth of a Boolean query), then the missing answer repair problem asks for a minimal cardinality repair in order to update an inconsistent database to a consistent one. We do not view the work in the present paper as particularly relevant to this line of research, since expressing commonly studied forms of integrity constraints, such as functional and inclusion dependencies, or tuple-generating dependencies, is not possible without using some form of universal quantification in the query. In contrast, we focus here on fragments of semi-positive datalog, which lacks universal quantification¹¹1However, it should be noted that some integrity constraints, such as tuple-generating dependencies, can be expressed in semi-positive datalog when the universally-quantified variables are instantiated with constants. In this sense, our results show that tuple-generating dependencies can be repaired “tuple-by-tuple” in polynomial-time (for each tuple) data complexity..

As deletion propagation and resilience are concerned with modifying a database to add tuples to the answer of a query, they might be aptly interpreted as wrong answer repair problems. Missing and wrong answer repairs are related as follows. Given a query $Q$, let $\neg Q$ (the negation of $Q$; see Remark 2.3) denote a query which, on each database instance $𝐈$, returns the complement of $Q(𝐈)$ (with respect to all tuples of appropriate arity over the active domain of $𝐈$). Clearly, the problem of deleting a tuple from the answer to $Q$ is the same as inserting a tuple into the answer to $\neg Q$. Prior work on wrong answer repairs has focused on non-recursive monotone queries, primarily conjunctive queries or unions of conjunctive queries [15, 16, 22, 40, 41, 44, 45]. In contrast, the present paper focuses on semi-positive datalog and its fragments. While negation provides a direct link between missing and wrong answer repairs, the application of negation to unions of conjunctive queries yields universal (rather than existential) queries which are not expressible in the sub-classes of semi-positive datalog that we consider here.

We consider four versions of the problem in the combined complexity setting: MA${}_{}{}^{ℒ}{}_{dec}{}^{}$, MA${}_{}{}^{ℒ}{}_{bound}{}^{}$, MA${}_{}{}^{ℒ}{}_{size}{}^{}$, and MA${}_{}{}^{ℒ}{}_{min}{}^{}$, where the problem is parametrized by a class $ℒ$ of queries. Our main combined complexity results are summarized in the following table.

Some of the results in Table 1 are not tight; in cases like this, the table depicts only our best upper bound for the complexity of the problem. For example, the upper bound we provide for MA${}_{}{}^{ℒ}{}_{min}{}^{}$ for $ℒ\in \{\text{PJ},\text{UCQ}\text{<sub class="ltx\_sub">¬</sub>}\}$ is ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}[O(n^2)]}$, which does not match our lower bound of ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}[O(\log (n))]}$. However, this is typical for such results on oracle complexity for (the function versions of) optimization problems²²2The formal definitions of ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}[O(\log (n))]}$ and ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}[O(n^2)]}$ can be found in Section 2.. For example, to the authors’ knowledge, the best known lower bound for constructing optimal solutions for optimization problems like minimum set cover, minimum vertex cover, maximum clique, and others, is ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}[O(\log (n))]}$, while the tightest known upper bound known for these problems is ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}[O(n)]}$. Another bound which is not tight is the complexity of MA${}_{}{}^{\text{sp-Datalog}}{}_{bound}{}^{}$. We show in Section 4 that this problem is $\mathrm{𝐄𝐗𝐏}$-hard and contained in $\mathrm{𝟐}𝐄𝐗𝐏$, but we leave open its precise complexity.

In addition to the results depicted in the Table 1, we also provide a minimum set cover-hardness of approximation result for MA${}_{}{}^{\text{PJ}}{}_{min}{}^{}$ via strict reductions (a special case of the $L$-reductions defined in [48]; see Definition 2.5). The class $\mathrm{𝐎𝐩𝐭𝐏}$, introduced in [34] and expounded further in [24], is used to capture the complexity of determining the optimal value for $\mathrm{𝐍𝐏}$-complete optimization problems. Given the $\mathrm{𝐍𝐏}$-completeness of MA${}_{}{}^{\text{PJ}}{}_{bound}{}^{}$, this is the natural class to capture the complexity of MA${}_{}{}^{\text{PJ}}{}_{size}{}^{}$.

In data complexity, we study the MA${}_{}{}^Q{}_{dec}{}^{}$, MA${}_{}{}^Q{}_{bound}{}^{}$, and MA${}_{}{}^Q{}_{min}{}^{}$ problems, where the query $Q$ is fixed; the results are summarized in Table 2. Note that the complexity of the MA${}_{}{}^Q{}_{bound}{}^{}$, MA${}_{}{}^Q{}_{size}{}^{}$, and MA${}_{}{}^Q{}_{min}{}^{}$ problems for RA queries $Q$ varies from query to query; we discuss the decidability of these problems at the end of Section 5. Furthermore, the results on CCQ follow immediately from the observations in the introduction involving negation, together with results from [22, 23] providing dichotomies for resilience of certain sub-classes of conjunctive queries. The MA${}_{}{}^Q{}_{size}{}^{}$ and MA${}_{}{}^Q{}_{min}{}^{}$ results for this class follow from standard arguments ([47, pgs. 415-422]) using binary search with $\mathrm{𝐍𝐏}$ oracle queries to identify the size of an optimal repair as well as a polynomial-time construction of a minimal repair via $\mathrm{𝐍𝐏}$ oracle queries. We include this row to indicate that the various missing answer problems can be intractable, even in data complexity, for reasonable classes of queries.

Under combined complexity, the missing answer repair problem generalizes query satisfiability [1] (recall that a query $Q$ is satisfiable if there exists a database instance $𝐈$ where $Q(𝐈)\ne \mathrm{\varnothing }$). More precisely, a Boolean query $Q$ is satisfiable if and only if there exists a repair for the input $⟨Q,𝐄,ϵ⟩$ to the missing answer decision problem, where $𝐄$ and $ϵ$ are the empty database and empty tuple, respectively. In Section 4, we extend this observation to non-Boolean queries, and we use this relationship to transfer known complexity lower bounds for satisfiability to the missing answer problem for many classes of queries.

As mentioned in the introduction, there are, in general, many updates to a database which might yield a desired change in a view. Consequently, work on view updates has focused on finding updates with certain goals in mind: (1) minimizing the size of the instance update, (2) updating the instance while preserving specified integrity constraints, (3) determining if an update to the view exists which does not induce any other view “side-effects,” and (4) minimizing “side-effects” on the view. Note that view side-effects refer to additional changes to the tuples appearing in the view beyond the original desired update.

We focus on view insertions which minimize the number of insertions and deletions made to the database (i.e., goal (1) above). This problem has been studied to some extent in prior work. In particular, it was shown in [15, 16] that for selection-free conjunctive queries, under combined complexity, computing a minimal repair for view insertions is $\mathrm{𝐍𝐏}$-hard, while it can be done in polynomial-time for unions of conjunctive queries which lack either joins or projections. We refine this result in several ways. First, we provide a similar hardness result for selection-free conjunctive queries, even under the assumption that the schema is fixed. In contrast, [15] allows for arbitrarily many relations to occur in the schema, and their proof of hardness depends on this fact. Second, we show that the polynomial-time results are extendable to queries with atomic negation. Finally, we provide concrete upper bounds in $\mathrm{𝐎𝐩𝐭𝐏}$ and ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$ for the functional versions of these problems (MA_size and MA_min). Other work on insertion propagation has emphasized (2) and (3), particularly on computing updates to the source database which maintain integrity constraints such as functional dependencies without view side-effects [43, 44]. This has also been the focus for much of the work on annotation propagation [15, 16]. In the study of deletion propagation and resilience, all of (1) through (4) have been studied [8, 15, 16, 32, 31, 22, 41, 40, 45, 23, 42], albeit not for query languages as powerful as those we study in this paper.

In [41], the authors define a bounded insertion propagation problem, which they show is ${\mathrm{\Sigma }}_2^P$-complete for conjunctive queries under combined complexity. The problem defined in that paper is analogous to our definition of the MA_bound problem, but differs in important ways. First, the schema is not fixed. Second, the relations are assumed to be associated with typed attributes, where the domain of each attribute is specified in the input. In contrast, we assume that the schema is fixed, and that any data (even outside the active domain of the input structure) can appear in repairs. Both of these differences feature prominently in the ${\mathrm{\Sigma }}_2^P$-completeness proof in [41, Theorem 4], and so it is clear that the problem is computationally much different. In particular, a consequence of our results is that the MA_bound problem for conjunctive queries is $\mathrm{𝐍𝐏}$-complete.

One significant difference between the work presented here and prior work on the missing and wrong answer problems is that we consider more powerful query languages. We consider conjunctive queries, unions of conjunctive queries, and datalog, as well as their extensions with negated (extensional) atoms. In particular, such extensions require that repairs consist of both insertions and deletions, as opposed to just insertions, which suffice only to repair missing answers for monotone queries. With respect to combined complexity, the relationship with satisfiability is for arbitrary classes of queries closed only under composition with weak forms of selection or projection. In contrast, previous work on wrong answers focuses on unions of conjunctive queries (UCQs) [8, 16] or just conjunctive queries (CQs) [32, 31, 22, 23]. Another significant difference is that we allow for insertions with data that is not necessarily in the active domain of the input database $𝐈$ or the query $Q$. For queries without negation, this makes no difference; however, as mentioned above, we consider queries with negated atoms. In contrast, prior work on missing answers for arbitrary first-order queries [25, 57] limits insertions to those constructed from active domain elements.

It is also important to highlight a distinct approach to view updates originating in [19], where the authors define update translations and provide conditions for a correct translation of view updates. This work is extended in [4], which introduces the notion of the complement of the view, which is a particular type of mapping from database instances to pairs of views. Note that the translation and complement definitions are independent of a given database model. In [17], the authors apply this framework specifically to the relational database model, in the simplified setting with a single relation, functional dependencies, and views defined by projections on that relation. The authors provide several complexity results for decision problems related to view insertions and view complements. In general, these problems appear in the lower levels of the polynomial hierarchy, and more work is needed to determine the relationship of this framework to the missing answer repair problem studied here.

The issue of finding explanations for missing answers has also been studied using a variety of techniques [12, 28, 27, 54, 56, 50, 7, 6, 49], and especially using formalizations of provenance [9, 26, 29, 25, 57] and of causality. The latter work discusses two ways of quantifying the relative importance of causes: responsibility [39, 38] and resilience [22, 23, 37]. In fact, computing resilience is essentially computing repairs for wrong answers.

We fix countably infinite sets $\mathrm{𝐕𝐚𝐫}$ and $\mathrm{𝐃𝐨𝐦}$ of variables and constants, respectively. Terms are elements of $\mathrm{𝐕𝐚𝐫}\cup \mathrm{𝐃𝐨𝐦}$. An assignment is a partial map $g:\mathrm{𝐕𝐚𝐫}\to \mathrm{𝐃𝐨𝐦}$. We write $x,y,z,u,v$ to denote variables, $a,b,c,d,e$ to denote constants, and $s,t$ to denote arbitrary terms. We use an overline notation to denote tuples of variables or constants, and we write $\text{len}(\overline{a})$ to denote the length of a tuple $\overline{a}$. Given a tuple $\overline{t}$ of terms and an assignment $g$, we write $g(\overline{t})$ to denote the tuple of constants obtained by replacing all variables in $\overline{t}$ with their image under $g$. We will sometimes abuse notation by treating tuples as sets. We fix a finite schema $\mathrm{\Sigma }$ of extensional database predicates (EDBs) and an infinite schema $𝐒$ of intensional database predicates (IDBs). Each relation symbol $F\in \mathrm{\Sigma }\cup 𝐒$ has an associated natural number arity (denoted $\mathrm{𝐚𝐫𝐢𝐭𝐲}(F)$), and we assume $𝐒$ contains infinitely many symbols of each arity.

Atoms are either equalities of the form $s=t$, where $s$ and $t$ are terms, or expressions of the form $F(t_1,\mathrm{\dots },t_k)$, where $F\in \mathrm{\Sigma }\cup 𝐒$ with $\mathrm{𝐚𝐫𝐢𝐭𝐲}(F)=k$ and $t_1,\mathrm{\dots },t_k$ are terms. An extensional (resp. intensional) atom is one constructed with a relation symbol from $\mathrm{\Sigma }$ (resp. $𝐒$). A positive literal is an atom, and a negative literal is an expression of the form $\neg \alpha$, where $\alpha$ is a positive literal. We write $\alpha ,\beta ,\gamma$ to denote (positive or negative) literals. We write $\mathrm{𝐫𝐞𝐥}(\alpha )$ to denote the relation symbol occurring in a literal $\alpha$ and $\mathrm{𝐯𝐚𝐫}(\alpha )$ to denote the variables occurring in $\alpha$. A fact is an extensional atom with no variables. Given a subset $D\subseteq \mathrm{𝐃𝐨𝐦}$, we write $\mathrm{𝐅𝐚𝐜𝐭𝐬}(D)$ to denote the set of all facts containing only constants in $D$. An instance is a finite set of facts; we denote instances by $𝐈$, $𝐉$.

A datalog rule is an expression $r$ of the form

where $S(\overline{x})$ is an intensional atom, $\overline{x}$ is a tuple over $\mathrm{𝐕𝐚𝐫}$ with $\text{len}(\overline{x})=\mathrm{𝐚𝐫𝐢𝐭𝐲}(S)$, each ${\alpha }_i$ is a positive literal with $\mathrm{𝐫𝐞𝐥}({\alpha }_i)\in \mathrm{\Sigma }\cup 𝐒$, and $\overline{x}\subseteq \overline{y}={\bigcup }_{i\le n}\mathrm{𝐯𝐚𝐫}({\alpha }_i)$. We refer to $S(\overline{x})$ as the head of $r$, and ${\alpha }_1,\mathrm{\dots },{\alpha }_n$ as the body of $r$, denoted ${\mathrm{𝐁𝐨𝐝𝐲}}_r(\overline{y})$. While we do not allow constants to appear in the head of rules, these can be simulated using equality atoms in the body of the rule. We write $\mathrm{𝐟𝐫𝐞𝐞}(r)$ to denote the variables occurring in the head of $r$ and $\mathrm{𝐛𝐨𝐮𝐧𝐝}(r)$ to denote the variables in the body of $r$ which do not occur in $\mathrm{𝐟𝐫𝐞𝐞}(r)$. Additionally, we set $\mathrm{𝐯𝐚𝐫}(r)=\mathrm{𝐟𝐫𝐞𝐞}(r)\cup \mathrm{𝐛𝐨𝐮𝐧𝐝}(r)$. If $\overline{t}$ is a tuple of terms with $\text{len}(\overline{y})=\text{len}(\overline{t})$, then we write ${\mathrm{𝐁𝐨𝐝𝐲}}_r(\overline{t})$ to denote the expression obtained by substituting the terms in $\overline{t}$ for the corresponding variables in $\overline{y}$.

A datalog program $P$ is a finite sequence $r_1,\mathrm{\dots },r_m$ of rules such that every intensional relation symbol which occurs in the body of some $r_i$ also must occur in the head of some $r_j$; each datalog program $P$ also has a designated intensional relation symbol ${\mathrm{𝐚𝐧𝐬}}_P$ denoting the answer predicate for $P$. The arity of a program $P$ (denoted by $\mathrm{𝐚𝐫𝐢𝐭𝐲}(P)$) is the arity of its answer predicate. We also assume that all datalog programs are safe, meaning that every variable in each rule appears in some positive literal in the body of the rule.

A conjunctive query is a datalog program containing a single rule whose body contains only extensional atoms, and a union of conjunctive queries is a datalog program consisting of conjunctive queries, each having the same head. We write CQ, UCQ, and Datalog to denote the classes of conjunctive queries, unions of conjunctive queries, and datalog programs, respectively. A semi-positive datalog rule has the same form as a datalog rule (see Equation 1), except that we allow each ${\alpha }_i$ to be a positive literal with $\mathrm{𝐫𝐞𝐥}({\alpha }_i)\in \mathrm{\Sigma }\cup 𝐒$, a negative literal with $\mathrm{𝐫𝐞𝐥}({\alpha }_i)\in \mathrm{\Sigma }$, or an inequality atom of the form $s\ne t$, where $s,t\in \mathrm{𝐃𝐨𝐦}\cup \mathrm{𝐕𝐚𝐫}$. We write CQ_¬, UCQ_¬, and sp-Datalog for the extensions of CQ, UCQ, and Datalog with negated extensional atoms and inequality atoms. We will generally use $P$ to denote Datalog or sp-Datalog programs, and $Q$ to denote queries in UCQ_¬ or its sub-classes. We write $\text{adom}(Q)$ for the set of constants occurring in a query $Q$, and for a database instance $𝐈$, we also set $\text{adom}(Q,𝐈)=\text{adom}(Q)\cup \text{adom}(𝐈)$.

In Section 4, we provide a characterization of which subclasses of UCQ_¬ (i.e., SPJU_¬), defined by operations of the relational algebra, admit polynomial-time solvability of the missing answer problem. Rather than introduce the notation of the relational algebra, we instead look at the equivalent notions in our rule-based framework. We say that a semi-positive datalog program $P$ is self-join-free if, for each rule $r$ in $P$, the body of $r$ does not contain more than one occurrence of a given relation symbol in $\mathrm{\Sigma }\cup 𝐒$. We say that a semi-positive datalog program $P$ is projection-free if, for each rule $r$ in $P$, we have that $\mathrm{𝐛𝐨𝐮𝐧𝐝}(r)=\mathrm{\varnothing }$. We say that a semi-positive datalog program is selection-free if it contains no occurrences of constants or equality atoms and none of its atoms contain duplicate variables. We say that $r$ is join-free if the body of the rule contains only one atom. We write PJ for the selection-free sub-class of CQ, SPU_¬ for the join-free sub-class of UCQ_¬, and SJU_¬ for the projection-free sub-class of UCQ_¬. We study these classes in Section 4.

As suggested in the introduction, the missing answer repair problem for a class $ℒ$ of queries may be seen as a generalization of the satisfiability problem for $ℒ$, formally defined below.

It is well-known that this problem is undecidable for the relational calculus [53], and hence also for relational algebra and stratified datalog. In addition to satisfiability, we will also compare the evaluation problem to the missing answer repair problem.

We write Eval^Q to denote the data complexity version of this problem, where the query $Q$ is fixed, and inputs are of the form $⟨𝐈,\overline{a}⟩$. Finally, for ease of reference, we define the following notion of the negation of a query.

We assume familiarity with the usual classes $𝐏$, $\mathrm{𝐍𝐏}$, $\mathrm{𝐄𝐗𝐏}$, $\mathrm{𝐍𝐄𝐗𝐏}$, $\mathrm{𝟐}𝐄𝐗𝐏$, and $\mathrm{𝟐}𝐍𝐄𝐗𝐏$. We prepend an “F” to a class to indicate the corresponding class of function problems (e.g., $\mathrm{𝐅𝐏}$, $\mathrm{𝐅𝐄𝐗𝐏}$).

For the next three definitions, we fix a finite tape alphabet $\mathrm{\Gamma }$.

Before turning to our main results, we begin with some preliminary observations.

The first claim is by the reduction $⟨Q,𝐈,\overline{a}⟩\mapsto ⟨Q,𝐈,\overline{a},0⟩$. The second claim follows from the observation that $\text{MA}{}_{}{}^{ℒ}{}_{size}{}^{}(Q,𝐈,\overline{a})=0$ if and only if $\text{MA}{}_{}{}^{ℒ}{}_{min}{}^{}(Q,𝐈,\overline{a})=(\mathrm{\varnothing },\mathrm{\varnothing })$ if and only if $\text{Eval}\text{<sup class="ltx\_sup"><span class="ltx\_text ltx\_font\_caligraphic">L</span></sup>}(Q,𝐈,\overline{a})$ returns true. The linear running time is only required in order to copy the input to the oracle tape, call the oracle, and return the answer. $◀$

Note that the relationships in Proposition 3.3 also hold for the data complexity versions of the problems. Since Eval${}^{\text{CQ}}$ is $\mathrm{𝐍𝐏}$-complete [11], it follows immediately from Proposition 3.3 that MA${}_{}{}^{\text{CQ}}{}_{bound}{}^{}$ is $\mathrm{𝐍𝐏}$-hard, and that MA${}_{}{}^{\text{CQ}}{}_{min}{}^{}$ cannot be solved in polynomial time (unless $𝐏=\mathrm{𝐍𝐏}$). We refine these statements significantly in Section 4. Proposition 3.3 also implies that MA${}_{}{}^{\text{Datalog}}{}_{bound}{}^{}$ is $\mathrm{𝐄𝐗𝐏}$-hard, since Eval${}^{\text{Datalog}}$ is $\mathrm{𝐄𝐗𝐏}$-complete [18] (implicit in [55, 30]).

We now consider some basic relationships between the different versions of the missing answer problem. Clearly, the MA${}_{}{}^{ℒ}{}_{min}{}^{}$ problem is at least as hard as MA${}_{}{}^{ℒ}{}_{dec}{}^{}$, MA${}_{}{}^{ℒ}{}_{bound}{}^{}$, and MA${}_{}{}^{ℒ}{}_{size}{}^{}$; similarly, MA${}_{}{}^Q{}_{min}{}^{}$ is at least as hard as MA${}_{}{}^Q{}_{size}{}^{}$ and MA${}_{}{}^Q{}_{bound}{}^{}$. Furthermore, MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ is the natural “decision version” of the MA${}_{}{}^{ℒ}{}_{min}{}^{}$ optimization problem. There is no immediate relationship between MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ and MA${}_{}{}^{ℒ}{}_{dec}{}^{}$, since for a given triple $⟨Q,𝐈,\overline{a}⟩$, there may be a repair, but not one of size $k$. However, a straightforward relationship can be identified for classes of queries with the following property.

The intuition for Definition 3.4 is in the name: for a class of queries $ℒ$ which admits computable bounded repairs, there is a computable function which outputs a finite search space of repairs for any missing answer input for that class. A notion similar to Definition 3.4 will appear in Section 5 when analyzing the data complexity of the MA${}_{}{}^Q{}_{min}{}^{}$ problem for sp-Datalog queries $Q$ (cf. Definition 5.1). It is straightforward from Definition 3.4 to verify the following proposition.

Importantly, although the MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ problem for a class $ℒ$ of queries appears to have the flavor of an $\mathrm{𝐍𝐏}$ problem, this is not true in general. As an example, the combined complexity of Datalog evaluation is $\mathrm{𝐄𝐗𝐏}$-complete [18, 55, 30], and so MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ is not in $\mathrm{𝐍𝐏}$ (unless $\mathrm{𝐍𝐏}=\mathrm{𝐄𝐗𝐏}$), since $\text{Eval}{}^{\text{Datalog}}{\le }_P\text{MA}{}_{}{}^{\text{Datalog}}{}_{bound}{}^{}$ per Proposition 3.3. However, since inputs to MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ include the integer $k$ which bounds the total number of insertions and deletions in witness repairs, it suffices to consider repairs which are at most exponentially-large with respect to the input. This allows us to state a general upper bound, which requires only that the class of queries in question has an evaluation problem in $\mathrm{𝐍𝐄𝐗𝐏}$, and that the class contains only generic queries, as defined below.

In other words, a query is generic if its answer is invariant to renaming constants not explicitly appearing in the active domain of the query. We are now ready to state and prove the general upper bound for MA${}_{}{}^{ℒ}{}_{bound}{}^{}$.

By genericity, for an input $⟨Q,𝐈,\overline{a},k⟩$ of size $N$, it suffices to consider repairs over $\overline{a}\cup \text{adom}(Q,𝐈)\cup C$, where $C$ is a set of fresh constants of size $k$. The algorithm proceeds as follows: non-deterministically generate an update $𝖴$ of cardinality at most $k$, and then non-deterministically generate a possible witness for Eval^L for the instance ${𝐈}_{𝖴}$. The algorithm concludes by computing $\text{Eval}\text{<sup class="ltx\_sup"><span class="ltx\_text ltx\_font\_caligraphic">L</span></sup>}({𝐈}_{𝖴})$ and returning the answer. This algorithm is clearly correct. Furthermore, note that, since $k$ is represented in binary, the instance ${𝐈}_{𝖴}$ may be exponentially-larger than the encoding of the input. Then, because the witness for Eval^L may be exponentially-larger than ${𝐈}_{𝖴}$, the algorithm is in $\mathrm{𝟐}𝐍𝐄𝐗𝐏$. $◀$

Since Eval${}^{\text{sp-Datalog}}$ is in $\mathrm{𝐄𝐗𝐏}$ and Eval${}^{\text{RA}}$ is in $\mathrm{𝐏𝐒𝐏𝐀𝐂𝐄}$ ([1]), the above result implies that MA${}_{}{}^{\text{Datalog}}{}_{bound}{}^{}$, MA${}_{}{}^{\text{sp-Datalog}}{}_{bound}{}^{}$, and MA${}_{}{}^{\text{RA}}{}_{bound}{}^{}$ are in $\mathrm{𝟐}𝐍𝐄𝐗𝐏$. Note that the argument for Proposition 3.7 also yields a $\mathrm{𝟐}𝐍𝐄𝐗𝐏$ upper bound for the complexity of MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ even if we assume that Eval^L is in $\mathrm{𝐄𝐗𝐏}$; we state the proposition for the hypothesis that Eval^L is in $\mathrm{𝐍𝐄𝐗𝐏}$ to make it as general as possible. In Section 4, we refine the upper bound for MA${}_{}{}^{\text{Datalog}}{}_{bound}{}^{}$ (resp. MA${}_{}{}^{\text{sp-Datalog}}{}_{bound}{}^{}$) down to $\mathrm{𝐄𝐗𝐏}$ (resp. $\mathrm{𝟐}𝐄𝐗𝐏$) by giving a $\mathrm{𝐅𝐄𝐗𝐏}$ (resp. $\mathrm{𝐅𝟐𝐄𝐗𝐏}$) algorithm for MA${}_{}{}^{\text{Datalog}}{}_{min}{}^{}$ (resp. MA${}_{}{}^{\text{sp-Datalog}}{}_{min}{}^{}$).

While MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ is not always an $\mathrm{𝐍𝐏}$ problem, we can give a very simple general criterion for MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ to be in $\mathrm{𝐍𝐏}$. Say that a class of queries $ℒ$ admits polynomially-bounded repairs if $ℒ$ admits computable bounded repairs and ${\beta }_{ℒ}$ is computable in polynomial time. Then by a similar algorithm to the proof of Proposition 3.7, we obtain the following proposition.

Recall that a query $Q$ in UCQ_¬ is satisfied in an instance if there exists a satisfying assignment from the domain of the instance to one of the conjunctive queries in the definition of $Q$. Let $m$ denote the number of variables in the conjunctive query in the definition of $Q$ with the most variables. The range of a satisfying assignment for $Q$ has size at most $m$, and so it suffices to consider repairs over the domain $\overline{a}\cup \text{adom}(Q,𝐈)\cup C$, where $C$ is a set of $m$ fresh constants. We conclude that UCQ_¬ admits polynomially-bounded repairs. Furthermore, it is already known that Eval${}^{\text{UCQ}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}}$ is in $\mathrm{𝐍𝐏}$ [1]. Hence UCQ_¬ satisfies the hypotheses of Proposition 3.8, and so the MA${}_{}{}^{\text{UCQ}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}}{}_{bound}{}^{}$ problem (and MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ for all syntactic fragments $ℒ$ of UCQ_¬) are in $\mathrm{𝐍𝐏}$.

For our results relating MA${}_{}{}^{ℒ}{}_{dec}{}^{}$ and dbSAT${}^{ℒ}$, we need only to assume that the query class $ℒ$ is closed under a weak form of selection and projection. We say that a class $ℒ$ of queries is closed under (weak) selection if there is a polynomial-time computable map which, given an $n$-ary query $Q\in ℒ$ and a tuple $\overline{a}$ of length $n$, constructs a query $Q^{\prime }\in ℒ$ such that for all instances $𝐈$, we have $Q^{\prime }(𝐈)\ne \mathrm{\varnothing }$ if and only if $\overline{a}\in Q(𝐈)$. We say that a class $ℒ$ of queries is closed under (weak) projection if there is a polynomial-time computable map which, given $Q\in ℒ$, constructs a query $Q^{\prime }\in ℒ$ such that for all instances $𝐈$ we have $Q^{\prime }(𝐈)=\top$ if and only if $Q(𝐈)\ne \mathrm{\varnothing }$.

Given an input $⟨Q,𝐈,\overline{a}⟩$ to MA${}_{}{}^{ℒ}{}_{dec}{}^{}$, let $Q^{\prime }$ be the query in $ℒ$ guaranteed by closure under weak selection. If $⟨Q,𝐈,\overline{a}⟩\in \text{MA}{}_{}{}^{ℒ}{}_{dec}{}^{}$, then $Q^{\prime }({𝐈}_{𝖴})\ne \mathrm{\varnothing }$, and so $Q^{\prime }\in \text{dbSAT}{}^{ℒ}$. Conversely, if $Q^{\prime }\in \text{dbSAT}{}^{ℒ}$, then there exists an instance $𝐉$ such that $Q^{\prime }(𝐉)=\top$, and so $\overline{a}\in Q(𝐉)$. Then for the repair $𝖴=(\mathrm{𝖨𝗇𝗌},\mathrm{𝖣𝖾𝗅})$ where $\mathrm{𝖨𝗇𝗌}=𝐉\setminus 𝐈$ and $\mathrm{𝖣𝖾𝗅}=𝐈\setminus 𝐉$, we have that ${𝐈}_{𝖴}=𝐉$. Hence $\overline{a}\in Q({𝐈}_{𝖴})$, and so we conclude that $⟨Q,𝐈,\overline{a}⟩\in \text{MA}{}_{}{}^{ℒ}{}_{dec}{}^{}$. $◀$

The proof of the next theorem is similar to the proof of Theorem 4.1.

All query classes mentioned in Section 2 satisfy the weak selection and projection properties, and the maps are in fact computable in time linear in the size of the query.

By Theorems 4.1 and 4.2, together with known results on the complexity of the satisfiability problems for these classes [1, 51, 35, 53]. $◀$

Since MA${}_{}{}^{ℒ}{}_{dec}{}^{}$ can be solved with an oracle for MA${}_{}{}^{ℒ}{}_{size}{}^{}$ or MA${}_{}{}^{ℒ}{}_{min}{}^{}$, Corollary 4.3 implies MA${}_{}{}^{\text{Datalog}}{}_{size}{}^{}$, MA${}_{}{}^{\text{sp-Datalog}}{}_{size}{}^{}$, MA${}_{}{}^{\text{Datalog}}{}_{min}{}^{}$, and MA${}_{}{}^{\text{sp-Datalog}}{}_{min}{}^{}$ are $\mathrm{𝐄𝐗𝐏}$-hard, while MA${}_{}{}^{\text{RA}}{}_{size}{}^{}$ and MA${}_{}{}^{\text{RA}}{}_{min}{}^{}$ are uncomputable.

We now turn to the complexity of the MA${}_{}{}^{ℒ}{}_{bound}{}^{}$ and MA${}_{}{}^{ℒ}{}_{min}{}^{}$ problems for sub-classes of UCQ_¬. For the polynomial-time cases of MA${}_{}{}^{ℒ}{}_{bound}{}^{}$, it clearly suffices to show that MA${}_{}{}^{ℒ}{}_{min}{}^{}$ can be solved in polynomial time.

To find a minimal repair for a query $Q\in \text{UCQ}$ which is the union of conjunctive queries $Q_1,\mathrm{\dots },Q_m$, it suffices to find minimal repairs ${𝖴}_i$ for each $Q_i$ and return the smallest of these. Thus we need only to show that minimal repairs for CQ_¬[sjf], SJ_¬, and SP_¬ queries can be found in polynomial time. For the first, observe that for a self-join-free conjunctive query, the body contains at most $|\mathrm{\Sigma }|$ literals. Since the schema is fixed, we can form a repair for a triple $⟨Q,𝐈,\overline{a}⟩$ with only a constant number of insertions or deletions over the domain $\overline{a}\cup \text{adom}(Q,𝐈)\cup \{c\}$, where $c$ is a fresh constant. Furthermore, the Eval${}^{\text{CQ}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}\text{[sjf]}}$ is in polynomial-time, and so we can solve MA${}_{}{}^{\text{CQ}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}\text{[sjf]}}{}_{min}{}^{}$ in polynomial-time with a brute force search of all possible repairs. The MA${}_{}{}^{\text{SJ}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}}{}_{min}{}^{}$ and MA${}_{}{}^{\text{SP}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}}{}_{min}{}^{}$ cases are similar, and their proofs can be found in the extended version of this paper [14]. $◀$

We know that UCQ_¬ has polynomially-bounded repairs (see Section 3). Hence we can solve MA${}_{}{}^{\text{UCQ}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}}{}_{size}{}^{}$ with an $\mathrm{𝐍𝐏}$ metric Turing machine as follows. Given an input $⟨Q,𝐈,\overline{a}⟩$, on each branch of the computation, we non-deterministically generate a possible update, non-deterministically generate a possible satisfying assignment, and then check if the satisfying assignment witnesses that the update is a repair with respect to $⟨Q,𝐈,\overline{a}⟩$. If yes, then we write down the size of the repair in binary and accept. Otherwise, we reject on that branch. This algorithm is clearly correct, and each branch runs in polynomial time.

For membership of MA${}_{}{}^{\text{UCQ}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}}{}_{min}{}^{}$ in ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}[O(n^2)]}$, let $⟨Q,𝐈,\overline{a}⟩$ be an input with $Q$ in UCQ_¬. We first determine the size $K$ of the optimal repair (if it exists) by a binary search, using $\mathrm{𝐍𝐏}$ queries to MA${}_{}{}^{\text{UCQ}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}}{}_{bound}{}^{}$, on the interval $[0,m]$, where $m$ is the number of literals in the rule of $Q$ with the most literals. Then, we construct an optimal repair as follows. First, we let $C$ denote a set of constants distinct from $\overline{a}\cup \text{adom}(𝐈)$ equal to the number of variables occurring in $Q$, and we initialize a partial assignment $g=\{⟨x_i,a_i⟩\mid i\le \text{len}(\overline{a})\}$. For each variable $x$ in $Q$ and each element $b$ in $\overline{a}\cup \text{adom}(D)\cup C$, we query the oracle for an answer to “does there exist a repair with respect to $⟨Q,𝐈,\overline{a}⟩$ of size $K$ where the fact that $\overline{a}\in Q(𝐈)$ is witnessed by an assignment extending $g\cup \{⟨x,b⟩\}$?” It is straightforward to see that this query is in $\mathrm{𝐍𝐏}$. Furthermore, we need only ask $O(m(|\overline{a}|+|\text{adom}(𝐈)|+m))$ queries to this oracle, which is quadratic in the size of the input. Hence MA${}_{}{}^{\text{UCQ}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_medium" style="font-size:70\%;">¬</span></sub>}}{}_{min}{}^{}$ is in ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}[O(n^2)]}$. $◀$

We now provide $\mathrm{𝐎𝐩𝐭𝐏}[\log (n)]$ and ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}[\log (n)]}$ lower bounds for MA${}_{}{}^{\text{PJ}}{}_{bound}{}^{}$ and MA${}_{}{}^{\text{PJ}}{}_{min}{}^{}$, respectively, by providing a strict and metric reduction to the minimum set cover³³3The MIN-SC problem is, given a collection $X=\{s_1,\mathrm{\dots },s_m\}$ of sets, where $U={\bigcup }_{i\le m}{s}_i$, to find a set $C\subseteq X$ such that for each $u\in U$, there exists $s\in C$ such that $u\in s$. (MIN-SC) problem. See Section 2 for the definitions of strict and metric reductions. Note that we view MA${}_{}{}^{ℒ}{}_{min}{}^{}$ as an approximation algorithm by taking repairs $𝖴$ with respect to $⟨Q,𝐈,\overline{a}⟩$ as feasible solutions for instances $⟨Q,𝐈,\overline{a}⟩$, and the size $|𝖴|$ of the repair as its cost. It is known that if there exists an approximation algorithm for MIN-SC with approximation ratio $(1-\alpha )\ln (n)$ for any $\alpha >0$, where $n$ is the size of the instance, then $𝐏=\mathrm{𝐍𝐏}$ [20]. The proof of the following theorem can be found in the extended version of this paper [14].

We conclude this section with an upper bound for MA${}_{}{}^{\text{Datalog}}{}_{min}{}^{}$. The proof can be found in the extended version of this paper [14].

Let $Q\in \text{CQ}\text{<sub class="ltx\_sub">¬</sub>}$ be an arbitrary query defined by a rule $r$ of the form

where the ${\alpha }_i$ are positive literals, the $\neg {\beta }_i$ are negative literals, the ${\gamma }_i$ are either inequality or equality atoms. Let $𝐈$ denote an arbitrary instance and $\overline{a}$ denote an arbitrary tuple over $\mathrm{𝐃𝐨𝐦}$. To ensure that $\overline{a}\in {𝐈}_{𝖴}$, we need to find a repair $𝖴$ such that for some assignment $g$ with $g(\overline{x})=\overline{a}$, we have that ${\alpha }_i[g]\in {𝐈}_{𝖴}$ for each $i\le n_1$, ${\beta }_i[g]\notin {𝐈}_{𝖴}$ for each $i\le n_2$, and the ${\gamma }_i$ equalities/inequalities are satisfied by $g$. For any assignment $g$ which satisfies the ${\gamma }_i$, the maximum number of insertions needed is $n_1$, and the maximum number of deletions needed in $n_2$. Therefore, the maximum size of any minimal repair, if one exists at all, is $n_1+n_2$. $◀$

Let $Q$ be as in the statement of the claim, and let $⟨𝐈,\overline{a}⟩$ be an input to MA${}_{}{}^Q{}_{min}{}^{}$. Let $m=\max \{\mathrm{𝐚𝐫𝐢𝐭𝐲}(R)\mid R\in \mathrm{\Sigma }\}$ and let $C=\{c_1,\mathrm{\dots },c_{m\cdot c_Q}\}$ be a set of constants disjoint from $\text{adom}(Q,𝐈)\cup \overline{a}$. We use the following claim.

Let $D$ denote the set of constants occurring in $𝖴$ which do not occur in $\text{adom}(Q,𝐈)\cup \overline{a}$. Since $𝖴$ is minimal and $Q$ admits constant-sized repairs, we have $|D|\le m\cdot c_Q$. By the $\text{adom}(Q)$-genericity of $Q$, we have that $\rho (Q({𝐈}_{𝖴}))=Q(\rho ({𝐈}_{𝖴}))$ for any bijective map $\rho :\mathrm{𝐃𝐨𝐦}\to \mathrm{𝐃𝐨𝐦}$ with ${\text{Im}}_{\rho }[D]\subseteq C$ and which fixes $\text{adom}(Q)\cup \overline{a}$ point-wise. In particular, ${𝖴}^{\prime }=\rho (𝖴)$, obtained by replacing each constant in $𝖴$ by its image under $\rho$, is also a minimal cardinality repair over $C\cup \text{adom}(Q,𝐈)\cup \overline{a}$ such that $\overline{a}\in Q({𝐈}_{{𝖴}^{\prime }})$. $\mathrm{⊲}$