Module 4

1. Define the term functional dependency. Why are some functional dependencies called trivial?

A functional dependency is a relationship between two sets of attributes in a relation. It specifies that if two
tuples (rows) have the same values for a set of attributes X, then they must also have the same values for
another set of attributes Y. Formally, Y is functionally dependent on X (denoted as X → Y) if, for every pair of
tuples, whenever they agree on X, they also agree on Y.

In simple words:
Knowing the value of X determines the value of Y.

Why are some functional dependencies called trivial?

A functional dependency X → Y is called trivial if Y is a subset of X. That is, the dependency holds automatically
because Y is contained within X.

Example of trivial dependency:

If X = {A, B} and Y = {A}, then X → Y is trivial because Y is part of X.

2. List Armstrong Axiom rules

Armstrong’s Axioms are a set of inference rules used to derive all functional dependencies (FDs) logically
implied by a given set of FDs. These are fundamental in normalization and relational schema design.

1. Reflexivity

If Y is a subset of X, then X → Y
Example: If {A, B} ⊇ {B}, then {A, B} → {B}

2. Augmentation

If X → Y, then XZ → YZ for any Z

Example: If A → B, then AC → BC

3. Transitivity

If X → Y and Y → Z, then X → Z
Example: If A → B and B → C, then A → C

4. Union

If X → Y and X → Z, then X → YZ
Example: A → B and A → C ⟹ A → BC

5. Decomposition (or Projectivity)

If X → YZ, then X → Y and X → Z

6. Pseudotransitivity

If X → Y and YZ → W, then XZ → W

3. Define Boyce-Codd normal form. How does it differ from 3NF?

A relation is in Boyce-Codd Normal Form (BCNF) if: For every non-trivial functional dependency X → Y,
X is a superkey of the relation.
• A non-trivial functional dependency is one where Y is not a subset of X.
• A superkey is a set of attributes that uniquely identifies a tuple in the relation.
Difference Between BCNF and 3NF
1
 Feature 3rd Normal Form (3NF) Boyce-Codd Normal Form
(BCNF)
Stricter Condition less strict more strict
Condition For every X → Y, either: For every X → Y,
- X is a superkey OR - X must be a superkey
- Y is a prime attribute (part of some candidate key)

Allows some Yes (if non-prime attributes depend on part of a No

redundancy? candidate key)
Guarantees no Not always Yes
anomalies?
Example:Consider a relation: R(StudentID, Course, Instructor)
With FDs:
• StudentID, Course → Instructor
• Instructor → Course
Candidate Key: StudentID, Course
This is in 3NF because:
• Instructor → Course, and Course is a prime attribute
But not in BCNF because:
• Instructor is not a superkey, but determines Course

4. Suppose, a relational schema R (P,Q, R, S) and set of functional dependencies F and G are as follow: F :
{ P → Q, Q → R, R → S } G : { P → QR, R → S }. Check the equivalency of functional dependencies F and G.

2
5. Illustrate different anomalies in designing a database (or) Write briefly on the different types of
anomalies in designing a database (or) Explain insert, update and delete anomalies with suitable
examples

When designing databases, poor normalization or improper structure can lead to various types of anomalies,
which cause inconsistencies and difficulties in maintaining data. The main anomalies are:

1. Insertion Anomaly

• Description: Difficulty inserting new data due to existing data constraints.

• Example:
If a department must have at least one employee to be added, you can't add a new department unless
an employee is assigned.
Suppose you want to add a new course but cannot do so because no student has enrolled yet.

2. Deletion Anomaly

• Description: Loss of important data when deleting records.

• Example:
Deleting the last employee of a department might also remove the entire department record if the data
is stored together, leading to loss of the department info.

3. Update Anomaly

• Description: Inconsistency when updating data in multiple places.

• Example:
If a customer's address is stored in multiple records and the address changes, all instances must be
updated; otherwise, discrepancies occur. For example, updating one record but forgetting to update
others causes inconsistent data.

6. How can we conclude two FDs are equivalent?

Two sets of functional dependencies, say F and G, are said to be equivalent if they imply exactly the same set of
dependencies. That is:
F ≡ G if and only if:
• Every dependency in the closure of F (denoted F+) is also in G+
• Every dependency in G+ is also in F+
In other words, F+ = G+
Steps to Determine Equivalence:
1. Compute the closure of F (F+) using Armstrong’s Axioms.
2. Compute the closure of G (G+)
3. Compare F+ and G+
o If they are equal, then F and G are equivalent.
o If not, they are not equivalent.
Example: Let:
• F = {A → B, B → C}
• G = {A → B, A → C}
Step 1: Compute F+
From F:
• A→B
• B→C
• Therefore, A → C (by transitivity)
So, F+ includes: A → B, B → C, A → C

