Quiz 2
Registry Synced

11 - Relational Calculus

1740 words
9 min read

Reading compass

Now · 🎯 Learning Objectives

11 - Relational Calculus

🎯 Learning Objectives

After reading this topic, you will be able to:
  • Write queries in tuple relational calculus (TRC)
  • Write queries in domain relational calculus (DRC)
  • Explain the difference between procedural (algebra) and non-procedural (calculus)
  • Understand safety in calculus expressions
  • Translate between TRC, relational algebra, and SQL

📋 Prerequisites

  • 10 - Relational Algebra — Basic relational operations
  • Predicate logic (BSMA1001 — Maths 1) — ∃ (exists), ∀ (for all)

📖 Core Content

11.1 Intuition: WHAT Not HOW

Relational algebra is procedural — you specify the steps:
πname(σdeptname=′CS′(instructor))\pi_{name}(\sigma_{dept_name='CS'}(instructor))
"First select, then project." Relational calculus is declarative — you specify WHAT you want:
{t∣t∈instructor∧t.deptname=′CS′}\{t \mid t \in instructor \land t.dept_name = 'CS'\}
"Give me tuples t such that t is in instructor and t's department is CS." The DBMS figures out HOW to get it. Calculus is closer to how humans think about queries.
Why This Matters: Relational calculus is the theoretical basis for SQL's declarative nature. Every SQL query has an equivalent calculus expression.

11.2 Tuple Relational Calculus (TRC)

A TRC query has the form:
{t∣P(t)}\{t \mid P(t)\}
Where:
  • tt is a tuple variable (ranges over tuples)
  • P(t)P(t) is a formula (predicate) describing tt

Basic Queries

Find all instructors in CS:
{t∣t∈instructor∧t.deptname=′Comp.Sci.′}\{t \mid t \in instructor \land t.dept_name = 'Comp. Sci.'\}
Find instructor names and salaries:
{t∣∃s∈instructor (t.name=s.name∧t.salary=s.salary)}\{t \mid \exists s \in instructor\ (t.name = s.name \land t.salary = s.salary)\}

Using ∃ (Exists)

{t∣∃s∈instructor (t.name=s.name∧s.salary>80000)}\{t \mid \exists s \in instructor\ (t.name = s.name \land s.salary > 80000)\}
Instructors with salary > 80000. The ∃ says "there exists an instructor s satisfying these conditions."

Using ∃ for Joins

Find names of instructors who teach a course:
{t∣∃i∈instructor ∃c∈teaches (i.ID=c.ID∧t.name=i.name)}\{t \mid \exists i \in instructor\ \exists c \in teaches\ (i.ID = c.ID \land t.name = i.name)\}
"There exists an instructor i and a teaching assignment c such that i.ID = c.ID, and t.name is i.name."

Using ∀ (For All)

Find students who have taken EVERY course (division):
{t∣∃s∈student (∀c∈course (∃e∈takes (e.ID=s.ID∧e.courseid=c.courseid)))}\{t \mid \exists s \in student\ (\forall c \in course\ (\exists e \in takes\ (e.ID = s.ID \land e.course_id = c.course_id)))\}
"For a student s, for every course c, there exists an enrollment e matching the student to the course."

Implication (⇒)

P⇒Q≡¬P∨QP \Rightarrow Q \equiv \lnot P \lor Q
Find students who, IF they take a course, get an 'A':
{t∣∃s∈student (∀e∈takes (e.ID=s.ID⇒e.grade=′A′))}\{t \mid \exists s \in student\ (\forall e \in takes\ (e.ID = s.ID \Rightarrow e.grade = 'A'))\}

11.3 Domain Relational Calculus (DRC)

DRC uses domain variables (column values) instead of tuple variables:
{⟨x1,x2,…,xn⟩∣P(x1,x2,…,xn)}\{\langle x_1, x_2, \dots, x_n \rangle \mid P(x_1, x_2, \dots, x_n)\}
Find instructor ID, name, department, salary for CS:
{⟨i,n,d,s⟩∣⟨i,n,d,s⟩∈instructor∧d=′CS′}\{\langle i, n, d, s \rangle \mid \langle i, n, d, s \rangle \in instructor \land d = 'CS'\}
Find names of instructors in CS (only name projected):
{n∣∃i ∃d ∃s (⟨i,n,d,s⟩∈instructor∧d=′CS′)}\{n \mid \exists i\ \exists d\ \exists s\ (\langle i, n, d, s \rangle \in instructor \land d = 'CS')\}

DRC Join Example

Find names of instructors who teach a course:
{n∣∃i ∃d ∃s ∃ci ∃se ∃y (⟨i,n,d,s⟩∈instructor∧⟨i,ci,se,y⟩∈teaches)}\{n \mid \exists i\ \exists d\ \exists s\ \exists ci\ \exists se\ \exists y\ (\langle i, n, d, s \rangle \in instructor \land \langle i, ci, se, y \rangle \in teaches)\}

