Hamish Burke | 2025-05-22

Related to: #databases

Attribute Closure

• The set of $X\star$ of all attributes that $X$ functionally determines using $F$

Compute $X\star$

1. Initialise $X\star =X$
2. For each FD $Y\to Z$ in F, if $Y\in X\star$ then add $Z$ to $X\star$
3. Repeat until no new attributes can be added

X is a superkey is $X\star$ contains all attributes, a candidate key if $X$ is a superkey and no proper subset of $X$ is a superkey

Example

R(A,B,C,D), F{AB->C,C->D}

Compute $\{A,B\}\star$

1. Start with $\{A,B\}$
2. For AB->C, AB is a subset of $\{A,B\}$, so add $C$
3. Now its $\{A,B,C\}$
4. For C->, C is a subset of $\{A,B,C\}$, so add $D$
5. Now its $\{A,B,C,D\}$
6. Nothing else would make it grow, so stop
7. $\{A,B\}\star =\{A,B,C,D\}$

Compute $\{A\}\star$

1. Start with $\{A\}$
2. For AB->C, AB is not a subset of $A$, do nothing
3. For C->D, C is not a subset of $A$, do nothing
4. $\{A\}\star =\{A\}$