Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates Benny Kimelfeld # Technion – Israel Institute of Technology Ester Livshits # Technion – Israel Institute of Technology

arXiv:2608.15328v1 [cs.DS] 15 Aug 2026

Abstract If a table violates its required set of functional dependencies (FDs), what is the minimum number of cell changes needed to restore consistency? This fundamental problem, known as finding an optimal update repair (U-repair), is known to admit polynomial-time algorithms only for a small number of specific FD sets. Whether additional tractable cases exist has remained open. The only established hardness result for this problem is due to Kolahi and Lakshmanan (2009); subsequent attempts to prove hardness for additional cases have failed, leaving these cases unresolved. In this work, we make substantial progress on this open problem by completely resolving the case of unary FDs, in which every FD has a single attribute on its left-hand side. We show that every set of unary FDs either falls into one of the previously known tractable classes or makes the problem of finding an optimal U-repair NP-hard. 2012 ACM Subject Classification Information systems → Data management systems Keywords and phrases Update repairs, functional dependencies Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23

1

Introduction

Suppose that a database violates a set of functional dependencies (FDs). How many cell values need to be changed, at minimum, to restore consistency? This question defines the problem of computing an optimal update repair (or optimal U-repair): we seek a database that satisfies the FDs and differs from the original database in as few cells as possible. Despite the elementary formulation of the problem and the central role of FDs in databases, its computational complexity is surprisingly poorly understood. As we explain later, polynomialtime algorithms are known only for a few restricted classes of FD sets, and the only established hardness result applies to a specific configuration of two FDs. Whether further tractable cases exist has remained open. This problem is a natural instance of the general framework of database repairs. Inconsistencies arise in databases for many reasons. Data may originate from noisy or imprecise sources, such as sensors, social platforms, or automatically extracted content, and may be produced by error-prone processes such as machine learning and generative Artificial Intelligence (AI). Inconsistencies can also emerge when integrating databases from different sources, which may provide conflicting information or represent the same information in incompatible ways. Arenas et al. [2] introduced a principled approach to managing such inconsistencies through the notions of repairs and consistent query answering. Given a database D that violates a collection of integrity constraints, a repair is a consistent database D′ obtained from D through a minimal collection of editing operations. Consistent query answering then seeks the query answers that hold across all repairs. The repair framework admits many variants, according to three basic choices: the integrity constraints that define consistency, the operations allowed for restoring consistency, and the criterion used to measure minimality [1]. Integrity constraints commonly include denial © CC-BY; licensed under Creative Commons License CC-BY 4.0 42nd Conference on Very Important Topics (CVIT 2016). Editors: John Q. Open and Joan R. Access; Article No. 23; pp. 23:1–23:28 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

23:2

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

constraints [6], and in particular the classical functional dependencies, as well as inclusion dependencies [3], which include referential constraints. Repair operations may consist of deleting or inserting tuples, or modifying individual cell values. Finally, minimality may be local, requiring that no proper subset of the performed operations suffices, or global, requiring minimum total cost among all ways of restoring consistency. For instance, when repairs are restricted to tuple deletions, a subset repair [4] is locally minimal, whereas a cardinality repair [14] minimizes the number of deleted tuples. Operations may also be assigned nonuniform costs, for example to reflect different levels of confidence in data items [7, 10, 14] or distance between the original and the updated values [9, 11]. We study the natural combination in which consistency is defined by FDs, repairs are obtained exclusively through value updates, and minimality is global. In the basic setting, changing a single cell has unit cost, so the objective is precisely to minimize the number of changed cells. Our results extend directly to weighted updates, where cells may have different costs. This notion was called an “optimum V-repair” by Kolahi and Lakshmanan [10], and we adapt the term “optimal U-repair” by Livshits et al. [13]. The current understanding of this optimization problem leaves a substantial gap between tractability and hardness. Livshits et al. [13] established polynomial-time algorithms for two general forms of FD sets, up to equivalence. The first is an lhs-chain, where the lefthand sides of the FDs form a chain under inclusion. The second is a matching constraint {A → B, B → A}, which we denote by A ↔ B. When all FDs are unary, these results provide tractability essentially only when the FD set reduces to a single determinant {A → X} or to a matching constraint A ↔ B. In addition, when an FD set is a union of FD sets that share no common attributes, then the two corresponding repair problems can be solved separately (hence, {A ↔ B, C ↔ D} is also tractable). The known hardness landscape is even more limited. Kolahi and Lakshmanan [10] proved NP-hardness for {A → B, B → C}. Attempts to extend hardness beyond this case have not succeeded. In particular, in their conference version, Livshits et al. [12] claimed hardness for {A ↔ B → C}; an error in the proof was subsequently discovered, as they discuss in the journal version [13]. More recently, Miao et al. [15] claimed NP-hardness for {A → C, B → C}. As we explain in Section 5.1, the proposed reduction does not establish this claim. Hence, even after restricting attention to unary FDs (i.e., FDs with a single attribute on the left-hand side), a basic question has remained unanswered: are the known polynomial-time cases isolated exceptions, or are there additional classes of unary FDs that admit efficient optimal U-repair algorithms? We answer this question completely. We prove a dichotomy for unary FDs: for every set ∆ of unary FDs, either ∆ falls, up to equivalence, within one of the previously known tractable cases, or computing an optimal U-repair with respect to ∆ is NP-hard. In particular, the previously known algorithms exhaust the tractable cases among unary FDs.

2

Preliminaries

We begin with preliminary definitions and notation. Relations. Throughout the paper, we will assume countably infinite sets Val of values and Att of attributes. A relation schema is a set R = {A1 , . . . , Ak } of attributes. An R-tuple is a function t : R → Val that maps each attribute A ∈ R to a value that we denote by t[A]. A relation r is associated with a relation schema, denoted Att(r), a finite set of tuple

Kimelfeld and Livhits

23:3

identifiers, denoted tids(r), and a mapping from tids(r) to Att(r)-tuples. We say that r is a relation over the relation schema Att(r). We denote by r[i] the tuple that r maps to the identifier i. Hence, r[i][A] is the value that tuple i has for the attribute A. ▶ Remark 1. Note that we allow duplicate tuples, since we do not assume that tuples with different identifiers are necessarily distinct. ◁ Let X be a set of attributes. We denote by πX r the projection of r onto X. Formally, πX r is the relation r′ such that Att(r′ ) = X, tids(r′ ) = tids(r), and r′ [i][A] = r[i][A] for every A ∈ Att(r) ∩ X. Observe that, under our notation, (πX r)[i] is the projection of the tuple r[i] onto X. As a shorthand, we write r[i][X] instead of (πX r)[i]. Functional dependencies. A functional dependency, or FD for short, is an expression of the form X → Y , where X and Y are finite sets of attributes. We say that X → Y is over a relation schema R if X ∪ Y ⊆ R. A relation r over a relation schema containing X ∪ Y satisfies the FD X → Y if the values of the attributes in X uniquely determine the values of the attributes in Y . That is, whenever two tuples of r agree on all attributes of X, they must also agree on all attributes of Y . More formally, r satisfies X → Y if, for all tuple identifiers i and i′ in tids(r), if r[i][X] = r[i′ ][X] then r[i][Y ] = r[i′ ][Y ]. For a set ∆ of FDs over Att(r), we denote by r |= ∆ the statement that r satisfies every FD in ∆. An FD X → Y is unary if X consists of a single attribute, and it is trivial if Y ⊆ X, in which case it is satisfied by every relation. A matching constraint is a constraint of the form X ↔ Y , which is shorthand for the pair {X → Y, Y → X}. An attribute A is a common left-hand side (common lhs) of ∆ if A occurs in the left-hand side of every FD in ∆. In our examples, we adopt the standard convention of omitting curly braces and commas when writing sets of attributes. For example, we write AB instead of {A, B}. We also use a compact notation for sets of FDs by combining multiple dependency expressions and possibly varying the direction of the arrows. For example, A ↔ B ← CD is shorthand for the set {A → B, B → A, CD → B}. The closure of a set ∆ of FDs, denoted ∆+ , is the set of all FDs implied by ∆ (equivalently, all FDs that can be derived from ∆ using Armstrong’s axioms). In particular, ∆+ contains all trivial FDs. + The closure of a finite set X of attributes with respect to ∆, denoted X∆ , is the set of + all attributes A such that X → A belongs to ∆ . Two finite sets X and Y of attributes + are equivalent (with respect to ∆) if they have the same closure, that is, if X∆ = Y∆+ (or, + equivalently, X → Y and Y → X both belong to ∆ ). By a slight abuse of notation, we say that two attributes A and B are equivalent if the singleton sets {A} and {B} are equivalent. Finally, for a set ∆ of FDs, we denote by Att(∆) the set of all attributes that appear in either the left-hand or right-hand side of an FD in ∆. Strongly Connected Components (SCCs) of attributes. When ∆ is a set of unary FDs, it is convenient to view it as a directed graph over its attributes. Since a relation satisfies ∆ if and only if it satisfies its closure ∆+ , the two induce exactly the same repair problem; we therefore define the graph over ∆+ , which is more convenient to work with. ▶ Definition 2 (FD graph). Let ∆ be a set of unary FDs over R. The FD graph of ∆, denoted G(∆) = (V, E), is the directed graph whose node set V is the set Att(∆) of attributes occurring in ∆, and in which (A, B) ∈ E if and only if A ̸= B and A → B ∈ ∆+ . The strongly connected components (SCCs) of ∆ are the sets of FDs induced by the SCCs of G(∆). Hence, the SCCs are the equivalence classes of Att(∆) under the aforementioned equivalence relation on attributes: two attributes lie in the same SCC if and only if they are

CVIT 2016

23:4

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

equivalent, that is, each determines the other. Since G(∆) is transitively closed, the SCCs are the maximal complete directed subgraphs. The weakly connected components of ∆ are the sets of FDs induced by the weakly connected components of G(∆); that is, two FDs lie in the same weakly connected component whenever their attributes are joined by a path in the undirected graph underlying G(∆). We say that ∆ is weakly connected if G(∆) consists of a single weakly connected component.

3

Optimal Update Repairs

In this section, we formally introduce the computational problem studied in this paper, that of computing an optimal update repair of an inconsistent relation. We also give an overview of the state of affairs for this problem.

3.1

Problem Definition

As is standard in the study of repairs, we measure complexity in the sense of data complexity: the relation schema R and the set ∆ of FDs are fixed, and the input consists of a single relation r over R. Updates and optimal U-repairs. Let r be a relation over a schema R. An update of r is a relation r′ over R obtained from r by modifying attribute values, without inserting or deleting tuples; formally, r′ is an update of r if tids(r′ ) = tids(r). Note that the values used in an update are not restricted to the active domain of r (the values already occurring in r); any value in Val may be used. Following prior work [10, 13], we define the distance from an update r′ to r, denoted dist(r′ , r), as the total number of cells in which r′ differs from r: X def dist(r′ , r) = {A ∈ Att(r) | r′ [i][A] ̸= r[i][A]} . i∈tids(r)

