Turn Desktop View Off
You are here:   HomeDatabase SystemRDBMS NotesWhat is Relational Calculus
by Dinesh Thakur Category: RDBMS

We have already seen relational algebra is a procedural language, in which user has to write the steps or procedure to obtain the required results but in general a user should not have to be concerned with the details of how to obtain information. In relational calculus user is not concerned with the procedure to obtain the results, he/she just tell his/her requirements and the output is available without knowing the method about its retrieval.

In relational calculus, a query is expressed as a formula consisting of a number of variables and an expression involving these variables. It is up to the DBMS to transform these nonprocedural queries into equivalent, efficient, procedural queries. The concept of relational calculus was first proposed by Codd. The relational calculus is used to measure the selective power of relational languages. A language that can be used to produce any relation that can be derived using the relational calculus is said to be relationally complete.

Relation calculus, which in effect means calculating with relations, is based on predicate calculus, which is calculating with predicates. It is a formal language used to symbolize logical arguments in mathematics. Propositions specifying a property consist of an expression that names an individual object, and another expression, called the predicate, that stands for the property that the individual object possesses. If for instance, p and q are propositions, we can build other propositions "not p", "p or q", "p and q" and so on. In predicate calculus, propositions may be built not only out of other propositions but also out of elements that are not themselves propositions. In this manner we can build a proposition that specifies a certain property or characteristic of an object.

Example

Consider these statements:

B.Tech. is a class.

Ajay is a student.

Anil is an analyst.

Ram is an analyst.

India is a country.

USA is a country.

Each of these is a statement about an object having a certain feature or property. In these examples, the parts "is a class", "is an analyst", and "is a country" are instances of predicates. Each describes some property or characteristic of an object.




A convenient method of writing the statements of above example is to place the predicate first and follow it with the object enclosed in parentheses. Therefore, the statement B.Tech is a class" can be written as "is a class(B.Tech.). Now we drop the "is a" part and write the first statement as "class(B.Tech.)." Finally if we use symbols for both the predicate and the object, we can rewrite the statements of above example as P(x). The lowercase letters from the end of the alphabet ( x,y,z) denote variables, the beginning letters (a,b,c ) denote constants, and uppercase letters denote predicates. P(x), where x is the argument is a one-place predicate. DBMS(x) and COMPANY(y) are examples of one-place predicates. The variable x and yare replaceable by constants such as DBMS (Oracle).

The use of constants and variables is similar to that in some high-level languages. A constant specifies a particular value or object; a variable is used as a placeholder for the values in an expression or procedure.

Example 2

Consider these statements:

Naresh is taller than Rajesh.

WXY is bigger than BCD.

Canada is north of the USA.

In these statements, the predicates "is taller than", "is bigger than", "is north of' require two objects and are called two-place predicates.

In general, we have predicates of degree n, where the predicate takes n arguments. In the case of BIGGER_THAN (WXY, BCD), the predicate BIGGER_THAN specifies the relation between WXY and BCD.




Atomic Formula: A predicate followed by its arguments is called an atomic formula. Examples of these are DBMS(x), COMPANY(y) and BIGGER_THAN (WXY; BCD). A language consists of symbols. We can also specify logical connectors such as "not" or negation, denoted by l,"or"(V), “and"(A), and "implication" (-). Atomic formulas may be combined using the logical connectors to generate formulas such as P(X) A Q(y), P(x) V Q(y) and so on. DBMS (ISS) A COMPANY (BCD), for instance can represent "ISS is a DBMS and BCD is a company." Other interesting formulas are formed with the use of quantifiers: universal or "for all," denoted by V and existential or "for some", denoted by 3. "x is a DBMS" is n example of a formula. If the symbol x in the formula is replaced by the name of a DBMS, e have a declarative sentence that is either true or false. The phrase "s is a DBMS produced y company y" is a formula with two variables. If the occurrences of the variables x and y re replaced by the appropriate specific objects, the result is again a declarative sentence that s either true or false. For example, the declarative sentence" ISS is a DBMS produced by BC" is false. The sentence "ISS is a DBMS produced by BCD" is true. The fundamental aspect of calculus is the "Range Variables".

Relational Calculus can be classified in two categories:

• Tuple Oriented relational Calculus

• Domain Oriented relational calculus

In relational tuple calculus, the variables represent the tuples from specified relations; in relational domain calculus, the variables represent values drawn from specified domains.

Tuple Oriented Relational Calculus

