2.1 Relational Algebra: Combining Queries with Relations

SQL lets you express "what you want," while relational algebra provides a set of operators that can be combined, rewritten, and reasoned about. Query optimizers don’t execute SQL text literally; instead, they first construct a logical plan and then search for a lower-cost physical execution strategy while preserving the query’s semantics.

Learning Objectives

• Define relation, tuple, attribute, and schema;
• Use selection, projection, rename, union, difference, and product;
• Derive join from product combined with selection;
• Explain the differences between set semantics and SQL's bag/NULL semantics;
• Translate simple SQL statements into relational algebra trees.

The Minimal Model of Relation

Given schema:

Items(item_id, type_id, name, value_cents)
Types(type_id, code)

In classical relational model:

• A relation is a set of tuples with identical attributes;
• Tuples have no inherent order;
• The relation itself has no inherent row order;
• As a set, duplicate tuples are not allowed;
• Attribute values come from their respective domains.

SQL tables do not fully align with this mathematical model. SQL queries default to bag/multiset semantics, allowing duplicate results; NULL values introduce three-valued logic; and certain types and expressions exhibit implementation-defined behaviors. When applying relational algebra to SQL, specify whether the model uses classical sets or includes duplicates and NULLs.

This lesson starts with classical operators, then explains SQL differences. SQL examples use the SQLite tables created in Lessons 1.1 and 1.2. Algebraic Items.type_id corresponds to catalog_items.item_type_id, and Types.type_id to item_types.item_type_id.

Selection σ

Select tuples based on a predicate without altering the schema:

σ value_cents >= 50000 (Items)

Equivalent SQL:

SELECT item_id, item_type_id AS type_id, name, value_cents
FROM catalog_items
WHERE value_cents >= 50000;

Input n rows; the selection output ranges from 0 to n rows. Output order is not guaranteed.

Multiple conjunctions can be applied sequentially:

σ type_id = 1 AND value_cents >= 50000 (Items)

= σ type_id = 1 (σ value_cents >= 50000 (Items))

Under classical two-valued logic, this equivalence holds directly. In SQL, rows with a predicate evaluating to UNKNOWN are treated the same as those with FALSE and are filtered out by the WHERE clause. However, when predicates involve NULL values, expressions that produce errors, or volatile functions, the actual rewriting must adhere to the target database’s semantic rules, as determined by the query optimizer.

Projection π

Projection selects attributes:

π type_id (Items)

The result of classical relational algebra is a set, so duplicate type_id entries are eliminated. In SQL, explicit DISTINCT is required:

SELECT DISTINCT item_type_id
FROM catalog_items;

Plain SQL:

SELECT item_type_id
FROM catalog_items;

This query retains duplicates, so it does not implement classical π.

Projections can also compute expressions within extended algebra, such as converting cents into a major unit; but computation, type conversion, and rounding must be explicitly defined in the semantics.

Rename ρ

A self-join needs distinct names for its two relation instances:

ρ I1 (Items)
ρ I2 (Items)

In SQL, aliases serve a similar purpose:

SELECT left_item.name, right_item.name
FROM catalog_items AS left_item
JOIN catalog_items AS right_item
  ON left_item.item_type_id = right_item.item_type_id
 AND left_item.item_id < right_item.item_id;

The final inequality prevents a pair of items from appearing twice in reverse order and also excludes self-pairing.

Union ∪

A union requires union-compatible inputs: the number of attributes must match, and the domains or types must be compatible.

π item_id (ActiveTaskItems)
∪
π item_id (CompletedTaskItems)

In SQL, UNION eliminates duplicates, making the operation closer to a set union; UNION ALL preserves duplicates and typically avoids the cost of duplicate elimination.

SELECT qi.item_id
FROM task_items AS qi JOIN tasks AS q ON q.task_id = qi.task_id
WHERE q.status = 'active'
UNION
SELECT qi.item_id
FROM task_items AS qi JOIN tasks AS q ON q.task_id = qi.task_id
WHERE q.status = 'completed';

The resulting column name is usually determined by the first input, while type compatibility and coercion follow the specific database rules.

Set difference −

AllItemIds − ReferencedItemIds

