Database
Ch8.relational design
8.1 features of good design
8.1.1 larger alternatives
why design is good ?
Otherwise ,a larger alternative(schema) may cause:
1)redundancy
2)update may cause inconsistency
3)update may bring nulls
8.1.2 smaller alternatives
Functional dependency : A-->B, i.e.A determines uniquely B (a kind of function relation , injection) ,lead to repetition in schema.
//An e.g. of bad deposition.
So,how do we make a smaller alternative(schema)?
It is impossible to divide a larger schema into a smaller one by means of finding repetition caused by join(why impossible? large amount of data and unknown of relations int the real world).
What matters is the the functional dependency(the rules in the real world).
On the other hand,a smaller alternative(schema) may cause:
1) lossy decomposition.which means when you decompose relation X,getting Y&Z.You will find Y join Z !=X.
8.2 atomic domains &1st normal form
atomic if elements of the domain are considered to be indivisible units.
a relation schema R is in first normal form (1NF) if the domains of all attributes of R are atomic.
Discuss in whether cs0114 is an atomic domain.
8.3 Decomposition Using Functional Dependencies
Recall notation
1)Roman letter stands for a relation set while Greek letter for other attribute set(always one attribute).
2)K is a super-key of r (R).(candidate key is a minimal super-key )
3)we use single lowercase letter in our definitions and algorithms,not for eg. Instructor.
4)instance of r means a particular value at some given time.
8.3.1 Keys and Functional Dependencies
Define :relations have feature of functions .
α → β holds on R if and only if for any legal relations r(R), whenever any
two tuples t1 and t2 of r agree on the attributes α, they also agree
on the attributes β. That is,
t1[α] = t2 [α] ⇒ t1[β ] = t2 [β ]
We say that the instance satisfies the functional Dependency
We say that the functional dependency α → β holds on schema r (R)
A functional dependency is trivial if it is satisfied by all instances of a relation
Example:
4 ID, name → ID
4 name → name
l In general, α → β is trivial if β ⊆ α Some times α !→ β but alpha,gamma->beta.
(i.e.. In some special instance of instructor,name may ->ID,but it is not true for all instances)
notation F+ to denote the closure(satisfy transitive) of the set F,
8.3.2 Boyce–Codd Normal Form
Boyce–Codd normal form (BCNF) eliminates all redundancy that can be discovered based on functional dependencies.
Formal definition
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
α → β
where α ⊆ R and β ⊆ R, at least one of the following holds:
1)α → β is trivial (i.e., β ⊆ α)
2)nα is a superkey for R
In other words,BCNF requires that all nontrivial dependencies be of the form α → β , where α is a superkey.
In other words,BCNF requires that all α → β ,where α is not super key , to be trivial.
Suppose we have a schema R and a non-trivial dependency α →β
causes a violation of BCNF.
We decompose R into:
• (α U β )
• ( R - ( β - α ) )
It’s quite reasonable.
8.3.3 BCNF and Dependency Preservation
About testing constrains.
Constraints, including functional dependencies, are costly to check in practice unless they pertain to only one relation
A decomposition is dependency preserving.If it is sufficient to test only those dependencies on each individual relation of a decomposition in order to ensure that all functional dependencies hold
It is not always possible to achieve both BCNF and dependency preservation(in some cases, decomposition into BCNF can prevent efficient testing of certain functional dependencies.)
, we consider a weaker normal form, known as third normal form.
When a dependency whose attributes do not all appear in any one schema we call it is not dependency preserving.
BCNF is not dependency preserving but 3rdNF is.
second normal(满足第一范式且不存在partial dependency（部分依赖）the 3rd rule of 3rd NF) form is of historical significance only and is not used in practice.
8.3.4 Third Normal Form
A relation schema R is in third normal form (3NF) if for all:
α → β in F+
at least one of the following holds:
l α → β is trivial (i.e., β ∈ α)
l α is a superkey for R
l Each attribute A in β – α is contained in a candidate key for R.
(NOTE: each attribute may be in a different candidate key)
BCNF requires that all nontrivial dependencies be of the form α→β , where α is a superkey.
Third normal form (3NF) relaxes this constraint slightly by allowing certain nontrivial functional dependencies whose left side is not a superkey.
Third condition is a minimal relaxation of BCNF to ensure dependency preservation (will see why later).
Normalization:
In the case that a relation scheme R is not in “good” form,
decompose it into a set of relation scheme {R1, R2, ..., Rn} such that
l each relation scheme is in good form
l the decomposition is a lossless-join decomposition
l Preferably, the decomposition should be dependency preserving
8.4 8.5 8.6:theorem &&algorithm for decomposition using NF