Category: 05. Relational Database Design

In database management and normalization, it’s important that one understands the concepts of functional dependency, closure property, and candidate keys. These concepts help us design efficient relational schemas, ensure data integrity, and optimize queries. In this chapter, we will elaborate these concepts with the help of practical examples and also understand the process of finding closures and identifying candidate keys.

What is Functional Dependency?

For a basic recap on functional dependency, it describes a relationship between attributes in a relational schema. If X → Y, it means the value of X uniquely determines the value of Y. Now here, X is the determinant, and Y is the dependent.

Let us see one example for this. In a table where each employee has a unique ID, the dependency ID → Name this signifies that knowing an employee’s ID is enough to find their name.

Functional dependencies can be defined formally. Consider two tuples, T1 and T2, in a relational schema. If T1.X = T2.X this implies T1.Y = T2.Y. Then X → Y is a valid functional dependency.

But this relationship is not necessarily reciprocal. So the attribute Y may not determine X.

Example of Functional Dependency

Let us consider a relational schema R (A, B, C) with the following data −

A	B	C
1	1	4
1	1	3
4	2	6
6	5	7

Let’s understand the dependencies −

• A → C − This does not hold. This is because A = 1 maps to both C = 4 and C = 3.
• A → B − This is valid since each unique value of A maps to a unique value of B.
• B → A − This is also valid for the given dataset.

Thus, we derive the following functional dependencies −

• A → B
• B → A

What is Attribute Closure?

The closure of an attribute set, X, which is denoted as X+. This is the set of all attributes that can be determined by X using the given functional dependencies. The closures properties help us to identify keys and candidate keys for a relational schema.

Following are the Steps to Find Closure −

• We can start with X+ = X (the attribute set itself).
• Iteratively add attributes that can be determined from the functional dependencies.
• Stop when no more attributes can be added to X+.

Example of Closure

Using the functional dependencies, say, A → B, B → D, and CD → E −

Finding A+	Finding B+
Start with A+ = {A}A → B: Add B to A+B → D: Add D to A+CD → E: A+ contains C and D, so add E	Start with B+ = {B}B → D: Add D toB+No further dependencies to apply
Final closure: A+={A,B,C,D,E}	Final closure: B+={B,D}

Concept of Candidate Key

A candidate key is a minimal set of attributes that can uniquely identify all other attributes in a relational schema.

• A candidate key’s closure must contain all attributes in the schema.
• If multiple candidate keys exist, they provide alternate ways to uniquely identify tuples.

Finding Candidate Keys

To find candidate keys we must follow the following set of points in mind.

• Compute the closure of each attribute (or combination of attributes).
• If the closure contains all attributes in the schema then the attribute set is a candidate key.
• Ensure the minimality by checking if removing any attribute from the set still results in a closure containing all attributes.

Example of Candidate Keys

Relational Schema R (A, B, C, D, E) −

Functional dependencies −

• A → B, C
• B → D
• CD → E

Step 1: Find Closures

The following table highlights how you can find closures −

Finding A+	B+	CD+
Start with {A}A → B, C: Add B, CB → D: Add DCD → E: Add EA+={A,B,C,D,E}	Start with {B}B → D: Add DNo further dependencies to applyB+={B,D}	Start with {C, D}CD → E: Add EC, D, E does not reach A or B, so CD+ is incomplete
A+ contains all attributes, so A is a candidate key.	B+ does not contain all attributes, so B is not a candidate key.	CD is not a candidate key.

Step 2: Check Combinations

Other candidate keys can be found by combining attributes and checking closures.

Shortcut for Finding Candidate Keys −

• If a single attribute or minimal set of attributes has a closure, and it is containing all schema attributes, that set is a candidate key. Additionally:
• If E is determined by CD, then CD can be replaced with CB. This combinations involving B should be checked.

By systematically using dependencies, we can infer keys without exhaustive searches.

Conclusion

In this chapter, we understood how to use functional dependencies to find closures and candidate keys. We started with the basics of functional dependency and understood its role in identifying relationships between attributes. Then, we used examples to understand how closures work and how they help determine candidate keys.

We also analyzed the efficient methods for finding candidate keys and highlighted their significance in relational schema design.

Functional dependencies are quite useful while making databases and designing proper table relations. Functional dependencies define relationships between attributes in a table; they help in normalizing the tables and ensuring data consistency as well.

