Scribd
Upload
524 views8 pages

Analyzing Functional Dependencies in DBMS

The document describes determining if a relation R is in 3NF and converting it if necessary based on a set of functional dependencies. For the relation R(P, Q, R, S, T, U, V, W, X, Y) with functional dependencies PQ → R, P → ST, Q → U, U → VW, and S → XY: - The candidate key is determined to be PQ - P → ST, Q → U, U → VW, and S → XY violate 3NF as the determining attributes are not superkeys and determined attributes are not prime - R is decomposed into 5 relations R1-R5 placing each functional dependency in

Uploaded by

Shrutika Tayde
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
524 views8 pages

Analyzing Functional Dependencies in DBMS

The document describes determining if a relation R is in 3NF and converting it if necessary based on a set of functional dependencies. For the relation R(P, Q, R, S, T, U, V, W, X, Y) with functional dependencies PQ → R, P → ST, Q → U, U → VW, and S → XY: - The candidate key is determined to be PQ - P → ST, Q → U, U → VW, and S → XY violate 3NF as the determining attributes are not superkeys and determined attributes are not prime - R is decomposed into 5 relations R1-R5 placing each functional dependency in

Uploaded by

Shrutika Tayde
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
  • Functional Dependency Analysis - Problem 15
  • 2NF Checking - Problem 16
  • 2NF Testing - Problem 17
  • 3NF Testing - Problem 18
  • 3NF Verification - Problem 19
  • BCNF Compliance - Problem 20

15) Compute the closure of the following set F of functional dependencies for relation schema R

= {A, B, C, D, E}.
A -> BC
CD -> E
B -> D
E -> A
List the candidate keys for R.

Answer:
A -> BC, B -> D so A -> D so A -> DC -> E
therefore A -> ABCDE

E -> A, A -> ABCDE, so E -> ABCDE


CD -> E, so CD -> ABCDE
B -> D, BC -> CD, so BC -> ABCDE

Attribute closure:
A -> ABCDE
B -> BD
C -> C
D -> D
E -> ABCDE
AB -> ABCDE
AC -> ABCDE
AD -> ABCDE
AE -> ABCDE
BC -> ABCDE
BD -> BD
BE -> ABCDE
CD -> ABCDE
CE -> ABCDE
DE -> ABCDE
ABC -> ABCDE
ABD -> ABCDE
ABE -> ABCDE
ACD -> ABCDE
ACE -> ABCDE
ADE -> ABCDE
BCD -> ABCDE
BDE -> ABCDE
CDE -> ABCDE
ABCD -> ABCDE
ABCE -> ABCDE
ABDE -> ABCDE
ACDE -> ABCDE
BCDE -> ABCDE

The candidate keys are A, E, CD, and BC

Any combination of attributes that includes those is a super key.


16) Given a relation R( A, B, C, D) and Functional Dependency set FD = { AB → CD, B → C },
determine whether the given R is in 2NF? If not convert it into 2 NF.

Solution: Let us construct an arrow diagram on R using FD to calculate the candidate key.

From above arrow diagram on R, we can see that an attributes AB is not determined by any of the given FD,
hence AB will be the integral part of the Candidate key, i.e. no matter what will be the candidate key, and how
many will be the candidate key, but all will have W compulsory attribute.

Let us calculate the closure of AB

AB + = ABCD (from the method we studied earlier)

Since the closure of AB contains all the attributes of R, hence AB is Candidate Key

From the definition of Candidate Key(Candidate Key is a Super Key whose no proper subset is a Super key)

Since all key will have AB as an integral part, and we have proved that AB is Candidate Key, Therefore, any
superset of AB will be Super Key but not Candidate key.

Hence there will be only one candidate key AB

Definition of 2NF: No non-prime attribute should be partially dependent on Candidate Key

Since R has 4 attributes: - A, B, C, D, and Candidate Key is AB, Therefore, prime attributes (part of candidate
key) are A and B while a non-prime attribute are C and D

a) FD: AB → CD satisfies the definition of 2NF, that non-prime attribute(C and D) are fully dependent on
candidate key AB

b) FD: B → C does not satisfy the definition of 2NF, as a non-prime attribute(C) is partially dependent on
candidate key AB( i.e. key should not be broken at any cost)

As FD B → C, the above table R( A, B, C, D) is not in 2NF

