Repairing Databases over Metric Spaces with Coincidence Constraints

Recall that a metric space is a pair $(M,\delta )$ where $M$ is a set of points and $\delta :M\times M\to ℝ$ is a function satisfying the following: positivity: $\delta (x,y)\ge 0$ for all $x,y\in M$ and $\delta (x,y)=0$ if and only if $x=y$; symmetry: $\delta (x,y)=\delta (y,x)$ for all $x,y\in M$; and the triangle inequality: $\delta (x,z)\le \delta (x,y)+\delta (y,z)$ for all $x,y,z\in M$. When $M$ is finite, the metric $(M,\delta )$ can also be seen as having its distances correspond to the length of the shortest paths in an undirected graph, such as a complete graph on $M$ where each edge $(u,v)$ has weight $\delta (u,v)$.

We will discuss three special cases of metric spaces $(M,\delta )$, and we will distinguish between them via a subscript of the distance function $\delta$.

• $\mathrm{■}$

  A line metric $(M,{\delta }_{ℝ})$, where $M\subseteq ℝ$ and ${\delta }_{ℝ}(x,y)=|x-y|$.

• $\mathrm{■}$

  A discrete metric $(M,{\delta }_{\ne })$, where ${\delta }_{\ne }(x,y)=1$ whenever $x\ne y$.

• $\mathrm{■}$

  A tree metric $(M,{\delta }_T)$, where $T$ is a weighted tree with the vertex set $M$, and ${\delta }_T(x,y)$ is the weighted distance (i.e., sum of weights along the unique path) in $T$ between $x$ and $y$.

We assume three countably infinite sets: $\mathrm{𝖠𝗍𝗍𝗌}$ is the set of all attributes, $\mathrm{𝖢𝖾𝗅𝗅𝗌}$ is a set of all cells, and $\mathrm{𝖵𝖺𝗅𝗌}$ is a set of values. Each cell $c$ is labeled with an attribute $\lambda (c)\in \mathrm{𝖠𝗍𝗍𝗌}$. If $\lambda (c)=A$, then we call $c$ an $A$-cell. By a domain we refer to a set $M\subseteq \mathrm{𝖵𝖺𝗅𝗌}$ of values.

A database is a mapping $D$ from a finite set of cells, denoted $\mathrm{𝖢𝖾𝗅𝗅𝗌}(D)$, to values. Hence, we view a database as a function $D:\mathrm{𝖢𝖾𝗅𝗅𝗌}(D)\to \mathrm{𝖵𝖺𝗅𝗌}$. We denote by $\mathrm{𝖵𝖺𝗅𝗌}(D)$ the set of values that occur in $D$, that is, $\mathrm{𝖵𝖺𝗅𝗌}(D):=\{D(c)\mid c\in \mathrm{𝖢𝖾𝗅𝗅𝗌}(D)\}$. We say that $D$ is a database over a domain $M\subseteq \mathrm{𝖵𝖺𝗅𝗌}$ if $\mathrm{𝖵𝖺𝗅𝗌}(D)\subseteq M$. If $D$ is a database and $A\in \mathrm{𝖠𝗍𝗍𝗌}$, then we denote by $D[A]$ the restriction of $D$ to its $A$-cells; hence, $\mathrm{𝖢𝖾𝗅𝗅𝗌}(D[A])=\{c\in \mathrm{𝖢𝖾𝗅𝗅𝗌}(D)\mid \lambda (c)=A\}$, and $D[A](c)=D(c)$ for all $c\in \mathrm{𝖢𝖾𝗅𝗅𝗌}(D[A])$. If $D$ is a database and $v\in \mathrm{𝖵𝖺𝗅𝗌}$, then we denote by $D^{-1}(v)$ the set of cells $c\in \mathrm{𝖢𝖾𝗅𝗅𝗌}(D)$ with $D(c)=v$. We denote by $\mathrm{𝖠𝗍𝗍𝗌}(D)$ the set of attributes that occur in $D$, that is, $\mathrm{𝖠𝗍𝗍𝗌}(D):=\{\lambda (c)\mid c\in \mathrm{𝖢𝖾𝗅𝗅𝗌}(D)\}$.

A signature $𝐀$ is a sequence $(A_1,\mathrm{\dots },A_q)$ of attributes. We denote by $\mathrm{𝖠𝗍𝗍𝗌}(𝐀)$ the attribute set $\{A_1,\mathrm{\dots },A_q\}$. An instance of $𝐀$ is a database $D$ such that $\mathrm{𝖠𝗍𝗍𝗌}(D)\subseteq \mathrm{𝖠𝗍𝗍𝗌}(𝐀)$. In the remainder of this paper, we always assume the presence of a signature $𝐀$, and a database $D$ that we mention is implicitly assumed to be an instance of $𝐀$.

