Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 37 ยท Applications in CS

Relational Algebra, Sets and SQL

See databases as set theory and logic: relations as sets of tuples, the relational algebra operators, first-order queries and Datalog recursion, checked against SQLite in Python.

A relational database is applied set theory. A table is a finite relation: a set of tuples, exactly the n-ary relations from relations and their properties. A query language is then a way to build new sets from old ones. SQL, which millions of programmers use daily, is a friendly surface over two mathematical languages from the 1970s: relational algebra (operators on sets) and relational calculus (first-order logic formulas).

Edgar Codd's 1970 insight was that you can describe what you want declaratively, with set operations or logic, and let the system decide how to compute it.

Relations as sets of tuples

A relation has a schema (attribute names, e.g. (name, dept)) and an instance, a set of tuples. Because it is a set, there are no duplicates and no row order. (SQL tables are bags by default and allow duplicates, which is one place SQL departs from the pure theory; SELECT DISTINCT restores set semantics.)

The operators

Operator Symbol Meaning SQL
Selection ฯƒ_cond(R) rows satisfying a condition WHERE
Projection ฯ€_attrs(R) keep some columns, drop duplicates SELECT DISTINCT
Rename ฯ rename attributes AS
Union, intersection, difference โˆช โˆฉ โˆ’ set operations on compatible relations UNION, INTERSECT, EXCEPT
Cartesian product ร— all pairs of rows CROSS JOIN
Natural join โ‹ˆ match on shared attributes NATURAL JOIN

Selection, projection, union, difference, product and rename are the basic operators; join and intersection can be derived (a join is a product followed by a selection and a projection). Because the result of each operator is again a relation, you can compose them, exactly like function composition.

Python Relational algebra operators on sets of tuples

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 same queries in SQL

Python on Pyodide includes sqlite3, so we can run the SQL equivalents and compare results. The point is that the algebra expression ฯ€_name(ฯƒ_city='Oslo'(Emp โ‹ˆ Dept)) and the SQL query return the same set.

Python Algebra expression versus SQLite

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.

Relational calculus: queries as logic formulas

Tuple relational calculus writes a query as a first-order formula: { t.name | Emp(t) โˆง โˆƒd (Dept(d) โˆง d.dept = t.dept โˆง d.city = 'Oslo') }. This is the predicate logic you know: the answer is the set of tuples that make the formula true. Codd's theorem says relational algebra and safe relational calculus have exactly the same expressive power, so SQL's EXISTS, NOT EXISTS and IN are quantifiers in disguise:

  • โˆƒ is EXISTS (subquery).
  • โˆ€x P(x) is NOT EXISTS (x such that NOT P(x)), which is how you write "for all" queries.
  • Division (R รท S) answers "which x are related to all of S?", a universal quantifier in algebra form.
Python Universal quantification: who works on all projects? (division)

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.

Recursion and Datalog

Relational algebra cannot express transitive closure ("all ancestors", "all reachable cities") with a fixed expression: it would need a loop. Modern SQL adds WITH RECURSIVE, and the logic-programming language Datalog is built for it. Datalog states rules like path(X, Z) :- edge(X, Y), path(Y, Z). and computes the least fixed point by repeatedly applying the rules until nothing new appears. This is the same closure you computed with Warshall's algorithm earlier and the same forward chaining as Horn-SAT.

Python Transitive closure: Datalog-style fixed point and WITH RECURSIVE

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.

Because SQL tables are bags and SQL has NULL, its logic is three-valued (true, false, unknown). That is why x = NULL is never true and NOT IN with a NULL in the list behaves surprisingly. The set-theoretic model assumes no NULLs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In relational algebra, what is a relation?

    A relation instance is a set of tuples over a schema, so it has no duplicates and no inherent order.
  2. 2. Which SQL clause corresponds to selection ฯƒ?

    Selection filters rows by a condition, which WHERE does. Projection ฯ€ corresponds to the column list of SELECT.
  3. 3. How do you express โˆ€ in SQL?

    โˆ€x P(x) is equivalent to ยฌโˆƒx ยฌP(x), which becomes a doubly nested NOT EXISTS.
  4. 4. Why does transitive closure need recursion?

    A fixed expression joins a bounded number of times; reachability needs an unbounded number, so Datalog or WITH RECURSIVE iterates to a fixed point.

Summary

  • A table is a set of tuples; queries are built by composing set-valued operators.
  • The basic operators are selection, projection, rename, union, difference and product; join is derived.
  • Relational algebra and safe relational calculus (first-order logic) are equally expressive; โˆ€ becomes double NOT EXISTS or division.
  • Transitive closure needs recursion: Datalog and WITH RECURSIVE compute a least fixed point.

Next: Project: A Resolution Theorem Prover