RELATIONAL DATABASE DESIGN
FEATURES OF GOOD RELATIONAL DESIGN
Combine Schemas?
• Suppose we combine instructor and department into inst_dept
o (No connection to relationship set inst_dept)
• Result is possible repetition of information
A Combined Schema Without Repetition
• Consider combining relations
o sec_class(sec_id, building, room_number) and
o section(course_id, sec_id, semester, year)
• into one relation
o section(course_id, sec_id, semester, year,
building, room_number)
• No repetition in this case
What About Smaller Schemas?
• Suppose we had started with inst_dept. How would we know to split up (decompose) it
into instructor and department?
• Write a rule “if there were a schema (dept_name, building, budget), then dept_name
would be a candidate key”
• Denote as a functional dependency:
• dept_name → building, budget
• In inst_dept, because dept_name is not a candidate key, the building and budget of a
department may have to be repeated.
o This indicates the need to decompose inst_dept
• Not all decompositions are good. Suppose we decompose
employee(ID, name, street, city, salary) into
employee1 (ID, name)
employee2 (name, street, city, salary)
• The next slide shows how we lose information -- we cannot reconstruct the original
employee relation -- and so, this is a lossy decomposition.
• A Lossy Decomposition
• Example of Lossless-Join Decomposition
• Lossless join decomposition
• Decomposition of R = (A, B, C)
R1 = (A, B) R2 = (B, C)
First Normal Form
• Domain is atomic if its elements are considered to be indivisible units
o Examples of non-atomic domains:
Set of names, composite attributes
Identification numbers like CS101 that can be broken up into parts
• A relational schema R is in first normal form if the domains of all attributes of R are
atomic
• Non-atomic values complicate storage and encourage redundant (repeated) storage of
data
o Example: Set of accounts stored with each customer, and set of owners stored
with each account
• We assume all relations are in first normal form
• Atomicity is actually a property of how the elements of the domain are used.
o Example: Strings would normally be considered indivisible
o Suppose that students are given roll numbers which are strings of the form
CS0012 or EE1127
o If the first two characters are extracted to find the department, the domain of roll
numbers is not atomic.
o Doing so is a bad idea: leads to encoding of information in application program
rather than in the database.
• Goal — Devise a Theory for the Following
• Decide whether a particular relation R is in “good” form.
• In the case that a relation R is not in “good” form, decompose it into a set of relations
{R1, R2, ..., Rn} such that
o each relation is in good form
o the decomposition is a lossless-join decomposition
• Our theory is based on:
o functional dependencies
o multivalued dependencies
FUNCTIONAL DEPENDENCIES
• Constraints on the set of legal relations.
• Require that the value for a certain set of attributes determines uniquely the value for
another set of attributes.
• A functional dependency is a generalization of the notion of a key.
• Let R be a relation schema
α ⊆ R and β ⊆ R
• The functional dependency
• α →β
holds on R if and only if for any legal relations r(R), whenever any two tuples t1 and t2 of
r agree on the attributes α , they also agree on the attributes β . That is,
t1[α ] = t2 [α ] ⇒ t1[β ] = t2 [β ]
• Example: Consider r(A,B ) with the following instance of r.
• On this instance, A → B does NOT hold, but B → A does hold.
• K is a superkey for relation schema R if and only if K → R
• K is a candidate key for R if and only if
K → R, and
for no α ⊂ K, α → R
• Functional dependencies allow us to express constraints that cannot be expressed
using superkeys. Consider the schema:
inst_dept (ID, name, salary, dept_name, building, budget ).
We expect these functional dependencies to hold:
dept_name→ building
and ID à building
but would not expect the following to hold:
dept_name → salary
Use of Functional Dependencies
We use functional dependencies to:
o test relations to see if they are legal under a given set of functional
dependencies.
If a relation r is legal under a set F of functional dependencies, we
say that r satisfies F.
o specify constraints on the set of legal relations
We say that F holds on R if all legal relations on R satisfy the set
of functional dependencies F.
• Note: A specific instance of a relation schema may satisfy a functional
dependency even if the functional dependency does not hold on all legal
instances.
o For example, a specific instance of instructor may, by chance, satisfy
name → ID.
• A functional dependency is trivial if it is satisfied by all instances of a relation
o Example:
ID, name → ID
name → name
o In general, α → β is trivial if β ⊆ α
