Introduction To DBMS

Super Key in DBMS Examples

Relationship in DBMS

Normalization

Relational Algebra

Structured Query Language (SQL)

PL-SQL

Transaction

Concurrency Control

Schedule

Indexing

File Organization

MIX

Super Keys in DBMS Examples

A super key in DBMS is a collection of one or more attribute that uniquely identifies each tuple (record) within a relation (table). A super key may consist of a single attribute or a combination of multiple attributes, provided that together. They ensure the uniqueness of every record.

There are six important characteristics of super keys in DBMS are as follows:

Uniqueness
Single or Multiple Attributes
Contains a Candidate Key
Candidate key as a Subset
Additional (Non-Essential) Attributes
Role in Relational Database Design

Key Characteristics of Super Keys in DBMS

Let’s explain key characteristics of super keys in DBMS

1.Uniqueness

The defining property of a super key is its ability to uniquely identify every tuple (row) in a relation. This ensure that no two records share the same values for the attributes included in the super key.

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

2.Single or Multiple Attributes

A super key may consist of a single attributes or a combination of multiple attributes. Regardless of the number of attributes, the selected set must uniquely identify every tuple in the relation.

Example: If ID is unique, then both {ID} and {ID, Name} and valid super keys.

3. Contains a Candidate Key

Every super key must include at least one candidate key. Since a candidate key is the minimum set of attributes required to uniquely identify a tuple, a super key cannot exist without containing a candidate key.

Example: If {ID} is a candidate key, then every valid super key must include ID.

4. Candidate Key as a Subset

A candidate key is always a subset of a super key. By adding one or more extra attributes to a candidate key, a new super key is formed while preserving uniqueness.
Example: If {ID} is a candidate key, then {ID, Name} and {ID, Department} are also super keys.

5. Additional (Non-Essential) Attributes

A super key may contain attributes that are not necessary for uniquely identifying a tuple. These additional attributes do not effect uniqueness but make the super key not-minimal.

Example: If {ID} uniquely identifies each record, then {ID, Name, Age} is still a super key even though name are age are not required.

6. Role in Relational Database Design

Super key is play an important role in relational database design by ensuring that each record can be uniquely identified. They provide the foundation for identifying candidate keys and help maintain data consistency and integrity within the database.

How to Find Super Keys in DBMS

The method used to determine super keys depends on the number of candidate keys available in a relation.

If the relation has only one candidate key, apply the Single Candidate Key Formula described in Category 1.
If the relation has multiple candidate key, use the Inclusion-Exclusion Principle explained in Category 2 to eliminate duplicate super keys.
Accordingly, the process of finding super keys can be divided into the following categories.

Category 1: Finding Super Keys in DBMS Using a Single Candidate key

The number of super keys in a DBMS relation depends on the candidate keys defined for that relation. When a relation R contains n attributes and has only one candidate key of length k, the total number of super keys can be calculated using the following formula:

Super Keys = 2ⁿ⁻ᵏ

The following section presents illustrative examples for determining super keys based on a single candidate key of length K.

Finding Super Key in DBMS Example 1:

When the following data is given

Relation R(A, B) has two attributes, so n = 2.
The only candidate key is {A} having length =1, Therefore, K =1.

By using the diagram below, Let’s calculate all super keys of example 1 from the given data.

Finding Super Key in DBMS Example 2:

When the following data is given

Relation R(A, B) has two attributes, so n = 2.
The only candidate key is {B} having length =1, Therefore, K =1.

By using the diagram below, Let’s calculate all super keys of example 2 from the given data.

Finding Super Key in DBMS Example 3:

When the following data is given

Relation R(A, B) has two attributes, so n = 2.
The two candidate key is {A,B} having length =2, Therefore, K =2.

By using the diagram below, Let’s calculate all super keys of example 3 from the given data.

Finding Super Key in DBMS Example 4:

When the following data is given

Relation R(A, B, C) has three attributes, so n = 3.
The single candidate key is {A} having length =1, Therefore, K =1.

By using the diagram below, Let’s calculate all super keys of example 4 from the given data.

Finding Super Key in DBMS Example 5:

When the following data is given

Relation R(A, B, C) has three attributes, so n = 3.
The two candidate key is {B, C} having length =2, Therefore, K =2.

By using the diagram below, Let’s calculate all super keys of example 5 from the given data.

Finding Super Key in DBMS Example 6:

When the following data is given

Relation R(A, B, C) has three attributes, so n = 3.
The three candidate key is {A, B, C} having length =3, Therefore, K =3.

By using the diagram below, Let’s calculate all super keys of example 6 from the given data.

Finding Super Key in DBMS Example 7:

When the following data is given

Relation R(A, B, C, D) has four attributes, so n = 4.
The two candidate key is {A, B} having length =2, Therefore, K =2.

By using the diagram below, Let’s calculate all super keys of example 7 from the given data.

Finding Super Key in DBMS Example 8:

When the following data is given

Relation R(A, B, C, D) has four attributes, so n = 4.
The three candidate key is {A, B, C} having length =3, Therefore, K =3.

By using the diagram below, Let’s calculate all super keys of example 8 from the given data.

Finding Super Key in DBMS Example 9:

When the following data is given

Relation R(A, B, C, D) has four attributes, so n = 4.
The four candidate key is {A, B, C, D} having length =4, Therefore, K =4.

By using the diagram below, Let’s calculate all super keys of example 9 from the given data.

Finding Super Key in DBMS Example 10:

When the following data is given

Relation R(A, B, C, D, E) has five attributes, so n = 5.
The five candidate key is {A, B, C, D, E} having length =5, Therefore, K =5.

By using the diagram below, Let’s calculate all super keys of example 10 from the given data.

Category 2: Finding Super Keys in DBMS Using Multiple Candidate Keys of the Same Length

When a relation contains multiple candidate keys of the same length, each candidate key generates its own set of super keys. Some of these super keys may be common to more than one candidate key, resulting in duplicate counting. To ensure that each super key is counted only once, the

Inclusion-Exclusion principle is applied.

This approach is used when:

A relation R contains n attributes.
Multiple candidate keys of the same length are given.

The goal is to determine the total number of distinct super keys.

Inclusion-Exclusion Principle: General Counting Rule

The total number of distinct super keys in relation with multiple candidate keys can be obtained using the Inclusion-Exclusion Principle. This method correct duplicate counting by following an alternating sequence of addition and subtraction .General Formula: Total Super Keys = (Sum of Singles) – (Sum of Pairs) + (Sum of Triples) – (Sum of Quadruples) + …. Pattern: Single – Pairs + Triples – Quadruples + Quintuples – Sextuples + Septuples – Octuples + … According to this rule:

Odd-numbered groups are added (+).

Even-numbered groups are subtracted (-).The example that follow illustrate the practical application of this principle.

Finding Super Key in DBMS Example 11:

When the following data is given

A relation R(A, B) consists of two attributes, so n = 2.

