# 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.