Relational Model
CHAPTER 14
Copyright By PowCoder代写 加微信 powcoder
Basics of Functional Dependencies and Normalization for Relational Databases
Chapter 14 – Objectives
Normal forms beyond Third Normal Form (3NF)
How to identify Boyce– Form (BCNF).
How to represent attributes shown on a report as BCNF relations using normalization.
Chapter 14 – Objectives
Concept of multi-valued dependencies and Fourth Normal Form (4NF).
The problems associated with relations that break the rules of 4NF.
How to create 4NF relations from a relation, which breaks the rules of to 4NF.
Chapter 14 – Objectives
Concept of join dependency and Fifth Normal Form (5NF).
The problems associated with relations that break the rules of 5NF.
How to create 5NF relations from a relation, which breaks the rules of 5NF.
functional
dependencies
multivalued
dependencies
dependencies
HIGHER NORMAL FORMS
Review of Normalization
Reports are unnormalized data
UNF -> 1NF)
Reports contain repeating groups of data (UNF)
Identify FDs
Decomposition to higher forms
Boyce– Form (BCNF)
Based on functional dependencies that take into account all candidate keys in a relation, however BCNF also has additional constraints compared with the general definition of 3NF.
Boyce–Codd normal form (BCNF)
A relation is in BCNF if and only if every determinant is a candidate key.
Normalization
Boyce- Form (BCNF)
Boyce- Form:
If X A holds in R,
then X is a superkey of R,
Note: BCNF 3NF 2NF
Remember SuperKeys?
A subset of the relation attributes where all tuple values must be distinct.
SK is a set of attributes
t1 and t2 are tuples
Then, t1 [SK] t2 [SK]
Normalization
(Student, Subject, Teacher)
Smith Physics Green
Jones Math White
Jones Physics Brown
Narayan Database Mark
Database Navathe
Real world constraints:
Students have only 1 Teacher for a Subject (J)
Teachers teach only 1 Subject.
Candidate Keys
Normalization
Is SJT In 2NF AND 3NF?
2NF: R is in 1NF and every non-key attribute is fully dependent on the key
Yes. T is a non-key attribute. and dependent on all prime attributes
3NF: R is 2NF and every non-key attribute is non-transitively dependent on the key
It’s okay. T is not a part of the key, but then J is not a non-key attribute.
But, Is it weird to have a key attribute (J) dependent on a non-key (T)?
Boyce– Form (BCNF)
3NF allows T J, if J is a primary-key attribute and T is not a candidate key.
BCNF insists that for this dependency to remain in a relation, determinant must be a candidate key.
Every relation in BCNF is also in 3NF. However, a relation in 3NF is not necessarily in BCNF.
Boyce– Form (BCNF)
Violation of BCNF is quite rare.
The potential to violate BCNF may occur in a relation that:
contains two (or more) composite candidate keys;
the candidate keys overlap, that is have at least one attribute in common.
Normalization
(Student, Subject, Teacher)
Smith Physics Green
Smith database Navathe
Jones Math White
Jones Physics Brown
Narayan Database Mark
Database Navathe
Real world constraints:
Students have only 1 Teacher for a Subject (J)
Teachers teach only 1 Subject.
A subJect may be taught by several Teachers.
False: J T
A Student may take several subJects.
False: S J
Several Students may take a subJect from a Teacher.
False: T, J S
OK. S, J is a candidate key, thus a superkey.
Not OK. T is not a superkey.
Thus SJT is not in BCNF.
Candidate Keys
Normalization
BCNF Decomposition Theorem
For any relation R, there exists a non-loss decomposition of R into a set of BCNF relations.
Normalization
(Student, subJect, Teacher)
Smith Physics Green
Smith database Navathe
Jones Math White
Jones Physics Brown
Narayan Database Mark
Database Navathe
ST( Student, Teacher)
Jones White
Jones Brown
TJ ( Teacher, subJect)
White Math
Brown Physics
Navathe Database
Kerr Database
T J SJT = ST * TJ
Candidate Keys
Normalization
– Dependency not Preserved
ST( Student, Teacher)
Jones White
Jones Brown
TJ ( Teacher, Subject)
White Math
Brown Physics
Navathe Database
Kerr Database
Preserved in TJ: T J
Not Preserved: S, J T
Goal: Eliminate Redundancy with
No loss of data
No loss of functional dependencies
Can’t always satisfy both goals.
functional
dependencies
multivalued
dependencies
dependencies
HIGHER NORMAL FORMS
Multivalued Dependency
Multi-valued dependency (MVD) can also cause data redundancy.
Dependency between attributes sets in a relation, such that
For each value of A there is a set of values for B and a set of values for C.
However, B and C are independent of each other.
MVD – Example
For each branchNo, there is a sName and oName
But sName and oName are independent of each other
i.e. sName does not determine oName, or vice versa.
MVD Notation
MVD between attributes A, B, and C in a relation using the following notation:
branchNo ->> sName
branchNo ->> oName
Trivial MVD
A multi-valued dependency can be trivial or nontrivial.
MVD A −>> B in relation R is trivial if
B is a subset of A or
A B = R.
A trivial MVD does not specify a constraint on a relation
nonTrivial MVD
A multi-valued dependency can be trivial or nontrivial.
MVD A −>> B in relation R is nontrivial if
B is NOT a subset of A and
A B != R.
A nontrivial MVD specifies a constraint on a relation
Fourth Normal Form (4NF)
Defined as a relation that is in Boyce- Form and contains no nontrivial multi-valued dependencies.
i.e., for every nontrivial MVD,
X ->>Y, X is a superkey
Normalization
UNF often leads to MVD
PRESIDENT ->> LOSER
PRESIDENT ->> VP
Normalization
Multivalued Dependency (MVD)
Given R(A, B, C)
R.A ->>R.B
attribute R.B is multidependent on attribute R.A
R.A multidetermines attribute R.B
if the set of B-values matching a given (A-value, C-value) pair in R depends only on the A-value and is independent of the C-value.
As usual A, B, and C may be composite.
PRESIDENT ->> LOSER
PRESIDENT ->> VP
Normalization
R.A →→ R.B
if and only if
R.A →→ R.C
We can write
R.A →→ R.B | R.C
For example:
President →→ VP | Loser
4NF Theorem
Normalization
The relation R(A, B, C) can be non-loss decomposed into its two projections R1(A,B) and R2(A, C)
the multivalued dependency
A →→ B|C holds in R.
Any relation can be non-loss decomposed into an equivalent collection of 4NF relations.
If R is in 4NF, then it is also in BCNF.
4NF Theorem
Normalization
MVD resolved – 4NF
functional
dependencies
multivalued
dependencies
dependencies
HIGHER NORMAL FORMS
Join Dependencies
and Fifth Normal Form
Multiway decomposition into fifth normal form (5NF) to reduce redundancy in recording multi-valued facts
These are situations in which a complex real-world constraint governing the valid combinations of attribute values in the 4NF table is not implicit in the structure of that table.
Fifth Normal Form (5NF)
Defined as a relation that has no join dependency.
i.e., it cannot be recreated by joining multiple tables each having a subset of the attributes
Result of ternary relationships not properly resolved:
More informal guidelines for good design
Look at your Candidate keys and PKs
Minimize number of attributes in the key, introduce artificial PKs if needed
Other than using FK attributes, the rest of the attributes should be describing only one entity
Resolve n-nary relationships during DB schema design not after full DB implementation
Ex., Subjects Lecturer Semesters
Semester 1 has Mathematics, Physics and Chemistry
Semester 2 has only Physics
Constraint not implicit in the structure of that table.
Ex., Subjects Lecturer Semesters
All 3 fields are required to identify valid data
Want to add Semester 3, without knowing Lecturers and Subjects.
Can’t leave other attributes NULL (b/c keys)
Ex., Subjects Lecturer Semesters
Not in 5NF because,
adding records would cause redundancy or anomaly
We should decompose table so that each fact is defined separately
And no new data is created or lost
Ex., Subjects Lecturer Semesters
All tables in now in 4NF!
Also, all tables are in 5nf.
There is no join dependency.
Tables cannot be recreated by creating tables of subsets of attributes and joining.
To find Physics Lecturer in Semester1
SELECT t3.Class, t3.Subject, t1.Lecturer
FROM TABLE3 t3, TABLE3 t2, TABLE3 t1,
WHERE t3.Class = ‘SEMESTER1’ and
t3.SUBJECT= ‘PHYSICS’ AND
t3.Subject = t1.Subject AND
t3.Class = t2.Class AND
t1.Lecturer = t2.Lecturer;
Key columns of each table are joined to get the correct data. No data loss or gain.
Fifth Normal Form (PJNF)
A table is said to be in the 5NF or Project-Join Normal Form (PJNF) IFF
every join dependency in it is implied by the candidate keys.
it cannot have a lossless decomposition into any number of smaller tables.
Very rarely done in practice
Informal guidelines for good design
Functional dependency
Basic tool for analyzing relational schemas
Normalization:
1NF, 2NF, 3NF, BCNF, 4NF, 5NF
PVL(Unnormalized)
PRESIDENTVPLOSER
ClintonGoreBush,
QuayleDukakis
ReaganBushCarter,
MondaleFord
Ford Agnew,
PVL(Normalized)
PRESIDENTVPLOSER
ClintonGoreBush
ClintonGore QuayleDukakis
ReaganBush Bush MondaleFord
Ford AgnewMcGovern
NixonFord Ford FordMcGovern
PVPRESIDENTVP
ClintonGore
BushQuayle
ReaganBush
Carter Ford
PLPRESIDENTLOSER
ClintonBush
Clinton Dukakis
Reagan Ford
Sheet: Sheet1
(Normalized)
Agnew, Ford
Humphrey, Walace, McGovern
Humphrey, Walace, McGovern
Humphrey, Walace, McGovern
Humphrey, Walace, McGovern
PV PRESIDENT VP
Clinton Gore
Bush Quayle
Reagan Bush
Carter Ford
MBD0799844A.xls
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com