Targeted Least Cardinality Candidate Key for Relational Databases

A relational database schema $R$, represented as $R(A_1,\mathrm{\dots },A_n)$, consists of a set of attributes or variables. An instance of $R$, denoted by $r(R)$, is a set of tuples, where each tuple is an element of the Cartesian product of the attributes’ domains, i.e., $r(R)\subseteq \text{dom}(A_1)\times \mathrm{\dots }\times \text{dom}(A_n)$. We also use $V=\{A_1,\mathrm{\dots },A_n\}$, or simply $V=[n]$, to denote the set of attributes/variables. Each element $t\in r(R)$ is referred to as a tuple. Functional dependencies (FDs for short) are properties of the semantics of the attributes in $R$ [17]. Specifically an FD is a constraint between two sets of attributes $X,Y\subseteq V$. We say that $X$ functionally determines $Y$ and this means that if two tuples have the same value for all the attributes in $X$, they must also have the same values for all the attributes in $Y$. This is denoted as $X\to Y$. We refer to an FD $X\to Y$ as regular when $|Y|=1$. Any irregular FD $X\to y_1{y}_2\mathrm{\dots }{y}_k$ is equivalent to the set of regular FDs $X\to y_i$ for $i=1,\mathrm{\dots },k$. An input set $ℱ$ of FDs, may logically imply more FDs. For instance, the set $ℱ=\{a\to b,b\to c\}$ logically implies $a\to c$. The set of all possible valid FDs for $ℱ$ is its closure ${ℱ}^{+}$. The inference of valid FDs is performed using Armstrong’s axioms which are sound and complete [16]. In practice $|ℱ|\ll |{ℱ}^{+}|$. Finding a smaller set of FDs ${ℱ}^{\prime }$ than $ℱ$ such that ${ℱ}^{\prime +}={ℱ}^{+}$ is known as the canonical cover problem and can be solved efficiently [37]. Other compression schemes are also available, see [3]. The attribute closure $X^{+}$ is the set of attributes that are functionally determined by $X$. In contrast to the FD closure, computing the closure $X^{+}$ of a subset of attributes $X\subseteq V$ is solvable in linear time [37].

A key of a relation $r$ is a subset $X\subseteq V$ that satisfies two conditions: (i) uniqueness, meaning no two distinct tuples in $r$ have identical values for the attributes in $X$, and (ii) minimality, meaning no proper subset of $X$ satisfies the uniqueness property. When $X$ is a key, the functional dependency (FD) $X\to V$ is valid, or equivalently, the closure of $X$, denoted $X^{+}$, is equal to $V$. A subset of attributes $X$ is considered a super-key if it satisfies the uniqueness property but not the minimality property. If a relation has more than one minimal key, each of these keys is referred to as a candidate key of $R$. Finding the least cardinality key is NP-hard. Specifically, deciding if there exists a key of cardinality $k$ is NP-complete using a straight-forward reduction from vertex cover [32]. Furthermore, in terms of approximation algorithm very little is known. Specifically, Akutsu and Bao [1] proved that the problem is at least as hard as the set cover problem [18] but they do not discuss algorithmic upper bounds.

The Set Cover problem is a quintessential problem in computer science, renowned for its wide applicability and fundamental role in computational complexity theory. It was one of Karp’s 21 NP-complete problems [24], serving as a cornerstone for the study of approximation algorithms and computational intractability. The problem is defined as follows: given a universe $U=\{u_1,u_2,\mathrm{\dots },u_n\}$ and a collection of subsets $S=\{S_1,S_2,\mathrm{\dots },S_m\}$ where each $S_i\subseteq U$, the Set Cover problem seeks to find a minimum subset $C\subseteq [m]$ of set indices such that ${\bigcup }_{i\in C}{S}_i=U$. Feige showed that the Set Cover problem cannot be approximated in polynomial time to within a factor of $(1-o(1))\cdot \ln n$ unless NP has quasi-polynomial time algorithms. This inapproximability result was further improved by Dinur and Steuer who showed optimal inapproximability by proving that it cannot be approximated to $(1-o(1))\cdot \ln n$ unless $P=\text{NP}$ [14]. We use the latter result in Theorem 6. The Set Cover problem admits an approximation within a factor of $O(\log n)$ utilizing either a straightforward greedy strategy or a randomized algorithm based on linear programming (LP) rounding techniques. Additionally, there is a deterministic LP-based algorithm that guarantees an $f$-factor approximation, with $f$ denoting the maximum frequency an element of the universe is represented in the set collection $S$ [42]. The Set Cover problem is not only fundamental in computer science but also has a wide range of applications, as discussed in [13].