▶ Remark 3. We may also wish to capture scenarios in which modifying certain cells is more costly than modifying others. To this end, the definition of distance naturally extends to a weighted distance, in which each cell is assigned a specific update cost. For clarity of presentation, we focus on the unweighted distance defined above. However, our results immediately extend to this weighted case, as we explain in Section 7. ◁ Fix a set ∆ of FDs over R. A consistent update of r (with respect to ∆) is an update r′ of r such that r′ |= ∆. ▶ Definition 4 (Optimal update repair). An optimal update repair of r (with respect to ∆), or optimal U-repair for short, is a consistent update r′ of r that minimizes dist(r′ , r) among all consistent updates of r; that is, dist(r′ , r) ≤ dist(r′′ , r) for every update r′′ of r with r′′ |= ∆. The computational problem we study is that of producing such an optimum. Problem: Input: Goal:

Computing an optimal U-repair for (R, ∆) A relation r over R. Compute an optimal U-repair of r with respect to ∆.

Note that every pair (R, ∆) defines a separate computational problem. A straightforward observation is that R does not play any role in the complexity of this problem, as long as it

Kimelfeld and Livhits

23:5

contains all of the attributes in Att(∆). Our main result, stated formally as Theorem 5 in Section 3.3, is a complete dichotomy in the complexity of this problem for the case in which ∆ consists of unary FDs. Specifically, we classify all such ∆ into ones where an optimal U-repair can be found in polynomial time, and ones that induce an NP-hard optimization problem. To present this result, we first need to review the state of affairs for this problem.

3.2

State of Affairs

The complexity of computing optimal repairs by value updates was first studied by Kolahi and Lakshmanan [10] and later, in a systematic way, by Livshits et al. [13]. The latter work develops a rich toolbox for the problem, yet the exact tractability frontier for update repairs has remained elusive; indeed, in contrast to the full dichotomy they establish for subset repairs, the authors explicitly leave the complexity of optimal update repairs largely open. We summarize below what is known, focusing on unary FDs. Decomposition. Livshits et al. [13] establish a decomposition property: the optimal Urepair problem for ∆ can be solved by partitioning ∆ into its weakly connected components, computing an optimal U-repair for each component independently, and combining the resulting cell updates, which are guaranteed to touch pairwise disjoint sets of attributes. Consequently, the problem for ∆ is solvable in polynomial time whenever it is solvable in polynomial time for every weakly connected component of ∆; conversely, if the problem is NP-hard for even a single weakly connected component, then it is NP-hard for ∆ as a whole. Two tractable cases. Livshits et al. [13] further establish the tractability of two families of FD sets. The first consists of the chain FD sets: ∆ is a chain if its FDs can be arranged so that the left-hand side of each is contained in the left-hand side of the next. For unary FDs this criterion is restrictive: since every left-hand side is a single attribute, all FDs of a chain must share the same left-hand-side attribute, so the case collapses to ∆ having a common lhs. The second family is the matching {A → B, B → A}. Combined with the aforementioned decomposition property, this yields the following state of knowledge on the positive side: the optimal U-repair problem is in P if every weakly connected component of ∆ has a common lhs or is a matching. Known intractable case. On the negative side, the only FD set previously known to induce an NP-hard optimal U-repair problem is the directed path {A → B, B → C}, whose hardness was established by Kolahi and Lakshmanan [13]. This single intractable component, together with the decomposition property, is the extent of the known hardness landscape. Two attempts to enlarge the map of intractable cases have appeared, both of which turned out to be flawed. First, Livshits et al. [12] provided an NP-hardness argument for the FD set {A → B, B → A, B → C}, but subsequently acknowledged an error in that proof [13]. Second, Miao et al. [15] claimed NP-hardness for the FD set {A → C, B → C}; as we discuss in Section 5.1, their proof contains a flaw.

3.3

Main Result

We make a significant step toward resolving the long-standing open problem of the complexity of U-repairs: we provide a complete complexity classification of the optimal U-repair problem for the case of unary FDs. As it turns out, the two polynomial-time cases identified by Livshits et al. [13] are, in fact, the only tractable cases (assuming P ̸= NP): for unary FDs,

CVIT 2016

23:6

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

every FD set that is not captured by these two cases gives rise to an NP-hard optimal U-repair problem. Note that trivial FDs never take part in a violation and can be removed from ∆ without changing the set of consistent updates of any relation; therefore, we assume throughout that ∆ contains no trivial FDs. ▶ Theorem 5. Let ∆ be a set of nontrivial unary FDs. An optimal U-repair can be computed in polynomial time if every weakly connected component ∆′ of ∆ has a common lhs (A → X) or is a matching constraint (A ↔ B). Otherwise, computing an optimal U-repair is NP-hard. As aforesaid, the tractable side of Theorem 5, the case in which every weakly connected component has a common lhs or is a matching, has already been settled by Livshits et al. [13]. Our contribution is therefore the hardness side, which we establish for the natural decision variant of the problem: given a relation r and a budget K ∈ N, decide whether there is a consistent update r′ of r with dist(r′ , r) ≤ K.

3.4

Proof Strategy

We prove the hardness side of Theorem 5 using two main steps. In the first step, we establish the NP-hardness for several specific cases. One case is where the FD set is a single SCC with three or more attributes (Section 4). Other cases are specific FD sets involving three or four attributes (Section 5). Among the FD sets that we handle are those whose complexity has been left open following published proofs that were found flawed, as we discussed in Section 3.2; hence, this part of the proof resolves these open problems. The second part (Section 6) extends the specific cases of the first part to the general case of a set of unary FDs. We first show that whenever the FD set does not belong to the positive side of Theorem 5, there is a set of attributes, called convex, that induces one of the special cases proved hard in the first part. Finally, we show a reduction from the U-repair problem for any convex set of attributes to the original problem (involving all attributes).

4

Three or More Strongly Connected Attributes

We begin our analysis with the case of a strongly connected set of FDs (consisting of a single SCC). Recall that ∆ is strongly connected if it is a set of pairwise-equivalent attributes. We denote by ∆sc c the strongly connected FD set with c attributes. (Note that all such FD sets are equivalent.) Specifically, we assume that ∆sc c := {Ai → Aj | i, j ∈ {1, . . . , c} ∧ i ̸= j}

with

Att(∆sc c ) = {A1 , . . . , Ac } .

▶ Theorem 6. For every c ≥ 3, computing an optimal U-repair for ∆sc c is NP-hard. The proof of Theorem 6 is nontrivial, and the rest of this section sketches the proof. The complete construction and formal analysis are provided in the Appendix. Importantly, the combinatorial core of the proof lies in the case of three attributes. We establish this case by a reduction from a restricted variant of three-dimensional matching, and we then reduce it to ∆sc c for every c > 3 by padding each tuple with values that no repair within the budget can preserve. Hence, the challenge of the proof is concentrated on the case of c = 3, and it is the case that we sketch here. The fact that all attributes in ∆sc c determine one another imposes a strict structure on consistent relations. If two tuples of a relation r |= ∆sc c agree on even a single attribute Ai , then they must agree on all attributes A1 , . . . , Ac . Equivalently, every two tuples are either completely identical on A1 , . . . , Ac , or they disagree on every single one of them.

Kimelfeld and Livhits

23:7

Gadget of s = (x, y, z)

Enforcing groups

A1

A2

A3

ts

x

y

z

u1s

c1

y

z

c1

d1,2

d1,3

×N

u2s

x

c2

z

d2,1

c2

d2,3

×N

u3s

x

y

c3

d3,1

d3,2

c3

×N

Figure 1 The tuples that the reduction introduces for a triple s = (x, y, z). Each auxiliary tuple inherits two values from the S-tuple and contains a fresh constant in the remaining attribute; the dashed arrows lead to the enforcing group that anchors this constant.

Consequently, a consistent relation partitions its tuples into clusters of identical tuples. Each cluster is defined by a single target tuple v ∈ Valc shared by all its members, and the assignments of any two distinct clusters must disagree in all c coordinates. Repairing r is thus the act of assigning a target tuple v to every tuple: a tuple t modified to match v is charged one unit for each coordinate on which t and v differ (that is, c minus the number of original cells it retains). Computing an optimal U-repair for ∆sc c is therefore the problem of partitioning the tuples into these disjoint clusters and modifying each cluster to a joint v, which is unique on every attribute, while preserving as many original cells as possible. Restricted to three attributes, this clustering problem is closely related to the 3-Dimensional Matching (3DM) problem. Consider the values that occur in these three attributes as elements of three disjoint sets X, Y , and Z, so that every tuple is a triple in X × Y × Z. In 3DM, one is given such sets, each of size q, and a set S ⊆ X × Y × Z of triples, and the goal is to select a subset of S that touches every element of X ∪ Y ∪ Z exactly once; equivalently, we ask whether we can find q pairwise-disjoint triples. Our repair problem has a similar shape: a repair, too, selects a set of target triples that must be pairwise disjoint, and it pays nothing for a tuple it leaves unchanged and one unit for each cell it modifies. However, in 3DM, the chosen triples must belong to S, whereas a repair may use any triple of Val3 as a target triple. To this aim, we define a restricted form of 3DM. Restricted matching problem (R3DM). The restricted variant we reduce from, R3DM, imposes two structural conditions on the input triples of 3DM: Limited Intersection (LI): every two distinct triples share at most one element; Triangle-freeness (TF): there are no three distinct triples and three elements x, y, z such that one triple contains {x, y}, another {x, z}, and the third {y, z}. We prove in the Appendix that R3DM is still NP-complete. As we explain later, our reduction relies heavily on the LI and TF properties for correctness, specifically to show that an optimal U-repair yields a perfect matching. Reduction gadget. Next, we describe our reduction, which is illustrated in Figure 1. Fix an R3DM instance. For each triple s = (x, y, z) in the instance, we build a gadget on the three attributes, as shown in Figure 1. An S-tuple (x, y, z), that is, s itself; Three auxiliary tuples: the auxiliary tuple for a given attribute agrees with the S-tuple on the other two attributes, but contains a fresh constant in its own attribute.

CVIT 2016

23:8

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

We refer to these four tuples as the gadget tuples. Finally, to prevent fresh constants from being chosen as part of a target triple, each fresh constant is anchored by an enforcing group: a set of N identical tuples that agree with the auxiliary tuple on the fresh constant and carry, in every other attribute, a value that occurs nowhere else. We set the budget to K := 8m − 5q and the size of the enforcing groups to N := K + 1. All in all, the constructed relation r consists of the 4m tuples of the m gadgets and the 3m enforcing groups.

