Eroxl's NotesGraph
Normal Forms (Practice)

Problem 1

Briefly answer the following questions

(a). Define the Term Functional Dependency

A functional dependence is some column which can always be determined by another group of one or more columns.

(b). Why Are Some Functional Dependencies Called Trivial?

Because they're the dependence from something to itself, and exists for all attributes making them trivial.

(c). Give a Set of FDs for the relation Schema R(A,B,C,D) with Primary Key AB under Which R is in 1NF but not in 2NF

  • A, B C, D

(d). Give a Set of FDs for the relation Schema R(A,B,C,D) with Primary Key AB under Which R is in 2NF but not in 3NF

  • A, B C, D
  • C D

(e). Consider the relation Schema R(A,B,C), Which Has the FD B C. if A is A Candidate Key for R, is it Possible for R to Be in BCNF? if So, under what Conditions? if Not, Explain why not

It's possible only if B is a candidate key of R.

(g). Suppose We Have a relation Schema R(A,B,C) Representing a Relationship between Two Entity Sets with Keys A and B, Respectively, and Suppose that R Has (among others) the FDs A B and B A. Explain what such a Pair of Dependencies means (i.e., what They Imply about the Relationship that the relation models)

It means that the relationship is 1 to 1 as every A is associated with only one B and vice-versa.

Problem 2

Consider a relation R with five attributes ABCDE. You are given the following dependencies: A B, B,C E, and E,D A.

(a). List All Keys for R

  • A, C, D
  • B, C, D
  • C, D, E

(b). Is R in 3NF?

Yes it is.

(c). Is R in BCNF?

No it's not as A B violates it as A is not by itself a candidate key.

Problem 3

Consider the relation shown below

X Y Z
x1 y1 z1
x1 y1 z2
x2 y1 z1
x2 y1 z3

(a). List All the Functional Dependencies that This relation Instance Satisfies

  • X Y
  • X, Z Y
  • X, Y, Z X, Y, Z

(b). Assume that the Value of Attribute Z of the Last Record in the relation is Changed from Z3 to Z2. Now List All the Functional Dependencies that This relation Instance Satisfies

  • X Y
  • X, Z Y
  • X, Y, Z X, Y, Z

Problem 4

Assume that you are given a relation with attributes ABCD.

(a). Assume that no Record Has NULL Values. Write an SQL Query that Checks whether the Functional Dependency A B Holds

SELECT * FROM ABCD AS i1 
WHERE EXISTS (
    SELECT * FROM ABCD AS i2
    WHERE i2.a = i1.a
    AND i1.b != i2.b
);

(b). Assume Again that no Record Has NULL Values. Write an SQL Assertion that Enforces the Functional Dependency A B

CREATE ASSERTION enforce_A_determines_B
CHECK (
    NOT EXISTS (
        SELECT * FROM ABCD AS i1
        WHERE EXISTS (
            SELECT * FROM ABCD AS i2
            WHERE i2.A = i1.A
              AND i1.B != i2.B
        )
    )
);

Problem 5

Consider the following collection of relations and dependencies. Assume that each relation is obtained through decomposition from a relation with attributes ABCDEFGHI and that all the known dependencies over relation ABCDEFGHI are listed for each question. (The questions are independent of each other, obviously, since the given dependencies over ABCDEFGHI are different.)

For each (sub)relation:

  1. State the strongest normal form that the relation is in.
  2. If it is not in BCNF, decompose it into a collection of BCNF relations.

(a). R1(A,C,B,D,E), A B, C D

(i). State the Strongest Normal Form that the relation is in

1NF

(ii). If it is not in BCNF, Decompose it into a Collection of BCNF Relations

  • R2(A, C, E)
  • R3(A, B)
  • R4(C, D)

(b). R2(A,B,F), AC E, B F

(i). State the Strongest Normal Form that the relation is in

1NF

(ii). If it is not in BCNF, Decompose it into a Collection of BCNF Relations

  • R2(A, B)
  • R3(B, F)

(c). R3(A,D), D G, G H

(i). State the Strongest Normal Form that the relation is in

BCNF

(ii). If it is not in BCNF, Decompose it into a Collection of BCNF Relations

Already in BCNF

(d). R4(D,C,H,G), A I, I A

(i). State the Strongest Normal Form that the relation is in

