database 2

→ is the symbol for

functional dependency

x → Y

set of attributes X determines the set of attributes Y

where do functional dependencies come from

unique attributes, domain, constraints (person having one father)

2 requirements to be a key / primary key

uniqueness and minimality

candidate key

when you compute the closure set the individual attributes are not keys by themselves?

super key

unique but not minimal, column(s) that uniquely identify a row

functional dependency

property of one or more attributes that uniquely determines the value of other attributes

how do you determine functional dependency

look at the table, if the left is the same and the right is the same then its an fd

shortcut to find keys

any attribute not on the right side of functional dependencies must be in any key/superset

what is normalization for?

minimizing redundancy, anomalies, data storage

how does normalization work

decompose unsatisfactory relation schemas into smaller schemas

what it means to have atomic attributes

no repeating columns within a row, no multivalued columns

transitive dependency

two separate entities exist within one table

first normal form 1NF

each attribute is atomic aka =

• no repeating columns within a row

• no multi value columns

second normal form 2NF

each attribute functionally dependent on primary key

third normal form 3NF

get rid of transitive dependencies

has a prime

BCNF

require keys in FDs to be superkeys, each attribute on LHS must be superkey

resolve intrakey dependencies

prime

right side of attribute is member of a key

how to make a violating schema, R, fit BCNF

decompose R into a set of S relations

each relation S must be in BCNF

must be able to “recover” R from the relations S

decomposition algorithm for BCNF with table R

R = R₁ + R₂ where ((x → y) aka x det y in FD)

R₁ = x⁺ (closure set of attr on LHS)

R₂ = R - x⁺ + x

why is 3NF special case of BCNF?

when there is a prime, decomposition would ruin the FDs, LHS not superkey but RHS has prime

how to violate 3NF

X → A, if X is not a superkey and A is not prime

lossless join

decompose schema keeping original relations AND able to reconstruct without losing too

dependency preservation

possible to check in projected relations whether all FD are satisfied

which is ALWAYS lossless and dependency preservation: BCNF or 3NF

3NF

BCNF is always

lossless, but not always dependency preservation

3NF synthesis algorithm

minimal basis

1. RHS single attr

2. no FD removed

3. no attr removed from the left

nontrivial FD’s in BCNF

are always superkeys

nontrivial FD do NOT look like

ex: AC → C