Tuple and Domain Relational Calculus

Relational calculus is a non-procedural query language based on mathematical logic (predicate calculus). It describes what data to retrieve without specifying how to retrieve it.

Two Variants:

1. Tuple Relational Calculus (TRC)
Variables range over tuples (rows)

2. Domain Relational Calculus (DRC)
Variables range over domain values (individual attributes)

General Form (TRC):

{ t | P(t) }

Where:

• t is a tuple variable
• P(t) is a predicate (logical formula)
• Result contains all tuples t for which P(t) is true

Quantifiers:

Existential (∃): "There exists"
∃t ∈ R (P(t)) means: There exists a tuple t in relation R such that P(t) is true

Universal (∀): "For all"
∀t ∈ R (P(t)) means: For all tuples t in relation R, P(t) is true

Relationship to SQL:

TRC/DRC ≡ SQL SELECT
Relational Algebra ≡ Query execution plans

All three are relationally complete (express same queries)

EXAMPLE SCHEMA:

Employee Table:

EmpID	Name	DeptID	Salary
101	Alice	10	60000
102	Bob	20	55000
103	Charlie	10	70000
104	Diana	30	50000

Department Table:

DeptID	DeptName	Location
10	IT	NYC
20	HR	LA
30	Sales	Chicago

Project Table:

ProjID	ProjName	DeptID
P1	Alpha	10
P2	Beta	20
P3	Gamma	10

WorksOn Table:

EmpID	ProjID	Hours
101	P1	20
101	P3	15
102	P2	30
103	P1	25

TRC EXAMPLES:

Example 1: Simple Selection

Query: Find all employees with salary > 55000

TRC:
{ t | t ∈ Employee ∧ t.Salary > 55000 }

Result:

EmpID	Name	DeptID	Salary
101	Alice	10	60000
103	Charlie	10	70000

SQL:
SELECT * FROM Employee WHERE Salary > 55000;

Example 2: Projection

Query: Find names of employees earning > 55000

TRC:
{ t.Name | t ∈ Employee ∧ t.Salary > 55000 }

Result:

Name
Alice
Charlie

SQL:
SELECT Name FROM Employee WHERE Salary > 55000;

Example 3: Join with Existential Quantifier

Query: Find names of employees in IT department

TRC:
{ t.Name | t ∈ Employee ∧ ∃d ∈ Department (t.DeptID = d.DeptID ∧ d.DeptName = 'IT') }

Result:

Name
Alice
Charlie

SQL:
SELECT e.Name
FROM Employee e
WHERE EXISTS (
SELECT 1
FROM Department d
WHERE e.DeptID = d.DeptID AND d.DeptName = 'IT'
);

Example 4: Multiple Conditions

Query: Find employees in NYC earning > 55000

TRC:
{ t.Name, t.Salary | t ∈ Employee ∧ ∃d ∈ Department (t.DeptID = d.DeptID ∧ d.Location = 'NYC' ∧ t.Salary > 55000) }

Result:

Name	Salary
Alice	60000
Charlie	70000

SQL:
SELECT e.Name, e.Salary
FROM Employee e
JOIN Department d ON e.DeptID = d.DeptID
WHERE d.Location = 'NYC' AND e.Salary > 55000;

Example 5: Universal Quantifier

Query: Find employees who work on ALL projects in their department

TRC:
{ t.Name | t ∈ Employee ∧ ∀p ∈ Project (p.DeptID ≠ t.DeptID ∨ ∃w ∈ WorksOn (w.EmpID = t.EmpID ∧ w.ProjID = p.ProjID)) }

Explanation:

• For all projects p
• Either p is not in employee's department OR employee works on p

Result:

Name
Alice
(Alice works on both IT projects P1 and P3)

SQL:
SELECT e.Name
FROM Employee e
WHERE NOT EXISTS (
SELECT p.ProjID
FROM Project p
WHERE p.DeptID = e.DeptID
AND p.ProjID NOT IN (
SELECT w.ProjID
FROM WorksOn w
WHERE w.EmpID = e.EmpID
)
);

