FDs

Question 1

How to identify “bad” schemas and improve them

Answer 1

1. express constraints on the data: functional dependencies

2. use FDs to decompose the relation

Question 2

Normalization

Answer 2

obtains a schema in the “normal form” that guarantees certain properties

Question 3

Functional dependencies (FDs)

Answer 3

form of constraint that generalizes the concept of keys

Question 4

A functionally determines B

Answer 4

if 2 tuples agree on the attributes A = A1, A2…An then they must agree on the attributes B = B1, B2, …Bm

Question 5

A,B -> C,D can be split how?

Answer 5

A,B -> C
A,B -> D
Attributes on right are independently determined by A,B

Question 6

A,B -> C,D

= A-> C,D and B->C,D?

Answer 6

cannot split this way

Question 7

Trivial FDs

X->A

Answer 7

the attribute A belongs to the attribute set X

Question 8

examples of trivial FDs

Answer 8

A -> A

A, B, C -> C

Question 9

FD is domain knowledge

Answer 9

• inherent property of the application and data

- not something we can infer from a set of tuples

Question 10

Given a table with a set of tuples, can we confirm FD is valid?

Answer 10

No, can only confirm FD seems valid or infer FD is invalid, can’t prove FD is valid

Question 11

Why FDs?

Answer 11

• keys are special cases of FDs
• more integrity constraints
• help detect if schema has redundancies

Question 12

Armstrongs Axioms

Answer 12

Reflexivity, Augmentation, Transitivity

Question 13

Reflexivity

Answer 13

For any subset X in {A1..An}

A1, A2, …An -> X

Question 14

examples reflexivity

Answer 14

A,B -> B
A,B,C -> A,B
A,B,C -> A,B,C

Question 15

Augmentation

Answer 15

For any attribute sets X,Y,Z:

if X->Y, then X,Z -> Y,Z

Question 16

examples Augmentation

Answer 16

A -> B implies A,C -> B,C

A,B -> C implies A,B,C -> C

Question 17

Transitivity

Answer 17

For any attribute sets X, Y, Z: if X-> Y and Y -> Z then X -> Z

Question 18

examples transitivity

Answer 18

A-> B and B-> C then A-> C

A->C,D and C,D -> then A->E

Question 19

FD closure

Answer 19

the closure F+ is the set of all FDs logically implied by F

Question 20

Armstrong’s axioms are:

Answer 20

sound

complete

Question 21

Sound

Answer 21

any FD generated by an axiom belongs in F+

Question 22

Complete

Answer 22

repeated application of the axioms will generate all FDs in F+

Question 23

Attribute Closure

Answer 23

If X is an attribute set, the closure X+ is the set of all attributes B s.t. X -> B
X+ includes all attributes that are functionally determined from X

Question 24

Closure Algorithm

Answer 24

X = {A1, A2, …An}

Until X doesn’t change repeat: if B1,…Bm -> C is an FD and B1…Bm are all in X, then add C to X

Question 25

Why is closure needed?

Answer 25

Does X-> Y hold?

We can check if Y is in X+

Question 26

To compute the closer F+ of FDs

Answer 26

for each subset of attributes X, compute X+, for each subset of attributes Y in X+, ouput FD X->Y

Question 27

superkey

Answer 27

set of attributes A1, A2,…An s.t. for any other attribute B in the relation:
A1, A2,…An -> B

Question 28

key

Answer 28

minimal super key

none of its subsets functionally determines all attributes of the relation

Question 29

Compute X+ for all sets of attributes X. How do we know if X is a key or superkey?

Answer 29

if X+ = all attributes, X is a superkey

if no subset of X is a superkey, X is a key

Question 30

Is it possible to have many keys in a relation R?

Answer 30

Yes. R(A,B,C) with FDs
A,B -> C
A,C -> B

Question 31

S is a minimal basis for a set F of FDs if:

Answer 31

S+ = F+
every FD in S has one attribute on the RHS
if we remove a FD from S, the closure is not F+
if we remove 1+ attributes on LHS from any FD in S, closure is not F+