The Relational Model and Relational Algebra

Relations, tuples, attributes and domains, schema vs instance, superkeys, candidate, primary and foreign keys, and the relational algebra — selection, projection, set operations, Cartesian product, renaming, joins (theta, equi, natural, outer), intersection and division — with set semantics, result-size bounds, algebraic equivalences and query trees.

Relations

A relation is a set of tuples (rows) over a fixed list of attributes (columns), each attribute taking values from a domain.

Schema: Student(sid, name, dept, cgpa) — the structure. Instance: the current set of tuples.
Degree (arity) = number of attributes; cardinality = number of tuples.
Relations are sets: no duplicate tuples and no inherent order of rows. (SQL tables are bags — duplicates allowed.)
Values are atomic (first normal form).

Keys

Key	Definition
Superkey	a set of attributes whose values uniquely identify each tuple
Candidate key	a minimal superkey (no proper subset is a superkey)
Primary key	the candidate key chosen to identify tuples; cannot be NULL
Alternate key	a candidate key not chosen as primary
Foreign key	attributes referencing the primary key of another (or the same) relation

A relation with $n$ attributes has at most $2^n - 1$ superkeys. If $\{A\}$ is a candidate key of $R(A, B, C)$ , every superset of $\{A\}$ is a superkey: $2^{n-1} = 4$ superkeys.

Relational algebra

A procedural query language: each operator takes relations and returns a relation, so operators compose.

Operator	Notation	Result
Selection	$\sigma_{\text{cond}}(R)$	rows satisfying the condition
Projection	$\pi_{A_1,\dots,A_k}(R)$	chosen columns, duplicates removed
Union	$R \cup S$	tuples in either (schemas must be union-compatible)
Difference	$R - S$	tuples in $R$ not in $S$
Intersection	$R \cap S$	tuples in both
Cartesian product	$R \times S$	all pairs; $\lvert R\rvert\cdot\lvert S\rvert$ tuples
Rename	$\rho_{T(B_1,\dots)}(R)$	same tuples, new names
Theta join	$R \bowtie_\theta S = \sigma_\theta(R \times S)$	pairs satisfying $\theta$
Equi-join	theta join with only equality conditions
Natural join	$R \bowtie S$	equi-join on all common attributes, common columns kept once
Outer joins	⟕, ⟖, ⟗	join plus unmatched tuples padded with NULL
Division	$R \div S$	values of $R$ 's other attributes paired with all of $S$
Semi-join	$R \ltimes S$	tuples of $R$ that have a match in $S$

Size bounds

Expression	Min tuples	Max tuples
$\sigma(R)$	0	$\lvert R\rvert$
$\pi(R)$	1 (if $R$ non-empty)	$\lvert R\rvert$
$R \cup S$	$\max(\lvert R\rvert, \lvert S\rvert)$	$\lvert R\rvert + \lvert S\rvert$
$R \cap S$	0	$\min(\lvert R\rvert, \lvert S\rvert)$
$R - S$	0	$\lvert R\rvert$
$R \times S$	$\lvert R\rvert\cdot\lvert S\rvert$	$\lvert R\rvert\cdot\lvert S\rvert$
$R \bowtie S$	0	$\lvert R\rvert\cdot\lvert S\rvert$
$R \bowtie S$ , common attribute is a key of $S$	0	$\lvert R\rvert$
R ⟕ S	$\lvert R\rvert$	$\lvert R\rvert\cdot\lvert S\rvert$

Division, carefully

For $R(X, Y)$ and $S(Y)$ , $R \div S = \{x : \forall y \in S,\ (x, y) \in R\}$ :

R \div S = \pi_X(R) - \pi_X\big((\pi_X(R) \times S) - R\big).

Read it as: all candidates, minus those that are missing some required $y$ .

Equivalences used by query optimisers

Cascade and commute selections: $\sigma_{p\wedge q}(R) = \sigma_p(\sigma_q(R)) = \sigma_q(\sigma_p(R))$ .
Push selections down below joins: $\sigma_p(R \bowtie S) = \sigma_p(R) \bowtie S$ if $p$ uses only $R$ 's attributes — filter early, join smaller relations.
Push projections down (keeping join attributes).
Joins are commutative and associative — join order is the optimiser's main choice.
$\pi$ distributes over $\cup$ but not over $-$ or $\cap$ .

Pushing the selection below the join shrinks the join input.