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.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.