The relation has one candidate key, {A}, whose length is 1. Therefore, k = 1.

Using the diagram below, we can calculate all the super keys for Example 11 based on the given information.

The following section presents a step by step explanation of Example 11.

Step 01: Deriving Super Keys from Individual Candidate Keys

For the candidate key {A} :

Every super key include A. Therefore, the generated super keys are : {A}, {A,B}

Finding Super Key in DBMS Example 12:

When the following data is given

A relation R(A, B) consists of two attributes, so n = 2.

The relation has one candidate key, {B}, whose length is 1. Therefore, k = 1.

Using the diagram below, we can calculate all the super keys for Example 12 based on the given information.

The following section presents a step by step explanation of Example 12.

Step 01: Deriving Super Keys from Individual Candidate Keys

For the candidate key {B} :

Every super key include B. Therefore, the generated super keys are : {B}, {A,B}

Finding Super Key in DBMS Example 13:

When the following data is given

A relation R(A, B, C) consists of three attributes, so n = 3.

The relation has one candidate key, {A}, whose length is 1. Therefore, k = 1.

Using the diagram below, we can calculate all the super keys for Example 13 based on the given information.

The following section presents a step by step explanation of Example 13.

Step 01: Deriving Super Keys from Individual Candidate Keys

For the candidate key {A} :

Every super key include A. Therefore, the generated super keys are : {A}, {A,B}, {A,C}, {A,B,C}

Finding Super Key in DBMS Example 14:

When the following data is given

A relation R(A, B, C) consists of three attributes, so n = 3.

The relation has two candidate key, {A}, {B}, whose length is 2. Therefore, k = 2.

Using the diagram below, we can calculate all the super keys for Example 14 based on the given information.

The following section presents a step by step explanation of Example 14.

Step 01: Formula Explanation

The calculation process is divided into two parts.

In the above diagram

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻²

Step 02: Constructing Super Keys ( Single Candidate Keys to Super Keys )

Starting with {A}, all valid super keys must contain A. This result in : {A}, {A,B}, {A,C}, {A,B,C}

Repeating the process for {B} gives : {B}, {A,B}, {B,C}, {A,B,C}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

Given K single candidate keys, pair candidate keys are obtained by choosing two distinct candidate keys at a time. Each selected pair is combined into a single set using the union operation. As shown below

{A} ∪ {B} = {A,B}

Formula:

C(K , 1) = {K(K-1)} / {2!}

In Example 14, there are 2 single candidate keys, therefore K = 2.

C(2 , 1) = {2(2-1)} / {2} = 1

Thus, only one pair candidate key can be formed, which is {A,B}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B}, all valid super keys must contain A,B. This result in : {A,B}, {A,B,C}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 15:

When the following data is given

A relation R(A, B, C) consists of three attributes, so n = 3.

The relation has two candidate key, {B}, {C}, whose length is 2. Therefore, k = 2.

Using the diagram below, we can calculate all the super keys for Example 15 based on the given information.

The following section presents a step by step explanation of Example 15.

Step 01: Formula Explanation

The calculation process is divided into two parts.

In the above diagram

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻²

Step 02: Constructing Super Keys

Starting with {B}, all valid super keys must contain B. This result in : {B}, {A,B}, {B,C}, {A,B,C}

Repeating the process for {C} gives : {C}, {A,C}, {B,C}, {A,B,C}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

Given K single candidate keys, pair candidate keys are obtained by choosing two distinct candidate keys at a time. Each selected pair is combined into a single set using the union operation. As shown below

{B} ∪ {C} = {B,C}

Formula:

C(K , 1) = {K(K-1)} / {2!}

In Example 15, there are 2 single candidate keys, therefore K = 2.

C(2 , 1) = {2(2-1)} / {2} = 1

Thus, only one pair candidate key can be formed, which is {B,C}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {B,C}, all valid super keys must contain B,C. This result in : {B,C}, {A,B,C}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 16:

When the following data is given

A relation R(A, B, C, D) consists of four attributes, so n = 4.
The relation has two candidate key, {A}, {B}, whose length is 2. Therefore, k = 2.

Using the diagram below, we can calculate all the super keys for Example 16 based on the given information.

The following section presents a step by step explanation of Example 16.

Step 01: Formula Explanation

The calculation process is divided into two parts.

In the above diagram

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻²

Step 02: Constructing Super Keys

Starting with {A}, all valid super keys must contain A. This result in : {A}, {A,B}, {A,C}, {A,D}, {A,B,C}, {A,B,D}, {A,C,D}, {A,B,C,D}

