322views

written 2.7 years ago by

binitamayekar ★ 6.7k

• modified 2.7 years ago

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.

Answer -

CANDIDATE KEY - "P"

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

2] R1 = {P, Q, R}, R2 = {R, S, T} = Lossless Join Decomposition.

ADD COMMENT EDIT