Relational Calculus

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.

Enroll now!

Theoretical Paper

Practical Paper

Industrial Training