Functional Dependencies

Question 1

How does E-R and Functional Dependencies relate?

Answer 1

Question 2

What are Functional Dependencies?

Answer 2

In relational database theory, a functional dependency is a constraint between two sets of attributes in a relation from a database. In other words, functional dependency is a constraint that describes the relationship between attributes in a relation.

Question 3

Explain Assertions on a schema.

Answer 3

Question 4

Explain Assertions on a domain.

Answer 4

Question 5

What are FDs really?

Answer 5

What are FDs really?
• Functional dependencies represent a special kind of
constraints of a domain – dependency constraints.
• The database we design should properly capture all
constraints of the domain.
• We can use FDs to verify that our design indeed
captures the constraints we expect, and add more
constraints to the design when needed.

Question 6

What’s so functional about FDs?

Answer 6

What’s so functional?
• X → A is a (deterministic) function from X
to A. Given values for the attributes in the
set X, we get the value of A.
• Example:
– code → name
– imagine a deterministic function f(code)
which returns the name associated with a
given code.

Question 7

What is the difference between dependence and reference?

Answer 7

Question 8

Explain Multiple Attributes on R/LHS

Answer 8

Question 9

Answer 9

Question 10

What’s the difference between the LHS of a FD, and a key?

Answer 10

Question 11

FD: code, period → teacher ?

Answer 11

Question 12

Given values for a code and a period, starting from any relation where
they appear, is it possible to reach more than one teacher value by following
keys and references?

Answer 12

Question 13

Explain Trivial FD:s.

Answer 13

Question 14

Is this a trivial FD?
course, period → course, name

Answer 14

course, period → course, name

Shorthand for
course, period → course (trivial)
course, period → name (not trivial)

Question 15

Explain Inferring FD:s.

Answer 15

Question 16

Explain closure of attribute set X.

Answer 16

Question 17

How do you compute closure?

Answer 17

Question 18

Answer 18

Question 19

How to find all the implied FDs?

Answer 19

Question 20

Answer 20

Question 21

Simplifying trick to find F+?

Answer 21

Question 22

Explain how to find keys. What is a super key? Minimal super key?

Answer 22

Question 23

Schedules(code, name, period, #students,
teacher, room, #seats, weekday, hour)

Are these superkeys?

X = {code, period, weekday, hour}

Y = {code, period, weekday}

Answer 23

Question 24

Answer 24

Question 25

Explain Primary Keys.

Answer 25

Primary keys • There can be more than one key for the same relation. • We choose one of them to be the primary key, which is the key that we actually use for the relation. • Other keys could be asserted through uniqueness constraints. – E.g. for the self-referencing relation

Question 26

Syntax for determining primary key for scenario: Rooms(name, #seats) NextTo(right, left)

Answer 26

Question 27

Where do FDs come from?

Answer 27

Question 28

How NOT to find FDs and why not!

Answer 28

Question 29

Answer 29

Question 30

Why Normalizing Databases?

Answer 30

Normalization of Database Database Normalization is a technique of organizing the data in the database. Normalization is a systematic approach of decomposing tables to eliminate data redundancy(repetition) and undesirable characteristics like Insertion, Update and Deletion Anamolies. It is a multi-step process that puts data into tabular form, removing duplicated data from the relation tables. Normalization is used for mainly two purposes, Eliminating reduntant(useless) data. Ensuring data dependencies make sense i.e data is logically stored.

Question 31

How can FD:s be used to detect anomalies?

Answer 31

Question 32

What is the problem and how to fix it?

Answer 32

Question 33

Explain Boyce-Codd Normal Form.

Answer 33

Question 34

Explain BCFN violations using the example below:

Answer 34

Question 35

Explan the BCFN normalization algorithm.

Answer 35

Question 36

Answer 36

Question 37

What does Recovery mean?

Answer 37

Question 38

Explain Lossy joins using this example.

Answer 38

Question 39

Explain Lossless join.

Answer 39

Lossless join • Only if we decompose on proper dependencies can we guarantee that no facts are lost. – Schemas from proper translation of correct E-R diagrams get this ”for free”. – The BCNF decomposition algorithm guarantees lossless join. • A decompositon that does not give lossless join is bad.

Question 40

Answer 40

Question 41

Why not use BCNF decomposition for designing database schemas? Why go via E-R diagrams?

Answer 41

Question 42

Why use FDs and decomposition at all? Why not just go via E-R diagrams?

Answer 42

Question 43

Answer 43

Question 44

Answer 44

Question 45

Explain Equality Constraints

Answer 45

Equality constraints • FDs don’t always give the full story. • Equality constraints over circular relationship paths are relatively common. – Can sometimes – but not always – be captured via extra references. – Extra attributes may be needed – more on that later…

Question 46

Answer 46

Question 47

Answer 47

Question 48

What is a problem with BCNF?

Answer 48

Question 49

Explain the Third Normal Form (3NF).

Answer 49

Question 50

Explain the algorithm of 3NF.

Answer 50

Question 51

Answer 51

Question 52

Answer 52

Question 53

Answer 53

Question 54

Problem with 3NF?

Answer 54

Question 55

3NF vs BCNF

Answer 55

Question 56

What is X+?

Answer 56

X+ = Closure of X = all derivable (from X) attributes

Question 57

What is F+?

Answer 57

F+ = Closure of F = all implied (from F) FDs

Question 58

Short description of BCNF?

Answer 58

Boyce-Codd Normal Form (BCNF): – The LHS (X) of every non-trivial FD (X → A) must be a superkey

Question 59

Explain Decompostition.

Answer 59

Decomposition: – Split up relations until normal form (e.g. BCNF) holds – Make sure to preserve recovery!!! No lossy joins allowed

Question 60

Why Normal Forms?

Answer 60

Normal Forms?! • Use normal forms to detect anomalies (e.g. Redundancy) • Use decomposition to remove anomalies

Question 61

Scale of Normal Forms?

Answer 61

Question 62

Howcome?

Answer 62

Question 63

Answer 63

Question 64

Explain Independencies (INDs).

Answer 64

Question 65

Independent how?

Answer 65

Question 66

If two tuples have the same value for X, different values for Y and different values for the Z attributes, then there must also exist tuples where the values of Y are exchanged, otherwise Y and Z are not independent! (Visualize)

Answer 66

Question 67

Explain.

Answer 67

Question 68

Explain Joining.

Answer 68

Question 69

Are FD:s Independencies?

Answer 69

Question 70

What are the possible combinations of attibutes?

Answer 70

Question 71

Are IND rules equal FD rules?

Answer 71

Question 72

Problems with IND?

Answer 72

Question 73

Explain Fourth Normal Form (4NF) holistically.

Answer 73

Fourth Normal Form (4NF) • The redundancy that comes from IND’s is not removable by putting the databaseschema in BCNF. • There is a stronger normal form, called 4NF, that (intuitively) treats IND’s as FD’s when it comes to decomposition, but not when determining keys of the relation.

Question 74

Explain 4NF in detail.

Answer 74

Question 75

BCNF vs 4NF.

Answer 75

Question 76

INDs for validation?

Answer 76