As we show, a variant of the Set Cover problem that plays an important role for the TCAND problem is the Red Blue Set Cover problem introduced by Carr et al. [8]: given a universe $U=R\cup B$ where $R$ and $B$ are disjoint sets representing red and blue elements respectively, and a collection of subsets $S=\{S_1,S_2,\mathrm{\dots },S_m\}$ where each $S_i\subseteq U$, the Red Blue Set Cover problem seeks to find a subset $C\subseteq S$ such that ${\bigcup }_{S_i\in C}{S}_i\cap B=B$ and ${\bigcup }_{S_i\in C}{S}_i\cap R$ is minimized. Recently, Chlamtáč et al. [11] proved the following state-of-the-art approximation result for the Red Blue Set Cover problem.

To discuss the inapproximability of the Red Blue Set Cover we need to introduce the Dense-vs-Random Conjecture [7]. Given a graph $G(V,E)$, the density of a subgraph induced by $S\subseteq V$ is defined as $\rho (S)=\frac{e(S)}{|S|}$, which is the ratio of the number of edges to the number of nodes in the subgraph [20]. The densest $k$-subgraph problem (D$k$S) problem asks for the densest subgraph with exactly $k$ nodes; it is NP-hard with the best-known approximation ratio being $\mathrm{\Omega }(1/n^{1/4+ϵ})$ for any $ϵ>0$ [7]. This approximability result is far off from the best-known hardness result that assumes the Exponential Time Hypothesis (ETH). If ETH holds, then D$k$S cannot be approximated within a ratio of $n^{1/{(\log \log n)}^c}$ for some $c>0$ [33]. Define the log-density of a graph with $n$ nodes as ${\log }_n(D_{avg})$, where $D_{avg}$ represents the average degree. The Dense-vs-Random Conjecture on graphs [9] conjectures that it is hard to distinguish between the following two cases: 1) $G=G(n,p)$ where $p=n^{\alpha -1}$ (and thus the graph has log-density concentrated around $\alpha$), and 2) $G$ is adversarially chosen so that the densest $k$-subgraph has log-density $\beta$ where $k\beta \gg pk$ (and thus the average degree inside this subgraph is approximately $k^{\beta }$). In this context, $G(n,p)$ represents the random Erdős and Rényi graph model  [15, 19].

Using an extension of the above conjecture on hypergraphs, Chlamtáč et al. [11] proved the following inapproximability result.

The integrality gap of an integer program is the worst-case ratio over all instances of the problem of value of an optimal solution to the integer programming formulation to value of an optimal solution to its linear programming relaxation [42, 41]. Notice that in the case of a minimization problem, the integrality gap satisfies

This gap provides insights into how closely the LP relaxation approximates the IP and is a measure of the performance of approximation algorithms. A small integrality gap (i.e., close to 1) indicates that the LP relaxation is a good approximation of the IP, while a large gap suggests the LP relaxation might not yield a good approximation and that other approximation strategies may be needed. It is often used as a benchmark to understand the effectiveness of approximation algorithms and to determine the best possible approximation ratio that can be achieved by any polynomial-time algorithm for NP-hard problems. Lovász proved that the integrality gap for the straight-forward LP formulation of the Set Cover is $O(\log n)$ [31].

In Section 3, we make use of the following theorem, known as the equitable coloring theorem, which was proved by Hajnal and Szemerédi [22].

There exist efficient algorithms for finding such a coloring, e.g.,  [27, 28]. The best known algorithm is due to Kierstead et al. [28] and runs in $O(k{n}^2)$ time and returns such an equitable coloring. We apply the Hajnal-Szemerédi theorem to establish a Chernoff-type concentration result under conditions of limited dependencies, as demonstrated in works like [29, 36].

