Computer Science and Engineering - Tutorials, Notes, MCQs, Questions and Answers

Tuesday, August 26, 2014

How to find key of a given table? - An alternate way

Closure of Attribute Set - Alternate Way / Closure of Attribute Set Algorithm / How do we find a key given a set of attributes? / How to find super key? / Attribute Closure in DBMS / Closure of Attributes Set Example

To find the Closure of attribute/attribute set A, we have to do the following;

a) First of all find the set of all functional dependencies (F⁺) that are implied by a given set of functional dependencies (F).

b) Then take all the FDs from F⁺ that has A on the left hand side of the arrow.

C) Finally, find the union of right hand side of all those functional dependencies that have A on the left hand side. If the union includes all the attributes of the given relation R, then A is the key for the relation.

Example:

Assume a relation schema R = (A, B, C) with the set of functional dependencies F = {A → B, B → C}. Now, we can find the closure of attribute A as follows, according to this method;

Step 1: Find the F⁺.

F+ = { A → B, B → C, A → C } [A → C is derived using Transitivity rule]

Step 2: A → B, and A → C are the two functional dependencies that have common left hand side attribute A.

Step 3: The union of right hand sides ends with A → BC. Hence, A is the one of the keys for the relation R.

Advantages:

Simple.

Drawbacks:

The number of functional dependencies in F⁺ can be as many as 2ⁿ⁺¹ where n is the number of attributes. It costs too much of time.

Very very useful link in knowing closure, canonical cover, normalization etc.

How to find closure of attributes in DBMS?

Closure of Attribute Set / Closure of Attribute Set Algorithm / How do we find a key given a set of attributes? / How to find super key? / Attribute Closure in DBMS / Closure of Attributes Set Example / How to find key for a relation?

Closure of Attribute Set

After finding a set of functional dependencies that are hold on a relation, the next step is to find the Super key for that relation (table). The set of identified functional dependencies play a vital role in finding the key for the relation. We can decide whether an attribute (or set of attributes) of any table is a key for that table or not by identifying the attribute or set of attributes’ closure. If A is an attribute, (or set of attributes) then its attribute closure is denoted as A+.

Algorithm:

The following algorithm will help us in finding the closure of an attribute;

result := A;

while (changes to result) do

for each functional dependency B → C in F do

begin

if B ⊆ result then result := result ∪ C;

end

Let us discuss this algorithm with an example;

Assume a relation schema R = (A, B, C) with the set of functional dependencies F = {A → B, B → C}. Now, we can find the attribute closure of attribute A as follows;

Step 1: We start with the attribute in question as the initial result. Hence, result = A.

Step 2: Take the first FD A → B. Its left hand side (i.e, A) is in the result, hence the right hand side can be included with the result. This lead to result = AB.

Step 3: Take the second FD B → C. Its left hand side (i.e, B) is in the result (or subset of result), hence the right hand side can be included with the result. Now, result = ABC.

We have no more attributes. Hence the algorithm exits. As the result, A⁺ includes all the attributes of relation R. now we would say A⁺ is ABC. And, A is one of the keys of the relation R.

Example:

Question:

Consider a relation R with the schema R(A, B, C, D, E, F) with a set of functional dependencies F as follows;

{AB → C, BC → AD, D → E, CF → B}

Find the super key for this relation.

Solution:

Finding (AB)⁺

First, let us find (AB)⁺ , the closure of attribute set AB (We do not need to test all the attributes individually. Instead we can try with those attributes that are on the left hand side of any FD.)

· result = AB

· As AB determines C, C can be included with the result. Hence, result = AB U C = ABC.

· According to second FD BC → AD, the attributes B and C together can identify both A and D. Hence, result = ABC U AD = ABCD

· If you know D, you will know E according to third FD D → E. so, result = ABCD U E = ABCDE.

· F cannot be identified by any of these FDs. And our result can include ABCDE attributes only.

Hence, the solution is AB is not the key for R. The reason is, the closure of AB, i.e., (AB)⁺ does not include all the attributes of R in the result.

Finding (ABF)⁺

Then what would be the key for R?. As I told you initially, we can try all the left hand side attributes (because they are the determiners), or some of their combination. From the above example, we would get an idea to include F as one of the key attribute. So, let us try to find (ABF)⁺ , the closure of attribute set ABF.

· result = ABF

· from the above example, we could say (AB)⁺ = ABCDE

· we know C and F, then according to CF → B, we would deduce the result as ABCDEF, which includes all the attributes from R.

Hence, the solution is ABF is one of the key for R. because, (ABF)⁺ includes all the attributes of R.

Go to Normalization Exercises - Solved page

Go to How to find closure of set of functional dependencies page

Very very useful link in knowing closure, canonical cover, normalization etc.

Saturday, August 23, 2014

Closure of Set of Functional Dependencies - Example

Finding Closure of Set of Functional Dependencies Examples / Solved Examples - Closure of Set F of Functional Dependencies / Example for finding F⁺ / What is meant by the closure of a set of functional dependencies illustrate with an example

Closure of Set F of Functional Dependencies can be found from the given set of functional dependencies by applying the Armstrong's axioms. Closure is denoted as F⁺.

Recall the axioms;

Reflexivity rule	If X is a set of attributes, and Y is subset of X, then we would say, X → Y.
Augmentation rule	If X → Y, and Z is another set of attributes, then we write XZ → XY.
Transitivity rule	If X → Y, and Y → Z, then X → Z is true.
Union rule	If X → Y and X → Z, then X → YZ is true.
Decomposition rule	Its reverse of Rule 4. If X → YZ, then X → Y, and X → Z are true
Pseudotransitivity rule	If X → Y and ZY → A are true, then XZ → A is also true.

Example 1 - Finding F⁺ of given set F of functional dependencies:

Consider a relation R with the relation schema R = (A, B, C, D, E). Assume that the relation holds the following set of functional dependencies. That is, F is given as follows;

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

Find the F⁺ (Closure).

From A → BC and B → D, we can deduce A → D (By applying Transitivity rule)

Through A → BC, A → D, and CD → E, we can derive A → E (By applying Transitivity rule)
Through above deductions, we can write A → ABCDE.

From E → A, and A → ABCDE, we can derive E → ABCDE
From CD → E and E → ABCDE, then CD → ABCDE
From B → D, we can derive BC → CD using Augmentaion rule. It would further mean, BC → ABCDE

Like this, we can continue to derive all the possible functional dependencies.

We would write all the functional dependencies as follows to get F⁺;

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