The SQL standard operator is EXCEPT, with variations in support across products and different duplicate rules:

SELECT item_id FROM catalog_items
EXCEPT
SELECT item_id FROM task_items;

You can also use NOT EXISTS to express an anti-join, which often provides a clearer way to handle correlation and NULL values.

SELECT v.item_id
FROM catalog_items AS v
WHERE NOT EXISTS (
    SELECT 1
    FROM task_items AS qi
    WHERE qi.item_id = v.item_id
);

Don't mechanically replace with NOT IN (subquery); when a subquery produces NULL, three-valued logic might cause the result to become entirely non-TRUE.

Cartesian product ×

R × S pairs every tuple from relation R with every tuple from relation S. If the cardinalities are m and n, the output has exactly m × n tuples; only a subsequent filter reduces that count.

SELECT *
FROM catalog_items
CROSS JOIN item_types;

A Cartesian product is rarely the final business result, but it defines the input to a theta join. Omitting a join predicate can result in an unintended Cartesian product, which rapidly expands the number of rows and increases computational cost.

Join is product plus selection

theta join:

Items ⋈ Items.type_id = Types.type_id Types

= σ Items.type_id = Types.type_id (Items × Types)

SQL:

SELECT
    i.item_id,
    i.name,
    t.code
FROM catalog_items AS i
JOIN item_types AS t
  ON t.item_type_id = i.item_type_id;

Logical equivalence does not mean the engine must actually materialize the product. A physical plan may use nested-loop joins, hash joins, merge joins, or index lookups, any of which preserves the result semantics.

Risks of natural joins

Natural joins automatically form equality predicates based on columns with the same name. If the schema evolves to include additional columns with the same name in the future, the query semantics may change silently. Therefore, production SQL typically explicitly writes JOIN ... ON ... or USING (...) to avoid ambiguity.

Relational expression tree

Query: Find the names of devices worth at least 50,000 cents.

SELECT i.name
FROM catalog_items AS i
JOIN item_types AS t
  ON t.item_type_id = i.item_type_id
WHERE t.code = 'device'
  AND i.value_cents >= 50000;

A logical expression:

π i.name
  (
    σ t.code = 'device' AND i.value_cents >= 50000
      (
        ρ i(Items)
        ⋈ i.type_id = t.type_id
        ρ t(Types)
      )
  )

Tree-based interpretation:

projection: i.name
└─ selection: t.code='device' AND i.value_cents>=50000
   └─ inner join: i.type_id=t.type_id
      ├─ Items as i
      └─ Types as t

This tree expresses the logical relationships involved, without specifying the order of hash table access, index lookup, or scan operations.

Derived operators

Intersection

R ∩ S = R − (R − S)

SQL can use INTERSECT, but care must be taken to verify product support and duplicate semantics.

Semijoin

A left semijoin returns only the tuples that match on the left side, without including any attributes from the right side:

SELECT i.item_id, i.name
FROM catalog_items AS i
WHERE EXISTS (
    SELECT 1
    FROM task_items AS qi
    WHERE qi.item_id = i.item_id
);

Using a regular inner join followed by a SELECT of left-table columns may produce duplicates; EXISTS more directly expresses "existence of a match."

Division

Division is suitable for queries that ask, "Which entities satisfy all requirements?" It identifies objects that have completed every task in the required set. SQL typically implements this using double NOT EXISTS, grouping with count, or set difference. Special handling is required when the required set is empty, to account for vacuous truth.

Self-Check

1. Why is SELECT item_type_id not a classical projection?
2. When there are 1,000 tuples on each side, how many tuples does R × S produce?
3. Why doesn't the logical definition of an inner join require the database to generate a complete product?
4. What differences might exist between NOT EXISTS and NOT IN when NULL values are present?
5. Write the semijoin SQL query for "all items referenced by active tasks".

Lesson Summary

Relational algebra expresses complex queries using a small set of composable operators. SQL's bag semantics, NULL values, and type rules make it only partially equivalent to classical algebra; before optimization or reasoning can proceed, the semantics must be clearly established. The next lesson explores which query transformations are safe and which may alter results due to outer joins, duplicates, or NULL values.