Relational Algebra

Composed Query

A relational algebra tree recomputes children before parent operators.

highlighted = computed this step

Compose operators bottom up

A composed query recomputes each child before the parent operator reads it. Changing an inner predicate can change the final cardinality. Note: the tree shows the recompute flow, and the table shows the final rows.

bottom up recompute\text{bottom up recompute}

First composed query

The final recomputed row count is 2. Note: selection runs before join, and projection runs last.

final rows=2\text{final rows}=2

set algebra not SQL bag/NULL, tiny finite tables, no product/perf claims

Composed queryproject namearity 1 rows 2join sid=sidarity 3 rows 2Studentsarity 2 rows 3select course eq DBarity 2 rows 2Enrollarity 2 rows 3
projectnameAnnBo

Second composed query

The same tree shape with a different inner predicate has recomputed row count 1. Note: a local predicate change can propagate to the final output.

final rows=1\text{final rows}=1

set algebra not SQL bag/NULL, tiny finite tables, no product/perf claims

Composed query contrastproject namearity 1 rows 1join sid=sidarity 3 rows 1Studentsarity 2 rows 3select course eq OSarity 2 rows 1Enrollarity 2 rows 3
projectnameAnn

Summary

Composed relational algebra is honest because every parent consumes recomputed child outputs. Note: Bag or multiset duplicates and NULL behavior are deferred to the next book.

composed query summary\text{composed query summary}