Relational Algebra

Everything else is shorthand. R ⋈ S is a product followed by a selection on the shared attributes and a projection to remove the duplicate column. Intersection is R − (R − S). Division, natural join and theta join are all definable from the six.

Every operator returns a relation. That closure property is what allows operators to be stacked into an expression, and is why the algebra is a language rather than a list of tricks.

Functional dependency (X → Y)

Knowing X pins down Y. If two rows agree on X they must agree on Y. This is a statement about the world being modelled, not about the rows that happen to be in the table today.

Superkey and candidate key

A superkey determines every attribute in the relation. A candidate key is a superkey with nothing spare in it — remove any attribute and it stops working.

Prime attribute

One that appears in some candidate key. The normal forms are mostly rules about how non-prime attributes are allowed to depend on prime ones.

Partial dependency

A non-prime attribute determined by only part of a composite key. Forbidden by 2NF, and the direct cause of the update, insert and delete anomalies.

Transitive dependency

Key → X → Y where X is not a key. Forbidden by 3NF: the fact really belongs in a table keyed by X.

Lossless decomposition

Splitting a relation so that re-joining it gives back exactly the original rows — no more, no fewer. Guaranteed when the shared attribute is a key of one of the two pieces.

• Duplicates. A relation is a set, so π removes duplicates automatically. SQL's SELECT keeps them unless you write DISTINCT — SQL operates on multisets.
• Nulls. The algebra has none. SQL's three-valued logic is an extension with no counterpart here.
• Order. Neither has any. ORDER BY is applied after the algebra has finished.
• Aggregation and grouping are additions to the algebra, not part of the classical six.

SQL says what is wanted; the algebra says how, and equivalent expressions can differ enormously in cost. The optimiser's job is to generate equivalent forms and pick the cheapest, using rewrite rules that the algebra makes provably safe:

• Push selections down. σ(R ⋈ S) becomes σ(R) ⋈ σ(S) where the conditions allow. Filtering before joining is the single most valuable rewrite there is.
• Push projections down. Discard unneeded columns early so less data moves.
• Reorder joins. Joins are associative and commutative, so the order is free to choose — and with n relations there are exponentially many orders, which is why join ordering is the hard part of query planning.

Filter-then-join and join-then-filter return identical answers. One may touch a thousand rows and the other ten million.