Correctness We first show that a perfect matching yields a U-repair. This direction is fairly simple. Given a perfect matching M ⊆ S, we use the triples of M as the target tuples, and update every gadget tuple to be equal to a target tuple that is closest to it. (In general, finding a low-cost U-repair for ∆sc c boils down to finding a good set of target tuples.) Next, we show that an in-budget U-repair yields a perfect matching. This direction is considerably more challenging. Consider a consistent update r′ of cost at most K. Every two target tuples are disjoint. We show that r′ has at least q clusters where each has a target tuple that is an S-tuple (i.e., a triple of the R3DM instance). Hence, these q target tuples form a perfect matching. To this end, we first show that the enforcing groups prevent the gadget tuples from retaining their fresh constants. Moreover, r′ has no reason to change the enforcing tuples. Therefore, the cost of r′ is the number of cells changed within the gadget tuples. We also show that there is no reason to update more than two cells in each tuple of r. Hence, the cost ct incurred by each individual gadget tuple t is at most two. For convenience, we refer to 2 − ct as the saving of t. We further refer to the saving of a cluster as the total savings of all tuples in the cluster. With zero savings, we have 4m tuples with a total cost of 8m. Since the total cost of r′ is at most K = 8m − 5q, we conclude that the total savings over all clusters are at least 5q. From here on, we analyze the different clusters of r′ according to properties of their target tuples v. There are four types: (a) No pair of values in v co-occurs in any triple of S. (b) Exactly one pair in v co-occurs in a triple of S. (c) Exactly two pairs in v co-occur in triples of S. (d) v is an S-tuple. Due to the TF property, these types are pairwise disjoint, and they cover all possibilities of clusters of r′ . We show a bound on the savings of each cluster, according to its type. A numerical analysis then shows that, to reach the savings of 5q (or more), there can be no clusters of type (a)-(c), and there are precisely q clusters of type (d). As aforesaid, the corresponding q target tuples form a perfect matching, as required.

Beyond three attributes. To extend this construction to relations of arity c, we select three arbitrary attributes to carry the R3DM gadgets and their matching logic. For each of the remaining c − 3 attributes, we assign a unique fresh constant to every tuple, and guard this constant with a dedicated enforcing group. This forces every consistent update within the budget to modify all values in these additional attributes, at a fixed, uniform cost. Since this extra cost is independent of the other choices, it merely shifts the budget by a constant, leaving the equivalence with the existence of a perfect matching unaffected.

Kimelfeld and Livhits

5

23:9

Case Analysis for Small SCCs

Theorem 6 settles the FD sets that are strongly connected and have three or more attributes. In this section, we turn to the FD sets in which every SCC of G(∆) consists of one or two attributes. An SCC of a single attribute induces no nontrivial FDs at all, and an SCC of two attributes A and B induces the matching constraint A ↔ B, which is one of the two tractable cases of Theorem 5. Hence, unlike the situation of Section 4, intractability can no longer originate in a single SCC; it can arise only from the way in which several SCCs are combined, that is, from the FDs that hold between attributes of distinct SCCs. The FD sets that neither section covers, namely those that have an SCC of three or more attributes without being strongly connected themselves, are handled in Section 6, where we show that an FD set inherits the hardness of a convex subset and, in particular, that of any of its SCCs. We establish hardness for the following combinations of small SCCs: A → B → C: three single-attribute SCCs forming a directed path; A → B ← C: two single-attribute SCCs that determine a third; A ↔ B → C: a matching constraint that determines a single attribute; A → B ↔ C: a single attribute that determines a matching constraint; A ↔ B → C ↔ D: a matching constraint that determines another matching constraint. The first combination, the directed path, is already known to be intractable [10], as discussed in Section 3.2, so we prove hardness for the remaining four. We give the full proof for A → B ← C; for the other three, we give only a proof sketch here, and the complete construction and formal analysis are provided in the appendix.

5.1

Hardness of A → B ← C

We begin with A → B ← C, that is, the FD set {A → B, C → B}, in which two independent attributes determine a third. As mentioned in Section 3.2, Miao et al. [15] have already claimed that this FD set is intractable. They give two arguments, and we begin by explaining why each of them is flawed. The first argument is based on the conflict hypergraph of a relation r: the vertices are the cells of r, and the hyperedges are the sets of cells that jointly witness a violation of an FD of ∆. The authors construct a reduction from the optimal U-repair problem to minimum vertex cover over conflict hypergraphs, and intractability is then deduced from the NP-hardness of the latter. This deduction reverses the direction of the reduction. Observe also that the hardness argument is stated for every ∆ that contains two FDs X → C and Y → C with X = ̸ Y , and in this generality it cannot hold (unless P = NP): the FD set {A → C, AB → C} satisfies this condition, yet its left-hand sides form a chain, since A ⊆ AB, and so an optimal U-repair for it can be computed in polynomial time [13]. The second argument is a direct reduction from Max NM-E3SAT, the problem of satisfying as many clauses as possible of a 3CNF formula φ in which every clause consists of either three positive literals or three negative literals. Given such a formula with m clauses, the constructed relation over {A, B, C} contains, for every clause c and every variable x occurring in c, the tuple (c, 1, x) if x occurs positively in c, and the tuple (c, 0, x) if it occurs negatively. The analysis concludes that the minimum cost of a consistent update of this relation is precisely 3m − s, where s is the maximum number of clauses of φ that a single assignment satisfies; as s ≤ m, this cost is at least 2m. The conclusion is false. Setting the B-value of every tuple to 1 makes the B-column constant and, therefore, already produces a consistent relation; its cost is the number of tuples that carry 0, that is, three times the

CVIT 2016

23:10

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

number of all-negative clauses. Symmetrically, setting every B-value to 0 costs three times the number of all-positive clauses. One of the two is of cost at most 3m/2, which is strictly below the claimed minimum. We now establish the hardness of A → B ← C. ▶ Proposition 7. Computing an optimal U-repair for A → B ← C is NP-hard. Proof. We reduce from the multiway-cut problem with three terminals on bipartite graphs. Let G = (U, W, E) be a bipartite graph with sides U and W , and let S = {s1 , s2 , s3 } ⊆ U ∪ W be three distinct terminals. A multiway cut of (G, S) is a set E ′ ⊆ E such that no two terminals are connected in the graph obtained from G by deleting the edges of E ′ . Deciding whether (G, S) has a multiway cut of size at most k is NP-complete already for three terminals [5]. It remains NP-complete on bipartite graphs: subdividing every edge once (i.e., replacing each edge u − v by a path u − xuv − v through a new vertex xuv ) makes the graph bipartite, changes neither the terminals nor the minimum size of a multiway cut, and preserves NP-completeness [8]. Construction. Let (G, S, k) be such an instance, with G bipartite, and denote m = |E| and n = |U | + |W |. We may assume that k ≤ m, since otherwise E itself is a multiway cut of size at most k. We construct a relation r, as illustrated in Figure 2, over {A, B, C} and a budget Kr , writing a tuple as a triple (a, b, c) that lists its values for A, B and C. The attribute B holds one of three colors 1, 2 and 3, one for each terminal. We set H := 2k + 1. The relation r consists of the following tuples. Anchors. If v ∈ U ∪ W and b ∈ {1, 2, 3}, then we call the tuple (v, b, v) an anchor of v. We add to r: H anchors for every vertex v and color i ∈ {1, 2, 3} (hence, 3H tuples in total for v). Additional H anchors (si , i, si ) for every terminal si ∈ {s1 , s2 , s3 }. Edge gadgets. For every edge {u, w} ∈ E with u ∈ U and w ∈ W , the relation contains the three tuples (u, 1, w), (u, 2, w) and (u, 3, w). The FD set ∆ requires that, whenever two tuples agree on A or on C, they should also agree on the color in B. Hence, the multiplicity of colors is what causes the violations in r. Finally, we set Kr := 2nH +2m+2k. Both r and Kr are clearly computable in polynomial time. We need to show that (G, S) has a multiway cut of size at most k if and only if r has a consistent update r′ with dist(r′ , r) ≤ Kr . From a multiway cut to a consistent update. Let E ′ be a multiway cut of (G, S) with |E ′ | ≤ k. Every connected component of the graph G′ = (U ∪ W, E \ E ′ ) contains at most one terminal, so we obtain a coloring λ : U ∪ W → {1, 2, 3} by setting λ(v) = i if the component of v contains si , and λ(v) = 1 if it contains no terminal. In particular, λ(si ) = i, and λ(u) = λ(w) for every remaining edge {u, w} ∈ E \ E ′ . We construct r′ as follows. For every vertex v, we change to λ(v) the color of every anchor of v whose color differs from λ(v). A vertex v ∈ / S has 2H such anchors that we update, and so does a terminal si , since λ(si ) = i and there are 2H anchors of si of the other two colors. The anchors therefore cost 2nH in total. Next, consider the gadget of an edge {u, w}. If λ(u) = λ(w), then we change to λ(u) the color of the two tuples of the gadget whose color differs from λ(u); the gadget becomes three copies of (u, λ(u), w), at a cost of 2. If λ(u) ̸= λ(w), then the edge {u, v} is necessarily one of the removed tuples in E ′ . We replace the C-value of the tuple of color λ(u) with a fresh value, we replace the A-value of the tuple of color λ(w) with a fresh value, and we replace both the A-value and the

Kimelfeld and Livhits

23:11

Anchors of v A B C

Anchors of w = s1 A B C

v

1

v

×H

u

1

u

×H

w

1

w

×2H

v

2

v

×H

u

2

u

×H

w

2

w

×H

v

3

v

×H

u

3

u

×H

w

3

w

×H

The path v − u − w

u

U

W

Anchors of u A B C

v

w

Gadget of {u, v}

Gadget of {u, w}

u

1

v

u

1

w

u

2

v

u

2

w

u

3

v

u

3

w

Figure 2 The tuples that the reduction constructs for a path v − u − w of G, where u ∈ U , v, w ∈ W , and w is the terminal s1 .

C-value of the third tuple with fresh values, where every fresh value is used in a single cell of r′ . The cost is 1 + 1 + 2 = 4. Thus, every edge incurs a cost of 2, and each edge in E ′ may incur 2 more. Since |E ′ | ≤ k, we conclude that the total cost for updates in the edge gadgets is at most 2m + 2k. We conclude that dist(r′ , r) ≤ 2nH + 2m + 2k = Kr , as required. It remains to show that r′ |= {A → B, C → B}. Let a be a value that occurs in the A-column of r′ . If a = v for a vertex v ∈ U ∪ W , then the tuples with A = v are the anchors of v together with the tuples of gadgets of edges incident to v that retained their A-value, and all of them have the color λ(v). Every other value of the A-column is fresh and occurs in a single tuple. Hence, r′ |= A → B. The argument for C → B is symmetric. From a consistent update to a multiway cut. Let r′ be a consistent update of r with dist(r′ , r) ≤ Kr . We say that a tuple of r′ is attached to a vertex u ∈ U if its A-value is u, and that it is attached to a vertex w ∈ W if its C-value is w. Since r′ |= A → B and r′ |= C → B, all the tuples that are attached to a vertex v agree on their B-value; we denote this value by λ(v). If no tuple is attached to a node v, then we let λ(v) be a value that is not a color, say ⋄. We first bound the cost of the anchors. If an anchor of v is unchanged in r′ , then it is attached to v, and its color is λ(v). Consequently, the anchors of v contribute to dist(r′ , r) at least the number of anchors of v whose color differs from λ(v). This number is: 2H if v ∈ / S and λ(v) is a color, or v ∈ S is the terminal si and λ(v) = i. 3H or more in every other case, that is, λ(v) = ⋄ or v = si and λ(v) ̸= i. Summing over the n vertices, the anchors cost at least 2nH, and at least 2nH + H if some vertex v has a λ(v) that is not a color or some terminal si has λ(si ) ̸= i. We now bound the cost of the edge gadgets. The three tuples of the gadget of {u, w} agree on A and on C but have distinct colors, so at most one of them is unchanged in r′ , and the gadget costs at least 2. Therefore, the edge gadgets contribute at least 2m to the cost. Hence, the anchors and the gadgets cost at least 2nH + 2m altogether, which leaves a slack of Kr − (2nH + 2m) = 2k. Since H = 2k + 1, the additional cost of H identified above exceeds this slack, and it follows that λ maps every vertex to a color and that λ(si ) = i for i = 1, 2, 3. In particular, every vertex has at least one attached tuple in r′ , since otherwise its λ-value would not be a color.

