Relational Model & Normalization: Tables, Keys, and Clean Data

TAKEAWAYS:

• A relation is a table with rows (tuples) and columns (attributes) that enforces strict rules (atomicity, no duplicate rows).
• Primary keys uniquely identify records, while foreign keys link tables (e.g., EmpID in employees → DeptID in departments).
• Normalization (1NF–BCNF) removes redundancy by breaking tables into smaller, well-structured ones (e.g., splitting Author and Book tables).
• Denormalization is sometimes used for performance (e.g., eSewa’s transaction logs) but risks redundancy.
• Functional dependencies (e.g., EmpID → Salary) guide normalization steps.
• Lossless join and dependency preservation ensure data integrity after normalization.

1. The Relational Model: Tables as Data Structures

The relational model treats data as tables (relations) with rows (tuples) and columns (attributes). Unlike spreadsheets, relations enforce rules:

• Atomicity: Each cell holds a single value (no lists or nested tables).
• No duplicate rows: Identical tuples are merged.
• Ordered columns: Columns have a fixed schema (e.g., employees(EmpID, Name, Salary)).

Key Concepts

• Relation Schema: Defines column names and data types (e.g., Book(BID: INT, Title: VARCHAR, Price: DECIMAL)).
• Relation Instance: The actual data at a moment (e.g., 5 books in the Book table).
• Domain: The set of allowed values for an attribute (e.g., Price ∈ [0, 1000]).

Example: HR Database

Consider these tables (primary keys underlined):

employees (EmpID, FirstName, LastName, Salary, DeptID)
departments (DeptID, DeptName, LocationID)
locations (LocationID, StreetAddress, PostalCode, City)

• EmpID is the primary key for employees.
• DeptID in employees is a foreign key referencing departments(DeptID).

Visual: Relation Schema vs. Instance

Why this matters: Foreign keys enforce referential integrity (e.g., no EmpID can reference a non-existent DeptID).

2. Keys in Relations

Keys ensure data integrity and enable efficient queries.

Types of Keys

Worked Example: Identifying Keys

Given:

Publishes (AID, BID, publishedDate)

• Primary Key: (AID, BID) (since one author can publish multiple books, and one book can have multiple publishing records).
• Foreign Keys: AID → Author(AID), BID → Book(BID).

Visual: Composite Key in Publishes

Real-world tie: In Daraz’s inventory system, the (ProductID, WarehouseID) composite key tracks stock across multiple warehouses.

3. Normalization: Eliminating Redundancy

Normalization splits tables to remove anomalies (insert/update/delete issues) caused by redundancy.

Normal Forms (NFs)

Step-by-Step Normalization

Problem Table (Violates 1NF, 2NF, 3NF):

Author (AID, A_Name, Age, Address, country, Book_Titles)

• Issue: Book_Titles is a repeating group (violates 1NF).
• Step 1 (1NF): Split into Author and Book tables.

  Author (AID, A_Name, Age, Address, country)
  Book (BID, B_Name, Price)
  

• Step 2 (2NF): No partial dependencies (e.g., AID → A_Name is fine).
• Step 3 (3NF): Check transitive dependencies. If country depends on AID (e.g., via Address), it’s fine. If not, split further.

Final Normalized Schema:

(Shows a before/after table split for Author and Book.)

Real-world tie: eSewa’s Transaction Logs eSewa stores transactions in a normalized schema:

• Transactions(TransID, UserID, Amount, Timestamp)
• Users(UserID, Name, Email)
• Merchants(MerchantID, Name, BankAccount) Why? Normalization prevents duplicate user data and ensures fast lookups by UserID.

4. Functional Dependencies and Closure

Functional dependencies (FDs) define how attributes relate:

• FD: X → Y means X determines Y uniquely.
• Closure: Given a set of FDs, compute all attributes determined by a candidate key.

Example: Finding FDs in departments

Assume:

• DeptID → DeptName (a department has one name).
• DeptID → LocationID (a department is in one location).
• LocationID → City (a location has one city).

Closure of DeptID: DeptID → DeptName → LocationID → City. Thus, DeptID is a superkey (but not necessarily a candidate key unless no other attributes depend on it).

Visual: Functional Dependency Graph

graph TD
    DeptID --> DeptName
    DeptID --> LocationID
    LocationID --> City

Exam tip: For BCNF, check if every determinant (left side of →) is a candidate key.

5. Denormalization: When to Break Normalization