Convert the table R(A, B, C, D) in 2NF:

Since FD: B → C, our table was not in 2NF, let's decompose the table

R1(B, C)

Since the key is AB, and from FD AB → CD, we can create R2(A, B, C, D) but this will again have a problem
of partial dependency B → C, hence R2(A, B, D).

Finally, the decomposed table which is in 2NF


a) R1( B, C)

b) R2(A, B, D)

17) Given a relation R( P, Q, R, S, T) and Functional Dependency set FD = { PQ → R, S → T },


determine whether the given R is in 2NF? If not convert it into 2 NF.

Solution: Let us construct an arrow diagram on R using FD to calculate the candidate key.

From above arrow diagram on R, we can see that an attributes PQS is not determined by any of the given FD,
hence PQS will be the integral part of the Candidate key, i.e., no matter what will be the candidate key, and how
many will be the candidate key, but all will have PQS compulsory attribute.

Let us calculate the closure of PQS

PQS + = PQSRT (from the method we studied earlier)

Since the closure of PQS contains all the attributes of R, hence PQS is Candidate Key

From the definition of Candidate Key (Candidate Key is a Super Key whose no proper subset is a Super
key)

Since all key will have PQS as an integral part, and we have proved that PQS is Candidate Key. Therefore, any
superset of PQS will be Super Key but not Candidate key.

Hence there will be only one candidate key PQS

Definition of 2NF: No non-prime attribute should be partially dependent on Candidate Key.

Since R has 5 attributes: - P, Q, R, S, T and Candidate Key is PQS, Therefore, prime attributes (part of candidate
key) are P, Q, and S while a non-prime attribute is R and T

a) FD: PQ → R does not satisfy the definition of 2NF, that non-prime attribute( R) is partially dependent on part
of candidate key PQS.

b) FD: S → T does not satisfy the definition of 2NF, as a non-prime attribute(T) is partially dependent on
candidate key PQS (i.e., key should not be broken at any cost).

Hence, FD PQ → R and S → T, the above table R( P, Q, R, S, T) is not in 2NF

Convert the table R( P, Q, R, S, T) in 2NF:

Since due to FD: PQ → R and S → T, our table was not in 2NF, let's decompose the table
R1(P, Q, R) (Now in table R1 FD: PQ → R is Full F D, hence R1 is in 2NF)

R2( S, T) (Now in table R2 FD: S → T is Full F D, hence R2 is in 2NF)

And create one table for the key, since the key is PQS.

R3(P, Q, S)

Finally, the decomposed tables which is in 2NF are:

a) R1( P, Q, R)

b) R2(S, T)

c) R3(P, Q, S)

18) Given a relation R( X, Y, Z, W, P) and Functional Dependency set FD = { X → Y, Y → P,


and Z → W}, determine whether the given R is in 3NF? If not convert it into 3 NF.

Solution: Let us construct an arrow diagram on R using FD to calculate the candidate key.

From above arrow diagram on R, we can see that an attributes XZ is not determined by any of the given FD,
hence XZ will be the integral part of the Candidate key, i.e. no matter what will be the candidate key, and how
many will be the candidate key, but all will have XZ compulsory attribute.

Let us calculate the closure of XZ

XZ + = XZYPW (from the closure method that we studied earlier)

Since the closure of XZ contains all the attributes of R, hence XZ is Candidate Key

From the definition of Candidate Key (Candidate Key is a Super Key whose no proper subset is a Super
key).

Since all key will have XZ as an integral part, and we have proved that XZ is Candidate Key, Therefore, any
superset of XZ will be Super Key but not the Candidate key.

Hence there will be only one candidate key XZ

Definition of 3NF: First it should be in 2NF and if there exists a non-trivial dependency between two sets of
attributes X and Y such that X → Y ( i.e., Y is not a subset of X) then

a. Either X is Super Key


b. Or Y is a prime attribute.

Since R has 5 attributes: - X, Y, Z, W, P and Candidate Key is XZ, Therefore, prime attribute (part of candidate
key) are X and Z while a non-prime attribute are Y, W, and P

Given FD are X → Y, Y → P, and Z → W and Super Key / Candidate Key is XZ