Let $𝐀=(A_1,\mathrm{\dots },A_q)$ be a signature. If $D$ is database and $v\in \mathrm{𝖵𝖺𝗅𝗌}$, then the sequence $p_D(v):=(|D{[A_1]}^{-1}(v)|,\mathrm{\dots },|D{[A_q]}^{-1}(v)|)$ lists the number of $A_i$-cells with the value $v$ for $i=1,\mathrm{\dots },q$. We call $p_D(v)$ the coincidence profile of $v$ (stating how many cells of each attribute coincide at $v$).

Let $M\subseteq \mathrm{𝖵𝖺𝗅𝗌}$ be a domain. A coincidence constraint over $M$ (w.r.t. $𝐀$) is a function $\mathrm{\Gamma }$ that maps every value $v\in M$ to a subset $\mathrm{\Gamma }(v)\subseteq {\mathbb{N}}^q$, stating the allowed coincidence profiles for every value in $M$. A database $D$ over $M$ satisfies $\mathrm{\Gamma }$, denoted $D\vDash \mathrm{\Gamma }$, if $p_D(v)\in \mathrm{\Gamma }(v)$ for all $v\in M$; that is, the coincidence profile of every value in $M$ is allowed by $\mathrm{\Gamma }$. Conversely, $D$ violates $\mathrm{\Gamma }$ if $p_D(v)\notin \mathrm{\Gamma }(v)$ for at least one value $v\in M$, and then we denote it by $D\vDash ̸\mathrm{\Gamma }$.

Note that the class of coincidence constraints is closed under conjunction (intersection), disjunction (union), and negation (complement). That is, if ${\mathrm{\Gamma }}_1$ and ${\mathrm{\Gamma }}_2$ are coincidence constraints over $M$, then ${\mathrm{\Gamma }}_1\cup {\mathrm{\Gamma }}_2$ (that maps every $v\in M$ to ${\mathrm{\Gamma }}_1(v)\cup {\mathrm{\Gamma }}_2(v)$) is a coincidence constraint over $M$, and so are ${\mathrm{\Gamma }}_1\cap {\mathrm{\Gamma }}_2$ and ${\mathbb{N}}^q\setminus {\mathrm{\Gamma }}_2$. Also note that a $\mathrm{\Gamma }(v)$ may be infinite, but for a given database, only a finite subset is relevant (see Remark 6 later in the section).

For illustration, let $𝐀=(A_1,\mathrm{\dots },A_q)$, and let $M$ be a set of values. The key constraint $\mathrm{𝗄𝖾𝗒}(A_j)$ states that no two $A_j$-cells can have the same value. Hence, $\mathrm{𝗄𝖾𝗒}(A_j)$ says that every value can have at most one $A_j$-cell. The constraint $\mathrm{𝗄𝖾𝗒}(A_j)$ can be expressed as the following function (which is the same on every point $v$):

The inclusion constraint $A_{\mathrm{\ell }}⊑A_j$ states that every value in an $A_{\mathrm{\ell }}$-cell must also occur in an $A_j$-cell. Hence, $A_{\mathrm{\ell }}⊑A_j$ states that every value that has one or more $A_j$-cells must also have one or more $A_{\mathrm{\ell }}$ cells, and can be expressed by the following coincidence constraint:

Finally, the foreign-key constraint $A_{\mathrm{\ell }}{⊑}_{𝗄}{A}_j$ is the conjunction of $\mathrm{𝗄𝖾𝗒}(A_j)$ and $A_{\mathrm{\ell }}⊑A_j$, hence expressed by the coincidence constraint ${\mathrm{\Gamma }}_{A_{\mathrm{\ell }}{⊑}_{𝗄}{A}_j}:={\mathrm{\Gamma }}_{\mathrm{𝗄𝖾𝗒}(A_j)}\cap {\mathrm{\Gamma }}_{A_{\mathrm{\ell }}⊑A_j}$.

A coincidence constraint $\mathrm{\Gamma }$ may, in principle, pose a different restriction on every value of $M$. We also consider the uniform case where $\mathrm{\Gamma }$ is the same everywhere. Formally, we say that $\mathrm{\Gamma }$ is uniform if $\mathrm{\Gamma }(v)=\mathrm{\Gamma }(u)$ for all pairs $u$ and $v$ of values in $M$. In this case, we may write just $\mathrm{\Gamma }$ instead of $\mathrm{\Gamma }(v)$, and treat $\mathrm{\Gamma }$ simply as a set of coincidence profiles $(i_1,\mathrm{\dots },i_q)$. For example, each of ${\mathrm{\Gamma }}_{\mathrm{𝗄𝖾𝗒}(A_j)}$, ${\mathrm{\Gamma }}_{A_{\mathrm{\ell }}⊑A_j}$ and ${\mathrm{\Gamma }}_{A_{\mathrm{\ell }}{⊑}_{𝗄}{A}_j}$ is uniform since its definition does not depend on $v$, hence we can write, for instance, ${\mathrm{\Gamma }}_{\mathrm{𝗄𝖾𝗒}(A_j)}:=\{(i_1,\mathrm{\dots },i_q)\mid i_j\le 1\}$.

