Tuple Relational Calculus(TRC)

• Tuple Relational Calculus (TRC) is introduced

Introduction

• Procedural Query language specification involves giving a step by step process of obtaining the query result
• Relational algebra is an example of a procedural query language
• Usage calls for detailed knowledge of the operators involved, making it difficult for non-experts
• Declarative Query languages query specification involves giving the logical conditions the results are required to satisfy
• Declarative Query languages are easy for the use of non-experts

Predicates

• A predicate is an expression with place-holders (aka variables) that takes a Boolean value when values are substituted for variables
• Lessthan(x,y) is an example of a predicate; e.g., lessthan(2,5) is true, and lessThan(5,1) is false
• livesIn(p,c) is another example; e.g., livesIn(SindhuPV, Hyderabad) is true, livesIn(AvaniLekhara, Jaipur) is true, and livesIn(AdarPoonawala, Chennai) is false
• Predicates can have n-places

Relations and Predicates

• Can the 'relation names' of a relational model be interpreted as predicates?
• Recall that a DB Relation is a finite set of tuples
• A Tuple sequence of values, where 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
• Closed-World Assumption (CWA): tuples in the relation instance make the predicate true and those not present in the instance make it false

TRC Query Language

• TRC is a declarative query language
• A Tuple variable is associated with a relation and takes tuples as its values, called the range relation
• For a tuple variable t over relation r with scheme R(A,B,C), t.A stands for value of column/attribute A in t
• TRC Query - basic form: {t1. Ai,t2. Ai...tm. Ai | 0}
  • Predicate logic expression involving tuple variables t1, t2,..., tm, tm+1,..., ts specifies the condition to be satisfied

TRC Query Example

• Using two relations: student (rollNo, name, degree, year, sex, deptNo, advisor) and department (deptId, name, hod, phone)
• To obtain the rollNo and name of all girl students in the Maths Dept (deptId = 2): {s.rollNo,s.name | student (s) ^ s.sex='F' A s.deptno=2}
• Predicate is true whenever value of s is a tuple from the Student instance; otherwise, it's false
• 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

TRC Queries Conditions

• General form of the condition in TRC queries include:
  • Atomic expressions: r(t) is true if t is a tuple in the relation instance r
  • t1.Ai <compOp> t2.Aj, where compOp is one of {<, ≤, >, ≥, =, ≠ }
  • t.Ai <compOp> c, where c is a constant of appropriate type
• Composite expressions include:
  • Any atomic expression
  • F1 ∧ F2, F1 ∨ F2, ¬F1, where F1 and F2 are expressions
  • (∀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

TRC Query Interpretation

• 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
• The only free variables are the ones that appear to the left of the vertical bar

TRC Queries Example 2

• To obtain the rollNo and name of all girl students in the Maths Dept: {s.rollno, s.name | student (s) ^ s.sex = 'F' A (∃d) (department (d) ^ d.name= 'Maths' ∧ d.deptId = s.deptno)}
  • s is a free tuple variable and d is an 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

Relational Scheme Examples

• The following relations and attributes can be used:
  • 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)
  • enrollment (rollNo, courseId, sem, year, grade)
  • teaching (empId, courseId, sem, year, classRoom)
  • preRequisite (preReqCourse, courseID)

TRC Queries Example 3

• Determine the departments that do not have any girl students using:
  • student (rollNo, name, degree, year, sex, deptNo, advisor)
  • department (deptId, name, hod, phone)
• TRC Query: {d.name|department (d) ^ -(∃s) (student(s) ^ s.sex = ‘F’ A s.deptno = d.deptId)}

TRC Queries Example 4

• Given a database with two relations, Determine names of courses enrolled By a students called Mahesh
• Relations
  • course (courseId, cname, credits, deptNo)
  • enrollment (rollNo, courseId, sem, year, grade)
  • student (rollNo, name, degree, year, sex, deptNo, advisor)
• To find the names of courses enrolled by student named Mahesh use the following expression -{c.name | course (c) ∧ (∃s)(∃e)(Student(s) ∧ enrollment (e) ∧ s.name = “Mahesh”∧ s.rollNo = e.rollNo ∧ c.courseId = e.courseId)}

TRC Queries Example 5

• Get the names of students who have scored 'S' in all subjects they have enrolled, assuming that every student is enrolled in at least one course
• Given relations: student(s) and enrollment(e)
• Expression: {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

TRC Queries Example 6

• To get the names of students who have taken at least one course taught by their advisor:
  • Given relations: student(s), enrollment(e), and teaching(t)
  • {s.name | student(s) ∧ (∃e)(∃t)(enrollment (e) ∧ teaching(t) ∧ e.courseId = t.courseId ∧ e.sem = t.sem ∧ e.year = t.year ∧ e.rollNo = s.rollNo ∧ t.empId = s.advisor)}
• To display the departments whose HODs taught at least one course in the odd semester of 2019:
  • Given relations: department(d) and teaching(t)
  • {d.name | department(d) ∧ (∃t)(teaching(t) ∧ t.empid = d.hod ∧ t.sem = 'odd' ∧ t.year = '2019')}

TRC Queries Example 7

• Determine the students who are enrolled for every course taught by Prof Ramanujam, assuming that Prof Ramanujam teaches at least one course
  • Given relations: student(s), course(c), professor(p), teaching(t), and enrollment(e)
    • {s.rollNo | student (s) ∧ (∀c) (course (c) ∧ ((∃t)(∃p)( teaching(t) p.name = "Ramanujam" ∧ p.empId = t.empId) → (∃e) (enrollment (e) ∧ e.courseId = c.courseId ∧ e.rollNo = s.rollNo ∧ e.sem = t.sem ∧ e.year = t.year ))}

Negation Restriction

• Problem: What is the result of the query {s.rollNo | ¬student(s)}?
  • Infinite answers
• An 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

TRC Expressive power

• 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

Extra Practice Queries

• List the name and 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)
• Use the following code block: {s.rollno, s.name, e.courseId | student(s) ∧ enrollment (e) ∧ s.rollNo = e.rollNo ∧ e.grade = "s" }

Extra Practice Queries2

• 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)
• Use the following code block: {s.rollno, s.name, p.name | student(s) ∧ professor (p) ∧ s.sex = "M" ∧ p.sex = "F" ∧ s.advisor = p.empId }

Extra Practice Queries3

• List the name, course number of all the prerequisites of the course "Data Mining"
• course (courseId, cname, credits, deptNo)
• preRequisite (preReqCourse, courseID)
• Use the following code block: {c.courseId, c.cname | course (c) ∧ (∃d) (∃q) (course(d) ∧ d.cname = "Data Mining” ∧ prerequisite(q) ∧ q.courseId = d.courseId ∧ q.preReqCourse = c.courseId ) }