skip to content

What does the projection operator π (pi) do in relational algebra, and why can projecting a relation return fewer tuples than it read?

level: middleimportance: must knowfreq 62%

answer

  1. π = vertical, heading shrinks
  2. set semantics → collapse of duplicates is intrinsic
  3. project a key ⇒ cardinality preserved
  4. π_X(π_Y) = π_X when X ⊆ Y
  5. SQL column list = π only with DISTINCT

basics

~20 s

Projection π_{A,B}(R) keeps only the listed attributes of every tuple, producing a relation with a narrower heading. Because a relation is a set, tuples that become identical after the other attributes are dropped collapse into one — so the row count can shrink.

solid answer

~50 s

π is the **vertical** operator: `π_{A,B}(R)` returns a relation whose heading is just the listed attributes, formed by trimming each tuple of R down to those attributes. The row count can drop because relational algebra is defined over **sets**. If you project away the attributes that made two tuples distinct, the trimmed tuples become identical, and a set holds one copy — so duplicate elimination is part of projection's definition, not an optional extra. `π_{department}(employee)` over 500 employees in 6 departments yields 6 tuples. Two corollaries. Projecting a superkey (or any key) never loses rows, because key values are already unique. And projection is generally **not** information-preserving: you cannot reconstruct R from `π_{A}(R)` and `π_{B}(R)` unless the decomposition is lossless — the property normalization theory is built on. In SQL the column list is the projection, but SQL keeps duplicates unless you write `DISTINCT`, because a SQL table is a bag.

code

sql · 6 lines
sql
-- π_{department}(employee)  → one tuple per distinct department
SELECT DISTINCT department FROM employee;

-- π_{emp_id, department}(employee) — emp_id is the key,
-- so DISTINCT cannot remove anything; cardinality is preserved
SELECT emp_id, department FROM employee;

go deeper

for a junior

Give the definition — keep the listed columns — and be able to say why the row count can shrink: relations are sets, so identical trimmed tuples merge.

for a middle

State the cardinality rule precisely (distinct count of the projected attributes; preserved when a key is included) and the SQL bag-vs-set divergence requiring DISTINCT.

for a senior

Bring in the cost of duplicate elimination (sort vs hash, spill risk) and when a planner can prove it away from unique constraints, plus the σ/π reordering condition.

for a principal

Connect projection to lossless decomposition and normalization theory, and discuss where enforcing distinctness belongs in a pipeline versus relying on declared keys to make it provably unnecessary.

