Richard's Database Design


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) | e1E1, e2E2, …, enEn} 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_namebuilding, 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.