skip to content

In relational algebra, what does the selection operator σ (sigma) do to a relation, and how does a conjunctive predicate σ over "p AND q" relate to applying two selections one after the other?

level: juniorimportance: must knowfreq 68%

answer

  1. σ = horizontal filter, heading unchanged
  2. σ_{p∧q} = σ_p(σ_q(R)) — cascade
  3. selections commute → free reorder by cost
  4. OR does not cascade → union of selections
  5. WHERE keeps only TRUE, not UNKNOWN

basics

~10 s

Selection σ_p(R) keeps exactly the tuples of relation R that satisfy predicate p. The schema is unchanged — it filters rows, never columns. Conjunctions cascade: σ_{p∧q}(R) = σ_p(σ_q(R)) = σ_q(σ_p(R)).

solid answer

~50 s

σ is the **horizontal filter** of relational algebra. `σ_p(R)` returns `{ t ∈ R | p(t) }` — the same heading (attribute names and types) as R, a subset of its tuples. The predicate p is built from attributes of R, constants, comparisons and the connectives AND/OR/NOT; it can only see one tuple at a time. Two equivalences matter. **Cascade**: `σ_{p∧q}(R) = σ_p(σ_q(R))`, because both conjuncts must hold and each selection is independent. **Commutativity**: the order of the two selections doesn't change the result, so an optimizer is free to evaluate whichever conjunct is cheapest or most selective first — for example the one an index supports. Disjunction does *not* cascade: `σ_{p∨q}(R)` equals `σ_p(R) ∪ σ_q(R)`, not a nesting. Selection is also idempotent: `σ_p(σ_p(R)) = σ_p(R)`. In SQL, σ corresponds to the `WHERE` clause over a single relation.

code

sql · 6 lines
sql
-- σ_{status='ACTIVE' ∧ balance > 0}(account)
SELECT * FROM account WHERE status = 'ACTIVE' AND balance > 0;

-- semantically identical (cascade + commutativity)
SELECT * FROM (SELECT * FROM account WHERE balance > 0) t
WHERE t.status = 'ACTIVE';

go deeper

for a junior

State the definition — σ keeps rows matching the predicate, same columns — and give the WHERE-clause mapping plus the cascade rule for AND.

for a middle

Add the algebraic laws precisely (cascade, commutativity, idempotence), and note that OR becomes a union of selections rather than nested selections.

for a senior

Connect the laws to predicate pushdown and selectivity-driven conjunct ordering, and flag the SQL divergences: three-valued logic in WHERE and bag semantics.

for a principal

Frame σ as the rewrite licence the optimizer depends on: order-independent semantics with order-dependent cost, and be explicit about which movements need extra correctness conditions (outer joins, non-deterministic or side-effecting predicates).