a. FD: X → Y does not satisfy the definition of 3NF, that neither X is Super Key nor Y is a prime
attribute.
b. FD: Y → P does not satisfy the definition of 3NF, that neither Y is Super Key nor P is a prime attribute.
c. FD: Z → W satisfies the definition of 3NF, that neither Z is Super Key nor W is a prime attribute.

Convert the table R( X, Y, Z, W, P) into 3NF:

Since all the FD = { X → Y, Y → P, and Z → W} were not in 3NF, let us convert R in 3NF

R1(X, Y) {Using FD X → Y}

R2(Y, P) {Using FD Y → P}

R3(Z, W) {Using FD Z → W}

And create one table for Candidate Key XZ

R4( X, Z) { Using Candidate Key XZ }

All the decomposed tables R1, R2, R3, and R4 are in 2NF( as there is no partial dependency) as well as in 3NF.

Hence decomposed tables are:

R1(X, Y), R2(Y, P), R3( Z, W), and R4( X, Z)

19) Given a relation R( P, Q, R, S, T, U, V, W, X, Y) and Functional Dependency set FD = { PQ


→ R, P → ST, Q → U, U → VW, and S → XY}, determine whether the given R is in 3NF? If not
convert it into 3 NF.

Solution: Let us construct an arrow diagram on R using FD to calculate the candidate key.

From above arrow diagram on R, we can see that an attribute PQ is not determined by any of the given FD,
hence PQ will be the integral part of the Candidate key, i.e. no matter what will be the candidate key, and how
many will be the candidate key, but all will have PQ compulsory attribute.

Let us calculate the closure of PQ


PQ + = P Q R S T U X Y V W (from the closure method we studied earlier)

Since the closure of XZ contains all the attributes of R, hence PQ is Candidate Key

From the definition of Candidate Key (Candidate Key is a Super Key whose no proper subset is a Super
key)

Since all key will have PQ as an integral part, and we have proved that XZ is Candidate Key, Therefore, any
superset of PQ will be Super Key but not Candidate key.

Hence there will be only one candidate key PQ

Definition of 3NF: First it should be in 2NF and if there exists a non-trivial dependency between two sets of
attributes X and Y such that X → Y (i.e., Y is not a subset of X) then

c) Either X is Super Key

d) Or Y is a prime attribute.

Since R has 10 attributes: - P, Q, R, S, T, U, V, W, X, Y, V, W and Candidate Key is PQ, Therefore, prime


attribute (part of candidate key) are P and Q while a non-prime attribute are R S T U V W X Y V W

Given FD are {PQ → R, P → ST, Q → U, U → VW and S → XY} and Super Key / Candidate Key is PQ

a. FD: PQ → R satisfy the definition of 3NF, as PQ Super Key


b. FD: P → ST does not satisfy the definition of 3NF, that neither P is Super Key nor ST is the prime
attribute
c. FD: Q → U does not satisfy the definition of 3NF, that neither Q is Super Key nor U is a prime attribute
d. FD: U → VW does not satisfy the definition of 3NF, that neither U is Super Key nor VW is a prime
attribute
e. FD: S → XY does not satisfy the definition of 3NF, that neither S is Super Key nor XY is a prime
attribute

Convert the table R( X, Y, Z, W, P) into 3NF:

Since all the FD = { P → ST, Q → U, U → VW, and S → XY } were not in 3NF, let us convert R in 3NF

R1(P, S, T) {Using FD P → ST }

R2(Q, U) {Using FD Q → U }

R3( U, V, W) { Using FD U → VW }

R4( S, X, Y) { Using FD S → XY }

R5( P, Q, R) { Using FD PQ → R, and candidate key PQ }

All the decomposed tables R1, R2, R3, R4, and R5 are in 2NF( as there is no partial dependency) as well as in
3NF.
Hence decomposed tables are:

R1(P, S, T), R2(Q, U), R3(U, V, W), R4( S, X, Y), and R5( P, Q, R)

Conclusion: From the above three examples, we can conclude that the following steps are followed to check
whether the given relational schema R is in 3 NF or not? If not, how to decompose it into 3 NF.

STEP 1: Calculate the Candidate Key of given R by using an arrow diagram and then using the closure of an
attribute on R, such that from the calculated candidate key, we can separate the prime attributes and non-prime
attributes.

STEP 2: Verify each FD with Definition of 3NF (First it should be in 2NF and if there exist a non-trivial
dependency between two sets of attributes X and Y such that X → Y (i.e., Y is not a subset of X) then Either X
is Super Key or Y is a prime attribute).

