Objectives

Upon completion of this lesson, you will be able to:

  • define a tuple relational calculus expression
  • use tuple relational calculus to express queries
  • contrast relational calculus with relational algebra

Overview

Relational calculus is an alternative to relational algebra for specifying queries of a relational schema in an abstract manner. Unlike relational algebra it is a non-procedural or declarative query language as it specifies what is to be retrieved rather than how to retrieve it. In relational calculus, queries are expressed in the form of set expressions that define the properties of the resultant relation.

There are two forms of relational calculus: - tuple relational calculus (TRC), and - domain relational calculus (DRC).

This lesson focuses on tuple relational calculus.

In tuple relational calculus, the set specification ranges over tuples from a specified relation. Relational calculus is based on first order predicate logic.

Tuple Variables

The TRC is based on tuple variables, which take tuples of a specific relation as its values. A simple TRC query is of the form:

\(\{t:P(t)\}\) or \(\{t | P(t)\}\)

where, \(t\) is a tuple variable and \(P(t)\) is a condition or formula for defining which tuples should be selected from a relation. The resultant relation of this query is the set of all tuples \(t\) for which the condition \(P(t)\) evaluates to true.

Example Expressions

For the examples, assume the schema and relation instance below:

\(book(\underline{sku},title,price,author)\)

{(1107, "Introduction to C++", "Peter Maffei", 39.95), 
 (1009, "Software Architecture", "Nina Hagen", 69.50), 
 (1432, "Project Management" , "Udo Lindenbergh", 49.99), 
 (3309, "Predicate Logic", "Doris Day", 129.00)}

Example I: Selection

The tuple relational calculus expression is a selection of specific tuples from a relation.

\(\{t : book(t) \land t.price > 50\}\)

specifies all tuples that are in the relation \(book\) and have a value of the price attribute more than 50, i.e., this is the query “find all books that cost more than $50”.

In the TLC expression, \(t\) is a tuple variable that binds to all tuples that match the specification. The result of the expression is a set of tuples. Recall that a set cannot, by definition, contain duplicates so there is no need to some kind of “unique” or “distinct” operator as is needed in SQL.

As an exercise, express the tuple relational calculus expression above in SQL.

Example II: Projection

The tuple relational calculus expression below is a selection with a projection from a relation.

\(\{t.title, t.price : book(t) \land t.price > 10\}\)

specifies all tuples that are in the relation \(book\) and have a value of the price attribute of more than 10, i.e., this is the query “retrieve the title and price of all books that cost more than $50”.

The above expression could be expressed in relational algebra with:

\(\pi_{t.title,t.price}(\sigma_{t.price \gt 10}(\rho_{t}(book)))\)

or, more simply,

\(\pi_{title,price}(\sigma_{price \gt 10}(book))\)

Likewise, the expression could be expressed in SQL as follows:

SELECT t.title, t.price
  FROM book AS t
 WHERE t.price > 10;

Expressions & Formulas

A general expression in the tuple relational calculus consists of a tuple variable \(t\) and a formula \(P(t)\). A formula consists of one or more tuple variables and is composed of atoms.

Logical Operators

Logical (or Boolean) operators are used to build atoms that evaluate to either TRUE or FALSE. These, in turn, are grouped into logical expressions which also have a truth value. The table below summarizes the logical operators. Note that the operators are the same as those found in first order logic.

Operator Alternative Meaning Example Explanation
\(\land\) AND, +, & AND \(Q \land W\) True only if both \(Q\) and \(W\) are true
\(\lor\) OR, |, || OR \(Q \lor W\) True only if either or both \(Q\) and \(W\) are true
\(\neg\) NOT, ~, ! NOT \(\neg Q\) True if \(Q\) is false
\(\exists\) Existential Quantifier \(\exists P(Q)\) There is at least one \(Q\) for which the expression \(P\) is true
\(\exists !\) Uniqueness Quantifier \(\exists !P(Q)\) There is exactly one \(Q\) for which the expression \(P\) is true
\(\nexists\) Existential Quantifier \(\nexists P(Q)\) There is no \(Q\) for which the expression \(P\) is true
\(\forall\) Universal Quantifier \(\forall P(Q)\) The expression \(P\) is true for all \(Q\)
\(\implies\) \(\to\) implies \(Q \implies P\) If \(Q\) is true, then \(P\) must be true as well

Rules for Building Formulas

  1. An atom is a formula.
  2. If \(F\) is a formula, then so is \(\neg F\).
  3. If \(F_1\) and \(F_2\) are formulae, then so are \(F_1 \land F_2\), \(F_1 \lor F_2\) and \(F_1 \implies F_2\), where \(F_1 \implies F_2\) is also equivalent to \(\neg{F_1} \lor F_2)\).
  4. If \(F\) is a formula, then so is \(\exists{t}(F)\), where \(t\) is a tuple variable.
  5. If \(F\) is a formula, then so is \(\forall{t}(F)\), where \(t\) is a tuple variable.

Bound vs Free Tuple Variables