## The setting: relations and a closed algebra A **relation** is a set of tuples over a fixed **heading** — a set of named, typed attributes. "Set" is load-bearing: no duplicate tuples, no ordering. Relational algebra is **closed**: every operator consumes relations and produces a relation, so expressions nest arbitrarily. Selection is one of the two unary operators that shape a single relation (the other is projection). ## What selection does `σ_p(R)` is defined as `{ t ∈ R | p(t) evaluates to true }`. Three consequences fall straight out of that definition: - **The heading is unchanged.** The output has exactly the attributes of R, with the same types. Selection is a *horizontal* operation — it removes rows, never columns. - **The result is a subset.** `|σ_p(R)| ≤ |R|`, and since R is a set with no duplicates, the output cannot contain duplicates either. Selection therefore never needs a deduplication step. - **It is tuple-at-a-time.** p is evaluated against one tuple in isolation. A predicate cannot reference another tuple of R, or a tuple of another relation, or an aggregate — those needs are met by joins, set operators, or extended (aggregate) operators, not by σ. ## The predicate language The classical predicate is a boolean formula over: - attribute names of R and constants, - comparison operators `=`, `≠`, `<`, `≤`, `>`, `≥`, - the connectives `∧` (and), `∨` (or), `¬` (not). Attribute-to-constant comparisons (`σ_{status='ACTIVE'}`) and attribute-to-attribute comparisons within the same tuple (`σ_{ship_date > order_date}`) are both legal. ## The algebraic laws worth memorising **Cascade of conjunction.** `σ_{p ∧ q}(R) = σ_p(σ_q(R))`. Requiring both conditions in one pass is the same as filtering twice, because each surviving tuple must satisfy both. This is what lets a planner *split* a compound predicate into pieces it can evaluate at different points in a plan. **Commutativity.** `σ_p(σ_q(R)) = σ_q(σ_p(R))`. Order is semantically irrelevant, so the engine may reorder purely on cost — for example evaluate the conjunct backed by an index first to cut the row count early, and apply the expensive function-call conjunct to the survivors. **Idempotence.** `σ_p(σ_p(R)) = σ_p(R)`. **Disjunction does not cascade.** `σ_{p ∨ q}(R)` is *not* `σ_p(σ_q(R))` — nesting means AND. The correct rewrite under set semantics is `σ_p(R) ∪ σ_q(R)`. (Under SQL's bag semantics, that union has to eliminate duplicates, since a tuple satisfying both p and q would otherwise appear twice.) **Empty and total cases.** A predicate that is always false yields the empty relation with R's heading; a predicate that is always true yields R itself. ## Correspondence to SQL σ is the `WHERE` clause: `σ_{p}(R)` ⇔ `SELECT * FROM R WHERE p`. Two mismatches are worth naming so you are not surprised: - **Three-valued logic.** Classical algebra assumes a two-valued predicate over a null-free relation; SQL predicates can evaluate to *unknown*, and `WHERE` keeps only rows where the predicate is *true*. So a SQL `WHERE` is closer to `σ_{p is true}`. - **Bags.** A SQL table may hold duplicate rows; filtering a bag yields a bag. Selection preserves whatever multiplicity the input had — it neither creates nor removes duplicates. ## Why any of this matters in practice The cascade and commutativity laws are the formal licence behind **predicate pushdown**: because a conjunction can be split and reordered freely, a query engine can move individual conjuncts down the plan tree toward the scan, apply the index-supported one as an access predicate, and leave the rest as a residual filter. Selectivity — the fraction of tuples a predicate keeps — is what the optimizer estimates to choose the order. Understanding that the *semantics* are order-independent while the *cost* is not is the core insight this question is really probing. A final framing: selection and projection are complementary. Selection chooses rows and preserves the heading; projection chooses attributes and can shrink the tuple count as a side effect of set semantics. Together they express "the part of this table I care about" before any join or set operation enters the picture.

  • Why can an optimizer reorder the two conjuncts of a selection but not always reorder a selection with respect to a join?
    Two selections over the same relation commute unconditionally, because each looks at one tuple of that relation in isolation. Moving a selection across a join is only safe when the predicate references attributes available on that side of the join and the join type preserves the rows involved — pushing a filter below the null-supplying side of an outer join, for instance, changes the result. So conjunct reordering is a free win; cross-operator movement needs a correctness check.
  • How would you rewrite σ over "p OR q" without a disjunction?
    As `σ_p(R) ∪ σ_q(R)`. Under set semantics the union removes the tuples that satisfy both, so the result is correct. Under bag semantics you must deduplicate explicitly, otherwise a tuple satisfying both p and q appears twice. Engines do exactly this rewrite when each branch can use a different index, then combine the row sets — the reason a disjunction is often more expensive than a conjunction.
  • Does selection ever change the cardinality upward, or change the schema?
    No on both counts. σ returns a subset of the input tuples with the identical heading, so cardinality can only stay the same or shrink and the attribute list is untouched. Any operation that widens or narrows the tuple is projection or an extended operator, not selection.

Selection is a sieve laid over a stack of index cards: every card that passes keeps all of its printed fields, and stacking two sieves in either order lets through exactly the cards that pass both.

saying these in an interview costs you the question

  • Saying selection picks columns — confusing σ with π.
  • Claiming σ_{p∨q}(R) = σ_p(σ_q(R)); nesting means AND, not OR.
  • Believing the order of two selections changes the result rather than only the cost.
  • Assuming selection can dedupe rows or reference other tuples/aggregates in its predicate.
  • Treating SQL WHERE as identical to σ while ignoring that UNKNOWN rows are dropped.

context

resolving links…