Relational Model & Relational Algebra

The relational model is not “data in rectangular files.” It is a separation of concerns: users describe what relation they want, an algebra gives that request precise meaning, constraints define which database states are legal, and the engine is free to choose a physical representation and execution plan. That logical/physical boundary is why an index, partitioning scheme, or join algorithm can change without changing the meaning of a correct query.

The theory is deliberately small. A relation is a set of typed tuples; every query operator consumes relations and produces another relation. From that closure property comes composability, equivalence reasoning, views, and most rule-based query optimization.

Four layers that must not be conflated #

flowchart TD
  W["Real-world facts"] --> S["Schema and constraints"]
  S --> R["Relation values"]
  R --> A["Relational expression"]
  A --> P["Physical execution plan"]
  P --> O["Result relation"]

The formal object #

Let each attribute $A_i$ have a domain $D_i$. A relation schema

$$R(A_1:D_1, A_2:D_2, \ldots, A_n:D_n)$$

names the attributes and their domains. A tuple $t$ is a finite mapping from attribute names to domain values, so $t[A_i] \in D_i$. A relation value (often called an instance) is a finite set of such tuples:

$$r(R) \subseteq D_1 \times D_2 \times \cdots \times D_n.$$

Using attribute names rather than only positions matters: it makes projection, renaming, and natural join precise without treating the third physical column as part of the fact's identity.

Heading

The schema: attribute names and domains.

Body

The current set of tuples satisfying that heading and the declared constraints.

Degree (arity)

The number of attributes in the heading.

Cardinality

The number of tuples in the body.

A mathematical relation has three consequences that SQL users often overlook:

• tuples are unordered;
• attributes are identified by name, not display position;
• duplicate tuples do not exist because the body is a set.

The empty relation is valid. So are a zero-degree relation containing no tuple (false) and a zero-degree relation containing the single empty tuple (true): they are the relational counterparts of Boolean values and explain why closed relational expressions can represent predicates as well as data.

A running database #

We will use three relation schemas:

$$\begin{aligned} Supplier&(sid, name, city) \\ Product&(pid, label, category) \\ Supplies&(sid, pid, price) \end{aligned}$$

with the following small instances:

Supplier

Product

Supplies

One Supplies tuple means one supplier offers one product at one price. That sentence is part of the schema contract. If prices vary by currency, quantity, or validity interval, those attributes—or separate relations representing those facts—must be added. A table cannot repair an underspecified predicate.

Integrity constraints define legal states #

Domains say which individual values are admissible. Constraints say which combinations of tuples form a legal database state.

Keys #

For an attribute set $K \subseteq attrs(R)$, $K$ is a superkey when no two distinct tuples in any legal instance agree on every attribute in $K$. A candidate key is a minimal superkey: removing any attribute destroys uniqueness. One candidate key may be designated the primary key; the remaining candidate keys are alternate keys. “Primary” is a schema/implementation choice, not a stronger mathematical kind of key.

In the running example:

• Supplier.sid and Product.pid are candidate keys;
• (Supplies.sid, Supplies.pid) is a candidate key if each supplier has at most one current offer per product;
• (sid, pid, price) is a superkey but not a candidate key, because price is redundant for uniqueness.

Referential and general constraints #

A foreign key from Supplies.sid to Supplier.sid requires every non-null referencing value to identify an existing supplier. Likewise for pid. This is referential integrity: the database cannot assert an offer for a supplier or product absent from the referenced relation.

Other invariants include:

• domain constraints: price is numeric;
• tuple constraints: price > 0;
• relation constraints: no two active offers share (sid, pid);
• cross-relation constraints: every offer references a supplier and product.

SQL exposes these through types, NOT NULL, CHECK, UNIQUE, PRIMARY KEY, FOREIGN KEY, and sometimes exclusion constraints or triggers. Their exact null and timing semantics are implementation concerns layered on the logical invariant.

The algebra: operators that stay inside the model #

If $R$ and $S$ are relations, relational algebra builds expressions from a small operator set. Closure means every well-typed result is itself a relation, so it can feed the next operator.

Selection chooses tuples #

