Canonical cover in DBMS Theory - Mini Project: Build & Apply

Canonical Cover for Functional Dependencies

📖 Scenario: You are working with a database design team. They have a set of functional dependencies (FDs) for a relation, and they want to simplify these FDs to a minimal form called the canonical cover. This helps in designing efficient database schemas.

🎯 Goal: Build a step-by-step process to find the canonical cover of a given set of functional dependencies by simplifying and minimizing them.

📋 What You'll Learn

Create a dictionary called fds with given functional dependencies as keys and values

Create a list called attributes containing all attributes involved

Implement a function called remove_extraneous to remove extraneous attributes from the left side of FDs

Implement the final step to combine and minimize the FDs into a canonical cover stored in canonical_cover

💡 Why This Matters

🌍 Real World

Database designers use canonical covers to simplify functional dependencies, which helps in normalizing database schemas and avoiding redundancy.

💼 Career

Understanding canonical covers is essential for roles like database administrator, data engineer, and software developer working with relational databases.

1

Set up the initial functional dependencies

Create a dictionary called fds with these exact functional dependencies: {'AB': 'C', 'A': 'B', 'B': 'C'}.

DBMS Theory

# Create the dictionary fds with the given functional dependencies
# Your code here

Need a hint?

Use a Python dictionary with strings as keys and values representing the functional dependencies.

2

List all attributes involved

Create a list called attributes containing the unique attributes 'A', 'B', and 'C'.

DBMS Theory

fds = {'AB': 'C', 'A': 'B', 'B': 'C'}
# Create the list attributes with 'A', 'B', and 'C'
# Your code here

Need a hint?

List all attributes as strings inside a Python list.

3

Define a function to remove extraneous attributes

Define a function called remove_extraneous that takes a left side string and returns a simplified string by removing extraneous attributes. Use the fds dictionary inside the function.

DBMS Theory

fds = {'AB': 'C', 'A': 'B', 'B': 'C'}
attributes = ['A', 'B', 'C']
# Define the function remove_extraneous(left) below
# Your code here

Need a hint?

Check each attribute in the left side. Remove it temporarily and check if the right side is still implied by the closure. If yes, remove it permanently.

4

Create the canonical cover by minimizing FDs

Create a dictionary called canonical_cover by applying remove_extraneous to each left side in fds and combining FDs with the same left side.

DBMS Theory

fds = {'AB': 'C', 'A': 'B', 'B': 'C'}
attributes = ['A', 'B', 'C']

def remove_extraneous(left):
    for attr in left:
        temp = left.replace(attr, '')
        closure = set(temp)
        changed = true
        while changed:
            changed = false
            for l, r in fds.items():
                if set(l).issubset(closure) and r not in closure:
                    closure.add(r)
                    changed = true
        if all(c in closure for c in fds[left]):
            left = temp
    return left

# Create canonical_cover dictionary by minimizing fds
# Your code here

Need a hint?

For each FD, simplify the left side and merge right sides if left sides match.