Tuple Relational Calculus ( TRC )

Introduction

Procedural Query language

§ query specification involves giving a step by step process of
obtaining the query result
e.g., relational algebra
§ usage calls for detailed knowledge of the operators involved
§ difficult for the use of non-experts

Declarative Query language

§ query specification involves giving the logical conditions the
results are required to satisfy
§ easy for the use of non-experts

Prof P Sreenivasa Kumar, 1

Department of CS&E, IITM.

Predicates
We have studied “Predicate Logic” in Discrete Maths course

What is a “predicate”?
A predicate is an expression with place-holders (aka variables)
– it takes a Boolean value when values are substituted for variables
lessThan(x,y) – lessThan(2,5) is true; lessThan(5,1) is false

livesIn(p,c) – livesIn(SindhuPV, Hyderabad) – true

– livesIn(PriyankaVadra, Hyderabad) – false

One can have n-place predicates also…

Prof P Sreenivasa Kumar, 2

Department of CS&E, IITM.

Relations and Predicates

Can we interpret
“relation names” of a relational model as predicates??
Recall: DB Relation – finite set of tuples
Tuple – sequence of values;
each value corresponds to an attribute
and comes from a domain of atomic values
Each DB relation name with n attributes
– can be thought of as an n-place predicate
We make Closed-World Assumption (CWA) where...
– tuples in the relation instance make the predicate true
– those not present in the instance make it false
Prof P Sreenivasa Kumar, 3
Department of CS&E, IITM.

1
 TRC – a declarative query language
Tuple variable – associated with a relation
(called the range relation)
• takes tuples as its values
• t : tuple variable over relation r with scheme R(A,B,C )
t.A stands for value of column/attribute A in t etc

TRC Query – basic form:

{ t1.Ai1, t2.Ai2,…tm.Aim | θ }

predicate calculus/logic expression

involving tuple variables
t1, t2,…, tm, tm+1,…,ts
- specifies the condition to be satisfied

Prof P Sreenivasa Kumar, 4

Department of CS&E, IITM.

An example TRC query

student (rollNo, name, degree, year, sex, deptNo, advisor )
department (deptId, name, hod, phone )

Obtain the rollNo, name of all girl students

in the Maths Dept(deptId = 2)
{s.rollNo,s.name| student(s)^ s.sex=‘F’^ s.deptNo=2}

attributes
This predicate is true whenever
required in
value of s is a tuple from the
the result
Student instance, false otherwise
In general, if t is a tuple variable with range
relation r, r(t) is taken as a predicate which
is true if and only if the value of t is a tuple in r
Prof P Sreenivasa Kumar, 5
Department of CS&E, IITM.

General form of the condition in TRC queries

Atomic expressions are the following:
1. r ( t ) -- true if t is a tuple in the relation instance r
2. t1.Ai <compOp> t2 .Aj compOp is one of {<, ≤ , >, ≥, =, ≠ }
3. t.Ai <compOp> c c is a constant of appropriate type

Composite expressions:
1. Any atomic expression
2. F1 ∧ F2 ,, F1 ∨ F2 , ¬ F1 where F1 and F2 are expressions
3. (∀t) (F), (∃t) (F) where F is an expression
and t is a tuple variable

Free Tuple Variable – a variable that is not quantified

Bound Tuple Variable – a quantified variable

Prof P Sreenivasa Kumar, 6

Department of CS&E, IITM.

2
Interpretation of the query in TRC
All possible tuple assignments to the free variables in the query are
considered.

For any specific assignment,

if the expression to the right of the vertical bar evaluates to true,
that combination of tuple values
would be used to produce a tuple in the result relation.

While producing the result tuple, the values of the attributes for the
corresponding tuple variables as specified on the left side of the
vertical bar would be used.

Note: The only free variables are the ones that appear to the left
of the vertical bar
Prof P Sreenivasa Kumar, 7
Department of CS&E, IITM.

Example TRC queries

Obtain the rollNo, name of all girl students in the
Maths Dept

{s.rollNo, s.name | student(s) ^ s.sex=‘F’ ^

(∃ d)(department(d) ^ d.name=‘Maths’
^ d.deptId = s.deptNo)}

s: free tuple variable d: existentially bound tuple variable

Existentially or universally quantified tuple variables can be used

on the RHS of the vertical bar to specify query conditions

Attributes of free (or unbound ) tuple variables can be used on LHS

of vertical bar to specify attributes required in the results

Prof P Sreenivasa Kumar, 8

Department of CS&E, IITM.

Example Relational Scheme

student (rollNo, name, degree, year, sex, deptNo, advisor)

department (deptId, name, hod, phone)

professor (empId, name, sex, startYear, deptNo, phone)

course (courseId, cname, credits, deptNo)

Q2
enrollment (rollNo, courseId, sem, year, grade) Q3
Q4
teaching (empId, courseId, sem, year, classRoom)
Q5

preRequisite (preReqCourse, courseID)

Prof P Sreenivasa Kumar, 9

Department of CS&E, IITM.

3
Example queries in TRC (1/5)

1)Determine the departments that do not have

any girl students

