Relational Database Design and SQL Basics Relational ...
嚜燎elational Database Design
and
SQL Basics
CPS 216
Advanced Database Systems
Relational design: a review
?
?
?
?
?
Identifying tuples: keys
Generalizing the key concept: FDs
Non-key FDs: redundancy
Avoiding redundancy: BCNF decomposition
Preserving FDs: 3NF
2
BNCF = no redundancy?
? Student (SID, CID, club)
每 Suppose your classes have nothing to do with the
clubs you join
每 FDs?
每 BNCF?
每 Redundancies?
SID
142
142
142
142
123
123
#
CID
CPS 216
CPS 216
CPS 214
CPS 214
CPS 216
CPS 216
#
club
ballet
sumo
ballet
sumo
chess
golf
#
3
1
Multi-valued dependencies
? A multi-valued dependency (MVD) has the form
X ↙↙ Y, where X and Y are sets of attributes in a
relation R
? X ↙↙ Y means that whenever two tuples in R
agree on all the attributes of X, then we can swap
their Y components and get two new tuples that
are also in R
4
MVD examples
Student (SID, CID, club)
5
Complete MVD + FD rules
? FD reflexivity, augmentation, and transitivity
? MVD complementation:
If X ↙↙ Y, then X ↙↙ attrs(R) 每 X 每 Y Try proving
dependencies
? MVD augmentation:
If X ↙↙ Y and V ? W, then XW ↙↙ YV with these!?
? MVD transitivity:
If X ↙↙ Y and Y ↙↙ Z, then X ↙↙ Z 每 Y
? Replication (FD is MVD):
If X ↙ Y, then X ↙↙ Y
? Coalescence:
If X ↙↙ Y and Z ? Y and there is some W disjoint from
Y such that W ↙ Z, then X ↙ Z
6
2
An elegant solution: chase
? Given a set of FDs and MVDs D, does another
dependency d (FD or MVD) follow from D?
? Procedure
每 Start with the hypotheses of d, and treat them as
※seed§ tuples in a relation
每 Apply the given dependencies in D repeatedly
? If we apply an FD, we infer equality of two symbols
? If we apply an MVD, we infer more tuples
每 If we infer the conclusion of d, we have a proof
每 Otherwise, if nothing more can be inferred, we have a
counterexample
7
Proof by chase
? In R (A, B, C, D), does A ↙↙ B and B ↙↙ C
imply A ↙↙ C?
8
Counterexample by chase
? In R (A, B, C, D), does A ↙↙ BC and CD ↙ B
imply A ↙ B?
9
3
4NF
? A relation R is in Fourth Normal Form (4NF) if
每 For every non-trivial MVD X ↙↙ Y in R, X is a
super key
每 That is, all FDs and MVDs follow from ※key ↙ other
attributes§
? 4NF is stronger than BCNF
10
4NF decomposition algorithm
? Find a 4NF violation
每 A non-trivial MVD X ↙↙ Y in R where X is not a super key
? Decompose R into R1 and R2, where
每 R1 has attributes X ﹍ Y
每 R2 has attributes X ﹍ Z (Z contains attributes not in X or Y)
? Repeat until all relations are in 4NF
? Almost identical to BCNF decomposition algorithm
? Any decomposition on a 4NF violation is lossless
11
4NF decomposition example
Student (SID, CID, club)
SID
142
142
142
142
123
123
#
CID
CPS 216
CPS 216
CPS 214
CPS 214
CPS 216
CPS 216
#
club
ballet
sumo
ballet
sumo
chess
golf
#
12
4
3NF, BCNF, and 4NF
3NF
BCNF
4NF
Preserves FDs?
Redudancy due to FDs?
Redundancy due to MVDs?
13
Recap
? Another source of redundancy: MVDs
? Reasoning about FDs and MVDs: chase
? Avoiding redundancy due to MVDs: 4NF
14
A complete design example
? Information about parts and assemblies for a
manufacturing company; e.g.:
每 A bicycle consists of one frame and two wheels; the
cost of assembly is $30
每 A frame is just a basic part
每 A wheel consists of one tire, one rim, and 48 spokes;
the cost of assembly is $40
每 Everything has a part ID and a name
15
5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- constraints types of sql constraints duke university
- cs1307 database management systems lab manual
- create table students virginia tech
- sumita arora xii structured query language
- oracle sql tutorial emory university
- sql to hive cheat sheet cloudera
- defining relational schema cs 2451 database systems
- the relational model carnegie mellon school of computer
- sql data types and schemas integrity constraints
- chapter 4 advanced sql date and time data types in sql
Related searches
- database design tutorial for beginners
- access database design best practices
- database design best practices microsoft
- access database design pdf
- access database design basics
- access database design examples
- access database design tutorial
- ms access database design tutorial
- database design best practices
- database design normalization
- relational database normalization pdf
- example of relational database model