Relational Database Design:

Chapter 8: Relational Database Design

Lecture Outcome

• Upon completion, students will be able to:

  • Identify problems tied to bad database design

  • Explain Functional Dependency (FD)

  • List various types of dependencies

  • Explain Armstrong Inference Axioms

  • Determine closures of attributes/attribute sets

  • Determine closures of Functional Dependencies (FDs)

  • Determine equivalences of FDs

  • Identify redundant FDs

  • Determine Canonical or Minimal Cover

Organization of the Lecture

• Introduction to Database Design

• Problems associated with bad design

• Functional Dependency Theory

• Armstrong Inference Axioms

• Closure of Attributes/Attribute Set

• Closure of a Set of Functional Dependency

• Equivalence of FDs

• Redundancy of FDs

• Canonical Cover

Introduction to Database Design

• Goal: Create relational schemas for storing information without unnecessary redundancy while maintaining ease of data retrieval.

• Steps for Good Design:

  1. Characterize data requirements through textual descriptions.

  2. Choose an Entity-Relationship (ER) model for designing a conceptual schema.

  3. Map the conceptual schema onto a relational data model (Logical Design).

  4. Use the specific database schema during the Physical Design phase.

Approaches to Database Design

• Bottom-up Approach (Design by Synthesis):

  • Focuses on relationships among individual attributes to construct schemas.

  • Challenges include identifying numerous binary relationships from attributes.

• Top-down Approach (Design by Analysis):

  • Starts with aggregating attributes into relations that naturally exist (e.g., an Invoice).

  • Analyzes relations leading to decomposition until all desirable properties are achieved.

Bad Database Design / Concepts of Anomalies

• Anomalies in Poorly Planned Databases:

  • Problems arise from storing all data in a single table, affecting data insertion, deletion, and updates.

  • Example: Student Database which leads to inefficiencies.

Types of Anomalies

1. Insertion Anomaly:

   • Occurs when an attribute cannot be inserted due to the absence of another attribute.

   • Example: Unable to record a new professor without course assignment.

2. Deletion Anomaly:

   • Deleting an entry leads to loss of valuable information related to another entity.

   • Example: Deleting a course inadvertently deletes associated professor information.

3. Updation Anomaly:

   • Requires modulating the same attribute across several records, risking inconsistency.

   • Example: Updating a student's phone number incorrectly affects the database state.

Functional Dependency (FD)

Functional Dependency is the building block of normalization

principles.

• Definition: Basic principle of normalization.

  • If attribute(s) A in relation schema R functionally determines attribute(s) B, then for a given value of A, there is a single, corresponding value of B.

  • Symbolically: A → B (A is determinant, B is dependent).

Checking Functional Dependency

• Conditions to Ensure FD (A → B):

  1. Unique values of A imply FD holds.

  2. If all B values for given A values are the same, FD holds.

  3. If same A values yield differing B values, the FD does not hold.

Types of Functional Dependencies

1. Trivial vs Non-Trivial FD:

   • Trivial: If Y is a subset or equal to X (e.g., {Name, Course} → Course).

   • Non-Trivial: Y is not a subset of X; e.g., Prof → Grade.

2. Multivalued Dependency:

   • Occurs when multiple independent multivalued attributes exist downwards;

   • Consider a bike manufacture company, havind attributes as (bike_model, mfg_year, color), here mfg_year and color are independent to eachother.

     e.g.:

     bike_model ->> mfg_year; 
     bike_model ->> color

3. Transitive Dependency:

   • Indirect dependency formed by two functional dependencies (X → Z if X → Y and Y → Z).

Armstrong’s Inference Axioms

• Purpose: Infer FDs satisfied by a relation.

  • Includes several fundamental rules:

  • Reflexivity: If Y is a subset of X, then X → Y.

  • Augmentation: If X → Y, then {X, Z} → {Y, Z}.

  • Transitivity: If X → Y and Y → Z, then X → Z.

Secondary Inference Rules

• Union Rule: X → Y and X → Z implies X → {Y, Z}.

• Decomposition Rule: X → {Y, Z} implies X → Y and X → Z.

• Composition Rule: If X → Y and Z → W, then {X, Z} → {Y, W}.

• Pseudotransitivity Rule: If X → Y and {Y, W} → Z, then {X, W} → Z.

Example of Functional Dependencies

• Testing functional dependencies with various attributes and their relations.

Closure of Attribute Sets

• Definition: Set of attributes functionally defined from set 'A', denoted as A+.

Steps To Determine Attribute Closure:

1. Apply FDs to the set.

2. Keep add-ons until no more attributes can be derived.

3. Test the closure for candidate keys and FDs.

Closure of a Set of Functional Dependencies

• Closure F+: the set of FDs logically implied by F, generated by applying axioms through combinations of attributes.

Equivalence of Functional Dependencies

• FDs F and G are equivalent if F+ = G+; can be verified through testing attribute closures.

Redundant Functional Dependencies

• Definition: An FD is redundant if it can be derived from other FDs in the set.

  • Method to find redundancy involves testing each FD's derivability within the remaining set.

Canonical Cover/Minimal Cover

• Definition: A canonical cover is a minimal set of FDs where:

  1. F and Fc are equivalent.

  2. Every FD is simple with one attribute on the RHS.

  3. No FD is redundant.

  4. The LHS attributes are irreducible.

• Method: Achieve a cover by eliminating non-essential dependencies and reducing FDs.

Steps to Find Canonical Cover

1. Write FDs with one attribute on the RHS.

2. Check each FD's essentiality using attribute closures.

3. If FDs have more than one attribute on the LHS, reduce them using closure checks.