The tuple relational calculus is based on specifying a number of tuple variables. Each such tuple variable normally ranges over a particular database relation. This means that the variable may take any individual tuple from that relation as its value. A simple tuple relational calculus query is of the form { t I COND(t)·}, where '1' is a tuple variable and COND(t) is a conditional expression involving '1'. The result of such a query is a relation that contains all the tuples (rows) that satisfy COND(t).

For example, the relational calculus query {t I BOOK(t) and t.PRICE>lOO} will get you all the books whose price is greater than 100. In the above example, the condition 'BOOK(t)' specifies that the range relation of the tuple variable '1' is BOOK. Each BOOK tuple 't' that satisfies the condition 't.PRICE> 100' will be retrieved. Note that 't.PRICE' references the attribute PRICE of the tuple variable '1'.

The query {t IBOOK (t) and t.PRICE>100} retrieves all attribute values for each selected

BOOK tuple. To retrieve only some of the attributes (say TITLE, AUTHOR and PRICE) we can modify the query as follows:

{t.TITLE, t.AUTHOR, t.PRICE I BOOK(t) and t.PRICE>200}

Thus, in a tuple calculus expression we need to specify the following information:

For each tuple variable the range relation 'R' of 'to This value is specified by a condition of the form R(t) .

• A condition to select the required tuples from the relation.

• A set of attributes to be retrieved. This set is called the requested attributes. The values of these attributes for each selected combination of tuples. If the requested attribute list is not specified, then all the attributes of the selected tuples are retrieved.

Thus, to retrieve the details of all books (Title and Author name) which were published by 'Kalyani' and whose price is greater than 100 we will write the query as follows:

{t.TITLE, t.AUTHOR I BOOK (t) and t.PUBLISHER='xyz' and t.PRICE>100}

 

Expressions and Formulas

A general expression of the.tuple relational calculus is of the following form:

{tl·Aj,t2·A2, tn·An, I COND(tl,t2· .. tn, tn+j,1n+2.... tn+m)}

Where tj,t2 1n,1n+j,1n+2 1n+mare tuple variables, each Ai is an attribute of the relation on which ranges and COND is a condition or formula of the tuple relational calculus.

A formula is defined as follows:

Every condition is a WFF (Well Formed Formula). Here, a well-formed formula is constructed from conditions, Boolean operations (AND, OR, NOT) and quantifiers like for all values (V) or there exists (3).

There are following rules which are applicable on WFF:

• Every condition is WFF.

• If F is a WFF the (F) and NOT(F) are also WFF.

• If Fj and F2 are WFFs, then (Fj AND F2), (Fj OR F2) are also WFFs .

• If F is a WFF in which T occurs as a free variable (free variables are those range

variables when, the meaning of the formula changed if all the occurrences of range

variable say 'x' were replaced by some other variables say 'y') then 3 T(t) and

V T(F) are WFFs .

• Nothing else is WFF.

Bound variables: Bound variables are those range variables when the meaning of the formula would remain unchanged if all the occurrence of range variable say 'x' were replaced by some other variable say 'y'. Then range variable 'x' is called as the Bound variable.

For example: x (x>3) means

EXISTS x (x>3)

Here, WFF simply states that there exists some integer x that is greater than 3. Note, that the meaning of this WFF would remain totally unchanged if all references of x were replaced by references to some other variable y. In other words the WFF EXISTS y(y>3) is semantically same.

Free Variables: Free variables are those range variables when the meaning of the formula changed, if all the occurrences of range variable say 'x' were replaced by some other variables say 'y'. Then range variable 'x' is called as the Free variable.

For example: x (x>3) and x<O means

EXISTS x (x>3) and x <0

Here, there are three references to x, denoting two different variables. The first two references are bound and could be replaced by references to some other variable y without changing the overall meaning. The third reference is free, and cannot be replaced without changing the meaning of the formula. Thus, of the two WFFs shown below, the first is equivalent to the one just given and the second is not: -

EXIST Y (y>3) and x<O

EXITS y (y>3) and y<O

Closed and Open WFF: A WFF in which all variables references are bound is called Closed WFF. e.g. EXISTS x (x>3) is a closed WFF.

An open WFF is a WFF that is not closed i.e. one that consists of at least one free variable reference. e.g. EXISTS y (y>3) and x<O

 

Examples of Pure Tuple Calculus

Consider following database:

EMP( empno, ename, job, mgr, hiredate, sal, comm, deptno)

DEPT ( deptno, dname, loc)

.

• Get the name and salary of all employees working for the 'Accounting' department.

{e.ENAME, e.SAL I EMP(e) and (3d)

(DEPT(d) and d.DNAME=='Accounting' and d.DEPTNO==e.DEPTNO)}

