Connexions

You are here: Home » Content » Relational Calculus

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
• VOCW

This module is included inLens: Vietnam OpenCourseWare's Lens
By: Vietnam OpenCourseWare

Click the "VOCW" link to see all content affiliated with them.

Recently Viewed

This feature requires Javascript to be enabled.

Relational Calculus

Module by: Nguyen Kim Anh. E-mail the author

Summary: In this lecture, we will discuss another formal languages for the relational model: Relational Calculus. In Relational Calculus, we write a declarative expression to specify a retrieval request

Relational Calculus

In this lecture, we will discuss another formal language for the relational model: Relational Calculus

In Relational Calculus, we write a declarative expression to specify a retrieval request. Relational Calculus expression specifies what data to be retrieved rather than how to retrieve the expected data. Therefore, Relational Calculus is a non-procedural language.

The Relational Calculus comes in two flavors

• Tuple Relational Calculus (TRC) : variables range over tuples of a relation
• Domain Relational Calculus (DRC): variables range over elements of a domain

The concepts used in Relational Calculus include : variables, constants, comparison operations, logical connectivities and quantifiers.

Each query is specified in Relational Calculus as a formula. An answer tuple is an assignment of constants to variables that make formula evaluated to true. The following sections will cover in detail two type of Relational Calculus.

Tuple Relational Calculus

The Tuple Relational Calculus is based on specifying a number of tuple variables which are variables that range over a relation ( theirs values are tuples of the relation).

A formal query in TRC is expressed as {t | P(t)} where t is a tuple variable and P(t) is a expression involving variable t. The result of the query is considered as a set of tuple t so predicate P is true for t.

Example of basic queries in Tuple Relational Calculus

Consider the COMPANY relational database schema (From chapter 3)

EMPLOYEE (SSN, Name, Bdate, Address, Salary, DeptId)

DEPARTMENT(DeptId, Dname, Office, Mng-SSN)

PROJECT(Code, Name, Budget, DeptId)

JOIN(ESSN, PCode, StartDate)

EMP-DEPENDENT(ESSN, Dependent-Name, Bdate, Relationship)

Query 1: Find all employees whose salary is greater than 30.000

{ t t EMPLOYEE t . Salary > 30 . 000 } { t t EMPLOYEE t . Salary > 30 . 000 } size 12{ lbrace "t " \lline " t" in "EMPLOYEE " and " t" "." "Salary ">" 30" "." "000" rbrace } {}

Query 2: Find the name, address of employees who works for department number 1

{ t . Name, t . Address t EMPLOYEE t . DeptId = 1 } { t . Name, t . Address t EMPLOYEE t . DeptId = 1 } size 12{ lbrace t "." "Name, t" "." "Address " \lline " t " in " EMPLOYEE" and t "." "DeptId "=" 1" rbrace } {}

Query 3: Find the name of the department that employee John works for.

{ t . Dname t DEPARTMENT e EMPLOYEE ( e . Name = 'John' e . DeptId = t . DeptId ) } { t . Dname t DEPARTMENT e EMPLOYEE ( e . Name = 'John' e . DeptId = t . DeptId ) } size 12{ lbrace t "." "Dname " \lline " t " in " DEPARTMENT" and exists "e EMPLOYEE" $$" e" "." "Name = 'John' " and " e" "." "DeptId = t" "." "DeptId"$$ rbrace } {}

Query 4: Find the SSN, start date of the employees who works for project number 1 or project number 2

{ t . ESSN, t . StartDate t JOIN ( t . Pcode = 1 t . Pcode = 2 ) } { t . ESSN, t . StartDate t JOIN ( t . Pcode = 1 t . Pcode = 2 ) } size 12{ lbrace t "." "ESSN, t" "." "StartDate " \lline " t" in "JOIN " and $$" t" "." "Pcode "=" 1 " or t "." "Pcode"=2$$ rbrace } {}

Query 5: Find the name, relationship of all the dependents of employees who works for Department Human Resource

{ t . ESSN, t . Dependent-Name, t . Relationship t EMP-DEPENDENT e EMPLOYEE { t . ESSN, t . Dependent-Name, t . Relationship t EMP-DEPENDENT e EMPLOYEE size 12{ lbrace t "." "ESSN, t" "." "Dependent-Name, t" "." "Relationship " \lline " t" in "EMP-DEPENDENT" and exists e in "EMPLOYEE "} {}

( e . SSN = t . ESSN d DEPARTMENT ( d . DeptId = e . DeptId d . Dname ='Human Resource' ) ) } ( e . SSN = t . ESSN d DEPARTMENT ( d . DeptId = e . DeptId d . Dname ='Human Resource' ) ) } size 12{ $$e "." "SSN "=" t" "." "ESSN" and exists d in "DEPARTMENT " \( " d" "." "DeptId = e" "." "DeptId " and " d" "." "Dname ='Human Resource'"$$ \) rbrace } {}

