DBMS Notes
Tuple Relational Calculus (TRC) is a non-procedural query language where each query is expressed as:
Definition
Tuple Relational Calculus (TRC) is a non-procedural query language where each query is expressed as:
{ t | P(t) }
t → a tuple variable
P(t) → a predicate (condition) that must be satisfied
The result is the set of all tuples t for which the predicate P(t) evaluates to TRUE.
Logical Connectives
Atoms are combined using:
∧(AND) — both conditions true∨(OR) — at least one condition true¬(NOT) — negation
Quantifiers
| Quantifier | Symbol | Meaning |
|---|---|---|
| Existential | ∃ | There exists at least one tuple |
| Universal | ∀ | For all tuples |
Worked Examples
Setup Tables
Example 1: Simple Selection
Find all employees with salary greater than 80,000.
{ t | t ∈ EMPLOYEE ∧ t.Salary > 80000 }
SQL:
SELECT * FROM EMPLOYEE WHERE Salary > 80000;
Example 2: Projection
Find the names of all employees.
{ t.Name | t ∈ EMPLOYEE }
SQL:
SELECT Name FROM EMPLOYEE;
Example 3: Join Using Existential Quantifier
Find names of employees and their department names.
{ <t.Name, s.DeptName> |
t ∈ EMPLOYEE ∧
∃s (s ∈ DEPARTMENT ∧ s.DeptID = t.DeptID)
}
SQL:
SELECT e.Name, d.DeptName
FROM EMPLOYEE e JOIN DEPARTMENT d ON e.DeptID = d.DeptID;
Example 4: Multiple Conditions
Find names of employees in the CS department earning more than 70,000.
{ t.Name |
t ∈ EMPLOYEE ∧
t.Salary > 70000 ∧
∃s (s ∈ DEPARTMENT ∧
s.DeptID = t.DeptID ∧
s.DeptName = 'Computer Science')
}
SQL:
SELECT e.Name FROM EMPLOYEE e
JOIN DEPARTMENT d ON e.DeptID = d.DeptID
WHERE e.Salary > 70000 AND d.DeptName = 'Computer Science';
Example 5: Negation
Find employees NOT in department 1.
{ t | t ∈ EMPLOYEE ∧ ¬(t.DeptID = 1) }
SQL:
SELECT * FROM EMPLOYEE WHERE DeptID <> 1;
Example 6: Universal Quantifier (Division-like)
Find employees who work on ALL projects.
{ t | t ∈ EMPLOYEE ∧
∀p (p ∈ PROJECT →
∃w (w ∈ WORKS_ON ∧ w.EmpID = t.EmpID ∧ w.ProjID = p.ProjID))
}
"For every project p, there exists a WORKS_ON record linking this employee to p"
SQL (using NOT EXISTS):
SELECT e.* FROM EMPLOYEE e
WHERE NOT EXISTS (
SELECT p.ProjID FROM PROJECT p
WHERE NOT EXISTS (
SELECT * FROM WORKS_ON w
WHERE w.EmpID = e.EmpID AND w.ProjID = p.ProjID
)
);
Free and Bound Variables
- A variable is bound if it appears within the scope of a quantifier (∃ or ∀)
- A variable is free if it is not bound
{ t.Name | t ∈ EMPLOYEE ∧ ∃s (s ∈ DEPARTMENT ∧ s.DeptID = t.DeptID) }
↑ free ↑ bound (within ∃s scope)
The answer tuple variable (the one before |) must be a free variable.
TRC to SQL Mapping
| TRC Construct | SQL Equivalent | |
|---|---|---|
| `{ t \ | t ∈ R ∧ P(t) }` | SELECT * FROM R WHERE P |
| `{ t.A \ | t ∈ R }` | SELECT A FROM R |
P1 ∧ P2 | P1 AND P2 | |
P1 ∨ P2 | P1 OR P2 | |
¬P | NOT P | |
∃s(s ∈ S ∧ ...) | EXISTS (SELECT * FROM S WHERE ...) | |
∀s(s ∈ S → ...) | NOT EXISTS (SELECT * FROM S WHERE NOT ...) |
Continue the lesson path