A common question in this domain is how to compare two sets of functional dependencies and determine if they are equivalent. Read this chapter to get a good understanding of the concept of equivalence of functional dependencies and explain how to determine if one set is a subset of another, or if both sets are the same.

What is Equivalence of Functional Dependencies?

Consider there are two sets of functional dependencies, F and G. They are considered equivalent if −

• Every dependency in F can be derived from G.
• Every dependency in G can be derived from F.

In other words, F ⊆ G and G ⊆ F. If both conditions hold, then F and G are equal.

The Importance of Equivalence

It is important to have a good understanding of the concept of “equivalence” while designing databases or while performing normalization and query optimization. It ensures that dependencies are not repeated and helps to compare alternative dependency sets to see if they represent the same relationship.

How to Compare Two Sets of Functional Dependencies?

To check whether two Functional Dependencies are equivalent, we can use the “closure of attributes”. The closure of an attribute set is the set of attributes that can be determined using the given functional dependencies.

The process involves −

• Calculating closures for attributes using one set of dependencies.
• Verifying if these closures match when computed using the other set.
• Repeating the process with the roles reversed to ensure equivalence.

Step-by-Step Example

Let us see one example for a relational schema R with attributes and two sets of functional dependencies F and G −

Set F	Set G
A → CAC → DE → AH	A → CDE → AH

We will check if F and G are equivalent or not.

Step 1: Compute Closures Using G

We start by computing the closure of each attribute or attribute combination from F. Here we calculate them using the functional dependencies in G.

Closure of A Using G −

• A is in the closure by itself
• A → CD (from G): Add C and D to the closure
• Closure of A is: {A, C, D}

Closure of AC Using G −

• Start with AC
• A → CD (from G): Add C and D to the closure
• Closure of AC: {A, C, D}

Closure of E Using G −

• E is in the closure by itself
• E → AH (from G): Add A and H
• A → CD (from G): Add C and D using A

Closure of E: {E, A, H, C, D}

At this point, we have computed closures for A, AC, and E using G.

Step 2: Verify F ⊆ G

Now, we check if F’s dependencies are covered by G −

Dependency A → C from F −

• Closure of A using G: {A, C, D}
• C is in the closure, so A → C is valid in G

Dependency AC → D from F −

• Closure of AC using G: {A, C, D}
• D is in the closure, so AC → D is valid in G

Dependency E → A, H from F −

• Closure of E using G: {E, A, H, C, D}
• A and H are in the closure, so E → A, H is valid in G

Since all dependencies in F can be derived from G, F ⊆ G is true.

Step 3: Compute Closures Using F

Next, we compute closures for attributes in G, but this time using F.

Closure of A Using F −

• A is in the closure by itself
• A → C (from F): Add C to the closure
• AC → D (from F): Add D using AC
• Closure of A: {A, C, D}

Closure of E Using F −

• E is in the closure by itself
• E → A, H (from F): Add A and H
• A → C (from F): Add C
• AC → D (from F): Add D using AC

Closure of E: {E, A, H, C, D}

Step 4: Verify G ⊆ F

Finally, we check if G’s dependencies are covered by F −

Dependency A → CD from G −

• Closure of A using F: {A, C, D}
• C and D are in the closure, so A → CD is valid in F

Dependency E → AH from G −

• Closure of E using F: {E, A, H, C, D}
• A and H are in the closure, so E → AH is valid in F

Since all dependencies in G can be derived from F, G ⊆ F is true.

Conclusion: F and G Are Equivalent

From the above steps, we conclude that F ⊆ G and G ⊆ F. It means F and G are equivalent functional dependency sets.

Key Points to Note

Take a note of the following key points –

• Use Closures for Comparison − To compare two sets of dependencies, we must compute closures for each attribute or attribute set.
• Check Both Directions − Verify the subsets like F ⊆ G and G ⊆ F to ensure equivalence.
• Simplify Where Possible − Minimize the dependency sets before comparison to avoid unnecessary computations.

Conclusion

In this chapter, we understood how to determine the equivalence of functional dependencies. We started the discussion by understanding the concept and importance of equivalence, followed by a step-by-step process to compare two sets of dependencies.

Using closures, we verified that both sets could derive the same attributes, proving their equivalence. This process is needed in database design; it helps in identifying redundant dependencies and in performing schema normalization.