Query 6: Finds the name of the employees who join in every project.

{ t . Name t EMPLOYEE p PROJECT ( e JOIN ( e . ESSN = t . SSN p . Pcode = e . Pcode ) ) } { t . Name t EMPLOYEE p PROJECT ( e JOIN ( e . ESSN = t . SSN p . Pcode = e . Pcode ) ) } size 12{ lbrace t "." "Name " \lline " t" in "EMPLOYEE" and forall "p PROJECT" $$e in "JOIN " \( e "." "ESSN "=" t" "." "SSN" and p "." "Pcode "=" e" "." "Pcode"$$ \) rbrace } {}

Query 7: Finds the names of the employees who have no dependent

{ t . Name t EMPLOYEE ¬ ( d EMP-DEPENDENT ( d . ESSN = t . SSN ) ) } { t . Name t EMPLOYEE ¬ ( d EMP-DEPENDENT ( d . ESSN = t . SSN ) ) } size 12{ lbrace t "." "Name " \lline " t EMPLOYEE " and neg $$exists d in "EMP-DEPENDENT " \( d "." "ESSN "=" t" "." "SSN"$$ \) rbrace } {}

Formal Definition of TRC formulas

As we mentioned above, a TRC expression is of the form {t | P(t) } where P is a formula. Several tuple variables appear in a formula. A variable might be free or bound in a formula. A free tuple variable is one which is not quantified by a size 12{ exists } {} or a size 12{ forall } {}. For example in formula：

