L5/6: Database Design Theory

Question 1

What is

Design Theory

about?

Answer 1

How to represent your data

in such a way that you

avoid Anomalies

caused by data redundancy, null values, etc

Question 2

What are

Armstrongs 4 Rules

used for?

Answer 2

Discovering Functional Dependencies

from Functional Dependencies that are already known

Question 3

Armstrong’s Rules

(names only)

Answer 3

• Reduction (trivial)
• Transitivity
• Augmentation
• Split/Combine

Question 4

Armstrong’s Rules:

Reduction

Answer 4

Given a set of attributes: X, Y, Z

If Y is a subset of X (Y is in X),

Then X is Functionally Dependent on Y

X → Y

This is kind of trivial.

Question 5

Armstrong’s Rules:

Transitivity

Answer 5

Given a set of attributes: X, Y, Z

If X is functionally dependent on Y (X → Y),

and Y is functionally dependent on Z ( Y → Z),

then X is functionally dependent on Z:

X → Y → Z, therefore X → Z

Question 6

Armstrong’s Rules:

Augmentation

Answer 6

Given a set of attributes: X, Y, Z

If X is functionally dependent on Y (X → Y),

then XZ is functionally dependent on YZ ( XZ → YZ):

X → Y, therefore XZ → YZ for any Z

Question 7

Armstrong’s Rules:

Split/Combine

Answer 7

Given a set of attributes: X, Y, Z

Combine:

If X is functionally dependent on Y (X → Y),

and X is functionally dependent on Z ( X → Z),

then X is functionally dependent on YZ:

X → Y , and X→Z, therefore X → YZ

Split:

If X is functionally dependent on YZ,(X → YZ),

then X is functionally dependent on Y ( X → Y)

and X is functionally dependent on Z ( X → Z),

X → YZ therefore: X→Y and X → Z

Question 8

Good Functional Depenedencies

vs

Bad Functional Depenedencies

Answer 8

Good Functional Depenedency:

• Minimal Redundancy
• Less possibility of anomalies
• Example: EmployeeID → Name, Phone

Bad Functional Depenedency:

• A lot of redundancy
• May tie unrelated things together, allowing data anomalies
• Example: Position → PhoneNumber

Question 9

Functional Dependencies

as Constraints

Answer 9

• A Functional Dependency will hold on some instances, and will not hold on others
• If designed as part of the schema, a FD can help define a valid instance
• Can check if a FD is violated by checking a single instance
• But cannot prove that a FD exists by checking a single instance

Question 10

Using Functional Dependencies

for Database Schema Design:

General Steps

Answer 10

1. Start with some Relational Schema
2. Determine it’s Functional Dependencies (FDs)
3. Use the FDs to design a better schema
   
   • ​​One which minimizes the possibility of anomalies

Question 11

Definition:

Closure of a

Set of Attributes

Answer 11

Given a set of attributes: {A₁, …, A_n }

and a set of FDs, F

The Closure: {A₁, …, A_n }+

is the set of attributes B such that

{A₁, …, A_n } → B

So, the closure is the set of attributes dependent on attributes of A

Question 12

Algorithm for

Computing Attribute Closure

Answer 12

closure = x;

repeat until there is no change:

if there is an FD: U → V in F

such that U is a subset of the Closure,

then set closure = closure UNION V

Translation:

If an FD implies another attribute that is not in the closure, add it to the closure

Question 13

Types of Anomalies

Answer 13

• Update Anomaly
• Deletion Anomaly
• Insertion Anomaly
• Redundancy

Question 14

Anomaly Types:

Update Anomaly

Answer 14

Updating one tuple causes inconsistent data

Question 15

Anomaly Types:

Deletion Anomaly

Answer 15

Deleting one kind of information makes you lose another

Question 16

Anomaly Types:

Insertion Anomaly

Answer 16

Storing one kind of info depends on storing another

Question 17

Anomaly Types:

Redundancy

Answer 17

Storage of multiple instances

of redundant information

Question 18

What is a

Functional Dependency (FD) ?

Answer 18

• An Integrity Constraint
  
  • not explicity expressed in the E/R diagram
• Occurs when one attribute in a relation uniquely determines another attribute
  
  • Two attributes always occur in the same pair
  • Example: classroom and course
• A → B
  
  • If A, then B

Question 19

Superkeys

and

Keys

Answer 19

Superkey

a set of attributes {A₁, …, A_n} such that

for any other attribute B in a relation R,

{A₁, …, A_n } → B

• All attributes are functionally dependent by a superkey
• A Key is a minimal superkey,
  
  • no subset of the key is a superkey

Question 20

Steps for finding

Keys and Superkeys

Answer 20

For each set of attributes X:

1. Compute X+ (The Closure)
2. If X+ = the set of all attributes, then X is a Superkey
3. If X is minimal, then X is a Key

Question 21

Functional Dependency:

Formal Definition

Answer 21

Let A, B be sets of attributes

We write A → B, or say “A functionally determines B”

If, for any tuples t₁ and t₂ :

t₁[A] = t₂[A] implies t₁[B] = t₂[B]

We call A → B a Functional Dependency

Question 22

First Normal Form

(1NF)

Answer 22

A Relation is in First Normal Form (1NF) if:

Every field contains only Atomic Values

(No lists or sets)

This is an implicit requirement in the Relational Model.

Pretty simple: One column, one value

Question 23

Second Normal Form (2NF)

Answer 23

A Relation R is in Second Normal Form (2NF) if:

Every non-key attribute in R is has Full Funtional Dependency on the Candidate Key of R

A non-2NF schema can be decomposed to 2NF

