Relational Model & Algebra: Tables, Queries & Math

TAKEAWAYS:

• The relational model stores data as tables (relations) with rows (tuples) and columns (attributes), enforcing strict rules like atomicity and uniqueness.
• Relational algebra is a set of 12 operations (e.g., SELECT, JOIN) to query and manipulate tables mathematically, not like SQL.
• Primary keys uniquely identify tuples, while foreign keys enforce referential integrity between tables (e.g., linking Student and Enrollment).
• Normalization (covered later) reduces redundancy by applying functional dependencies (e.g., City should not repeat for all students).
• Cartesian products (cross joins) are the foundation of joins but must be filtered to avoid useless data.
• Relational algebra vs. SQL: Algebra is theoretical (used in optimizers), while SQL is practical (what you write).

1. The Relational Data Model: Tables as the Foundation

The relational model represents data as tables (called relations), where:

• Each table has a name (e.g., Student, Course).
• Columns are attributes (e.g., SID, SName) with a fixed domain (e.g., VARCHAR(50)).
• Rows are tuples (records) with the same structure.
• Keys enforce uniqueness:
  • Primary key (PK): Uniquely identifies tuples (e.g., SID in Student).
  • Foreign key (FK): References a PK in another table (e.g., SID in Enrollment links to Student).

Key Properties of Relations

A valid relation must satisfy:

1. Atomicity: Each attribute holds a single value (no nested tables or arrays).
2. Ordered columns: Columns have a fixed order (though this is often ignored in practice).
3. No duplicate tuples: Identical rows are not allowed (unless explicitly modeled).
4. No implicit ordering: Rows are unordered unless specified (e.g., by ORDER BY in SQL).

Example: Student-Course Database

Consider these tables:

erDiagram
    STUDENT ||--o{ ENROLLMENT : takes
    COURSE ||--o{ ENROLLMENT : enrolls_in
    STUDENT {
        string SID PK
        string SName
        string City
        string Faculty
    }
    COURSE {
        string CID PK
        string CName
        int Credits
    }
    ENROLLMENT {
        string SID FK
        string CID FK
        string Grade
    }

• Primary keys: SID (Student), CID (Course).
• Foreign keys: SID in Enrollment → Student(SID); CID in Enrollment → Course(CID).
• Referential integrity: No Enrollment record can reference a non-existent Student or Course.

Why this matters:

• eSewa’s transaction tables use this structure to link users (User), accounts (Account), and transactions (Transaction). The Transaction table has FKs to User and Account to track who paid what.
• Daraz’s order system stores Order, Customer, and Product as separate tables with FKs to avoid duplicate customer/product data.

2. Functional Dependencies: The Math Behind Tables

A functional dependency (FD) describes how one attribute determines another. Formally:

X → Y means that if two tuples have the same value for X, they must also have the same value for Y.

Example: Student Table

In Student(SID, SName, City, Faculty):

• SID → SName, City, Faculty (a student’s ID uniquely determines their name, city, and faculty).
• Faculty → City? No, because multiple faculties can share the same city (e.g., Kathmandu has CS, Eng, and Med faculties).

Closure and Determinants

• Closure: Given X → Y, the closure of X (denoted X+) includes all attributes functionally dependent on X.
  • Example: If SID → SName and SName → City (unlikely, but possible), then SID+ = {SName, City}.
• Minimal cover: A set of FDs with no redundant dependencies (used in normalization).

Worked Example: Finding FDs

Given EMPLOYEE(Ssn, Fname, Minit, Lname, Bdate, Address, Sex, Salary, Super_ssn, Dno):

1. Ssn → Fname, Minit, Lname, Bdate, Address, Sex, Salary, Super_ssn, Dno (PK).
2. Dno → Dname (from DEPARTMENT table, not shown here).
3. Super_ssn → Ssn (a supervisor’s SSN references an employee’s SSN).

Ssn → Fname, Minit, Lname, Bdate, Address, Sex, Salary, Super_ssn, Dno
Super_ssn → Ssn
Dno → Dname

Real-world tie:

• NEPSE’s stock trading system uses FDs to ensure each Trade record has a valid Stock (e.g., StockCode → StockName) and a valid Trader (e.g., TraderID → TraderName). If TraderID is missing, the trade is invalid.

3. Relational Algebra: The 12 Operations

Relational algebra is a set-based language for querying tables. It does not use SQL syntax but is the foundation for query optimization.

Core Operations (5)

Join Operations (5)

Aggregation (2)

| Operation      | Symbol | Example                          | Output Description                          |
|----------------|--------|----------------------------------|---------------------------------------------|
| Select         | σ      | σ(Salary > 50k)(EMPLOYEE)        | Employees earning >50k                      |
| Project        | π      | π(SName)(EMPLOYEE)               | List of employee names                      |
| Natural Join   | ⋈      | EMPLOYEE ⋈ DEPARTMENT            | Employees with their department names       |

Worked Example: Retrieving "John Smith’s" Department

Given:

• EMPLOYEE(Ssn, Fname, Lname, Dno)
• DEPARTMENT(Dno, Dname)

Goal: Find Lname, Dno, Dname for "John Smith" (assuming Fname = "John", Lname = "Smith").

Steps:

1. Select John Smith’s records: σ(Fname = "John" ∧ Lname = "Smith")(EMPLOYEE) Output: (Ssn=123, Fname=John, Lname=Smith, Dno=5)

2. Join with DEPARTMENT: (σ(Fname = "John" ∧ Lname = "Smith")(EMPLOYEE)) ⋈ DEPARTMENT Output:

   | Ssn | Fname | Lname | Dno | Dname   |
   |-----|-------|-------|-----|---------|
   | 123 | John  | Smith | 5   | HR      |
   

Real-world tie:

• Pathao’s driver assignment system uses a similar join to match drivers (Driver) to available rides (Ride) based on location (Location). The query would be: σ(Location = "Kathmandu" ∧ Status = "Available")(Driver) ⋈ Ride

4. Relational Algebra vs. SQL

Why this matters:

• Google’s BigQuery uses relational algebra under the hood to optimize SQL queries before execution. For example, it might rewrite your SQL into a more efficient algebra expression.

5. Normalization: Avoiding Redundancy (Preview)

While not part of Unit 4, normalization is closely tied to relational algebra. Normal forms ensure data integrity by eliminating redundancy using FDs.

Example of 1NF Violation:

erDiagram
    ORDERS {
        int OrderID PK
        string CustomerName
        string Products[] // Repeating group (violates 1NF)
    }
    ORDERS_1NF {
        int OrderID PK
        string CustomerName
    }
    ORDER_ITEMS {
        int OrderID FK
        string ProductName
    }

1NF Violation (left) vs. Fixed (right) Fixed (2NF):

erDiagram
    ORDERS {
        int OrderID PK
        string CustomerName
    }
    ORDER_ITEMS {
        int OrderID FK
        string ProductName
    }

Real-world tie:

• Khalti’s payment processing avoids redundancy by normalizing tables like Transaction, User, and Merchant separately. If User data were duplicated in every Transaction, updates (e.g., changing a user’s email) would require patching every record.

6. Exam Tip: How This Unit is Tested

1. SQL vs. Algebra:

   • You may be given a relational algebra expression and asked to write the equivalent SQL (or vice versa).
   • Example: Convert π(SName, Salary)(σ(Salary > 50000)(EMPLOYEE)) to SQL:

     SELECT SName, Salary
     FROM EMPLOYEE
     WHERE Salary > 50000;
     

2. Joins and FDs:

   • Expect questions on how to map ER diagrams to relations, especially 1:N and N:M relationships.
   • Example: Map Student takes Course (N:M) to a junction table Enrollment(SID, CID, Grade).

3. Functional Dependencies:

   • Given a table, identify all FDs and determine the closure of a set of attributes.
   • Example: For Student(SID, SName, City, Faculty), list all FDs and compute City+ if Faculty → City.

4. Relational Algebra Queries:

   • Solve problems using algebra operations (e.g., "Find all employees who earn more than their supervisor").
   • Example:

5. Real-world Scenarios:

   • Tie concepts to Nepali examples (e.g., "How would you model Pathao’s driver-ride matching using joins?").
   • Example answer:

     "Pathao uses a natural join between Driver (with Location and Status) and Ride (with Location and RideID) to match available drivers to new rides. The join condition is Driver.Location = Ride.Location ∧ Driver.Status = "Available". This ensures only relevant drivers are considered."

6. Common Pitfalls:

   • Cartesian products: Forgetting to filter after a cross join (e.g., EMPLOYEE × DEPARTMENT returns 1000×20 = 20,000 rows!).
   • Duplicate tuples: π removes duplicates, but σ does not.
   • Key constraints: Always check if a join preserves referential integrity (e.g., no orphaned Enrollment records).

Given:
EMPLOYEE(Ssn, Fname, Lname, Dno)
DEPARTMENT(Dno, Dname)

Find: Employee names and department names where the employee earns more than the department average salary.

Solution steps:

1. Compute department average salary: γ(AVG(Salary), Dno)(EMPLOYEE).
2. Join with EMPLOYEE and filter: σ(Salary > γ(AVG(Salary), Dno)(EMPLOYEE).Salary)(EMPLOYEE ⋈ DEPARTMENT).

Final Summary Table

Exam Tip:

• Always assume tables are in 1NF unless told otherwise.
• Draw the tables when solving join problems—visualizing helps avoid Cartesian explosions.
• Practice converting SQL to algebra (and vice versa) to build intuition.
• For FD questions, list all obvious dependencies first (e.g., PK → all attributes).