3
Step 2: Compute G+
From G:
• A→B
• A→C
So, G+ includes: A → B, A → C
Now check: does G+ include B → C? No.
Therefore, F+ ≠ G+ and F and G are not equivalent.
7. Why Armstrong’s axioms are said to sound and complete?

Armstrong’s Axioms are said to be sound and complete because they form a reliable and sufficient basis for
reasoning about functional dependencies (FDs) in relational databases.

1. Soundness

Armstrong’s axioms are sound because:

Every functional dependency derived using the axioms is logically correct —

i.e., it must hold in all relation instances that satisfy the given set of FDs.

Meaning:
The axioms will never lead you to infer a false or invalid dependency. They produce only those FDs that are truly
implied by the original set.

2. Completeness

Armstrong’s axioms are complete because:

Every valid functional dependency that is logically implied by the original set can be derived using the axioms.

Meaning:
If an FD is logically implied by a given set, the axioms can be used (possibly in combination) to derive it.

8. What is meant by lossless join property?

The lossless join property ensures that when a relation is decomposed into two or more smaller relations (for
normalization), no data is lost during the join process.

In simple terms:

A decomposition of a relation R into R₁, R₂, ..., Rn is lossless if

R = R₁ ⨝ R₂ ⨝ ... ⨝ Rn
(i.e., the natural join of the decomposed relations gives back the original relation)

Why It Matters

• It preserves all original data.

• Prevents spurious tuples when relations are joined.

• Ensures data consistency after decomposition.

Example: Suppose you have a relation: Employee(EmpID, DeptID, DeptName) and you decompose it into:

• R₁(EmpID, DeptID)

• R₂(DeptID, DeptName)

If DeptID → DeptName, then the join of R₁ and R₂ will restore the original relation, so the decomposition is
lossless.

9. When do you say that a relation is not in 1NF?

4
A relation is in 1NF if all its attributes contain only atomic (indivisible) values, and each attribute contains only a
single value per tuple.

A relation is not in 1NF when:

1. An attribute has multiple values (multi-valued attributes)

2. An attribute contains sets, arrays, or lists

3. An attribute stores records or nested relations

4. The same attribute stores values of different types or structures

Example – Not in 1NF

StudentID Name Phone Numbers

101 Alice 9876543210, 9123456780

102 Bob 8877665544

Here, Phone Numbers contains multiple values in a single field. This violates 1NF.

To Convert to 1NF

Break the relation into multiple rows, one for each phone number:

StudentID Name PhoneNumber

101 Alice 9876543210

101 Alice 9123456780

102 Bob 8877665544

Now it’s in 1NF.

10. Given the FDs P→Q, P→R, QR→S, Q→T, QR→U, PR→U, write the sequence of Armstrong’s Axioms needed
to arrive at a. P → T b. PR → S

11. Consider a relation R with five attributes (A,B,C,D,E) . You are given the following dependencies: A → B,
BC → E, and ED → A. i. List all keys for R. ii. Is R in 3NF? iii. Is R in BCNF?

5
12. Define minimal cover. Let the given set of functional dependencies be: 𝐸: {𝐵 → 𝐴, 𝐷 →𝐴, 𝐴𝐵 → 𝐷} . Find
the minimal cover of E

A minimal cover for a set of functional dependencies (FDs) is a simplified, equivalent set of dependencies that
has the following properties:

• Each FD in the set has a single attribute on the right side.

• The set is minimal, meaning:

o Removing any FD from the set makes it no longer equivalent to the original set.

o Removing any attribute from the left side of an FD makes it lose its equivalence.

In other words, a minimal cover is a canonical or smallest set of FDs that preserves the same constraints as the
original set, making schema design and normalization easier.

13. Explain with example 2NF, 3NF and BCNF.

1. Second Normal Form (2NF)

Definition:
A relation is in 2NF if it is in 1NF and no partial dependency exists.
Partial dependency means that a non-prime attribute depends only on part of a candidate key (not the whole
key).
Example:
Suppose we have a relation:
| StudentID (PK) | CourseID (PK) | Instructor | Grade |
Here, (StudentID, CourseID) is a candidate key.
• If Instructor depends only on CourseID (not on the entire key), then it violates 2NF.

