# The Domain Relational Calculus

There is another type of relational calculus called the domain relational calculus, or simply, domain calculus.

The Domain Relational Calculus

There is another type of relational calculus called the domain relational calculus, or simply, domain calculus. Historically, while SQL (see Chapters 4 and 5), which was based on tuple relational calculus, was being developed by IBM Research at San Jose, California, another language called QBE (Query-By-Example), which is related to domain calculus, was being developed almost concurrently at the IBM T.J. Watson Research Center in Yorktown Heights, New York. The formal specification of the domain calculus was proposed after the development of the QBE language and system.

Domain calculus differs from tuple calculus in the type of variables used in formu-las: Rather than having variables range over tuples, the variables range over single values from domains of attributes. To form a relation of degree n for a query result, we must have n of these domain variables—one for each attribute. An expression of the domain calculus is of the form

{x1, x2, ..., xn | COND(x1, x2, ..., xn, xn+1, xn+2, ..., xn+m)}

where x1, x2, ..., xn, xn+1, x n+2, ..., xn +m are domain variables that range over domains (of attributes), and COND is a condition or formula of the domain relational calculus.

A formula is made up of atoms. The atoms of a formula are slightly different from those for the tuple calculus and can be one of the following:

An atom of the form R(x1, x2, ..., xj), where R is the name of a relation of degree j and each xi, 1 i j, is a domain variable. This atom states that a list of values of <x1, x2, ..., xj> must be a tuple in the relation whose name is R, where xi is the value of the ith attribute value of the tuple. To make a domain calculus expression more concise, we can drop the commas in a list of vari-ables; thus, we can write:

{x1, x2, ..., xn | R(x1 x2 x3) AND ...} instead of:

{x1, x2, ... , xn | R(x1, x2, x3) AND ...}

An atom of the form xi op xj, where op is one of the comparison operators in the set {=, <, , >, , }, and xi and xj are domain variables.

An atom of the form xi op c or c op xj, where op is one of the comparison operators in the set {=, <, , >, , }, xi and xj are domain variables, and c is a constant value.

As in tuple calculus, atoms evaluate to either TRUE or FALSE for a specific set of val-ues, called the truth values of the atoms. In case 1, if the domain variables are assigned values corresponding to a tuple of the specified relation R, then the atom is TRUE. In cases 2 and 3, if the domain variables are assigned values that satisfy the condition, then the atom is TRUE.

In a similar way to the tuple relational calculus, formulas are made up of atoms, variables, and quantifiers, so we will not repeat the specifications for formulas here. Some examples of queries specified in the domain calculus follow. We will use low-ercase letters l, m, n, ..., x, y, z for domain variables.

Query 0. List the birth date and address of the employee whose name is ‘John B. Smith’.

Q0:                               {u, v | (q) (r) (s) (t) (w) (x) (y) (z) (EMPLOYEE(qrstuvwxyz) AND q=‘John’ AND r=‘B’ AND s=‘Smith’)}

We need ten variables for the EMPLOYEE relation, one to range over each of the domains of attributes of EMPLOYEE in order. Of the ten variables q, r, s, ..., z, only u and v are free, because they appear to the left of the bar and hence should not be bound to a quantifier. We first specify the requested attributes, Bdate and Address, by the free domain variables u for BDATE and v for ADDRESS. Then we specify the con-dition for selecting a tuple following the bar (|)—namely, that the sequence of val-ues assigned to the variables qrstuvwxyz be a tuple of the EMPLOYEE relation and that the values for q (Fname), r (Minit), and s (Lname) be equal to ‘John’, ‘B’, and ‘Smith’, respectively. For convenience, we will quantify only those variables actually appearing in a condition (these would be q, r, and s in Q0) in the rest of our examples.14

An alternative shorthand notation, used in QBE, for writing this query is to assign the constants ‘John’, ‘B’, and ‘Smith’ directly as shown in Q0A. Here, all variables not appearing to the left of the bar are implicitly existentially quantified:15

Q0A:                             {u, v | EMPLOYEE(‘John’,‘B’,‘Smith’,t,u,v,w,x,y,z) }

Query 1. Retrieve the name and address of all employees who work for the ‘Research’ department.

Q1:                               {q, s, v | (z) (l) (m) (EMPLOYEE(qrstuvwxyz) AND

DEPARTMENT(lmno) AND l=‘Research’ AND m=z)}

A condition relating two domain variables that range over attributes from two rela-tions, such as m = z in Q1, is a join condition, whereas a condition that relates a domain variable to a constant, such as l = ‘Research’, is a selection condition.

Query 2. For every project located in ‘Stafford’, list the project number, the controlling department number, and the department manager’s last name, birth date, and address.

Q2:        {i, k, s, u, v | (j)(m)(n)(t)(PROJECT(hijk) AND

EMPLOYEE(qrstuvwxyz) AND DEPARTMENT(lmno) AND k=m AND n=t AND j=‘Stafford’)}

Query 6. List the names of employees who have no dependents.

Q6:        {q, s | (t)(EMPLOYEE(qrstuvwxyz) AND

(NOT(l)(DEPENDENT(lmnop) AND t=l)))}

Q6 can be restated using universal quantifiers instead of the existential quantifiers, as shown in Q6A:

Q6A:     {q, s | (t)(EMPLOYEE(qrstuvwxyz) AND

((l)(NOT(DEPENDENT(lmnop)) OR NOT(t=l))))}

Query 7. List the names of managers who have at least one dependent.

Q7:        {s, q | (t)(j)(l)(EMPLOYEE(qrstuvwxyz) AND DEPARTMENT(hijk)

AND DEPENDENT(lmnop) AND t=j AND l=t)}

As we mentioned earlier, it can be shown that any query that can be expressed in the basic relational algebra can also be expressed in the domain or tuple relational cal-culus. Also, any safe expression in the domain or tuple relational calculus can be expressed in the basic relational algebra.

The QBE language was based on the domain relational calculus, although this was realized later, after the domain calculus was formalized. QBE was one of the first graphical query languages with minimum syntax developed for database systems. It was developed at IBM Research and is available as an IBM commercial product as part of the Query Management Facility (QMF) interface option to DB2. The basic ideas used in QBE have been applied in several other commercial products. Because of its important place in the history of relational languages, we have included an overview of QBE in Appendix C.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Related Topics