Example 6: Negation

Query: Find employees NOT in IT department

TRC:
{ t.Name | t ∈ Employee ∧ ¬∃d ∈ Department (t.DeptID = d.DeptID ∧ d.DeptName = 'IT') }

Result:

Name
Bob
Diana

SQL:
SELECT Name
FROM Employee
WHERE DeptID NOT IN (
SELECT DeptID FROM Department WHERE DeptName = 'IT'
);

DRC EXAMPLES:

Example 7: Simple Selection (DRC)

Query: Find employee IDs and names with salary > 55000

DRC:
{ <i, n> | ∃d, s (<i, n, d, s> ∈ Employee ∧ s > 55000) }

Result:

EmpID	Name
101	Alice
103	Charlie

SQL:
SELECT EmpID, Name FROM Employee WHERE Salary > 55000;

Example 8: Join (DRC)

Query: Find employee names and their department names

DRC:
{ <en, dn> | ∃ei, ed, es, did, dl (
<ei, en, ed, es> ∈ Employee ∧
<did, dn, dl> ∈ Department ∧
ed = did
) }

Result:

EmpName	DeptName
Alice	IT
Bob	HR
Charlie	IT
Diana	Sales

SQL:
SELECT e.Name AS EmpName, d.DeptName
FROM Employee e
JOIN Department d ON e.DeptID = d.DeptID;

Example 9: Universal Quantifier (DRC)

Query: Find students enrolled in all courses

Assume:
Student: <StudentID, Name>
Course: <CourseID, CourseName>
Enrollment: <StudentID, CourseID>

DRC:
{ <sid> | ∃sn (<sid, sn> ∈ Student ∧
∀cid (∃cn (<cid, cn> ∈ Course) ⇒
∃ (<sid, cid> ∈ Enrollment))
) }

SQL:
SELECT s.StudentID
FROM Student s
WHERE NOT EXISTS (
SELECT c.CourseID
FROM Course c
WHERE NOT EXISTS (
SELECT *
FROM Enrollment e
WHERE e.StudentID = s.StudentID
AND e.CourseID = c.CourseID
)
);

Example 10: Complex Query with Multiple Quantifiers

Query: Find departments where all employees earn > 50000

TRC:
{ d.DeptName | d ∈ Department ∧
∀t ∈ Employee (t.DeptID ≠ d.DeptID ∨ t.Salary > 50000)
}

Explanation:

• For all employees t
• Either t is not in this department OR t.Salary > 50000

DRC:
{ <dn> | ∃did, dl (<did, dn, dl> ∈ Department ∧
∀ei, en, ed, es (
<ei, en, ed, es> ∈ Employee ⇒
(ed ≠ did ∨ es > 50000)
))
}

SQL:
SELECT d.DeptName
FROM Department d
WHERE NOT EXISTS (
SELECT *
FROM Employee e
WHERE e.DeptID = d.DeptID AND e.Salary <= 50000
);

SAFETY EXAMPLES:

Example 11: Unsafe Expression

Unsafe:
{ t | ¬(t ∈ Employee) }

Why unsafe? Result includes infinite tuples not in Employee

Safe version:
Not possible to make this safe meaningfully

Example 12: Safe Expression with Negation

Query: Find employees NOT working on any project

Unsafe:
{ t | t ∈ Employee ∧ ¬∃w ∈ WorksOn (w.EmpID = t.EmpID) }

Actually this IS safe because:

1. t bounded to Employee
2. Result limited to Employee tuples

Result:

EmpID	Name	DeptID	Salary
104	Diana	30	50000

SQL:
SELECT *
FROM Employee e
WHERE NOT EXISTS (
SELECT * FROM WorksOn w WHERE w.EmpID = e.EmpID
);

PRACTICAL APPLICATIONS:

1. Query Language Foundation:

Relational calculus is the theoretical basis for SQL's SELECT statement.

SQL SELECT = TRC/DRC expression

