Relational Algebra: Operations, Expressions & Query Design

1. Introduction to Relational Algebra

Relational algebra is a collection of set-based operations used to manipulate relations (tables) in a relational database. Unlike procedural languages, relational algebra is declarative: it specifies what data is needed rather than how to retrieve it. These operations form the backbone of query processing in databases like MySQL, PostgreSQL, and Oracle.

Key Concepts

• Relations: Tables with rows (tuples) and columns (attributes).
• Operations: Set-based operations like union, intersection, difference, and relational-specific operations like select, project, join.
• Expressions: Combinations of operations to express complex queries.

---

2. Basic Relational Algebra Operations

Relational algebra consists of five categories of operations:

A. Unary Operations (Single Relation Input)

1. Select (σ, "sigma"): Filters tuples based on a condition.

   • Syntax: σ<condition>(relation)
   • Example: Select employees earning >50,000 from the Employee table.

     sequenceDiagram
         participant E as Employee(Relation)
         participant S as σ(salary > 50000)
         E->>S: All tuples
         S-->>E: Tuples where salary > 50000

2. Project (π, "pi"): Extracts specified columns.

   • Syntax: π<attributes>(relation)
   • Example: Get person_name and salary from Employee.

     sequenceDiagram
         participant E as Employee(Relation)
         participant P as π(person_name, salary)
         E->>P: All tuples
         P-->>E: Tuples with only person_name and salary

3. Rename (ρ, "rho"): Renames a relation or attributes.

   • Syntax: ρ<new_name>(relation)
   • Example: Rename Employee to Staff.

     sequenceDiagram
         participant E as Employee(Relation)
         participant R as ρ(Staff)
         E->>R: All tuples
         R-->>E: Relation renamed to Staff

B. Binary Operations (Two Relations Input)

1. Cartesian Product (×): Combines every tuple of the first relation with every tuple of the second.

   • Syntax: R × S
   • Example: Combine Employee and Company relations.

     sequenceDiagram
         participant E as Employee(Relation)
         participant C as Company(Relation)
         participant CP as ×
         E->>CP: All tuples
         C->>CP: All tuples
         CP-->>E: All possible combinations

2. Union (∪): Combines tuples from two relations with identical schemas.

   • Syntax: R ∪ S
   • Example: Merge two Customer tables from different branches.

3. Set Difference (−): Returns tuples in the first relation but not in the second.

   • Syntax: R − S
   • Example: Find employees not in the Works relation.

4. Intersection (∩): Returns tuples present in both relations.

   • Syntax: R ∩ S
   • Example: Find common customers in two sales tables.

C. Relational-Specific Operations

1. Join (⋈): Combines tuples from two relations based on a condition (often a key match).

   • Syntax: R ⋈<condition> S

   • Example: Join Employee and Works on person_name.

     sequenceDiagram
         participant E as Employee(Relation)
         participant W as Works(Relation)
         participant J as ⋈(person_name)
         E->>J: All tuples
         W->>J: All tuples
         J-->>E: Tuples joined on person_name

   • Types of Joins:

     • Natural Join: Joins on common attribute names (no condition needed).
     • Equi-Join: Joins on equality condition (e.g., E.employee_id = W.employee_id).
     • Theta-Join: Joins on any condition (e.g., E.salary > W.min_salary).

2. Division (÷): Finds tuples in one relation for which all tuples in another relation satisfy a condition.

   • Syntax: R ÷ S
   • Example: Find departments where every employee earns >30,000.

     sequenceDiagram
         participant E as Employee(Relation)
         participant D as Department(Relation)
         participant DIV as ÷
         E->>DIV: All employee tuples
         D->>DIV: All department tuples
         DIV-->>E: Departments where all employees earn >30,000

---

3. Worked Example: Relational Algebra Query

Given Relations:

• Employee(person_name, street, city)
• Works(person_name, company_name, salary)
• Company(company_name, city)

Query: Find the names of employees who work for companies located in Kathmandu and earn more than 40,000.

Step-by-Step Solution:

1. Select employees earning >40,000:

   sequenceDiagram
       participant E as Employee
       participant S1 as σ(salary > 40000)
       E->>S1: All tuples
       S1-->>E: Tuples with salary > 40000

   Expression: σ(salary > 40000)(Works)