STEP 3: Make a set of FD which does not satisfy 3NF, i.e. all those FD which do not have an attribute on the
left side of FD as a super key or attribute on the right side of FD as a prime attribute.

STEP 4: Convert the table R in 3NF by decomposing R such that each decomposition based on FD should
satisfy the definition of 3NF.

STEP 5: Once the decomposition based on FD is completed, create a separate table of attributes in the Candidate
key.

STEP 6: All the decomposed R obtained from STEP 4 and STEP 5 forms the required decomposition where
each decomposition is in 3NF.

20) Given a relation R( P, Q, R, S, T, U, V, W, X) and Functional Dependency set FD = { PQ → R,


QS → TU, PS → VW, and P → X }, determine whether the given R is in which normal form?

Solution: Let us construct an arrow diagram on R using FD to calculate the candidate key.

From the above arrow diagram on R, we can see that an attribute PQS is not determined by any of the given FD,
hence PQS will be the integral part of the Candidate key, i.e. no matter what will be the candidate key, and how
many will be the candidate key, but all will have PQS compulsory attribute.

Let us calculate the closure of PQS

PQS + = P Q R S T U X V W (from the closure method we studied earlier)

Since the closure of PQS contains all the attributes of R, hence PQS is Candidate Key
From the definition of Candidate Key (Candidate Key is a Super Key whose no proper subset is a Super
key)

Since all key will have PQS as an integral part, and we have proved that PQS is Candidate Key, Therefore, any
superset of PQS will be Super Key but not a Candidate key.

Hence there will be only one candidate key PQS

Since R has 9 attributes: - P, Q, R, S, T, U, V, W, X, and Candidate Key is PQS, Therefore, prime attributes (part
of candidate key) are P Q and S while a non-prime attribute is R T U V W X

Given FD are { PQ → R, QS → TU, PS → VW, and P → X } and Super Key / Candidate Key is PQS

NOTE: To solve such questions, we apply reverse engineering, i.e. 1st check BCNF, if not then 3NF, if not then
2NF, and so on.

a. FD: PQ → R does not satisfy the definition of BCNF, as PQ is not Super Key, hence the table is not in
BCNF (because if one dependency fails, all fails) now we check the same FD for 3NF.
b. FD: PQ → R even does not satisfy the definition of 3NF, as PQ is not Super Key or R is not a prime
attribute, hence table is not in 3NF also (because if one dependency fails, all fails) now we check same
FD for 2NF
c. FD: PQ → R even does not satisfy the definition of 2NF, as PQ is not Super Key and R which is not
prime attribute depending on part of the key (partial dependency), hence table is not in 2NF also
(because if one dependency fails, all fails).

Hence from the above three statements, we can say that table R ( P, Q, R, S, T, U, V, W, X) is in 1NF only.

Common questions

Powered by AI

A relation is not in BCNF if there exists any dependency A → B where A is not a superkey. Violation of BCNF occurs when non-trivial functional dependencies have an attribute on the right that is not uniquely determined by a candidate key. For instance, in relation R(P, Q, R, S, T, U, V, W, X, Y) with FD {PQ → R, P → ST}, the dependency P → ST violates BCNF because P is not a superkey, hence R is not in BCNF .

To determine 3NF, check if each functional dependency adheres to the rule: a non-trivial dependency X → Y is allowed if X is a superkey or Y is a prime attribute. For example, in R(P, Q, R, S, T) with FD set {PQ → R, S → T}, check each FD. PQ → R passes as PQ is a superkey, but S → T doesn't as S isn't a superkey and T isn't prime. Hence, R isn't in 3NF until decomposed to eliminate such dependencies, leading to R1(P, Q, R) and R2(S, T).

First, identify the candidate keys to determine prime and non-prime attributes. Then verify each FD against BCNF criteria: a dependency X → Y requires X to be a superkey for BCNF. If any FD fails BCNF, check for 3NF eligibility next, where Y must be a prime attribute if X isn't a superkey. Correspondingly, decompose relations to eliminate unwanted dependencies until each aligns with the highest attainable form. For instance, convert R(P, Q, R, S, T) with FDs like P → ST into components like R1(P, S, T) if necessary, each satisfying the normal form definitions and dependencies involved .

