Relational Algebra and Operations

Relational algebra is a procedural query language consisting of operations that take one or two relations as input and produce a new relation as output.

Fundamental Operations:

1. Selection (σ): Selects rows that satisfy a condition
σcondition(Relation)

2. Projection (π): Selects specific columns
πcolumns(Relation)

3. Union (∪): Combines tuples from two relations
R ∪ S

4. Set Difference (−): Tuples in R but not in S
R − S

5. Cartesian Product (×): All combinations of tuples
R × S

6. Rename (ρ): Renames relation or attributes
ρnew_name(Relation)

Derived Operations:

7. Intersection (∩): R ∩ S = R − (R − S)

8. Join (⋈): Combines related tuples from two relations

• Natural Join (⋈): Equi-join on common attributes
• Theta Join (⋈θ): Join with arbitrary condition
• Equi-join: Join with equality condition
• Outer Joins: Include unmatched tuples
  • Left Outer Join (⟕): All from left, matched from right
  • Right Outer Join (⟖): All from right, matched from left
  • Full Outer Join (⟗): All from both

9. Division (÷): R ÷ S finds tuples in R that match all tuples in S

Properties:

Closure Property: Result of operation is also a relation

Composability: Operations can be nested
πname(σsalary>50000(Employee))

EXAMPLE SCHEMA:

Employee Table:

EmpID	Name	DeptID	Salary
101	Alice	10	60000
102	Bob	20	55000
103	Charlie	10	70000
104	Diana	30	50000

Department Table:

DeptID	DeptName	Location
10	IT	NYC
20	HR	LA
30	Sales	Chicago

Project Table:

ProjID	ProjName	DeptID
P1	Alpha	10
P2	Beta	20

EXAMPLE 1: SELECTION

Query: Find employees with salary > 55000

Relational Algebra:
σsalary>55000(Employee)

Result:

EmpID	Name	DeptID	Salary
101	Alice	10	60000
103	Charlie	10	70000

SQL:
SELECT * FROM Employee WHERE Salary > 55000;

EXAMPLE 2: PROJECTION

Query: Get employee names and salaries

Relational Algebra:
πName,Salary(Employee)

Result:

Name	Salary
Alice	60000
Bob	55000
Charlie	70000
Diana	50000

SQL:
SELECT Name, Salary FROM Employee;

EXAMPLE 3: COMBINED SELECTION AND PROJECTION

Query: Names of employees in Dept 10

Relational Algebra:
πName(σDeptID=10(Employee))

Result:

Name
Alice
Charlie

SQL:
SELECT Name FROM Employee WHERE DeptID = 10;

EXAMPLE 4: UNION

Query: All IDs from Employee and Department tables

Relational Algebra:
πEmpID(Employee) ∪ πDeptID(Department)

Note: Must rename for union-compatibility
ρ(ID)(πEmpID(Employee)) ∪ ρ(ID)(πDeptID(Department))

SQL:
SELECT EmpID AS ID FROM Employee
UNION
SELECT DeptID AS ID FROM Department;

EXAMPLE 5: SET DIFFERENCE

Query: Department IDs that have no employees

Relational Algebra:
πDeptID(Department) − πDeptID(Employee)

Result:

DeptID
(None in this example, all depts have employees)

SQL:
SELECT DeptID FROM Department
EXCEPT
SELECT DISTINCT DeptID FROM Employee;

EXAMPLE 6: CARTESIAN PRODUCT

Query: All combinations of employees and projects

Relational Algebra:
Employee × Project

Result: 4 employees × 2 projects = 8 tuples

SQL:
SELECT * FROM Employee, Project;
-- or
SELECT * FROM Employee CROSS JOIN Project;

EXAMPLE 7: NATURAL JOIN

Query: Employees with their department names

Relational Algebra:
Employee ⋈ Department

Result:

EmpID	Name	DeptID	Salary	DeptName	Location
101	Alice	10	60000	IT	NYC
102	Bob	20	55000	HR	LA
103	Charlie	10	70000	IT	NYC
104	Diana	30	50000	Sales	Chicago

SQL:
SELECT *
FROM Employee
NATURAL JOIN Department;
-- or explicitly
SELECT e.*, d.DeptName, d.Location
FROM Employee e
JOIN Department d ON e.DeptID = d.DeptID;

EXAMPLE 8: THETA JOIN

Query: Employees in departments located in NYC or LA

Relational Algebra:
Employee ⋈Location IN ('NYC','LA') Department

SQL:
SELECT e.*
FROM Employee e
JOIN Department d ON e.DeptID = d.DeptID
WHERE d.Location IN ('NYC', 'LA');

EXAMPLE 9: LEFT OUTER JOIN

Assume we add a department with no employees:

Department Table (updated):

DeptID	DeptName	Location
10	IT	NYC
20	HR	LA
30	Sales	Chicago
40	Finance	Boston

Query: All departments with their employees (including depts with no employees)

Relational Algebra:
Department ⟕ Employee