Question 24

Full Functional Dependency

vs

Partial Functional Dependency

Answer 24

X → Y is a:

Full Functional Dependency

if removing attribute A from X makes X → Y not hold

Partial Functional Dependency

if after removing attribute A from X,

X → Y still holds

Question 25

Decomposing a

Non-2NF Schema

to 2NF

Answer 25

To be in Second Normal Form, all attributes must be Fully Dependent on the Candidate Key

Steps:

1. Identify which attributes are not Fully Dependent on a key
2. Seperate into tables that are Fully Dependent

Question 26

Decompose the following non-2NF schema:

Employee(ssn, pno, hours, ename, plocation)

into 2NF

Answer 26

1. Identify candidate key: (ssn, pno)
2. Identify Full Dependencies:

• (ssn, pno) → (hours, ename, plocation)
• ssn → ename
• pno → plocation

3. Split into other tables;

• T1(ssn, pno, hours)
• T2(ssn, ename)
• T3(pno, plocation)

Question 27

Third Normal Form

(3NF)

Answer 27

A Relation R, with Functional Dependencies F,

is in 3NF if:

For all Dependencies X→A in the Closure F+ :

1. A is a part of X (trivial FD)
2. X contains a key for R (X is a superkey) or
3. A is part of some key for R

R should not have a non-key attribute that is functionally determined by another non-key attribute

Question 28

Normal Forms:

1NF, 2NF, 3NF Summaries

Answer 28

• 1NF
  
  • Remove non-atomic values
• 2NF
  
  • Remove partial dependencies
• 3NF
  
  • Remove transitive dependencies

Question 29

First Normal Form (1NF):

• Test
• Remedy

Answer 29

Test

Should NOT have non-atomic values

Remedy

Create relations for each non-atomic attribute

Question 30

Second Normal Form( 2NF):

• Test
• Remedy

Answer 30

Test

No non-key attributes are functional dependencies on just a part of primary key

Remedy

Decompose and create a new relation for each partial dependency

Question 31

Third Normal Form (3NF):

• Test
• Remedy

Answer 31

Test

Should NOT have non-key attribute FD by another non-key attribute

Remedy

Decompose, create relation including non-key attributes that are functionally dependent on other non-keys

Question 32

Boyce-Codd Normal Form (BCNF)

Answer 32

A Relation R is in BCNF if:

For all Functional Dependencies(X→A) in the Closure(F+):

• A is part of X (trivial FD)
• X contains a key for R, X is a superkey

Intuitively:

The only non-trivial dependencies are those in which a key determines some attributes.

Each tuple can be seen as an entity or relationship, identified by a key and described by attributes.

Question 33

BCNF:

Relation Diagram

Answer 33

*Need an image

Each attribute is exclusively functionally dependent on the key

Question 34

Motivation for

decomposing data into BCNF

Answer 34

• Redundancies in data can lead to data anomalies
  
  • Bad functional dependencies can be a factor
• We want to detect and remove redundancies
• Sometimes, decomposition can lead to subtle and unwanted effects

Question 35

Decomposition:

Two Types

Answer 35

• Lossless/Lossless-Join
• Dependency Preserving

Question 36

Decomposition:

Checks

Answer 36

It is important to check that a decomposition doesn’t introduce new problems

Checks:

Good decomposition should allow us to:

• Recover the original relation
• Check integrity constraints efficiently

Question 37

Decompositions:

• Basic Structure
• Projections

Answer 37

For an original relation:

R( [key attributes] , [Attr. Set A] , [Attr. Set B] )

R can be decomposed into two new relations, each using the Key of R as their own Keys:

R₁( [key attributes], [Attr. Set A] )

R₂( [key attributes], [Attr. Set B] )

These are called the Projections of R

Question 38

Dependency Preservation

during Decomposition

Answer 38

A Functional Dependency(FD) X→Y in a relation R,

is Preserved in a projection R_n if:

R_n contains all of the attributes of X and Y

A FD can therefore be checked by accessing only R

Question 39

True or False:

BNCF Decomposition is

always lossless

Answer 39

TRUE!

All Functional Dependencies in a BNCF table are already dependent on the superkey

This means that all tables would have the same key:

R = R₁ Join R₂ Join … Join R_n

Question 40

Dependency Checking

after

Decomposition

Answer 40

A decomposition is Dependency Preserving if:

the set of new Functional Dependencies, F++

is the same as the set F+ from the original table

F++ = F+

Question 41

BCNF

Normalization

Algorithm

Answer 41

Starting with a relation R, not in BCNF:

Let X in R,A be a single attribute in R,

and X → A be an FD that causes a violation of BCNF

Decompose into R-A and XA

If either R-A or XA is not in BCNF, decompose those Relations

Question 42

Functional Dependencies:

Useful Rules derived from

Armstrong’s Axioms

Answer 42

• Decomposition
  
  • If (A₁, …, A_n) -> (B₁, …, B_m) then
    
    • (A₁, …, A_n) -> B₁ , (A₁, …, A_n)
    • (A₁, …, A_n) -> B₂ , (A₁, …, A_n)
    • etc
• Union
  
  • If (A₁, …, A_n) -> B₁, …, (A₁, …, A_n)-> B_m
  • then (A₁, …, A_n) -> (B₁, …, B_m)
• Pseudotransitivity
  
  • If (A₁, …, A_n) -> (B₁, …, B_m)
  • and (B₁, …, B_m), (C₁, …, C_k) -> (D₁, …, Dp)
  • then
  • (A₁, …, A_n)(C₁, …, C_k) -> (D₁, …, Dp)