2. Query Optimization:

Understanding calculus helps:

• Rewrite queries for efficiency
• Understand query equivalences
• Recognize optimization opportunities

3. Formal Verification:

Prove two queries are equivalent using calculus

Query 1 (SQL):
SELECT Name FROM Employee WHERE Salary > 50000;

Query 2 (SQL):
SELECT Name FROM Employee WHERE NOT (Salary <= 50000);

Both equivalent to:
{ t.Name | t ∈ Employee ∧ t.Salary > 50000 }

4. Database Theory:

• Prove query language completeness
• Study expressiveness limitations
• Understand decidability

5. Advanced Query Features:

Calculus forms basis for:

• Nested subqueries
• Correlated subqueries
• EXISTS/NOT EXISTS
• ALL/ANY quantifiers

SQL TO CALCULUS PATTERNS:

EXISTS → ∃

SQL:
SELECT e.Name
FROM Employee e
WHERE EXISTS (
SELECT * FROM Department d
WHERE e.DeptID = d.DeptID AND d.DeptName = 'IT'
);

TRC:
{ t.Name | t ∈ Employee ∧ ∃d ∈ Department (t.DeptID = d.DeptID ∧ d.DeptName = 'IT') }

NOT EXISTS → ∀ (negated)

SQL:
SELECT e.Name
FROM Employee e
WHERE NOT EXISTS (
SELECT * FROM WorksOn w
WHERE w.EmpID = e.EmpID
);

TRC:
{ t.Name | t ∈ Employee ∧ ¬∃w ∈ WorksOn (w.EmpID = t.EmpID) }

Or equivalently:
{ t.Name | t ∈ Employee ∧ ∀w ∈ WorksOn (w.EmpID ≠ t.EmpID) }

ALL → ∀

SQL:
SELECT Name
FROM Employee
WHERE Salary >= ALL (SELECT Salary FROM Employee);

TRC:
{ t.Name | t ∈ Employee ∧ ∀s ∈ Employee (t.Salary ≥ s.Salary) }

ANY → ∃

SQL:
SELECT Name
FROM Employee
WHERE Salary > ANY (SELECT Salary FROM Employee WHERE DeptID = 10);

TRC:
{ t.Name | t ∈ Employee ∧ ∃s ∈ Employee (s.DeptID = 10 ∧ t.Salary > s.Salary) }

TOOLS FOR PRACTICE:

1. Paper and Pencil: Best for learning
2. Logic Proof Assistants: Coq, Isabelle
3. Relational Calculus Interpreters: Some academic tools
4. SQL: Practice by writing equivalent SQL

COMMON MISTAKES:

Mistake 1: Forgetting Domain Restriction

Wrong:
{ t | t.Salary > 50000 }

Right:
{ t | t ∈ Employee ∧ t.Salary > 50000 }

Mistake 2: Incorrect Quantifier Usage

Wrong (for "employees in IT"):
{ t.Name | ∀d ∈ Department (t.DeptID = d.DeptID ∧ d.DeptName = 'IT') }

Right:
{ t.Name | t ∈ Employee ∧ ∃d ∈ Department (t.DeptID = d.DeptID ∧ d.DeptName = 'IT') }

Mistake 3: Unsafe Expressions

Wrong:
{ t | ¬(t ∈ Employee) }

Right:
{ t | t ∈ SomeRelation ∧ ¬(t ∈ Employee) }

Mistake 4: Confusing ∀ with ∃

"Find employees working on project P1":
Wrong: ∀w ∈ WorksOn (w.ProjID = 'P1')
Right: ∃w ∈ WorksOn (w.EmpID = t.EmpID ∧ w.ProjID = 'P1')

INTERVIEW TIPS:

1. Remember: ∃ = OR, ∀ = AND (loosely)
2. Universal quantifier often used with implication (⇒)
3. Double negation for "for all": ¬∃ ≡ ∀¬
4. Always specify tuple variable domain (t ∈ R)
5. Check safety: Result must be finite