Search Knowledge

© 2026 LIBREUNI PROJECT

Database Systems/Data contracts, relations, and SQL
Page 3 of 20

Relational algebra: derive a query before SQL

Use selection, projection, joins, difference, and product to state precisely which tuples a query should return.

Lesson briefData contracts, relations, and SQL · 7 h · 3 outcomes

Required knowledge

  • Relation schemas, instances, keys, and grain
  • Sets, predicates, Cartesian products, and functions

Learning outcomes

  • Translate a scoped data question into relational-algebra operators with compatible schemas.
  • Trace an algebra expression over small relations and state the grain of every intermediate result.
  • Justify or reject a simple inner-join rewrite, including its semantic preconditions.

Assessment target

Given a deployment dataset and a requirement involving all required services, derive an algebra expression, trace it, and identify one unsafe rewrite under outer-join or bag semantics.

Scope boundary

  • Full query-optimizer search, SQL window functions, recursion, and cost estimation are outside this lesson.

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

Definition 1.3.1Set-relational operators

For a relation RR and predicate θ\theta

σθ(R)={t∈R∣θ(t)}\sigma_{\theta}(R) = \{t \in R \mid \theta(t)\}
  • Selection σθ(R)\sigma_{\theta}(R) keeps tuples satisfying θ\theta
  • Projection πA,B(R)\pi_{A,B}(R) keeps named attributes and removes duplicate tuples under set semantics.
  • Rename ρnew_name←old_name(R)\rho_{new\_name \leftarrow old\_name}(R) changes a relation or attribute name so an expression is well-formed.
  • Product R×SR \times S pairs every tuple of RR with every tuple of SS
  • Join R⋈R.a=S.aSR \bowtie_{R.a = S.a} S is a selected product with compatible joined attributes.
  • Difference R−SR - S keeps tuples in RR that are not in SS RR and SS must have compatible schemas.

Trace a query, not just its notation

Use these fixed relations for region us-east.

Node:

node_idtier
worker-01edge
worker-02core
worker-03edge

RequiredService:

service_id
S101
S201

Deployment:

node_idservice_idregion
worker-01S101us-east
worker-01S201us-east
worker-02S101us-east
worker-02S201eu-west
worker-03S101us-east

Worked example. “Which nodes are hosting service S101 in us-east?” starts with selection, then projection:

πnode_id(σservice_id=’S101’∧region=’us-east’(Deployment))={worker-01,worker-02,worker-03}.\pi_{node\_id}\bigl(\sigma_{service\_id = \text{'S101'} \land region = \text{'us-east'}}(Deployment)\bigr) = \{\text{worker-01}, \text{worker-02}, \text{worker-03}\}.

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

πnode_id,service_id(σregion=’us-east’(Deployment))?\pi_{node\_id,service\_id}\bigl(\sigma_{region = \text{'us-east'}}(Deployment)\bigr)?
HintExpand

Selection leaves all attributes in place; projection then drops only region.

Worked solutionExpand

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.

Interactive exploration

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.

Selection keeps only us-east tuples; it does not change their attributes.
Relational operator

Deployment

Deployment
node_idservice_idregion
worker-01S101us-east
worker-02S101us-east
worker-03S202eu-west
worker-01S202eu-west

σ region = 'us-east' (Deployment)

σ region = 'us-east' (Deployment)
node_idservice_idregion
worker-01S101us-east
worker-02S101us-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.

Execute an algebra operator over visible relations

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

Deployment
node_idservice_idregion
worker-01S101us-east
worker-02S101us-east
worker-03S202eu-west
worker-01S202eu-west

Service

Service
service_idname
S101Auth API
S202Billing Worker

Deployment ⋈ Deployment.service_id = Service.service_id Service

Deployment ⋈ Deployment.service_id = Service.service_id Service
node_idservice_idregionname
worker-01S101us-eastAuth API
worker-02S101us-eastAuth API
worker-03S202eu-westBilling Worker
worker-01S202eu-westBilling 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.

Deployed=πnode_id,service_id(σregion=’us-east’(Deployment))Expected=πnode_id(Node)×RequiredServiceMissing=Expected−DeployedAnswer=πnode_id(Node)−πnode_id(Missing)\begin{aligned} Deployed &= \pi_{node\_id,service\_id}\bigl(\sigma_{region = \text{'us-east'}}(Deployment)\bigr) \\ Expected &= \pi_{node\_id}(Node) \times RequiredService \\ Missing &= Expected - Deployed \\ Answer &= \pi_{node\_id}(Node) - \pi_{node\_id}(Missing) \end{aligned}

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?

HintExpand

The tier condition restricts which nodes are required to satisfy all pairs, not what counts as a matching deployment.

Worked solutionExpand

Restrict the candidate nodes before forming expected pairs:

Eligible=σtier=’edge’(Node),Expected=πnode_id(Eligible)×RequiredService.Eligible = \sigma_{tier = \text{'edge'}}(Node), \qquad Expected = \pi_{node\_id}(Eligible) \times RequiredService.

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.

Proposition 1.3.2Safe inner-join selection pushdown

For set relations, an inner join, and a two-valued predicate θR\theta_R that mentions only attributes of RR

σθR(R⋈R.a=S.aS)=σθR(R)⋈R.a=S.aS.\sigma_{\theta_R}(R \bowtie_{R.a = S.a} S) = \sigma_{\theta_R}(R) \bowtie_{R.a = S.a} S.
ProofExpand proof

A joined tuple survives the left expression exactly when its R component satisfies θR\theta_R 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 WHERE into a pre-join filter can preserve unmatched left rows that the original WHERE condition removes. For example, if R has one row and S has 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

σR.region=’us-east’(R⋈R.node_id=S.node_idS)\sigma_{R.region = \text{'us-east'}}(R \bowtie_{R.node\_id = S.node\_id} S)

to

σR.region=’us-east’(R)⋈R.node_id=S.node_idS.\sigma_{R.region = \text{'us-east'}}(R) \bowtie_{R.node\_id = S.node\_id} S.

List the three facts you would check before accepting the rewrite.

HintExpand

Match the proposition's assumptions one by one.

Worked solutionExpand

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.

Section Exercises

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

Descriptionrecall

Given relation schema Deployment(node_id,service_id,region)Deployment(node\_id, service\_id, region) and selection σregion=’us-east’(Deployment)\sigma_{region = \text{'us-east'}}(Deployment) determine the schema and result grain of πnode_id,service_id(σregion=’us-east’(Deployment))\pi_{node\_id,service\_id}\bigl(\sigma_{region = \text{'us-east'}}(Deployment)\bigr) Explain why dropping regionregion affects subsequent multi-region queries.

HintExpand

Selection preserves all attributes; projection then retains only node_id and service_id.

Worked solutionExpand

The output schema is (node_id,service_id)(node\_id, service\_id) with tuples representing nodes actively hosting a service in us-east. Because regionregion 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

Verificationapplication

An engineer proposes rewriting σR.region=’us-east’(R⋈R.node_id=S.node_idS)\sigma_{R.region = \text{'us-east'}}(R \bowtie_{R.node\_id = S.node\_id} S) into σR.region=’us-east’(R)⋈R.node_id=S.node_idS\sigma_{R.region = \text{'us-east'}}(R) \bowtie_{R.node\_id = S.node\_id} S Referring to Proposition 1.3.2, verify whether this rewrite is valid under two-valued set semantics, and identify one condition under which it fails for outer joins.

HintExpand

Check predicate attribute dependency and outer-join null extension semantics.

Worked solutionExpand

Under two-valued set semantics, the rewrite is valid because the selection predicate references only attributes of RR and the join is an inner equijoin. For a left outer join where the predicate references SS instead (e.g. S.active=’Y’S.active = \text{'Y'} pushing the predicate into SS retains non-matching RR tuples with NULL padding, whereas the post-join filter eliminates them.

Exercise 1.3.3: Universal Division via Difference Formulation

Constructionapplication

Let Node(node_id,tier)Node(node\_id, tier) RequiredService(service_id)RequiredService(service\_id) and Deployment(node_id,service_id,region)Deployment(node\_id, service\_id, region) be set relations. Using relational algebra operators from Definition 1.3.1, construct an expression that returns all nodes in the edge tier that host every service in RequiredServiceRequiredService in region us-east.

HintExpand

Restrict candidate nodes first before constructing the Cartesian product of expected pairs.

Worked solutionExpand

Define candidate edge nodes and expected pairs:

Eligible=σtier=’edge’(Node)Expected=πnode_id(Eligible)×RequiredServiceDeployed=πnode_id,service_id(σregion=’us-east’(Deployment))Missing=Expected−DeployedAnswer=πnode_id(Eligible)−πnode_id(Missing)\begin{aligned} Eligible &= \sigma_{tier = \text{'edge'}}(Node) \\ Expected &= \pi_{node\_id}(Eligible) \times RequiredService \\ Deployed &= \pi_{node\_id,service\_id}\bigl(\sigma_{region = \text{'us-east'}}(Deployment)\bigr) \\ Missing &= Expected - Deployed \\ Answer &= \pi_{node\_id}(Eligible) - \pi_{node\_id}(Missing) \end{aligned}

Filtering candidates before forming the product avoids generating missing pairs for unrelated tiers.

Exercise 1.3.4: Constrained Core-Service Deployment Derivation

Generalisationtransfer

Let Node(node_id)Node(node\_id) Service(service_id)Service(service\_id) Deployed(node_id,service_id,region)Deployed(node\_id, service\_id, region) and Core(service_id)Core(service\_id) 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.

HintExpand

Derive universal deployment of Core, then subtract the set of nodes with non-core deployments.

Worked solutionExpand

First isolate us-east deployments: Active=πnode_id,service_id(σregion=’us-east’(Deployed))Active = \pi_{node\_id,service\_id}(\sigma_{region = \text{'us-east'}}(Deployed)) Compute nodes hosting all core services:

ExpectedCore=πnode_id(Node)×CoreAllCore=πnode_id(Node)−πnode_id(ExpectedCore−Active)\begin{aligned} ExpectedCore &= \pi_{node\_id}(Node) \times Core \\ AllCore &= \pi_{node\_id}(Node) - \pi_{node\_id}(ExpectedCore - Active) \end{aligned}

Next isolate non-core services: NonCore=πservice_id(Service)−CoreNonCore = \pi_{service\_id}(Service) - Core (both schema (service_id)(service\_id) Find nodes with any non-core service: HasNonCore=πnode_id(Active⋈NonCore)HasNonCore = \pi_{node\_id}(Active \bowtie NonCore) The final answer is AllCore−HasNonCoreAllCore - HasNonCore Both operands have schema (node_id)(node\_id)

References & Further Reading