In database management systems (DBMS), a minimal cover (or irreducible set) is a simplified version of a given set of functional dependencies. It preserves the original meaning but eliminates redundancies and unnecessary complexities. One needs to learn the process of finding a minimal cover for database normalization. It helps in creating efficient and well-structured tables.

In this chapter, we will explain the concept of minimal cover in simple steps, and see the process with an example for a better understanding.

What is Minimal Cover in Functional Dependency?

A minimal cover of a set of functional dependencies is an equivalent set that satisfies these conditions −

• The right-hand side (RHS) of every functional dependency has exactly one attribute.
• No functional dependency will be redundant.
• The left-hand side (LHS) of every functional dependency is as small as possible. It means we cannot remove any attribute without losing the dependency.

With these conditions, a minimal cover helps us in simplifying the design while retaining the same functional relationships as the original set.

Steps to Find Minimal Cover

Let us now understand how to find the minimal cover. To compute the minimal cover, we follow three key steps −

• Decompose the RHS − It shows that every functional dependency has only one attribute on its RHS.
• Remove Redundant Functional Dependencies − Check and eliminate any dependencies that are not needed.
• Minimize the LHS − Simplify the LHS of each dependency by removing unnecessary attributes.

Let us get a good understanding of these steps see these steps down further with an example.

Example: Finding the Minimal Cover

Suppose we are given the following functional dependencies −

• A → B
• C → B
• D → A, B, C
• AC → D

We aim to find the minimal cover for this set.

Step 1: Decompose the RHS

First, we make sure that each functional dependency has only one attribute on its RHS. This is done using the decomposition property.

• A → B: This is already in the correct form. It has the RHS has a single attribute.
• C → B: Again, this is fine as is.
• D → A, B, C: Here, the RHS has three attributes. We decompose it into three separate dependencies:
  • D → A
  • D → B
  • D → C
• AC → D: The RHS has one attribute. So it remains unchanged.

After Step 1, our updated set of dependencies looks like this −

• A → B
• C → B
• D → A
• D → B
• D → C
• AC → D

Step 2: Remove Redundant Dependencies

Next, we check each functional dependency. To see if it is redundant. A dependency is redundant if it can be removed without changing the meaning of the set. This shows finding closures and verifying if the dependent attribute can still be determined without the removed dependency.

• Check A → B − Remove A → B and calculate the closure of A using the remaining dependencies. The closure of A only includes A. Since B is not in the closure, A → B is not redundant and must be kept.
• Check C → B − Remove C → B and calculate the closure of C. The closure of C only includes C. So B cannot be determined. Thus, C → B is not redundant and must be kept.
• Check D → A − Remove D → A and calculate the closure of D. The closure of D includes D, B, C, but A cannot be determined without this dependency. Therefore, D → A is not redundant and must stay.
• Check D → B − Remove D → B and calculate the closure of D. The closure of D still includes B. So D → B is redundant and can be removed.
• Check D → C − Remove D → C and calculate the closure of D. The closure of D does not include C, so D → C is not redundant and must stay.
• Check AC → D − Remove AC → D and calculate the closure of AC. Without AC → D, D cannot be determined. So this dependency is not redundant and must stay.

After Step 2, the updated set of dependencies is −

• A → B
• C → B
• D → A
• D → C
• AC → D

Step 3: Minimize the LHS

In the final step, we minimize the LHS of each dependency. It involves removing attributes from the LHS if they are not needed to determine the RHS.

Minimize AC → D −

Check if either A or C can be removed from the LHS.

• Remove A and calculate the closure of C. The closure of C does not include D, so A cannot be removed.
• Remove C and calculate the closure of A. The closure of A also does not include D, so C cannot be removed.

Thus, AC → D remains as is.

All other dependencies already have a single attribute on the LHS. So, no further minimization is needed.

Final Minimal Cover

The minimal cover for the given functional dependencies is −

• A → B
• C → B
• D → A
• D → C
• AC → D

Importance of Minimal Cover

Minimal cover is needed because it simplifies the set of functional dependencies while maintaining their original meaning. It helps in −

• Avoiding redundant computations.
• Reducing the complexity of database design.
• Making normalization easier.

By ensuring that both the LHS and RHS of dependencies are as simple as possible, the minimal cover aids in creating efficient and well-organized databases.

