DB C6 Relational Database Design

First Normal Form, 1NF

RECALL

Domain is atomic if its elements are considered to be indivisible units.

• dealing with non-atomic:

  • Composite attributes : a number of attributes
  • Multi-value attribute : multi-fields / separate table / single field
  • Complex data type : a number of attributes

• Drawbacks of non-atomic strategy:

  • Complicate storage

  • Encourage redundant storage of data

  • Complicated to query

A relational schema $R$ is in first normal form,1NF if the domains of all attributes of $R$ are atomic.

• For the relational database, it’s required that all relations are in 1NF.
• Atomicity is actually a property of how the elements of the domain are used.

Pitfalls in Relational Database Design

Relational database design requires that we find a “good” collection of relation schemas.

A bad design may lead to:

• Redundant storage: Wastes space / Easy to result in inconsistency.
• insert / delete / update anomalies : complicated / many null which is difficult to handle.
• inability to represent certain information.

Two design methods

• Top-down
• Button-up: Universal relation (泛关系) $\Rightarrow$ decomposition $\Rightarrow$ good database schema

Functional Dependencies

Let $R$ be a relation schema, $\alpha$ and $\beta$ be attributes, i.e $\alpha,\beta \sube R$

The functional dependency $\alpha \rightarrow \beta$ holds on $R$ if and only if for any legal relations $r(R)$, whenever any two tuples $t_1$ and $t_2$ of $r$ agree on the attributes $\alpha$, they also agree on the attributes $\beta$, i.e

$$\forall t_1,t_2 \in r, t_1[\alpha] = t_2[\alpha] \rightarrow t_1[\beta] = t_2[\beta]$$

We say $\beta$ is functionally dependent on $\alpha$, $\alpha$ functionally determines $\beta$.

• Functional dependency is a kind of integrity constraints, expressing the relationship of values on specific attributes.

• Functional dependency can be used to judge schema normalization and to suggest refinements.

Functional dependency vs. key

• A functional dependency is a generalization of the notion of a key.

• $K$ is a superkey for the relation schema $R$ if and only if $K \rightarrow R$ .

• $K$ is a candidate key for $R$ if and only if $K\rightarrow R ,\lnot\exist\alpha \sube K,\alpha \rightarrow R$.

• Functional dependencies allow us to express constraints that cannot be expressed using keys.

Usage

• Test relations to see if they are legal under a given set of functional dependencies $F$.

  If a relation $r$ is legal under a set $F$ of functional dependencies, we say that $r$ satisfies $F$.

• Specify constraints ($F$) on the set of legal relations — schema.

  We say that $F$ holds on $R$ if all legal relations $r$ on $R$ satisfy the set of functional dependencies $F$.

Trivial and Non-Trivial

• $ a\rightarrow b$ is trvial if $b \sube a$,
• otherwise, is non-trivial

Closure

Closure of a Set of Functional Dependencies

Given a set of functional dependencies $F$, the set of all functional dependencies logically implied by $F$ is the closure of $F$, denoted by $F^+$ .

Computing

F+ = F 
	Repeat 
		For each functional dependency f in F+ 
		       Apply reflexivity and augmentation rules on f 
		       Add the resulting functional dependencies to F+ 
		For each pair of functional dependencies f1and f2 in F+ 
		       If f1 and f2 can be combined using transitivity 
		       Then add the resulting functional dependency to F+ 
	Until F+ does not change any further 

The maximum number of possible Functional Dependencies (FDs) is $2^n \times 2^n$, for $n$ attributes.

Armstrong’s Axioms

• reflexivity, 自反律: If $b \sube a$,then $a \rightarrow b$
• augmentation, 增补律: If $a \rightarrow b$,then $ga \rightarrow gb$
• transitivity, 传递律: If $a \rightarrow b,b\rightarrow g$,then $a \rightarrow g$

• The reflexivity is trivial.
• Based on augmentation: If $a \rightarrow b$,then $ga \rightarrow gb$; By reflexivity, $gb \rightarrow b$; By transitivity, $ga \rightarrow b$.
• These rules are
  • Sound, 保真的: generate only functional dependencies that actually hold.
  • Complete, 完备的: generate all functional dependencies that hold.

Additional Armstrong’s Axioms

• union,合并律: If $a \rightarrow b,a\rightarrow c$, then $a\rightarrow bc$
• decomposition, 分解律: If $a\rightarrow bg$, then $a \rightarrow b,a \rightarrow g$.
• pseudo transitivity, 伪传递律: If $a\rightarrow b,bg\rightarrow d$, then $ag \rightarrow d$.

Closure of Attribute Sets

Given a set of attributes $a$, the closure of $a$ under $F$, denoted by $a^+$, is the set of attributes that are functionally determined by $a$ under $F$.

• $a \rightarrow b \Leftrightarrow b \sube a^+$
• $a$ is superkey $ \Leftrightarrow a \rightarrow R \Leftrightarrow R \sube a^+$
• $a$ is a candidate key for $R$ $\Leftrightarrow R \sube a^+ ,\forall b \sube a,R \not\sube b^+$.

Computing $a^+$:

result := a; 
while (changes to result) do 
  	for each fd(b,g) in F do begin 
    	If (all b in result) then
        	result := union(result,g)  
	end; 
a+ := result 

Uses of Attribute Set Closure

• Testing for a superkey: $a\rightarrow R \Leftrightarrow R \sube a^+$

