Candidate key finding using closure in DBMS Theory - Mini Project: Build & Apply

Candidate Key Finding Using Closure

📖 Scenario: You are working with a database table and want to find which sets of columns can uniquely identify every row. These sets are called candidate keys. To find them, you use the concept of closure of attributes under given functional dependencies.Imagine you have a table of students with columns like StudentID, Name, Course, and Instructor. You want to find which columns or combinations of columns can serve as candidate keys.

🎯 Goal: Build a step-by-step process to find candidate keys by computing the closure of attribute sets under given functional dependencies.You will create the data for attributes and dependencies, set up a target attribute set, compute closure, and finally identify candidate keys.

📋 What You'll Learn

Create a dictionary of functional dependencies with exact keys and values

Create a list of all attributes in the relation

Write code to compute closure of a given attribute set

Identify candidate keys based on closure covering all attributes

💡 Why This Matters

🌍 Real World

Finding candidate keys helps database designers ensure each row in a table can be uniquely identified, which is essential for data integrity.

💼 Career

Database administrators and developers use candidate key analysis to design efficient and normalized database schemas.

1

Setup Functional Dependencies and Attributes

Create a dictionary called fd with these exact functional dependencies: 'A': ['B', 'C'], 'B': ['D'], 'C': ['E']. Also create a list called attributes containing 'A', 'B', 'C', 'D', and 'E'.

DBMS Theory

# Create the dictionary fd and list attributes
# Your code here

Hint

Use a dictionary for functional dependencies where keys are single attributes and values are lists of attributes they determine.

Attributes list should include all attributes mentioned.

2

Set Initial Attribute Set for Closure

Create a list called initial_set containing only the attribute 'A'. This will be the starting point to find closure.

DBMS Theory

fd = {'A': ['B', 'C'], 'B': ['D'], 'C': ['E']}
attributes = ['A', 'B', 'C', 'D', 'E']
# Create initial_set with 'A'
# Your code here

Hint

Just create a list with one element 'A'.

3

Compute Closure of Initial Attribute Set

Write code to compute the closure of initial_set under the functional dependencies fd. Create a set called closure initialized with initial_set. Then repeatedly add attributes to closure if they are functionally determined by any attribute in closure. Use a loop until no new attributes can be added.

DBMS Theory

fd = {'A': ['B', 'C'], 'B': ['D'], 'C': ['E']}
attributes = ['A', 'B', 'C', 'D', 'E']
initial_set = ['A']
# Compute closure of initial_set
# Your code here

Hint

Use a set to hold closure for easy membership checks.

Loop until no new attributes are added.

4

Identify Candidate Key Based on Closure

Check if the closure contains all attributes in attributes. Create a boolean variable called is_candidate_key that is true if closure covers all attributes, otherwise false.

DBMS Theory

fd = {'A': ['B', 'C'], 'B': ['D'], 'C': ['E']}
attributes = ['A', 'B', 'C', 'D', 'E']
initial_set = ['A']
closure = set(initial_set)
changed = True
while changed:
    changed = False
    for attr in list(closure):
        if attr in fd:
            for dep in fd[attr]:
                if dep not in closure:
                    closure.add(dep)
                    changed = True
# Check if closure covers all attributes
# Your code here

Hint

Use the set method issuperset() to check if closure contains all attributes.

Practice

1. What does the closure of a set of attributes represent in candidate key finding?

easy

A. All attributes functionally determined by the set

B. The number of attributes in the set

C. The total number of functional dependencies

D. The primary key of the table

Solution

1. Step 1: Understand closure definition

   The closure of a set of attributes includes all attributes that can be functionally determined from that set using the given functional dependencies.

2. Step 2: Relate closure to candidate keys

   If the closure covers all attributes in the relation, the set is a superkey; minimal such sets are candidate keys.

3. Final Answer:

   All attributes functionally determined by the set -> Option A

4. Quick Check:

   Closure = attributes reachable from set [OK]

Hint: Closure shows all attributes a set can determine [OK]

Common Mistakes:

• Confusing closure with number of attributes
• Thinking closure is the primary key itself
• Ignoring functional dependencies in closure

2. Which of the following is the correct notation to represent the closure of attribute set {A, B}?

easy

A. {A, B}+

B. {A, B}*

C. closure(A, B)

D. closure{A, B}

Solution

1. Step 1: Recall standard closure notation

   The closure of a set of attributes X is denoted as X⁺, meaning all attributes functionally determined by X.

2. Step 2: Match notation to options

   {A, B}+ uses the correct notation {A, B}+. Other options are not standard or incorrect.

3. Final Answer:

   {A, B}+ -> Option A

4. Quick Check:

   Closure notation uses plus sign [OK]

Hint: Closure notation always uses plus sign after attribute set [OK]

Common Mistakes:

• Using star (*) instead of plus (+)
• Writing closure as a function call
• Misplacing braces or parentheses

3. Given relation R(A, B, C, D) and functional dependencies:
A -> B, B -> C, C -> D. What is the closure of {A}?

medium

A. {A, B}

B. {A, B, C}

C. {A, B, C, D}

D. {A}

Solution

1. Step 1: Start with attribute set {A}

   Initially, closure({A}) = {A}.

2. Step 2: Apply functional dependencies stepwise

   From A -> B, add B: closure = {A, B}. Then B -> C adds C: closure = {A, B, C}. Finally, C -> D adds D: closure = {A, B, C, D}.

3. Final Answer:

   {A, B, C, D} -> Option C

4. Quick Check:

   Closure includes all reachable attributes [OK]

Hint: Apply dependencies repeatedly until no new attributes added [OK]

Common Mistakes:

• Stopping after first dependency
• Ignoring transitive dependencies
• Confusing closure with original set

4. Identify the error in this closure calculation for relation R(A, B, C) with FDs:
A -> B, B -> C. Closure of {B} is given as {B, A}. What is wrong?

medium

A. Closure should include all attributes

B. Closure cannot include B itself

C. Closure should be empty

D. Closure should include C, not A

Solution

1. Step 1: Analyze given closure {B, A}

   Starting with {B}, applying B -> C adds C, so closure should be {B, C}.

2. Step 2: Check if A can be added

   There is no FD that allows B to determine A, so A should not be in closure.

3. Final Answer:

   Closure should include C, not A -> Option D

4. Quick Check:

   Closure only adds attributes functionally determined [OK]

Hint: Only add attributes on right side of FDs from closure set [OK]

Common Mistakes:

• Adding attributes not functionally dependent
• Confusing direction of dependencies
• Assuming closure includes all attributes

5. For relation R(A, B, C, D, E) with FDs:
A -> BC, CD -> E, B -> D. Which of the following is a candidate key?

hard

A. {A, D}

B. {A}

C. {A, C}

D. {B, C}

Solution

1. Step 1: Compute closure of {A}

   Start with {A}. From A -> BC, add B and C: closure = {A, B, C}. From B -> D, add D: closure = {A, B, C, D}. From CD -> E, since C and D are in closure, add E: closure = {A, B, C, D, E}.

2. Step 2: Check minimality of {A}

   Since closure({A}) includes all attributes, {A} is a superkey. It is minimal because it has only one attribute.

3. Final Answer:

   {A} -> Option B

4. Quick Check:

   Minimal set with full closure is candidate key [OK]

Hint: Check closure of smallest sets covering all attributes [OK]

Common Mistakes:

• Not checking transitive dependencies
• Assuming larger sets are always candidate keys
• Ignoring minimality condition