1
4.7kviews
For the following dependencies find the candidate keys.

For the following dependencies find the candidate keys. A={ P,Q,R,S,T } P->QR , Q->S , RS->T, R->S Is the following decomposition a lossless join? 1. R1 = {P,Q,R}, R2 ={P,S,T} 2. R1={P,Q,R} R2={R,S,T}

2
286views

Relational Schema A = {P,Q,R,S,T}

The Functional Dependencies =

$P → QR$

$Q → S$

$RS → T$

$R → S$

The Decomposition of Relation A =

1] R1 = {P, Q, R}, R2 = {P, S, T}

2] R1 = {P, Q, R}, R2 = {R, S, T}

## Candidate Key

• Candidate Key - It is a set of the minimal attribute(s) that can identify each tuple uniquely in the given relation.
• That means any relation can have one or more candidate keys.
• Candidate Key for the given Relational Schema A based on the given Functional Dependencies (FDs).

Let's find out the candidate key for the given relational schema A.

Step 1 -

• Identify all essential attributes for the given relation A.
• Essential attributes are those attributes that are not present on the Right Hand Side (RHS) of any functional dependency and always be a part of every candidate key.

Therefore,

• The essential attribute for the given relation is only one which is P.
• That means P will be a part of every Candidate key.

Step 2 -

• Now, check whether the essential attribute P can determine all remaining non-essential attributes.
• To do this find out the closure of P.

Therefore,

$\{P\}^+ = \{P\}$

$= \{P, Q, R\} (......Using\ P → QR)$

$= \{P, Q, R, S\}(.....Using\ Q → S)$

$= \{P, Q, R, S, T\}(.....Using\ RS → T)$

$$\{P\}^+ = \{P, Q, R, S, T\}$$

Hence, this shows that P can determine all the attributes of the given Relation A based on Functional Dependencies (FDs).

Therefore,

'P' is the only possible CANDIDATE KEY for the given Relation A.

# Decomposition in DBMS

• Decomposition divides a single relation into two or more sub relations.
• Decomposition can produce either Lossless Join Decomposition or Lossy Join Decomposition.

How to identify Whether Decomposition Is Lossless Or Lossy?

• If a relation A is decomposed into two sub relations R1 and R2.
• Then,

• If all the following conditions satisfy, then the decomposition is Lossless.
• If any of these conditions is not satisfied, then the decomposition is Lossy.

Condition 1 -

• The Union of both the sub relations must contain all the attributes that are present in the original relation R.

Therefore,

$$R1 ∪ R2 = A$$

Condition 2 -

• The Intersection of both the sub relations must not be null.
• That means some common attribute must be present in both of the sub relations.

Therefore,

$$R1 ∩ R2 ≠ ∅$$

Condition 3 -

• The Intersection of both the sub relations must be a super key of either R1 or R2 or both.

Therefore,

$$R1 ∩ R2 = Super\ key\ of\ R1\ or\ R2\ or\ both$$

Let's find out the given decompositions are lossless join or lossy join

## 1] R1 = {P, Q, R}, R2 = {P, S, T}

• Let's check for all conditions one by one.
• If any condition is not satisfied that means decomposition is lossy otherwise lossless.

Condition 1 - Union of R1 and R2

$$R1 \{P, Q, R\} ∪ R2 \{P, S, T\} = A \{P, Q, R, S, T\}$$

• That shows Union of sub relations contains all the attributes of relation A.

Therefore, Condition - 1 is satisfied.

Condition 2 - Intersection of R1 and R2

$$R1 \{P, Q, R\} ∩ R2 \{P, S, T\} = A \{P\}$$

• That shows Intersection of sub relations must contain at least one common attribute 'P' in both sub relations and can not be null.

Therefore, Condition - 2 is satisfied.

Condition 3 - Intersection of both the sub relations must be a super key of either R1 or R2 or both.

• As we know already that

$$R1 \{P, Q, R\} ∩ R2 \{P, S, T\} = A \{P\}$$

• Now, need to check whether attribute P is the super key of any of the sub relations or not.
• To do this find out the closure of P.
• As we already find out the closure of P in the previous answer.

$$\{P\}^+ = \{P, Q, R, S, T\}$$

• This shows that Attribute P can determine both the attributes of Sub Relations R1 and R2.
• Therefore, it acts as a Super key for both the Sub Relations R1 and R2.

Therefore, Condition - 3 is satisfied.

Decomposition R1 = { P, Q, R }, R2 = { P, S, T} satisfies all the three condition therefore it is a Lossless Join Decomposition.

## 2] R1 = {P, Q, R}, R2 = {R, S, T}

• Again, repeat the same procedure as shown in the above question to find out whether the given decomposition is a lossless join or a lossy join.

Condition 1 - Union of R1 and R2

$$R1 \{P, Q, R\} ∪ R2 \{R, S, T\} = A \{P, Q, R, S, T\}$$

• That shows Union of sub relations contains all the attributes of relation A.

Therefore, Condition - 1 is satisfied.

Condition 2 - Intersection of R1 and R2

$$R1 \{P, Q, R\} ∩ R2 \{R, S, T\} = A \{R\}$$

• That shows Intersection of sub relations must contain at least one common attribute 'R' in both sub relations and can not be null.

Therefore, Condition - 2 is satisfied.

Condition 3 - Intersection of both the sub relations must be a super key of either R1 or R2 or both.

• As we know already that

$$R1 \{P, Q, R\} ∩ R2 \{R, S, T\} = A \{R\}$$

• Now, need to check whether the attribute R is the super key of any of the sub relations or not.
• To do this find out the closure of R.

Therefore,

$\{R\}^+ = \{R\}$

$= \{R, S\} (......Using\ R → S)$

$= \{R, S, T\}(.....Using\ RS → T)$

$$\{R\}^+ = \{R, S, T\}$$

• This shows that Attribute R can determine all the attributes of Sub Relations R2.
• Therefore, it acts as a Super key for the Sub Relations R2.

Therefore, Condition - 3 is satisfied.

Decomposition R1 = {P, Q, R}, R2 = {R, S, T} also satisfies all the three conditions therefore it is also a Lossless Join Decomposition.