Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 79 · Relational Algebra and Calculus

Tuple and Domain Relational Calculus

Learn tuple and domain relational calculus: tuple variables, the quantifiers exists and for all, safe expressions, Codd's theorem and how queries translate to SQL.

Relational algebra tells the database how to compute an answer: first select, then join, then project. Relational calculus takes the opposite stance. It is a declarative notation where you describe what the answer looks like, as a logical condition, and say nothing about the steps. If that sounds like SQL, it should: SQL is a practical blend of both ideas, and its SELECT ... FROM ... WHERE shape comes straight from the calculus.

There are two flavours. In tuple relational calculus (TRC) variables range over whole rows. In domain relational calculus (DRC) variables range over single column values. This lesson explains both, the dangerous "unsafe" expressions that must be excluded, and the famous result that calculus and algebra can express exactly the same queries. Only the SQL translations at the end run live; the calculus itself is mathematical notation, not something a database executes.

Two ways to ask the same question

Algebra Procedural. A recipe of operators.
Calculus Declarative. A condition the answer must satisfy.
Same power For safe queries, they express the same set of queries.

SQL borrows from both, but its WHERE clause is calculus at heart.

1 / 2

Tuple relational calculus

A TRC query has the form

{ t | P(t) }

and reads "the set of all tuples t such that the formula P is true for t". The formula P is built from small pieces:

  • Range atoms such as Student(s), meaning "the tuple variable s is a row of the relation Student".
  • Comparisons such as s.age > 20 or s.dept = c.dept, which compare attributes of tuple variables or an attribute and a constant.
  • Logical connectives: ∧ (and), ∨ (or), ¬ (not) and ⇒ (implies).
  • Quantifiers: ∃ x (P) (there exists a tuple x for which P holds) and ∀ x (P) (for all tuples x, P holds).

A variable that is not tied to a quantifier is free; the free variable is the one that describes the answer. A variable under a quantifier is bound. In { s | Student(s) ∧ s.age > 20 } the variable s is free, so the answer contains whole Student rows.

Use the notation { t.name | ... } when you only want some attributes, which plays the role of projection. Here is a small catalogue of the four standard patterns. Suppose Student(id, name, age), Course(code, title) and Enrolled(sid, code).

Question Tuple calculus
Students older than 20 { s | Student(s) ∧ s.age > 20 }
Names of students enrolled in at least one course { s.name | Student(s) ∧ ∃e (Enrolled(e) ∧ e.sid = s.id) }
Students enrolled in nothing { s | Student(s) ∧ ¬∃e (Enrolled(e) ∧ e.sid = s.id) }
Students enrolled in every course { s | Student(s) ∧ ∀c (Course(c) ⇒ ∃e (Enrolled(e) ∧ e.sid = s.id ∧ e.code = c.code)) }

The last one is the calculus version of the "for all" query that algebra needs the division operator for. In the calculus it is just a quantifier.

Quantifiers are the heart of it

Two equivalences are worth memorising, because they are exactly how you move between calculus and SQL:

  • ∀x (P(x)) is the same as ¬∃x (¬P(x)): "everything satisfies P" means "nothing fails P".
  • P ⇒ Q is the same as ¬P ∨ Q.

Combine them and the "enrolled in every course" query becomes "there is no course for which there is no matching enrollment". That is the double negation you will see as nested NOT EXISTS in SQL.

Domain relational calculus

In DRC the variables are values, one per column. A query looks like

{ <n> | ∃i, a ( <i, n, a> ∈ Student ∧ a > 20 ) }

and reads "all names n for which some id i and age a exist such that (i, n, a) is a row of Student and a > 20". You list one variable per attribute of the relation, which makes DRC more verbose but also closer to Query By Example (QBE), the grid-based query interface where you type example values into table skeletons. QBE, in turn, influenced the visual query builders in some desktop database tools. TRC maps more directly to SQL, so we use it for the rest of the lesson.

