Closure in database - home page

Database Closure, Explained, Examples, Solved Exercises, Quizzes

Database Closure

• Closure of attribute(s) / How to find candidate key(s) of a table? – Method 1  

• Closure of attribute(s) / How to find candidate key(s) of a table? – Method 2

• Closure of attributes - How to find all candidate keys of a table - Method 3

• Closure of set of functional dependencies

Go back to Database Normalization - Home page

Normalize the relational schema to third normal form

How to normalize a table to 3NF? / Show the steps in 3nf normalization / Normalization solved exercises / 1nf, 2fn, 3nf

Question:

Consider the relation schema Membership for a library database as follows;

Membership (MID, Name, Address, PhoneNum, ParentMID, ISBN, Title, Authors, BorrowDate, ReturnedDate, FineDue, FinePaid).

Here, ParentMID may have the values Null, Father_Name, Mother_Name or both. The following is the set F of functional dependencies that hold in Membership table;

F = { MID → Name, Address, PhoneNum, ParentMID;

(MID, ISBN, BorrowDate) → ReturnedDate, FinePaid, FineDue;

ISBN → Title, Authors}

Normalize the Membership schema to 3NF and show the steps.

Answer:

Given set of FDs;

• FD 1: MID → Name, Address, PhoneNum, ParentMID
• FD 2: (MID, ISBN, BorrowDate) → ReturnedDate, FinePaid, FineDue
• FD 3: ISBN → Title, Authors

Is the table Membership in 1NF?

It is not in 1NF because of the attribute ParentMID which is a multi-valued attribute (when both parents MIDs are issued and stored for a member). To solve this we may create a separate table with MID and ParentMID attributes as follows;

Parent (MID, ParentMID)

For parent table the key is {MID, ParentMID}, hence the table is in 3NF.

After this decomposition, we have the following schemas;

• Schema 1: Parent (MID, ParentMID)
• Schema 2: Membership (MID, Name, Address, PhoneNum, ISBN, Title, Authors, BorrowDate, ReturnedDate, FineDue, FinePaid)

At this stage, the Membership table is in 1NF.

Is Membership in 2NF?

2NF is about eliminating partial keydependencies (if any) from a relational schema. To do this, we need to find the primary key for Membership table.

Let us find the closure of LHS attributes of given functional dependencies to check whether the LHS attributes form a key or not;

From FD1,

(MID)⁺ = MID, Name, Address, PhoneNum ≠ Membership

From FD2,

(MID, ISBN, BorrowDate)⁺ = MID, Name, Address, PhoneNum, ISBN, Title, Authors, BorrowDate, ReturnedDate, FineDue, FinePaid = Membership

Hence, the key for Membership is a composite key (MID, ISBN, BorrowDate).

Now let us check for partial dependencies;

• The attributes MID, Name, Address, and PhoneNum can be determined by using MID alone.

• The attributes ISBN, Title, and Authors can be determined by using ISBN alone. [from FD3].

So, the schema shows partial functional dependencies;

We shall break schema 2 to convert into a set of 2NF schemas;

Schema 2a: (MID, Name, Address, PhoneNum)

Schema 2b: (ISBN, Title, Authors)

Schema 2c: (MID, ISBN, BorrowDate, ReturnedDate, FineDue, FinePaid)

Is schema 2a in 2NF? – Yes. MID is the key and no partial key dependency.

Is schema 2b in 2NF? – Yes. ISBN is the key and no partial dependencies.

Is schema 2c in 2NF? – Yes. (MID, ISBN, BorrowDate) is the composite key and no partial dependencies.

Are schema 1, 2a, 2b and 2c are in 3NF?

3NF is about eliminating transitivefunctional dependencies.

As per the given set of functional dependencies, we do not have any transitive functional dependencies in any of these tables. Hence, the list of 3NF tables is as follows;

• Schema 1: Parent (MID, ParentMID)
• Schema 2a: (MID, Name, Address, PhoneNum)
• Schema 2b: (ISBN, Title, Authors)
• Schema 2c: (MID, ISBN, BorrowDate, ReturnedDate, FineDue, FinePaid)

Go to normalization solved exercises page

Go to normalization multiple choice questions page

 

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