Relational algebra & database theory

#Bonus: why relational algebra matters to a .NET engineerBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

A query can be syntactically valid and still return wrong totals because of join multiplicity, duplicates or filter placement. Relational algebra gives you a small language for decomposing a query and reviewing EF-generated or AI-generated SQL. This entire topic is optional; understand the result before debating execution speed.

A relation is a set of tuples sharing a schema. A tuple is a row, an attribute is a named column, and a domain is its permitted set of values. The theoretical relation has no ordering or duplicates; a SQL table can contain duplicates and NULLs. Algebra examples use set semantics; SQL uses DISTINCT where that distinction matters.

SELECT Id, Name FROM Products ORDER BY Id; -- (1)

#σ, π and ρ: rows, columns and namesBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

A product screen asking only for book names should not load every row and column. Selection σ filters rows. Projection π selects attributes and removes duplicates in the algebra. Rename ρ names a relation or its attributes to remove ambiguity, especially in self joins.

SELECT * FROM Products WHERE Category = 'Books';       -- (1) σ
SELECT DISTINCT Category FROM Products;               -- (2) π
SELECT P.Id AS ProductId, P.Name FROM Products AS P;   -- (3) ρ

Do not discard a join key before it is needed. DISTINCT can hide a join bug; understand why duplicates appear first.

#∪, − and ∩: set operationsBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

Customers who bought this month or last month require union; those in both require intersection; those who bought previously but did not return require difference. Inputs must be union-compatible: the same number of attributes with compatible domains, renaming attributes where needed.

SELECT UserId FROM A UNION SELECT UserId FROM B;       -- (1)
SELECT UserId FROM A EXCEPT SELECT UserId FROM B;      -- (2)
SELECT UserId FROM A INTERSECT SELECT UserId FROM B;   -- (3)

Use UNION ALL when duplicates should remain; unnecessary deduplication adds work. These combine result rows, unlike a join that combines attributes. SQL details: Combining queries.

#× and ⋈: from all pairs to joinsBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

A Cartesian product × forms every pair. Two P rows and three O rows produce six pairs. A theta join selects pairs satisfying a predicate θ; an equi-join uses equality predicates. A natural join implicitly equates all same-named attributes and keeps one copy of them, so adding another shared name can unexpectedly change results.

SELECT P.Id, O.OrderId FROM P CROSS JOIN O;                 -- (1)
SELECT P.Id, O.OrderId FROM P
JOIN O ON P.Id = O.ProductId;                              -- (2)
SELECT P.Id, O.OrderId FROM P
JOIN O ON P.Price < O.MaxPrice;                            -- (3)
-- Natural join equivalent with explicit matching names after rename:
SELECT P.Id, P.Price, O.OrderId, O.MaxPrice
FROM P JOIN O ON P.Id = O.ProductId;                       -- (4)

Check cardinality before SUM: a one-to-many join may repeat an order amount for every line. Do not use CROSS JOIN when a relationship predicate is required.

#Outer joins, ⋉ and ▷: matching and absenceBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

Imagine Users on the left and Orders on the right: a join connects rows when their key values match. An inner join returns matches only. A left outer join keeps every user, even without an order, and puts NULL where matching order data is missing; here NULL means “no matching value,” not zero. Right reverses the sides, and full preserves unmatched rows from both. These extend classical algebra, which has no NULL. A semi-join ⋉ returns users who have orders without order columns or duplicate users when they have several orders. Here an anti-join ▷ returns users with no order; notation varies between references.

Left join produces (1,10), (1,11), (2,NULL). Right produces (NULL,12) instead of (2,NULL). Full produces all four.

SELECT U.Id, O.Id AS OrderId FROM Users U
LEFT JOIN Orders O ON O.UserId = U.Id;                     -- (1)
SELECT U.Id, O.Id AS OrderId FROM Users U
RIGHT JOIN Orders O ON O.UserId = U.Id;
SELECT U.Id, O.Id AS OrderId FROM Users U
FULL OUTER JOIN Orders O ON O.UserId = U.Id;
SELECT U.Id FROM Users U WHERE EXISTS
    (SELECT 1 FROM Orders O WHERE O.UserId = U.Id);         -- (2)
SELECT U.Id FROM Users U WHERE NOT EXISTS
    (SELECT 1 FROM Orders O WHERE O.UserId = U.Id);         -- (3)

Put a right-side filter in ON when unmatched left rows must survive. A subsequent WHERE O.Status = 'Paid' rejects NULLs and commonly changes the effective meaning to an inner join.

#÷ and γ: all required items and aggregationBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

Division ÷ asks “who bought every required product?” Given Bought(UserId, ProductId) and Required(ProductId), it returns users paired with every Required product. Aggregation γ belongs to extended algebra and groups rows to calculate counts or sums.

-- Candidate users are the users occurring in Bought, as in division.
SELECT DISTINCT B.UserId FROM Bought B
WHERE NOT EXISTS (
    SELECT 1 FROM Required R
    WHERE NOT EXISTS (
        SELECT 1 FROM Bought B2
        WHERE B2.UserId = B.UserId AND B2.ProductId = R.ProductId)); -- (1)

-- γ UserId; COUNT(*)→ItemCount (Bought)
SELECT UserId, COUNT(*) AS ItemCount
FROM Bought GROUP BY UserId;                                   -- (2)