## Definition `π_{A₁,…,Aₙ}(R)` produces the relation whose heading is exactly `{A₁,…,Aₙ}` (which must be a subset of R's heading) and whose body is `{ t[A₁,…,Aₙ] | t ∈ R }`, where `t[…]` means the tuple restricted to those attributes. The key phrase is *the set of*. Relational algebra's values are sets of tuples: no duplicates, no order. Once the restriction is applied, any two trimmed tuples that are equal are the same element of the set, so only one survives. ## Why the cardinality drops Suppose `employee(emp_id, name, department)` holds 500 tuples across 6 departments. Restricted to `department`, tuple 17 and tuple 204 might both become `('SALES')`. As set elements they are indistinguishable, so the result has at most 6 tuples. This **duplicate elimination is intrinsic**: it is not a step the engine chooses to add, it follows from the output being a relation. More precisely: `|π_X(R)|` equals the number of *distinct* X-values in R. It ranges from 1 (when X is functionally determined by a constant, or all tuples agree) up to `|R|`. ## When projection preserves cardinality `|π_X(R)| = |R|` exactly when X contains a **key** (or more generally a superkey) of R — because key values are unique by definition, no two tuples can collide after trimming. This is a genuinely useful reasoning tool: if you project a table's primary key plus anything else, you know the row count is unchanged. It is also why a planner can skip a deduplication step when it can prove the projected list covers a unique constraint. ## Projection loses information Projection is not invertible. From `π_{emp_id,name}(R)` and `π_{name,department}(R)` you generally cannot rebuild R: joining them back on `name` can manufacture tuples that never existed (a *lossy* decomposition) when `name` is not a key. Relational design theory formalises the condition — a decomposition of R into X and Y is lossless when `X ∩ Y` is a superkey of X or of Y — and that theorem is stated entirely in terms of projection and join. So "projection throws away rows *and* the ability to reconstruct" is the honest summary. ## Algebraic laws - **Cascade / absorption**: `π_X(π_Y(R)) = π_X(R)` provided `X ⊆ Y`. The outer, narrower list wins; the inner one is redundant. - **Idempotence**: `π_X(π_X(R)) = π_X(R)`. - **Interaction with selection**: `π_X(σ_p(R)) = σ_p(π_X(R))` **only if** every attribute p references is contained in X. If the predicate needs a column that the projection drops, you cannot project first — the filter would have nothing to test. - **Interaction with union**: `π_X(R ∪ S) = π_X(R) ∪ π_X(S)` for union-compatible R and S. Projection does *not* distribute over difference in the same way: `π_X(R − S) ≠ π_X(R) − π_X(S)` in general, because dropping attributes can make a tuple of R match a tuple of S that it did not match before. ## Correspondence to SQL The `SELECT` column list is the projection. The important divergence: **SQL relations are bags**, so `SELECT department FROM employee` returns 500 rows, one per employee, while `π_{department}(employee)` returns 6 tuples. `SELECT DISTINCT department FROM employee` is the faithful translation of π. That divergence has a cost story. Duplicate elimination is not free: an engine implements `DISTINCT` by sorting (then discarding adjacent equals) or by hashing, which means either an O(n log n) sort with possible spill to disk, or a hash table sized by the number of distinct values. If a unique constraint or an already-sorted index guarantees distinctness, the engine can drop the operator entirely — which is exactly the "projection over a key preserves cardinality" rule turned into an optimization. SQL also allows *extended* projection — computed expressions and renaming in the select list (`price * qty AS total`). Classic projection only restricts to existing attributes; expressions and renaming belong to the extended/rename operators of the algebra, which sit alongside π rather than inside it. ## The one-sentence version Selection narrows a relation vertically by dropping *rows*; projection narrows it horizontally by dropping *columns*, and because the result must still be a set, dropping columns can silently drop rows too.

  • When can a query engine safely skip the duplicate-elimination step that a projection implies?
    When it can prove the projected attribute list already yields distinct tuples — most commonly because the list contains a primary key or another unique constraint of the source relation, or because the input arrives distinct from an upstream operator. Some engines also drop the step when the consumer does not care about duplicates, for example an EXISTS subquery or a semi-join. The proof matters because deduplication costs a sort or a hash build.
  • Under what condition can you swap the order of a projection and a selection?
    Only when every attribute referenced by the selection predicate is among the projected attributes. If the predicate tests a column the projection drops, filtering after projecting is impossible — the column is gone. When the condition holds, the swap is semantically neutral, and pushing the projection down early can still help by shrinking tuple width before an expensive operator.
  • Why is projection called a lossy operation, and where does that show up in database design?
    Because you generally cannot reconstruct the original relation from its projections — joining them back can produce spurious tuples that were never in the original. Normalization theory addresses this directly: a decomposition into two projections is lossless exactly when their shared attributes form a superkey of at least one of the parts. That test is why normal-form decompositions are chosen along functional dependencies rather than arbitrarily.

Projection is like photocopying a stack of forms with all but two fields blacked out: forms that differed only in the hidden fields come out as identical sheets, and you keep one of each.

saying these in an interview costs you the question

  • Saying projection only removes columns and can never change the row count.
  • Treating a plain SQL column list as a faithful π, forgetting SQL keeps duplicates.
  • Claiming DISTINCT is free or merely cosmetic, rather than a sort/hash operator.
  • Assuming R can always be rebuilt by joining its projections back together.
  • Confusing projection with selection — "π filters rows matching a condition".

context

resolving links…