•. Get the name, department name of all employees whose pay is greater than 10000.

{e.ENAME, d.DNAME I EMP (e) and DEPT (d) and (3e

(e.DEPTNO=d.DEPTNO and e.SAL>lOOOO)}

• Get the name of all departments who have no employee.

{d.DNAME I DEPT(d) and (not(3e) EMP(e) and e.DEPTNO=d.DEPTNO)}

• Get the name of all departments who have at least one employee.

{e.NAME I EMP(c) and (3d)

(DEPT(d) and e.DEPTNO=d.DEPTNO)}

Examples in QUEL (based on Tuple Calculus)

Consider again the same database:

EMP( empno, ename, job, mgr, hiredate, sal, cornm, deptno)

DEPT ( deptno, dname, loc )

Definitions of tuples used in examples:

Range of EX is EMP

Range of DX is DEPT

• Get employee number in relation EMP.

EX.empno

• Get employee number for job 'Clerk'.

EXempno where EX.job='Clerk'

• Get Employee names that belong to deptno 10 and having salary >2000.

(EXename) where EXdeptno=lO and EXsal>2000

• Get Employee number and name who are working in "Accounting" department.

(EXempno, EXename ) where

EXISTS DX (EXdepno=DXdeptno and DXdname="Accounting"

 

Updation in QUEL

• Change the Name of employee Ajay to Rakesh.

Replace EX (ename = 'Ajay') where EXename = 'Rakesh'

• Increase the salary by 100 of all employed in "Sales" department.

Replace EX (sal = sal+100) where EX .deptno=DXdeptno and

DXdname= 'Sales'

Insertion in QUEL

• Add employee 2000 (Name='Raja', Job ='Clerk').

APPEND TO EMP( empno= 2000, ename= 'Raja', Job ='Clerk')

Deletion in QUEL

• Delete all records of Clerks.

   DELETE EX where EX.job= 'Clerk'

 

Domain Oriented Relational Calculus




The domain calculus differs from the tuple calculus in the type of variables used in formulas. In domain calculus the variables range over single values from domains of attributes rather than ranging over tuples. To form a relation of degree 'n' for a query result, we must have 'n' of these domain variables-one for each attribute.

An expression of the domain calculus is of the following form:

{Xl, X2, ... , Xn I COND(XI, X2, .. ·, Xn, Xn+b Xn+2, , Xn+m)}

In the above expression Xl, X2, ... , Xn, Xn+b Xn+2, , Xn+m are domain variables that range over domains of attributes and COND is a condition or formula of the domain relational calculus.

Expression of the domain calculus are constructed from the following elements:

• Domain variables Xl, X2, ... , Xn, Xn+b Xn+2, ... , Xn+m each domain variable is to range over some specified domain .

• Conditions, which can take two forms:

• Simple comparisons of the form x * y, as for the tuple calculus, except that x and yare now domain variables.

• Membership conditions, of the form R (term,

term ...).

Here, R is a relation, and each "term" is a pair AV, where A in turn is an attribute

Of R and V is either a domain variable or a constant. For example EMP (empno: 100, ename: 'Ajay') is a membership condition (which evaluates to true if and only if there exists an EMP tuple having empno=100 and ename = 'Ajay') .

• Well Formed Formulates (WFFs), formed in accordance with rules of tuple calculus (but with the revised definition of "condition").

 

Free and Bound Variables

The rules concerning free and bound variables given for the tuple calculus are also applicable similarly on the domain calculus.

Examples

Consider again the following database:

EMP (empno, ename, job, mgr, hiredate, sal, comm, deptno)

DEPT ( deptno, dname, loc)

• Get employee number in relation EMP.

EX where EMP( empno:EX)

• Get employee number for job 'Clerk'.

EX where EMP( empno:EX, job='Clerk')

• Get Sno and Cities for supplier who supply part P2.

SX, CityX where S (Sno: SX, City = CityX) and SP (Sno: SX, Pno = P2)

• Get Employee names that belong deptno 10 and having salary >2000.

EX where EMP (ename: EX, deptno: 10, sal>2000)

• Get Employee number and name who are working in "Accounting" department.

EX, NX where EMP (empno:EX, ename :NX, deptno:DX) and

DEPT( deptno:DX, dnarne :'Accounting')

If you liked this article, you can also catch us on facebook and Google+

Related Articles (You May Also Like)






Subscribe To Free Daily Newsletter!

Get Free News Updates Delivered Directly To Your Inbox
About Dinesh Thakur

Dinesh ThakurDinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to contact us.



What's New and Popular





Search Content







Advance Courses



Basic Courses



Advertise with Us