What is partial functional dependency in dbms

Partial functional dependency / What is partial functional dependency / Why it is called as partial functional dependency? / Define partial functional dependency

Partial Functional Dependency

A functional dependency A → B is said to be partial if removal of any subset of A still able to recognize B uniquely.  

Partial Dependency is a form of Functional dependency that holds on a set of attributes. It is about the complete dependency of a right hand side attribute on one of the left hand side attributes.

For example, in a functional dependency PQ → R, if either P alone or Q alone can uniquely identify R, then this is said to be Partial Functional Dependency. We read this as R is partially functionally dependent on P or R is partially functionally dependent on Q.

Another example: Assume the set of FDs for a relation Student as follows;

F = {regno → name, regno → dob, {regno, phone} → gender, regno → gender}

Here, in FD {regno, phone} → gender, the attribute gender is partially dependent on regno attribute or left hand side. Here, phone is not required to identify gender uniquely.

 

Go to the index page

Go to the Normalization page

What is meant by full functional dependency

Define full functional dependency / When would you say that an attribute is fully functionally dependent on other attributes? / What is full functional dependency?

Full Functional Dependency

In a functional dependency A → B, (A is a set of attributes and B is another set of attributes), the dependency where B is fully dependent on A, and not on any of the subset of A is called Full Functional dependency. For example, assume that attributes P and Q together can only uniquely identify the value of the other attribute R. Then, PQ → R is Full Functional Dependency. 

As another example, let us consider the set F of functional dependencies; F = { A → B, AD → B }. In this case, the FD A → B is full functional dependency whereas AD → B is not full, that is B is not fully functionally dependent on AD, instead it depends on A alone.

Go to index page

What is trivial functional dependency in dbms

What is trivial functional dependency in DBMS? / Define trivial functional dependency / What is the trivial property in normalization process?

Trivial Functional Dependency

A FD is said to be as Trivial, if it holds for all relations. In other words, a functional dependency A → B is said to be trivial, if B is the subset or equal to that of A. That is, if you know the value of B already, you would uniquely determine the value of B.

If all of the right hand side attributes are either subset or equal to the left hand side attributes in a functional dependency, then that particular functional dependency is said to be trivial.

For example, 

• A → A is trivial, 
• AB → B is trivial, 
• {regno, phone} → phone and so on.

Go to keywords page

Describe trivial functional dependency in normalization process

What is functional dependency in dbms

What is functional dependency in DBMS? / Define Functional dependency / How to write a functional dependency? / Functional dependency examples

Functional Dependency

Functional Dependency is the property which verifies the relationship between two attributes / two sets of attributes. It means, determination of the value(s) of one attribute (or one set of attributes) using the other (or other set of attributes). This property is helping us in designing a good database.

A FD can be written as A → B. This can be read as "A determines the value of B" or "value of B can be uniquely determined by A". 

For example, if you know the register number of a student you would easily identify other details of that particular student. hence, all the other attributes of student table like name, branch, gender, dob etc. are all dependent on the register number attribute. In other words, register number determines all the other attributes uniquely.



To know more about functional dependencies Click here

Go to Database Glossary - DBMS Important Keywords page

What is normalization

Define normalization / What is normalization / Define the term normalization

Normalization is the process that is a part of database design process which helps us to eliminate some anomalies (problems / nature of data which would cause problems) which are present in the design of a table. It actually examines the relationship between the attributes of a table (relation) to eliminate anomalies like insertion, deletion and updation.

To know more about normalization Click here

One more way to find candidate keys in normalization process

How to find the candidate keys? Another way to find candidate keys in normalization process / Easy way to find key of relational table in DBMS

Another way to find candidate keys

When we try to find the candidate keys we always start with the attributes that are in the left hand side and we try to find the closure of Left Hand Side (LHS) attributes. In many cases, there are possibilities such that the attributes that are on both sides may also contribute in forming a candidate keys. Hence, we would use the following method to find all the candidate keys.

We separate the attributes from the given set of FDs as follows;

LHS only attributes (L)	Not listed attributes (N)	RHS only attributes (R)	Both LHS and RHS (B)

The attributes that are on the LHS must present in a key. That is, L ⊇ Key (L is subset or equal to a key).

