Determining number of possible super keys of a sub relation

If the closure result of an attribute set contains all the attributes of the relation, then that attribute set is called as a super key of that relation. Thus, we can say " The closure of a super key is the entire relation schema".

There are different ways to find super of a sub relation. Depending upon the given problem we will follow one of these methods.

 Method-1: If a relation contains 'n' number of attributes and 'p' unique candidate keys then, number of possible super keys are =2^n-p

Examples:-

1. Find number of possible super keys for the relation R(ABCD) with key/candidate key {B}.

Solution:

In the given relation n=4 and p=1 then 2^4-1 = 2^3 = 8

Therefore, number of possible super keys =8 and the keys are AB,B,BC,BD, ABC, ABD, BCD, ABCD

Method-2: Consider the relation R(A1,A2,A3, ...........AN) With CK={A1,A2} then number of possible super keys are

n(A1 U A2) = n(A1)+n(A2)-n(A1A2)

Examples:

1. How many super keys exist for the relation R(ABCDEF) with  CK={ ABC, EF}

Solution:

Given relation contains six attributes, so n=6

There are two CK for 

a) For  ABC the value of p=3

b) For EF the value of p=2

c) For { ABC, EF} [ that is n(A1A2) according to formula ]the value of p=5

Therefore, number of super keys =2^6-3 + 2^6-2 - 2^6-5 = 8+16-2 = 22

2. How many super keys exist for the relation R(MNPQRST) with CK={ MNPQ, NRTQ}

solution:

Given relation contains seven attributes, so n=7

There are two CK for 

a) For  MNPQ the value of p=4

b) For NRTQ the value of p=4

c) For { MNPQ, NRTQ} [ that is n(A1A2) according to formula ]the value of p=6 ( since we need to count unique attributes)

Therefore, number of super keys = 2^7-4 + 2^7-4  - 2^7-6 = 8+8-2 = 14

Similarly for the relation  R(A1,A2,A3, ...........AN) With CK={A1,A2,A3} then number of possible super keys are

n(A1 U A2 U A3) = n(A1) + n(A2) + n(A3) - n(A1A2) - n(A2A3) - n(A1A3) + n(A1A2A3)