6
To convert into 2NF:
Remove partial dependencies by creating separate tables.
2. Third Normal Form (3NF)
Definition:
A relation is in 3NF if it is in 2NF and no transitive dependencies exist.
Transitive dependency means: non-prime attribute depends on another non-prime attribute.
Example:
Suppose a relation:
| StudentID (PK) | AdvisorID | AdvisorName |
• AdvisorName depends on AdvisorID.
• AdvisorID depends on StudentID via StudentID being the key.
• AdvisorName depends transitively on StudentID through AdvisorID.
To achieve 3NF:
Remove transitive dependencies, often by creating another table:
• Students table with StudentID, AdvisorID.
• Advisors table with AdvisorID, AdvisorName.
3. Boyce-Codd Normal Form (BCNF)
Definition:
A relation is in BCNF if every determinant is a candidate key.
• It is a stronger form than 3NF.
• No non-trivial functional dependency exists where the determinant is not a candidate key.
Example:
Suppose a relation:
| RoomNumber | Building |
• RoomNumber uniquely determines Building (RoomNumber is a candidate key).
• But if Building also determines RoomNumber (each room belongs to one building, but a building has
many rooms), then Building → RoomNumber is not true unless the RoomNumber is unique across all
buildings (which typically isn't).
To satisfy BCNF:
Remove dependencies where the determinant isn't a candidate key, often via decomposition.

14. Explain with example 2NF, 3NF and BCNF. Consider a relation schema R(X Y Z W P ) (above table R) is
decomposed into R1( X Y Z ) and R2( Z W P). Determine whether the above R1 and R2 are Lossless or
Lossy?

7
15. Consider a relation R(A, B, C, D, E) with FDs AB → C, AC → B, BC → A, D → E. Determine all the keys of
relation R. Also decompose the relation into collections of relations that are in BCNF.

16. Consider a relation schema R (A,B,C,D) with the following functional dependencies A → B, B → C, C → D,
D → B. Determine whether the decomposition of R into R1 ( A , B ) , R2 ( B , C ) and R3 ( B , D ) is lossless or
lossy. Write the complete steps.

8
17. What is dependency preservation property for decomposition? Why is it important?

The dependency preservation property ensures that when a relation is decomposed into multiple relations
(tables), all the functional dependencies (FDs) that hold in the original relation can be enforced by restricting
operations (like insert, update, delete) on the smaller, decomposed relations without needing to recombine the
relations.

Why is it important?
It is crucial because:

• It simplifies enforcement of constraints.

• Prevents the need for complex join operations to check dependencies during updates, making
database operations more efficient and less error-prone.

• Ensures the integrity constraints in the original relation are maintained after normalization.

18. i) What are Armstrong’s axioms? ii) Write an algorithm to compute the attribute closure of a set of
attributes (X) under a set of functional dependencies (F). iii) Explain three uses of attribute closure
algorithm.

i) Input:
• A set of attributes X
• A set of functional dependencies F
Output:
• The closure of X under F, denoted as X⁺
1. Initialize X⁺ := X
2. Repeat
a. For each functional dependency Y → Z in F:
If Y ⊆ X⁺ then
X⁺ := X⁺ ∪ Z
Until no more attributes can be added to X⁺
3. Return X⁺
Explanation
• Start with the attributes in X
• Iteratively add attributes to X⁺ if their left-hand side (Y) is already in the closure
• Stop when no new attributes can be added
II)

9
 a) To Test if a Functional Dependency Holds: To check if X → Y holds in F, compute X⁺ and see if Y ⊆ X⁺.
b) To Determine Candidate Keys: If the closure of an attribute set X includes all attributes of the relation,
then X is a candidate key.
c) In Normalization (e.g., 3NF and BCNF): Helps to determine whether a functional dependency violates
the normal form based on whether the left side is a superkey.

19. Explain the difference between BCNF and 3NF with an example

Both Boyce-Codd Normal Form (BCNF) and Third Normal Form (3NF) aim to eliminate redundancy in relational
schemas by organizing data around functional dependencies. However, BCNF is stricter than 3NF.
1. Third Normal Form (3NF) – Definition
A relation is in 3NF if for every functional dependency X → A, at least one of the following holds:
• X → A is trivial (i.e., A ⊆ X)
• X is a superkey
• A is a prime attribute (i.e., part of some candidate key)
2. Boyce-Codd Normal Form (BCNF) – Definition
A relation is in BCNF if for every functional dependency X → A, one of the following holds:
• X → A is trivial
• X is a superkey
BCNF does not allow the exception for "A is a prime attribute."
Key Difference
• 3NF allows certain dependencies if the right-hand side is a prime attribute, even when the left-hand
side is not a superkey.
• BCNF does not allow such dependencies; it strictly requires that the left side must be a superkey.
Example That Is in 3NF but Not in BCNF
Relation: R(A, B, C)
Functional Dependencies:
• A→B
• B→A
Candidate key: {A, C} and {B, C} (since A ↔ B)
Check each FD:
• A → B: A is not a superkey, but B is a prime attribute → OK in 3NF, not OK in BCNF
• B → A: B is not a superkey, but A is a prime attribute → OK in 3NF, not OK in BCNF
So, R is in 3NF but not in BCNF.
20. Consider the relation R = {A, B, C, D, E, F, G, H} and the set of functional dependencies F = {A→DE, B→F,
AB→C, C→GH, G→H}. What is the key for R? Decompose R into 2NF and then 3NF relations.