We create an instance of the $D$-round TCAND problem as follows. Consider the variable set $V:=V^{(0)}\cup V^{(1)}\cup \mathrm{\dots }\cup V^{(D)}$ where $V^{(r)}:={\left\{(i,r)\right\}}_{i\in [5]}$. Note that we use tuples as variable names. We insert FDs in $ℱ$ from some pairs of variables in $V^{(r)}$ to variables in $V^{(r+1)}$ as follows for $r=0,\mathrm{\dots },D-1$. For each variable $(k,r+1)$ in $V^{(r+1)}$, we create two FDs of the form $(i,r),(j,r)\to (k,r+1)$. Note that $|V^{(r)}\times V^{(r)}|=\left(\genfrac{}{}{0pt}{}{5}{2}\right)=10$ pairs of variables in layer $r$. These 10 pairs are then partitioned into 5 sets, each containing 2 pairs. Each set corresponds to the left-hand side of an FD for a specific variable in the next layer, $V^{(r+1)}$. In other words, for each variable in $V^{(r+1)}$, there are two pairs of variables from $V^{(r)}$ that determine it through FDs. Finally, we set $T=V^{(D)}$ as the target set for this instance. Notice that $T\subseteq {(V^{(0)})}^{+}$.

A feasible fractional solution to our LP formulation is to assign the fractional weight $c:=2^{-D+1}$ to every variable in $V^{(0)}$, i.e. set $x_{i,0}^{(0)}=2^{-D+1},i\in [5]$. One can verify that $z_{LS}^{(1)}:=1$ for every $LS\to (i,1)$ and hence we have that $x_{i,1}^{(1)}$ can be as large as ${\sum }_{z_{LS}^{(1)}\to (i,1)}c=2c$ for all $i$ by the fact that every $(i,r)$ variable can be inferred from exactly two FDs. Inductively, we have that $x_{i,d}^{(d)}$ can be as large as $2^{d}c$ and hence in the last layer we have $x_{i,D}^{(D)}=2^D\cdot c=1$, meaning that every element in the last layer, which is exactly our target set, satisfies the target constraint of our LP. This shows that the total fractional cost is $5\cdot 2^{-D}$ whereas the integral cost is $5$, yielding the $2^D$ integrality gap. $◀$

It is important to note that our proof employs an inductive approach. However, the underlying intuition becomes more apparent when we consider the process starting from the final layer $D$ and moving backwards. In the final layer, each variable is a target variable, so its corresponding LP variable is set to 1 because of the target constraints. Given that each variable can be inferred by two FDs, an unfavorable yet feasible scenario for the LP would involve equally distributing the weight between these two FDs, and this pattern continues in preceding layers. The complete proof of Theorem 12 essentially extends this concept by adjusting the number of FDs associated with each variable.

To obtain the general hardness on the integrality gap, we note that it suffices to set $V^{(r)}:={\left\{(i,r)\right\}}_{i\in [g]}$ for some parameter $g$. Then we can force each variable in $V^{(0)},V^{(1)},\mathrm{\dots },V^{(D)}$ to participate in $\left(\genfrac{}{}{0pt}{}{g}{2}\right)/g\ge \lfloor \frac{g-1}{2}\rfloor$ FDs. Thus, the base of exponent in the fractional magnification per level is $g-1$ in contrast to $2$ and thus we may obtain both results by setting $g:=n/(D+1)$ (for a total of $g\cdot D=n$ nodes) or $g=f=ma{x}_{i\in V}|X\subseteq V:X\to i\in ℱ|$ for any $f\ge 3$.

For $f=2$, we observe that the problem is as hard as the Vertex Cover problem, so it cannot be approximated within a factor $2-ϵ$ for any $ϵ>0$ assuming the Unique Games Conjecture [25]. To prove the equivalence $G(V,E)$ we create a non-target variable $x_v$ for each vertex $v\in V$ and a target variable $x_e$ for each edge $e\in E$ adding the FD $x_u{x}_v\to x_e$ if $e:=(u,v)$. We first observe that any vertex cover in $G$ corresponds trivially to a set of variables which cover all target variables ${\{x_e\}}_{e\in E}$. For the other direction, every set $S$ of variables of size $\le k$ from which ${\{x_e\}}_{e\in E}$ can be inferred we can create a set $\tilde{S}$ of size $|\tilde{S}|\le |S|\le k$ by substituting each $x_e\in S,e:=(u,v)$ with $x_u$ (if $x_u$ already in the set) and noting that $\tilde{S}$ is a vertex cover for $G$. $◀$ The above instances rule out any hope for designing efficient approximation algorithms for TCAND using linear programming based approaches.