The Relational Model and Relational Algebra
A relation is a set of tuples over named attributes. Classical relational algebra combines selection, projection, join, union and difference to express queries. Different expressions can return the same relation.
What a learner can do afterwards
- Write a query as a composition of relational algebra operations
- Show two different algebra expressions that produce the same relation
- Explain what it means that a relation is a set rather than a list
1 · Read
A relation is a set of tuples over named attributes. Each tuple gives one value for each attribute. Row order does not matter, and each distinct tuple appears once. Two relations with the same schema are equal when they contain the same tuples. Every operation here returns a relation. SQL often retains duplicate rows unless distinct results are requested, so its usual duplicate rules differ.
Selection σ keeps whole tuples passing a test. Projection π keeps the named attributes and removes duplicate tuples created by dropping columns. In π_name(σ_age>16(Students)), evaluate the inner selection first, then project names. A test needs its attributes to remain available. The projection's attribute list is the result schema.
Here ⋈ means natural join. Pair tuples agreeing on every shared attribute, then combine their attributes, keeping each shared attribute once. Members(id,name) ⋈ Loans(id,book) matches on id. One member with two matching loan tuples contributes two combined tuples. Unmatched tuples contribute none. If two attributes are shared, both must match.
For R ∪ S, R ∩ S and R - S, use the same attribute names and matching types. Union keeps tuples in either relation. Intersection keeps tuples in both. Difference keeps tuples in R but not S. Union size is the two sizes added minus the shared count. Difference size is R's size minus the shared count. With no shared tuples, intersection is empty.
For compatible schemas, σ_a>7(R ∩ S) = σ_a>7(R) ∩ σ_a>7(S). Each expression keeps tuples that belong to R and S and have a above 7. Selection also distributes over union: filter the pooled tuples, or pool the separately filtered tuples. The test must be defined on both inputs. Difference is directional: R - S need not equal S - R.
Selection can move past projection when projection retains every attribute used by the test. Thus π_b(σ_b>7(R)) = σ_b>7(π_b(R)). Dropping b first would make its test undefined. Nested projections reduce to the final attributes if the inner projection retains them: π_a(π_a,b(R)) = π_a(R).
Projection does not always distribute over intersection. Let R(a,b) contain (3,6) and S(a,b) contain (3,8). The full tuples differ, so R ∩ S is empty. Projecting each onto a gives {3} on both sides. Their intersection contains 3. Dropping b hid the difference between the original tuples.
Students(id,name,age) and Enrolled(id,course) share only id, a unique student identifier. To return name/course pairs for students over 16, filter Students, join Enrolled, then project name and course. To return only enrolled IDs of students over 16, use π_id(σ_age>16(Students)) ∩ π_id(Enrolled). Names alone may match different people.
A selection can move before a natural join when its test uses only attributes of that input. Here σ_age>16(Students ⋈ Enrolled) = σ_age>16(Students) ⋈ Enrolled. Both retain exactly the matching pairs whose student passes the age test. A test needing an attribute supplied only by Enrolled cannot run on Students alone.
Relations are sets. Check schemas, evaluate nested operations inside out, and justify equivalent expressions by the tuples they retain.
This relational-algebra lesson, question bank and flashcards were written for this dataset.
These relational-algebra questions and readings were independently written for this dataset.
More to read
Duplicates in algebra and SQL
Records(id,colour) contains (41,green), (42,green) and (43,blue). These are three distinct full tuples because their identifiers differ.
Projecting onto colour removes id. Under pure relational algebra, the result contains (green) and (blue). The repeated green value contributes one tuple because projection returns a set.
The SQL query SELECT colour FROM Records usually returns three rows here: green, green and blue. SELECT DISTINCT colour FROM Records requests distinct colour rows. This difference matters when comparing an SQL result with a mathematical algebra expression.
Row order also needs care. Rearranging a relation's displayed tuples leaves its membership unchanged. SQL uses ORDER BY when a query needs a specified output order. Without it, a particular displayed order is not guaranteed.
Before counting a result, identify the model. For the algebra in this lesson, count distinct tuples. For SQL, check whether the query retains duplicates or requests distinct rows.
Track the attributes a query still needs
Devices(id,label,status) and Checks(id,date) share only id. A query asks for labels and check dates of active devices.
Select Devices tuples whose status is active. Retain id so those tuples can join Checks. Each matching pair supplies the device label and a check date. Project label and date after the join.
Removing status before selection would leave no attribute for the test. Removing id before the join would remove the intended matching attribute. Track the available attributes after every operation.
Another valid route joins Devices and Checks first, selects active status, then projects label and date. The status test uses only Devices attributes, so moving that selection earlier retains the same matching pairs.
Describe a surviving pair to check the equivalence: its device and check have the same id, and the device is active. Both routes require those conditions. Their final projections contain the same distinct label/date tuples.
2 · Watch
En anglaisTake it off screen
Where it sits
20 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.