Databases - Normalization

ohsobeezee23's version from 2016-11-03 21:39

Section 1

Question Answer
Redundant storageSome info is stored repeatedly
Insertion anomaliesMay not be possible to store certain info unless osme other (unrelated) info is stored as well
Deletion anomaliesMay not be possible to delete certain indo without losing some other (unrelated) info os stored as well
Update anomaliesIf one copy of such repeated data is updated, an inconsistency is created unless all copies are similarly updated
Functional DependenciesIntegrity constraints that can be used to identify schemas with such problems and to suggest refinements
Decomposition Splits a table into many tables, each with fewer attributes(Eg, replace R(A,B,C,D) with R1(A,B) R2(B,C,D))
An example of inferring functional dependencies(eID -> dID) and (dId -> addr) implies (eID->addr)
Dependency ClosureF+ = te set of all functional dependencies that are implied by a set of FDs F
Dependency closure example{(eID ->dId), (dID-> addr)}+ = {(eID->dID),(dID->addr),(eID->addr)}
Attribute closure X+ = the set if all attrs that are limited by a set of attrs X wrt F
Attribute closure examples{eID}+ = {eID,dID,addr} eg2 {dID}+ = {dID,addr} eg3 {eID,dID}+ = {eID,dID,addr}

Section 2

Question Answer
Armstrongs AxiomsReflexivity, Augmentation, Transitivity
ReflexivityIf Y⊆R, then X->Y
AugmentationIf X->Y, then XZ -> YZ for all Z
Transitivityif (X->Y) and (Y->Z), then X-> Z
UnionIf (X->Y) and (X->Z), then X->YZ
DecomositionIf X->YZ, then (X->Y) and (X->Z)
Prove: If (X-> Y) and (WY->Z), then WX->Z

1. X->Y given(FD1)

2.WX->WY augmentation(W)

3. WY->Z given(FD2)

4. WX-> Z 2,3,transitivity


Normal Forms

Question Answer
Normalizationthe process of removing redundancy from data
1st Normal formif every attribute contains only atomic values (no lists, or sets) every cell must have one attribute in it
2nd Normal formRelation is in 1NF, and every attribute of A in R either appears in a candidate key or is not partially dependent on a candidate key (i.e no partial key dependency)
3rd Normal formA relation R is in 3NF if

1. R is in 2NF, and

2. for every functional dependency X->A, one of the following conditions hold:

i. Ais part of some candidate keys for R, or

ii.A belongs to X (Trivial FD) or

X is a superkey

i.e, no partial dependency and no transitive dependency

BCNF (Boyce-Codd NF)A relation R is in BCNF if for every Functional dependecy X->A that holds over R, one of the following is true:

A belongs to X (trivial FD), or

ii. X is a superkey

(i.e, all determinants X must be superkeys)


NF Shortcuts

Question Answer
1NFNo lists
2NFUse ALL of a candidate key in all FDs
3NFNo transitivity in FDs
BCNFAll determinants are superkeys

Recent badges