Relational Algebra - Complete Reference

Relational algebra is a procedural query language that defines operations to manipulate relations (tables) in a relational database. It provides a mathematical foundation for database operations and serves as the theoretical basis for SQL.

1. Unary Operations

1.1 Selection (σ - Sigma)

Symbol: σ_condition(R)

Purpose: Selects tuples (rows) that satisfy a given condition

Syntax: σ_condition(Relation)

Conditions:

• Uses comparison operators: =, ≠, <, >, ≤, ≥
• Logical operators: ∧ (AND), ∨ (OR), ¬ (NOT)
• Can combine multiple conditions

Example Tables:

Original Employee Table:

Selection Examples:

1. σ_{age > 25}(Employee) - Select employees older than 25:

   EID	Name	Age	Dept	Salary
   101	John	28	CS	55000
   103	Bob	35	CS	65000

2. σ_{dept = ‘CS’ ∧ salary > 50000}(Employee) - Select CS employees with salary > 50000:

   EID	Name	Age	Dept	Salary
   101	John	28	CS	55000
   103	Bob	35	CS	65000

3. σ_{name = ‘John’ ∨ name = ‘Jane’}(Employee) - Select employees named John or Jane:

   EID	Name	Age	Dept	Salary
   101	John	28	CS	55000
   102	Jane	24	IT	45000

1.2 Projection (Π - Pi)

Symbol: Π_attributes(R)

Purpose: Selects specific columns from a relation and eliminates duplicates

Syntax: Π_{A₁, A₂, …, Aₙ}(Relation)

Conditions:

• Selected attributes must exist in the relation
• Automatically removes duplicate tuples
• Order of attributes in result follows the order specified

Projection Examples:

Original Employee Table:

1. Π_{name, age}(Employee) - Project name and age columns:

   Name	Age
   John	28
   Jane	24
   Bob	35
   Alice	22

2. Π_{dept, salary}(Employee) - Project department and salary:

   Dept	Salary
   CS	55000
   IT	45000
   CS	65000
   HR	40000

3. Π_dept(Employee) - Project only department (duplicates removed):

   Dept
   CS
   IT
   HR

1.3 Rename (ρ - Rho)

Symbol: ρ_{new_name/old_name}(R) or ρ_{S(A₁, A₂, …, Aₙ)}(R)

Purpose: Renames relations and/or attributes

Syntax Options: ρ_{new_attr/old_attr}(R) # Rename attribute ρ_S(R) # Rename relation to S ρ_{S(A₁, A₂, …, Aₙ)}(R) # Rename relation and all attributes

Rename Examples:

Original Employee Table:

1. ρ_{emp_name/name}(Employee) - Rename ’name’ attribute to ’emp_name’:

   EID	emp_name	Age	Dept
   101	John	28	CS
   102	Jane	24	IT

2. ρ_Staff(Employee) - Rename Employee relation to Staff: Staff Table:

   EID	Name	Age	Dept
   101	John	28	CS
   102	Jane	24	IT

3. ρ_{E(eid, ename, age, department)}(Employee) - Rename relation and all attributes: E Table:

   eid	ename	age	department
   101	John	28	CS
   102	Jane	24	IT

2. Combining Operations

3. Set Theory Operations

3.1 Union (∪)

Symbol: R ∪ S

Purpose: Combines tuples from two relations, eliminating duplicates

Conditions (Union Compatibility):

• Both relations must have the same number of attributes
• Corresponding attributes must have compatible data types
• Attribute names should be the same (or renamed to match)

Union Example:

Students Table:

Faculty Table:

Students ∪ Faculty (Union Result):

Note: Jane appears only once (duplicates eliminated)

3.2 Intersection (∩)

Symbol: R ∩ S

Purpose: Returns tuples common to both relations

Conditions (Union Compatibility):

• Both relations must have the same number of attributes
• Corresponding attributes must have compatible data types

Intersection Example:

Current Students Table:

Alumni Table:

Current Students ∩ Alumni (Intersection Result):

Note: Only Jane with Year 2024 exists in both tables

3.3 Set Difference (−)

Symbol: R − S

Purpose: Returns tuples in R but not in S

Conditions (Union Compatibility):

• Both relations must have the same number of attributes
• Corresponding attributes must have compatible data types

Set Difference Example:

All Students Table:

Graduated Students Table:

All Students − Graduated Students (Difference Result):

Note: Students who have NOT graduated

3.4 Cartesian Product (×)

Symbol: R × S

Purpose: Combines every tuple from R with every tuple from S

Conditions:

• When relations have common attribute names, use RelationName.attribute notation
• If no common attributes, proceed normally

Cartesian Product Examples:

Case 1: No Common Attributes

Employee Table:

Project Table:

Employee × Project:

Case 2: Common Attributes (Name)

Student Table:

Teacher Table:

Student × Teacher (using RelationName.attribute):

Note: Common attribute ‘Name’ requires RelationName.attribute notation

4. Join Operations

4.1 Inner Joins

4.1.1 Natural Join (⋈)

Symbol: R ⋈ S

Purpose: Joins relations on common attributes with same names

Conditions:

• Relations must have at least one attribute with the same name
• Common attributes must have compatible data types
• Automatically eliminates duplicate columns

Natural Join Example:

Employee Table:

Department Table:

Employee ⋈ Department (Natural Join Result):

Note: Common attribute DID appears only once (combined/eliminated). Alice (DID=30) and HR (DID=40) not included as no match.

4.1.2 Theta Join (θ-Join)

Symbol: R ⋈_θ S where θ is a condition

Purpose: Joins relations based on any comparison condition

Conditions:

• Can use any comparison operator: =, ≠, <, >, ≤, ≥
• Can combine multiple conditions with ∧, ∨
• Does not eliminate duplicate columns (unlike natural join)
• Uses RelationName.attribute when common attributes exist

Theta Join Examples:

Case 1: Different Attribute Names

Employee Table:

Manager Table:

Employee ⋈_{Salary < MaxSal} Manager:

Case 2: Common Attribute Names

Employee Table:

Manager Table:

Employee ⋈_{Employee.Salary < Manager.Salary} Manager:

Note: RelationName.attribute used for common attributes (Name, Salary). All columns retained.

4.1.3 Equi-Join

Symbol: R ⋈_{A = B} S

Purpose: Special case of theta join using only equality conditions

Conditions:

• Uses only equality (=) operator
• Does not eliminate duplicate columns (unlike natural join)
• Attributes being compared can have different names
• Uses RelationName.attribute when common attributes exist

Equi-Join Examples:

Case 1: Different Attribute Names

Employee Table:

Department Table:

Employee ⋈_{DeptID = ID} Department:

Case 2: Common Attribute Names

Student Table:

Course Table:

Student ⋈_{Student.ID = Course.ID} Course:

Better Example - Student ⋈_{Student.Name = Course.Name} Course: Assuming Course has instructor names matching student names

Note: RelationName.attribute notation required for common attributes. Both duplicate columns retained.

Difference from Natural Join:

• Equi-join keeps duplicate columns
• Natural join eliminates duplicate columns
• Equi-join can join on different attribute names

4.2 Outer Joins

Purpose: Include unmatched tuples from one or both relations, filling with NULLs

Important: When relations have common attributes (other than join attributes), use RelationName.attribute notation for all joins except Natural Join.

Sample Tables for All Examples:

Employee Table:

Department Table:

Outer Join Results Comparison:

Results (Natural Join Based - Common DID Combined):

Note: Based on Natural Join (common DID combined). For other outer joins, use RelationName.attribute notation.

SQL Equivalents: LEFT JOIN, RIGHT JOIN, FULL OUTER JOIN

5. Additional Relational Operations

Features of Generalized Projection:

• Arithmetic operations: +, -, ×, ÷
• String operations: concatenation
• Functions: mathematical, date functions

5.3 Aggregate Functions and Grouping

5.3.1 Basic Aggregation

Symbol: G_{F₁, F₂, …, Fₙ}(R)

Aggregate Functions:

• SUM: Total of numeric values
• AVG: Average of numeric values
• COUNT: Number of tuples
• MAX: Maximum value
• MIN: Minimum value

Aggregate Function Examples:

Employee Table:

Basic Aggregation Examples:

1. G_COUNT(*)(Employee) - Count all employees:

   COUNT
   5

2. G_AVG(salary)(Employee) - Average salary:

   AVG_Salary
   51000

3. G_{MAX(salary), MIN(salary)}(Employee) - Max and min salary:

   MAX_Salary	MIN_Salary
   65000	40000

5.4 Division (÷)

Symbol: R ÷ S

Purpose: Finds tuples in R that are related to ALL tuples in S

Conditions:

• Attributes of S must be a subset of attributes of R
• Complex operation often used for “for all” queries

Division Example - “Find students enrolled in ALL courses”:

Enrollment Table (R):

AllCourses Table (S):

Enrollment ÷ AllCourses (Division Result):

Note: Only S1 is enrolled in ALL courses (C1, C2, C3). S2 is missing C3, S3 is missing C2 and C3.

Step-by-step Process:

1. S1 has {C1, C2, C3} - contains all courses ✓
2. S2 has {C1, C2} - missing C3 ✗
3. S3 has {C1} - missing C2, C3 ✗

Generalized Projection

Generalized projection allows for more complex expressions in the projection operation, including arithmetic operations, string concatenation, and function applications. Symbol: Π_{F₁, F₂, …, Fₙ}(R) Purpose: Projects specific attributes and allows for computed fields

Table Example:

Example:

Π_{name, salary * 0.1}(Employee)

6. Database Manipulation Operations

Database manipulation operations in relational algebra are used to modify the contents of relations. These operations correspond to SQL’s INSERT, UPDATE, and DELETE operations.

6.1 Insertion (∪ with new tuples)

Purpose: Add new tuples to a relation

Syntax: R ← R ∪ {new tuples}

Conditions:

• New tuples must have same schema as existing relation
• Duplicate tuples are automatically eliminated (set property)

Insertion Examples:

Original Employee Table:

Insert Single Tuple:

Employee ← Employee ∪ {(3, 'Bob', 'HR', 50000)}

Result:

Insert Multiple Tuples:

Employee ← Employee ∪ {(4, 'Alice', 'CS', 60000), (5, 'Tom', 'IT', 48000)}

Insert from Another Relation:

Employee ← Employee ∪ ΠEID, Name, Dept, Salary(NewHires)

6.2 Deletion (− Difference)

Purpose: Remove tuples that satisfy certain conditions

Syntax: R ← R − σ_condition(R)

Conditions:

• Uses selection to identify tuples to delete
• Remaining tuples form the new relation

Deletion Examples:

Original Employee Table:

Delete by Condition:

Employee ← Employee − σDept = 'HR'(Employee)

Result:

Delete Multiple Conditions:

Employee ← Employee − σSalary < 50000 ∨ Dept = 'IT'(Employee)

Delete All Tuples:

Employee ← Employee − Employee  (Results in empty relation)

6.3 Update (Combination of Delete and Insert)

Purpose: Modify attribute values of existing tuples

Approach: Update = Delete old tuples + Insert modified tuples

Syntax:

R ← (R − σcondition(R)) ∪ Πmodified_attributes(σcondition(R))

Update Examples:

Original Employee Table:

Update Single Attribute: Increase salary by 10% for CS employees

Employee ← (Employee − σDept = 'CS'(Employee)) ∪ 
           ΠEID, Name, Dept, Salary*1.1(σDept = 'CS'(Employee))

Result:

Update Multiple Attributes: Change Bob’s department to IT and increase salary

Employee ← (Employee − σName = 'Bob'(Employee)) ∪ 
           {(3, 'Bob', 'IT', 55000)}

Update with Complex Conditions: Give 5% raise to employees earning less than 50000

LowSalary ← σSalary < 50000(Employee)
Employee ← (Employee − LowSalary) ∪ 
           ΠEID, Name, Dept, Salary*1.05(LowSalary)

6.4 Transaction Operations

Purpose: Ensure database consistency during multiple operations

ACID Properties in Relational Algebra:

Transaction Example: Transfer employee from one department to another with salary adjustment

-- Step 1: Verify employee exists
Temp1 ← σEID = 123(Employee)

-- Step 2: Remove from current department
Employee ← Employee − Temp1

-- Step 3: Add to new department with updated info
Employee ← Employee ∪ {(123, 'John', 'NewDept', NewSalary)}

6.5 Bulk Operations

Purpose: Perform operations on multiple tuples efficiently

Bulk Insert:

Employee ← Employee ∪ σSalary > 60000(Contractors)

Bulk Update:

HighEarners ← σSalary > 70000(Employee)
Employee ← (Employee − HighEarners) ∪ 
           ΠEID, Name, Dept, Salary*0.95(HighEarners)

Bulk Delete:

Employee ← Employee − σDept ∈ {'HR', 'Admin'}(Employee)

6.6 Constraints and Validation

Purpose: Ensure data integrity during manipulation operations

Primary Key Constraint:

-- Before insertion, check for duplicates
NewEmployee ← {(NewEID, NewName, NewDept, NewSalary)}
Duplicate ← ΠEID(Employee) ∩ ΠEID(NewEmployee)

-- Insert only if no duplicate
Employee ← Employee ∪ (NewEmployee − (NewEmployee ⋈ Duplicate))

Foreign Key Constraint:

-- Ensure department exists before assigning employee
ValidDepts ← ΠDeptName(Department)
NewEmployee ← {(EID, Name, DeptName, Salary)}

-- Insert only if department is valid
Employee ← Employee ∪ (NewEmployee ⋈ ValidDepts)

Check Constraints:

-- Ensure salary is positive
ValidSalary ← σSalary > 0(NewEmployee)
Employee ← Employee ∪ ValidSalary

7. Database Manipulation vs Query Operations

Combined Example - Employee Promotion System:

-- Query: Find eligible employees
Eligible ← σYears > 2 ∧ Performance = 'Excellent'(Employee)

-- Manipulation: Promote eligible employees
Promoted ← ΠEID, Name, Dept, Salary*1.15(Eligible)
Employee ← (Employee − Eligible) ∪ Promoted

-- Query: Verify promotion results
NewHighEarners ← σSalary > 70000(Employee)