Industrial Training




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.


    Hi I am Pluto.