Relational Calculus

By the end of this lesson you will be able to read and write simple tuple relational calculus (TRC) and domain relational calculus (DRC) queries, use the quantifiers ∃ and ∀, spot unsafe expressions, and explain how calculus, algebra and SQL relate. This is an overview at the level university exams and GATE expect.

Algebra says how, calculus says what

Relational algebra is procedural: you list operations in order. Relational calculus is non-procedural (declarative): you describe the rows you want with a logical condition, and say nothing about how to find them.

A food delivery analogy: algebra is like giving the rider turn-by-turn directions. Calculus is like giving the address and letting the rider choose the route. SQL is closer to calculus, which is why SQL also lets the DBMS choose the route.

There are two flavours:

The pieces of a calculus formula

A calculus query has the form { result | condition }, read as "the set of results such that the condition is true". The condition is built from:

1. Atoms: t ∈ customers (t is a row of customers), t.city = 'Rohtak', t.price > s.price.
2. Connectives: ∧ (and), ∨ (or), ¬ (not), ⇒ (implies).
3. Quantifiers: ∃ ("there exists at least one") and ∀ ("for all").

A variable is bound if a quantifier introduces it, and free otherwise. In a TRC query, the variable on the left of | must be the only free variable.

Tuple relational calculus

Example 1: customers who live in Rohtak.

{ t | t ∈ customers ∧ t.city = 'Rohtak' }

Read it as: "all rows t such that t is a customer and t's city is Rohtak". To return only some attributes, write them on the left:

{ t.first_name, t.city | t ∈ customers ∧ t.state = 'Haryana' }

Example 2: names of customers who have placed at least one order. This needs ∃, because the order row is not part of the answer:

{ c.first_name | c ∈ customers ∧ ∃ o ( o ∈ orders ∧ o.customer_id = c.customer_id ) }

The existential quantifier maps directly to SQL's EXISTS. Step 1: read the formula. Step 2: run the SQL that says the same thing.

SELECT c.first_name
FROM customers c
WHERE c.state = 'Haryana'
  AND EXISTS (
    SELECT * FROM orders o
    WHERE o.customer_id = c.customer_id
  )
ORDER BY c.first_name;

first_name
----------
Aarav
Isha
Vikram
(3 rows)

You should see all three Haryana customers, since each has at least one order.

The universal quantifier ∀

Example 3: products whose every order line had quantity 1. "Every" means ∀:

{ p.product_name | p ∈ products ∧ ∃ x ( x ∈ order_items ∧ x.product_id = p.product_id )
                   ∧ ∀ i ( i ∈ order_items ∧ i.product_id = p.product_id ⇒ i.quantity = 1 ) }

SQL has no FOR ALL. You use the logic rule ∀x P(x) ≡ ¬∃x ¬P(x): "every line has quantity 1" is the same as "there is no line with quantity other than 1".

SELECT p.product_name
FROM products p
WHERE EXISTS (SELECT * FROM order_items x WHERE x.product_id = p.product_id)
  AND NOT EXISTS (
    SELECT * FROM order_items i
    WHERE i.product_id = p.product_id AND i.quantity <> 1
  )
ORDER BY p.product_name;

product_name
---------------------------
1TB External SSD
Bluetooth Speaker
HD Webcam
Mechanical Keyboard
Noise-Cancelling Headphones
(5 rows)

You should see five products. The 27-inch Monitor is missing because order 110 bought two of them, and the 64GB Pen Drive is missing because order 112 bought four.

Why does the formula also need the ∃ x part? Because a ∀ condition over nothing is true. This is called vacuous truth: "every order line for the Graphics Tablet had quantity 1" is true when there are no order lines at all. Step 3: drop the EXISTS line and see the never-ordered tablet sneak in.

SELECT p.product_name
FROM products p
WHERE NOT EXISTS (
  SELECT * FROM order_items i
  WHERE i.product_id = p.product_id AND i.quantity <> 1
)
ORDER BY p.product_name;

product_name
---------------------------
1TB External SSD
Bluetooth Speaker
Graphics Tablet
HD Webcam
Mechanical Keyboard
Noise-Cancelling Headphones
(6 rows)

You should now see six products, including the Graphics Tablet, which was never ordered. Always ask whether a "for all" question should include things that have no rows at all.

Domain relational calculus

In DRC, each variable stands for one column value, and a relation is written as a predicate with one variable per column:

customers(id, fn, ln, city, state, email, joined)

Example 1 in DRC, first names and cities of Haryana customers:

{ <fn, city> | ∃ id, ln, st, em, j ( customers(id, fn, ln, city, st, em, j) ∧ st = 'Haryana' ) }

DRC is wordier for wide tables, but it is the idea behind QBE (Query By Example), where you fill example values into a grid that looks like the table.

Safe expressions

Some calculus formulas describe an infinite answer. Consider:

{ t | ¬ (t ∈ customers) }

"All tuples that are not customers" includes every possible row in the universe: infinitely many. Such a formula is unsafe. A safe expression is one whose result values all come from the database (or constants in the query), so the answer is always finite. In exams, an expression is suspicious whenever a variable appears only under ¬ and is not tied to a relation with ∈ first.

How the three languages compare

Codd showed in the early 1970s that relational algebra and safe relational calculus have the same expressive power: any query in one can be written in the other. A query language with at least this power is called relationally complete.

So SQL is relationally complete and more: COUNT, GROUP BY and ORDER BY cannot be written in pure algebra or calculus.

Common mistakes

• Leaving extra free variables. In { t | ... } only t may be free; every other variable needs ∃ or ∀.
• Using ∀ with ∧ instead of ⇒. ∀ i (i ∈ order_items ∧ i.quantity = 1) claims every row in the universe is an order item. The correct pattern is ∀ i (i ∈ R ∧ condition ⇒ result).
• Calling calculus procedural. Calculus states what; algebra states how.
• Forgetting safety. A negation without a positive ∈ condition can make the answer infinite.

Key points

• Relational calculus is declarative: { result | condition }.
• TRC variables range over tuples; DRC variables range over column values.
• ∃ maps to SQL EXISTS; ∀ is written as NOT EXISTS ... NOT using ∀x P ≡ ¬∃x ¬P.
• Safe expressions return only values from the database, so the result is finite.
• Relational algebra, safe TRC and safe DRC are equally powerful; such languages are relationally complete.
• SQL is relationally complete and adds aggregates, ordering and duplicates.

{ e.first_name | e ∈ employees ∧ ∀ s ( s ∈ employees ∧ s.department = 'Sales' ⇒ e.salary > s.salary ) }

SELECT e.first_name
FROM employees e
WHERE NOT EXISTS (
  SELECT * FROM employees s
  WHERE s.department = 'Sales' AND s.salary >= e.salary
)
ORDER BY e.salary DESC;