CVIT 2016

23:12

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

Let E ′ be the set of the edges {u, w} ∈ E with λ(u) ̸= λ(w). We claim that the gadget of such an edge costs at least 4. No tuple of r′ has both A = u and C = w, since its color would then be both λ(u) and λ(w); therefore, each of the three tuples of the gadget changes its A-value or its C-value. Moreover, the tuple t whose color is neither λ(u) nor λ(w) changes at least two cells: if t retains A = u, then it changes its color to λ(u) and, in addition, its C-value; if t retains C = w, then it changes its color to λ(w) and, in addition, its A-value; and if t retains neither, then it changes both its A-value and its C-value. We conclude that dist(r′ , r) ≥ 2nH +2m+2|E ′ |, and |E ′ | ≤ k follows from dist(r′ , r) ≤ Kr . Finally, E ′ is a multiway cut of (G, S): the endpoints of every edge of E \ E ′ have the same color, hence every connected component of (U ∪ W, E \ E ′ ) is monochromatic, whereas the terminals have pairwise distinct colors (i.e., λ(si ) = i). ◀

5.2

Remaining Proofs

We now turn to the three remaining combinations, describing for each of them the construction and the idea behind its analysis. ▶ Proposition 8. Computing an optimal U-repair for A ↔ B → C is NP-hard. Proof. (Sketch) We reduce from Vertex Cover. Let G = (V, E) be a graph and let k ≤ |V | be a bound on the size of a vertex cover. We set L := |V | + 1 and M := L|E| + |V | + 1, and we construct a relation r over {A, B, C} that consists of: The anchors of every vertex v ∈ V , consisting of M + 1 copies of the tuple (v, v, 0) and M copies of (v, v, 1); An edge gadget of L copies of (u, v, 1) for every edge {u, v} ∈ E. (We select an arbitrary ordering (u, v) between the nodes.) The budget is Kr := M |V | + L|E| + k. Given a vertex cover S of size at most k, we construct a repair by changing every anchor (v, v, 0) to (v, v, 1) if v ∈ S (cost M |S| + |S|), changing every anchor (v, v, 1) to (v, v, 0) if v∈ / S (cost M (|V | − |S|)), and changing every edge gadget (u, v, 1) to (u, u, 1) or (v, v, 1), depending on whether u or v is in S (cost L|E|). All in all, the cost is M |V |+L|E|+|S| ≤ Kr . Now suppose that we are given a repair of cost at most Kr . Since A ↔ B, the pairs of A-values and B-values that occur in a consistent relation form a partial bijection. The anchors of v all carry the pair (v, v) and split into a group of M + 1 tuples with C = 0 and a group of M tuples with C = 1, violating B → C. Hence, we must modify at least one cell in every tuple of one of them, at a cost of at least M per vertex. The budget is M |V | + L|E| + k, so this leaves a slack of L|E| + k. Pulling the two groups apart is expensive: a group can be separated only by changing both its A-value and its B-value, since changing one of the two alone collides with the group that stays, and this costs at least 2M . As M exceeds the entire slack, no repair can afford it, and every vertex must instead unify its anchors on a single value cv ∈ {0, 1} of C, at a cost of M if cv = 0 and of M + 1 if cv = 1. The anchors therefore cost precisely |V |M + |S|, where S := {v ∈ V | cv = 1} is the intended vertex cover. The edge gadgets test whether S covers E. A tuple (u, v, 1) cannot retain both A = u and B = v, since the anchors bind u to the pair (u, u) and v to the pair (v, v); it must join the cluster of u or the cluster of v. Joining that of u amounts to changing its B-value, and it changes nothing else exactly when cu = 1, and symmetrically for v. Hence, an edge costs L if at least one of its endpoints belongs to S, and at least 2L otherwise. Since L > k, the budget admits no uncovered edge, and it leaves |S| ≤ k. ◀

Kimelfeld and Livhits

23:13

▶ Proposition 9. Computing an optimal U-repair for A → B ↔ C is NP-hard. Proof. (Sketch) We reduce from 3SAT, assuming that every clause consists of three literals over three distinct variables. Let φ be a formula with variable set V and m clauses, and set L := 4m + 1. With every variable v we associate two fresh values Tv and Fv , one for each truth value. The constructed relation over {A, B, C} consists of a variable gadget for every variable v, namely L copies of (v, v, Tv ) and L copies of (v, v, Fv ), and a clause gadget for every clause c = (ℓ1 ∨ ℓ2 ∨ ℓ3 ) over the variables v1 , v2 , v3 , namely the three tuples: (c, v1 , w3 )

(c, v2 , w1 )

(c, v3 , w2 )

Here, wi is the value of vi that satisfies ℓi , that is, Tvi if ℓi is positive and Fvi if ℓi is negative. Note that the indices in a clause gadget are shifted: v1 , v2 and v3 coincide with w3 , w1 and w2 , respectively. For example, if c is x ∨ y ∨ ¬z, then the three tuples are: (c, x, Fz )

(c, y, Tx )

(c, z, Ty )

The budget is K := L|V | + 4m. The proof shows how a satisfying assignment can yield a repair that costs L on each variable gadget (changing the truth values according to the assignment) and 4 for each clause gadget. For the other direction, we show that with a budget of K, the variable gadgets must define an assignment τ as in the first direction, and each clause must spend precisely 4 updates, implying that it retains at least one of its satisfying wi ’s, which is delivered by the assignment τ . ◀ ▶ Proposition 10. Computing an optimal U-repair for A ↔ B → C ↔ D is NP-hard. Proof. (Sketch) We reduce from A ↔ B → C, which is the FD set of Proposition 8 and consists of the first three attributes of A ↔ B → C ↔ D. Let r be a relation over {A, B, C} with n tuples, let K be a budget, and set N := K + n + 1. We construct a relation r′ over {A, B, C, D} that consists of: A main tuple for every tuple of r, which copies its A-, B-, and C-values and uses a fresh value in the new attribute D, called the private value of the tuple; An enforcing group of N identical tuples for every fresh value d, using the value d in D and, in each of A, B and C, a value that occurs nowhere else. The budget is K + n. Given a consistent update s of r of cost at most K, we construct a consistent update of r′ of cost at most K + n: we leave the enforcing groups unchanged, we modify the A-, B- and C-cells of the main tuples as s does, at a cost of at most K, and we give the main tuples that share a C-value in s a common fresh D-value, which satisfies C ↔ D at the price of one cell per tuple of r. Since these D-values are fresh, no main tuple shares a value with an enforcing group in any attribute. Now suppose that we are given a consistent update of r′ of cost at most K + n. As N exceeds the budget, every enforcing group retains an unchanged copy. We may assume that no main tuple agrees with an enforcing tuple on C (equivalently, on D). Indeed, consider a group of main tuples that have been updated to the same (a, b, c, d), where (c, d) is the pair of an enforcing tuple. All of them have changed their C-value, since c occurs nowhere in r, and at most one of them retains its original D-value. We take the original C-value c′ of one of them, and we pair it with the D-value already used for c′ in the update, if c′ already occurs, or with a fresh D-value otherwise. We replace all of their pairs (c, d) by this pair (c′ , d′ ). If they also carry the A- and B-values of the enforcing tuple, then they have all been

CVIT 2016

23:14

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

updated, and we replace them by a fresh pair; this does not increase the cost since these cells were already changed. One C-cell is then restored and at most one extra D-cell is changed, so the cost does not increase. Repeating for every such group, we get a repair of r′ where no main tuple agrees with an enforcing tuple on D. It follows that no main tuple retains its private value, since it would then agree with its own enforcing tuple on D. The update therefore modifies all the D-cells of the main tuples and at most K cells on A, B and C, and their restriction to A, B and C is an update of r of cost at most K, which is consistent since A ↔ B → C is implied by A ↔ B → C ↔ D. ◀

6

Generalization via Hard Convex Sets

We now generalize the hardness results of the specific cases from the previous sections to the full hardness side of Theorem 5, thus completing the proof of the theorem. For the rest of this section, we fix a set ∆ of unary FDs. For a set S of attributes, we denote by ∆S the FD set that S induces, that is, the set of all FDs in ∆+ that use only attributes in S. The generalization goes as follows. We first define the notion of a convex set S of attributes with respect to ∆. Second, we show that for each convex set S of ∆, there is a reduction from computing an optimal U-repair for ∆S to computing an optimal U-repair for ∆. Third, we show that if ∆ is in the hardness side of Theorem 5, then at least one of its convex sets S induces one of the hard special cases ∆S of the previous sections. We begin with the definition of convexity. ▶ Definition 11 (Convexity). A subset S of attr(∆) is said to be convex ( w.r.t. ∆) if for every three attributes A, B and C with A → B → C ∈ ∆+ , if A ∈ S and C ∈ S then B ∈ S. As an example, consider ∆ = {A → B, B → C, A → D, D → C}. Then S = {A, B, C} is not convex, since we have A → D → C ∈ ∆+ and both A and C are in S, but D is not. On the other hand, the sets {A}, {A, B} and {A, B, D} are all convex. Also, convexity is closely related to strong connectivity: ▶ Observation 12. The following hold. 1. Every SCC is convex. 2. Every convex set is the union of SCCs (but a union of SCCs is not necessarily convex). We prove the following: ▶ Lemma 13 (Reduction from a convex set). Let ∆ be a set of unary FDs, and let S ⊆ attr(∆) be a convex set of attributes. There is a polynomial-time cost-preserving reduction from computing an optimal U-repair for ∆S to computing an optimal U-repair for ∆. Proof. We fix a constant ⋄ in Val that we use throughout the proof. An attribute B ∈ R \ S is said to be determined by S if A → B ∈ ∆+ for some A ∈ S. Given a relation s over S, we construct a relation r over R = (∆) with tids(s) = tids(r) by setting, for every i ∈ tids(r): r[i][A] = s[i][A] for each attribute A ∈ S; r[i][B] = ⋄ for each attribute B determined by S; r[i][C] is a fresh new value for each attribute that is neither in S nor determined by S. The construction is correct in the sense that to repair r, it is necessary and sufficient to repair the projection of r to S, namely s. Hence, a U-repair for r yields a U-repair (of the same or smaller cost) for s, and a U-repair for s yields a U-repair (of the same cost) for r.

Kimelfeld and Livhits

23:15

