4.2 Relational Calculus
Procedural vs Non-Procedural Languages
In a Procedural Language, we mention clearly what the predicate should be, what the condition is, what should be selected or projected, and what result should be computed. Relational Algebra is a procedural language.
In a Non-Procedural Language (also called a declarative language), we only describe what the output should be like and what the property of the result should be like. It is the job of the DBMS system to figure out how to get the result.
Relational Calculus is a non-procedural language. It has two types:
- Tuple Relational Calculus
- Domain Relational Calculus
Predicate Logic
Relational Calculus is based on Predicate Logic. Predicate Logic is an extension of Propositional Logic with variables and quantifiers. It was proposed to make Propositional Logic more expressive.
Propositional Logic and Its Limitations
A proposition is a declarative statement which has either a True or False value. Propositional Logic is a formal logic system where propositions are connected using logical connectives.
Consider these statements:
- P: Socrates is mortal.
- Q: Plato is mortal.
From these two statements, we cannot conclude that “All Humans are mortal”. Propositional Logic has this limitation. It cannot be generalized and does not have patterns or relationships.
In Predicate Logic, we break the statement down into objects, relations, and properties. For example, \text{Human}(\text{Socrates}) means Socrates is an object, and every property of Human will be applicable to Socrates.
Relational Logic is also called First-Order Logic.
Quantifiers
There are two types of quantifiers.
- Universal Quantifier (\forall) means “for all”.
\forall x (\text{Human}(x) \rightarrow \text{Mortal}(x))
For every x, if x is Human then x is mortal.
- Existential Quantifier (\exists) means “there exists”.
\exists x \; \text{Student}(x)
There exists an x such that x is a Student.
Tuple Relational Calculus
Formula:
\{ t \mid P(t) \}
It is the set of all tuples t such that predicate P is true for t. P(t) may have various logical connectives such as \land (and), \lor (or), \lnot (not), and \Rightarrow (implication).
Examples
Find the first names of students whose age is greater than 21.
\{ t.\text{fname} \mid \text{Student}(t) \land t.\text{age} > 21 \}
There are various ways to represent the same query:
\begin{gather*} \{ t.\text{Fname} \mid \text{Student}(t) \land t.\text{age} > 21 \} \\ \{ t.\text{Fname} \mid t \in \text{Student} \land t.\text{age} > 21 \} \\ \{ t \mid \exists s \in \text{Student} (s.\text{age} > 21 \land t.\text{Fname} = s.\text{Fname}) \} \end{gather*}
If we have more than one attribute to project, we connect them using the \land connective. For example, \{ t \mid t.\text{age} = s.\text{age} \land t.\text{name} = s.\text{name} \}.
The expression \{ t \mid s.\text{courseid} = c.\text{courseid} \} is how we represent an inner join in Relational Calculus.
Domain Relational Calculus
Domain Relational Calculus treats a tuple as a collection of domain values.
Formula:
\{ \langle x_1, x_2, \dots, x_n \rangle \mid P(x_1, x_2, \dots, x_n) \}
Each x_i represents a domain variable. P represents a formula similar to that of predicate calculus.
Equivalence of Algebra and Calculus
Relational Algebra and Relational Calculus are equivalent in expressive power. Every query that can be expressed in Relational Algebra can also be expressed in Relational Calculus, and the other way around.
Module Summary
Relational Calculus is a non-procedural language based on Predicate Calculus. It comes in two forms: Tuple Relational Calculus, where queries are of the form \{ t \mid P(t) \}, and Domain Relational Calculus, where queries are of the form \{ \langle x_1, \dots, x_n \rangle \mid P(x_1, \dots, x_n) \}. Both are equivalent in power to Relational Algebra.