Compute closure by starting with a set of attributes and iteratively adding any attributes implied by the functional dependencies until no more can be added. For the given schema R = {A, B, C, D, E}, start with A to find A -> ABCDE, and similarly for others, E -> ABCDE, CD -> ABCDE, etc. From the attribute closures, determine candidate keys as those sets whose closure includes all attributes of R. For instance, candidate keys for R are A, E, CD, and BC because they can determine all other attributes in the schema .

Some dependencies don't satisfy 3NF if they create transitive dependencies or involve non-superkey determinants. Resolve this by decomposition: isolate dependencies into new relations where their determinants become the primary keys. For example, in R with FDs {X → Y, Y → P}, decompose to R1(X, Y) and R2(Y, P) to eliminate transitive dependency and align with 3NF principles, ensuring no attribute set besides a key determines others .

The purpose of decomposing into 3NF is to eliminate transitive dependencies and ensure that each non-prime attribute is dependent on a superkey. Achieve this by decomposing the relation into smaller tables such that each functional dependency meets the 3NF conditions. For instance, relation R(X, Y, Z, W, P) with FD set {X → Y, Y → P, Z → W} can be decomposed into sub-relations R1(X, Y), R2(Y, P), R3(Z, W), and R4(X, Z) with each ensuring that all dependencies are on superkeys or involve only prime attributes, thus maintaining 3NF .

The process involves several steps: Step 1 is calculating the candidate key using an arrow diagram and determining attribute closure. Step 2 checks each functional dependency (FD) against the 3NF definition: a relation is in 3NF if it is in 2NF and all non-trivial dependencies have either the left side as a super key or the right side as a prime attribute. Step 3 involves identifying FDs that do not satisfy the 3NF conditions. Step 4 decomposes the table based on those FDs, ensuring each follows the 3NF rules. Step 5 creates a separate table for the candidate key. Finally, Step 6 ensures all decomposed tables are in 3NF and collectively form the original relation .

Decompose by splitting the relation into smaller relations that each satisfy the 2NF condition, which means removing partial dependencies. For the relation R(A, B, C, D) with FD {AB → CD, B → C}, decompose it into R1(B, C) and R2(A, B, D). This decomposition ensures that each non-prime attribute is completely functionally dependent on the candidate key for its respective table, thus achieving 2NF and reducing data redundancy .

A relation is not in 2NF if there are partial dependencies because 2NF requires that all non-prime attributes are fully functionally dependent on the candidate key. For example, in relation R(A, B, C, D) with FD set {AB → CD, B → C}, the FD B → C indicates a partial dependency since C is dependent on part of the candidate key, B, and not the whole key AB. As a result, the relation is not in 2NF until it's decomposed such that all partial dependencies are eliminated .

A candidate key is a minimal set of attributes that uniquely determines the whole tuple in a relation. It ensures there is no subset of it that can determine the tuple, thus a superkey but with no redundancy. Candidate keys influence normalization by defining the prime attributes and helping identify partial and transitive dependencies, essential for 2NF and 3NF validation, respectively. For instance, knowing PQ is a candidate key in a schema helps identify non-prime attributes (like R, S) and expose dependencies that prevent achieving higher normal forms .

15) Compute the closure of the following set F of functional dependencies for relation schema R = {A, B, C, D, E}. A -> BC
16) Given a relation R( A, B, C, D) and Functional Dependency set FD = { AB → CD, B → C }, determine whether the given R is
a) R1( B, C) b) R2(A, B, D) 17) Given a relation R( P, Q, R, S, T) and Functional Dependency set FD = { PQ → R, S → T },
R1(P, Q, R) (Now in table R1 FD: PQ → R is Full F D, hence R1 is in 2NF) R2( S, T) (Now in table R2 FD: S → T is Full F D, h
b. Or Y is a prime attribute. Since R has 5 attributes: - X, Y, Z, W, P and Candidate Key is XZ, Therefore, prime attribute
PQ + = P Q R S T U X Y V W (from the closure method we studied earlier) Since the closure of XZ contains all the attributes
Hence decomposed tables are: R1(P, S, T), R2(Q, U), R3(U, V, W), R4( S, X, Y), and R5( P, Q, R) Conclusion: From the above
From the definition of Candidate Key (Candidate Key is a Super Key whose no proper subset is a Super key) Since all key wil

You might also like