Let $𝐀=(A_1,\mathrm{\dots },A_q)$ be a signature, $(M,\delta )$ be a metric space, and $\mathrm{\Gamma }$ be a coincidence constraint over $M$. An inconsistent database is a database $D$ over $M$ such that $D\vDash ̸\mathrm{\Gamma }$. A repair of $D$ is a database $E$ such that $\mathrm{𝖢𝖾𝗅𝗅𝗌}(E)=\mathrm{𝖢𝖾𝗅𝗅𝗌}(D)$ and $E\vDash \mathrm{\Gamma }$. The cost of a repair $E$ is the cumulated distance that the values of $D$ undergo in the transformation to $E$. We allow to differentiate the cost between different attributes, so we assume a global weight function $w:\mathrm{𝖠𝗍𝗍𝗌}(𝐀)\to {ℝ}_{\ge 0}$.¹¹1For example, it may be the case that we trust $A_i$-cells more than we trust $A_j$-cells, so the same movement by distance $ϵ$ can contribute differently to the cost of $E$; this will be reflected in $w(A_i)>w(A_j)$. Hence, we define the cost of a repair $E$, denoted $\kappa (D,E,\delta )$, by

We study the complexity of computing a low-cost repair. Formally, we assume a fixed signature $𝐀$. The input consists of a finite metric space $(M,\delta )$, a finite coincidence constraint $\mathrm{\Gamma }$ over $M$, and an inconsistent database $D$ over $M$. The goal is to compute an optimal repair, that is, a repair $E$ such that $\kappa (D,E,\delta )\le \kappa (D,E^{\prime },\delta )$ for all repairs $E^{\prime }$, or declare that no repair exists. We will also study the approximate version of finding an $\alpha$-optimal repair, where $\alpha$ is a number (or a numeric function of the input), which is a repair $E$ such that $\kappa (D,E,\delta )\le \alpha \cdot \kappa (D,E^{\prime },\delta )$ for all repairs $E^{\prime }$.

It may be unclear upfront whether we can even test in polynomial time whether any repair exists (i.e., our version of the existence of repair problem [4]). It follows immediately from our later results on optimal repairs (e.g., Theorem 8) that this problem is, indeed, solvable in polynomial time. Yet, our first result in the next section states hardness of approximation, even when a repair is guaranteed to exist.

The following theorem states that for general input metrics, it is NP-hard to approximate the optimal repair beyond some fixed ratio. Recall that the metric space $(M,\delta )$ is given explicitly as part of the input (e.g., as a graph). Be reminded that APX-hardness means that there is some constant $\alpha >1$ such that there is no polynomial-time algorithm for computing an $\alpha$-approximation unless $\text{P}=\text{NP}$. The proof (in the full version [21]) is via a PTAS reduction from the problem of finding a minimum cover by 3-sets.

The remainder of this paper is therefore dedicated to obtaining optimal algorithms for metrics of interest (notably, the line metric and discrete metric), and providing provable approximation algorithms for general metrics.

Many problems in tree metrics are amenable to dynamic programming approaches, allowing for polynomial-time algorithms for problems that might be intractable on general metrics. This is also the case here. In this section, we devise a polynomial-time algorithm for finding an optimal repair in the case of a tree metric. Formally, we will prove that:

Theorem 8 implies, in particular, that we can test in polynomial time whether a repair exists (regardless of the metric): apply the theorem to an arbitrary tree metric over the points. Moreover, the tractability of tree metrics implies the same for other basic metrics:

Leveraging our algorithm for tree metrics and classic results for probabilistic tree embeddings, in this section we devise a logarithmic-ratio approximation for general (finite) metrics. Formally, we will prove that:

In the remainder of this section, we prove Theorem 11. We fix the input $(M,\delta ,\mathrm{\Gamma },D)$ for the rest of this section. The proof is based on the following classic tree embedding lemma [16] that allows for the translation of exact algorithms for tree metrics to $O(\log |M|)$-approximation algorithms for arbitrary metrics.

Blelloch, Gu, and Sun [6] show a near-linear-time counterpart of Lemma 12. We note that randomization and expectation are crucial for this theorem; for example, if we embed an $n$-point cycle with unit-distance edges in any tree, then at least one pair of vertices will suffer an $\mathrm{\Omega }(n)$ distortion [3, Theorem 7].