• Testing functional dependencies: $a \rightarrow b \Leftrightarrow b \sube a^+$

  a simple and cheap and very useful test.

• Computing the closure of $F$ ,$F^+$

  1. For each $g \sube R$, we find $g^+$.
  2. For each $S \sube g^+$, we output a functional dependency $g \rightarrow S$.
  3. All $g \rightarrow S$ form $F^+$.

Canonical Cover

DBMS should always check to ensure not violate any Functional Dependency (FD) in $F$. $F$ may be simplified!

Intuitively, a canonical cover of $F$, denoted by $F_c$, is a minimal set of FDs equivalent to $F$:

$$F_c \overset{Logically}{\underset{imply}{====}}F$$

• Having no redundant FDs and no redundant parts of FDs;
• Each left side is unique.

Computing

1. Sets of Functional Dependency (FD) may have redundant dependencies that can be inferred from the others.

2. Parts of a functional dependency on left side may be redundant.

3. Parts of a functional dependency on right side may be redundant .

   Extraneous Attributes, 无关属性

   Consider $a \rightarrow b$ in $F$.

   • Attribute $A$ is extraneous in $a$, if $A \in a$ and $F$ logically implies $F' = (F – \left\{a \rightarrow b\right\}) \cup \left\{(a – A) \rightarrow b\right\}$.
   • Attribute $B$ is extraneous in $b$, if $B \in b$ and $F$ logically implies $F' = (F – \left\{a \rightarrow b\right\}) \cup \left\{a \rightarrow (b - B)\right\}$.

Decomposition

Requirements

• All attributes of an original schema $R$ must appear in the decomposition $R_1,R_2$ i.e

  $$R = R_1 \cup R_2$$

• Lossless-join decomposition (无损连接分解), i.e for all possible relations $r$ on schema $R$

  $$r = \Pi_{R_1}(r) \Join \Pi_{R_2}(r)$$

  A decomposition of $R$ into $R_1$ and $R_2$ is lossless-join if and only if at least one of the following dependencies are held in $F^+$:

  • $\{R_1 \cap R_2\} \rightarrow R_1$
  • $\{R_1 \cap R_2\} \rightarrow R_2$

• dependency preservation (依赖保持)： But may not be satisfied.

Boyce-Codd Normal Form, BCNF

A relation schema $R$ is in BCNF, with respect to a set $F$ of functional dependencies, if for all functional dependencies in $F^+$ of the form $a \rightarrow b$ , where $a \sube R$ and $b \sube R$ , at least one of the following holds:

• $a \rightarrow b$ is trival
• $R \sube a^+$

Any relation schema with two attributes is in BCNF.

Testing

Testing for BCNF is to check if a non-trivial dependency $a \rightarrow b$ causes a violation of BCNF.

• Compute $a^+$
• Verify that if $R \sube a^+$

Simplified Test

If none of the dependencies in $F$ causes a violation of BCNF, then none of the dependencies in $F^+$ will cause a violation of BCNF either.

However, using only $F$ to test for BCNF may be incorrect when testing a relation $R_i$ in a decomposition of $R$.

Computing

result := {R}; 
done := false; 
compute F+;   //shown before          
while (not done) do 
	if (there is a schema Ri in result that is not in BCNF) 
		then begin 
		    let a -> b be a nontrivial functional 
		    dependency that holds on Ri such 
		    that a -> Ri is not in F+, and a AND b = empty; 
		    result := (result – Ri) UNION (a, b) UNION (Ri – b); 
	    end	
	    else done := true; 

Finally, every sub-schema is in BCNF, and the decomposition is lossless-join.

Third Normal Form, 3NF

A relation schema $R$ is in third normal form (3NF) if for all $a \rightarrow b$ in $F^+$, at least one of the following conditions holds:

• $a \rightarrow b$ is trivial
• $R \sube a^+$.
• Each attribute $A$ in $b - a$ is contained in a candidate key for $R$. (即$A \in b - a$是主属性, 若$a\cap b = \phi$, 则A = b是主属性).

• each attribute may be in a different candidate key.
• 国内其他教材关于3NF的定义: 不存在非主属性对码的部分依赖和传递依赖。即, 当$b$为非主属性时, $a$必须是码; 但当$b$为主属性时, 则$a$无限制。
• There is always a lossless-join, dependency-preserving decomposition into 3NF.

Testing

We just need to check only FDs in $F$, need not check all FDs in $F^+$.

• Use attribute closure to check for each dependency $a \rightarrow b$, to see if $a$ is a superkey.

• If $a$ is not a superkey, we have to verify if each attribute in $b$ is contained in a candidate key of $R$.

  • This test is rather more expensive, since it involve finding all candidate keys.
  • Testing for 3NF has been shown to be NP-hard.
  • Decomposition into 3NF can be done in polynomial time.

Computing

Let Fc be a canonical cover for F; 
i := 0; 
for each functional dependency a -> b in Fc do 
	if none of the schemas Rj, 1 <= j <= i, contains ab 
	      then begin 
		    i := i  + 1; 
		    Ri := ( ) 
	      end
if none of the schemas Rj, 1 <= j <= i, contains a candidate key for R then 
begin 
	i := i  + 1; 
	Ri := any candidate key for R; 
end 
return (R1, R2, ..., Ri) 

BCNF vs. 3NF

Multivalued Dependencies, MVD

Fourth Normal Form