BCNF

(ii). If it is not in BCNF, Decompose it into a Collection of BCNF Relations

Already in BCNF

(e). R5(A,I,C,E)

(i). State the Strongest Normal Form that the relation is in

BCNF

(ii). If it is not in BCNF, Decompose it into a Collection of BCNF Relations

Already in BCNF

Problem 6

Suppose that we have the following three tuples in a legal instance of a relation schema S with three attributes ABC (listed in order): (1,2,3), (4,2,3), and (5,3,3).

(a). Which of the following Dependencies Can You Infer Does not Hold over Schema S?

  • [ ] A B
  • [x] B, C A
  • [ ] B C

(b). Can You Identify Any Dependencies that Hold over S?

  • A B
  • B C
  • A C

Problem 7

Suppose you are given a relation R with four attributes ABCD. For each of the following sets of FDs, assuming those are the only dependencies that hold for R, do the following:

  1. Identify the candidate key(s) for R.
  2. Identify the strongest normal form that R satisfies (1NF, 2NF, 3NF, or BCNF).
  3. If R is not in BCNF, decompose it into a set of BCNF relations that preserve the dependencies.

(a). C D, C A, B `C

(i). Identify the Candidate key(s) for R

  • B

(ii). Identify the Strongest Normal Form that R Satisfies (1NF, 2NF, 3NF, or BCNF)

2NF

(iii). If R is not in BCNF, Decompose it into a Set of BCNF Relations that Preserve the dependencies.`

  • R1(B, C)
  • R2(C, A, D)

(b). B C, D A

(i). Identify the Candidate key(s) for R

  • B, D

(ii). Identify the Strongest Normal Form that R Satisfies (1NF, 2NF, 3NF, or BCNF)

1NF

(iii). If R is not in BCNF, Decompose it into a Set of BCNF Relations that Preserve the dependencies.`

  • R1(B, D)
  • R2(B, C)
  • R3(D, A

(c). A, B, C D, D A

(i). Identify the Candidate key(s) for R

  • A, B, C
  • D, B, C

(ii). Identify the Strongest Normal Form that R Satisfies (1NF, 2NF, 3NF, or BCNF)

3NF

(iii). If R is not in BCNF, Decompose it into a Set of BCNF Relations that Preserve the Dependencies

  • `R1(B, C, D)
  • R2(D, A)

(d). A B, B,C D, A C

(i). Identify the Candidate key(s) for R

  • A

(ii). Identify the Strongest Normal Form that R Satisfies (1NF, 2NF, 3NF, or BCNF)

2NF

(iii). If R is not in BCNF, Decompose it into a Set of BCNF Relations that Preserve the dependencies.`

  • R1(A, B, C)
  • R2(B, C, D)

(e). A, B C, A, B D, C A, D B

(i). Identify the Candidate key(s) for R

  • A, B
  • A, D
  • B, C
  • C, D

(ii). Identify the Strongest Normal Form that R Satisfies (1NF, 2NF, 3NF, or BCNF)

3NF

(iii). If R is not in BCNF, Decompose it into a Set of BCNF Relations that Preserve the Dependencies

There is no way to decompose it into BCNF without losing a FD.

Problem 8

Consider a relation R with five attributes ABCDE. With the following instances:

  • (i) { } (i.e., empty relation)
  • (ii) {(a,2,3,4,5), (2,a,3,5,5)}
  • (iii) {(a,2,3,4,5), (2,a,3,5,5), (a,2,3,4,6)}
  • (iv) {(a,2,3,4,5), (2,a,3,4,5), (a,2,3,6,5)}
  • (v) {(a,2,3,4,5), (2,a,3,7,5), (a,2,3,4,6)}
  • (vi) {(a,2,3,4,5), (2,a,3,4,5), (a,2,3,6,5), (a,2,3,6,6)}
  • (vii) {(a,2,3,4,5), (a,2,3,6,5), (a,2,3,6,6), (a,2,3,4,6)}

(a). For Each of the Instances of R, State whether it Violates the FD BC E

  • (i). Does not Violate
  • (ii). Does not Violate
  • (iii). Violates
  • (iv). Does not Violate
  • (v). Violates
  • (vi). Violates
  • (vii). Violates

We can't say anything project just the name of this relation as.