$$\sigma_{\theta}(R) = \{t \in R \mid \theta(t)\}$$

Selection preserves the heading and keeps tuples satisfying predicate $\theta$. Kyiv suppliers are:

$$\sigma_{city = \text{"Kyiv"}}(Supplier).$$

It is a horizontal restriction: fewer rows, same attributes.

Projection chooses attributes #

$$\pi_X(R) = \{t[X] \mid t \in R\}$$

Projection keeps attributes $X$ and removes duplicates created by discarding distinguishing attributes. Supplier cities are $\pi_{city}(Supplier)=\{\text{Kyiv},\text{Lviv}\}$, not three rows.

Projection is existential quantification in disguise. From a ternary predicate Supplies(sid,pid,price), projecting (sid,pid) asks whether some price makes the original predicate true.

Rename makes schemas composable #

The rename operator $\rho$ changes a relation or attribute name without changing tuples. It is essential for self-joins and for making headings compatible:

$$\rho_{S_1(sid_1,name_1,city_1)}(Supplier).$$

Renaming is not cosmetic when names carry operator semantics. A natural join matches equally named attributes; careless names can therefore change a query.

Set operators combine compatible relations #

For union-compatible relations—same attribute names with corresponding domains—set union, intersection, and difference have their ordinary meanings:

$$R \cup S, \qquad R \cap S, \qquad R - S.$$

Difference is the expressive step that supports “has no,” “all,” and anti-join-style questions. It is also non-monotone: adding input tuples can remove result tuples.

Cartesian product combines every pair #

After resolving duplicate attribute names,

$$R \times S = \{t \cup u \mid t \in R, u \in S\}.$$

Its cardinality is $|R||S|$. A product is rarely the intended final answer, but it is the substrate of joins: first consider pairs, then retain pairs that satisfy a relationship.

Join combines related facts #

A theta join is selection over a product:

$$R \bowtie_{\theta} S = \sigma_{\theta}(R \times S).$$

An equijoin uses equality conditions. A natural join equates every same-named attribute and emits one copy of each matched attribute. The supplier names attached to offers can be expressed as:

$$Supplier \bowtie_{Supplier.sid = Supplies.sid} Supplies.$$

Join does not mean “look up by foreign key.” A foreign key is an integrity constraint; a join is a query operator. Joins can use non-key conditions, and a foreign key can exist without a query joining the tables.

Semijoin and antijoin answer existence questions #

A left semijoin keeps only the left tuples that have at least one match:

$$R \ltimes S = \pi_{attrs(R)}(R \bowtie S).$$

An antijoin keeps those with no match. These are useful mental models for SQL EXISTS and NOT EXISTS, and they prevent accidental row multiplication when the question asks only whether a related tuple exists.

Division expresses “for every” #

Suppose $R(X,Y)$ records pairs and $S(Y)$ lists required values. Division returns each $X$ related to every $Y$ in $S$:

$$R \div S = \{x \mid \forall y \in S,\ (x,y) \in R\}.$$

An expression using primitive set operators is:

$$\pi_X(R) - \pi_X\big((\pi_X(R) \times S) - R\big).$$

Read it causally:

1. form every candidate $x$ paired with every required $y$;
2. subtract the pairs that actually exist—what remains are missing requirements;
3. project the failing $x$ values;
4. subtract failures from all candidates.

For “suppliers that supply every electronic product,” let

$$E = \pi_{pid}(\sigma_{category=\text{"electronic"}}(Product))$$

and then compute

$$\pi_{sid,pid}(Supplies) \div E.$$

Only supplier 3 qualifies in the running data.

A complete query derivation #

Question: Which Kyiv suppliers offer an electronic product for less than 2?

Work from meaning to operators:

1. restrict suppliers by city;
2. restrict products by category;
3. restrict offers by price;
4. join the three relations on their identifiers;
5. project the requested supplier attributes.

$$\pi_{sid,name}\left( \sigma_{city=\text{"Kyiv"}}(Supplier) \bowtie \sigma_{price<2}(Supplies) \bowtie \sigma_{category=\text{"electronic"}}(Product) \right)$$

The result is {(1, Ada Parts), (3, Circuit House)}.