Repeating the process for {B} gives : {B}, {A,B}, {B,C}, {B,D}, {A,B,C}, {A,B,D}, {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

{A} ∪ {B} = {A,B}

Formula:

C(K , 1) = {K( K-1)} / {2!}

In Example 16, there are 2 single candidate keys, therefore K = 2.

C(2 , 1) = {2(2-1)} / {2} = 1

Thus, only one pair candidate key can be formed, which is {A,B}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B}, all valid super keys must contain A,B. This result in : {A,B}, {A,B,C}, {A,B,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 17:

When the following data is given

A relation R(A, B, C, D) consists of four attributes, so n = 4.

The relation has two candidate key, {C}, {D}, whose length is 2. Therefore, k = 2.

Using the diagram below, we can calculate all the super keys for Example 17 based on the given information.

The following section presents a step by step explanation of Example 17.

Step 01: Formula Explanation

The calculation process is divided into two parts.

In the above diagram

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻²

Step 02: Constructing Super Keys

Starting with {C}, all valid super keys must contain C. This result in : {C}, {A,C}, {B,C}, {C,D}, {A,B,C}, {A,C,D}, {B,C,D}, {A,B,C,D}

Repeating the process for {D} gives : {D}, {A,D}, {B,D}, {C,D}, {A,B,D}, {A,C,D},{B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

{C} ∪ {B} = {C,D}

Formula:

C(K , 1) = {K(K-1)} / {2!}

In Example 17, there are 2 single candidate keys, therefore K = 2.

C(2 , 1) = {2(2-1)} / {2} = 1

Thus, only one pair candidate key can be formed, which is {C,D}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {C,D}, all valid super keys must contain C,D. This result in : {C,D}, {A,B,D}, {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 18:

When the following data is given

A relation R(A, B, C, D) consists of four attributes, so n = 4.

The relation has three candidate key, {A}, {B}, {C}, whose length is 3. Therefore, k = 3.

Using the diagram below, we can calculate all the super keys for Example 18 based on the given information.

The following section presents a step by step explanation of Example 18.

Step 01: Formula Explanation

The calculation process is divided into three parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻²

Part 3: Add back the super keys that are common all three candidate keys to correct the final count.

+ 2ⁿ⁻³

Step 02: Constructing Super Keys

Starting with {A}, all valid super keys must contain A. This result in : {A}, {A,B}, {A,C}, {A,D}, {A,B,C}, {A,B,D}, {A,C,D}, {A,B,C,D}

Repeating the process for {B} gives : {B}, {A,B}, {B,C}, {B,D}, {A,B,C}, {A,B,D}, {B,C,D}, {A,B,C,D}

Repeating the same process for {C} gives : {C}, {A,C}, {B,C}, {C,D}, {A,B,C}, {A,C,D}, {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

Given K single candidate keys, pair candidate keys are obtained by choosing two distinct candidate keys at a time. Each selected pair is combined into a three set using the union operation. As shown below

{A} ∪ {B} = {A,B}
{A} ∪ {C} = {A,C}
{B} ∪ {C} = {B,C}

Formula:

C(K , 3) = {K(K-1)} / {2!}

In Example 18, there are 3 single candidate keys, therefore K = 3.

C(3 , 3) = {3( 3-1)} / {2} = 3

Thus, only three pair candidate key can be formed, which is {A,B}, {A,C}, {B,C}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B}, all valid super keys must contain A,B. This result in : {A,B}, {A,B,C}, {A,B,D}, {A,B,C,D}

Starting with {A,C}, all valid super keys must contain A,C. This result in : {A,C}, {A,B,C}, {A,C,D}, {A,B,C,D}

Starting with {B,C}, all valid super keys must contain B,C. This result in : {B,C}, {A,B,C}, {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 05: Single Candidate Keys to Triple Candidate Keys

Given K single candidate keys, triple candidate keys are obtained by choosing three distinct candidate keys at a time. Each selected triple is combined into a only one set using the union operation. As shown below

{A} ∪ {B} ∪ {C} = {A,B,C}

Formula:

C(K , 1) = {K(K-1)( K-2)} / {3!}

In Example 18, there are 3 single candidate keys, therefore K = 3.

C(3 , 1) = {3(3-1)(3-2)} / {6} = 1

Thus, only one triple candidate key can be formed, which is {A,B,C}.

The diagram below illustrates the complete process of generating the triple candidate key.

Step 06: Constructing Super Keys ( Triple Candidate Keys to Super Keys )

Starting with {A,B,C}, all valid super keys must contain A,B,C. This result in : {A,B,C}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 19:

When the following data is given

A relation R(A, B, C, D) consists of four attributes, so n = 4.

The relation has four candidate key, {A}, {B}, {C}, {D}, whose length is 4. Therefore, k = 4.

Using the diagram below, we can calculate all the super keys for Example 19 based on the given information.

The following section presents a step by step explanation of Example 19.

Step 01: Formula Explanation

The calculation process is divided into four parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻²

Part 3: Add back the super keys that are common all three candidate keys to correct the final count.

+ 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³

Part 4: Subtract the super keys that are common to all four candidate keys to complete the inclusion-exclusion calculation.

– 2ⁿ⁻⁴

Step 02: Constructing Super Keys

Starting with {A}, all valid super keys must contain A. This result in : {A}, {A,B}, {A,C}, {A,D}, {A,B,C}, {A,B,D}, {A,C,D}, {A,B,C,D}

Repeating the process for {B} gives : {B}, {A,B}, {B,C}, {B,D}, {A,B,C}, {A,B,D}, {B,C,D}, {A,B,C,D}

Repeating the process for {C} : {C}, {A,C}, {B,C}, {C,D}, {A,B,C}, {A,C,D}, {B,C,D}, {A,B,C,D} gives :

Repeating the same process for {D} : {D}, {A,D}, {B,D}, {C,D}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D} gives :

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

Given K single candidate keys, pair candidate keys are obtained by choosing two distinct candidate keys at a time. Each selected pair is combined into a six set using the union operation. As shown below

{A} ∪ {B} = {A,B}
{A} ∪ {C} = {A,C}
{A} ∪ {D} = {A,D}
{B} ∪ {C} = {B,C}
{B} ∪ {D} = {B,D}
{C} ∪ {D} = {C,D}

Formula:

C(K , 6) = {K(K-1)} / {2!}

In Example 19, there are 4 single candidate keys, therefore K = 4.

C(4 , 6) = {4(4-1)} / {2} = 6

Thus, six pair candidate keys can be formed, which is {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B}, all valid super keys must contain A,B. This result in : {A,B}, {A,B,C}, {A,B,D}, {A,B,C,D}

Starting with {A,C}, all valid super keys must contain A,C. This result in : {A,C}, {A,B,C}, {A,C,D}, {A,B,C,D}

Starting with {A,D}, all valid super keys must contain A,D. This result in : {A,D}, {A,B,D}, {B,C,D}, {A,B,C,D}

Starting with {B,C}, all valid super keys must contain B,C. This result in : {B,C}, {A,B,C}, {B,C,D}, {A,B,C,D}

Starting with {B,D}, all valid super keys must contain B,D. This result in : {B,D}, {A,B,D}, {B,C,D}, {A,B,C,D}

Starting with {C,D}, all valid super keys must contain C,D. This result in : {C,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 05: Single Candidate Keys to Triple Candidate Keys

Given K single candidate keys, triple candidate keys are obtained by choosing three distinct candidate keys at a time. Each selected triple is combined into a four set using the union operation. As shown below

{A} ∪ {B} ∪ {C} = {A,B,C}
{A} ∪ {B} ∪ {D} = {A,B,D}
{A} ∪ {C} ∪ {D} = {A,C,D}
{B} ∪ {C} ∪ {D} = {B,C,D}

Formula:

C(4 , 4) = {K(K-1)(K-2)} / {3!}

In Example 19, there are 4 single candidate keys, therefore K = 4.

C(4 , 4) = {4(4-1){4-2}} / {6} = 4

Thus, four triple candidate key can be formed, which is {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}.

The diagram below illustrates the complete process of generating the triple candidate key.

Step 06: Constructing Super Keys ( Triple Candidate Keys to Super Keys )

Starting with {A,B,C}, all valid super keys must contain A,B,C. This result in : {A,B,C}, {A,B,C,D}

Starting with {A,B,D}, all valid super keys must contain A,B,D. This result in : {A,B,D}, {A,B,C,D}

Starting with {A,C,D}, all valid super keys must contain A,C,D. This result in : {A,C,D}, {A,B,C,D}

Starting with {B,C,D}, all valid super keys must contain B,C,D. This result in : {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 07: Single Candidate Keys to Quadruple Candidate Keys

Given K single candidate keys, quadruple candidate keys are obtained by choosing four distinct candidate keys at a time. Each selected quadruple is combined into a one set using the union operation. As shown below

{A} ∪ {B} ∪ {C} ∪ {D} = {A,B,C,D}

Formula:

C(K , 1) = {K(K-1)(K-2)(K-3)} / {4!}

In Example 19, there are 4 single candidate keys, therefore K = 4.

C(4 , 1) = {4(4-1)(4-2)(4-3)} / {24} = 1

Thus, one quadruple candidate key can be formed, which is {A,B,C,D}.

The diagram below illustrates the complete process of generating the quadruple candidate key.

Step 08: Constructing Super Keys ( Quadruple Candidate Keys to Super Keys )

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 20:

When the following data is given

A relation R(A, B, C, D, E) consists of five attributes, so n = 5.

The relation has four candidate key, {A}, {B}, {C}, {D}, whose length is 4. Therefore, k = 4.

Using the diagram below, we can calculate all the super keys for Example 20 based on the given information.

The following section presents a step by step explanation of Example 20.

Step 01: Formula Explanation

The calculation process is divided into four parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻²

Part 3: Add back the super keys that are common all three candidate keys to correct the final count.

+ 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³

Part 4: Subtract the super keys that are common to all four candidate keys to complete the inclusion-exclusion calculation.

– 2ⁿ⁻⁴

Step 02: Constructing Super Keys

Starting with {A}, all valid super keys must contain A. This result in : {A}, {A,B}, {A,C}, {A,D}, {A,E}, {A,B,C}, {A,B,D}, {A,B,E}, {A,C,E}, {A,C,D}, {A,D,E}, {A,B,C,D}, {A,B,C,E}, {A,B,D,E}, {B,C,D,E}, {A,B,C,D,E}

Repeating the process for {B} gives : {B}, {A,B}, {B,C}, {B,D}, {B,E}, {A,B,C}, {A,B,D}, {A,B,E}, {A,C,E}, {A,C,D}, {A,D,E}, {A,B,C,D},{A,B,C,E}, {A,B,D,E}, {B,C,D,E}, {A,B,C,D,E}

Repeating the process for {C} gives : {C}, {A,C}, {B,C}, {C,D}, {C,E}, {A,B,C}, {A,C,D}, {A,C,E}, {B,C,D}, {B,C,E}, {C,D,E}, {A,B,C,D},{A,B,D,E}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Repeating the same process for {D} gives : {D}, {A,D}, {B,D}, {C,D}, {D,E}, {A,B,D}, {A,C,D}, {A,D,E}, {B,C,D}, {B,D,E}, {C,D,E}, {A,B,C,D},{A,B,D,E}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

{A} ∪ {B} = {A,B}
{A} ∪ {C} = {A,C}
{A} ∪ {D} = {A,D}
{B} ∪ {C} = {B,C}
{B} ∪ {D} = {B,D}
{C} ∪ {D} = {C,D}

Formula:

C(K , 6) = {K(K-1)} / {2!}

In Example 20, there are 4 single candidate keys, therefore K = 4.

C(4 , 6) = {4(4-1)} / {2} = 6

Thus, six pair candidate keys can be formed, which is {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B}, all valid super keys must contain A,B. This result in : {A,B}, {A,B,C}, {A,B,D}, {A,B,E}, {A,B,C,D}, {A,B,C,E}, {A,B,D,E}, {A,B,C,D,E}

Starting with {A,C}, all valid super keys must contain A,C. This result in : {A,C}, {A,B,C}, {A,C,D}, {A,C,E}, {A,B,C,D}, {A,B,C,E}, {A,C,D,E}, {A,B,C,D,E}

Starting with {A,D}, all valid super keys must contain A,D. This result in : {A,D}, {A,B,D}, {A,C,D}, {A,D,E} ,{A,B,C,D}, {A,B,D,E}, {A,C,D,E}, {A,B,C,D,E}

Starting with {B,C}, all valid super keys must contain B,C. This result in : {B,C}, {A,B,C}, {B,C,D}, {B,C,E}, {A,B,C,D}, {A,B,C,E}, {B,C,D,E}, {A,B,C,D,E}

Starting with {B,D}, all valid super keys must contain B,D. This result in : {B,D}, {A,B,D}, {B,C,D}, {B,D,E}, {A,B,C,D}, {A,B,D,E}, {B,C,D,E}, {A,B,C,D,E}

Starting with {C,D}, all valid super keys must contain C,D. This result in : {C,D}, {A,C,D}, {B,C,D}, {B,D,E}, {A,B,C,D}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 05: Single Candidate Keys to Triple Candidate Keys

{A} ∪ {B} ∪ {C} = {A,B,C}
{A} ∪ {B} ∪ {D} = {A,B,D}
{A} ∪ {C} ∪ {D} = {A,C,D}
{B} ∪ {C} ∪ {D} = {B,C,D}

Formula:

C(4 , 4) = {K(K-1)(K-2)} / {3!}

In Example 29, there are 4 single candidate keys, therefore K = 4.

C(4 , 4) = {4(4-1){4-2}} / {6} = 4

Thus, four triple candidate key can be formed, which is {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}.

The diagram below illustrates the complete process of generating the triple candidate key.

Step 06: Constructing Super Keys ( Triple Candidate Keys to Super Keys )

Starting with {A,B,C}, all valid super keys must contain A,B,C. This result in : {A,B,C}, {A,B,C,D}

Starting with {A,B,D}, all valid super keys must contain A,B,D. This result in : {A,B,D}, {A,B,C,D}

Starting with {A,C,D}, all valid super keys must contain A,C,D. This result in : {A,C,D}, {A,B,C,D}

Starting with {B,C,D}, all valid super keys must contain B,C,D. This result in : {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 07: Single Candidate Keys to Triple Candidate Keys

{A} ∪ {B} ∪ {C} ∪ {D} = {A,B,C,D}

Formula:

C(K , 1) = {K(K-1)(K-2)(K-3)} / {4!}

In Example 20, there are 4 single candidate keys, therefore K = 4.

C(4 , 1) = {4(4-1)(4-2)(4-3)} / {24} = 1

Thus, one quadruple candidate key can be formed, which is {A,B,C,D}.

The diagram below illustrates the complete process of generating the quadruple candidate key.

Step 08: Constructing Super Keys ( Quadruple Candidate Keys to Super Keys )

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,B,C,D}, {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 21:

When the following data is given

A relation R(A, B, C, D, E) consists of five attributes, so n = 5.

The relation has five candidate key, {A}, {B}, {C}, {D}, {E}, whose length is 5. Therefore, k = 5.

Using the diagram below, we can calculate all the super keys for Example 21 based on the given information.

The following section presents a step by step explanation of Example 21.

Step 01: Formula Explanation

The calculation process is divided into five parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻² − 2ⁿ⁻²

Part 3: Add back the super keys that are common all three candidate keys to correct the final count.

+ 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³ + 2ⁿ⁻³

Part 4: Subtract the super keys that are common to all four candidate keys to complete the inclusion-exclusion calculation.

– 2ⁿ⁻⁴ – 2ⁿ⁻⁴ – 2ⁿ⁻⁴ – 2ⁿ⁻⁴

Part 5: Add back the super keys that are shared by all five candidate keys, since they were subtracted one extra time in the previous step.

2ⁿ⁻⁵

Step 02: Constructing Super Keys

Repeating the process for {B} gives : {B}, {A,B}, {B,C}, {B,D}, {B,E}, {A,B,C}, {A,B,D}, {A,B,E}, {A,C,E}, {A,C,D}, {A,D,E}, {A,B,C,D},{A,B,C,E}, {A,B,D,E}, {B,C,D,E}, {A,B,C,D,E}

Repeating the process for {C} gives : {C}, {A,C}, {B,C}, {C,D}, {C,E}, {A,B,C}, {A,C,D}, {A,C,E}, {B,C,D}, {B,C,E}, {C,D,E}, {A,B,C,D},{A,B,D,E}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Repeating the process for {D} gives : {D}, {A,D}, {B,D}, {C,D}, {D,E}, {A,B,D}, {A,C,D}, {A,D,E}, {B,C,D}, {B,D,E}, {C,D,E}, {A,B,C,D},{A,B,D,E}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Repeating the same process for {E} gives : {E}, {A,E}, {B,E}, {C,E}, {D,E}, {A,B,E}, {A,C,E}, {A,D,E}, {B,C,D}, {B,D,E}, {C,D,E}, {A,B,C,E}, {A,B,D,E}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

Given K single candidate keys, pair candidate keys are obtained by choosing two distinct candidate keys at a time. Each selected pair is combined into a ten set using the union operation. As shown below

{A} ∪ {B} = {A,B}
{A} ∪ {C} = {A,C}
{A} ∪ {C} = {A,C}
{A} ∪ {E} = {A,E}
{B} ∪ {C} = {B,C}
{B} ∪ {D} = {B,D}
{B} ∪ {E} = {B,E}
{C} ∪ {D} = {C,D}
{C} ∪ {E} = {C,E}
{D} ∪ {E} = {D,E}

Formula:

C(K , 6) = {K(K-1)} / {2!}

In Example 21, there are 5 single candidate keys, therefore K = 5.

C(4 , 6) = {4(4-1)} / {2} = 6

Thus, six pair candidate keys can be formed, which is {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B}, all valid super keys must contain A,B. This result in : {A,B}, {A,B,C}, {A,B,D}, {A,B,E}, {A,B,C,D}, {A,B,C,E}, {A,B,D,E}, {A,B,C,D,E}

Starting with {A,C}, all valid super keys must contain A,C. This result in : {A,C}, {A,B,C}, {A,C,D}, {A,C,E}, {A,B,C,D}, {A,B,C,E}, {A,C,D,E}, {A,B,C,D,E}

Starting with {A,D}, all valid super keys must contain A,D. This result in : {A,D}, {A,B,D}, {A,C,D}, {A,D,E}, {A,B,C,D}, {A,B,D,E}, {A,C,D,E}, {A,B,C,D,E}

Starting with {A,E}, all valid super keys must contain A,E. This result in : {A,E}, {A,B,E}, {A,C,E}, {A,D,E}, {A,B,C,E}, {A,B,D,E}, {A,C,D,E}, {A,B,C,D,E}

Starting with {B,C}, all valid super keys must contain B,C. This result in : {B,C}, {A,B,C}, {B,C,D}, {B,C,E}, {A,B,C,D}, {A,B,C,E}, {B,C,D,E}, {A,B,C,D,E}

Starting with {B,D}, all valid super keys must contain B,D. This result in : {B,D}, {A,B,D}, {B,C,D}, {B,D,E}, {A,B,C,D}, {A,B,D,E}, {B,C,D,E}, {A,B,C,D,E}

Starting with {B,E}, all valid super keys must contain B,E. This result in : {B,E}, {A,B,E}, {B,C,E}, {B,D,E}, {A,B,C,D}, {A,B,D,E}, {B,C,D,E}, {A,B,C,D,E}

Starting with {C,D}, all valid super keys must contain C,D. This result in : {C,D}, {A,C,D}, {B,C,D}, {B,D,E}, {A,B,C,D}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Starting with {C,E}, all valid super keys must contain C,E. This result in : {C,E}, {A,C,E}, {B,C,E}, {C,D,E}, {A,B,C,E}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Starting with {D,E}, all valid super keys must contain D,E. This result in : {D,E}, {A,D,E}, {B,D,E}, {C,D,E}, {A,B,D,E}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 05: Single Candidate Keys to Triple Candidate Keys

Given K single candidate keys, triple candidate keys are obtained by choosing three distinct candidate keys at a time. Each selected triple is combined into a ten set using the union operation. As shown below

{A} ∪ {B} ∪ {C} = {A,B,C}
{A} ∪ {B} ∪ {D} = {A,B,D}
{A} ∪ {B} ∪ {E} = {A,B,E}
{A} ∪ {C} ∪ {D} = {A,C,D}
{A} ∪ {C} ∪ {E} = {A,C,E}
{A} ∪ {D} ∪ {E} = {A,D,E}
{B} ∪ {C} ∪ {D} = {B,C,D}
{B} ∪ {C} ∪ {E} = {B,C,E}
{B} ∪ {D} ∪ {E} = {B,D,E}
{C} ∪ {D} ∪ {E} = {C,D,E}

Formula:

C(5 , 10) = {K(K-1)(K-2)} / {3!}

In Example 21, there are 5 single candidate keys, therefore K = 5.

C(5 , 10) = {5(5-1){5-2}} / {6} = 10

Thus, ten triple candidate key can be formed, which is {A,B,C}, {A,B,D}, {A,B,E}, {A,C,D}, {A,C,E}, {A,D,E}, {B,C,D}, {B,C,E}, {B,D,E}, {C,D,E}.

The diagram below illustrates the complete process of generating the triple candidate key.

Step 06: Constructing Super Keys ( Triple Candidate Keys to Super Keys )

Starting with {A,B,C}, all valid super keys must contain A,B,C. This result in : {A,B,C}, {A,B,C,D}, {A,B,C,E}, {A,B,C,D,E}

Starting with {A,B,D}, all valid super keys must contain A,B,D. This result in : {A,B,D}, {A,B,C,D}, {A,B,D,E}, {A,B,C,D,E}

Starting with {A,B,E}, all valid super keys must contain A,B,E. This result in : {A,B,E}, {A,B,C,E}, {A,B,D,E}, {A,B,C,D,E}

Starting with {A,C,D}, all valid super keys must contain A,C,D. This result in : {A,C,D}, {A,B,C,D}, {A,C,D,E}, {A,B,C,D,E}

Starting with {A,C,E}, all valid super keys must contain A,C,E. This result in : {A,C,E}, {A,B,C,E}, {A,C,D,E}, {A,B,C,D,E}

Starting with {A,D,E}, all valid super keys must contain A,D,E. This result in : {A,D,E}, {A,B,D,E}, {A,C,D,E}, [A,B,C,D,E}

Starting with {B,C,D}, all valid super keys must contain B,C,D. This result in : {B,C,D}, {A,B,C,D}, {B,C,D,E}, {A,B,C,D,E}

Starting with {B,C,E}, all valid super keys must contain B,C,E. This result in : {B,C,E}, {A,B,C,E}, {B,C,D,E}, {A,B,C,D,E}

Starting with {B,D,E}, all valid super keys must contain B,D,E. This result in : {B,D,E}, {A,B,D,E}, {B,C,D,E}, {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 07: Single Candidate Keys to Quadruple Candidate Keys

Given K single candidate keys, quadruple candidate keys are obtained by choosing five distinct candidate keys at a time. Each selected quadruple is combined into a five set using the union operation. As shown below

{A} ∪ {B} ∪ {C} ∪ {D} = {A,B,C,D}
{A} ∪ {B} ∪ {C} ∪ {E} = {A,B,C,E}
{A} ∪ {B} ∪ {D} ∪ {E} = {A,B,D,E}
{A} ∪ {C} ∪ {D} ∪ {E} = {A,C,D,E}
{B} ∪ {C} ∪ {D} ∪ {E} = {B,C,D,E}

Formula:

C(K , 5) = {K(K-1)(K-2)(K-3)} / {4!}

In Example 21, there are 5 single candidate keys, therefore K = 5.

C(5 , 5) = {5(5-1)(5-2)(5-3)} / {24} = 5

Thus, five quadruple candidate key can be formed, which is {A,B,C,D,E}.

The diagram below illustrates the complete process of generating the quadruple candidate key.

Step 08: Constructing Super Keys ( Quadruple Candidate Keys to Super Keys )

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,B,C,D}, {A,B,C,D,E}

Starting with {A,B,C,E}, all valid super keys must contain A,B,C,E. This result in : {A,B,C,E}, {A,B,C,D,E}

Starting with {A,B,D,E}, all valid super keys must contain A,B,D,E. This result in : {A,B,D,E}, {A,B,C,D,E}

Starting with {A,C,D,E}, all valid super keys must contain A,C,D,E. This result in : {A,C,D,E}, {A,B,C,D,E}

Starting with {B,C,D,E}, all valid super keys must contain B,C,D,E. This result in : {B,C,D,E}, {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 09: Single Candidate Keys to Quintuple Candidate Keys

Given K single candidate keys, quintuple candidate keys are obtained by choosing five distinct candidate keys at a time. Each selected quintuple is combined into a one set using the union operation. As shown below

{A} ∪ {B} ∪ {C} ∪ {D} ∪ {E} = {A,B,C,D,E}

Formula:

C(K , 1) = {K(K-1)(K-2)(K-3)(K-4)} / {5!}

In Example 21, there are 5 single candidate keys, therefore K = 5.

C(5 , 1) = {5(5-1)(5-2)(5-3)(5-4)} / {120} = 1

Thus, one quintuple candidate key can be formed, which is {A,B,C,D,E}.

The diagram below illustrates the complete process of generating the quintuple candidate key.

Step 10: Constructing Super Keys ( Quintuple Candidate Keys to Super Keys )

Starting with {A,B,C,D,E}, all valid super keys must contain A,B,C,D,E. This result in : {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 22:

When the following data is given

A relation R(A, B, C, D) consists of four attributes, so n = 4.

The relation has two candidate key, {A} and {B,C}, where the length of {A} is 1 and the length of {B,C} is 2.

Using the diagram below, we can calculate all the super keys for Example 22 based on the given information.

The following section presents a step by step explanation of Example 22.

Step 01: Formula Explanation

The calculation process is divided into two parts.

In the above diagram

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻²

Step 02: Constructing Super Keys

Starting with {A}, all valid super keys must contain A. This result in : {A}, {A,B}, {A,C}, {A,D},{A,B,C},{A,C,D},{B,C,D},{A,B,C,D}

Repeating the process for {B,C} gives : {B,C}, {B,C,E},{B,C,D},{A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

{A} ∪ {B,C} = {A,B,C}

Formula:

C(K , 1) = { K ( K-1 )} / {2!}

In Example 22, there are 2 single candidate keys, therefore K = 2.

C(2 , 1) = { 2 ( 2-1 )} / {2} = 1

Thus, only one pair candidate key can be formed, which is {A,B,C}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B,C}, all valid super keys must contain A,B,C. This result in : {A,B,C}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 23:

When the following data is given

A relation R(A, B, C, D) consists of four attributes, so n = 4.

The relation has three candidate key, {A}, {B} and {C,D}, where the length of {A},{B} is 1 and the length of {C,D} is 2.

Using the diagram below, we can calculate all the super keys for Example 23 based on the given information.

The following section presents a step by step explanation of Example 23.

Step 01: Formula Explanation

The calculation process is divided into three parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻²

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻² − 2ⁿ⁻³ − 2ⁿ⁻³

Part 3: Add back the super keys that are common all three candidate keys to correct the final count.

+ 2ⁿ⁻⁴

Step 02: Constructing Super Keys

Starting with {A}, all valid super keys must contain A. This result in : {A}, {A,B}, {A,C}, {A,D}, {A,B,C}, {A,C,D}, {B,C,D}, {A,B,C,D}

Repeating the process for {B} gives : {B}, {A,B}, {B,C}, {B,D}, {A,B,C}, {A,B,D}, {B,C,D}, {A,B,C,D}

Repeating the process for {C,D} gives : {C,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 03: Single Candidate Keys to Pair Candidate Keys

{A} ∪ {B} = {A,B}
{A} ∪ {C,D} = {A,C,D}
{B} ∪ {C,D} = {B,C,D}

Formula:

C(K , 3) = { K ( K-1 )} / {2!}

In Example 23, there are 3 single candidate keys, therefore K = 3.

C(3 , 3) = { 3 ( 3-1 )} / {2} = 3

Thus, only three pair candidate key can be formed, which is {A,B}, {A,C,D}, {B,C,D}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B}, all valid super keys must contain A,B. This result in : {A,B}, {A,B,C}, {A,B,D}, {A,B,C,D}

Starting with {A,C,D}, all valid super keys must contain A,C,D. This result in : {A,C,D}, {A,B,C,D}

Starting with {B,C,D}, all valid super keys must contain B,C,D. This result in : {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 05: Single Candidate Keys to Triple Candidate Keys

{A} ∪ {B} ∪ {C,D} = {A,B,C,D}

Formula:

C(3 , 1) = {K(K-1)(K-2)} / {3!}

In Example 23, there are 3 single candidate keys, therefore K = 3.

C(3 , 1) = {3(3-1){3-2}} / {6} = 1

Thus, one triple candidate key can be formed, which is {A,B,C,D}.

The diagram below illustrates the complete process of generating the triple candidate key.

Step 06: Constructing Super Keys ( Triple Candidate Keys to Super Keys )

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 24:

When the following data is given

A relation R(A, B, C, D) consists of four attributes, so n = 4.

The relation has three candidate key, {A}, {B,C} and {C,D}, where the length of {A}, is 1 and the length of {B,C} and {C,D} is 2.

Using the diagram below, we can calculate all the super keys for Example 24 based on the given information.

The following section presents a step by step explanation of Example 24.

Step 01: Formula Explanation

The calculation process is divided into three parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻¹ + 2ⁿ⁻² + 2ⁿ⁻²

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻³ − 2ⁿ⁻³ − 2ⁿ⁻³

Part 3: Add back the super keys that are common all three candidate keys to correct the final count.

+ 2ⁿ⁻⁴

Step 02: Constructing Super Keys

Starting with {A}, all valid super keys must contain A. This result in : {A}, {A,B}, {A,C}, {A,D}, {A,B,C}, {A,C,D}, {B,C,D}, {A,B,C,D}

Repeating the process for {B} gives : {B,C}, {A,B,C}, {B,C,D}, {A,B,C,D}

Repeating the process for {C,D} gives : {C,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

Step 03: Single Candidate Keys to Pair Candidate Keys

{A} ∪ {B,C} = {A,B,C}
{A} ∪ {C,D} = {A,C,D}
{B} ∪ {C,D} = {B,C,D}

Formula:

C(K , 3) = { K ( K-1 )} / {2!}

In Example 24, there are 3 single candidate keys, therefore K = 3.

C(3 , 3) = { 3 ( 3-1 )} / {2} = 3

Thus, only three pair candidate key can be formed, which is {A,B,C}, {A,C,D}, {B,C,D}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B,C}, all valid super keys must contain A,B,C. This result in : {A,B,C}, {A,B,C,D}

Starting with {A,C,D}, all valid super keys must contain A,C,D. This result in : {A,C,D}, {A,B,C,D}

Starting with {B,C,D}, all valid super keys must contain B,C,D. This result in : {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 05: Single Candidate Keys to Triple Candidate Keys

{A} ∪ {B,C} ∪ {C,D} = {A,B,C,D}

Formula:

C(3 , 1) = {K(K-1)(K-2)} / {3!}

In Example 24, there are 3 single candidate keys, therefore K = 3.

C(3 , 1) = {3(3-1){3-2}} / {6} = 1

Thus, one triple candidate key can be formed, which is {A,B,C,D}.

The diagram below illustrates the complete process of generating the triple candidate key.

Step 06: Constructing Super Keys ( Triple Candidate Keys to Super Keys )

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 25:

When the following data is given

A relation R(A, B, C, D) consists of four attributes, so n = 4.

The relation has three candidate key, {A,B}, {B,C} and {C,D}, where the length of {A,B}, {B,C} and {C,D} is 2.

Using the diagram below, we can calculate all the super keys for Example 25 based on the given information.

The following section presents a step by step explanation of Example 25.

Step 01: Formula Explanation

The calculation process is divided into three parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻² + 2ⁿ⁻² + 2ⁿ⁻²

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻³ − 2ⁿ⁻³ − 2ⁿ⁻³

Part 3: Add back the super keys that are common all three candidate keys to correct the final count.

+ 2ⁿ⁻⁴

Step 02: Constructing Super Keys

Starting with {A,B}, all valid super keys must contain A,B. This result in : {A,B}, {A,B,C}, {A,B,D}, {A,B,C,D}

Repeating the process for {B,C} gives : {B,C}, {A,B,C}, {B,C,D}, {A,B,C,D}

Repeating the process for {C,D} gives : {C,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

Step 03: Single Candidate Keys to Pair Candidate Keys

{A} ∪ {B,C} = {A,B,C}
{A,B} ∪ {C,D} = {A,B,C,D}
{B} ∪ {C,D} = {B,C,D}

Formula:

C(K , 3) = { K ( K-1 )} / {2!}

In Example 25, there are 3 single candidate keys, therefore K = 3.

C(3 , 3) = { 3 ( 3-1 )} / {2} = 3

Thus, only three pair candidate key can be formed, which is {A,B,C}, {A,B,C,D}, {B,C,D}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B,C}, all valid super keys must contain A,B,C. This result in : {A,B,C}, {A,B,C,D}

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,C,D,D}

Starting with {B,C,D}, all valid super keys must contain B,C,D. This result in : {B,C,D}, {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Step 05: Single Candidate Keys to Triple Candidate Keys

{A,B} ∪ {B,C} ∪ {C,D} = {A,B,C,D}

Formula:

C(3 , 1) = {K(K-1)(K-2)} / {3!}

In Example 25, there are 3 single candidate keys, therefore K = 3.

C(3 , 1) = {3(3-1){3-2}} / {6} = 1

Thus, one triple candidate key can be formed, which is {A,B,C,D}.

The diagram below illustrates the complete process of generating the triple candidate key.

Step 06: Constructing Super Keys ( Triple Candidate Keys to Super Keys )

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,B,C,D}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 26:

When the following data is given

A relation R(A, B, C, D, E) consists of five attributes, so n = 5.

The relation has two candidate key, {A,B,C} and {B,C,D}, where the length of {A,B,C}, and {B,C,D} is 3.

Using the diagram below, we can calculate all the super keys for Example 26 based on the given information.

The following section presents a step by step explanation of Example 26.

Step 01: Formula Explanation

The calculation process is divided into two parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻³ + 2ⁿ⁻³

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻⁴

Step 02: Constructing Super Keys

Starting with {A,B,C}, all valid super keys must contain A,B,C. This result in : {A,B,C}, {A,B,C,D}, {A,B,C,E}, {A,B,C,D,E}

Repeating the process for {B,C,D} gives : {B,C,D}, {A,B,C,D}, {B,C,D,E}, {A,B,C,D,E}

Step 03: Single Candidate Keys to Pair Candidate Keys

Given K single candidate keys, pair candidate keys are obtained by choosing two distinct candidate keys at a time. Each selected pair is combined into a only one set using the union operation. As shown below

{A,B,C} ∪ {B,C,D} = {A,B,C,D}

Formula:

C(K , 1) = { K ( K-1 )} / {2!}

In Example 26, there are 2 single candidate keys, therefore K = 2.

C(2 , 1) = { 2 ( 2-1 )} / {2} = 1

Thus, only one pair candidate key can be formed, which is {A,B,C,D}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B,C,B,C,D}, all valid super keys must contain A,B,C,B,C,D. This result in : {A,B,C,D}, {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 27:

When the following data is given

A relation R(A, B, C, D, E) consists of five attributes, so n = 5.

The relation has two candidate key, {A,B,C,D} and {E}, where the length of {A,B,C,D}, is 4 and {E} is 1.

Using the diagram below, we can calculate all the super keys for Example 27 based on the given information.

The following section presents a step by step explanation of Example 27.

Step 01: Formula Explanation

The calculation process is divided into two parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻⁴ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻⁵

Step 02: Constructing Super Keys

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,B,C,D}, {A,B,C,D,E}

Repeating the process for {E} gives : {E}, {A,E}, {B,E}, {C,E}, {D,E}, {A,B,E}, {A,C,E}, {A,D,E},{B,C,E},{B,D,E}, {C,D,E}, {A,B,C,E}, {A,B,D,E}, {A,C,D,E}, {B,C,D,E}, {A,B,C,D,E}

Step 03: Single Candidate Keys to Pair Candidate Keys

{A,B,C,D} ∪ {E} = {A,B,C,D,E}

Formula:

C(K , 1) = { K ( K-1 )} / {2!}

In Example 27, there are 2 single candidate keys, therefore K = 2.

C(2 , 1) = { 2 ( 2-1 )} / {2} = 1

Thus, only one pair candidate key can be formed, which is {A,B,C,D,E}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B,C,D,E}, all valid super keys must contain A,B,C,D,E. This result in : {A,B,C,D,E}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 28:

When the following data is given

A relation R(A, B, C, D, E, F) consists of six attributes, so n = 6.

The relation has two candidate key, {A,B,C,D,E} and {F}, where the length of {A,B,C,D,E}, is 5 and {F} is 1.

Using the diagram below, we can calculate all the super keys for Example 28 based on the given information.

The following section presents a step by step explanation of Example 28.

Step 01: Formula Explanation

The calculation process is divided into two parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻⁵ + 2ⁿ⁻¹

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻⁶

Step 02: Constructing Super Keys

Starting with {A,B,C,D,E}, all valid super keys must contain A,B,C,D,E. This result in : {A,B,C,D,E}, {A,B,C,D,E,F}

Repeating the process for {F} gives : {F},{A,F},{B,F},{C,F},{D,F},{E,F},{A,B,F},{A,C,F},{A,D,F},{A,E,F},{B,C,F},{B,D,F},{B,E,F},{C,D,F},{C,E,F},{D,E,F},{A,B,C,F},{A,B,D,F},{A,B,E,F},{A,C,D,F},{A,C,E,F},{A,D,E,F},{B,C,D,F},{B,C,E,F},{B,D,E,F},{C,D,E,F},{A,B,C,D,F},{A,C,D,E,F},{A,B,D,E,F},{A,C,D,E,F},{B,C,D,E,F},{A,B,C,D,E,F}

Step 03: Single Candidate Keys to Pair Candidate Keys

{A,B,C,D,E} ∪ {F} = {A,B,C,D,E,F}

Formula:

C(K , 1) = { K ( K-1 )} / {2!}

In Example 28, there are 2 single candidate keys, therefore K = 2.

C(2 , 1) = { 2 ( 2-1 )} / {2} = 1

Thus, only one pair candidate key can be formed, which is {A,B,C,D,E,F}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B,C,D,E,F}, all valid super keys must contain A,B,C,D,E,F. This result in : {A,B,C,D,E,F}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 29:

When the following data is given

A relation R(A, B, C, D, E, F) consists of six attributes, so n = 6.

The relation has two candidate key, {A,B,C,D} and {E,F}, where the length of {A,B,C,D}, is 4 and {E,F} is 2.

Using the diagram below, we can calculate all the super keys for Example 29 based on the given information.

The following section presents a step by step explanation of Example 29.

Step 01: Formula Explanation

The calculation process is divided into two parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻⁴ + 2ⁿ⁻²

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻⁶

Step 02: Constructing Super Keys

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,B,C,D},{A,B,C,D,E}, {A,B,C,D,F}, {A,B,C,D,E,F}

Repeating the process for {E,F} gives : {E,F},{A,E,F},{B,E,F},{C,E,F},{D,E,F},{A,B,E,F},{A,C,E,F},{A,D,E,F},{B,C,E,F},{B,D,E,F},{C,D,E,F},{A,B,C,E,F},{A,B,D,E,F},{A,C,D,E,F},{B,C,D,E,F},{A,B,C,D,E,F}

Step 03: Single Candidate Keys to Pair Candidate Keys

Given K single candidate keys, pair candidate keys are obtained by choosing two distinct candidate keys at a time. Each selected pair is combined into a only single set using the union operation. As shown below

{A,B,C,D} ∪ {E,F} = {A,B,C,D,E,F}

Formula:

C(K , 2) = { K ( K-1 )} / {2!}

In Example 29, there are 2 single candidate keys, therefore K = 2.

C(2 , 2) = { 2 ( 2-1 )} / {2} = 1

Thus, only one pair candidate key can be formed, which is {A,B,C,D,E,F}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B,C,D,E,F}, all valid super keys must contain A,B,C,D,E,F. This result in : {A,B,C,D,E,F}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.

Finding Super Key in DBMS Example 30:

When the following data is given

A relation R(A, B, C, D, E, F, G) consists of seven attributes, so n = 7.

The relation has two candidate key, {A,B,C,D} and {E,F,G}, where the length of {A,B,C,D}, is 4 and {E,F,G} is 3.

Using the diagram below, we can calculate all the super keys for Example 30 based on the given information.

The following section presents a step by step explanation of Example 30.

Step 01: Formula Explanation

The calculation process is divided into two parts.

Part 1: Determine the number of super keys generated from each candidate key separately.

+ 2ⁿ⁻⁴ + 2ⁿ⁻³

Part 2: Deduct the duplicated super keys that are common to both candidate keys.

− 2ⁿ⁻⁷

Step 02: Constructing Super Keys

Starting with {A,B,C,D}, all valid super keys must contain A,B,C,D. This result in : {A,B,C,D},{A,B,C,D,E},{A,B,C,D,F},{A,B,C,D,G},{A,B,C,D,E,F},{A,B,C,D,E,G},{A,B,C,D,F,G},{A,B,C,D,E,F,G}

Repeating the process for {E,F,G} gives : {E,F,G},{A,E,F,G},{B,E,F,G},{C,E,F,G},{D,E,F,G},{A,B,E,F,G},{A,C,E,F,G},{A,D,E,F,G},{B,C,E,F,G},{B,D,E,F,G},{C,D,E,F,G},{A,B,C,E,F,G},{A,B,D,E,F,G},{A,C,D,E,F,G},{B,C,D,E,F,G},{A,B,C,D,E,F,G}

Step 03: Single Candidate Keys to Pair Candidate Keys

{A,B,C,D} ∪ {E,F,G} = {A,B,C,D,E,F,G}

Formula:

C(K , 2) = { K ( K-1 )} / {2!}

In Example 30, there are 2 single candidate keys, therefore K = 2.

C(2 , 2) = { 2 ( 2-1 )} / {2} = 1

Thus, only one pair candidate key can be formed, which is {A,B,C,D,E,F,G}.

The diagram below illustrates the complete process of generating the pair candidate key.

Step 04: Constructing Super Keys ( Pair Candidate Keys to Super Keys )

Starting with {A,B,C,D,E,F,G}, all valid super keys must contain A,B,C,D,E,F,G. This result in : {A,B,C,D,E,F,G}

Note: The overlapping super keys are handled using the inclusion-exclusion principle in the next step.