RELATIONAL CALCULUS
Click here for audio-text lecture (for both this unit and the next) and feed it to the speech agent
Click here for an audio lecture that can be played using RealPlayer
Relational calculus is nonprocedural
It has the same expressive power as
relational algebra, i.e. it is
relationally complete
It is a formal language based upon
a branch of mathematical logic called
"predicate calculus"
There are two approaches:
tuple relational calculus and
domain relational calculus
(We will discuss only tuple relational
calculus)
WHY IS RELATIONAL CALCULUS IMPORTANT?
It lays the formal foundation for
many query languages, such as QUEL,
QBE, SQL, etc.
TUPLE RELATIONAL CALCULUS
{ t | COND(t) }
{ t | EMPLOYEE(t) and t.SALARY > 50000 }
The RANGE RELATION is EMPLOYEE
The TUPLE VARIABLE is t
The ATTRIBUTE of a TUPLE VARIABLE is
t.SALARY
(This is similar to SQL's T.SALARY
In relational algebra, we will write
T[SALARY] )
{t.FNAME,t.LNAME | EMPLOYEE(t) and
t.SALARY > 50000 }
is equivalent to
SELECT T.FNAME, T.LNAME
FROM EMPLOYEE T
WHERE T.SALARY > 50000
FORMAL SPECIFICATION OF TUPLE RELATIONAL CALCULUS
{t1.A1, t2.A2, ..., tn.An |
COND(t1,..., tn, .... , tm}
The condition COND is a formula in
relational calculus.
Existential Quantifer E
(E t)(F) is true, if for some tuple t
the formula F is true
Universal Quantifier A
(A t)(F) is true, if for all tuple t
the formula F is true
A variable is BOUND in F, if it
is of the form,
(E t) (F) or (A t) (F)
Otherwise it is FREE in F, for example
d.DNAME = 'Research'
EXAMPLES
Q1: Retrieve the name and address of all
employees who work for 'X' department.
Q1: {t.FNAME, t.LNAME, t.ADDRESS |
EMPLOYEE(t) and
((E d) (DEPARTMENT(d) and
d.DNAME = 'X' and
d.DNUMBER = t.DNO)) }
Note: The only FREE tuple varaibles should
be those appearing to the left of the bar |
Q2: For every project located in 'Y', retrieve
the project number, the controlling department
number, and the last name, birthdate, and
address of the manager of the department.
Q2: {p.PNUMBER, p.DNUM, m.LNAME,
m.BDATE, m.ADDRESS |
PROJECT(p) and EMPLOYEE(m) and
p.PLOCATION = 'Y' and
((E d) (DEPARTMENT(d) and
p.DNUM = d.DNUMBER and
d.MGRSSN = m.SSN)) }
MORE EXAMPLES
Q3: Retrieve the employee's first and last
name and the first and last name of his or
her immediate supervisor.
Q3: {e.FNAME, e.LNAME, s.FNAME, s.LNAME |
EMPLOYEE(e) and
EMPLOYEE(s) and
e.SUPERSSN = S.SSN }
Q4: Make a list of all projects that involve
an employee whose last name is 'Smith' as
a worker or as manager of the controlling
department of the project.
Q4: {p.PNUMBER | PROJECT(p) and
((E e)(E w)(EMPLOYEE(e) and
WORKS_ON(w) and w.PNO=p.PNUMBER
and e.LNAME='Smith' and
e.SSN = w.ESSN))
or
((E m)(E d)(EMPLOYEE(m) and
DEPARTMENT(d) and p.DNUM=d.DNUMBER
and d.MGRSSN=m.SSN and
m.LNAME='Smith')) }
TRANSFORMATION RULES
(A x)(P(x)) = (not E x) (not(P(x))
(E x)(P(x)) = not (A x) (not (P(x))
(A x)(P(x) and Q(x)) = (not E x) (not(P(x)) or not(Q(x)))
(A x)(P(x) or Q(x)) = (not E x) (not(P(x)) and not(Q(x)))
(E x)(P(x) or Q(x)) = (not A x)(not(P(x)) and not(Q(x)))
(E x)(P(x) and Q(x)) = (not A x)(not(P(x)) or not(Q(x)))
(A x)(P(x)) => (E x)(P(x))
(not E x)(P(x)) => not (A x) (P(x))
QUANTIFIERS IN SQL
In SQL, we have the EXISTS function
SELECT
FROM
WHERE EXISTS (SELECT *
FROM R X
WHERE P(X))
SQL does not have universal quantifier.
We can use the transformation to convert
(A x)(P(x)) into (not E x)(not(P(x))
SELECT
FROM
WHERE NOT EXISTS (SELECT *
FROM R X
WHERE NOT P(X))
SAFE EXPRESSIONS
A SAFE EXPRESSION is one that is
guaranteed to yield a finite number
of tuples as its results.
Otherwise, it is called UNSAFE.
{ t | not(EMPLOYEE) }
is UNSAFE!
Technique to guarantee SAFENESS
can be applied to transform a query.
Q6: Find the names of employees
without dependents.
Q6: {e.FNAME, e.LNAME | EMPLOYEE(e)
and (not(E d) (DEPENDENT(d) and
e.SSN = d.ESSN) }
Q6A: {e.FNAME, e.LNAME | EMPLOYEE(e)
((A d)(not(DEPENDENT(d)) or
((E d)(DEPENDENT(d) and
not(e.SSN=d.ESSN))) ) ) }
APPLYING TRANSFORMATION RULES TO MAKE QUERY PROCESSING EFFICIENT
Query: Find the names of employees who work on all
projecs controlled by department number 5.
Q: { e.SSN | EMPLOYEE(e) and F' }
F' = (A x)(not(PROJECT(x)) or F1)
F1 = (E x) (PROJECT(x) and (not(x.DNUM=5) or F2)))
F2 = (E x) (WORKS_ON(w) and
w.ESSN=e.SSN and x.PNUMBER=w.PNO)
Note: A universally quantified tuple variable must
evalue to TRUE for every possible tuple assigned
to it!
Trick: Try to exclude the tuples we are not
interested in, from further consideration.