Chapter 17 of 41

Relational Calculus

On this page

In the previous chapter, Relational Algebra, every query was a recipe: select these rows, join with that relation, project these columns. You told the database how to compute the answer.

Relational Calculus takes the opposite approach. You describe what the answer looks like, using a logical formula, and leave the "how" entirely to the system.

Relational Calculus is a non-procedural (declarative) query language based on first-order predicate logic. A query specifies the properties that the result tuples must satisfy, not the steps to compute them.

A good everyday analogy: relational algebra is like giving a taxi driver turn-by-turn directions; relational calculus is like giving the driver the destination address. SQL is much closer to the second style, which is why understanding calculus makes SQL subqueries (especially EXISTS and NOT EXISTS) much easier.

There are two forms:

  • Tuple Relational Calculus (TRC): variables stand for whole tuples (rows).

  • Domain Relational Calculus (DRC): variables stand for individual attribute values (domain elements).


Sample Relations

We reuse the same university database from the Relational Algebra chapter, so you can compare both styles directly.

Student(sid, name, dept, age)     6 students: Asha, Bharat, Chitra, Dev, Esha, Farhan
Course(cid, title, dept, credits) C1 DBMS (CSE), C2 OS (CSE), C3 Signals (ECE), C4 Networks (ECE)
Enrolled(sid, cid)                (1,C1) (1,C2) (1,C3) (2,C3) (3,C1) (3,C2) (4,C1) (5,C2)

Farhan (sid 6) has no enrollments, and nobody takes C4.


A Quick Logic Refresher

Calculus formulas are built from a few logical symbols. You only need these:

Symbol

Read as

Meaning

∧

and

Both conditions are true

∨

or

At least one is true

¬

not

Negation

⇒

implies

P ⇒ Q is the same as ¬P ∨ Q

∃

there exists

At least one value makes it true

∀

for all

Every value makes it true

Two identities do most of the heavy lifting when you translate calculus to SQL:

∀x P(x)   ≡   ¬∃x ¬P(x)        "everyone passed" = "nobody failed"
P ⇒ Q     ≡   ¬P ∨ Q

Free and Bound Variables

A variable is bound if it is introduced by a quantifier (∃ or ∀); otherwise it is free. In a calculus query, the variable that appears to the left of the bar | must be the only free variable; it is the one whose values form the answer.

{ t | ∃s ∈ Student (s.sid = t.sid) }
      t is free  → it is the result
      s is bound → it is only a helper inside the formula

Tuple Relational Calculus (TRC)

A TRC query has the form:

{ t | P(t) }

Read it as: "the set of all tuples t such that the formula P(t) is true."

The formula is built from atoms:

  • t ∈ R : tuple t belongs to relation R

  • t.A op s.B : compare two attribute values, where op is one of =, ≠, <, ≤, >, ≥

  • t.A op c : compare an attribute with a constant

Atoms are combined with ∧, ∨, ¬, ⇒, ∃ and ∀. We write ∃s ∈ R (P) as a short form of ∃s (s ∈ R ∧ P), and ∀s ∈ R (P) as a short form of ∀s (s ∈ R ⇒ P).

Example 1: Selection (all CSE students)

{ t | t ∈ Student ∧ t.dept = 'CSE' }

Result: Asha, Chitra, Esha (all four attributes). This is the same as σ[dept='CSE'](Student) in algebra.

Example 2: Projection (names of students older than 20)

We want only the name attribute in the answer. So t is a tuple with one attribute, and we say that some Student tuple s supplies its value:

{ t | ∃s ∈ Student ( s.age > 20 ∧ t.name = s.name ) }

Result: Bharat, Chitra, Esha, Farhan. Projection in TRC always looks like this: an existential quantifier over the full tuple, and the result tuple copies only the attributes you want.

Example 3: Join (names of students enrolled in DBMS)

{ t | ∃s ∈ Student ∃e ∈ Enrolled ∃c ∈ Course (
          s.sid = e.sid ∧ e.cid = c.cid ∧ c.title = 'DBMS'
          ∧ t.name = s.name ) }

Notice there is no join operator. A join is simply "there exist matching tuples in both relations". SQL's EXISTS expresses exactly this idea, and the translation is almost word for word:

SELECT s.name
FROM Student s
WHERE EXISTS (SELECT *
              FROM Enrolled e, Course c
              WHERE e.sid = s.sid AND e.cid = c.cid AND c.title = 'DBMS');
+--------+
| name   |
+--------+
| Asha   |
| Chitra |
| Dev    |
+--------+

Example 4: Negation (students not enrolled in any course)

