Super Key in DBMS

A Super Key in DBMS is a set of one or more attributes (columns) in a table that can uniquely identify a tuple (record) in that table by its attribute or combination of attributes.

Here are key points about Super Key in DBMS:

• The super set of any candidate key is a super key (i.e., a candidate key is always a subset of a super key).
• More than one candidate key can exist for a super key.
• Every candidate key is a super key, but not every super key is a candidate key.
• Super keys can include unnecessary attributes beyond what is needed for uniqueness.
• They play a crucial role in ensuring data integrity and are used in relational database design.

Key Characteristics of Super Key in DBMS

Here are the key characteristics of a super key in DBMS

1. Uniqueness

A super key uniquely identifies each tuple (row) in a table. No two rows can have the same values for the attributes included in the super key.

Example: If ID is unique, then {ID} is a super key.

2. Combination of Attributes

A super key can contain one attribute or multiple attributes together. The combined values must uniquely identify each row.

Example: {ID, Name} can be a super key if ID alone is unique.

3. Candidate Key is Compulsory

Every super key must contain at least one candidate key because a candidate key is the minimum attribute set required to uniquely identify a tuple. Without including a candidate key, uniqueness cannot be guaranteed. We can also say that candidate key is always a subset of a super key

Example: If {ID} is a candidate key, then {ID} and {ID, Name} can be super keys, but {Name} alone cannot be a super key if it is not unique.

4. May Include Extra Attributes

A super key can have additional attributes that are not required for uniqueness. These extra attributes make the key non-minimal.

Example: {ID, Salary} is a super key if ID alone is enough to identify rows.

5. Multiple Super Keys Possible

A single relation can have many super keys because different attribute combinations may uniquely identify tuples.

Example: {ID}, {ID, Name}, and {ID, Email} can all be super keys.

6. Supports Normalization

Super keys help determine functional dependencies, which are used in normalization to reduce redundancy and improve database design.

Example: Knowing {ID} → Name, Salary helps during normalization.

Now we will see various examples of super key calculations over the given candidate keys and attributes

Category – 1: Finding Super Key in DBMS Using a Single Candidate Key

Finding the super keys in DBMS depends on how many candidate keys exist in the relation (R). If the relation (R) has “n” attributes and only a single candidate key, then superkeys can be calculated using the following formula

• Super keys = 2^n-k

where

• “n” represents all the attributes in the relation
• “k” represents the length of the candidate key

Finding Super Key in DBMS Example 1:

Suppose

• A relation R(A, B) represents a table with two attributes. Therefore, n=2.
•  There is a single candidate key, which is {A}, whose length is 1. Therefore, K =1

Using the diagram below, calculate all super keys from the given data.

   Finding Super Key in DBMS Example 2:

Suppose

• A relation R(A, B, C) represents a table with three attributes. Therefore, n=3.
•  There is a single candidate key which {A}, whose length is 1. Therefore, K =1

Using the diagram below, calculate all super keys from the given data.

Finding Super Key in DBMS Example 3:

Suppose

• A relation R(A, B, C, D) represents a table with four attributes. Therefore, n=4.
•  There is a single candidate key which {A}, whose length is 1. Therefore, K =1

Using the diagram below, calculate all super keys from the given data.

Finding Super Key in DBMS Example 4:

Suppose

• A relation R(A, B, C) represents a table with three attributes. Therefore, n=3.
•  There is a single candidate key which {A,B}, whose length is 2. Therefore, K =2

Using the diagram below, calculate all super keys from the given data.

Finding Super Key in DBMS Example 5:

Suppose

• A relation R(A, B, C, D, E) represents a table with five attributes. Therefore, n=5.
•  There is a single candidate key which {A,B,C}, whose length is 3. Therefore, K =3

Using the diagram below, calculate all super keys from the given data.

Finding Super Key in DBMS Example 6:

Suppose

• A relation R(A, B, C, D, E) represents a table with three attributes. Therefore, n=5.
•  There is a single candidate key which {A,B,C,D,E}, whose length is 5. Therefore, K =5

Using the diagram below, calculate all super keys from the given data.

Category – 2:  Finding Super Key in DBMS Using a Multiple Candidate Keys, each of Same Length

When a relation contains several candidate keys. Each candidate key can generate many superkeys. If we add super keys produced by each candidate key, some super keys may appear in more than one group. Therefore, duplicates occur. The Inclusion–Exclusion Principle removes these duplicate counts.

According to the Inclusion–Exclusion Principle

• Total Super Keys = (Sum of single candidate-key counts) − (Sum of pair overlaps) + (Sum of triple overlaps) − (Sum of quadruple overlaps) + …

Simply, we can write as well

Pattern: Singles − Pairs + Triples − Quadruples + Quintuples − Sextuples + Septuples − Octuples + …

So, we can say that Odd-numbered groups are added (+), and even-numbered groups are subtracted (−). Let’s discuss some examples where multiple candidate keys exist.

Finding Super Key in DBMS – Example 7

To calculate the super keys of example 7, the following data is given

• A relation R(A, B, C) represents a table with three attributes. Therefore, n=3.
•  There are two candidate keys {A}, {B}, each of length 1.

Using the diagram below, calculate all super keys from the given data.

Let’s explain the above example 7 in the following steps

Step 01: Understanding the Formula

The formula is divided into two different parts based on the number of candidate keys combined.

Part 1: Count super keys formed from single candidate keys

• + 2^n-1 + 2^n-1

Part 2: Subtract super keys formed from pair candidate-key overlaps

• − 2^n-2

Step 02: Single Candidate Keys to Super Keys 

