Relational Algebra: Selection, Projection, and Renaming

Selection ($\sigma$)

Selection picks the rows of a relation that satisfy a Boolean predicate. It does not change the columns or their names.

$\sigma_{\text{predicate}}(R)$

Example. Given a relation Employees(name, department, salary):

$\sigma_{\text{salary} > 50000}(\text{Employees})$

returns all employees earning more than 50,000. The result has the same schema as Employees.

SQL translation.

SELECT DISTINCT *
FROM Employees
WHERE salary > 50000;

The asterisk denotes all fields — there is no projection. DISTINCT is needed because SQL defaults to multiset semantics (see Lecture 7), whereas RA operates on sets.

Predicates can be combined with $\land$, $\lor$, $\neg$:

$\sigma_{\text{salary} > 50000\;\land\;\text{department} = \text{'CS'}}(\text{Employees})$

SQL:

SELECT DISTINCT *
FROM Employees
WHERE salary > 50000 AND department = 'CS';

Projection ($\pi$)

Projection picks specified columns and eliminates duplicate rows. It corresponds to the mathematical operation of projecting a relation onto a subset of its attributes.

$\pi_{A_1, A_2, \ldots, A_k}(R)$

Example.

$\pi_{\text{name}, \text{department}}(\text{Employees})$

returns all (name, department) pairs in the database, with duplicates removed. If two employees share the same name and department, the projection contains that pair only once.

SQL translation.

SELECT DISTINCT name, department
FROM Employees;

Note the misleading keyword: SELECT in SQL performs projection, not selection. In RA, projection is $\pi$, selection is $\sigma$. The SQL WHERE clause corresponds to RA $\sigma$ (selection); the SQL SELECT clause corresponds to RA $\pi$ (projection).

A projection with no selection:

SELECT DISTINCT name, department FROM Employees;
-- no WHERE clause -- so no RA selection, despite the 'SELECT' keyword

Renaming ($\rho$)

Renaming changes column names. It does not alter data.

$\rho_{\{A \mapsto C,\; B \mapsto D, \ldots\}}(R)$

Example.

$\rho_{\{\text{name} \mapsto \text{fullName},\; \text{salary} \mapsto \text{annualPay}\}}(\text{Employees})$

produces a relation with columns fullName, department, annualPay instead of name, department, salary.

SQL translation.

SELECT name AS fullName, department, salary AS annualPay
FROM Employees;

SQL implements renaming with the AS keyword. Renaming is frequently needed to make schemas compatible for set operations or products.

Combined use

RA operators compose naturally. To find the departments of highly-paid employees:

$\pi_{\text{department}}(\sigma_{\text{salary} > 50000}(\text{Employees}))$

SQL:

SELECT DISTINCT department
FROM Employees
WHERE salary > 50000;

The RA expression reads inside-out: first filter rows, then project columns and deduplicate. SQL reads more like linear prose: decide what columns, from what table, subject to what condition.

Operator precedence (convention)

In RA expressions, unary operators ($\sigma$, $\pi$, $\rho$) bind tighter than binary operators ($\times$, $\cup$, $-$, $\cap$). When writing queries, use parentheses to make the evaluation order explicit.

Summary table

RA operator	SQL equivalent	Function
$\sigma_p(R)$	WHERE	Filter rows by predicate $p$
$\pi_X(R)$	SELECT DISTINCT	Pick columns in $X$, deduplicate
$\rho_M(R)$	AS	Rename columns per map $M$