Relational Algebra

Definition

Relational Algebra is a procedural formal language for the relational model that uses a set of operations to take one or more relations as input and produce a relation as output.

A relation is a table with rows and columns, and each operation in relational algebra returns another valid relation. This property is called closure. The algebra includes operations such as selection, projection, union, difference, Cartesian product, join, and division.

Example: If STUDENT(RollNo, Name, Dept) is a relation, relational algebra can be used to find:

• all students in the CSE department,
• only the names of students,
• students who took a particular course,
• students who appear in one relation but not another.

Main Content

1. Basic Operations in Relational Algebra

Selection (σ)

• : Used to filter rows based on a condition.
• It chooses tuples that satisfy a predicate.
• Example: σ Dept = 'CSE' (STUDENT) returns only students from the CSE department.

Projection (π)

• : Used to select specific columns.
• It removes unwanted attributes and keeps only required ones.
• Example: π Name, Dept (STUDENT) returns only the Name and Dept columns.
• Duplicate rows are automatically eliminated in relational algebra.

Union, Difference, and Cartesian Product

• :
• Union (∪) combines tuples from two compatible relations.
• Difference (-) returns tuples in one relation but not in the other.
• Cartesian Product (×) pairs every tuple of one relation with every tuple of another relation.
• Example:
  • R ∪ S gives all tuples in either R or S.
  • R - S gives tuples present in R but absent in S.
  • R × S creates all possible combinations of rows.

These operations form the foundation of querying in relational algebra. Selection and projection are unary operations, while union, difference, and Cartesian product are binary operations.

2. Derived Operations and Join Operations

Intersection (∩)

• :
• Returns only the tuples common to both relations.
• It can also be derived using difference and union.
• Example: R ∩ S gives tuples present in both R and S.

Join Operations

• :
• Joins are among the most important operations because they combine related data from multiple relations.
• Theta Join (⋈θ): Combines tuples based on a comparison condition such as =, <, >, <=, >=.
  • Example: STUDENT ⋈ STUDENT.DeptID = DEPT.DeptID DEPT
• Equi Join: A theta join using only equality.
• Natural Join (⋈): Automatically joins relations using common attribute names and removes duplicate join columns.
• Example: EMPLOYEE ⋈ DEPARTMENT joins on common attributes like DeptID.

Division (÷)

• :
• Used for queries involving “for all” conditions.
• Example: If ENROLLED(Student, Course) and REQUIRED(Course), division can find students enrolled in all required courses.
• This is useful for questions like “Find students who took every course in a set.”

Joins connect relational algebra to real-world database problems because many queries require combining data from multiple tables.

3. Properties, Characteristics, and Relation to SQL

Closure Property

• :
• The result of every relational algebra operation is a relation.
• This allows operations to be chained together.
• Example: π Name (σ Dept = 'IT' (STUDENT)) is valid because each step returns a relation.

Procedural Nature

• :
• Relational algebra tells the system how to get the result step by step.
• This is different from SQL, which is declarative and focuses on what result is needed.
• Example:
  • SQL: SELECT Name FROM STUDENT WHERE Dept = 'CSE';
  • Relational Algebra: π Name (σ Dept = 'CSE' (STUDENT))

Query Optimization and Foundation of SQL

• :
• Database engines use relational algebra principles to rewrite queries into more efficient execution plans.
• Equivalent relational algebra expressions can produce the same result, allowing optimization.
• Example:
  • Applying selection before join can reduce the number of tuples processed.
  • σ Dept = 'CSE' (STUDENT ⋈ ENROLLMENT) may be optimized by first filtering STUDENT.

Relational algebra is essential for understanding how databases process queries, and it gives a theoretical basis for efficient database design and implementation.

Working / Process

1. Identify the relations and required result

• Determine which tables are involved and what output is needed.
• Example: To find names of students in CSE, use the STUDENT relation and the condition Dept = 'CSE'.

2. Choose the appropriate relational algebra operations

• Use selection to filter rows, projection to choose columns, join to combine tables, and other operations as needed.
• Example expression: π Name (σ Dept = 'CSE' (STUDENT))

3. Apply operations in the correct order

• Start with the innermost operation and move outward.
• For the example:
  • First apply selection: keep only CSE students.
  • Then apply projection: keep only the Name attribute.

4. Interpret the final relation

• The output is a new relation that satisfies the query.
• Example output:
  • Amit
  • Riya
  • Karan

A simple visual representation:

STUDENT
---------------------------------
RollNo | Name  | Dept
---------------------------------
1      | Amit  | CSE
2      | Riya  | ECE
3      | Karan | CSE

Query: names of CSE students

σ Dept = 'CSE' (STUDENT)
          ↓
---------------------------------
RollNo | Name  | Dept
---------------------------------
1      | Amit  | CSE
3      | Karan | CSE
          ↓
π Name
          ↓
Name
-----
Amit
Karan

Advantages / Applications

Mathematical foundation of databases

• It provides a rigorous and formal way to represent database queries.
• This helps in proving query correctness and understanding relational theory.

Basis for SQL query processing

• SQL is translated internally into algebraic operations by database systems.
• Understanding relational algebra makes it easier to understand how SQL queries are executed.

Supports query optimization

• Equivalent algebraic expressions can be transformed into more efficient forms.
• This reduces execution time and improves performance on large datasets.

Useful in database design and learning

• It helps students and developers understand relational models deeply.
• It is also used in textbooks, examinations, and theoretical database analysis.

Handles complex retrieval tasks

• Operations like join and division allow advanced queries such as matching multiple conditions or universal quantification.
• This makes it suitable for sophisticated information retrieval in relational databases.

Summary

• Relational algebra is a formal method for querying and manipulating relational data.
• It uses operations like selection, projection, join, union, and division to produce new relations.
• It is the theoretical foundation behind SQL and database query optimization.
• Important terms to remember: relation, tuple, attribute, selection, projection, join, division, closure.