Unit-7: Relational Database Design

Introduction to Relational Database Design

Relational Database Design is the process of organizing data into tables (relations) and columns (attributes) and establishing relationships between them. The primary goals are to:

• Minimize Redundancy: Store each piece of information only once.
• Ensure Data Integrity: Maintain consistency and accuracy of data.
• Avoid Anomalies: Prevent issues during insertion, deletion, and update operations.
• Improve Query Performance: Design a schema that allows efficient data retrieval.

Features of Good Relational Database Design

A well-designed relational database schema exhibits several key features:

• Minimizing Data Redundancy: Duplication of data wastes storage space and can lead to inconsistencies. Good design reduces this by structuring data appropriately.
• Avoiding Update Anomalies: Anomalies are problems that arise when redundant data is not handled properly during data modification operations.
  • Insertion Anomaly: Cannot insert new data without also inserting data for unrelated attributes. Example: Cannot add a new department without having an employee assigned to it.
  • Deletion Anomaly: Deleting one piece of data inadvertently deletes other, unrelated data. Example: Deleting the last employee of a department also deletes the department's information.
  • Update Anomaly: Updating one piece of data requires updating multiple copies, leading to inconsistency if some copies are missed. Example: Changing a department's name requires updating every employee record associated with that department.
• Ensuring Data Integrity: Maintaining the accuracy and consistency of data over its entire life cycle. This includes entity integrity (primary keys are unique and non-null) and referential integrity (foreign keys correctly reference primary keys).
• Flexibility and Scalability: The design should be adaptable to future changes in requirements and capable of handling increasing amounts of data and users.
• Ease of Querying and Reporting: A logical and structured design simplifies writing queries and generating reports, making data access more intuitive for users and applications.

Atomic Domains and First Normal Form (1NF)

Atomic Domains

A domain is atomic if elements of the domain are considered to be indivisible units. This means that each value in the domain cannot be further decomposed into smaller meaningful parts.

Example:

• An integer (e.g., 123) is atomic.
• A string (e.g., 'John Doe') is atomic in the context of a name, but if we wanted to query by 'first name' or 'last name' separately, it wouldn't be atomic for those individual parts. A good practice is to separate first and last names into different attributes.
• A list of phone numbers (e.g., '{123-456-7890, 987-654-3210}') within a single attribute is not atomic because it's a collection of values. Each phone number should be a separate entry or in a separate table.

First Normal Form (1NF)

A relation (table) is in First Normal Form (1NF) if and only if all attribute values are atomic (indivisible) and there are no repeating groups of attributes.

Conditions for 1NF:

1. Each column must contain only atomic values (no lists, sets, or nested structures within a single cell).
2. Each column must contain values of the same data type.
3. Each column must have a unique name.
4. The order of rows does not matter.
5. The order of columns does not matter.

Example of Non-1NF Relation:

STUDENT_COURSE (StudentID, StudentName, Courses)

Here, the Courses attribute contains multiple values (a repeating group), violating 1NF.

Converting to 1NF:

To convert the above table to 1NF, we eliminate the repeating group by creating separate rows for each course or by creating a separate relation.

This table is now in 1NF. Note that the primary key for this table would be (StudentID, Course).

Functional Dependency Theory

Functional dependencies are fundamental to understanding and applying normal forms. They describe relationships between attributes.

Definition of Functional Dependency (FD)

A functional dependency (FD) is a constraint between two sets of attributes in a relation. For a relation R, if A and B are two sets of attributes of R, then B is functionally dependent on A (denoted as A -> B), if for every valid instance of R, whenever two tuples have the same values for A, they must also have the same values for B. In simpler terms, A uniquely determines B.

Key Concepts:

• Determinant: The attribute(s) on the left-hand side of the arrow (A).
• Dependent: The attribute(s) on the right-hand side of the arrow (B).

Example: Consider a Student relation with attributes (StudentID, StudentName, Major, Advisor).

• StudentID -> StudentName: If you know a StudentID, you uniquely know the StudentName.
• StudentID -> Major: A student has only one major.
• StudentID -> StudentName, Major, Advisor: StudentID determines all other attributes of that student.

Armstrong's Axioms

Armstrong's Axioms are a set of inference rules used to derive all possible functional dependencies from a given set of FDs. They are sound (do not derive incorrect FDs) and complete (can derive all correct FDs).

