Relational-Database-Design-Functional-Dependency

Functional dependencies are some constraints on the set of legal relations. The constraint is that the value for a certain set of attributes uniquely determines the value for another set of attributes. 约束条件是一组属性的值唯一确定另一组属性的值 A functional dependency is a generalization of the notion of a key. 功能依赖关系是键概念的泛化

Functional Dependency Property 功能依赖

• $K$ is a super key for relation schema iff $K\to R$

• $K$ is a condidate key for $R$ iff $K\to R$ and for no $\alpha \notin K,\alpha \to R$

• Functional dependencies can express constraints that cannot be expressed using superkeys. For example:

$cours{e}_{i}nfo=(\underset{―}{c\mathrm{\_}name,p\mathrm{\_}code},credits,domain,c\mathrm{\_}number)$

We can use functional dependency to hold

$c\mathrm{\_}name\to credits$

But would not expect the following to hold:

$credits\to c\mathrm{\_}name$

• we can use functional dependency to specify constraints on the set of legal relations

• Trivial A functional dependency is trivial if it is satisfied by all instances of a relation. Equivalently, If $\beta \subseteq \alpha $, then $\alpha \to \beta$ is trivial. Example: $(credits,domain,c\mathrm{\_}number\to c\mathrm{\_}number)$$(c\mathrm{\_}name\to c\mathrm{\_}name)$

Closure of a Set of Functional Dependencies 功能依赖的闭包

The set of all functional dependencies logically implied by $F$ is the closure of $F$, denoted by $F^{+}$.

$F^{+}$ is a superset of $F$.

How to find $F^{+}$

• Applying Armstrong's Axioms
  1. reflexivity
     • if $\beta \subseteq \alpha ,$ then $\alpha \to \beta$
  2. augumentation
     • if $\alpha \to \beta ,$ then $\gamma \alpha \to \gamma \beta$ for any $\gamma$.
  3. transitivity
     • if $\alpha \to \beta$ and $\beta \to \gamma$, then $\alpha \to \gamma .$
• These rules are sound and complete.

This method is also apply in Attribute Closure.

Prove Armstrong's Axioms

For Union: If $\alpha \rightarrow \beta $ and $\alpha \to \gamma ,$ then $\alpha \to \gamma \beta$

1. $\alpha \to \beta$
2. $\alpha \alpha \to \alpha \beta$ According to augmentation
3. $\alpha \to \alpha \beta$
4. $\alpha \to \gamma$
5. $\alpha \beta \to \gamma \beta$
6. $\alpha \to \alpha \beta \to \beta \gamma$ According to transitivity
7. $\alpha \to \beta \gamma$

For Decomposition: if $\alpha \to \beta \gamma$, then $\alpha \to \beta$ and $\alpha \to \gamma$

1. $\alpha \to \beta \gamma$
2. $\beta \gamma \to \beta$ according to reflexivity
3. $\beta \gamma \to \gamma$ according to reflexivity
4. $\therefore \alpha \to \beta ,\alpha \to \gamma$ according to transitivity

For pseudotransitivity if $\alpha \to \beta$ and $\gamma \beta \to ϵ$ then $\alpha \gamma \to ϵ$

1. $\because \alpha \to \beta$
2. $\therefore \alpha \gamma \to \beta \gamma$ according to augmentation
3. $\because \alpha \gamma \to \beta \gamma \to ϵ$ according to transitivity
4. $\therefore \alpha \gamma \to ϵ$