A GROUP BY/HAVING alternative must handle duplicates and an empty required set correctly. Division is not numeric division and is unnecessary for “any product,” which needs a single EXISTS.

#Equivalences and query trees: optimizer reasoningBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

If a query joins a million orders before filtering paid ones, pushing the selection below the join may reduce intermediate rows. This is a logical equivalence, not a promise of a particular physical plan. The optimizer weighs statistics, indexes and join-algorithm costs.

Before:                             After:
π U.Name, O.Id                      π U.Name, O.Id
       |                                   |
σ O.Status='Paid'                         ⋈ U.Id=O.UserId
       |                                /               \
⋈ U.Id=O.UserId                       Users       σ Status='Paid'   (1)
 /           \                                          |
Users       Orders                                    Orders

SELECT U.Name, O.Id FROM Users U
JOIN Orders O ON U.Id = O.UserId
WHERE O.Status = 'Paid';                         -- (2)

Do not apply these rules blindly to outer joins, LIMIT, aggregates or nondeterministic expressions. Projection pushdown must retain keys and attributes needed by joins and predicates. Inspect the actual plan rather than judging the SQL's appearance.

#SQL bags and NULL: where direct translation breaksBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

SQL normally uses bags: duplicates are part of the result. Prices 20, 20, 100 produce three rows with SELECT Price but only 20 and 100 with theoretical projection. Joins multiply multiplicities; DISTINCT at the end can hide a bug without repairing a SUM computed earlier.

NULL is not an unknown value that equals itself. Comparisons involving it generally produce UNKNOWN; WHERE and HAVING keep only TRUE. NOT UNKNOWN remains UNKNOWN; FALSE AND UNKNOWN is FALSE, while TRUE OR UNKNOWN is TRUE.

SELECT Price FROM Products;                         -- (1) preserves duplicates
SELECT DISTINCT Price FROM Products;
SELECT UserId FROM A UNION ALL SELECT UserId FROM B; -- (2) preserves duplicates
SELECT Id FROM Products WHERE Price IS NULL;        -- (3)
SELECT U.Id FROM Users U WHERE NOT EXISTS (
    SELECT 1 FROM Orders O WHERE O.UserId = U.Id);    -- (4)

Duplicate elimination treats NULLs as not distinct from each other even though NULL = NULL is not TRUE. Do not infer set-operator behavior solely from WHERE comparisons.

#Functional dependencies, closure and keysBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

Assume a table has one row per product on an order. One OrderId can appear on several rows, but those rows belong to the same user. If each OrderId has exactly one allowed UserId, write OrderId → UserId. This functional dependency is a rule about every valid version of the data: any two rows agreeing on the left must agree on the right, not just in the sample shown. The arrow does not imply the reverse or a cause-and-effect relationship. We will use these rules to find which columns distinguish one order line.

Before the calculation: the closure of a set of columns is every column we can infer from it by repeatedly applying the rules. If its closure reaches every table column, the set is a superkey that identifies a row; if no smaller subset does, it is a candidate key. The primary key is the candidate key chosen for the table.

R(OrderId, UserId, UserEmail, ProductId, Qty)
Assumed rules: one line per product per order.
FDs:
  OrderId → UserId
  UserId → UserEmail
  OrderId, ProductId → Qty

{OrderId}+ = {OrderId, UserId, UserEmail}                    (1)
{OrderId, ProductId}+ = all attributes of R                 (2)

A superkey identifies a tuple; a candidate key is a minimal superkey with no removable attributes; a primary key is a selected candidate. Minimal does not mean shortest among all candidates. We did not assume unique email; add that rule and recalculate if it applies.

CREATE TABLE OrderLines (
    OrderId int NOT NULL,
    ProductId int NOT NULL,
    Qty int NOT NULL,
    PRIMARY KEY (OrderId, ProductId)
);

The primary key enforces uniqueness of the pair; it does not automatically establish the other dependencies.

#Normalization from FDs, and calculus versus algebraBonus

Optional but valuable: not asked in every interview, but knowing it deepens your understanding and sets you apart.

Repeating UserEmail on every order line causes update anomalies: one row changes and another is forgotten. Decompose according to dependencies, not merely because a table is large.

A prime attribute belongs to some candidate key. With a single simple key, “no transitive dependency of non-key attributes” is useful intuition, not a substitute for the general 3NF definition.

Users(UserId PK, UserEmail)                              (1)
Orders(OrderId PK, UserId FK)
OrderLines(OrderId FK, ProductId, Qty, PK(OrderId, ProductId))

Lossless reconstruction:
Users ⋈ Orders ⋈ OrderLines                              (2)

SELECT O.OrderId, U.UserId, U.UserEmail, L.ProductId, L.Qty
FROM Orders O JOIN Users U ON U.UserId = O.UserId
JOIN OrderLines L ON L.OrderId = O.OrderId;               -- (3)

Relational calculus describes desired tuples through predicates and quantifiers; algebra expresses compositions of operators. Safe, domain-independent calculus and classical algebra have equivalent expressive power. SQL is declarative and related to this logic, but bags, NULL and aggregation require additional care. Algebra is not a physical execution plan imposing a fixed runtime order.

Do not denormalize before measuring a bottleneck and assigning responsibility for updating copies. Further reading: Relational algebra and normalization.