1. Reflexivity Axiom: If B is a subset of A, then A -> B.

   • Explanation: Any set of attributes trivially determines any of its subsets. This is always true.
   • Example: If A = {StudentID, StudentName} and B = {StudentName}, then {StudentID, StudentName} -> {StudentName}.

2. Augmentation Axiom: If A -> B, then AC -> BC (where C is any set of attributes).

   • Explanation: If A determines B, then adding common attributes C to both sides of the dependency does not change its validity.
   • Example: If StudentID -> StudentName, then {StudentID, CourseID} -> {StudentName, CourseID}.

3. Transitivity Axiom: If A -> B and B -> C, then A -> C.

   • Explanation: If A determines B, and B in turn determines C, then A indirectly determines C.
   • Example: If StudentID -> Major and Major -> DepartmentHead, then StudentID -> DepartmentHead.

Additional Derived Rules: These rules can be proven using Armstrong's Axioms but are often used directly for convenience.

• Union Rule: If A -> B and A -> C, then A -> BC.

  • Explanation: If a set of attributes determines multiple other attributes independently, it also determines their combination.

• Decomposition Rule: If A -> BC, then A -> B and A -> C.

  • Explanation: If a set of attributes determines a combination of attributes, it also determines each of them individually.

• Pseudotransitivity Rule: If A -> B and BC -> D, then AC -> D.

  • Explanation: Similar to transitivity, but with augmentation.

Closure of a Set of FDs (F+)

The closure of a set of functional dependencies F (denoted as F+) is the set of all functional dependencies that can be logically inferred from F using Armstrong's Axioms.

Finding F+ involves iteratively applying Armstrong's Axioms until no new FDs can be derived.

Example: Given R(A, B, C, D) and F = {A -> B, B -> C}.

Initial F+ = {A -> B, B -> C}

• Applying Transitivity: A -> C (from A -> B and B -> C)
• Applying Augmentation: A -> BD (from A -> B), AB -> BC (from A -> B), etc.
• Applying Reflexivity: A -> A, B -> B, etc.

The complete F+ would include all these and further derived dependencies.

Closure of an Attribute Set (X+)

The closure of an attribute set X (denoted as X+) with respect to a set of FDs F is the set of all attributes A such that X -> A can be inferred from F. It helps identify all attributes determined by X.

Algorithm to find X+:

1. Initialize result = X.
2. Repeat until no new attributes can be added to result:
   • For each functional dependency Y -> Z in F:
   • If Y is a subset of result, then add all attributes in Z to result.
3. Return result.

Example: Given R(A, B, C, D, E) and F = {A -> BC, CE -> D, B -> E}. Find the closure of A (A+).

1. result = {A}

2. Iteration 1:

   • A -> BC: A is a subset of result. Add B, C. result = {A, B, C}.
   • CE -> D: C is in result, but E is not. Skip.
   • B -> E: B is in result. Add E. result = {A, B, C, E}.

3. Iteration 2:

   • A -> BC: Y ({A}) is subset of result. Z ({B,C}) already in result.
   • CE -> D: Y ({C, E}) is subset of result ({A, B, C, E}). Add D. result = {A, B, C, D, E}.
   • B -> E: Y ({B}) is subset of result. Z ({E}) already in result.

4. Iteration 3: No new attributes added.

Therefore, A+ = {A, B, C, D, E}. Since A+ contains all attributes of R, A is a candidate key for R.

Minimal Cover (Canonical Cover)

A minimal cover (or canonical cover) for a set of functional dependencies F is a simplified set of FDs G that is equivalent to F (meaning G+ = F+), but satisfies the following properties:

1. Every dependency in G has a single attribute on the right-hand side.
2. No dependency in G can be removed without changing G+. (Irreducible)
3. No attribute can be removed from the left-hand side of any dependency in G without changing G+. (Non-redundant left-hand side)

Finding a minimal cover is useful for database design and normalization as it provides a minimal set of constraints to consider.

Algorithm (general steps):

1. Split right-hand sides: For each FD X -> Y in F, if Y is a composite attribute, replace it with X -> A1, X -> A2, ..., X -> An, where Y = {A1, A2, ..., An}.

   Example: If A -> BC, replace with A -> B and A -> C.

2. Remove extraneous attributes from left-hand sides: For each FD X -> A in the current set G, and for each attribute B in X, check if (X - {B}) -> A can be inferred from F. If it can, remove B from X. Repeat until no more attributes can be removed.

   Example: If ABC -> D and AC -> D is derivable using the rest of FDs, then B is extraneous, and ABC -> D can be replaced by AC -> D.