• For the candidate key {A}, every super key must contain A. After fixing A, the remaining attributes B and C can be added in different combinations. Therefore, {A} generates (2^3-1 = 4) super keys: {A}, {A,B}, {A,C}, {A,B,C}.
• For the candidate key {B}, every super key must contain B. After fixing B, the remaining attributes A and C can be added in different combinations. Therefore, {B} generates (2^3-1=4) super keys: {B}, {A,B}, {B,C}, {A,B,C}.

Note: Some super keys like {A,B} and {A,B,C} appear in both candidate key lists of {A} and {B}. So, they are counted twice. To fix this, we will subtract them once in the next step when we use the pair candidate key {A,B}.

Step 03: Single to Pair Candidate Keys Conversions Process 

To get the pair candidate key from {A} and {B}, simply combine both candidate keys into one set: {A} + {B} = {A,B}

Step 04: Pair Candidate Keys to Super Keys 

The candidate key {A} generates some super keys, and the candidate key {B} also generates some super keys. Some of these super keys are the same because they contain both A and B. Therefore, these common super keys are counted twice.

To find these common super keys, combine {A} and {B} to form pair candidate key {A,B} which generates (2^3-2 =2 ) common super keys as given below

• {A, B}
• {A, B, C}

Since these two super keys appear in both the {A} list and the {B} list, they must be subtracted once to get the correct total number of super keys.

Finding Super Key in DBMS Example 8:

To calculate the super keys of example 8, the following data is given

• A relation R(A, B, C, D) represents a table with four attributes. Therefore, n=4.
•  There are three candidate keys {A}, {B}, {C} each of length 1.

Using the diagram below, calculate all super keys from the given data.

Let’s explain the above example 8 in the following steps

Step 01: Understanding the Formula 

The formula is divided into three different parts based on the number of candidate keys combined.

Part 1: Count super keys formed from single candidate keys

• + 2^n-1 + 2^n-1 + 2^n-1

Part 2: Subtract super keys formed from pair candidate-key overlaps

• − 2^n-2 − 2^n-2 − 2^n-2

Part 3: Add super keys formed from triple candidate-key overlaps

• + 2^n-3

Step 02: Single Candidate Keys to Super Keys 

For candidate key {A}: All super keys must contain A 

• {A}, {A,B}, {A,C}, {A,D}, {A,B,C}, {A,B,D}, {A,C,D}, {A,B,C,D}

For candidate key {B}:

All super keys must contain B

• {B}, {A,B}, {B,C}, {B,D}, {A,B,C}, {A,B,D}, {B,C,D}, {A,B,C,D}

For candidate key {C}:

All super keys must contain C

• {C}, {A,C}, {B,C}, {C,D}, {A,B,C}, {A,C,D}, {B,C,D}, {A,B,C,D}

Step 03: Single to Pair Candidate Keys Conversions Process 

Pair candidate keys are formed as: {A, B}, {A, C}, {B, C} over single candidate keys {A}, {B}, and {C}. The following diagram shows it

Super Keys Using Pair Candidate Keys – Example 08

The following diagram shows all super keys formed over the paired candidate keys, which are {A,B}, {A,C}, and {B,C}.

Single to Triple Candidate Keys Conversions 

Triple candidate keys are formed as: {A, B, C} over single candidate keys {A}, {B}, and {C}. The following diagram shows it

Finding Super Keys Using Triple Candidate Keys

The following diagram shows all super keys formed over the triple candidate keys, which is {A,B,C}. it is called triple because it involves three candidate keys, i.e., {A}, {B}, and {C}.

Finding Super in DBMS Key Example 9:

Let’s explain the above example 9 in the following steps

Step 01: Understanding the Formula

The formula is divided into four different parts based on the number of candidate keys combined.

Part 1: Count super keys formed from single candidate keys

• + 2^n-1 + 2^n-1 + 2^n-1 + 2^n-1

Part 2: Subtract super keys formed from pair candidate-key overlaps

• − 2^n-2 − 2^n-2 − 2^n-2 − 2^n-2 − 2^n-2 − 2^n-2

Part 3: Add super keys formed from triple candidate-key overlaps

• + 2^n-3 + 2^n-3 + 2^n-3 + 2^n-3

Part 4: Subtract super keys formed from quadruple candidate-key overlap

• − 2^n-4

Step 02: Single Candidate Keys to Super Keys 

The single candidate keys are {A}, {B}, {C}, and {D}. The number of super keys over single candidate keys are given in the following diagram

Step 03: Single to Pair Candidate Keys Conversions Process 

Super Keys Using Pair Candidate Keys – Example 09

Single to Triple Candidate Keys Conversions – Example 09

Finding Super Keys Using Triple Candidate Keys in Example 09

Single to Quadruple Candidate Keys Conversions in Example 09

Finding Super Keys Using Quadruple Candidate Keys in Example 09

Finding Super Key Example 10:

To calculate the super keys of example 10, the following data is given

• A relation R(A, B, C, D, E) represents a table with five attributes. Therefore, n=5.
•  There are five candidate keys {A}, {B}, {C}, {D}, {E} each of length 1.

Using the diagram below, calculate all super keys from the given data.

Let’s explain the above example 10 in the following steps

Step 01: Understanding the Formula

The formula is divided into five different parts based on the number of candidate keys combined.

Step 02: Single Candidate Keys to Super Keys 

The single candidate keys are {A}, {B}, {C}, {D} and {E}. The number of super keys over single candidate keys is given in the following diagram

Super Keys Using Pair Candidate Keys – Example 10

Finding Super Keys Using Triple Candidate Keys in Example 10

Finding Super Keys Using Quadruples Candidate Keys in Example 10

Finding Super Keys Using Quintuples Candidate Keys in Example 10