2. Join with Company to find Kathmandu-based companies:

Expression: σ(salary > 40000)(Works) ⋈ (company_name, city = "Kathmandu") Company

3. Project only person_name:

   sequenceDiagram
       participant J as Result from step 2
       participant P as π(person_name)
       J->>P: All joined tuples
       P-->>J: Only person_name

   Final Expression:

   π(person_name)(
       σ(salary > 40000)(Works) ⋈ (company_name, city = "Kathmandu") Company
   )
   

---

4. Comparison of Relational Algebra and SQL

---

5. Advantages and Disadvantages

Advantages:

• Mathematical Foundation: Provides a rigorous way to design and analyze queries.
• Optimization: Helps in rewriting queries for better performance (e.g., avoiding Cartesian products).
• Theoretical Basis: Used in database design, normalization, and query optimization.

Disadvantages:

• Complexity: Harder to read and write compared to SQL.
• No Direct Execution: Must be translated into SQL or another language for execution.
• Limited Practical Use: Rarely used directly by developers; more for academic and theoretical purposes.

---

6. Real-World Applications

In the Real World

1. eSewa/Khalti (Payment Gateways)

   • Idea: Join Operations When a user initiates a payment, eSewa/Khalti joins the User table (to verify credentials) with the Transaction table (to record the payment) using the user_id as the join key. This ensures that only valid users can process transactions.

     sequenceDiagram
         participant U as User(Relation)
         participant T as Transaction(Relation)
         participant J as ⋈(user_id)
         U->>J: Valid user tuples
         T->>J: Transaction tuples
         J-->>U: Authorized transaction

2. Daraz (E-Commerce Platform)

   • Idea: Project and Select Operations When a customer searches for products, Daraz uses π(product_id, name, price) to project only the relevant attributes from the Inventory table and σ(price < 1000) to filter products under a certain price range.

     sequenceDiagram
         participant I as Inventory(Relation)
         participant S as σ(price < 1000)
         participant P as π(product_id, name, price)
         I->>S: All inventory tuples
         S-->>P: Tuples with price < 1000
         P-->>I: Projected attributes

3. NEPSE (Stock Exchange)

   • Idea: Division Operation To find brokers who have traded in all listed companies, NEPSE uses division to ensure that a broker’s transaction history includes every company in the Company table.

     sequenceDiagram
         participant B as Broker(Relation)
         participant C as Company(Relation)
         participant DIV as ÷
         B->>DIV: All broker transactions
         C->>DIV: All companies
         DIV-->>B: Brokers who traded in all companies

---

7. Query Optimization Using Relational Algebra

Optimizing relational algebra expressions is crucial for performance. For example:

• Avoid Cartesian Products: Replace R × S with explicit joins where possible.
• Use Select Before Join: Filter data early to reduce the size of relations before joining.
• Rewrite Joins: Convert expensive joins (e.g., nested loops) into hash joins or merge joins if supported.

Example Optimization: Original (inefficient):

π(person_name)(
    Employee ⋈ Works
)

Optimized (efficient):

π(person_name)(
    σ(person_name ∈ Works)(Employee)
)

This ensures that only employees who work somewhere are considered before joining.

---

8. Exam Tip

• Focus on Operations: Know the syntax and semantics of each operation (select, project, join, etc.).
• Worked Examples: Practice converting real-world queries into relational algebra expressions.
• Optimization: Understand how to rewrite expressions for efficiency (e.g., push down selects).
• SQL Conversion: Be able to translate relational algebra into SQL and vice versa.
• Common Pitfalls:
  • Avoid Cartesian products unless necessary.
  • Ensure relations have compatible schemas for operations like union or join.
  • Always specify primary keys and foreign keys in your examples.

Past Exam Question Practice: For the given relations:

• Employee(person_name, street, city)
• Works(person_name, company_name, salary)
• Company(company_name, city)

Write a relational algebraic expression to find the names of employees who work for companies in Kathmandu and earn more than 40,000. Answer:

π(person_name)(
    σ(salary > 40000)(Works) ⋈ (company_name, city = "Kathmandu") Company
)