Normalization isn’t always optimal:

• Pros of Denormalization:
  • Faster reads (e.g., eSewa’s "Quick Pay" feature denormalizes user balances for speed).
  • Simpler queries (e.g., Daraz’s product catalog avoids joins).
• Cons:
  • Update anomalies: Changing data in one place may require updates elsewhere.
  • Storage overhead: Duplicate data consumes more space.

Example: Denormalized Author Table

When to use it: For read-heavy systems (e.g., YouTube’s video metadata, which is rarely updated but frequently queried).

(Bar chart showing query speed vs. storage cost.)

6. Advanced Topics: Join Dependencies and Lossless Joins

• Join Dependency: A relation can be split into tables that can be reconstructed losslessly via joins. Example: Publishes(AID, BID, publishedDate) can be split into Author(AID) and Book(BID) with a join on (AID, BID).
• Lossless Join: A join preserves all original tuples. Condition: The intersection of the two tables must be a superkey of at least one table.

Worked Example: Lossless Join Check

Split Publishes(AID, BID, publishedDate) into:

• Author(AID, publishedDate)
• Book(BID, publishedDate)

Is the join lossless? No, because the intersection (AID, BID) is not a superkey of either table. We must include both AID and BID in both tables to preserve data.

Visual: Lossless Join Condition

Real-world tie: Ncell’s call records are stored in normalized tables (Call(AID, BID, Timestamp)) to avoid losing data when splitting by AID (user) or BID (bill ID).

7. Comparison: Normalized vs. Denormalized Architectures

(Pie chart showing 70% normalized for OLTP, 30% denormalized for OLAP.)

In the Real World

1. eSewa’s Transaction Processing

   • Idea: Uses normalized tables (Users, Transactions, Merchants) to ensure no duplicate user data and fast lookups by UserID.
   • Why? Prevents anomalies when users update their email or balance.

2. Daraz’s Inventory Management

   • Idea: Denormalized product tables (e.g., Product(ProductID, Name, Price, Stock[Warehouse1, Warehouse2])) for faster "Add to Cart" queries.
   • Tradeoff: Stock updates must sync across warehouses manually.

3. NEPSE’s Stock Market Data

   • Idea: Normalized schema (Stocks(StockID, Symbol, Price), Trades(TradeID, StockID, Quantity, Time)) to track trades without redundancy.
   • Real Example: When StockID = "NCL" (Nepal Chemicals), all trades are linked via StockID without duplication.

Worked Example: Daraz Order Queue Scenario: Daraz receives 100 orders for a best-selling phone. The Orders table is normalized:

Orders(OrderID, UserID, ProductID, Quantity, Status)
Products(ProductID, Name, Price, Stock)

• Problem: If Stock is denormalized in Orders, updating stock after each order is slow.
• Solution: Use a normalized Products table and update Stock atomically via transactions.

Exam Tip

• Focus on these 3 things:

  1. Normalization steps: Always show how a table violates 1NF/2NF/3NF and how to fix it.
     • Example: Start with a table like Author(AID, Name, Books) (repeating group → violates 1NF).
     • Split into Author(AID, Name) and Book(AID, Title).
  2. Key identification: For any table, identify primary, foreign, and candidate keys.
     • Example: In Publishes(AID, BID, Date), (AID, BID) is the PK if one author can publish one book multiple times.
  3. Join dependencies: Explain when a join is lossless and why.
     • Example: Splitting Publishes into Author and Book is not lossless unless you include both AID and BID.

• Common mistakes to avoid:

  • Forgetting to include all attributes in functional dependencies (e.g., missing publishedDate in Publishes).
  • Assuming denormalization is always bad—mention read-heavy systems like analytics.
  • Not checking for transitive dependencies in 3NF (e.g., DeptID → ManagerID → ManagerName).

• Formula to remember: For BCNF, if a table has a functional dependency X → A where X is not a candidate key, it violates BCNF. Example: In departments(DeptID, DeptName, ManagerName), if DeptID → ManagerName and DeptID is the PK, but ManagerName doesn’t determine DeptID, it violates BCNF.

Final Visual: Normalization Cheat Sheet

mindmap
  root((Normalization))
    1NF
      Atomicity
      No repeating groups
    2NF
      Remove partial dependencies
      PK must be composite or single attribute
    3NF
      Remove transitive dependencies
      Non-key → non-key must not exist
    BCNF
      Every determinant must be a candidate key