By combining Theorem 8 and Lemma 12, we will show how we obtain an $O(\log |M|)$ approximation, with high probability, in polynomial time. We do so by repeatedly finding an optimal repair for multiple random trees $T$, and taking the best outcome. More precisely, to obtain an $O(\log |M|)$-approximation with probability at least $1-ϵ$, we take the best outcome out of the $O(\log \frac{1}{ϵ})$ repetitions of the following procedure:

1. 1.

   Select a random tree $T$ according to Lemma 12.

2. 2.

   Find an optimal repair $E_T$ for $(M,{\delta }_T)$, $\mathrm{\Gamma }$ and $D$.

We show that the process gives an $O(\log |M|)$-approximation with probability at least $1-ϵ$. Let us denote by $E_{\mathrm{opt}}$ an optimal repair for the original metric $(M,\delta )$. We use the following two lemmas.

Up to now, we have considered databases over a finite metric $(M,\delta )$ that is given explicitly as part of the input. In particular, a repair could use only values from the given point set $M$. There are, however, natural situations where the metric is a known infinite metric that can provide additional points for repairs. We wish to be able to repair an inconsistent database by using arbitrary values from the infinite metric. An example is the ${\mathrm{\ell }}_p$-metric $(M,\delta )$ where $M$ is the Euclidian space ${ℝ}^k$ and $\delta$ is the norm $\parallel \cdot {\parallel }_p$ over $M$, that is, $\delta (v,u)={\Vert v-u\Vert }_p$.

To model the computational problem in the case of infinite metrics, we consider the case where the metric $(M,\delta )$ is fixed and infinite. Moreover, the coincidence constraint $\mathrm{\Gamma }$ is fixed, and we restrict the discussion to a uniform $\mathrm{\Gamma }$ (that maps every point in $M$ to the same, possibly infinite, set of coincidence profiles). We will further assume that $\mathrm{\Gamma }$ contains the profile $(0,\mathrm{\dots },0)$ since, otherwise, it is impossible to satisfy $\mathrm{\Gamma }$ using any database, as our databases are finite. Computationally, we only require polynomial-time computation of distances $\delta (u,v)$, given $u$ and $v$, and membership testing in $\mathrm{\Gamma }$, given $(i_1,\mathrm{\dots },i_q)$.

The following theorem states that we need not use points outside of $D$ if we are satisfied with a 2-approximation and the coincidence constraint is closed under addition. Note that a uniform coincidence constraint $\mathrm{\Gamma }$ over $M$ is closed under addition if for every pair $(i_1,\mathrm{\dots },i_q)$ and $(i_1^{\prime },\mathrm{\dots },i_q^{\prime })$ of profiles in $\mathrm{\Gamma }$, the profile $(i_1+i_1^{\prime },,\mathrm{\dots },i_q+i_1^{\prime },)$ is also in $\mathrm{\Gamma }$. For illustration, referring to Section 2.3, the inclusion constraint ${\mathrm{\Gamma }}_{A_j⊑A_{\mathrm{\ell }}}$ is closed under addition, but the key constraint ${\mathrm{\Gamma }}_{\mathrm{𝗄𝖾𝗒}(A_j)}$ and the foreign-key constraint ${\mathrm{\Gamma }}_{A_j{⊑}_{𝗄}{A}_{\mathrm{\ell }}}$ are not closed under addition.

Note that a low cost of a repair $E$ does not necessarily imply that an individual cell is moved to a point that is close to its origin. This is due to our choice to measure the cost of a repair as the sum of cell movements. It is clearly of interest to consider the variant of the problem where we limit the movement of individual cells by a threshold.

In this section, we consider the extension of our repairing problem where a bound is posed on the maximal movement of a cell. Formally, consider a metric space $(M,\delta )$, a coincidence constraint $\mathrm{\Gamma }$, and an inconsistent database $D$. For a threshold $\tau >0$, a $(\delta \le \tau )$-repair is a repair $E$ such that $\delta (D(c),E(c))\le \tau$ for every $c\in \mathrm{𝖢𝖾𝗅𝗅𝗌}(D)$. Our goal is now to find a $(\delta \le \tau )$-repair $E$ with a minimal $\kappa (D,E,\delta )$.

However, the bound restriction is nontrivial to deal with. Our algorithms inherently fail to deal with this restriction. The dynamic-programming algorithm of Theorem 8 is based on the fact that we can remember the total movement of cells from/to the root, but not any information about individual cells. Moreover, the approximation using the random tree embedding of Lemma 12 cannot lead to the support of a bound restriction, since every random tree may (unavoidably) have a high distortion, meaning that two individual points $u$ and $v$ can be way farther in ${\delta }_T$ than in $\delta$. In fact, even the existence of a repair (regardless of its cost) becomes an intractable problem in the presence of a bound constraint.