We prove correctness as follows. Let i and j be identifiers in tids(r). We need to show that every FD A → B violated by {r[i], r[j]} is such that both A and B are in S (hence, ∆S |= A → B). Thus, it suffices to show that if either A ∈ / S or B ∈ / S, then the FD A → B is satisfied, regardless of the content of s. (In particular, it continues to be satisfied even if s is updated.) We consider several cases. 1. If B ∈ S, then A ∈ / S and A cannot be determined by S, or otherwise A would need to be in S since we assume that S is convex. Therefore, the rows disagree on A because r[i][A] and r[j][A] are fresh new values (by construction). 2. If B is determined by S, then the rows agree on B, since r[i][B] = r[j][B] = ⋄. 3. If B is neither in S nor determined by S, then A is also neither in S nor determined by S, or otherwise A → B would imply that B is determined by S. Hence, the rows disagree on A as in the first case. In each of the three cases, the FD A → B is satisfied, as claimed.

◀

From Observation 12 and Lemma 13, we immediately conclude that it is NP-hard to compute an optimal U-repair for ∆ if it is NP-hard for at least one SCC of ∆. The other direction, however, is false (assuming P = ̸ NP), as evident from the hardness of A → B → C, where each SCC consists of a single attribute. Finally, we show that the hard cases of the previous sections are exhaustive, in the sense that every FD set on the hardness side of Theorem 5 has a convex set of attributes that induces one of them. This, together with Lemma 13, completes the proof of Theorem 5. ▶ Lemma 14 (Existence of a hard convex set). Let ∆ be a set of nontrivial unary FDs that does not fall in the tractable side of Theorem 5. Then ∆ has a convex set S of attributes such that, up to a renaming of the attributes, ∆S is one of the FD sets A → B → C, A → B ← C, A ↔ B → C, A → B ↔ C, A ↔ B → C ↔ D, and ∆Kc for some c ≥ 3. Proof. Without loss of generality, we assume that ∆ is weakly connected. Otherwise, we apply the proof to a weakly connected component of ∆ where the tractability condition is violated. Clearly, an attribute set that is convex w.r.t. a weakly connected component of ∆ is also convex w.r.t. ∆. We use the SCC DAG of ∆: its nodes are the SCCs of ∆, and it has an edge from a node P to a node Q whenever P ̸= Q and the attributes of P determine those of Q. Note that the SCC DAG is connected, since we assume that ∆ is weakly connected. We write P ≺ Q to state that the SCC DAG has an edge from P to Q. Note that ≺ is transitive, asymmetric, and irreflexive, hence a strict partial order. In particular, every nonempty set of SCCs has a ≺-minimal member and a ≺-maximal member. We say that a node R is between P and Q if P ≺ R ≺ Q. Note that a union of SCCs is convex if and only if no SCC outside the union is between two SCCs in the union. Indeed, if ∆ |= A → B → C and A and C belong to the union, then the SCC of B is either that of A or C, or between them (hence, in the union). Since ∆ violates the condition of Theorem 5, it has at least three attributes. We consider three cases, according to the maximal number of attributes in an SCC of ∆. Case 1: Some SCC P has three or more attributes. By Observation 12, the set P is convex, and ∆P is ∆Kc for c = |P | ≥ 3. Case 2: The maximal number of attributes in an SCC is two. Let P be an SCC with two attributes, denoted A and B. Then ∆P is A ↔ B.

CVIT 2016

23:16

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

Suppose first that P ≺ Q′ for some SCC Q′ . Let Q be a ≺-minimal member of the set of nodes Q′ with P ≺ Q′ . The set S := P ∪ Q is convex: a node between P and Q would belong to the set from which we chose Q and would precede Q, contradicting the minimality of Q. If Q consists of a single attribute C, then ∆S is A ↔ B → C. If Q consists of two attributes C and D, then ∆S is A ↔ B → C ↔ D. If Q′ ≺ P for some SCC Q′ , then we select Q as a ≺-maximal member of the set of the nodes Q′ with Q′ ≺ P . The set S := P ∪ Q is again convex. If Q consists of a single attribute C, then ∆S is C → A ↔ B. If Q consists of two attributes C and D, then ∆S is C ↔ D → A ↔ B. Case 3: Every SCC has a single attribute. In this case, the SCC DAG is the same as G(∆), identifying each singleton with its single member. Hence, G(∆) is acyclic and weakly connected. Fix a topological order over the attributes. We first claim that at least one attribute C has two or more incoming edges. Let A′ be the first (leftmost) node in the topological order. If A′ has an outgoing edge to every other attribute, then at least one neighbor C of A′ has an incoming edge from an attribute that is not A′ , or else ∆ would be equivalent to A′ → X (satisfying the tractability condition). Otherwise, if A′ does not have an outgoing edge to every other attribute, then at least one neighbor C of A′ has an incoming edge from an attribute that is not A′ , since G(∆) is connected and transitively closed. This proves the claim. Choose an arbitrary node C with two or more incoming edges in G(∆). Let B be the rightmost attribute in the topological order with an edge to C. Let A be the rightmost attribute, different from B, with an edge to C. Let S = {A, B, C}. Hence, the FD set ∆S is either A → B → C or A → C ← B, depending on whether A → B or not. To complete the proof, we need to show that S is convex. This holds due to the choice of B and A as rightmost attributes: if D ∈ / S is such that if B → D → C, then D should have been chosen instead of B; and if A → D → B or A → D → C, then D should have been chosen instead of A. ◀ With Lemma 14, we have now completed the proof of Theorem 5.

7

Conclusions

We have established a complete complexity classification for computing optimal U-repairs under unary FDs. Our result shows that the previously known tractable cases are exhaustive: an optimal U-repair can be computed in polynomial time when every weakly connected component of the FD set has a common lhs or is a matching constraint, and the problem is NP-hard in every other case. Thus, for unary FDs, the boundary between tractability and intractability is now fully understood. We note that the tractable cases remain tractable even if every cell has an individual weight that determines its cost of update [13]. Since our results show that these are the only tractable cases even without weights, we conclude that the dichotomy trivially extends to the weighted case. The main question left open is whether a similar classification can be obtained for arbitrary FDs. The unary case already exhibits a rich interaction between the structure of the dependencies and the complexity of repairing the data, and several of our hardness arguments rely on phenomena that extend beyond unary FDs. It would be interesting

Kimelfeld and Livhits

23:17

to understand whether these techniques, together with the tractability tools developed in previous work, can lead to a complete dichotomy for optimal U-repairs under general FD sets. References 1 2 3 4 5

6 7

8

9

10

11 12 13 14

15

A

Foto N. Afrati and Phokion G. Kolaitis. Repair checking in inconsistent databases: algorithms and complexity. In ICDT, pages 31–41. ACM, 2009. Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In PODS, pages 68–79. ACM, 1999. Marco A. Casanova, Ronald Fagin, and Christos H. Papadimitriou. Inclusion dependencies and their interaction with functional dependencies. J. Comput. Syst. Sci., 28(1):29–59, 1984. Jan Chomicki and Jerzy Marcinkowski. Minimal-change integrity maintenance using tuple deletions. Inf. Comput., 197(1-2):90–121, 2005. E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23(4):864–894, 1994. doi:10.1137/S0097539792225297. Terry Gaasterland, Parke Godfrey, and Jack Minker. An overview of cooperative answering. J. Intell. Inf. Syst., 1(2):123–157, 1992. Amir Gilad, Aviram Imber, and Benny Kimelfeld. The consistency of probabilistic databases with independent cells. In ICDT, volume 255 of LIPIcs, pages 22:1–22:19. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2023. Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs. In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl – LeibnizZentrum für Informatik. Youri Kaminsky, Benny Kimelfeld, Ester Livshits, Felix Naumann, and David Wajc. Repairing databases over metric spaces with coincidence constraints. In ICDT, volume 328 of LIPIcs, pages 14:1–14:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. Solmaz Kolahi and Laks V. S. Lakshmanan. On approximating optimum repairs for functional dependency violations. In ICDT, volume 361 of ACM International Conference Proceeding Series, pages 53–62. ACM, 2009. Nick Koudas, Avishek Saha, Divesh Srivastava, and Suresh Venkatasubramanian. Metric functional dependencies. In ICDE, pages 1275–1278. IEEE Computer Society, 2009. Ester Livshits, Benny Kimelfeld, and Sudeepa Roy. Computing optimal repairs for functional dependencies. In PODS, pages 225–237. ACM, 2018. Ester Livshits, Benny Kimelfeld, and Sudeepa Roy. Computing optimal repairs for functional dependencies. ACM Trans. Database Syst., 45(1):4:1–4:46, 2020. Andrei Lopatenko and Leopoldo E. Bertossi. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In ICDT, pages 179–193, 2007. Dongjing Miao, Pengfei Zhang, Jianzhong Li, Ye Wang, and Zhipeng Cai. Approximation and inapproximability results on computing optimal repairs. VLDB J., 32(1):173–197, 2023.

Subset Repairs versus Update Repairs

It is instructive to contrast the situation with that of subset repairs, which are obtained by deleting a minimum number of tuples rather than by updating cells. For subset repairs, Livshits et al. [13] obtained a complete dichotomy: for every set of FDs, computing an optimal subset repair is either solvable in polynomial time or NP-hard (in fact, APX-complete).

CVIT 2016

23:18

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

Their hardness argument proceeds in two steps. First, they establish hardness directly for a small collection of “core” FD sets, each by a reduction from a well-known NP-hard problem. Second, they lift this hardness to every remaining intractable FD set by means of fact-wise reductions: a fact-wise reduction maps each tuple of a relation over one schema to a tuple of a relation over another schema in a way that preserves both consistency and inconsistency. Such a map induces a one-to-one correspondence between the subset repairs of the source relation and those of the target, and hardness therefore transfers immediately from the core sets to all others. This machinery is unavailable for update repairs, which is a central reason the updaterepair picture has remained so much coarser. A fact-wise reduction relates two relations over possibly different schemas, and in order to encode the source dependencies it typically represents the value of a single source attribute using several attributes of the target relation, so that one source value determines several target values. Two obstacles then arise. First, a single cell update in the source relation forces an entire group of cell updates in the target relation, and the size of this group may differ from one source attribute to another. The number of modified target cells is therefore not a fixed multiple of the number of modified source cells, so the reduction cannot preserve repair cost up to a fixed factor, and the tight, cost-preserving correspondence on which the subset-repair argument relies already fails. Second, and more fundamentally, the correspondence breaks down in the reverse direction. An update repair of the target relation is under no obligation to respect these groups: it may modify the target cells that are determined by a single source cell inconsistently, changing some of them but not others, or changing them to values that no longer agree. Such a target repair reflects no update of the source relation at all, since there each cell is atomic and is either left unchanged or updated as a whole. There is thus no faithful way to translate an optimal update repair of the target relation back into one of the source relation of comparable cost, and the fine-grained, cell-level cost accounting that defines an optimal update repair is not preserved. For these reasons, hardness cannot simply be transported from a handful of core FD sets to all the rest by means of fact-wise reductions, and different machinery is required.

B

Missing Proofs of Section 4

This section proves Theorem 6: for every c ≥ 3, computing an optimal U-repair for ∆sc c is NP-hard. The proof consists of three steps. We first show that R3DM, the restricted variant of three-dimensional matching from which we reduce, is NP-complete (Lemma 15). We then reduce R3DM to our problem for three attributes (Lemma 16). Finally, we reduce the problem for three attributes to the problem for c attributes, for every c > 3 (Lemma 17). Throughout, we specify a tuple by listing its values for A1 , . . . , Ac in this order.

B.1

Hardness of R3DM