10
21. What is the lossless join property of decomposition? Why is it important?

Lossless Join Property of Decomposition – Definition

The lossless join property ensures that when a relation is decomposed into two or more smaller relations (as
part of normalization), the original relation can be perfectly reconstructed by joining those decomposed
relations without any spurious (extra or incorrect) tuples.

In formal terms:

A decomposition of a relation R into R₁, R₂, ..., Rn is lossless if

R = R₁ ⨝ R₂ ⨝ ... ⨝ Rn

Why Is It Important?

1. Data Integrity:
Prevents loss of information during normalization or decomposition. All original data must remain
recoverable.

2. Correct Query Results:

Avoids spurious tuples during joins, which can lead to incorrect query results or misinterpretation of
data.

3. Safe Normalization:
Ensures we can normalize relations (to remove redundancy or update anomalies) without
compromising correctness.

4. Database Consistency:
Maintains a logically consistent database where every record makes sense based on the original
schema.

22. Given relation R(A,B,C,D,E) and functional dependencies F={AB → C, CE → D, A → E}. Determine whether
each functional dependency below is in F+ or not: i) AB → D ii) A → C

11
23. Consider the following relation: CAR_SALE(Car#, Date_sold, Salesperson#, Commission%,
Discount_amt) Assume that a car may be sold by multiple salespeople, and hence {Car#,Salesperson#} is
the primary key. Additional dependencies are : Date_sold → Discount_amt and Salesperson# →
Commission% (i) Based on the given primary key and functional dependencies, is this relation in 1NF,
2NF, or 3NF? Why or why not? (ii) How would you successively normalize it completely?

24. Consider the following decompositions for the relation schema R into R1, R2 and R3. Determine
whether the decomposition has the lossless join property with respect to the given F. R={P, Q, R, S, T, U}
R1={P, Q}, R2= {R, S, T}, R3={P,R,U} F = { P → Q, R → {S, T}, {P,R} → U}

12
25. Given a relation R(A1,A2,A3,A4,A5) with functional dependencies A1→A2A4 and A4→A5, check if the
decomposition R1(A1,A2,A3),R2(A1,A4),R3(A2,A4,A5) is lossless.

26. Consider the un-normalized relation R(A, B, C, D, E, F, G) with the FDs A→B , AC→G, AD→EF, EF→G,
CDE→AB. Trace the normalization process to reach 3NF relations

27. Illustrate Lossless Join Decomposition and Dependency Preserving Decomposition with typical
examples.

13
1. Lossless Join Decomposition

Definition:
A decomposition of a relation into smaller relations is lossless (or non-lossy) if, when we join the decomposed
relations, we get back the original relation without losing any information. This ensures no data loss occurs
during normalization.

Example:
Suppose we have a relation:

| StudentID | CourseID | Instructor |

with FDs:

• (StudentID, CourseID) → Instructor

To decompose losslessly:

• Divide into two relations:

R1: (StudentID, CourseID)

R2: (CourseID, Instructor)

Test for Losslessness:

The join of R1 and R2 on CourseID should produce the original relation without losing information.

2. Dependency Preserving Decomposition

Definition:
A decomposition preserves dependencies if all functional dependencies of the original relation can be
enforced using only the decomposed relations without needing to join them.

Example:
Using previous relation:

• Original FDs: (StudentID, CourseID) → Instructor and CourseID → Instructor.

If we decompose into R1 and R2:

• R1: (StudentID, CourseID)

• R2: (CourseID, Instructor)

Check dependency preservation:

• The FD (CourseID → Instructor) is preserved because R2 contains CourseID and Instructor.

• The FD (StudentID, CourseID) → Instructor may not be directly preserved unless R1 and R2 are
combined.

28. Given the FDs P→Q, P→R, QR→S, Q→T, QR→U, PR→U, write the sequence of Armstrong’s Axioms needed
to arrive at the following FDs: (a) P → T (b) PR → S (c) QR → SU

14
29. Consider a relation PLAYER (PLAYER-NO, PLAYER-NAME, PLAYER-POSN,TEAM, TEAM-COLOR, COACH-
NO, COACH-NAME, TEAM-CAPTAIN). Assume that PLAYER-NO is the only key of the relation and that the
following dependencies hold: TEAM→{TEAM-COLOR, COACH-NO, TEAM-CAPTAIN} COACH-NO→COACH-
NAME. i. Is the relation in 2NF? If not, decompose to 2NF. ii. Is the relation in 3NF? If not, decompose to
3NF

15