One SQL rendering is:

SELECT DISTINCT s.sid, s.name
FROM supplier AS s
JOIN supplies AS x ON x.sid = s.sid
JOIN product AS p ON p.pid = x.pid
WHERE s.city = 'Kyiv'
  AND x.price < 2
  AND p.category = 'electronic';

DISTINCT preserves the set-valued algebraic result when one supplier has multiple matching offers. Without it, SQL returns one output row per matching join combination.

Why equivalent expressions matter #

Because operators have algebraic laws, many syntactically different expressions denote the same relation. A query optimizer exploits exactly that freedom.

For predicates $\theta_1$ and $\theta_2$:

$$\sigma_{\theta_1 \land \theta_2}(R) = \sigma_{\theta_1}(\sigma_{\theta_2}(R)).$$

If $\theta$ mentions only attributes of $R$:

$$\sigma_{\theta}(R \bowtie S) = (\sigma_{\theta}(R)) \bowtie S.$$

The second form can discard tuples before the join. If Supplier has one million rows but only 2,000 Kyiv rows, early selection can shrink both memory and comparison work without changing meaning.

Projection can similarly be pushed down when every attribute needed by later predicates and joins is retained. The caveat is the lesson: transformations are justified by schemas and laws, not by visual resemblance.

SQL is relationally inspired, not identical #

The distinction is not pedantry; it predicts real bugs.

Null changes logical laws #

In SQL, x = NULL is not true or false; it is unknown. Use IS NULL to test the marker. A CHECK constraint in PostgreSQL is satisfied when its expression is true or null, so CHECK (price > 0) does not imply price IS NOT NULL. Declare both when both are invariants.

Unique constraints also need explicit null reasoning. PostgreSQL normally treats nulls as distinct for uniqueness, while UNIQUE NULLS NOT DISTINCT makes them collide. Neither behavior should be smuggled into the mathematical definition of a key; decide the domain semantics first, then choose matching SQL constraints.

Bags explain duplicate explosions #

If a supplier has three matching offers and the query projects only its name, plain SQL can return that name three times. That is not the engine “duplicating data”; it is the correct multiplicity of the joined bag. Ask which semantics the result needs:

• preserve occurrences because each match is meaningful;
• use EXISTS because only existence matters;
• aggregate because the question asks for a count or total;
• use DISTINCT because the intended mathematical result is a set.

Using DISTINCT blindly at the top often hides an incorrect join predicate.

Logical design before physical design #

A reliable modelling pass proceeds in this order:

1. Write the fact sentence. What does one tuple assert?
2. Name attributes and domains. Include units, time scope, currency, and identity semantics.
3. State candidate keys. Explain why each is guaranteed across all legal states.
4. State dependencies and constraints. Which values determine others? Which references must exist?
5. Normalize where dependencies create anomalies. This is covered in Functional Dependencies & Normalization.
6. Write representative relational queries. Ensure the schema can answer required questions without inventing meaning.
7. Only then choose indexes and storage. Those optimize the workload; they do not define the facts.

Diagnostic reasoning #

When a query or schema behaves unexpectedly, ask in this order:

1. What fact does one input tuple mean?
2. Which keys and foreign keys are actually enforced?
3. Is the intended result a set, a bag, or an aggregate?
4. Can one left tuple match several right tuples? Should it?
5. Does a predicate evaluate to unknown because of null?
6. Is a filter applied before or after an outer join creates null-extended rows?
7. Is ordering explicitly requested?
8. Which algebraic expression describes the intended result before SQL syntax?
9. Only after semantics are correct: which physical plan did the optimizer choose and why?

This ordering separates two very different failures: a wrong result relation and an inefficient plan for a correct relation.

Exercises #

1. Express “products supplied by no Kyiv supplier” with difference or antijoin.
2. Explain why projecting city from Supplier changes cardinality from 3 to 2 in relational algebra but not necessarily in SQL.
3. Show the difference between “suppliers that provide at least one electronic product” and “suppliers that provide every electronic product.”
4. Decide whether (sid,pid,price) is a candidate key when (sid,pid) is already guaranteed unique.