Define lossless-join decomposition with example

Lossless Decomposition, Lossless-Join Decomposition, Define lossless decomposition, lossless join decomposition example, properties of lossless decomposition

Lossless Decomposition

Assume that a relation R with set of functional dependencies F. If R is decomposed into relations R1 and R2, then this decomposition is said to be lossless decomposition (or lossless-join decomposition) if and only if at least one of the following functional dependencies holds in the closure of set of functional dependencies F⁺;

R1 ∩ R2 → R1

R1 ∩ R2 → R2

R1 ∩ R2 gives you the attribute or set of attributes that is/are used in joining R1 and R2. The above functional dependencies ensure that the attributes involved in the natural join of R1 and R2 are candidate keys for at least one of the relations R1 and R2.

In other words, R1 ∩ R2 should be a determinant that determines all the attributes of one of relations R1 and R2.

Example:

Assume a relation Student_Grades with the attributes Reg_no, Name, Semester, and Grade. Let us suppose the following functional dependencies are held in Student_Grades table;

F = { Reg_no → Name, Reg_No Semester → Grade}

Key for Student_Grades will be (Reg_No, Semester), a composite primary key (whole primary key) [Note: find closureof attributes to identify keys]

Is Student_Grades in 2NF?

NO. The reason is the partial dependency Reg_No → Name holds on Student_Grades.

The solution is to decompose Student_Grades. Let us decompose into the following relations (keys are underlined);

Student (Reg_No, Name)

SGrades (Reg_No, Semester, Grade)

Is this decomposition a lossless-join decomposition?

YES.

Student ∩ SGrades → Student.

i.e., Reg_No → Reg_No, Name

Reg_No is the common attribute in both relations and it determines all the attributes of one of the relations. Hence, the decomposition is lossless-join decomposition.

******************

Go back to Normalization – solved exercises page.

Is the given table in second normal form 2nf?

Is the given table in Second Normal Form (2NF)? Normalization solved exercise, second normal form example, normalize the given table to 2nf.

Normalization Solved Exercise

Consider a relation Movies_Screened with attributes Theatre_name, Movie, Day, Time, and Age_restriction. A sample table is given below;

Theatre_name	Movie	Day	Time	Age_restriction
Abirami	Gethu	Wed	10:00	15
Abirami	Gethu	Wed	15:00	15
Palazzo	Theri	Fri	10:00	15
Palazzo	Enthiran	Fri	10:00	12
Sathyam	Enthiran	Thu	10:00	12

A theatre can screen more than one movie on the same day and time but on different screens. Age_restriction provides the minimum age limit to watch that particular movie as instructed by the central board of film certification. Does this relation satisfy 2NF conditions? Or, is Movies_Screened in 2NF?

Solution:

The properties to be satisfied for 2NF relations are;

• Table should be in 1NF

• All non-key attributes must fully functionally dependent on the whole key (primary key).

Is Movies_Screened in 1NF?

YES. All the attributes contain only atomic values. Hence, Movies_Screened is in 1NF.

Is Movies_Screened in 2NF?

To check this, first we need to find the key for Movies_Screened. To find the key we need the possible functional dependencies that are held in the given table.

No attributes uniquely identify any other attributes in the given table.

For example,

• Theatre_name → Movie – Not hold, because it is given that a theatre may show more than one movies on different screens.

• Theatre_name → Day – Not hold, because it is given that a theatre may show more than one shows on the same day.

And so on. [Readers are requested to work on other attributes/attribute sets like this.]

• Movie → Age_restriction – Holds, because the value of Age_restriction can be uniquely identified by the value of Movie.

• Theatre_name, Movie, Day, Time → Age_restriction – Holds, because all these attributes Theatre_name, Movie, Day, and Time as a whole (together) uniquely determines the value of Age_restriction. Hence, this is the valid functional dependency.

From the above functional dependency, it is very clear that (Theatre_name, Movie, Day, Time) is the key for Movies_Screened table. It is a composite primary key.

For a table to be in 2NF, all non-key attributes must fully functionally dependent on the whole key. In our table, Age_restriction is the only non-key attribute. Also, it can be identified by the whole key and by Movie attribute. That means, the functional dependency