Result:

DeptID	DeptName	Location	EmpID	Name	Salary
10	IT	NYC	101	Alice	60000
10	IT	NYC	103	Charlie	70000
20	HR	LA	102	Bob	55000
30	Sales	Chicago	104	Diana	50000
40	Finance	Boston	NULL	NULL	NULL

SQL:
SELECT *
FROM Department d
LEFT OUTER JOIN Employee e ON d.DeptID = e.DeptID;

EXAMPLE 10: DIVISION

Enrollment Table:

StudentID	CourseID
S1	C1
S1	C2
S1	C3
S2	C1
S2	C3
S3	C1
S3	C2
S3	C3

Required_Courses Table:

CourseID
C1
C2
C3

Query: Find students enrolled in ALL required courses

Relational Algebra:
πStudentID,CourseID(Enrollment) ÷ πCourseID(Required_Courses)

Result:

StudentID
S1
S3

SQL (using double negation):
SELECT DISTINCT StudentID
FROM Enrollment e1
WHERE NOT EXISTS (
SELECT CourseID
FROM Required_Courses
WHERE CourseID NOT IN (
SELECT CourseID
FROM Enrollment e2
WHERE e2.StudentID = e1.StudentID
)
);

EXAMPLE 11: COMPLEX QUERY

Query: Names and salaries of IT department employees earning > 55000

Relational Algebra:
πName,Salary(σDeptName='IT' ∧ Salary>55000(Employee ⋈ Department))

Optimized (push selection down):
πName,Salary(σSalary>55000(Employee) ⋈ σDeptName='IT'(Department))

Result:

Name	Salary
Alice	60000
Charlie	70000

SQL:
SELECT e.Name, e.Salary
FROM Employee e
JOIN Department d ON e.DeptID = d.DeptID
WHERE d.DeptName = 'IT' AND e.Salary > 55000;

EXAMPLE 12: QUERY OPTIMIZATION

Original Query:
πName(σDeptName='IT'(Employee × Department))

Problems:

1. Cartesian product creates huge intermediate result
2. Selection after product

Optimized Query:
πName(σDeptID=DeptID(σSalary>55000(Employee) × σDeptName='IT'(Department)))

Better:
πName(σSalary>55000(Employee) ⋈ σDeptName='IT'(Department))

Best:
πName(σSalary>55000(Employee ⋈ σDeptName='IT'(Department)))

PRACTICAL APPLICATIONS:

1. Database Query Optimization:

Understanding relational algebra helps optimize SQL queries.

Bad Query:
SELECT Name
FROM Employee, Department
WHERE Employee.DeptID = Department.DeptID
AND Department.DeptName = 'IT'
AND Salary > 55000;

Execution Plan:

1. Cartesian product (expensive!)
2. Filter conditions
3. Project Name

Better Query (optimizer does this):
SELECT e.Name
FROM (SELECT * FROM Employee WHERE Salary > 55000) e
JOIN (SELECT * FROM Department WHERE DeptName = 'IT') d
ON e.DeptID = d.DeptID;

2. Query Translation:

SQL → Relational Algebra → Optimized Algebra → Execution Plan

3. Understanding Join Algorithms:

Different join strategies implement ⋈:

• Nested Loop Join: Iterate outer, for each tuple iterate inner
• Hash Join: Hash one relation, probe with other
• Sort-Merge Join: Sort both, merge

4. Design Query Processors:

Relational algebra forms basis of query processors in DBMS.

5. Verify Query Correctness:

Two SQL queries equivalent if their relational algebra expressions equivalent.

CONVERSION EXAMPLES:

SQL to Relational Algebra:

SQL:
SELECT Name, Salary
FROM Employee
WHERE DeptID = 10 AND Salary > 60000;

Relational Algebra:
πName,Salary(σDeptID=10 ∧ Salary>60000(Employee))

SQL:
SELECT e.Name, d.DeptName
FROM Employee e
JOIN Department d ON e.DeptID = d.DeptID
WHERE e.Salary > 55000;

Relational Algebra:
πName,DeptName(σSalary>55000(Employee ⋈ Department))

Relational Algebra to SQL:

πName(σSalary>(SELECT AVG(Salary) FROM Employee)(Employee))

SQL:
SELECT Name
FROM Employee
WHERE Salary > (SELECT AVG(Salary) FROM Employee);

TOOLS FOR PRACTICE:

1. RelaX (Web-based):

   • Visual relational algebra
   • Execute operations
   • See results

2. RA (Relational Algebra Interpreter):

   • Command-line tool
   • Text-based queries

3. Database Textbook Simulators:

   • Many textbooks provide online tools

INTERVIEW QUESTIONS:

1. Explain difference between natural join and theta join
2. Why is projection not commutative?
3. How to express intersection using other operations?
4. What is the result cardinality of R × S?
5. Give SQL for relational division
6. Why push selections down in query optimization?
7. Explain left vs right vs full outer join with examples