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! ## Footnote 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)