We first prove that the restricted matching problem that we reduce from is intractable. Recall that an instance of R3DM consists of three disjoint sets X, Y and Z of size q and a set S ⊆ X × Y × Z of triples that satisfies the two conditions LI and TF, and that the goal is to decide whether S has a perfect matching, that is, q pairwise disjoint triples. ▶ Lemma 15. R3DM is NP-complete. Proof. Membership in NP is clear, so we prove hardness by a reduction from 3DM. Let (X, Y, Z, S) be an instance of 3DM, where |X| = |Y | = |Z| = q and |S| = m. For every

Kimelfeld and Livhits

23:19

triple s = (x, y, z) ∈ S we introduce six fresh elements, namely as1 and as2 that we add to X, bs1 and bs2 that we add to Y , and cs1 and cs2 that we add to Z; these 6m elements are distinct from one another and from the elements of X ∪ Y ∪ Z. We call them the internal elements of s and the elements of X ∪ Y ∪ Z the original ones. We replace s by the gadget Gs that consists of the five triples σ1s = (x, bs1 , cs1 ),

σ2s = (as1 , y, cs2 ),

σ3s = (as2 , bs2 , z),

σ4s = (as1 , bs2 , cs1 ),

σ5s = (as2 , bs1 , cs2 ).

The three sides of the constructed instance are of size q + 2m each, the constructed set Ŝ of triples is of size 5m, and a perfect matching consists of q + 2m triples. The construction is clearly in polynomial time. Next, we show that Ŝ satisfies LI and TF. We use two properties of the construction. First, every triple of Ŝ contains at most one original element, since σ1s , σ2s and σ3s contain one each and σ4s and σ5s contain none. Second, the internal elements of s are introduced for s alone, so they occur only in the triples of Gs . For LI, consider two distinct triples of Ŝ. If they belong to distinct gadgets, then, by the second property, every element that they share is original, and, by the first, each of them has at most one such element; hence, they share at most one element. If they belong to the same gadget Gs , then a direct inspection of the five triples above shows that they share at most one element; the inspection also shows that they share an element precisely when one of them is σ1s , σ2s or σ3s and the other is σ4s or σ5s . For TF, suppose that Ŝ contains three distinct triples t1 , t2 and t3 and three distinct elements u, v and w such that u, v ∈ t1 , u, w ∈ t2 and v, w ∈ t3 . Every one of the three triples contains two of the three elements, so at most one of u, v and w is original: if two of them were, then some triple would contain both, contradicting the first property. At least two of the elements are therefore internal, say u and v. By the second property, t1 and t2 belong to the same gadget, since they share the internal element u, and so do t1 and t3 , since they share the internal element v; thus, all three belong to a single gadget Gs . This is impossible: by the inspection above, no two of σ1s , σ2s and σ3s share an element and neither do σ4s and σ5s , so among any three triples of Gs there are two that share no element. Now, given a perfect matching of S, we construct one of Ŝ. Let M ⊆ S be a perfect matching of the original instance, so |M | = q. We select the triples σ1s , σ2s and σ3s for every s ∈ M , and the triples σ4s and σ5s for every s ∈ S \ M . Each of the two selections covers the six internal elements of Gs exactly once, and the first covers, in addition, the three original elements of s. Since M is a perfect matching, every original element is covered exactly once, and the number of selected triples is 3q + 2(m − q) = q + 2m, as required. Conversely, let M̂ be a perfect matching of Ŝ. We construct a perfect matching of S. Let s ∈ S. As noted above, the six internal elements of s occur only in the triples of Gs , so M̂ covers each of them by a triple of Gs ; we determine which triples of Gs it uses. If σ4s ∈ M̂ , then as1 , bs2 and cs1 are covered, and the only triple of Gs that covers as2 without reusing them is σ5s ; the two together cover the six internal elements, and none of s’s original elements is covered by Gs . If σ4s ∈ / M̂ , then as1 forces σ2s ∈ M̂ , the element bs2 forces σ3s ∈ M̂ , s s and c1 forces σ1 ∈ M̂ ; these three cover the six internal elements, and they cover the original elements of s as well. Hence, every gadget either covers all three original elements of its triple or covers none of them. As every original element is covered exactly once, the set M of the triples s whose gadget covers them is a perfect matching of the original instance. ◀

B.2

Proof of Theorem 6

We first prove the statement for three attributes.

CVIT 2016

23:20

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

▶ Lemma 16. Computing an optimal U-repair for ∆sc 3 is NP-hard. Proof. We reduce from R3DM, which is NP-complete by Lemma 15. Let (X, Y, Z, S) be an instance of R3DM, where |X| = |Y | = |Z| = q and |S| = m, and where we may assume that m ≥ q ≥ 1, since otherwise S has no perfect matching. We refer to the members of X ∪ Y ∪ Z as S-elements. We construct a relation r over A1 , A2 and A3 and a budget K such that S has a perfect matching if and only if r has a consistent update r′ with dist(r′ , r) ≤ K. For c = 3, the target tuple of a cluster is a triple, and we call it the target triple of the cluster; recall that the target triples of distinct clusters disagree on A1 , A2 and A3 . We set: K := 8m − 5q

and

N := K + 1.

For every triple s = (x, y, z) ∈ S, the relation r contains the four gadget tuples ts = (x, y, z)

u1s = (cs1 , y, z)

u2s = (x, cs2 , z)

u3s = (x, y, cs3 )

where cs1 , cs2 and cs3 are fresh constants. We refer to ts as an S-tuple, and to u1s , u2s and u3s its auxiliary tuples; note that ujs contains csj in Aj and agrees with ts on the other two attributes. In addition, r contains, for every j ∈ {1, 2, 3}, an enforcing group: a set of N copies of a tuple that contains csj in Aj and, in the two other attributes, the values dsj,i ; that is, N copies of each of the following three tuples: (cs1 , ds1,2 , ds1,3 )

(ds2,1 , cs2 , ds2,3 )

(ds3,1 , ds3,2 , cs3 )

The 3m fresh constants csj and the 6m values dsj,i are distinct from one another and from the elements. Figure 1 depicts the tuples introduced for a single triple s, with the superscript s omitted. Altogether, r consists of the 4m gadget tuples and of the 3mN tuples of the enforcing groups, and it is constructed in polynomial time. Now, given a perfect matching of S, we construct a consistent update of r. Let M ⊆ S be a perfect matching, and recall that |M | = q. We leave every enforcing group unchanged, so that each of its tuples is its own target triple. For s = (x, y, z) ∈ M , we assign the target triple (x, y, z) to the four gadget tuples of s. The S-tuple ts is then left unchanged, and each auxiliary tuple ujs changes the single cell that contains csj , at a total cost of 3 for each of the q triples in M . Now let s′ = (x′ , y ′ , z ′ ) ∈ S \ M . As M covers every S-element, it contains a triple sx′ = (x′ , yx′ , zx′ ) that includes x′ , and it contains a triple sy′ = (xy′ , y ′ , zy′ ) that includes y ′ . Both tuples are distinct from s′ , so, by LI, each of them shares with s′ only one element (x′ or y ′ ), and hence xy′ ̸= x′ , yx′ ̸= y ′ , zx′ ̸= z ′ and zy′ ̸= z ′ . We assign: The target triple sx′ to ts′ , u2s′ and u3s′ ; The target triple sy′ to u1s′ . Since no fresh constant is an S-element, each of ts′ , u2s′ and u3′ s keeps only its value x′ in A1 , and u1s′ keeps only its value y ′ in A2 . Hence, each of the four tuples in the gadget changes two cells, at a total cost of 8. Hence, we get a total cost of 8 for each of the m − q triples s′ in S \ M . In conclusion, the resulting update r′ satisfies dist(r′ , r) = 3q + 8(m − q) = 8m − 5q = K, as required. It remains to verify that r′ is consistent, that is, that the target triples of distinct clusters disagree on A1 , A2 and A3 . These target triples are the q triples of M and the 3m tuples of the enforcing groups. Two triples of M are disjoint and therefore disagree on

Kimelfeld and Livhits

23:21

every attribute; a triple of M contains elements only, whereas a tuple of an enforcing group contains no elements; and two tuples of distinct enforcing groups disagree on every attribute, since the values csj and dsj,i are all distinct. Next, given a consistent update of r, we construct a perfect matching of S. Let r′ be a consistent update of r with dist(r′ , r) ≤ K. Then r′ includes several clusters, each consisting of copies of a target tuple. We will show that at least q of the target tuples must be S-tuples. From the consistency of r′ we can then conclude that these q S-tuples form a perfect matching M , as required. We begin with two observations. (O1) We can assume that every enforcing group is unchanged in r′ . Since N > K, at least one tuple from the enforcing group remains unchanged, so if any tuple in this group is changed, we can reverse its changes without causing any violation. (O2) We can further assume that every gadget tuple keeps at least one of its three cells. Let t ∈ r be a gadget tuple, and suppose that all three values of t are updated in r′ . If any target tuple t′ ∈ r′ coincides with t on at least one attribute, then we can update t to t′ and reduce the cost by one. If no such t′ agrees, then we can again reverse the updates of t′ and reduce the cost. The cost of r′ is then the number of cells changed within the gadget tuples. By (O2), we can assume that the cost ct incurred by each individual gadget tuple t is at most 2. For convenience, in the remainder of this proof, we refer to 2 − ct as the saving of t. We further refer to the saving of a cluster as the total savings of all tuples in the cluster. With zero savings, we have 4m tuples with a total cost of 8m. Since the total cost of r′ is at most K = 8m − 5q, we conclude that the total savings over all clusters are at least 5q. Next, we analyze the savings of clusters by the type of their target tuple. Before that, we need another observation. (O3) We can assume that whenever a target tuple is not equal to an enforcing tuple, then each value is either an S-element or a new value that does not occur in r. This means that values of the form dsj,i and csj cannot be used in clusters where the target tuple is not equal to an enforcing tuple. This follows directly from (O1), since enforcing tuples from r remain intact in r′ ; hence, if any dsj,i or csj is retained in a gadget tuple, then the tuple needs to agree on all attributes with the enforcing tuple that contains dsj,i or csj . We consider five types of clusters, each defined by a property of its target cluster v. For each cluster, we compute a bound on its savings. (a) No two elements of v co-occur together inside a triple of S. Due to the construction of the gadget tuples, and due to (O3), every gadget tuple differs from v in at least two attributes. Hence, this cluster saves nothing. (b) Exactly one pair of values in v co-occur together in a triple of S. Consider the two S-elements of v that co-occur together in S. By LI, exactly one S-triple contains both of them. By construction, precisely two of its gadget tuples contain both—its S-tuple and one auxiliary tuple; if assigned to the cluster, each of them keeps two cells and saves one. By (O3), every other tuple in the cluster differs from v in at least two attributes, so it saves nothing. So, this cluster saves at most 2 = 1 + 1. (c) Exactly two distinct pairs of values in v co-occur inside triples of S. Due to TF, the third pair of values does not co-occur inside any triple of S. Hence, this case is similar to (b), but with twice the bound. The cluster therefore saves at most 4 = 2 + 2.

CVIT 2016

23:22

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

v is an S-tuple v

x

y

z

ts

x

y

z

two pairs occur in triples v

