Database Decomposition & Keys: Normalization, Lossless Decomposition & Candidate Keys

TAKEAWAYS:

• Decomposition splits relations into smaller tables to eliminate redundancy and improve efficiency, but must preserve dependencies and avoid data loss.
• Lossless decomposition ensures no information is lost when relations are split, verified using functional dependencies.
• Candidate keys are minimal sets of attributes that uniquely identify tuples, while primary keys are chosen from candidates for database operations.
• Superkeys are any set of attributes that can uniquely identify tuples, containing at least one candidate key.
• Normalization (1NF, 2NF, 3NF, BCNF) directly relates to decomposition, ensuring tables are free of anomalies.
• SQL implementation uses PRIMARY KEY, FOREIGN KEY, and UNIQUE constraints to enforce key properties in decomposed databases.

Core Concepts: Keys in Databases

erDiagram
    Student ||--o{ Enrollment : takes
    Course ||--o{ Enrollment : offered
    Student {
        int SID PK
        string SName
        string SAddress
        string SEmail
    }
    Course {
        int CID PK
        string CName
        int Credit_hours
    }
    Enrollment {
        int SID PK, FK
        int CID PK, FK
    }

1. Superkeys, Candidate Keys, and Primary Keys

Keys are attributes (or sets of attributes) that uniquely identify tuples in a relation. They are fundamental to maintaining data integrity and enabling efficient querying.

Definitions

• Superkey: A set of attributes that can uniquely identify tuples in a relation. It may contain redundant attributes. Example: In Student(SID, SName, SAddress, SEmail), {SID, SName} is a superkey because SID alone is sufficient, but including SName (which may not be unique) still makes it a superkey.
• Candidate Key: A minimal superkey—no proper subset of it is a superkey. A relation can have multiple candidate keys. Example: In Employee(EID, SSN, Name), both {EID} and {SSN} are candidate keys if neither can be derived from the other.
• Primary Key: A candidate key chosen by the database designer to uniquely identify tuples. It cannot contain NULL values. Example: In Course(CID, CName, Credit_hours), CID is the primary key.

Why Keys Matter

• Uniqueness: Ensure no duplicate tuples exist.
• Referential Integrity: Enable foreign key relationships between tables.
• Efficiency: Speed up joins and indexing.

Visual: Key Types in a Relation

Database Decomposition

2. What is Decomposition?

Decomposition is the process of breaking down a relation into smaller relations (tables) to:

• Eliminate redundancy (e.g., repeating groups).
• Improve data integrity.
• Simplify queries.

Example: Decomposing a University Database

Consider a relation StudentCourse(SID, SName, SAddress, CID, CName, Credit_hours) with redundancy (e.g., SName repeats for each course a student takes). Decompose it into:

1. Student(SID, SName, SAddress)
2. Course(CID, CName, Credit_hours)
3. Enrollment(SID, CID) (junction table for many-to-many relationships).

3. Lossless Decomposition

Decomposition is lossless if the original relation can be reconstructed from the decomposed relations using natural joins. This depends on functional dependencies (FDs).

How to Check for Lossless Decomposition

1. Compute the closure of the intersection of attributes between decomposed relations under the given FDs.
2. If the closure includes all attributes of at least one of the decomposed relations, the decomposition is lossless.

Example: Lossless vs. Lossy Decomposition

Relation: R(A, B, C) with FDs: A → B, B → C.

• Decomposition 1: R1(A, B) and R2(B, C).
  • Intersection: {B}.
  • Closure of {B}: {B, C} (since B → C).
  • {B, C} includes all attributes of R2, so lossless.
• Decomposition 2: R1(A, C) and R2(B, C).
  • Intersection: {C}.
  • Closure of {C}: {C} (no FDs start with C).
  • {C} does not include all attributes of R1 or R2, so lossy.

4. Dependency Preservation

A decomposition preserves dependencies if all FDs of the original relation can be inferred from the FDs of the decomposed relations. This ensures no information is lost during updates.

Example: Dependency Preservation

Original Relation: R(A, B, C) with FDs: A → B, B → C.

• Decomposition: R1(A, B) and R2(B, C).
  • FDs in R1: A → B.
  • FDs in R2: B → C.
  • Both original FDs are preserved, so the decomposition is dependency-preserving.

Practical Applications: Keys and Decomposition in Real-World Systems

In the Real World

1. eSewa (Nepal):

   • Primary Key: TransactionID in the Transactions table ensures each payment is uniquely identified.
   • Foreign Key: UserID links transactions to users in the Users table, enforcing referential integrity.
   • Decomposition: The database splits into Users, Transactions, and ServiceProviders to avoid redundancy (e.g., storing user details repeatedly for each transaction).

2. Khalti (Nepal):

   • Candidate Keys: Both Email and PhoneNumber can uniquely identify a user (if no duplicates exist), but PhoneNumber is chosen as the primary key for simplicity.
   • Normalization: The Orders table is decomposed into Customers, Products, and OrderItems to eliminate repeating groups (e.g., multiple products per order).

3. Nepal Rastra Bank (NRB):

   • Superkey: In the BankAccounts table, {AccountNumber, BranchID} is a superkey because AccountNumber alone suffices, but including BranchID ensures uniqueness across branches.
   • Decomposition: The Loans table is split into LoanApplicants, LoanTypes, and LoanDisbursements to separate static (e.g., applicant details) and dynamic (e.g., payment schedules) data.

Worked Example: Decomposing a Bank Database

Original Relation: CustomerAccounts(CID, Name, Address, AcNo, Balance, Branch) Problem: Redundancy in Name and Address for each account, and repeating Branch details. Solution: Decompose into:

1. Customers(CID, Name, Address)
2. Accounts(AcNo, CID, Balance)
3. Branches(BranchID, BranchName, Location)

SQL Implementation:

-- Create decomposed tables
CREATE TABLE Customers (
    CID INT PRIMARY KEY,
    Name VARCHAR(100) NOT NULL,
    Address VARCHAR(200)
);

CREATE TABLE Accounts (
    AcNo VARCHAR(20) PRIMARY KEY,
    CID INT,
    Balance DECIMAL(10, 2),
    FOREIGN KEY (CID) REFERENCES Customers(CID)
);

CREATE TABLE Branches (
    BranchID INT PRIMARY KEY,
    BranchName VARCHAR(100),
    Location VARCHAR(100)
);

Why This Works:

• Lossless: The original relation can be reconstructed by joining Customers, Accounts, and Branches on CID and AcNo.
• Dependency Preservation: All FDs (e.g., CID → Name) are preserved in the decomposed tables.

Types of Decomposition

5. Horizontal vs. Vertical Decomposition

classDiagram
    class StudentAll {
        +SID: int
        +SName: string
        +SAddress: string
        +CID: int
        +CName: string
        +Credit_hours: int
    }
    class Student {
        +SID: int
        +SName: string
        +SAddress: string
    }
    class Course {
        +CID: int
        +CName: string
        +Credit_hours: int
    }
    StudentAll --> Student : Vertical split
    StudentAll --> Course : Vertical split
    Student ||--o{ Enrollment : horizontal split
    Course ||--o{ Enrollment : horizontal split

Visual: Horizontal vs. Vertical Decomposition

Normalization and Decomposition

6. How Normalization Guides Decomposition

Normalization (1NF, 2NF, 3NF, BCNF) directly influences decomposition:

• 1NF: Eliminate repeating groups (e.g., decompose Student(Courses) into Student and Enrollment).
• 2NF: Remove partial dependencies (e.g., decompose OrderItems(OrderID, ProductID, Quantity, ProductName) into Orders and Products).
• 3NF: Remove transitive dependencies (e.g., decompose Student(SID, SName, Department, DeptHead) into Student and Department).

Example: Decomposing to 3NF

Original Relation: R(SID, SName, Dept, DeptHead) with FDs: SID → SName, SID → Dept, Dept → DeptHead.

• Problem: Transitive dependency SID → DeptHead via Dept.
• Decomposition:
  1. Student(SID, SName, Dept)
  2. Department(Dept, DeptHead)
• Result: Both tables are in 3NF.

In the real world

• eSewa: Uses candidate keys (TransactionID and UserID) to uniquely identify transactions and users. The database is vertically decomposed into Users, Transactions, and ServiceProviders tables to eliminate redundancy (e.g., storing user details repeatedly for each transaction).
• Nepal Rastra Bank (NRB): Employs lossless decomposition in its Loan system. The LoanApplicants table (candidate key: ApplicantID) is joined with LoanDisbursements (foreign key: ApplicantID) to reconstruct the original relation without data loss, ensuring integrity during updates.
• Daraz (Nepal): Implements horizontal decomposition for order processing. The Orders table splits into Customers, Products, and OrderItems tables, where OrderItems stores only rows for products in a specific order (horizontal subset), while Customers and Products hold master data.

Exam Tip

1. Key Identification:

   • Always identify candidate keys first by checking for minimal uniqueness.
   • Remember: A primary key is just one chosen candidate key.
   • Superkeys are larger sets that include candidate keys (e.g., {A, B} where {A} is a candidate key).

2. Lossless Decomposition:

   • To prove losslessness, compute the closure of the intersection of attributes and check if it includes all attributes of at least one decomposed relation.
   • Example: For R1(A, B) and R2(B, C), check if B+ includes B and C (it does if B → C holds).

3. SQL Implementation:

   • Use PRIMARY KEY, FOREIGN KEY, and UNIQUE constraints to enforce keys in decomposed tables.
   • Example:

     CREATE TABLE Orders (
         OrderID INT PRIMARY KEY,
         CustomerID INT,
         FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID)
     );
     

4. Common Pitfalls:

   • Lossy Decomposition: Forgetting to check for losslessness can lead to incorrect queries (e.g., missing tuples after joins).
   • Redundant FDs: Not preserving all functional dependencies can cause anomalies (e.g., updates not propagating correctly).
   • NULL Values: Primary keys cannot contain NULL; use default values or surrogate keys (e.g., auto-incremented IDs) if natural keys allow NULL.

5. Real-World Scenarios:

   • Exams often ask about banking systems (e.g., decomposing Accounts and Transactions) or e-commerce (e.g., Customers, Products, Orders).
   • Relate decomposition to normalization levels (e.g., "Decompose this relation to 3NF").
   • Use past exam questions as templates:
     • Given a relation, decompose it into 3NF.
     • Given decomposed tables, write SQL to create them with proper keys.
     • Given a scenario (e.g., university database), identify keys and propose a decomposition.