Safe expressions

Calculus has a trap. Consider { t | ¬Student(t) }: "all tuples that are not students". That set is infinite, because every possible tuple of any values that is not in Student qualifies. A database cannot return an infinite answer. The same happens with { t | t.age > 20 }, which does not even restrict t to a relation.

An expression is safe if it always yields a finite result, and the practical test is: every value that appears in the answer must come from the database (from the relations or from constants in the query), not from the infinite universe of possible values. In SQL terms, every variable must be tied to a table through a range atom, which is why FROM is mandatory in a useful query. Only safe expressions are considered valid queries.

Codd's theorem

The key theoretical result, due to E. F. Codd in 1972, is that safe tuple relational calculus, safe domain relational calculus and relational algebra have the same expressive power. For every safe calculus query there is an algebra expression with the same result, and the other way round. A language that can express everything the algebra can is called relationally complete, and that is the bar SQL (and every other relational query language) is measured against.

The result matters for two reasons. First, it shows that the relational model has a natural, robust notion of "what a query can ask". Second, it licenses the optimizer: you write a declarative query, and the system is free to translate it into an algebra tree and rearrange it, as you will see in the query processing pipeline.

What neither language can do is compute things like the transitive closure of a graph (all the ancestors of a person) or arbitrary arithmetic loops. Those need extensions such as recursion; SQL adds them as recursive CTEs.

From calculus to SQL

The translation is mechanical:

Calculus SQL
Student(s) FROM student s
s.age > 20 WHERE s.age > 20
∃e (Enrolled(e) ∧ ...) EXISTS (SELECT 1 FROM enrolled e WHERE ...)
¬∃ NOT EXISTS
∀c (P) NOT EXISTS (... NOT P ...)
{ s.name | ... } SELECT s.name

Run all four example queries on a tiny database. The data is built in the first lines so that the example is self-contained.

SQL Four calculus queries as SQL

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

The first query returns Ana, Chen and Dina, the second Ana, Boris and Chen, the third only Dina and the fourth Ana and Chen. Notice how the last query follows the quantifier rewrite literally: "no course exists for which no enrollment exists".

You can also see the safety rule in action. The unsafe formula ¬Student(t) has no SQL equivalent, because there is no FROM clause to draw the tuples from. The closest thing is a difference with another relation, which does have a finite universe:

SQL Safe negation needs a finite universe

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

Both queries return Ana and Chen. The negation is safe because p is first restricted to the person relation.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the main difference between relational algebra and relational calculus?

    Algebra describes the steps (operators applied in order), while calculus describes the properties of the answer. Their expressive power is the same for safe queries.
  2. 2. Which formula is equivalent to ∀x (P(x))?

    Saying "everything satisfies P" means "nothing fails P". This rewrite is why a for-all query becomes a double NOT EXISTS in SQL.
  3. 3. Why is the expression { t | ¬Student(t) } unsafe?

    Every possible tuple that is not a student qualifies, and there are infinitely many of them. Safe queries draw every answer value from the database.
  4. 4. What does Codd's theorem state?

    For every safe calculus query there is an equivalent algebra expression and vice versa. This is what makes a language relationally complete.

Summary

  • Relational calculus is a declarative query notation: { t | P(t) } is the set of tuples satisfying a logical formula.
  • Tuple calculus uses variables that range over rows; domain calculus uses variables over single values and inspired Query By Example.
  • Quantifiers ∃ and ∀ express existence and "for all"; ∀x P equals ¬∃x ¬P, which is the double NOT EXISTS pattern in SQL.
  • Safe expressions always give finite answers because every answer value comes from the database.
  • Codd's theorem: safe calculus and relational algebra are equally expressive, so a language that matches them is relationally complete.
  • Neither can express recursion, which SQL adds separately.

Next: DDL: Creating and Altering Schemas, where the theory turns into CREATE TABLE statements.