Relational calculus

The relational calculus consists of two calculi, the tuple relational calculus and the domain relational calculus, that is part of the relational model for databases and provide a declarative way to specify database queries. The raison d'être of relational calculus is the formalization of query optimization, which is finding more efficient manners to execute the same query in a database.

The relational calculus is similar to the relational algebra, which is also part of the relational model: While the relational calculus is meant as a declarative language that prescribes no execution order on the subexpressions of a relational calculus expression, the relational algebra is meant as an imperative language: the sub-expressions of a relational algebraic expression are meant to be executed from left-to-right and inside-out following their nesting.

Per Codd's theorem, the relational algebra and the domain-independent relational calculus are logically equivalent.

Example

A relational algebra expression might prescribe the following steps to retrieve the phone numbers and names of book stores that supply Some Sample Book:

Join book stores and titles over the BookstoreID.
Restrict the result of that join to tuples for the book Some Sample Book.
Project the result of that restriction over StoreName and StorePhone.

A relational calculus expression would formulate this query in the following descriptive or declarative manner:

Get StoreName and StorePhone for book stores such that there exists a title BK with the same BookstoreID value and with a BookTitle value of Some Sample Book.

Equivalence with relational algebra

The relational algebra and the domain-independent relational calculus are logically equivalent: for any algebraic expression, there is an equivalent expression in the calculus, and vice versa. This result is known as Codd's theorem.

Let the relations be:

Bookstores ( $B$ ) with attributes (BookstoreID, StoreName, StorePhone, …), and
Titles ( $T$ ) with attributes (BookstoreID, BookTitle, …).

Relational algebra expression

The query can be written as: $\pi _{StoreName,StorePhone}(\sigma _{BookTitle='SomeSampleBook'}(B\bowtie _{B.BookstoreID=T.BookstoreID}T))$

A more explicit equivalent form is: $\pi _{StoreName,StorePhone}(B\bowtie _{B.BookstoreID=T.BookstoreID}(\sigma _{BookTitle='SomeSampleBook'}(T)))$

The second form is often preferred because it pushes the selection down before the join.

Relational calculus expression

In tuple relational calculus, the same query is:

$\{\langle b.StoreName,b.StorePhone\rangle \mid B(b)\wedge \exists t:(T(t)\wedge b.BookstoreID=t.BookstoreID\wedge t.BookTitle='SomeSampleBook')\}$

This says: return the store name and phone number of every bookstore $b$ for which there exists a title tuple $t$ with matching BookstoreID and the book title equal to "Some Sample Book".

Mathematical properties that prove the equivalence

The proof rests on the standard equivalence between join, selection, projection, and existential quantification.

Property A: Join + selection corresponds to conjunction with equality

$B\bowtie _{B.BookstoreID=T.BookstoreID}T$

means exactly the set of pairs (b, t) such that:

$B(b)\wedge T(t)\wedge b.BookstoreID=t.BookstoreID$

Then applying selection: $\sigma _{T.BookTitle='SomeSampleBook'}(\cdot )$

adds: $t.BookTitle='SomeSampleBook'$

So the algebraic expression becomes the set of all joined pairs satisfying:

$B(b)\wedge T(t)\wedge b.BookstoreID=t.BookstoreID\wedge t.BookTitle='SomeSampleBook'$

Property B: Projection corresponds to existential quantification

Projection over (StoreName,StorePhone) removes the title tuple and any other unneeded attributes. In logic, removing attributes corresponds to existentially quantifying them away.

So the projected algebra result corresponds to:

$\{\langle b.StoreName,b.StorePhone\rangle \mid \exists t:(B(b)\wedge T(t)\wedge b.BookstoreID=t.BookstoreID\wedge t.BookTitle='SomeSampleBook')\}$

which is exactly the calculus expression.

Property C: Selection pushdown is valid

Because selection only references $T.BookTitle$ , we can rewrite:

$\sigma _{BookTitle='SomeSampleBook'}(B\bowtie T)\equiv B\bowtie (\sigma _{BookTitle='SomeSampleBook'}(T))$

This is the relational algebra selection-pushdown law. It preserves meaning and often improves efficiency.

Final equivalence statement

Thus the relational algebra query and the relational calculus query are equivalent because:

$\pi _{StoreName,StorePhone}(\sigma _{BookTitle='SomeSampleBook'}(B\bowtie T))$

denotes the same set as