Relational Calculus For BE And MCA

Relational Calculus is a query system wherein queries are expressed as formulas consisting of a number of variables and an expression involving these variables.

It differs from the relational algebra in that relational calculus is non-procedural; which means queries which are expressed as formulas describe properties of the required result relation without specifying the method of evaluating it.

Relational algebra requires a sequence of operations to specify a retrieval request. Relational algebra allows nesting algebra operations to form a single expression with the requirement to follow certain order to be explicitly specified in the relational algebra expression. This order influences the strategy for evaluating the query. However a relational calculus expression may be written in different ways, but the way does not affect how the query should be evaluated.

Relational Calculus is of two types –

  • Tuple Relational Calculus
  • Domain Relational Calculus

Tuple Relational Calculus –

Tuples are found for which a predicate is true. This calculus is based on the use of tuple variable that ranges over a named relation, which means that a variable whose only permitted values are the tuples of the relation. A generalized expression of a query in the tuple relational calculus –

{t | COND(t)}

Where a query is assumed to be a set of all tuples t such that predicate (condition) COND(t) is true for t.

COND is also called well-formed formula (WFF) in mathematical logic.

Example –

List all the employees whose salary exceeds 1500 from emp table (relation).

Tuple calculus expression for the above query –

{t | EMP(t) ⋀ t.sal > 1500}

Explanation –

  • The condition EMP(t) specifies that the range relation of tuple variable t is EMP.
  • Each EMP tuple t that satisfies the condition t.sal > 1500 will be retrieved.

t.sal may also be written as t[sal].

In this example all the attributes (entire row) of each selected EMP tuple t is returned. If we do not want all the attributes but only ename, job and sal, then we may write –

{t.ename, t.job, t.sal | EMP(t) ∧ t[sal] > 1500}

In general a tuple calculus expression may consists of following 3 things specified in it –

  • Range relation R of t, specified as condition R(t) for each tuple variable t.
  • Condition(s) to select particular combinations of tuples.
  • Requested attributes i.e. set of attributes to be retrieved.

The COND (i.e. well-formed formula WFF) is made of predicate calculus atoms. It may be one or combination of following –

  1. An atom of the form R(ti) – this atom identifies the range of the tuple variable ti as the relation with name R.
  2. An atom of the form ti.A op tj.B – where A and B are the attributes respectively on which ti and tj ranges and op is standard comparison operator.
  3. An atom of the form ti.A op c or c op tj.B – where c is a constant value.

Every atom evaluates to truth value (either TRUE or FALSE). A formula may have one or more atoms connected by logical operators like AND, OR and NOT.

Bound & Free tuple variable –

A tuple variable t is bound if it is quantified, which means that it appears in an (∃t) or (∀t) clause; otherwise it is free.

∃ is called as existential quantifier and ∀ is called as universal quantifier. They are used in following way –

t r (Q(t)) (meaning there exists a tuple t in relation r such that predicate Q(t) is true).

tr (Q(t)) (meaning Q is true for all tuples t in relation r).

Example –

Query – List the names of employees and their salary working in the research department.

{t.ename, t.sal | EMP(t) ∧ ((∃d) DEPT(d) ∧ d.dname = ‘RESEARCH’ ∧ d.deptno = t.deptno)}

Observe that only free tuple variables in a relational calculus expression should be those that appear on the left of the bar (|).

There may be two or more tuple variables in a tuple calculus expression that may range over the same relation.

Query – List the names of employees along with the names of their managers.

{t.ename, d.ename | EMP(t) ∧ EMP(d) ∧ t.mgr = d.empno}

Domain Relational Calculus –

Domain relational calculus differs from tuple relational calculus in the variables range over single values from domains of attributes rather than having variables range over tuples. We must have one domain variable for each attribute of a relation.

An expression in the domain relational calculus is of the form –