x

y

z′

+2

ts

x

y

z

x

y

x x

u1s

c1

y

z

+1

u3s

u2s

x

c2

z

+1

ts′

+1

u2s′

u3s

x

y

c3

saving 5

one pair occurs in a triple v

x

y

w

+1

ts

x

y

z

+1

c3

+1

u3s

x

y

c3

+1

y′

z′

+1

c′2

z′

+1

saving 2

saving 4

Figure 3 The three savings that a cluster can attain, with the target triple v on top and, below it, the gadget tuples that save through it. Cells that agree with v are shown in blue and cells that differ from it in gray, and the saving of each tuple is written on its right. On the left, all three pairs of elements of v occur in the triple s; in the middle, the triples s = (x, y, z) and s′ = (x, y ′ , z ′ ) share only the element x, and v contains a pair of each; on the right, w is either not an element or an element that occurs in no triple together with x or with y.

(d) v is an S-tuple. Let s = (x, y, z) ∈ S be this tuple. If assigned to this cluster, the tuple ts keeps all three of its cells and saves 2, and each auxiliary tuple ujs keeps the two cells that it inherits from ts and saves 1. Every other gadget tuple belongs to a triple s′ ̸= s, which, by LI, shares at most one element with s; hence, assigning it to the cluster saves nothing. The cluster saves at most 5 = 2 + 1 + 1 + 1. Note that cases (a)-(d) are pairwise disjoint. Also, due to the TF, they cover all possible clusters. Let nx be the number of distinct target tuples of type (x). To complete the proof, we will show that nd = q; hence, the the target tuples of type (d) form a perfect matching. Let T be the total savings. The case analysis shows that 0na + 2nb + 4nc + 5nd ≥ T . On the other hand, we know that T ≥ 5q. Hence, 2nb + 4nc + 5nd ≥ 5q .

(1)

Let N be the number of S-elements that occur in the target triples. Then 3q ≥ N , which is the total number of S-elements. Two distinct clusters disagree on every attribute, so no S-element is contained in more than one target tuple. Each target tuple of type (b) includes at least two S-elements, and each target tuple of types (c) and (d) includes at least three S-elements. We conclude that N ≥ 2nb + 3nc + 3nd . Hence, 3q ≥ 2nb + 3nc + 3nd .

(2)

Combining Equation (1) and Equation (2), we get that 3q ≥ 2nb + 3nc + 3nd = 2nb + 4nc + 5nd − (nc + 2nd ) ≥ 5q − (nc + 2nd ) Hence, 2q ≤ nc + 2nd ≤ 2nc + 2nd , and therefore nc + nd ≥ q. Using Equation (2), we conclude that 3q ≥ 2nb + 3nc + 3nd ≥ 2nb + 3q, hence nb = 0. With that, from Equation (2) we conclude that 3q ≥ 3nc + 3nd , hence nc + nd ≤ q. Thus, nc + nd = q. Finally, recalling again Equation (1), we conclude that 5q ≤ 4nc + 5nd = 4nc + 4nd + nd = 4q + nd and, therefore, nd ≥ q (actually, nd = q and nc = 0), as claimed.

◀

Kimelfeld and Livhits

23:23

It remains to pass from three attributes to any larger number, which we do by padding every tuple with values that no consistent update within the budget can preserve. ▶ Lemma 17. Let c > 3. Given a relation r over A1 , A2 and A3 with n tuples and a budget K, one can construct in polynomial time a relation r∗ over A1 , . . . , Ac such that r has a ∗ consistent update of cost at most K with respect to ∆sc 3 if and only if r has a consistent sc update of cost at most K + n(c − 3) with respect to ∆c . Proof. Let N := K + n(c − 3) + 1. For every tuple t of r, the relation r∗ contains the tuple t∗ that agrees with t on A1 , A2 and A3 and contains a private value in each of A4 , . . . , Ac . In addition, for every private value p, say the one that t∗ contains in Aj , the relation r∗ contains an enforcing group of N copies of the enforcing tuple ep that contains p in Aj and, in every other attribute, a value that occurs nowhere else. All of these values are distinct and occur in no tuple of r. Now, given a consistent update of r, we construct a consistent update of r∗ . Let r′ be a consistent update of r with dist(r′ , r) ≤ K. We leave every enforcing group unchanged and assign to the tuples t∗ the target triples of r′ , each extended by values that occur nowhere in r∗ and are distinct across clusters. Every t∗ then changes its c − 3 private cells in addition to the cells that t changes in r′ , at a total cost of at most K + n(c − 3). The result is consistent: the extended target tuples pairwise disagree on A1 , A2 and A3 , as do the target triples of r′ , and they agree with no enforcing tuple in any attribute. Next, given a consistent update of r∗ , we construct a consistent update of r. Let r̂ be a consistent update of r∗ with dist(r̂, r∗ ) ≤ K + n(c − 3). Since N exceeds this budget, every enforcing group retains an unchanged copy, and so every enforcing tuple ep is a target tuple of r̂. As the target tuples of distinct clusters disagree on every attribute, we conclude the following. (⋆) For every private value p, the only target tuple of r̂ that contains p in the attribute in which ep contains it is ep itself. We say that a tuple t∗ is captured if its target tuple is an enforcing tuple ep . Since ep contains, in every attribute other than the one that holds p, a value that occurs nowhere else, a captured tuple retains at most one cell and therefore costs at least c − 1. We first show that we may assume that no tuple of r̂ is captured. Let t∗ be a captured tuple. If some target tuple v of r̂ that is not an enforcing tuple agrees with t∗ on an attribute, then we move t∗ to the cluster of v; the tuple t∗ then retains a cell and costs at most c − 1. Otherwise, we place t∗ in a cluster of its own, the target tuple of which agrees with t∗ on A1 , A2 and A3 and contains, in each of A4 , . . . , Ac , a value that occurs nowhere in r∗ and in no other target tuple; the tuple t∗ then costs c − 3. In both cases, the result is again a consistent update of r∗ , and its cost is no higher than that of r̂. This is clear in the first case. In the second case, the new target tuple contains new values in A4 , . . . , Ac and agrees with t∗ on A1 , A2 and A3 , so it suffices to observe that no other target tuple agrees with t∗ on A1 , A2 or A3 . For a target tuple that is not an enforcing tuple, this is the assumption of the case; and an enforcing tuple contains in A1 , A2 and A3 values that occur nowhere else in r∗ , whereas t∗ contains there values of r. Each application of this transformation reduces the number of captured tuples by one, so we may indeed assume that r̂ has none. By (⋆), a tuple t∗ that is not captured retains none of its private cells, and hence it changes all c − 3 of them, in addition to the cells among A1 , A2 and A3 on which it differs from its target tuple. Denoting by dt the number of the latter, we obtain that P P dist(r̂, r∗ ) ≥ n(c − 3) + t∈r dt and, therefore, that t∈r dt ≤ K.

CVIT 2016

23:24

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

We construct r′ by assigning to every tuple t of r the restriction of the target tuple of t∗ P to A1 , A2 and A3 . Every tuple then changes precisely dt cells, so dist(r′ , r) = t∈r dt ≤ K. Finally, r′ is consistent: two tuples of r′ that originate in the same cluster of r̂ are equal, and two tuples that originate in distinct clusters disagree on each of A1 , A2 and A3 , since the target tuples of distinct clusters disagree on every attribute. ◀ Theorem 6. For every c ≥ 3, computing an optimal U-repair for ∆sc c is NP-hard. Proof. For c = 3, this is Lemma 16, the proof of which shows that it is NP-complete to decide whether a relation over A1 , A2 and A3 has a consistent update of cost at most a given budget. For c > 3, Lemma 17 reduces this decision problem, in polynomial time, to the corresponding problem for ∆sc ◀ c .

C

Missing Proofs of Section 5

In this section, we provide the missing proofs for Section 5.

C.1

Proof of Proposition 8

Proposition 8. Computing an optimal U-repair for A ↔ B → C is NP-hard. Proof. We reduce from Vertex Cover. Let G = (V, E) be a graph and let k be a bound on the size of a vertex cover; we may assume that k ≤ |V |, since V itself is a vertex cover. We set L := |V | + 1 and M := L|E| + |V | + 1. We construct a relation r over {A, B, C}, writing a tuple as a triple (a, b, c) that lists its values for A, B and C. The relation consists of the following tuples. Anchors. For every vertex v ∈ V , the relation contains the anchors of v, namely M + 1 copies of (v, v, 0) and M copies of (v, v, 1). Edge gadgets. For every edge {u, v} ∈ E, the relation contains the edge gadget of {u, v}, namely L copies of (u, v, 1), where the two endpoints are ordered arbitrarily. The budget is Kr := M |V | + L|E| + k. We show that G has a vertex cover of size at most k if and only if r has a consistent update r′ with dist(r′ , r) ≤ Kr . Given a vertex cover of G, we construct a consistent update of r. Let S be a vertex cover of G with |S| ≤ k, and let cv := 1 if v ∈ S and cv := 0 otherwise. We change to cv the C-value of every anchor of v whose C-value differs from cv , at a cost of M + 1 if v ∈ S and of M otherwise, and therefore at a total cost of M |V | + |S|. For every edge {u, v}, we pick an endpoint in S, say u, and change to u the B-value of the L copies of (u, v, 1), at a cost of L per edge. The total cost is M |V | + |S| + L|E| ≤ Kr . Every tuple of the resulting relation is of the form (v, v, cv ) for a vertex v: the anchors of v by construction, and each edge tuple because cu = 1 for the chosen endpoint u. The FDs A → B and B → A hold because the A- and B-values of every tuple coincide, and B → C holds because all the tuples with B = v have the C-value cv . Next, given a consistent update of r, we construct a vertex cover of G. Let r′ be a consistent update of r with dist(r′ , r) ≤ Kr . Since r′ |= A ↔ B, the pairs of A- and B-values of r′ form a partial bijection: all the tuples that share their A-value also share their B-value, and vice versa. Moreover, since r′ |= B → C, all the tuples that share their B-value share their C-value as well.

Kimelfeld and Livhits

23:25

