Relational algebra gives a compact way to answer “what rows?” before a SQL dialect, a query plan, or a UI obscures the question. Its greatest practical use is not memorizing symbols. It is exposing a missing condition, an incompatible difference, or a changed result grain early.
The operators we will use
For a relation and predicate
- Selection keeps tuples satisfying
- Projection keeps named attributes and removes duplicate tuples under set semantics.
- Rename changes a relation or attribute name so an expression is well-formed.
- Product pairs every tuple of with every tuple of
- Join is a selected product with compatible joined attributes.
- Difference keeps tuples in that are not in and must have compatible schemas.
For a relation and predicate
- Selection keeps tuples satisfying
- Projection keeps named attributes and removes duplicate tuples under set semantics.
- Rename changes a relation or attribute name so an expression is well-formed.
- Product pairs every tuple of with every tuple of
- Join is a selected product with compatible joined attributes.
- Difference keeps tuples in that are not in and must have compatible schemas.
Trace a query, not just its notation
Use these fixed relations for region us-east.
Node:
node_id | tier |
|---|---|
| worker-01 | edge |
| worker-02 | core |
| worker-03 | edge |
RequiredService:
service_id |
|---|
| S101 |
| S201 |
Deployment:
node_id | service_id | region |
|---|---|---|
| worker-01 | S101 | us-east |
| worker-01 | S201 | us-east |
| worker-02 | S101 | us-east |
| worker-02 | S201 | eu-west |
| worker-03 | S101 | us-east |
Worked example. “Which nodes are hosting service S101 in us-east?” starts with selection, then projection:
The selected relation still has grain “one deployment.” The projected result has grain “one node that meets the condition.” That change is intentional.
Predict the intermediate result
What is the schema and tuple set of
HintExpandCollapse
Selection leaves all attributes in place; projection then drops only region.
Worked solutionExpandCollapse
Its schema is (node_id, service_id) and its tuples are (worker-01, S101), (worker-01, S201), (worker-02, S101), and (worker-03, S101). The result says that a node hosts a service during the chosen regional scope; it no longer states the region, so do not reuse it for a multi-region question without rebuilding the scope.
Make the same operations visible
The playground contains a separate fixed deployment fixture. Use it to perform one selection, compare bag versus set projection, and inspect an equijoin. Before each step, say whether you expect its output grain to be one deployment, one service, or a joined pair.
Execute an algebra operator over visible relations
Choose a logical operator and inspect its input/output tables. The model separates set projection from SQL’s default bag behavior.
Deployment
| node_id | service_id | region |
|---|---|---|
| worker-01 | S101 | us-east |
| worker-02 | S101 | us-east |
| worker-03 | S202 | eu-west |
| worker-01 | S202 | eu-west |
σ region = 'us-east' (Deployment)
| node_id | service_id | region |
|---|---|---|
| worker-01 | S101 | us-east |
| worker-02 | S101 | us-east |
Model scope: all values are non-NULL, the join key is unique in Service, and result order is deliberately unspecified. A real SQL optimizer must additionally preserve NULL, bag, collation, volatility, and outer-join semantics.
The static comparison keeps the input relations beside the result. The join has one output tuple for each deployment because Service.service_id is unique in this fixture.
Deployment
| node_id | service_id | region |
|---|---|---|
| worker-01 | S101 | us-east |
| worker-02 | S101 | us-east |
| worker-03 | S202 | eu-west |
| worker-01 | S202 | eu-west |
Service
| service_id | name |
|---|---|
| S101 | Auth API |
| S202 | Billing Worker |
Deployment ⋈ Deployment.service_id = Service.service_id Service
| node_id | service_id | region | name |
|---|---|---|---|
| worker-01 | S101 | us-east | Auth API |
| worker-02 | S101 | us-east | Auth API |
| worker-03 | S202 | eu-west | Billing Worker |
| worker-01 | S202 | eu-west | Billing Worker |
Static state: the equijoin carries each Deployment.service_id to the matching Service row and appends the service name; compare the input grain with the joined-pair grain.
“All required services” is a missing-pair problem
The word all often tempts people into a vague division operator. Derive it by enumerating what should exist and subtracting what is absent.
Expected and Deployed both have schema (node_id, service_id), so the difference is defined. For the data above, Missing contains (worker-02, S201), (worker-03, S201); Answer is {worker-01}.
Apply the derivation
A query specification requires finding nodes that host every required service and belong to the edge tier. Where should the tier condition go: in Deployed, Expected, or the final answer?
HintExpandCollapse
The tier condition restricts which nodes are required to satisfy all pairs, not what counts as a matching deployment.
Worked solutionExpandCollapse
Restrict the candidate nodes before forming expected pairs:
Then use the same Missing and final subtraction pattern with Eligible. Filtering only the final answer can be correct for a simple output filter, but it unnecessarily constructs missing pairs for nodes that were never candidates and obscures the requirement.
A rewrite needs stated assumptions
Algebra helps explain why an optimizer can sometimes move work earlier.
For set relations, an inner join, and a two-valued predicate that mentions only attributes of
For set relations, an inner join, and a two-valued predicate that mentions only attributes of
ProofExpand proofCollapse
A joined tuple survives the left expression exactly when its R component satisfies Because the predicate reads no S attribute, filtering R first removes exactly those same joined tuples. The statement does not claim the two expressions have equal cost, nor does it cover outer joins or SQL’s three-valued predicate behavior.
Counterexample. With a left outer join, moving a predicate about the right relation from
WHEREinto a pre-join filter can preserve unmatched left rows that the originalWHEREcondition removes. For example, ifRhas one row andShas none,WHERE S.flag = 'Y'removes the null-extended row after the join. The same condition inside the right input still lets the left outer join emit it. The expressions are not interchangeable.
Check a proposed rewrite
An engineer changes
to
List the three facts you would check before accepting the rewrite.
HintExpandCollapse
Match the proposition's assumptions one by one.
Worked solutionExpandCollapse
Check that the join is inner, the predicate reads only R attributes, and the intended semantics support the stated selection law (including how duplicate rows and NULL values are handled in the actual SQL dialect). Also confirm that region means the same thing at this point in the expression; an alias or prior rename can change that fact.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 1.3.1: Intermediate Schema and Tuple Projection
Given relation schema and selection determine the schema and result grain of Explain why dropping affects subsequent multi-region queries.
HintExpandCollapse
Selection preserves all attributes; projection then retains only node_id and service_id.
Worked solutionExpandCollapse
The output schema is with tuples representing nodes actively hosting a service in us-east. Because is omitted from the projected schema, the output relation loses geographic context and cannot be directly intersected with other regions without reapplying a region qualifier.
Exercise 1.3.2: Inner-Join Pushdown Precondition Check
An engineer proposes rewriting into Referring to Proposition 1.3.2
HintExpandCollapse
Check predicate attribute dependency and outer-join null extension semantics.
Worked solutionExpandCollapse
Under two-valued set semantics, the rewrite is valid because the selection predicate references only attributes of and the join is an inner equijoin. For a left outer join where the predicate references instead (e.g. pushing the predicate into retains non-matching tuples with NULL padding, whereas the post-join filter eliminates them.
Exercise 1.3.3: Universal Division via Difference Formulation
Let and be set relations. Using relational algebra operators from Definition 1.3.1edge tier that host every service in in region us-east.
HintExpandCollapse
Restrict candidate nodes first before constructing the Cartesian product of expected pairs.
Worked solutionExpandCollapse
Define candidate edge nodes and expected pairs:
Filtering candidates before forming the product avoids generating missing pairs for unrelated tiers.
Exercise 1.3.4: Constrained Core-Service Deployment Derivation
Let and be set relations. Derive an algebra expression for nodes that host every core service in us-east but host no non-core service in that region. State the compatibility of schemas in every difference operation.
HintExpandCollapse
Derive universal deployment of Core, then subtract the set of nodes with non-core deployments.
Worked solutionExpandCollapse
First isolate us-east deployments: Compute nodes hosting all core services:
Next isolate non-core services: (both schema Find nodes with any non-core service: The final answer is Both operands have schema