{<x1, x2, …, xn> | P (x1, x2, …, xn)} (where x1, x2, …, xn represent domain variables and P represents a formula composed of atoms.

An atom in the domain relational calculus has one of the following forms –

  • < x1, x2, …, xn> ∈ r, where r is a relation on n attributes and x1, x2, …, xn are domain variables or domain constants.
  • x op y where x and y are domain variables and op is a comparison operator.
  • x op c where c is a constant in the domain of the attribute for which x is domain variable.

Example – EMP (id, ename, job, sal, deptno), DEPT(deptno, dname, location)

Query – select ename, job, sal from emp where > 1500;

{<b, c, d> |∃a, e <a,b,c,d,e> ∈ emp d > 1500}

Observe that b, c and d domain variable representing ename, job and sal attributes respectively have not be quantified (i.e. free) as they are on the left hand side of the bar (|) to be projected. Variables a and e are quantified by ∃ ( i.e. bound) because domains these variables represent must range over the relation emp. (∃a, e is short hand for (∃a) (∃b) )

Query – select ename, dname from emp e, dept d where e.deptno = d.deptno

{<b, n> | ∃a, c, d, e, m, o (<a, b, c, d, e> ∈ emp ∧ <m,n,o> ∈ depto = m)}

Use of Universal Quantifier (∀) –

It is possible to express most relational expressions using existential (∃) quantifier, but expressions which use “for all” clause may be more conveniently written with Universal Quantifier (∀).

Consider following relations for use –

Emp(name, ssn, address, salary, mgr_ssn, dno)

Works_on(essn, pno, hours)

Project(pname,pnumber,dnum)

Query – list names, address and salary of the employees working on all the projects controlled by department number 5.

SQL – select name, address, salary from emp Where ssn in (select essn from works_on Where pno = all (select pnumber from project Where dnum = 5);

using existential (∃) quantifier –

tuple relational calculus expression – {e.name, e.address, e.salary | EMP(e) ∧ (NOT (∃x) PROJECT(x)∧ (x.dnum=5) ∧ (NOT (∃w) (works_on(w) ∧ w.essn=e.ssn ∧ x.pnumber=w.pno))))}

using Universal Quantifier (∀) –

tuple relational calculus expression –

{e.ename, e.address, e.salary | EMP(e) ∧ ((∀x)(NOT(PROJECT(x))∨NOT (x.dnum=5) ∨ ((∃w) (works_on(w) ∧ w.essn=e.ssn∧x.pnumber=w.pno))))}

Explanation : In using the universal quantifier, the inner formula must be true for all the tuples in the universe. So we must exclude all such tuples from consideration which we are not interested in. Breaking the expression in its individual components (atoms) it may be explained as –

  • e.ename, e.address, e.salary | EMP(e) F’  - selecting ename, address, salary from free tuple

variable with application formula F’

  • F’ = (x)(NOT(PROJECT(x) F1)) – Exclude all such rows which do not belong to the relation project or satisfying formula F1.
  • F1NOT (x.dnum=5) F2 Exclude all such rows which may belong to relation PROJECT but do not belong to department number 5. (i.e. up to this stage we have only those rows of PROJECT relation which are from department number 5)
  • F2 = ((w) (works_on(w) w.essn=e.ssn x.pnumber=w.pno)) – Gives the condition for finally selecting tuples from EMP where we are first matching project numbers from left over rows from project that with rows in works_on to get employee essn and matching this ssn in EMPLOYEE relation to fetch ename, address and salary.

 

Relational Calculus is a query system wherein queries are expressed as formulas consisting of a number of variables and an expression involving these variables.

It differs from the relational algebra in that relational calculus is non-procedural; which means queries which are expressed as formulas describe properties of the required result relation without specifying the method of evaluating it.

Relational algebra requires a sequence of operations to specify a retrieval request. Relational algebra allows nesting algebra operations to form a single expression with the requirement to follow certain order to be explicitly specified in the relational algebra expression. This order influences the strategy for evaluating the query. However a relational calculus expression may be written in different ways, but the way does not affect how the query should be evaluated.

Relational Calculus is of two types –

·         Tuple Relational Calculus

·         Domain Relational Calculus

Tuple Relational Calculus –

Tuples are found for which a predicate is true. This calculus is based on the use of tuple variable that ranges over a named relation, which means that a variable whose only permitted values are the tuples of the relation. A generalized expression of a query in the tuple relational calculus –

{t | COND(t)}

Where a query is assumed to be a set of all tuples t such that predicate (condition) COND(t) is true for t.

COND is also called well-formed formula (WFF) in mathematical logic.

Example –

List all the employees whose salary exceeds 1500 from emp table (relation).

Tuple calculus expression for the above query –

{t | EMP(t) t.sal > 1500}

Explanation –

·         The condition EMP(t) specifies that the range relation of tuple variable t is EMP.

·         Each EMP tuple t that satisfies the condition t.sal > 1500 will be retrieved.

t.sal may also be written as t[sal].

In this example all the attributes (entire row) of each selected EMP tuple t is returned. If we do not want all the attributes but only ename, job and sal, then we may write –

{t.ename, t.job, t.sal | EMP(t) t[sal] > 1500}

In general a tuple calculus expression may consists of following 3 things specified in it –

·         Range relation R of t, specified as condition R(t) for each tuple variable t.

·         Condition(s) to select particular combinations of tuples.

·         Requested attributes i.e. set of attributes to be retrieved.

The COND (i.e. well-formed formula WFF) is made of predicate calculus atoms. It may be one or combination of following –

1.       An atom of the form R(ti) – this atom identifies the range of the tuple variable ti as the relation with name R.

2.       An atom of the form ti.A op tj.B – where A and B are the attributes respectively on which ti and tj ranges and op is standard comparison operator.

3.       An atom of the form ti.A op c or c op tj.B – where c is a constant value.

Every atom evaluates to truth value (either TRUE or FALSE). A formula may have one or more atoms connected by logical operators like AND, OR and NOT.

Bound & Free tuple variable –

A tuple variable t is bound if it is quantified, which means that it appears in an (t) or (t) clause; otherwise it is free.

is called as existential quantifier and is called as universal quantifier. They are used in following way –

t r (Q(t)) (meaning there exists a tuple t in relation r such that predicate Q(t) is true).

t r (Q(t)) (meaning Q is true for all tuples t in relation r).

Example –

Query – List the names of employees and their salary working in the research department.

{t.ename, t.sal | EMP(t) ((d) DEPT(d) d.dname = ‘RESEARCH’ d.deptno = t.deptno)}

Observe that only free tuple variables in a relational calculus expression should be those that appear on the left of the bar (|).

There may be two or more tuple variables in a tuple calculus expression that may range over the same relation.

Query – List the names of employees along with the names of their managers.

{t.ename, d.ename | EMP(t) EMP(d) t.mgr = d.empno}

Domain Relational Calculus –

Domain relational calculus differs from tuple relational calculus in the variables range over single values from domains of attributes rather than having variables range over tuples. We must have one domain variable for each attribute of a relation.

An expression in the domain relational calculus is of the form –

{<x1, x2, …, xn> | P (x1, x2, …, xn)} (where x1, x2, …, xn represent domain variables and P represents a formula composed of atoms.

An atom in the domain relational calculus has one of the following forms –

·         < x1, x2, …, xn> r, where r is a relation on n attributes and x1, x2, …, xn are domain variables or domain constants.

·         x op y where x and y are domain variables and op is a comparison operator.

·         x op c where c is a constant in the domain of the attribute for which x is domain variable.

Example – EMP (id, ename, job, sal, deptno), DEPT(deptno, dname, location)

Query – select ename, job, sal from emp where > 1500;

{<b, c, d> |∃a, e <a,b,c,d,e> emp d > 1500}

Observe that b, c and d domain variable representing ename, job and sal attributes respectively have not be quantified (i.e. free) as they are on the left hand side of the bar (|) to be projected. Variables a and e are quantified by ( i.e. bound) because domains these variables represent must range over the relation emp. (a, e is short hand for (∃a) (b) )

Query – select ename, dname from emp e, dept d where e.deptno = d.deptno

{<b, n> | ∃a, c, d, e, m, o (<a, b, c, d, e> ∈ emp <m,n,o> dept o = m)}

Use of Universal Quantifier () –

It is possible to express most relational expressions using existential () quantifier, but expressions which use “for all” clause may be more conveniently written with Universal Quantifier ().

Consider following relations for use –

Emp(name, ssn, address, salary, mgr_ssn, dno)

Works_on(essn, pno, hours)

Project(pname,pnumber,dnum)

Query – list names, address and salary of the employees working on all the projects controlled by department number 5.

SQL – select name, address, salary from emp

           Where ssn in (select essn from works_on

                                     Where pno = all (select pnumber from project

                                                                    Where dnum = 5);

using existential () quantifier –

tuple relational calculus expression – {e.name, e.address, e.salary | EMP(e) (NOT (x) PROJECT(x)

                                                                     (x.dnum=5) (NOT (w) (works_on(w) w.essn=e.ssn

                                                                    x.pnumber=w.pno))))}

using Universal Quantifier () –

tuple relational calculus expression – {e.ename, e.address, e.salary | EMP(e) ((x)(NOT(PROJECT(x))

                                                                    NOT (x.dnum=5) ((w) (works_on(w) w.essn=e.ssn

                                                                      x.pnumber=w.pno))))}

Explanation : In using the universal quantifier, the inner formula must be true for all the tuples in the universe. So we must exclude all such tuples from consideration which we are not interested in. Breaking the expression in its individual components (atoms) it may be explained as –

·         e.ename, e.address, e.salary | EMP(e) F’ - selecting ename, address, salary from free tuple

variable with application formula F’

·         F’ = (x)(NOT(PROJECT(x) F1)) – Exclude all such rows which do not belong to the relation project or satisfying formula F1.

·         F1 =  NOT (x.dnum=5) F2 Exclude all such rows which may belong to relation PROJECT but do not belong to department number 5. (i.e. up to this stage we have only those rows of PROJECT relation which are from department number 5)

·         F2 = ((w) (works_on(w) w.essn=e.ssn x.pnumber=w.pno)) – Gives the condition for finally selecting tuples from EMP where we are first matching project numbers from left over rows from project that with rows in works_on to get employee essn and matching this ssn in EMPLOYEE relation to fetch ename, address and salary.