t DEPARTMENT e EMPLOYEE ( e . Name = John e . DeptId = t . DeptId ) t DEPARTMENT e EMPLOYEE ( e . Name = John e . DeptId = t . DeptId ) size 12{t in "DEPARTMENT" and exists " e" in "EMPLOYEE" $$e "." "Name "=" John " and e "." "DeptId "=" t" "." "DeptId"} {} the variable t is free and the variable e is bound. A TRC formula is built up out of atomic formula. An atomic formula has one of the following forms: • t rel t rel size 12{t in  ital "rel"} {} where t is a tuple variable, rel is a specified relation • t.a op const: t is a tuple variable, a is an attribute on which t is defined, op is a comparison operator ( < , > , =, ≠, ≥, ≤) , const is a constant in the domain of attribute a • t.a op s.b: s, t are tuple variables ; a is attribute on which t is defined, b is attribute on which s is defined; op is a comparison operator (assume that a, b have the same domain) The general formula is built up from atoms using the following rules • An atomic formula is a formula • If P is a formula , then so are ¬¬ size 12{ neg } {}P and (P) • If P1 and P2 are formulae, then so are P1P2P1P2 size 12{P rSub { size 8{1} } and P rSub { size 8{2} } } {} , P1P2P1P2 size 12{P rSub { size 8{1} } or P rSub { size 8{2} } } {} and P1 size 12{ drarrow } {} P2 • If P(t) is a formula containing a free variable t then tr(P(t))tr(P(t)) size 12{ exists t in r \( P \( t$$ \) } {} and tr(P(t))tr(P(t)) size 12{ forall t in r $$P \( t$$ \) } {} are also formulae.

Equivalent expressions

• P1 P2 ¬ ( ¬ P1 ¬ P2 ) P1 P2 ¬ ( ¬ P1 ¬ P2 ) size 12{P1 and P2 dlrarrow neg $$neg P1 or neg P2$$ } {}
• t r ( P1 ( t ) ) ¬ t r ( ¬ P1 ( t ) ) t r ( P1 ( t ) ) ¬ t r ( ¬ P1 ( t ) ) size 12{ forall t in r $$P1 \( t$$ \) dlrarrow neg exists t in r $$neg P1 \( t$$ \) } {}
• P1 P2 ¬ P1 P2 P1 P2 ¬ P1 P2 size 12{P1 drarrow P2 dlrarrow neg P1 or P2} {}

Safety of the expressions

A TRC expression may generate an infinite relation especially when we use universal quantifiers, existential quantifiers or negation of predicated in the expression. For example, the calculus expression {t¬(tr)}{t¬(tr)} size 12{ lbrace t \lline neg $$t in r$$ rbrace } {} with r is a particular relation is infinite .

Safe expression: An expression {t | P(t) } is safe if all values in the result set of that expression can be extracted from DOM(P).

DOM(P) is domain of the tuple relational formula. The domain of a formula P is the set of all values referenced by P. These include the constant values mentioned in P as well as the values that appear in tuples of relations mentioned in P.

For example:

• DOM(tEMPLOYEEt.Salary>30.000)DOM(tEMPLOYEEt.Salary>30.000) size 12{ ital "DOM" $$t in ital "EMPLOYEE" and t "." ital "Salary">"30" "." "000"$$ } {} is the set containing 1200 as well as all values appear in relation EMPLOYEE.
• DOM(¬(tEMPLOYEE))DOM(¬(tEMPLOYEE)) size 12{ ital "DOM" $$neg \( t in ital "EMPLOYEE"$$ \) } {}is the set of all values appearing in EMPLOYEE relation.

The expression {t¬(tEMPLOYEE)}{t¬(tEMPLOYEE)} size 12{ lbrace t \lline neg $$t in ital "EMPLOYEE"$$ rbrace } {} is unsafe since it is possible to have a tuple that is not in the EMPLOYEE that contains values that do not appear in EMPLOYEE.

Expressive Power of Languages

The Tuple – Relational Calculus is equivalent to relational algebra in term of expressive power. This means for every relational algebra expression, there is an equivalent tuple relational calculus expression and vice versa.

Domain Relational Calculus

The second form of relational calculus called Domain Relational Calculus (DRC). This forms use domain variables that takes values from an attribute’s domain.

A formal query in DRC is expressed as {<x1, x2 , …, xn> | P(x1, x2 , …, xn )} where x1, x2 , …, xn are domain variables and P(x1, x2 , …, xn) is a formula involving those variables.

Formal definition of DRC formula

Similar to the TRC, formula in Domain Relational Calculus is built up from atoms. An atom in the Domain Relational Calculus has one of the following forms:

• < x1 , x2 , . . . , xn > r < x1 , x2 , . . . , xn > r size 12{<x1,x2, "." "." "." , ital "xn"> in `r} {} where r is a relation of n attributes and x1, x2 , …, xn are domain variables or domain constant.
• x op y where x, y are domain variables , op is a comparison operation. Note that x, y have domains that can be compared by op
• x op const where x is a domain variable and const is a constant in domain of attribute for which x is a variable.

The following rules are used to build up the Domain Relational Calculus formula from atoms:

• An atom is a formula
• If P is a formula , then so are ¬¬ size 12{ neg } {}P and (P)
• If P1 and P2 are formulae, then so are P1P2P1P2 size 12{P rSub { size 8{1} } and P rSub { size 8{2} } } {} , P1P2P1P2 size 12{P rSub { size 8{1} } or P rSub { size 8{2} } } {}and P1 size 12{ drarrow } {} P2
• If P(t) is a formula in x where x is a domain variable then size 12{ exists } {}x (P(x)) and size 12{ forall } {}x(P(x)) are also formulae.

Example queries

Query 1: Find all employees whose salary is greater than 30.000

{ < id,n,b,a,s,d > < id,n,b,a,s,d > EMPLOYEE s > 30 . 000 } { < id,n,b,a,s,d > < id,n,b,a,s,d > EMPLOYEE s > 30 . 000 } size 12{ lbrace <"id,n,b,a,s,d"> \lline <"id,n,b,a,s,d"> in "EMPLOYEE " and "s ">" 30" "." "000" rbrace } {}

Query 2: Find the name, address of employees who works for department number 1

{ < n,a > id,b,s,d ( < id,n,b,a,s,d > EMPLOYEE d = 1 ) } { < n,a > id,b,s,d ( < id,n,b,a,s,d > EMPLOYEE d = 1 ) } size 12{ lbrace <"n,a"> \lline " " exists "id,b,s,d " $$<"id,n,b,a,s,d"> in "EMPLOYEE" and "d "=" 1"$$ rbrace } {}

Query 3: Find the name of the department that employee John works for.

{ < dn > di,o,m ( < di,dn,o,m > DEPARTMENT id,n,b,a,s,d ( < id, n, b, a, s, d > EMPLOYEE { < dn > di,o,m ( < di,dn,o,m > DEPARTMENT id,n,b,a,s,d ( < id, n, b, a, s, d > EMPLOYEE size 12{ lbrace <"dn"> \lline exists "di,o,m " $$<"di,dn,o,m"> in ital "DEPARTMENT" and exists "id,n,b,a,s,d " \( <"id, n, b, a, s, d"> in ital "EMPLOYEE"} {} ( n = John d = di ) ) ) } ( n = John d = di ) ) ) } size 12{ and \( " n "=" John " and d=" di"$$ \) \) rbrace } {}

Query 4: Find the SSN, start date of the employees who works for project number P1 or project number P2

{ < en,sd > p ( < en,p,sd > JOIN ( p = 1 p = 2 ) ) } { < en,sd > p ( < en,p,sd > JOIN ( p = 1 p = 2 ) ) } size 12{ lbrace <"en,sd">" " \lline exists "p " $$<"en,p,sd"> in "JOIN" and \( "p "=" 1 " or " p "=2$$ \) rbrace } {}

Query 5: Find the name, relationship of all the dependents of employees who works for Department Human Resource

{ en,name, r bd ( < en,name,bd,r > EMP-DEPENDENT { en,name, r bd ( < en,name,bd,r > EMP-DEPENDENT size 12{ lbrace "en,name, r " \lline exists "bd" $$<"en,name,bd,r"> in "EMP-DEPENDENT" and } {} id,n,b,a,s,d ( < id, n, b, a, s,d > EMPLOYEE id,n,b,a,s,d ( < id, n, b, a, s,d > EMPLOYEE size 12{ exists "id,n,b,a,s,d" \( <"id, n, b, a, s,d"> in "EMPLOYEE" and } {} ( en = id di, dn, o, m ( < di, dn, o, m > DEPARTMENT di = d dn = 'Human Resource' ) ) ) ) } ( en = id di, dn, o, m ( < di, dn, o, m > DEPARTMENT di = d dn = 'Human Resource' ) ) ) ) } size 12{ \( "en "=" id " and exists " di, dn, o, m " \( <"di, dn, o, m "> in "DEPARTMENT" and "di"=d and "dn"="'Human"" Resource"$$ \) \) \) rbrace } {}

Query 6: Finds the name of the employees who join in every project.

{ name id,n,b,a,s,d ( < id, n, b, a, s,d > EMPLOYEE c,pn,b,dept ( < c,pn,b,dept > PROJECT { name id,n,b,a,s,d ( < id, n, b, a, s,d > EMPLOYEE c,pn,b,dept ( < c,pn,b,dept > PROJECT size 12{ lbrace "name " \lline exists "id,n,b,a,s,d" $$<"id, n, b, a, s,d"> in "EMPLOYEE" and forall " c,pn,b,dept " \( <"c,pn,b,dept"> in ital "PROJECT"} {} ( emp, proj, s ( < emp, proj, s > JOIN proj = c emp = id ) ) ) ) } ( emp, proj, s ( < emp, proj, s > JOIN proj = c emp = id ) ) ) ) } size 12{ drarrow \( exists "emp, proj, s " \( <"emp, proj, s "> in "JOIN" and "proj"=c and "emp"="id"$$ \) \) \) rbrace } {}

Query 7: Finds the names of the employees who have no dependent

n { id,n,b,a,s,d ( < id,n, b, a, s,d > EMPLOYEE n { id,n,b,a,s,d ( < id,n, b, a, s,d > EMPLOYEE size 12{ lbrace "n " \lline exists "id,n,b,a,s,d" $$<"id,n, b, a, s,d"> in ital "EMPLOYEE" and } {} ¬ ( en, dn, bd, r ( < en,dn,bd,r > EMP-DEPENDENT id = en ) ) ) } ¬ ( en, dn, bd, r ( < en,dn,bd,r > EMP-DEPENDENT id = en ) ) ) } size 12{ neg \( exists "en, dn, bd, r" \( <"en,dn,bd,r"> in "EMP-DEPENDENT" and "id"="en"$$ \) \) rbrace } {}

Safety of the expression

As we mentioned before, in Tuple Relational Calculus, it is possible to write expressions that may generate infinite relation. The same situation arises for Domain Relational Calculus.

In the Domain Relational Calculus, we must concerned about the formular within “there exists” and “for all”. Consider the expression {x (<x,y>r)z(¬(<x,z>r)P(x,z))}{x (<x,y>r)z(¬(<x,z>r)P(x,z))} size 12{ lbrace "x " \lline exists $$<"x,y"> in r$$ and exists z $$neg \( <"x,z"> in r$$ and P $$x,z$$ \) rbrace } {}. In the second part of this expression z(¬(<x,z>r)P(x,z))z(¬(<x,z>r)P(x,z)) size 12{ exists z $$neg \( <"x,z"> in r$$ and P $$x,z$$ \) rbrace } {} we need to consider values for z that do not appear in r. This set of values actually an infinite set. This case does not appear in the Tuple relational Calculus because in TRC the universal and existential quantifiers are applied on variables that already range over a specific relation ( in the form size 12{ exists } {}t size 12{ in } {} r (P(t)) and size 12{ forall } {}t size 12{ in } {} r (P(t)) ) .

Therefore, in DRC, an expression {<x1, x2 , …, xn> | P(x1, x2 , …, xn )} is safe if all the following hold:

• All values in the result are values from DOM(P)
• For every “there exists” sub formula of the form size 12{ exists } {}x (P1(x)), the sub-formula is true iff there is a value x in DOM(P1) such that P1(x) is true
• For every “for all” sub formula of the form size 12{ forall } {}x(P2(x)), the su-bformula is true iff for all values x from DOM(P2) , P2(x) is true

Expressive Power of Languages

The Domain Relational Calculus restricted to safe expression, is equivalent to relational algebra in term of expressive power.

Content actions

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks