Useful Links
SQL Examples
This page references concepts and examples from the textbook "Database System Concepts, 6/e" by Silberschatz, Korth, and Sudarshan; and some other tutorial sites.
Database Design Fundamentals
So… someone asked you (or paid you) to build a web application or a mobile application or a desktop application, or any software application (like the weapon inventory system of the Starship Enterprise) …. and you realized that you need a not so simple database. Oops, suddenly, the concepts from the much hated database class came back to you. How to avoid data redundancy? How to maintain data integrity? What is relational algebra? How to make your database efficient? How not to get into trouble (lose time/resources/data) after six months (or thirty years) into this project?
A good database design is a good starting point. (or else… good luck)
Database Design Process
So... how to start? (Section 8.8 of [1])
Design Goals (Section 8.5.4 of [1]) of a relational database
But... sometimes we cannot achieve this... so... we may choose
Chapter 7: Entity-Relationship Model [1]
An entity is an object that exists and is distinguishable from other objects. (row of a table)
Entities have attributes
An entity set is a set of entities of the same type that share the same properties. (table)
A relationship is an association among several entities
A relationship set is a mathematical relation among n >= 2 entities, each taken from entity sets. (table)
{(e1, e2, … en) | e1 ∈ E1, e2 ∈ E2, …, en ∈ En}where (e1, e2, …, en) is a relationship (row of a table), ei is an object (entity, or row of a table) in a entity set, Ei is a entity set (table)
Degree of a Relationshp set
Domain - set of permitted values for each attribue
Attribute types (diagram: slide 7.18)
Cardinality Constraints
Keys
E-R Diagrams (diagram: slide 7.17)
Weak Entity Sets (diagram: slide 7.32)
7.6 Reduction to Relational Schemas (something extra)
Entity sets and relationship sets can be expressed uniformly as relation schemas that represent the contents of the database.
Entity Sets (examples):
Relationship Sets (example):
Redudancy of Schemas, to reduce number of tables
Composite and Multivalued Attributes
Converting Non-Binary Relationships to Binary Form (slide 7.48)
Chapter 2: Intro to Relational Model [1]
Schema Diagram (slide 2.8), note the difference between schema diagram and E-R diagram (ch 7)
Summary of relational query language symbols (slide 2.18)
Chapter 4: Intermediate SQL [1]
Useful SQL syntax in chapter 3 slides
Outer Join (slide 4.3) - computes join, avoids loss of information, add tuples from one relation (table) that does not match tuples in other relation (table), uses null value
Referential Integrity (foreign key): (slide 4.28)
Chapter 8: Relational Database Design (Normalization) [1]
Lossy Decomposition - decompose a relation (say split a table into two tables), cannot reconstruct the original relation (table) correctly
First Normal Form (1NF)
Functional Dependencies
Boyce-Codd Normal Form (BCNF)
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:
Example schema not in BCNF:
instr_dept (ID, name, salary, dept_name, building, budget )
because dept_name → building, budget
holds on instr_dept, but dept_name is not a superkey
Third Normal Form (3NF)
A relation schema R is in third normal form (3NF) if for all:
α → β
in F+ ; at least one of the following holds:
If a relation is in BCNF it is in 3NF (since in BCNF one of the first two conditions above must hold). Third condition is a minimal relaxation of BCNF to ensure dependency preservation.
Or simply put... 3NF = no transitive dependency.
Goals of Normalization
Let R be a relation scheme with a set F of functional dependencies. Decide whether a relation scheme R is in “good” form.
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
Closure of a Set of Functional Dependencies
We can find F+, by repeated applying Armstrong's Amions:
Algorithm: Procedure for Computing F+ (slide 8.28)
Algorithm: Closure of Attribute Sets (slide 8.30), can be used for
A canonical cover of F is a “minimal” set of functional dependencies equivalent to F, having no redundant dependencies
Extraneous attributes (slide 8.34). Testing if an attribute is extraneous (algorithm) (slide 8.35).
Algorithm: to compute canonical cover for F (slide 8.36)
Lossless-join decomposition (slide 3.38)
Dependency preservation: A decomposition is dependency preserving if (F1 ∪ F2 ∪ … ∪ Fn )+ = F +
Algorithm: Testing for dependency preservation (slide 8.41)
Testing for BCNF; Testing decomposition for BCNF;
Algorithm: DCNF Decomposition (slide 8.45); BCNF and dependency preservation (slide 8.49)
Testing for 3NF (slide 8.53) - NF-hard (decomposition is not)
Algorithm: 3NF Decomposition (slide 8.54)
References
[1] A. Silberschatz, H. Korth, S. Sudarshan, "Database System Concepts", McGraw-Hill, 6th edition, 2010.