{ t | t ∈ Student ∧ ¬∃e ∈ Enrolled ( e.sid = t.sid ) }
SELECT t.sid, t.name
FROM Student t
WHERE NOT EXISTS (SELECT * FROM Enrolled e WHERE e.sid = t.sid);
+-----+--------+
| sid | name   |
+-----+--------+
|   6 | Farhan |
+-----+--------+

In algebra, this needed set difference. In calculus, ¬∃ plays that role.

Example 5: Universal quantifier (students enrolled in ALL CSE courses)

This is the query that needed division in relational algebra. In calculus it reads almost like English:

{ t | t ∈ Student ∧
      ∀c ∈ Course ( c.dept = 'CSE' ⇒ ∃e ∈ Enrolled ( e.sid = t.sid ∧ e.cid = c.cid ) ) }

"t is a student, and for every course c, if c is a CSE course then t is enrolled in c."

SQL has no ∀, so we convert step by step using the identities above:

∀c (c.dept = 'CSE' ⇒ Enrolled(t, c))
≡ ¬∃c ¬(c.dept = 'CSE' ⇒ Enrolled(t, c))
≡ ¬∃c ¬(¬(c.dept = 'CSE') ∨ Enrolled(t, c))
≡ ¬∃c (c.dept = 'CSE' ∧ ¬Enrolled(t, c))

"there is NO CSE course that t is NOT enrolled in"

That last line becomes the famous double NOT EXISTS:

SELECT s.sid, s.name
FROM Student s
WHERE NOT EXISTS (
    SELECT * FROM Course c
    WHERE c.dept = 'CSE'
      AND NOT EXISTS (
          SELECT * FROM Enrolled e
          WHERE e.sid = s.sid AND e.cid = c.cid));
+-----+--------+
| sid | name   |
+-----+--------+
|   1 | Asha   |
|   3 | Chitra |
+-----+--------+

A Subtle Point: Vacuous Truth

What if no course satisfies the condition, say c.dept = 'CIVIL'? Then "for every CIVIL course, t takes it" is vacuously true for every student, because there is nothing to check. Running the same query with 'CIVIL' in MySQL returns all six students, including Farhan.

Relational algebra division behaves slightly differently here: Enrolled ÷ ∅ returns only students that appear in Enrolled (sids 1 to 5), because the result comes from π[sid](Enrolled). The two queries were written to answer the same question but start from different relations, so they disagree in this edge case. Always ask yourself where the candidate tuples come from.


Domain Relational Calculus (DRC)

In DRC, variables range over single attribute values instead of whole tuples. A query has the form:

{ <x1, x2, ..., xn> | P(x1, x2, ..., xn) }

The atoms are:

  • <x1, ..., xk> ∈ R : the values form a tuple of R (listed in the attribute order of R)

  • x op y and x op c : comparisons

Let us write the same queries in DRC. For Student we use variables <i, n, d, a> for (sid, name, dept, age).

Example 1: All CSE students

{ <i, n, d, a> | <i, n, d, a> ∈ Student ∧ d = 'CSE' }

Example 2: Names of students older than 20

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

Every attribute we do not want in the output is existentially quantified. That is how DRC does projection.

Example 3: Names of students enrolled in DBMS

{ <n> | ∃i ∃d ∃a ∃c ∃cd ∃cr (
            <i, n, d, a> ∈ Student
          ∧ <i, c> ∈ Enrolled
          ∧ <c, 'DBMS', cd, cr> ∈ Course ) }

Look at how the join happens: the same variable i appears in Student and Enrolled, and the same c appears in Enrolled and Course. Reusing a variable forces equality, so no explicit = is needed. We even put the constant 'DBMS' directly in the tuple pattern.

Example 4: Students enrolled in all CSE courses

{ <i, n> | ∃d ∃a ( <i, n, d, a> ∈ Student ) ∧
           ∀c ∀ti ∀cr ( <c, ti, 'CSE', cr> ∈ Course ⇒ <i, c> ∈ Enrolled ) }

Here c, ti and cr stand for a course's cid, title and credits. Read it as: "for every value combination that forms a CSE course, student i is enrolled in that course". Same answer as before: (1, Asha) and (3, Chitra).

DRC is the theory behind Query By Example (QBE), where you fill example values into a grid that looks like the table, and behind logic-based languages like Datalog.


Safety of Expressions

Calculus lets you write formulas that make no practical sense. Consider:

{ t | ¬(t ∈ Student) }

"All tuples that are not students." There are infinitely many such tuples (every possible combination of every possible value). No database can return that. Such a query is called unsafe.

A relational calculus expression is safe if every value in its result is guaranteed to come from the domain of the expression, that is, from the relations mentioned in the query or the constants written in it.

