18 - Relational Algebra

Overview

Relational algebra defines the basic set of operations for the relational model.

• The result of an operation is a new relation, which may have been formed from one or more input relations

Database Schema for Company

Unary Relational Operations

SELECT

The SELECT operation σ is used to select a subset of the tuples from a relation based on a selection condition.

• The selection condition acts as a filter, getting rid of all tuples that don’t meet the condition

In general, the SELECT operation is denoted by σ_{<selection condition>}(R)

Examples

• Select the EMPLOYEE tuples whose department number is 4:

σ_Dno=4(EMPLOYEE)

• Select the employee tuples whose salary is greater than $30,000:

σ_Salary>30000(EMPLOYEE)

Properties

• The SELECT operation σ_{<selection condition>} produces a relation S that has the same schema (attributes) as R.

• SELECT is commutative:

σ_<cond1>(σ_<cond2>(R)) = σ_<cond2>(σ_<cond1>(R))

• A cascade of SELECT operations may be replaced by a single selection with a conjunction of all the conditions:

σ_<cond1>(σ_<cond2>(σ_<cond3>(R))) = σ_{<cond1> AND <cond2> AND <cond3>}(R)

PROJECT

The PROJECT operation π keeps columns (attributes) from a relation and discards the other columns.

In general, the PROJECT operation is denoted by π_{<attribute list>}(R)

The PROJECT operation removes any duplicates, since it must return a set of tuples.

Examples

• List each employee’s first and last name and salary:

π_{Fname,Lname,Salary}(EMPLOYEE)

Properties

• The number of tuples in the result of a projection is less than or equal to the number in the original relation.

• PROJECT is not commutative

RENAME

The RENAME operator ρ is used rename the attributes and/or name of a relation.

The RENAME operation can take any of the following forms:

• ρ_{S(B1,B2,…,Bn)}(R) changes the relation name to S and the attribute names to B1, B2, … Bn.

• ρ_S(R) changes the relation name to S.

• ρ_{(B1,B2,…,Bn)}(R) changes the attribute names to B1, B2, … Bn

Relational Algebra Expressions with Multiple Operations

Suppose we want to apply several relational algebra operations consecutively. We have 2 options:

• Write as a single expression by nesting the operations

• Apply one condition at a time using intermediate result relation

Example

Retrieve the first name, last name, and salary of all employees who work in department number 5:

• Using nested operations:

π_{Fname,Lname,Salary}(σ_Dno=5(EMPLOYEE))

• Using intermediate relations:

DEP5_EMPS ← σ_Dno=5(EMPLOYEE) RESULT ← π_{Fname,Lname,Salary}(DEP5_EMPS)

Relational Algebra Operations from Set Theory

UNION

The UNION operator ∪ returns a relation that includes all tuples that are in either of its two operands. Duplicate tuples are eliminated. The two operands must have the same number of attributes and have compatible domains.

Example

Retrieve the social security numbers of all employees who either work in department 5 (RESULT1 below) or directly supervise an employee who works in department 5 (RESULT2 below):

DEP5_EMPS ← σ_Dno=5(EMPLOYEE) RESULT1 ← π_Ssn(DEP5_EMPS) RESULT2 ← π_Superssn(EP5_EMPS) RESULT ← RESULT1 ∪ RESULT2

INTERSECTION

The INTERSECTION operation ∩ returns all tuples that are in both operand relations.

SET DIFFERENCE

The SET DIFFERENCE (or MINUS or EXCEPT) operation - returns all tuples that are in the first operand but not the second.

CARTESIAN PRODUCT

The CARTESIAN (or CROSS) PRODUCT operation x combines tuples from two relations in a combinatorial fashion.

The resulting relation has n + m attributes: R(A1, A2, …, An) x S(B1, B2, …, Bn) = Q(A1, A2, …, An, B1, B2, …, Bn)

The operands do not have to be type compatible.

Type Compatibility for Set Operations

R1(A1, A2, …, An) and R2(B1, B2, …, Bn) are type compatible if:

• They have the same number of attributes and

• The domains of the corresponding attributes are type compatible (same domains)

Type compatibility is required for UNION ∪, INTERSECTION ∩, and SET DIFFERENCE -.

By convention, the relation resulting from R∪S has the attributes of R.