11.4 Safety

A calculus expression must be safe — it should produce a finite result. Unsafe expression:
{t∣¬(t∈instructor)}\{t \mid \lnot (t \in instructor)\}
This would return "all tuples NOT in instructor" — an infinite set (since the universe of all possible tuples is infinite). Safety condition: All values in the result must come from the domain of the database (constants in the query or values in the actual relations).

11.5 Equivalence: Calculus, Algebra, SQL

QueryRelational AlgebraTRCSQL
CS instructorsπname(σdept=′CS′(inst))\pi_{name}(\sigma_{dept='CS'}(inst)){t∣∃i∈inst (i.dept=′CS′∧t.name=i.name)}\{t \mid \exists i \in inst\ (i.dept='CS' \land t.name=i.name)\}SELECT name FROM instructor WHERE dept_name = 'CS'
CS instructors earning > 80000πname(σdept=′CS′∧sal>80000(inst))\pi_{name}(\sigma_{dept='CS' \land sal>80000}(inst)){t∣∃i∈inst (i.dept=′CS′∧i.sal>80000∧t.name=i.name)}\{t \mid \exists i \in inst\ (i.dept='CS' \land i.sal>80000 \land t.name=i.name)\}SELECT name FROM instructor WHERE dept_name = 'CS' AND salary > 80000

11.6 Worked Examples

Example 1: TRC → English

{t∣∃i∈instructor (i.salary>90000∧t.name=i.name)}\{t \mid \exists i \in instructor\ (i.salary > 90000 \land t.name = i.name)\}
"Find the names of all instructors whose salary exceeds 90000."

Example 2: Join in TRC

Find course IDs taught by instructors in the Physics department:
{c∣∃i∈instructor ∃t∈teaches (i.ID=t.ID∧i.deptname=′Physics′∧c=t.courseid)}\{c \mid \exists i \in instructor\ \exists t \in teaches\ (i.ID = t.ID \land i.dept_name = 'Physics' \land c = t.course_id)\}

Example 3: DRC for same query

{c∣∃i ∃n ∃d ∃s ∃se ∃y (⟨i,n,d,s⟩∈instructor∧⟨i,c,se,y⟩∈teaches∧d=′Physics′)}\{c \mid \exists i\ \exists n\ \exists d\ \exists s\ \exists se\ \exists y\ (\langle i, n, d, s \rangle \in instructor \land \langle i, c, se, y \rangle \in teaches \land d = 'Physics')\}

📐 Key Formulas / Concepts

Calculus TypeSyntaxVariablesUsage
Tuple RC{t∣P(t)}\{t \mid P(t)\}Tuple variable ttRanges over tuples
Domain RC{⟨x1,...,xn⟩∣P(x1,...,xn)}\{\langle x_1, ..., x_n \rangle \mid P(x_1, ..., x_n)\}Domain variablesIndividual attribute values
∃ (exists)∃t∈R (P(t))\exists t \in R\ (P(t))—"There exists"
∀ (for all)∀t∈R (P(t))\forall t \in R\ (P(t))—"For all"
⇒ (implies)P⇒QP \Rightarrow Q—"If P then Q"

⚠️ Common Pitfalls

Pitfall 1: Confusing Calculus with Algebra

The Mistake: Thinking TRC is the same as relational algebra. Why It's Wrong: Algebra is procedural (specifies steps); calculus is declarative (specifies properties). Algebra uses operators (σ, π); calculus uses predicate logic (∃, ∀). Correct: Algebra = "how to compute it"; Calculus = "what it is."

Pitfall 2: Writing Unsafe Expressions

The Mistake: {t∣¬(t∈instructor)}\{t \mid \lnot (t \in instructor)\} Why It's Wrong: This asks for "all tuples not in instructor" — an infinite set, since there are infinitely many possible tuples that aren't in instructor. Fix: Every value in the result must appear in the database relations or as a query constant.

Pitfall 3: Misusing Implication

The Mistake: In the query "Find students who only take CS courses," writing:
{t∣∃s∈student (∀e∈takes (s.ID=e.ID∧e.courseid starts with ’CS’))}\{t \mid \exists s \in student\ (\forall e \in takes\ (s.ID = e.ID \land e.course_id \text{ starts with 'CS'}))\}
Why It's Wrong: This says "for all enrollment e, s.ID = e.ID" — meaning the student must be enrolled in EVERY course in the takes table! Correct: Use implication:
{t∣∃s∈student (∀e∈takes (s.ID=e.ID⇒e.courseid starts with ’CS’))}\{t \mid \exists s \in student\ (\forall e \in takes\ (s.ID = e.ID \Rightarrow e.course_id \text{ starts with 'CS'}))\}
"If the student takes a course, it must be a CS course" — this correctly handles students who take no courses too.

📝 Practice Questions

