16-01-2013, 03:18 PM
Database Design and Normal Forms
1Database Design.pdf (Size: 595.83 KB / Downloads: 57)
why normal forms?
- format standardization (1NF)
- reduction/elimination of redundancies (2NF, 3NF, ...)
conceptual tool for improving database design quality
in practice, however: redundancy vs. efficiency
- redundant data may lead to inconsistencies after
updates
- but useful for efficiency reasons (shorter response
times)
tradeoff problem: to be decided case by case
2nd Normal Form (2NF)
The relation R is in 2NF IF:
(1) It is in 1NF AND
(2) For all non-trivial functional dependencies X → A in R,
one of the following conditions is true:
(2.1) X is no real subset of at least one key of R OR
(2.2) A is key attribute (i.e., part of at least one key of R)
(“non-trivial”: attribute A not contained in attribute set X)
Note: if R has only one key, this is equivalent to:
1 NF + each non-key attribute is fully functionally dependent
on the key, i.e., it can not be inferred from part of the key
This is obviously true for one-column keys, therefore all
relations with only one one-column key are in 2NF
How to decompose a non-3NF
relation into 3NF?
Given: relation R, set F of functional depencies
Find: decomposition of R into a set of 3NF relations Ri
Algorithm:
(1) Eliminate redundant FDs, resulting in a minimal set F
(2) Create a separate relation Ri = A for each attribute A
that does not occur in any FD in F;
(3) Create a relation Ri = XA for each FD X →A in F;
(4) If the key K of R does not occur in any relation Ri,
create one more relation Ri = K
Decomposition produces a lossless join and preserves
dependencies
Dense vs. Sparse Indices
• relations are stored in blocks (pages) on the magnetic disk
• crucial cost factor: how many blocks to I have to transfer from disk
to main memory in order to answer the query?
• non-dense (or sparse) index: one index entry per block
- for a primary index it suffices to store the smallest key value per block
- index supports the system when looking for the relevant block(s)
- inside each block: local search (cf. telephone directory)
- useful for large relations because very compact
- only possible for columns according to which the relation
has been sorted (cf. phone directory)
- therefore: at most one sparse index per relation
• dense index: one index entry per tuple