Tuple Relational Calculus TRC

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.

Atoms in TRC

A predicate is built from atoms, which are basic true/false conditions:

Atom Type	Syntax	Meaning
Membership	`t ∈ R`	Tuple t is in relation R
Comparison	`t.A op c`	Attribute A of t compared to constant c
Attribute comparison	`t.A op s.B`	Compare attribute of t to attribute of s

Where op ∈ { =, ≠, <, >, ≤, ≥ }

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

EMPLOYEE(EmpID, Name, DeptID, Salary) DEPARTMENT(DeptID, DeptName, Location) PROJECT(ProjID, Title, Budget, DeptID) WORKS_ON(EmpID, ProjID, Hours)

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 ...)`

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.

Atoms in TRC

A predicate is built from atoms, which are basic true/false conditions:

Atom Type	Syntax	Meaning
Membership	`t ∈ R`	Tuple t is in relation R
Comparison	`t.A op c`	Attribute A of t compared to constant c
Attribute comparison	`t.A op s.B`	Compare attribute of t to attribute of s

Where op ∈ { =, ≠, <, >, ≤, ≥ }

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

EMPLOYEE(EmpID, Name, DeptID, Salary) DEPARTMENT(DeptID, DeptName, Location) PROJECT(ProjID, Title, Budget, DeptID) WORKS_ON(EmpID, ProjID, Hours)

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 ...)`

Tuple Relational Calculus TRC

Definition

Atoms in TRC

Logical Connectives

Quantifiers

Worked Examples

Setup Tables

Example 1: Simple Selection

Example 2: Projection

Example 3: Join Using Existential Quantifier

Example 4: Multiple Conditions

Example 5: Negation

Example 6: Universal Quantifier (Division-like)

Free and Bound Variables

TRC to SQL Mapping

Continue learning this concept

Tuple Relational Calculus TRC

Definition

Atoms in TRC

Logical Connectives

Quantifiers

Worked Examples

Setup Tables

Example 1: Simple Selection

Example 2: Projection

Example 3: Join Using Existential Quantifier

Example 4: Multiple Conditions

Example 5: Negation

Example 6: Universal Quantifier (Division-like)

Free and Bound Variables

TRC to SQL Mapping

Continue learning this concept