Consider the anchors of a vertex v. In r, all of them use the pair (v, v) in A and B, and they split into a group of M + 1 tuples with C = 0 and a group of M tuples with C = 1, violating B → C. Hence, we must modify at least one cell in every tuple of one of the two groups, at a cost of at least M per vertex. The budget is M |V | + L|E| + k, so this leaves a slack of L|E| + k. Pulling the two groups apart is expensive. We say that an anchor of v stays if it retains both its A-value v and its B-value v in r′ , and that it leaves otherwise. Suppose that at least one anchor of v stays and at least one leaves. The anchors that stay use the pair (v, v), so every tuple of r′ with A = v has B = v and every tuple of r′ with B = v has A = v. Therefore, an anchor that leaves cannot retain just one of A = v and B = v: changing one of the two alone collides with the group that stays. It must change both, at a cost of 2 per leaving tuple. As the smaller group has M tuples, pulling a group apart costs at least 2M . If no anchor of v stays, then each of the 2M + 1 anchors of v changes a cell, which costs at least 2M + 1. As M exceeds the slack, neither option is affordable. Hence, every vertex has an anchor that stays, and every vertex unifies its anchors on a single value cv of C: the anchors that stay share the B-value v, hence they share their C-value as well, and we denote it by cv . An anchor that stays costs at least 1 if its C-value in r differs from cv , so the anchors of v cost at least M if cv = 0, at least M + 1 if cv = 1, and at least 2M + 1 if cv ∈ / {0, 1}. The last option exceeds the slack, so cv ∈ {0, 1}. Let S := {v ∈ V | cv = 1}; the anchors cost at least M |V | + |S|. The edge gadgets test whether S covers E. Since an anchor of v stays and carries the pair (v, v), the FD A → B implies that every tuple of r′ with A = v has B = v, and B → C implies that it has C = cv ; symmetrically, every tuple with B = v has A = v and C = cv . Now consider the gadget of an edge {u, v}. None of its L copies of (u, v, 1) can retain both A = u and B = v, so each of them must join the cluster of u or the cluster of v, or leave both. Joining that of u amounts to changing the B-value to u, and it changes nothing else exactly when cu = 1, since then C = 1 is already the C-value of the cluster; if cu = 0, the copy must also change its C-value to 0. The argument for joining the cluster of v is symmetric. A copy that joins neither cluster changes both its A-value and its B-value. Hence, the gadget costs at least L, and at least 2L if cu = cv = 0, that is, if the edge is not covered by S. Let E0 be the set of the edges that S does not cover. Putting the bounds together, Kr ≥ dist(r′ , r) ≥ M |V | + |S| + L|E| + L|E0 |,

hence

|S| + L|E0 | ≤ k.

Since L = |V | + 1 > k, we get E0 = ∅, so S is a vertex cover, and |S| ≤ k.

C.2

◀

Proof of Proposition 9

Proposition 9. Computing an optimal U-repair for A → B ↔ C is NP-hard. Proof. We reduce from 3SAT, assuming that every clause consists of three literals over three distinct variables. Let φ be a formula with variable set V and m clauses, and set L := 4m + 1. With every variable v we associate two fresh values Tv and Fv , one for each truth value. The constructed relation over {A, B, C} consists of: a variable gadget for every variable v, namely L copies of (v, v, Tv ) and L copies of (v, v, Fv ), and a clause gadget for every clause c = (ℓ1 ∨ ℓ2 ∨ ℓ3 ) over the variables v1 , v2 , v3 , namely the three tuples: (c, v1 , w3 )

(c, v2 , w1 )

(c, v3 , w2 )

CVIT 2016

23:26

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

where wi is the value of vi that satisfies ℓi , that is, Tvi if ℓi is positive and Fvi if ℓi is negative. Note that the indices in a clause gadget are shifted: v1 , v2 and v3 coincide with w3 , w1 and w2 , respectively. For example, if c is x ∨ y ∨ ¬z, then the three tuples are: (c, x, Fz )

(c, y, Tx )

(c, z, Ty )

The budget is K := L|V | + 4m. Given a satisfying assignment τ of φ, we construct a consistent update of cost exactly K. Denote by σ(v) the value Tv if τ (v) = true and the value Fv otherwise. For every variable v, we change to σ(v) the C-value of the L tuples of its gadget that carry the other value (cost L|V | in total). For every clause c, we pick a literal ℓi that τ satisfies, and we replace the three tuples of its gadget by (c, vi , wi ); one of the three has already the B-value vi , another already has the C-value wi = σ(vi ), and the third has neither (cost 1 + 1 + 2 = 4 per clause, hence 4m in total). The resulting relation r′ is consistent: it satisfies A → B since the tuples that share an A-value are those of a single gadget, and it satisfies B ↔ C since its pairs of B- and C-values are precisely the pairs (v, σ(v)). Now suppose that we are given a consistent update r′ of cost at most K. Since B ↔ C, the pairs of B-values and C-values that occur in it form a partial bijection, which we denote by σ. If no tuple has the B-value v, then σ(v) is undefined, and we let it be a value that is neither Tv nor Fv , say ⋄. Hence, σ(v) is defined for every variable v. Consider the gadget of a variable v, and let t be a tuple of the gadget whose C-value in r differs from σ(v). The update cannot keep both the B-value and the C-value of t, and it therefore changes at least one cell of t. Thus, the gadget costs at least the number of its tuples whose C-value differs from σ(v). As the gadget splits evenly between Tv and Fv , this number is at least L if σ(v) is one of Tv and Fv , and at least 2L if it is a different C-value in r′ . The cost is also at least 2L if σ(v) = ⋄, since it means that all 2L occurrences of v had to disappear in the update. In conclusion, the variable gadgets cost at least L|V | in total, and at least L|V | + L if σ maps some variable to neither of its two values. Since L exceeds the remaining budget of 4m, the latter is impossible. Hence, σ maps every variable v to one of Tv and Fv , and we can treat it as a truth assignment τ . We complete the proof by showing that τ is a satisfying assignment. Since the remaining budget is 4m, it suffices to show that a clause gadget costs at least 4, and that it costs exactly 4 only if τ satisfies its clause. We do so next. Due to the shift, every tuple of a clause gadget pairs a variable with a value of a different variable; no such pair belongs to σ, so each of the three tuples changes its B-value or its C-value, and the gadget costs at least 3. If the three tuples do not all retain the A-value c, then at least one of them changes its A-value as well, and the gadget costs at least 4. If they all retain it, then A determines both B and C, so the three tuples collapse into a single pair of σ; their three B-values are distinct and so are their three C-values, hence this pair agrees with at most two of the six B-cell and C-cells of the gadget, and the gadget again costs at least 4. In both cases, a cost of exactly 4 forces a pair of (v, σ(v)) that agrees with one B-cell and one C-cell of the gadget: In the first case, exactly one tuple changes its A-value and one of its B of C values, so the two tuples that retain their A have a budget of 2. Since they agree on A, they should

Kimelfeld and Livhits

23:27

be updated into identical tuples, and the only way we can do so is by retaining at least one of the wi of the gadget, and wi satisfies the clause (by construction). In the second case, where A-values are retained, the three tuples should become identical, and the gadget should update at least two B-cells and at least two C-cells. Hence, it updates precisely two C-cells, and again at least one wi is retained and satisfies the clause. We conclude that the clause is necessarily satisfied and τ is a satisfying assignment, as claimed. ◀

C.3

Proof of Proposition 10

Proposition 10. Computing an optimal U-repair for A ↔ B → C ↔ D is NP-hard. Proof. We reduce from A ↔ B → C, which is intractable by Proposition 8 and consists of the first three attributes of A ↔ B → C ↔ D. In the spirit of Lemma 17, the reduction pads every tuple with a private value in the new attribute D and anchors this value by an enforcing group. Let r be a relation over {A, B, C} with n tuples, let K be a budget, and set N := K +n+1. For every i ∈ tids(r), the relation r′ over {A, B, C, D} contains: the main tuple Mi that agrees with r[i] on A, B and C and contains a private value di in D, and for every private value di , the relation r′ contains an enforcing group of N copies of the enforcing tuple Ei that contains di in D and, in each of A, B and C, a value that occurs nowhere else. The budget is K + n. We show that r has a consistent update of cost at most K with respect to A ↔ B → C if and only if r′ has a consistent update of cost at most K + n with respect to A ↔ B → C ↔ D. Now, given a consistent update of r, we construct a consistent update of r′ , Let s be a consistent update of r with dist(s, r) ≤ K. We may assume that s uses none of the values that the construction introduces, since renaming the values of s that do not occur in r affects neither its cost nor its consistency. With every value c that occurs in the C-column of s we associate a fresh value δc , and we define the update s′ of r′ that leaves every enforcing group unchanged and replaces Mi by the tuple (s[i][A], s[i][B], s[i][C], δs[i][C] ). Every main tuple changes its D-cell, since δs[i][C] is fresh and di is not, and the main tuples change dist(s, r) cells in A, B and C in total; hence dist(s′ , r′ ) = dist(s, r) + n ≤ K + n. We verify that s′ |= A ↔ B → C ↔ D. Among the main tuples, A ↔ B and B → C hold because s |= A ↔ B → C, and C ↔ D holds because c 7→ δc is injective. An enforcing tuple Ei shares no value with any other tuple of s′ in any attribute: its A-, B- and C-values occur only in its own enforcing group, and its private value di is no longer used by Mi . Hence, no FD is violated. Next, given a consistent update of r′ , we construct a consistent update of r. Let s′ be a consistent update of r′ with dist(s′ , r′ ) ≤ K + n. Since N exceeds this budget, every enforcing group retains an unchanged copy, and so every enforcing tuple Ei occurs in s′ . As the enforcing tuples occur in s′ , the FDs C → D and D → C imply that a main tuple agrees with an enforcing tuple on C if and only if it agrees with it on D. We first show that we may assume that no main tuple agrees with an enforcing tuple on C. Consider a group Q of main tuples that have been updated to the same (a, b, c, d), where

CVIT 2016

23:28

Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates

(c, d) is the pair of C- and D-values of an enforcing tuple E. Every tuple of Q has changed its C-cell, since c occurs nowhere in r. Moreover, at most one tuple of Q retains its original D-value, namely the main tuple whose private value is d, if it belongs to Q. Let j ∈ Q and let c′ be the original C-value of j. If c′ already occurs in s′ , let d′ be the D-value already paired with it; otherwise, let d′ be a fresh value. We replace the pair (c, d) of every tuple of Q by (c′ , d′ ). If (a, b) is the pair of A- and B-values of E, those cells were already changed, since the values of E occur nowhere in r, and we replace them by a fresh pair as well, so as not to violate B → C against E. One C-cell is then restored, namely that of j, and at most one extra D-cell is changed, namely if some tuple of Q had retained d and d′ differs from d. Hence, the cost does not increase. The result is again a consistent update of r′ . The tuples of Q now agree on (c′ , d′ ). If we replaced A and B, they agree on a fresh pair that occurs nowhere else. If we kept (a, b), then no tuple outside Q has the B-value b: the enforcing tuple E has a different B-value, and every other tuple with B = b would have had C = c by B → C, hence would have belonged to Q. The value c′ occurs in r and is therefore the C-value of no enforcing tuple, so the tuples of Q no longer agree with an enforcing tuple on C or on D. Repeating the modification for every such group, we obtain a consistent update of r′ of cost at most K + n in which no main tuple agrees with an enforcing tuple on D, and we assume from now on that s′ is such an update. In s′ , no main tuple retains its private value, since it would then agree with its own enforcing tuple on D and hence on C. The main tuples therefore change n cells in the attribute D, and so they change at most K cells in A, B and C. Let s be the update of r obtained by restricting the main tuples of s′ to A, B and C; then dist(s, r) ≤ K, and s is consistent, since the FDs A → B, B → A and B → C are implied by A ↔ B → C ↔ D and hence hold in s′ , in particular among the main tuples. ◀

Related documents

• Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates#615300
• Optimal Repairs for Unary Functional Dependencies: Resolving the Case of Updates#614333
• DepRepair: LLM-Based Source-Code Repair for Dependency Breaking Changes#386947
• ORCA: Observability-Grounded Program Repair for Microservice Incidents#463299
• DebugRepair: Enhancing LLM-Based Automated Program Repair via Self-Directed Debugging#124132