Relational algebra query patterns¶

TL;DR patterns¶

Existential ("at least one"): join what you need, use \(\sigma\) to filter, then \(\pi\) to keep the id(s).
Universal / "only" / "all": \(\text{result ids} = \text{candidates} - \text{intruders}\) (project ids before the difference).
"At least k" matches: self-join \(k\) copies (or group if allowed), then require \(k\) distinct matches for the same id.
Min / Max via self-join: keep rows not beaten by a strictly smaller/greater one using self-join plus difference.

Keyword guide¶

Keyword	Quantifier	Core operator
"at least one", "some", "exists"	\(\exists\)	join + select \(\sigma\)
"only", "all", "every", "no"	\(\forall\)	difference (candidates \(-\) intruders)

Existential (easy case)¶

Pattern: join what you need, filter, project ids.

Example: students who passed at least one CS exam.

\[ \large{RESULT = \pi_{\text{student_id}}\bigl( \sigma_{\text{course}=\text{"CS"}}( \text{Students} \bowtie \text{Exams} )\bigr)} \]

Universal / "only" / "all" (complement trick)¶

Use candidates minus intruders. Always project to the same schema (usually ids) before the difference.

\(CANDIDATES = \pi_{id}(\dots)\) (everyone who could qualify)
\(INTRUDERS = \pi_{id}( \sigma_{\text{bad}}(\dots) )\)
\(RESULT = CANDIDATES - INTRUDERS\)

Example: people who attended only foreign concerts.

\[ \begin{aligned} \large{CANDIDATES} &= \large{\pi_{\text{pid}}(\text{Persons} \bowtie \text{Concerts})}\\ \large{INTRUDERS} &= \large{\pi_{\text{pid}}\bigl( \sigma_{\text{country}=\text{"IT"}}(\text{Persons} \bowtie \text{Concerts}) \bigr)}\\ \large{RESULT} &= \large{CANDIDATES - INTRUDERS} \end{aligned} \]

Mental model: find violators (intruders) and subtract them from the candidates.

"At least k" occurrences¶

If grouping is unavailable, self-join k distinct occurrences and force them to be different.

Example: customers who bought at least 2 distinct items (Order(cust, item)).

\[ \begin{aligned} \large{T} &= \large{\sigma_{\text{item}_1 \neq \text{item}_2}\bigl( \rho_1(\text{Order}) \bowtie_{\text{cust}_1=\text{cust}_2} \rho_2(\text{Order}) \bigr)}\\ \large{RESULT} &= \large{\pi_{\text{cust}_1}(T)} \end{aligned} \]

For k=3, chain three renamings and pairwise item inequalities; project one cust.

Min / Max with self-join¶

Given \(R(\text{id}, \text{val})\), keep rows that are not beaten by a strictly better competitor.

Minimum(s): \(\large{MIN = R - \pi_{\text{r1.*}}\bigl( \sigma_{\text{r2.val} < \text{r1.val}}( \rho_1(R) \bowtie \rho_2(R) ) \bigr)}\)
Maximum(s): replace \(<\) with \(>\).

This is the same anti-dominance trick: remove any row that has a strictly smaller (or larger) partner with the same comparison domain.

Quick checklist¶

Before \(A - B\), ensure \(A\) and \(B\) have the same attributes (usually just the id).
For "only/all", always project ids in both CANDIDATES and INTRUDERS.
For self-join min/max, use strict inequality so ties survive (you keep all minima/maxima).
Rename consistently when self-joining to avoid attribute clashes.