The attributes that are not part of any given FDs must be a part of a candidate key. That is, N ⊃ Key (N is a subset of a key).

The attributes that are on the RHS cannot be a part of key. That is, R ⊅ Key (R cannot be part of a key).

The attributes that are present on both sides of different functional dependencies may contribute in formation of a candidate key. That is, R ⊇ Key (R may be part of key).

Example 1:

Let us try this with an example;

Consider a relation R = ABCDEF with set F of functional dependencies, F = {A -> B, B -> D, C -> D, E -> F}; Find the candidate keys of R.

Using the set F, let us draw the table;

LHS only attributes (L)	Not listed attributes (N)	RHS only attributes (R)	Both LHS and RHS (B)
A, C, E	-	D, F	B

As per the theory, LHS contributes in forming a key. Hence, let us find the closure of LHS attributes first.

A+ = ABD

C+ = CD

E+ = EF

(AC)+ = ABCD

(AE)+ = ABDEF

(CE)+ = CDEF

(ACE)+ = ABCDEF

Hence, (ACE) is a candidate key.

We don’t need to find the closure for RHS only attributes D and F.

Both side attribute may contribute. But in the given example, B is the attribute available on both side but it already can be determined by A. Hence, it may not contribute in forming the key.

So, only candidate key is (ACE).

Example 2:

Let us try another example;

Consider a relation R = (ABCDEF) with set F as F = {DF -> C, BC -> F, E -> A, ABC -> E}. Find all the candidate keys.

LHS only attributes (L)	Not listed attributes (N)	RHS only attributes (R)	Both LHS and RHS (B)
D, B	-	-	A, C, E, F

Let us find the closure of LHS attributes.

D+ = D

B+ = B

(DB)+ = DB

Now we need the both sides attributes for finding the candidate key. But they can form the key in association with LHS attributes as LHS is must in a key.

A+ = A

C+ = C

E+ = AE

F+ = F

…

…

(DBA)+ = ABD

(DBAC)+ = ABCDEF – One candidate key

(DBEF)+ = ABCDEF – One candidate key

(ACEF)+ = ACEF

Hence, candidate keys are (ABCD) and (BDEF).

Go to normalization solved exercises page

Go to How to find closure of an attributes(s) page

one more way to find the candidate keys of a relational table

Simpler way to find the candidate keys in dbms

Is the given decomposition is a lossless join decomposition?

Is the given decomposition a lossless join decomposition?

Question:

10. Assume a relation R(A, B, C, D, E) with set F of functional dependencies as follows;

F = {A → BC, CD → E, B → D, E → A}

If R is decomposed in to R1(A, B, C) and R2(A, D, E), which of the following holds?

(a) Decomposition is Loss-less Join Decomposition

(b) Decomposition is Dependency Preserving Decomposition

(c) Decomposition is both (a) and (b)

(d) Decomposition is Lossy-Join Decomposition

Answer:

(a) Decomposition is Loss-less Join Decomposition

Discussion:

Is the given decomposition is loss-less?

YES

If either R1 ⋂ R2 → R1 is true or R1 ⋂ R2 → R2 is true for the given decomposition, then we would say that the decomposition is loss-less join decomposition.

What is R1 ⋂ R2? – The common attribute(s) between R1 and R2.

In our case, R1 ⋂ R2 is A. We have to check whether A can determine all attributes of R1 or all attributes of R2 uniquely using the given FDs.

From F we can determine A+ as follows using the closure finding algorithm;

Result = A

Result = ABC from A → BC

Result = ABCD from B → D

Result = ABCDE from CD → E

From this, we would know that A is a candidate key for R.

A determines A, B, and C which is R1. So, R1 ⋂ R2 → R1 is true.

Hence, the given decomposition is loss-less join decomposition.

Is the given decomposition is dependency preserving?

NO

The above said decomposition of R into R1 and R2 is a dependency preserving decomposition if (F1 U F2)⁺ = F⁺, where F1 is set of FDs hold by R1, F2 is set of FDs hold by R2, and F is the set of FDs hold by R. (F1 U F2)⁺ is the closure of (F1 U F2), and F⁺ is the closure of F.