A tuple variable \(t\) is said to be bound, if it is quantified, i.e., it appears in either a \(\exists t\) or a \(\forall t\) clause, otherwise, it is said to be free.

Transforming Quantifiers

An expression containing a universal quantifier \(\forall\) can be transformed into an equivalent expression containing an existential quantifier \(\exists\), \(\nexists\), \(\exists !\) and vice versa, using these rules:

  1. Replace one type of quantifier with the other and precede the quantifier by \(\neg\)
  2. Replace \(\land\) with \(\lor\) operator and vice versa
  3. Negate formula with \(\neg\)

Below are some examples or equivalent expressions to illustrate the above transformation rules.

  • \(\exists T(F) \equiv \neg \forall T(\neg F)\), which means that it is not true that for all \(T\) the formula \(F\) is false is the same as saying there exists a \(T\) for which the formula \(F\) is true
  • \(\forall T(F) \equiv \neg \exists T(\neg F)\), which means that for all \(T\) the formula \(F\) is true is equivalent to there not existing a \(T\) for which the formula \(F\) is not true

And, a few more – translate each one of them to “English” or your favorite spoken language and see if the transformations make sense.

  • \((\exists T)(F_1 ∧ F_2) \equiv \neg(\forall T)(\neg F_1 ∨ \neg F_2)\)
  • \((\forall T)(F_1 ∨ F_2) \equiv \neg(\exists T)(\neg F_1 ∧ \neg F_2)\)
  • \((\exists T)(\neg F_1 ∨ ¬ F_2) \equiv \neg(\forall T)(F_1 ∧ F_2)\)
  • \((\forall T)(\neg F_1 ∧ ¬ F_2) \equiv \neg(\exists T)(F_1 ∨ F_2)\)

Example Expressions

This section presents a number of examples, based on the relational schema below.

authors (aid, aname, city, phone, email)
books (isbn, title, price, category, page_count, pid)
publishers (pid, pname, address, phone, url)
authorships (aid, isbn)

Find the city, phone, and email of the author whose name is Brett Lantz.

\(\{t.city, t.phone, t.email : authors(t) \land t.aname = “Brett Lantz”\}\)

or

\(\{t.city, t.phone, t.email | (t \in authors) \land (t.aname = “Brett Lantz”)\}\)

Find the title and price of all textbooks with more than 1000 pages.

\(\{b.title, b.price : books(b) \land b.category = “Textbook” \land b.page_count > 1000\}\)

Find the name and phone of publishers that publish textbooks.

\(\{t.pname, t.phone : publishers(t) \land (\exists b)(books(b) \land b.pid = t.pid \land b.category = “Textbook”)\}\)

Find the name of the author and the category of the book with the title “SQL”.

\(\{a.aname, b.category : authors(a) \land books(b) ∧ b.title = “SQL” \land ((\exists p)(authorships(p) \land a.aid = p.aid \land p.isbn = b.isbn))\}\)

There are no operators for substring searching or regular expressions, but we can add them as ad hoc extensions as needed as long as we define them. For example, we might introduce the operator \(\triangleright\) to mean “contains text”. So, our expression to find books with the title that contains the string “SQL” might be \((b.title \triangleright “SQL”)\).

Retrieve title, price, author name for all books published by “Packt”.

\(\{b.title, b.price, a.aname : books(b) \land authors(a) \land ((\exists p) (\exists r) (publishers(p) \land authorships(r) \land b.isbn = r.isbn \land r.aid = a.aid \land b.pid = p.pid \land p.pname = “Packt”))\}\)

Retrieve name and address of publishers who have not published any books.

\(\{p.pname, p.address : publishers(p) \land (\neg(\exists b)(books(b) \land p.pid = b.pid))\}\)

or, equivalently,

\(\{p.pname, p.address : publishers(p) \land ((\forall b)(\neg (books(b)) \lor \neg (p.pid = b.pid)))\}\)

Unsafe Expressions

Safe vs Unsafe Expressions

An expression containing a universal quantifier, or an existential quantifier or a negation may lead to a resultant relation with infinite numbers of tuples:

\(\{b : \neg books(b)\}\)

This expression is syntactically correct but refers to all tuples that do not belong to the books relation, which, of course, is infinite. These types of expressions are known as unsafe expressions. A safe expression is an expression which results in a relation with finite number of tuples.

Relational Algebra vs Calculus

The two approaches are equivalent. Queries expressed in relational algebra can also be expressed in tuple relational calculus and vice versa. The difference is only in the notation used to express the queries: one is procedural while the other is declarative.

Tutorial

The video tutorial below is a narration of this lesson supported by the linked slide deck.

Slide Deck: Relational Calculus

Summary

Tuple relational calculus is an abstract and declarative mechanism for expressing queries on relations using first order predicate logic expressions containing formula composed of atoms. An alternative to tuple relational calculus are domain relational calculus and relational algebra.

Files & Resources

All Files for Lesson 60.505

References

None.

Errata

None collected yet. Let us know.