= Solution
Let $\mathcal A$ contain the $n$ <database attributes> of $R$, and let $F$ contain the given <functional dependencies> for $R$. To compute the <attribute closure> $X^+$, start with $X$ and repeatedly add $V$ for every <functional dependency> $U\to V$ with $U\subseteq X^+$, stopping when a full scan adds nothing.
Enumerate every $X\subseteq\mathcal A\setminus\{a\}$. For each, test whether $X$ is not a <superkey> but becomes one on adding $a$:
$$
\boxed{\text{return yes if }X^+\ne\mathcal A\quad\text{and}\quad(X\cup\{a\})^+=\mathcal A.}
$$
If no enumerated $X$ passes both tests, return no. A direct implementation is
``
for each subset X of attributes(R) minus {a}:
if closure(X, F) != attributes(R):
if closure(X union {a}, F) == attributes(R):
return yes
return no
``
If a <candidate key> $K$ contains $a$, choose $X=K\setminus\{a\}$. Minimality makes $X$ fail the <superkey> test while $X\cup\{a\}=K$ passes it, so the <algorithm> finds a witness.
Conversely, suppose an enumerated $X$ passes. Starting from $X\cup\{a\}$, repeatedly discard any <database attribute> other than $a$ whose removal preserves the <superkey> property. The process terminates at a <superkey> $K$ minimal with respect to these deletions. Removing $a$ cannot leave a <superkey>: $K\setminus\{a\}\subseteq X$, and a subset of $X$, which is not a <superkey>, cannot determine more <database attributes> than $X$. Hence $K$ is a <candidate key> containing $a$. The <algorithm> need not carry out this minimization to return the correct yes/no answer; it establishes why the witness test suffices.
For an explicit <analysis of algorithms>, let $L$ be the total encoded length of the <functional dependencies>, counting their left and right <database attribute> occurrences and delimiters. With Boolean membership arrays, one complete dependency scan costs $O(L)$. There are at most $n$ productive scans, followed by one unproductive scan, so a naive <attribute closure> costs $O(nL+n)$. There are $2^{n-1}$ subsets and at most two <attribute closure> computations per subset. Thus
$$
\boxed{\text{time }O\!\left(2^n n(L+1)\right),\qquad\text{space }O(n+L).}
$$
This is an exponential-time <algorithm> in the number of <database attributes>, not a polynomial-time claim. Subsets can be generated successively rather than stored all at once. The argument applies to <functional dependencies> within the <database relation> $R$; dependencies belonging to unrelated <database relations> do not constrain its <candidate keys>.
Back to article page