Step 1: for R1, the derivable non-trivial functional dependency is A → BC. Hence, F1 = {A → BC}

Step 1: for R1, the derivable non-trivial functional dependency is E → A. Hence, F2 = {E → A}

(F1 U F2)⁺ = {A → BC, E → A}

F⁺ = {A → BC, CD → E, B → D, E → A, E → BC, A → E}

A → BC is there in F⁺, hence preserved.

E → A is there in F⁺, hence preserved.

CD → E, and B → D are not there in F⁺, hence not preserved.

Hence, the decomposition is not dependency preserving.

         Previous Question                                                                                Next Question

Eliminate the redundant functional dependencies to find minimal cover

Find the functional dependencies that are redundant in a given set of FDs / Eliminate the redundant functional dependencies to find minimal cover / Eliminating unnecessary FDs to find canonical cover in normalization process

Question:

9. Let R(A, B, C) be a relation with the following set F of functional dependencies;

F = { A → B, B → A, A → C, C → A, B → C }

If we would like to find the minimal cover of F, then which of the following redundancies should be eliminated? ;

(a) B → A and A → C

(b) B → C

(c) Either (a) or (b)

(d) F is already minimal

Answer:

(c) Either (a) or (b)

Note: There can be more than one minimal cover for a set of functional dependencies.

Steps to find the minimal cover;

1. Ensure singleton attribute on the right hand side of each functional dependency.

2. Remove extraneous (redundant) attribute from the left hand side of each functional dependency.

3. Remove redundant functional dependency if any.

In our case, the functional dependencies given are already satisfying the first two rules.

According to rule 1, if we have any FDs with more than one attribute on the Right Hand Side, that FD should be decomposed using decomposition rule. We don’t have such FDs.

According to rule 2, if we have any FDs that have more than one attribute on the Left Hand Side (determiner), that FD must be checked for partial dependency. We don’t have such FDs.

Hence, the given set satisfies both rules.

For the third one we need to check.

Procedure : [refer here for different explanation].

Given : F = { A → B, B → A, A → C, C → A, B → C }

For the first FD A → B find A⁺ by hiding the FD A → B. A⁺ = AC which does not include B in it. Hence, A → B is not redundant.

For the second FD B → A find B⁺ by hiding the FD B → A.  B⁺ = ABC which includes A in it. Hence, B → A is redundant. We have to remove it immediately.

Now with the removal of B → A, our F becomes,

F = { A → B, A → C, C → A, B → C }

Find A⁺ by hiding A → C. A⁺ = ABC which includes C. Hence A → C is redundant and remove it immediately from F.

After removal of A → C, F becomes,

F = { A → B, C → A, B → C }

Find C⁺ by hiding C → A. C⁺ = C and this does not include A in the result. Hence, C → A is not redundant.

Finally find B⁺ by hiding B → C. B⁺ = B. Hence, B → C is mandatory.

We don’t have any more FDs. Our final set of functional dependencies are minimal after the removal of FDs B → A and A → C.

Hence, the minimal cover of F is as follows;

F_c = { A → B, C → A, B → C }

[Work out for the option B → C. While applying the above said procedure, start with the FD B → C. You will get the F_c as { A → B, B → A, A → C, C → A }]

         Previous Question                                                                                Next Question

Find the functional dependency that is not hold in a relation

Find the functional dependencies that are not holding on the given relation / Identify the wrong functional dependencies among the given / Find all valid functional dependencies of a relational table

Question:

8. Let R(A, B, C, D, E, F) be a relation with set F of functional dependencies as follows;

F = { A → B, A → C, CD → E, CD → F, B → E }

Which of the following functional dependencies does not hold in R?

(a) A → E

(b) CD → EF

(c) AD → F

(d) B → CD

Answer:

(d) B → CD

Discussion:

B → CD

B → CD is not true because the only functional dependency that has B on left hand side is B → E. now neither E nor B is not on the left hand side of any of the other functional dependencies.

A → E

A → E can be derived through the functional dependencies A → B and B → E. [ Transitivity rule ]

CD → EF

CD → EF can be derived through the functional dependencies CD → E and CD → F. [ Union rule]

AD → F

AD → F can be derived through the functional dependencies A → C and CD → F. [ Pseudo-transitivity rule]

         Previous Question                                                                                Next Question