Q1. Write a TRC expression to find names of all instructors in Physics.

Answer
{t∣∃i∈instructor (i.deptname=′Physics′∧t.name=i.name)}\{t \mid \exists i \in instructor\ (i.dept_name = 'Physics' \land t.name = i.name)\}
This returns names (single-attribute tuples) of all instructors whose department is Physics.

Q2. What is the key difference between TRC and relational algebra?

Answer
Relational AlgebraTuple Relational Calculus
Procedural (specifies operations in order)Declarative (specifies properties of result)
Uses operators: σ, π, ⋈, etc.Uses predicate logic: ∃, ∀, ∧, ∨, ¬
Step-by-step computation"What is true about the result?"
Easier to optimize mechanicallyCloser to human thinking

Q3. Write a DRC expression for: Find the IDs of all students who have taken a course with course_id 'CS-101'.

Answer
{i∣∃n ∃d ∃tc (⟨i,n,d,tc⟩∈student∧∃ci ∃se ∃y ∃g (⟨i,ci,se,y,g⟩∈takes∧ci=′CS−101′))}\{i \mid \exists n\ \exists d\ \exists tc\ (\langle i, n, d, tc \rangle \in student \land \exists ci\ \exists se\ \exists y\ \exists g\ (\langle i, ci, se, y, g \rangle \in takes \land ci = 'CS-101'))\}
Or more simply: {i∣∃ci ∃se ∃y ∃g (⟨i,ci,se,y,g⟩∈takes∧ci=′CS−101′)}\{i \mid \exists ci\ \exists se\ \exists y\ \exists g\ (\langle i, ci, se, y, g \rangle \in takes \land ci = 'CS-101')\}

Q4. What does it mean for a calculus expression to be "safe"?

Answer
A calculus expression is safe if all values in the result are guaranteed to come from the database domain (the actual values in the relations or constants in the query).
An unsafe expression like {t∣¬(t∈instructor)}\{t \mid \lnot(t \in instructor)\} would produce an infinite result (all possible tuples not in instructor — which is infinite).
Safe expressions ensure the result is finite and computable.

Q5. Translate to English: {t∣∃i∈instructor ∃d∈department (i.deptname=d.deptname∧d.building=′Watson′∧t.name=i.name)}\{t \mid \exists i \in instructor\ \exists d \in department\ (i.dept_name = d.dept_name \land d.building = 'Watson' \land t.name = i.name)\}

Answer
"Find the names of all instructors who work in a department located in the Watson building."
The query joins instructor and department on dept_name, filters for Watson building, and returns instructor names.

Q6. Use ∀ to write a TRC query: "Find students who have taken every course offered by the CS department."

Answer
{t∣∃s∈student (∀c∈course (c.deptname=′Comp.Sci.′⇒∃e∈takes (e.ID=s.ID∧e.courseid=c.courseid)))}\{t \mid \exists s \in student\ (\forall c \in course\ (c.dept_name = 'Comp. Sci.' \Rightarrow \exists e \in takes\ (e.ID = s.ID \land e.course_id = c.course_id)))\}
"For a student s, for every course c: if c is a CS course, then there exists an enrollment e showing that s took c."

Q7. Compare ∃ and ∀ in TRC with examples.

Answer
  • ∃ (exists): "There exists at least one" — used for existence checks. Example: {t∣∃i∈instructor (i.deptname=′CS′∧t.name=i.name)}\{t \mid \exists i \in instructor\ (i.dept_name = 'CS' \land t.name = i.name)\} — "there is an instructor in CS"
  • ∀ (for all): "For every" — used for universal quantification. Example: {t∣∀c∈course (∃e∈takes (e.ID=t.ID∧e.courseid=c.courseid))}\{t \mid \forall c \in course\ (\exists e \in takes\ (e.ID = t.ID \land e.course_id = c.course_id))\} — "for every course, the student took it"

Q8. Convert this SQL to TRC: SELECT name FROM instructor WHERE dept_name = 'CS' AND salary > ALL (SELECT salary FROM instructor WHERE dept_name = 'Biology');

Answer
{t∣∃i∈instructor (i.deptname=′CS′∧i.salary>ALL ({s∣∃j∈instructor (j.deptname=′Biology′∧s.salary=j.salary)})∧t.name=i.name)}\{t \mid \exists i \in instructor\ (i.dept_name = 'CS' \land i.salary > ALL\ (\{s \mid \exists j \in instructor\ (j.dept_name = 'Biology' \land s.salary = j.salary)\}) \land t.name = i.name)\}
Or more simply: "Find names of CS instructors whose salary is greater than every salary in Biology."

🔗 Cross-References

Document outline

Keep your place and jump directly to a heading.

Table of Contents
System Normal // Awaiting Context

Intelligence Hub

Navigate the knowledge graph to generate context. The Hub adapts dynamically to surface backlinks, related notes, and metadata insights.

Open library →Launch Assessment Engine