Functional Dependency is one of the basic but important concepts in databases. It is highly useful in understanding normalization and how attributes in a table relate to one another. We have come across this term “functional dependency” while studying the concepts of Database Design and topics like Keys and Normal Forms.

In this chapter, we will cover the concepts of functional dependencies in detail with simple explanations and practical examples for a better understanding.

What is Functional Dependency?

In short, functional dependency is all about relationships between attributes (columns) in a table. We can say that the value of one attribute (or a group of attributes) can be used to determine the value of another attribute in the same table.

Think of it this way: If we know the value of A, can we always find the corresponding value of B? If yes, then we say A determines B, or we can represent this with an arrow, A → B. We can also say that B is dependent on A.

To get a better understanding, let us compare this concept with a function in mathematics. Imagine we have a function f where we input a number ‘a‘, and it calculates the square of that number as the output ‘b‘.

For example − Input a = 5, the function calculates b = 25. Here, “a uniquely determines b“.

In databases, it is a little bit different. Instead of calculating a value, we simply use one attribute (or a set of attributes) to find or identify another. Let us see this with a table example.

Functional Dependency in Action

Consider a table T with two columns, A and B −

A	B
1	X
2	Y
3	Z

Here, if someone gives us the value of A, like A = 2, we can look at the table and find that the corresponding value of B is Y. This tells us that A determines B, or A → B.

Key Components of Functional Dependency

In functional dependencies we must keep in mind several terms or components −

• Determinant − The attribute(s) used to determine the other attribute (Left hand attribute)
• Dependent − The attribute whose value is determined (Right hand attribute)

In the example above −

• A is the determinant
• B is the dependent

Examples of Functional Dependency

Let us see more detailed examples and analyze if the dependencies are valid or not.

Example 1: Roll Number Determines Student Information

Imagine a table with the following attributes: (Roll Number, Student Name, Department Name, and Department Building).

Roll Number	Student Name	Department Name	Department Building
1	Alice	CS	A4
2	Bob	IT	B2
3	Carol	CS	A4

If we say Roll Number → Student Name, Department Name, Department Building, is this a valid functional dependency?

Yes, because, each roll number is unique, meaning it can help us identify the student’s name, department, and building. For example −

If Roll Number = 3, we can easily find that the student is Carol, in the CS department, and her building is A4.

Example 2: Department Name Determines Department Building

Using the same table, let us see another example. Check if Department Name → Department Building is a valid functional dependency or not. Observe carefully, the Department Name column has duplicate values: “CS” appears twice. However, for both instances, the corresponding Department Building is the same (A4).

So, even though there’s redundancy, this is still a valid dependency because CS always maps to A4, no matter how many times it appears.

Example 3: Different Determinants with the Same Dependent

Now, consider another functional dependency, say Department Name → Department Building, but we add another department to the table −

Department Name	Department Building
CS	A4
IT	B2
ME	B2

Here, two departments (IT and ME) share the same building (B2). Is this valid?

Yes, it is also valid. Multiple determinants (IT and ME) can point to the same dependent (B2). This does not violate the rules of functional dependency.

Example 4: Student Name Determines Department Name

Consider another example. Here the functional dependency Student Name → Department Name.

In our table, two students (Bob and another student) could share the same name but belong to different departments. For instance −

Student Name	Department Name
Bob	CS
Bob	IT

If we ask, “Which department is Bob in?”, there are two possible answers: CS and IT. This makes the dependency invalid. This is because a single determinant (Student Name) does not lead to a unique dependent (Department Name).

Analyzing Valid and Invalid Cases

Now let us categorize functional dependency scenarios −

• Unique Determinant to Unique Dependent − Example: Roll Number → Student Information. This is valid because each roll number is unique and maps to a specific set of values.
• Same Determinant with Same Dependent − Example: Department Name → Department Building. Valid even with duplicate department names. And as they always map to the same building.
• Different Determinants with Same Dependent − Example: IT → B2, ME → B2. This is valid because multiple attributes can lead to the same dependent value.
• Same Determinant with Different Dependents − Example: Student Name → Department Name (with duplicates). This is invalid because one determinant (Student Name) leads to multiple, conflicting values.

Importance of Functional Dependency

The functional dependencies are important for database normalization. They help us identify several factors as listed below −

• Redundancies in data
• Which attributes should serve as keys
• How to design efficient, error-free database structures

Without properly handling functional dependencies, we might design database tables that are prone to anomalies and inefficiencies.