Find the dependency preserving BCNF decomposition of the given relation

Find the dependency preserving BCNF decomposition of the given relation schema / Is the given decomposition is dependency preserving? / How to decompose a relation into BCNF with dependency preservation? / How to perform a dependency preserving decomposition? / Is the table in BCNF?

Question:

7. Assume a relation R(A, B, C, D, E) with the set of functional dependencies F = { A → B, BC → D } and the candidate key (ACE). The relation is not in BCNF. Which of the following is the dependency preserving decomposition for R into BCNF relations?

(a) R₁(B, C, D), R₂(A, B), R₃(A, C, E)

(b) R₁(A, B), R₂(A, C, D), R₃(A, C, E)

(c) R₁(A, B), R₂(A, C, D, E)

(d) All of the above

 

Answer:

(a) R₁(B, C, D), R₂(A, B), R₃(A, C, E)

• BCNF – In simpler terms, the Left Hand Side (LHS) of all the functional dependencies should be the key.

• Dependency preserving decomposition – If a relation R with set F of functional dependencies is decomposed into relations R₁, R₂, R₃, …, R_i then the closure of set of functional dependencies for these relations should satisfy the following; 
• (F₁ U F₂ U F₃ U … U F_i)⁺ = F⁺ 
• That is the closure of union of set of functional dependencies of relations R₁, R₂, …, R_i should be equal to the closure of set of functional dependencies F of R. In other words, all the functional dependencies in (F₁ U F₂ U F₃ U … U F_i)⁺ should be in F⁺ also.

Given: F = { A → B, BC → D }

Step 1: What is the candidate key for R?

A⁺ = AB

(BC)⁺ = BCD

E is not included in any of the functional dependencies, hence E should be in the left hand side and forms one of the key attributes.

(AE)⁺ = ABE

(BCE)⁺ = BCDE

(ACE)⁺ = ABCDE = R.

Hence, (ACE) is the candidate key for R.

Step 2: Which of the functional dependencies violate BCNF?

For the given table R, the following are the dependencies that violate the conditions for BCNF;

{ A → B, BC → D }

Because, the LHS of both FDs are not candidate keys.

Step 3: Break the relation using the violating FDs

Let us consider the FD BC → D and break (decompose) R using this functional dependency;

We create relation R₁ with the schema R₁(B, C, D). [all the attributes of functional dependency BC → D]

We create relation R₂ with the schema R₂(A, B, C, E). [the attributes for R₂ are derived by performing R – D, ie., {A, B, C, D, E} – {D}]

Step 4: R₁ is in BCNF?

The candidate key for R₁ is BC and the FD that holds in R₁ is BC → D. The LHS of the FD is the candidate key. Hence, R₁ is in BCNF.

Step 5: R₂ is in BCNF?

The candidate key for R₂ is ACE and the FD that holds in R₂ is A → B. The LHS of the FD is not the candidate key. Hence A → B violates the rule for BCNF.

Step 5.1: Break R₂ on FD A → B.

We create relation R₂₁(A, B) using A → B, the violating FD.

We create relation R₂₂(A, C, E) using R₂ – B.

Step 6: Is R₂₁ and R₂₂ are in BCNF?

The candidate key for R₂₁ is A and the LHS of A → B is A. Hence, R₂₁ is in BCNF.

The candidate key for R₂₂ is ACD and the FD holds in R₂₂ is trivial FD. Hence, R₂₂ is in BCNF.

Step 7: R into R₁, R₂₁, and R₂₂ is dependency preserving decomposition?

Let us consider the set of FDs of R, R₁, R₂₁, and R₂₂ as F, F₁, F₂₁, and F₂₂.

Apply the rule (F₁ U F₂ U F₃ U … U F_i)⁺ = F⁺.

(F₁ U F₂₁ U F₂₂)⁺ = F⁺

({BC → D} U {A → B} U {ACE → ACE})⁺ = ({ A → B, BC → D})⁺

All the FDs are found in decomposed relations. Hence, R into R₁(B, C, D), R₂₁(A, B), and R₂₂(A, C, E) is dependency preserving BCNF decompositions.

         Previous Question                                                                                Next Question