Exercise 1:

1)

FDs:

flight code --> everything,
departure airport --> departure city
destination airport --> destination city
aircraft type --> seats
prime flight --> everything except flight code and airline

and

prime flight, airline --> flight code
prime flight --> operating airline

Keys:

{flight code}, {prime flight, airline}

2) 

R(fc, air, prime, oper, depc, depa, destc, desta, type, seats)

FD depa --> depc violates BCNF.

{depa}+ = {depa, depc}

R1(depa, depc)

No FD that can be projected onto R1 violates BCNF.

{depa} + (R - {depa}+) = {fc, air, prime, oper, depa, destc, desta, type, seats}

R2(fc, air, prime, oper, depa, destc, desta, type, seats)

FD desta --> destc violates BCNF for R2.

{desta}+ = {desta, destc}

R3(desta, destc)

No FD violates R3.

{desta} + (R2 - {desta}+) = {fc, air, prime, oper, depa, desta, type, seats}

R4(fc, air, prime, oper, depa, desta, type, seats)

FD type --> seats violates BCNF for R4.

{type}+ = {type, seats}

R5(type, seats)

No FD violates R5.

{type} + (R4 - {type}+) = {fc, air, prime, oper, depa, desta, type}

R6(fc, air, prime, oper, depa, desta, type)

FD prime --> oper, depa, desta, type violates BCNF

{prime}+ = {prime, oper, depa, desta, type}

R7(prime, oper, depa, desta, type)

No FD violates R7.

{prime} + (R6 - {prime}+) = {fc, air, prime}

R8(fc, air, prime)

No FD violates R8.

Finally, we are left with:

R1(depa, depc)
R3(desta, destc)
R5(type, seats)
R7(prime, oper, depa, desta, type)
R8(fc, air, prime)

Exercise 2:

R(A, B, C, D, E, F, G)

1: AC --> E
2: EG --> D
3: AC --> B
4: DF --> A

a)

{A, C, E, F}+ = // Trivial
{A, C, E, F} = // 3
{A, B, C, E, F} // Not key.

{A, C, F, G}+ = // Trivial
{A, C, F, G} = // 3
{A, B, C, F, G} = // 1
{A, B, C, E, F, G} = // 2
{A, B, C, D, E, F, G} // Key.

{C, D, F, G}+ = // Trivial
{C, D, F, G} = // 4
{A, C, D, F, G} = // 3
{A, B, C, D, F, G} = // 1
{A, B, C, D, E, F, G} // Key.

{C, E, F, G}+ = // Trivial
{C, E, F, G} = // 2
{C, D, E, F, G} = // 4
{A, C, D, E, F, G} = // 3
{A, B, C, D, E, F, G} // Key.

{B, C, E, F, G}+ = // Trivial
{B, C, E, F, G} = // 2
{B, C, D, E, F, G} = // 4
{A, B, C, D, E, F, G} // Superkey since it contains the key {C, E, F, G}.

b) 

R(A, B, C, D, E, F, G)

All FDs violate BCNF for R, we pick AC --> E

{A, C}+ = {A, C, E, B}

R1(A, C, E, B)

No FD that can be projected onto R1 violates BCNF.

{A, C} + (R - {A, C}+) = {A, C, D, F, G}

R2(A, C, D, F, G)

Only FD DF --> A can be projected onto R2, and it violates BCNF.

{D, F}+ = {D, F, A}

R21(D, F, A)

No FD violates R21.

{D, F} + (R2 - {D, F}+) = {D, F, C, G}

R22(D, F, C, G)

No FD violates R22.

c) 

AC --> E is OK, since E is part of a key.
EG --> D is OK, since D is part of a key.
AC --> B is not OK, since AC is not a superkey and B is nor part of any key.
DF --> A is OK, since A is part of a key.

d)

AC --> E ==> R1(A, C, E)
EG --> D ==> R2(E, G, D)
AC --> B ==> R3(A, C, B)
DF --> A ==> R4(D, F, A)

No relation contains a key from original R, so we must add one more relation that does:

R5(A, C, F, G)

Exercise 3:

1) 

A relation is in 1NF if and only if the domain of each attribute contains only atomic values, and the value of each attribute contains only a single value from that domain.

Name 	Phone
Markus	555-861, 192-122 
Selpi	555-403

Not in NF1 since Phone contains a list of numbers.

2) 

A relation is in 2NF if and only if it is in 1NF and there’s no non-prime attributes determined by a subset of some key, where non-prime means “attribute that’s not part of any key for the relation”.

Manufacturer	Item		Headquarters
Dent-o-Fresh	EZ-Brush	USA
Hoch			Toothmaster	Germany

FDs : Manufacturer --> Headquarters
Key : { Manufacturer, Item }

In NF1 since no attribute contains a list. Not in 2NF since Headquarters is non-prime and Manufacturer is a subset of some key.

3) 

A relation is in 3NF if and only if it is in 2NF and all of its attributes are determined only by the keys of that relation, not by non-prime attributes.

Tournament		Year	Winner	Birthday
Indiana Closed	1998	Al 		21 Jul. 1975 
Indiana Closed	1999	Chip	14 Mar. 1977
Cleveland Open	1998	Alice	21 Sep. 1975 

FDs : Winner --> Birthday
      Tournament, Year --> Winner
Key : { Tournament, Year }

In NF2 since Winner isn't a subset of some key, and neither is Tournamnet, Year (they are a key). Not in 3NF since Birthday is determined by Winner, which is not a key.

4)

BCNF guarantees that redundancy is removed from a relation, while 3NF instead guarantees that all dependencies are preserved. For example, BCNF would require that we split the following table:

Title	Theater	City
Antz	Guild	Boston
Antz	Park	Boston

FDs: Theater --> City
     Title, City --> Theater
Keys: { Title, City }, { Title, Theater }

but then the smaller tables still contain the bad rows. On the other hand, the table is in 3NF and would therefore not be split and still contain redundancy.