Relational Calculus

An alternative to relational algebra is relational calculus. It is a query system where queries are expressed as variables and formulas on these variables. It is a non-procedural or declarative by nature. In this, the formulas describe the properties of the required result relation without describing how to compute it i.e., query represents only results and hides the procedure to find the result. Relational calculus is based on predicate calculus, which is used to symbolize logical arguments in mathematics. Relational calculus has two variants. The first one is called Tuple Relational Calculus in which variables take on tuples as values. The second one is called Domain Relational Calculus in which variables range over the underlying domains.

Relational Calculus has strongly influenced the design of many query languages like SQL and QBE.

1. Tuple Relational Calculus

Every query in tuple relational calculus is expressed by a tuple calculus expression, which is the  basic  construct. A tuple  calculus expression  is  of  the  form

Here, T is a set of tuple variable and F is the formula involving T. The result of this query is the set of all tuples t for which the formula F(T) is true with T = t.

A tuple calculus expression is a non-procedural definition of some relation in terms of some given  set  of  relations.

1.1. Basic Concepts

Here, we discuss about how the tuple calculus formulas can be derived and the various concepts related  with  these  formulas.

1. Free variables : Each tuple variable within a formula is either free or A variable within a formula is said to be free if it is not quantified by the existential quantifier (∃) or  the  universal  quantifier (∀).
2. Bound variables : A variable in a formula is said to be bound if it is quantified by either existential quantifier (∃) or  the  universal  quantifier (∀).
3. Qualifled variable : A qualified variable is of the form t(A), where t is a tuple variable of some relation and A is an attribute of that Two qualified variables P(A) and Q(B) are domain  compatible if  attributes A and B  are domain  compatible.
4. Atom or atomic formula : An atom or atomic formula may be in any of the following forms :
   1. t ∈ R, where t  is a tuple  variable and  R is a
   2. t[A] ⊗ p[B], where ⊗ is any one of comparison operators ( =, ≠, <, >, ≤, ≥) and t[A] and p[B] are domain compatible variables.
   3. t[A] ⊗ Constant or Constant ⊗ t[A], where constant must be domain compatible.

5. Well formed Formula (WFF) : A well formed formula (WFF) is recursively defined to be one of the following.
   1. Every atom is a WFF
   2. If f is a WFF, then so are (f) and ¬f.
   3. If f and g  are WFF’s  ,  then so  are f  v g,  f  ∧ g,  f → g.
   4. If f(x) is a WFF  and x  is free,  then ∃x(f(x)) and ∀x(f(x))  are also  WFF’s
6. Closed WFF : A WFF is said  to  be closed  if  it  does  not contain  any  free  variable.
7. Open WFF : A WFF is said  to  be open  if  it  contains at  least  one  free variable.

Consider the relation Employee and Department shown in Figure 5.19 for examples on tuple relational  calculus.

Examples

1. Find all employee, having salary more than  7,000

It means we find those tuple (t) that belong to relation (r) Employee and having salary more  than 7,000.  The  result is  shown  in Figure  5.20.

2. Name of employees having salary more than 7000. Here we use  notation

means there exist a tuple t that belong to relation r such that predicate P(t) is true.

It means t is a tuple in relation employee for which value of tuple s and t are equal for attribute salary and for tuple t value of attribute salary is greater than 7000. The result is  shown  in  Figure  5.21.

3. Name and department of  employees  that are  working in  marketing

First line of query gives the name attribute from relation employee or it is like projection then Ù operator acts as join operation of relation Employee and Department. Last line of query acts  as selection  operation. The  result is  shown in  Figure 5.22.

4. Names of employees other than

The result is shown in Figure 5.23.

2. Domain Relational Calculus

Every query in Domain relational calculus is expressed by a domain calculus expression, which is  the  basic  construct. A domain  calculus  expression  is  of the  form

Here, D is a set of domain variables (d₁, d₂, …, dn) and F is a formula involving D(d₁, d₂, …, dn). The result of this query is the set of all tuples for which the formula is true. The operators used by the Domain relational calculus are same as those used by tuple relational calculus. A tuple relational calculus expression can be converted to a domain calculus expression by replacing each tuple variable  by n domain variables, where n is  the arity of the tuple variable.

2.1.  Basic Concepts

The definitions of Free variables, Bound variables and Qualified variables are same as in tuple relational calculus. Here, we discuss about other definitions that are different from tuple relational  calculus.

Atom or Atomic formula : An atom or atomic formula may be in any of the following forms:

1. D ∈ R, where D(d₁, d₂, …,d_n) is the set of domain variables and R is a relation with n attributes.
2. X ⊗ Y, where ⊗ is any one of comparison operators (=, ≠, <, >, ≤, ≥) and X and Y are domain variables.
3. X ⊗ Constant or Constant ⊗ X, where constant must be domain compatible.

Well formed formula (WFF) : A well formed formula (WFF) is recursively defined to be one of the following:

• Every atom is a WFF.
• If f is a WFF, so are (f) and ¬f.
• If f and g  are WFF’s,  then so  are  f v  g, f  ∧ g,  f →  g.
• If f(x) is a WFF and X is free and a domain variable, then ∃X(f(x)) and ∀X(f(x)) are also WFF’s.

The major difference between tuple relational calculus and domain relational calculus is that in domain calculus the domain variables are used to represent component of tuples instead of tuples variables used in tuple calculus.

Again the relation Employee and Department shown in Figure 5.19 are used for examples on domain  relational  calculus.

Examples

1. Find all employees having salary  more than

{<E, N, S, D> | <E, N, S, D> ∈ Employee ∧ S > 7000}

2. Name of employees having salary  more than

{<N> | ∃ E, S, D ( <E, N, S, D> ∈ Employee ∧ S > 7000)}

3. Name of employees other than

{<N> | ∃ E, S, D (<E, N, S, D> ∈ Employee ∧ N ≠ “John”)}

4. Name and Department of  employees  who are  working  in marketing

{<N, DN> | ∃ E, S, D ((<E, N, S, D> ∈ Employee ∧ ∀ <DID> ∈ Department)
∧(D= DID ∧ DN = “Marketing”))}

Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)