Relational Database Design 6t3s42

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: •

•

In inst_dept, because dept_name is not a candidate key, the building and budget of a department may have to be repeated. o

•

dept_name → building, budget

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- Decomposition

•

Lossless 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 s stored with each customer, and set of owners stored with each

•

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- 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 

•

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

•

We say that F holds on R if all legal relations on R satisfy the set of functional dependencies F.

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

o

Example: 

ID, name → ID



name → name

In general, α → β is trivial if β ⊆ α