3. Remove redundant FDs: For each remaining FD X -> A in G, check if X -> A can be inferred from G - {X -> A} (i.e., from all other FDs in G). If it can, remove X -> A from G.

   Example: If G = {A -> B, B -> C, A -> C}, then A -> C is redundant because it can be derived from A -> B and B -> C. Remove A -> C.

The resulting set G is a minimal cover for F.

Decomposition Using Functional Dependencies

Decomposition is the process of breaking down a large, complex relation into smaller, simpler relations to improve database design by eliminating redundancy and anomalies.

Need for Decomposition

When a relation is not in a desirable normal form (e.g., it contains partial or transitive dependencies), it can suffer from update anomalies. Decomposing the relation into multiple smaller relations can resolve these issues, making the database more efficient and consistent.

Desirable Properties of Decomposition

When decomposing a relation, it's crucial to ensure that certain properties are maintained to avoid losing information or constraints.

Lossless Join Decomposition

A decomposition of a relation R into relations R1, R2, ..., Rn is a lossless-join decomposition if the natural join of all the decomposed relations (R1 JOIN R2 JOIN ... JOIN Rn) yields exactly the original relation R, without generating any spurious tuples (extra rows that were not in the original relation).

Condition for Lossless Join: For a decomposition of R into R1 and R2 to be lossless with respect to a set of FDs F, at least one of the following must hold:

1. (R1 intersection R2) -> R1 is in F+
2. (R1 intersection R2) -> R2 is in F+

The common attributes between R1 and R2 must functionally determine all other attributes in at least one of the decomposed relations.

Dependency Preservation

A decomposition of a relation R with FDs F into relations R1, R2, ..., Rn is dependency-preserving if all functional dependencies from the original set F can be enforced by simply enforcing the functional dependencies in each of the decomposed relations Ri. This means the union of FDs in each Ri (F1 U F2 U ... U Fn) is equivalent to F (i.e., (F1 U F2 U ... U Fn)+ = F+).

Why it's important: If a decomposition is not dependency-preserving, we might have to check dependencies across multiple tables, which can be inefficient or impossible for the DBMS to enforce automatically.

Decomposition to Third Normal Form (3NF)

The goal of 3NF decomposition is to eliminate transitive dependencies while preserving all functional dependencies and ensuring a lossless join.

Algorithm Sketch for 3NF Decomposition (Synthesis Approach):

1. Find a minimal cover G for the set of FDs F.
2. For each FD X -> A in G, create a relation schema Ri = {X U A}.
3. If none of the created schemas Ri contains a candidate key of the original relation R, then add a new relation schema Rk consisting of a candidate key of R.

This algorithm guarantees a lossless-join and dependency-preserving decomposition into 3NF.

Decomposition to Boyce-Codd Normal Form (BCNF)

BCNF is a stricter normal form than 3NF. Decomposition into BCNF aims to eliminate all FDs where the determinant is not a superkey.

Algorithm Sketch for BCNF Decomposition:

1. Start with a relation R that is not in BCNF.
2. Find a functional dependency X -> Y in R that violates BCNF (i.e., X is not a superkey of R, and X -> Y is non-trivial).
3. Decompose R into two relations: R1 = (X U Y) and R2 = (R - Y) U X.
4. Repeat the process for R1 and R2 until all relations are in BCNF.

Important Note: Decomposition into BCNF is always lossless-join, but it might *not* always be dependency-preserving. If dependency preservation is a strong requirement, 3NF might be preferred over BCNF in some cases, or a compromise might be sought.

Multivalued Dependencies (MVDs)

Definition of Multivalued Dependency (MVD)

A multivalued dependency (MVD) is a constraint that requires certain tuples to be present in a relation. For a relation R with attributes A, B, and C, an MVD A ->-> B (read as 'A multidetermines B') exists if, for any two tuples in R that have the same value for A, then the set of B-values associated with A is independent of the set of C-values associated with A.

In simpler terms, if A ->-> B, it means that for a given value of A, there is a set of B values associated with it, and this set of B values is independent of other attributes (C) in the relation. MVDs capture the fact that two or more independent, multivalued facts about an entity can coexist in a single table.

Example: Consider an EMPLOYEE_SKILL_PROJECT relation (EmployeeID, Skill, Project).

An employee can have multiple skills, and an employee can work on multiple projects. These two facts (skills and projects) might be independent of each other for a given employee. If EmployeeID 'E1' has skills {'S1', 'S2'} and works on projects {'P1', 'P2'}, the table might contain:

Here, EmployeeID ->-> Skill and EmployeeID ->-> Project are MVDs. This redundancy leads to storage waste and anomalies.

Functional Dependency vs. Multivalued Dependency

While FDs imply a one-to-one or many-to-one relationship, MVDs describe one-to-many relationships where the 'many' is independent of other attributes.

Decomposition to Fourth Normal Form (4NF)

Decomposition into 4NF specifically targets and eliminates the redundancy caused by multivalued dependencies.

Algorithm Sketch for 4NF Decomposition:

1. Start with a relation R that is not in 4NF. This means R has a non-trivial MVD A ->-> B where A is not a superkey.
2. Decompose R into two relations: R1 = (A U B) and R2 = (R - B).
3. Repeat the process for R1 and R2 until all relations are in 4NF.

This decomposition is always lossless-join and resolves anomalies related to MVDs. The example EMPLOYEE_SKILL_PROJECT table would be decomposed into (EmployeeID, Skill) and (EmployeeID, Project), eliminating redundancy.

More Normal Forms

Normalization is a systematic approach to decomposing relations to reduce redundancy and improve data integrity. Normal forms are a series of guidelines that help achieve this. Here's a summary of common normal forms:

Second Normal Form (2NF)

A relation is in Second Normal Form (2NF) if it is in 1NF and every non-prime attribute is fully functionally dependent on every candidate key. This means no non-prime attribute can be partially dependent on a candidate key.

• Prime Attribute: An attribute that is part of any candidate key.
• Non-Prime Attribute: An attribute that is not part of any candidate key.
• Partial Dependency: A non-prime attribute is dependent on only a part of a candidate key.

Example of Non-2NF: Consider ORDER_DETAILS (OrderID, ProductID, Quantity, ProductName, ProductPrice) with candidate key (OrderID, ProductID).

• (OrderID, ProductID) -> Quantity (Full functional dependency)
• ProductID -> ProductName (Partial dependency, ProductName depends only on ProductID, not OrderID)
• ProductID -> ProductPrice (Partial dependency)

To convert to 2NF, split the table:

• ORDER_PRODUCT (OrderID, ProductID, Quantity)
• PRODUCT (ProductID, ProductName, ProductPrice)

Third Normal Form (3NF)

A relation is in Third Normal Form (3NF) if it is in 2NF and there are no transitive dependencies of non-prime attributes on any candidate key.

• Transitive Dependency: An indirect functional dependency where A -> B and B -> C, leading to A -> C, and B is not a superkey and C is not a prime attribute.

Example of Non-3NF: Consider EMPLOYEE (EmployeeID, EmployeeName, DepartmentID, DepartmentName, DepartmentLocation) with candidate key EmployeeID.

• EmployeeID -> EmployeeName, DepartmentID, DepartmentName, DepartmentLocation
• DepartmentID -> DepartmentName, DepartmentLocation (Transitive dependency: EmployeeID -> DepartmentID -> DepartmentName)

To convert to 3NF, split the table:

• EMPLOYEE (EmployeeID, EmployeeName, DepartmentID)
• DEPARTMENT (DepartmentID, DepartmentName, DepartmentLocation)

Boyce-Codd Normal Form (BCNF)

A relation is in Boyce-Codd Normal Form (BCNF) if for every non-trivial functional dependency X -> Y, X is a superkey.

Key Differences from 3NF:

• BCNF is a stricter form of 3NF. A relation in BCNF is always in 3NF, but a relation in 3NF is not necessarily in BCNF.
• 3NF allows transitive dependencies if the determinant (B in A->B->C) is a prime attribute. BCNF does not allow this.
• BCNF eliminates all redundancy based on FDs.

When 3NF is not BCNF: This occurs when the relation has multiple overlapping candidate keys, and a non-prime attribute is functionally dependent on a part of a candidate key that is not a superkey itself. Also when there is a FD X -> A where X is not a superkey and A is a prime attribute.

Example: Consider a COURSE_LECTURER (Course, Lecturer, HeadOfDepartment) relation where:

• Course -> Lecturer
• Lecturer -> HeadOfDepartment
• (Course, Lecturer) is a candidate key.

This relation is in 3NF because Lecturer -> HeadOfDepartment is a transitive dependency, but HeadOfDepartment is a non-prime attribute, and Lecturer is not a candidate key. However, it's not in BCNF because Lecturer -> HeadOfDepartment, but Lecturer is not a superkey.