student (rollNo, name, degree, year, sex, deptNo, advisor)

department (deptId, name, hod, phone)

{d.name|department(d) ^
¬(∃ s)(student(s) ^
s.sex =‘F’ ^ s.deptNo = d.deptId)

Prof P Sreenivasa Kumar, 10

Department of CS&E, IITM.

Examples queries in TRC (2/5) Schema

2)Obtain the names of courses enrolled by student
named Mahesh

{c.name | course(c) ^
(∃s) (∃e) ( student(s) ^ enrollment(e)
^ s.name = “Mahesh”
^ s.rollNo = e.rollNo
^ c.courseId = e.courseId }

Prof P Sreenivasa Kumar, 11

Department of CS&E, IITM.

Examples queries in TRC (3/5) Schema

3)Get the names of students who have scored ‘S’ in all
subjects they have enrolled. Assume that every
student is enrolled in at least one course.
{s.name | student(s) ^
(∀e)(( enrollment(e) ^
e.rollNo = s.rollNo) → e.grade =‘S’)}

Person P with all S grades:

for enrollment tuples not having her roll number, LHS (of →) is false
for enrollment tuples having her roll number, LHS is true, RHS is also true
So the implication is true for all e tuples

Person Q with some non-S grades:

for enrollment tuples not having her roll number, LHS is false
for enrollment tuples having her roll number, LHS is true, but RHS is false for
at least one tuple.
So the implication is not true for at least one tuple.
Prof P Sreenivasa Kumar, 12
Department of CS&E, IITM.

4
 Examples queries in TRC (4/5) Schema

4) Get the names of students who have taken at least

one course taught by their advisor

{s.name | student(s) ^
(∃e)(∃t)(enrollment(e) ^ teaching(t) ^
e.courseId = t.courseId ^
e.rollNo = s.rollNo ^
t.empId = s.advisor}

5) Display the departments whose HODs are teaching

at least one course in the current semester

{d.name | department(d) ^(∃t)(teaching(t) ^

t.empid = d.hod
^ t.sem = ‘odd’ ^ t.year = ‘2019’)}

Prof P Sreenivasa Kumar, 13

Department of CS&E, IITM.

Examples queries in TRC (5/5) Schema

6)Determine the students who are enrolled for every

course taught by Prof Ramanujam. Assume that Prof
Ramanujam teaches at least one course.

1. {s.rollNo | student (s) ^

2. (∀c)(course (c) ^
3. ((∃t),(∃p)( teaching(t) ^ professor(p) ^
4. t.courseId = c.courseId ^
5. p.name = “Ramanujam” ^
6. p.empId = t.empId )) →
7. (∃e) (enrollment(e) ^
8. e.courseId = c.courseId ^
9. e.rollNo = s.rollNo)
10. )
11. }

Prof P Sreenivasa Kumar, 14

Department of CS&E, IITM.

Problem with unrestricted use of Negation

What is the result of the query:

{s.rollNo | ¬ student(s)} ?

Infinite answers !!

Unsafe TRC expression :

Any expression whose result uses “constants / values” that do not
appear in the instances of any of the database relations.

Unsafe expressions are to be avoided while specifying TRC queries.

Prof P Sreenivasa Kumar, 15

Department of CS&E, IITM.

5
Expressive power of TRC and Relational Algebra
It can be shown that
both Tuple Relational Calculus and Relational Algebra
have the same expressive power

A query can be formulated in (safe) TRC

if and only if it can be formulated in RA

Both can not be used to formulate queries involving

transitive closure
-- find all direct or indirect pre-requisites of a course
-- find all subordinates of a specific employee etc.

Prof P Sreenivasa Kumar, 16

Department of CS&E, IITM.

Try this query - 1

List the name, roll number of students along with the courses
( course number only) in which they got an S grade.

student (rollNo, name, degree, year, sex, deptNo, advisor)

enrollment (rollNo, courseId, sem, year, grade)

{s.rollNo, s.name, e.courseId |

student(s) ^ enrollment(e)
s.rollNo = e.rollNo ^
e.grade = “S” }

Prof P Sreenivasa Kumar, 17

Department of CS&E, IITM.

Try this query - 2

List the name, roll number of male students being advised by lady
professors along with the name of the advisor.

student (rollNo, name, degree, year, sex, deptNo, advisor)

professor (empId, name, sex, startYear, deptNo, phone)

{s.rollNo, s.name, p.name |

student(s) ^ professor(p)
s.sex = “M” ^ p.sex = “F”^
s.advisor = p.empId }

Prof P Sreenivasa Kumar, 18

Department of CS&E, IITM.

6
Try this query - 3
List the name, course number of the prerequisites of the course
“Data Mining”.

course (courseId, cname, credits, deptNo)

preRequisite (preReqCourse, courseID)

{c.courseId, c.cname |
course(c) ^
(∃d)(∃q)( course(d) ^ d.cname = “Data Mining” ^
preRequisite(q) ^
q.courseId = d.courseId ^
q.preReqCourse = c.courseId )
}

Prof P Sreenivasa Kumar, 19

Department of CS&E, IITM.