Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 79 ยท Relational Algebra and Calculus

Build a Relational Algebra Interpreter

Implement select, project, rename, union, difference, product, join and division on sets of tuples in Python, then check every result against real SQL.

The best way to understand an operator is to write it. Relational algebra is small enough that a complete working version fits on one screen of Python, and the result is more than a toy: it is a miniature of what the executor of a real DBMS does. In this lesson you will implement a Relation class whose methods are the operators from the last four lessons (selection and projection, set operations, joins and division), and then prove they are right by comparing them with SQL.

Everything runs in the browser in Python. Each example repeats the class it needs, so every block works on its own.

Design: relations are sets

A relation in the model is a set of tuples over a fixed list of attribute names. We copy that directly:

The data structure

attrs A tuple of attribute names, in order.
rows A frozenset of plain tuples. No duplicates, no order.
Immutable Every operator returns a new Relation.
1 / 2

Because rows is a frozenset, duplicate elimination is free: projecting away a key automatically collapses identical tuples, exactly as the algebra says. (SQL tables are bags and need DISTINCT; our interpreter has set semantics, which will matter when we compare.) Predicates receive a dictionary that maps attribute names to values, so a condition reads like lambda t: t["grade"] >= 70.

Selection, projection, rename and the set operators

Python A Relation class with the basic operators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output against your expectations. Selecting grades of 80 or more keeps four tuples. Projecting cid collapses ten enrollments into the four distinct course codes, with no DISTINCT needed. The three set operators agree with the arithmetic from Union, Intersection, Difference and Cartesian Product: students 1, 2, 3 and 4 took DB, students 1, 2 and 3 took OS, so the union has four members, the intersection three and DB minus OS just student 4. The last line shows the compatibility check in action.

Notice that select and project never change the original; they build new relations. This is the same idea as the iterator model in a real executor, where each operator consumes the output of another (The Query Processing Pipeline).

Joins and division

Now add the operators that are derived. Each is written in terms of the previous ones, exactly as the definitions say:

  • Theta join = product, then select.
  • Natural join = rename shared attributes, product, select on equality, project away the duplicates.
  • Division = ฯ€A(R) โˆ’ ฯ€A((ฯ€A(R) ร— S) โˆ’ R).
Python Joins and division, derived from the basic operators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The natural join first finds the attribute sid in both inputs, renames the right-hand copy to _sid, forms the product, keeps only the pairs where the two agree, and projects the duplicate away. It is the same recipe that Joins in Relational Algebra gave in words. Division returns students 1, 2 and 3 for DB and OS (Dev took only DB, and Eli took nothing, so Eli never even appears as a candidate) and only Cleo for all four courses.

This interpreter is deliberately simple: the product builds every pair in memory, and a real join would not. Join Algorithms shows how a hash join or a sort-merge join produces the same answer without the pair explosion. The interpreter is the specification; the engine is an optimized implementation of it.

Checking the interpreter against SQL

An implementation is only trustworthy when something else agrees with it. Python's standard library includes SQLite, the same engine family as this site's SQL runner, so we can load the same data into tables, run the SQL equivalent of each expression, and compare as sets. We compare as sets on purpose: the algebra returns sets, and a SQL result is a bag.

Python Algebra versus SQL: the same answers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All five lines report a match. Look at the division check: SQL needed three nested levels and a double negation, while our algebra method was four lines built from operators you already know. That asymmetry is exactly why division exists as its own operator in the theory.

If a check ever printed DIFFERENT, you would have found a bug in one of the two sides, and the usual suspects are duplicates (sets versus bags), NULL handling, and natural joins on columns that happen to share a name.

What this interpreter leaves out

Real executors differ in a few essential ways:

  • Bags and order. SQL keeps duplicates unless told otherwise and supports ORDER BY.
  • Nulls. Comparisons with unknown values need the three-valued logic from Nulls and Three-Valued Logic.
  • Aggregation and grouping, the extended operators from the last lesson, are an easy addition: group the rows by key, then fold each group.
  • Efficiency. Streaming iterators, indexes and join algorithms replace building every intermediate relation in memory.

Extending the class with a group_by method is a good exercise, and Project: Build a Mini Database Engine goes much further.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does project() in our interpreter remove duplicates without any extra code?

    Relations in the model are sets. Using a frozenset gives set semantics and the algebra's duplicate elimination for free.
  2. 2. How does the interpreter implement a theta join?

    theta_join is defined as self.product(other).select(predicate), exactly the algebra definition.
  3. 3. Why must shared attribute names be renamed before a product?

    A relation's attributes must be uniquely named. Rename (ฯ) gives the second copy a different name.
  4. 4. Why do the SQL checks compare results as sets instead of lists?

    Neither side promises an order, so the comparison must ignore order. Using set() also ignores duplicate rows, matching the algebra.
  5. 5. In divide(), what do the 'missing' pairs represent?

    missing = (ฯ€A(R) ร— S) โˆ’ R. Any A value that has a missing pair is removed from the candidates.

Summary

  • A relation is a set of tuples over named attributes; a frozenset of tuples gives the right semantics, including free duplicate elimination.
  • select, project, rename, union, difference and product are the primitives; joins and division are written in terms of them.
  • Comparing the interpreter with SQLite on the same data, as sets, catches mistakes on both sides.
  • The interpreter is a specification: real engines return the same answers with streaming operators, indexes and clever join algorithms.
  • Nulls, bags, ordering and grouping are the main gaps between this model and SQL.

Next: the logic-based alternative to algebra, in Tuple and Domain Relational Calculus.