Practical rules that keep a query safe:

  • Every free variable should be tied to a relation with a positive atom like t ∈ R (or appear in a tuple of R in DRC).

  • Negation should only remove tuples from a set that is already bounded, as in t ∈ Student ∧ ¬∃e ....

  • With ∨, both sides must be bounded. { t | t ∈ Student ∨ t.age > 20 } is unsafe, because the right side alone allows infinitely many tuples that are not students.

SQL avoids this problem by design: every query has a FROM clause, so all values come from real tables.


Expressive Power: Codd's Theorem

Do algebra and calculus have the same power? Yes:

Safe tuple relational calculus, safe domain relational calculus and basic relational algebra are equivalent in expressive power. Any query in one can be written in the others.

This result is known as Codd's theorem. A query language that can express every query of relational algebra is called relationally complete. SQL is relationally complete, and it goes further with aggregation, grouping, ordering and recursion (WITH RECURSIVE), which pure algebra and calculus cannot express.

One classic example of what plain algebra and calculus cannot do: transitive closure, such as "find all managers above an employee, at any depth". Each query can only follow a fixed number of joins.


Algebra vs TRC vs DRC

Feature

Relational Algebra

Tuple Calculus

Domain Calculus

Style

Procedural (how)

Declarative (what)

Declarative (what)

Variables range over

No variables, only operators

Tuples

Attribute values

Query form

Expression of operators

{ t | P(t) }

{ <x1..xn> | P }

Join written as

⋈

∃ with equality condition

Shared variable

"For all" written as

÷

∀ (or ¬∃¬)

∀ (or ¬∃¬)

Practical language

Query plans inside DBMS engines

Influenced SQL

QBE, Datalog


Translating Between the Three: One Query

Query: sids of students who are not enrolled in C1.

Algebra : π[sid](Student) − π[sid](σ[cid = 'C1'](Enrolled))

TRC     : { t | ∃s ∈ Student ( t.sid = s.sid
                 ∧ ¬∃e ∈ Enrolled ( e.sid = s.sid ∧ e.cid = 'C1' ) ) }

DRC     : { <i> | ∃n ∃d ∃a ( <i, n, d, a> ∈ Student ) ∧ ¬( <i, 'C1'> ∈ Enrolled ) }

Answer  : {2, 5, 6}

(Students 1, 3 and 4 take C1, so the rest remain.) Note that the DRC version is safe: i is bounded by Student first, and the negation only removes values.


Common Mistakes

  • Leaving more than one free variable. Helper tuples must be bound with ∃ or ∀.

  • Writing ∀ with ∧ instead of ⇒. ∀c ∈ Course (c.dept = 'CSE' ∧ ...) demands that every course be a CSE course, which is false, so the result is empty. The correct pattern is ∀c (condition ⇒ requirement).

  • Writing ∃ with ⇒ instead of ∧. ∃e (e ∈ Enrolled ⇒ ...) is true as soon as any non-enrolled value exists, which is almost always. The correct pattern is ∃e (e ∈ Enrolled ∧ ...).

  • Writing unsafe queries with a bare negation or an unbounded ∨.

  • Forgetting vacuous truth. A ∀ over an empty set is always true.


Interview and Exam Questions

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

Algebra is procedural: it specifies a sequence of operations. Calculus is declarative: it specifies a condition that the result must satisfy.

Q2. What is the difference between TRC and DRC?

In TRC, variables represent whole tuples (t ∈ Student). In DRC, variables represent individual attribute values (<i, n, d, a> ∈ Student).

Q3. What is an unsafe query? Give an example.

A query whose result may be infinite or depend on values outside the database, for example { t | ¬(t ∈ Student) }.

Q4. What does "relationally complete" mean?

A language is relationally complete if it can express every query that basic relational algebra (equivalently, safe relational calculus) can express. SQL is relationally complete.

Q5. How do you write a "for all" query in SQL?

Convert ∀ into ¬∃¬, which gives a double NOT EXISTS: "there is no required item that this entity does not have".

Q6. Which algebra operator corresponds to ∀ in calculus?

Division (÷).


Summary

  • Relational calculus is a declarative query language based on predicate logic: it states what the result must satisfy.

  • TRC uses tuple variables: { t | P(t) }. DRC uses domain variables: { <x1..xn> | P }.

  • Projection is done with ∃, joins with ∃ plus equality (or shared variables in DRC), difference with ¬∃, and division with ∀.

  • ∀x P ≡ ¬∃x ¬P turns "for all" into SQL's double NOT EXISTS.

  • Only safe expressions (results drawn from the database and constants) are allowed.

  • By Codd's theorem, safe TRC, safe DRC and basic relational algebra have the same expressive power.

With query languages covered, the next chapter, Functional Dependencies, moves to database design: how attributes depend on each other, and why that decides whether a table is well designed.