Movie → Age_restriction,

shows partial dependency.

Hence, the table Movies_Screened is not in 2NF.

*************

Go back to Normalization – solved exercises page.

Find the primary key of a database table

Set of solved exercises in Normalization / Normalization Solved Examples / How to find candidate keys, and primary keys in database? / Sets of examples to find the keys of a tables / Process of Key finding in a database – Examples

Question:

The following relation schema is used to store information about the customers of a car service center.

Customer (Customer_ID, CName, CAddr, Phone, Customer_Visit_Date, Service_Advisor_ID, SAName, SAPhone, No_of_Cars_Serviced, Service_Date)

A customer is identified with a unique Customer_ID, he can have only one phone number, and he may have visited the service center many times. There are more service advisors and each advisor services many cars on a given service date. Any service advisors can be reached at only one phone number.

Find the primary key for Customer.

Solution:

From the given information, we can derive the following set of functional dependencies;

• Customer_ID → CName CAddr Phone 
• [as customer id is unique, every id is related to exactly one name, one address, and one phone]

The FDs that do not hold Customer_ID → Customer_Visit_Date – This FD does not hold because a customer can visit many times. Hence, customer id cannot uniquely determine customer visit date. Customer_ID → Service_Advisor_ID – This FD does not hold because a might have been attended by different advisors during each of his visit. Service_Advisor_ID → Service_Date No_of_Cars_Serviced – This FD does not hold because a service advisor services every day with number of cars. Hence, we cannot uniquely determine the number of cars serviced or the service dates. Service_Date → No_of_Cars_Serviced – This FD does not hold because on a given service date other service advisors may have serviced many cars as well.

• Service_Advisor_ID → SAName SAPhone 
• [Service advisors name and phone can be uniquely determined by service advisor id]

• Service_Advisor_ID Service_Date → No_of_Cars_Servicesd 
• [if we know the service date and the advisor id, we can uniquely determine the number of cars serviced on a data by an advisor]

Finding closure of attributes/attributes sets

Normally, it is enough to find the closure for the LHS (Left Hand Side) attributes of the FDs. [Refer here to know how to find closure ofan attribute/attribute set]

(Customer_ID)⁺ = Customer_ID, CName, CAddr, Phone

• [(Customer_ID) does not derive all the attributes of customer]

(Service_Advisor_ID)⁺ = Service_Advisor_ID, SAName, SAPhone

• [(Service_Advisor_ID) does not derive all the attributes of customer]

(Service_Advisor_ID, Service_Date)⁺ = Service_Advisor_ID, SAName, SAPhone, Service_Date, No_of_Cars_Serviced

• [(Service_Advisor_ID, Service_Date) does not derive all the attributes of customer]

(Customer_ID, Service_Advisor_ID, Service_Date)⁺ = Customer_ID, CName, CAddr, Phone, Service_Advisor_ID, SAName, SAPhone, Service_Date, No_of_Cars_Serviced

• [(Customer_ID, Service_Advisor_ID, Service_Date) does not derive all the attributes of customer.]

Here customer visit date is missing. And this attribute is not part of any FDs. Hence, we can include customer_visit_date attribute to the left hand side by assuming the trivial FD, Customer_Visit_Date → Customer_Visit_Date.

Then we have,

(Customer_ID, Customer_Service_Date, Service_Advisor_ID, Service_Date)⁺ = Customer_ID, CName, CAddr, Phone, Customer_Service_Date, Service_Advisor_ID, SAName, SAPhone, Service_Date, No_of_Cars_Serviced

(Customer_ID, Customer_Service_Date, Service_Advisor_ID, Service_Date) derives all the attributes of Customer. Hence, this combination forms the key for Customer.

Customer_ID Customer_Visit_Date Service_Advisor_ID Service_Date → CName CAddr Phone SAName SAPhone No_of_Cars_Serviced - This FD holds on Customer

(Customer_ID Customer_Visit_Date Service_Advisor_ID Service_Date) is the key and it is a composite primary key.

Go back to Normalization – solved exercises page.

Related Posts:

Various uses of attribute closure

How to find Closure?