Relational algebra is a set of operators to retrieve and manipulate tuples in a relation. Each operator takes in one or more relations as inputs, and outputs a new relation. To write queries we can “chain” these operators together to create more complex operations.
Relational algebra describes a step-by-step procedure (i.e. describes the how) for computing the desired answer (imperative). This contrast with tuple calculus, which is declarative.
Different relational algebra expressions can be logically equivalent but with different execution costs. This gives DBMS opportunities to optimize.
Basic Operators
Select
Select is a unary operator that selects a subset of rows from a relation.
- Syntax:
- Example:
- SQL:
SELECT * FROM Students WHERE country = 'AUS'
The select operator corresponds to
WHERE
rather thanSELECT
in SQL
Projection
The projection is an unary operator that selects a subset of columns from a relation
- Syntax:
- Example:
- SQL:
SELECT name,country FROM Students
The projection operator correspond to
SELECT
in SQL
Cross-product
The cross product operator, also known as the Cartesian product, generates all possible combinations of tuples from two relations. It is defined as (SELECT * FROM R) CROSS JOIN (SELECT * FROM S)
, or simply SELECT * FROM R, S
Join
combines matching tuples from two relations
Conditional (or Theta) Join
Equi-Join
Special case of theta join where the condition
Natural Join
Equijoin on all common (i.e. same named) fields, followed by a projection
- Syntax:
- SQL:
SELECT * FROM R JOIN S USING (ATTRIBUTE1, ATTRIBUTE)
Set Operations
Important constraint:
Union
Set union of a relations A and B returns all tuples in relation A plus those that are in relation B
Syntax: (SELECT * FROM R) UNION ALL (SELECT * FROM S)
Intersection
Set intersection
Syntax: (SELECT * FROM R) INTERSECT (SELECT * FROM S)
Difference
Set difference
Syntax: (SELECT * FROM R) EXCEPT (SELECT * FROM S)
Rename ( )
Notation 1:
- returns the expression
under the name Notation 2: - (assumes that the relational-algebra expression E has arity N)
- rename all the attributes
Basis versus Derived Operations
Only 6 basic operators are required to express everything else
- Selection
- Projection
- Cross-product
- Union
- Set Difference
- Rename
Other operators can be derived. For example:
- Intersection
- join