To achieve BCNF, decompose into:

• COURSE_ASSIGNMENT (Course, Lecturer)
• LECTURER_DEPARTMENT (Lecturer, HeadOfDepartment)

Fourth Normal Form (4NF)

A relation is in Fourth Normal Form (4NF) if it is in BCNF and contains no non-trivial multivalued dependencies.

Key Point: 4NF addresses MVDs that are not FDs. If a relation has an MVD A ->-> B and A is not a superkey, the relation is not in 4NF. This leads to redundancy, as seen in the EMPLOYEE_SKILL_PROJECT example under MVDs.

Fifth Normal Form (5NF) / Project-Join Normal Form (PJNF)

A relation is in Fifth Normal Form (5NF) if it is in 4NF and cannot be decomposed into smaller tables without loss of information (i.e., it has no join dependencies that are not implied by the candidate keys).

Explanation: 5NF deals with join dependencies. A relation R has a join dependency if it can be reconstructed by joining several smaller relations, but R cannot be split into fewer than those relations without losing information. It is rarely encountered in practical database design because relations violating 5NF usually involve complex interdependencies that are best handled at the application level.

Domain-Key Normal Form (DKNF)

A relation is in Domain-Key Normal Form (DKNF) if every constraint on the relation is a logical consequence of its domain constraints and key constraints.

Explanation: This is an ideal, theoretical normal form. If a relation is in DKNF, it is free of all update, insertion, and deletion anomalies. The idea is that all constraints can be enforced merely by enforcing the domain and key constraints. However, achieving DKNF is often impractical as many real-world constraints (e.g., business rules) cannot be expressed solely as domain and key constraints.

Database Design Process

Designing a database is a systematic process involving several stages to ensure an efficient, reliable, and maintainable system.

1. Requirements Analysis:

   • Goal: Understand the purpose of the database, the data to be stored, and how users will interact with it.
   • Activities: Gather requirements from stakeholders, analyze existing systems, identify entities, attributes, and relationships. Create data dictionary.
   • Output: Detailed requirements document, user stories, use cases.

2. Conceptual Design (Entity-Relationship Modeling):

   • Goal: Create a high-level, implementation-independent representation of the data.
   • Activities: Develop an Entity-Relationship (ER) model or other conceptual data model. Identify entities (objects of interest), their attributes (properties), and relationships (associations between entities). Specify primary keys and cardinality of relationships (one-to-one, one-to-many, many-to-many).
   • Output: ER Diagram.

3. Logical Design (Relational Schema Design and Normalization):

   • Goal: Transform the conceptual model into a logical schema compatible with a specific data model (e.g., relational model). Apply normalization rules.
   • Activities:
     • Convert entities into relations (tables).
     • Convert attributes into columns.
     • Define primary keys for each relation.
     • Convert relationships into foreign keys or new relations.
     • Apply normalization (1NF, 2NF, 3NF, BCNF, etc.) to eliminate redundancy and anomalies based on functional and multivalued dependencies. This ensures the schema is well-structured.
     • Define data types for each attribute.
   • Output: Relational schema with tables, columns, primary keys, foreign keys, and normalized structure.

4. Physical Design:

   • Goal: Implement the logical design within a chosen Database Management System (DBMS). Optimize for performance and storage.
   • Activities:
     • Choose specific data types supported by the DBMS (e.g., VARCHAR, INT).
     • Define indexes for frequently accessed columns to speed up queries.
     • Specify storage structures (e.g., clustered/non-clustered indexes).
     • Determine partitioning strategies for large tables.
     • Implement security measures (user roles, permissions).
   • Output: DDL (Data Definition Language) scripts for table creation, index definitions, and security settings.

5. Implementation:

   • Goal: Create the actual database in the chosen DBMS.
   • Activities: Execute the DDL scripts generated during physical design. Load initial data into the database.
   • Output: A functional database instance.

6. Testing and Refinement:

   • Goal: Verify that the database meets requirements, functions correctly, and performs efficiently.
   • Activities: Populate the database with test data. Run various queries and transactions to check correctness and performance. Optimize queries or modify physical design if performance issues arise. Review data integrity.
   • Output: Performance reports, bug fixes, schema adjustments.

7. Maintenance:

   • Goal: Ensure the database continues to operate effectively and meet evolving needs.
   • Activities: Regular backups, performance monitoring, tuning, security updates, schema evolution (adding new tables/columns as requirements change), data archiving.
   • Output: Ongoing operational efficiency and adaptability.