Tuple Relational Calculus (TRC): Target List and Quantifiers (∃, ∀)

What is Relational Calculus? (In Simple Words)

While Relational Algebra is Procedural (“tells the computer HOW to evaluate step-by-step”), Relational Calculus is a Non-Procedural (Declarative) query language.

• In Relational Calculus, you specify WHAT data you want, without describing any sequence of operations to retrieve it.
• Analogy:
  • Relational Algebra: “Go to the kitchen, open the fridge, grab 2 eggs, heat the pan, fry them.” (Procedural recipe).
  • Relational Calculus: “I want fried eggs on my plate.” (Declarative goal).
• Relational Calculus forms the theoretical mathematical bedrock of SQL (Structured Query Language)!

1. Structure of a Tuple Relational Calculus (TRC) Query

A query in TRC is expressed as a set of mathematical tuples:

• Target List (t): Specifies the resulting tuple format or specific attributes to retrieve (e.g., t[Name]).
• Qualifying Statement / Predicate (P(t)): A boolean condition that evaluates to True or False for each tuple t. Only tuples where P(t) = True are included in the result!

2. Fundamental Components of TRC Formulas

A predicate formula P(t) is built from:

1. Relation Membership: t ∈ STUDENT (Tuple t belongs to table STUDENT).
2. Attribute Access: t[Name] or t.Name denotes the value of attribute Name for tuple t.
3. Comparison Conditions: t[Marks] > 75 or t[City] = 'Indore'.
4. Logical Connectives:
   • AND (∧): Both conditions must be True.
   • OR (∨): At least one condition must be True.
   • NOT (¬): Negates the condition.
5. Quantifiers: Existential Quantifier (∃) and Universal Quantifier (∀).

3. The Existential Quantifier (∃ - “There Exists”)

• Symbol: ∃ (Pronounced “There exists at least one”).
• Meaning: ∃ s (P(s)) evaluates to True if there is at least one tuple s that makes formula P(s) true.
• Used whenever a query involves checking for a match in another table (similar to a SQL EXISTS or JOIN).

Practical Example 1: Single Table Query

• Query: “Find all student tuples whose marks are greater than 80.”
  { t | t ∈ STUDENT ∧ t[Marks] > 80 }

Practical Example 2: Projecting Specific Columns

• Query: “Find the names and cities of students with marks > 80.”
  { t | ∃ s (s ∈ STUDENT ∧ s[Marks] > 80 ∧ t[Name] = s[Name] ∧ t[City] = s[City]) }

Practical Example 3: Two-Table Join

• Query: “Find the names of students enrolled in Course ‘CS101’.”
  { t | ∃ s (s ∈ STUDENT ∧ t[Name] = s[Name] ∧ (∃ e (e ∈ ENROLL ∧ e[Roll_No] = s[Roll_No] ∧ e[Course_ID] = 'CS101'))) }

4. The Universal Quantifier (∀ - “For All”)

• Symbol: ∀ (Pronounced “For all” or “For every”).
• Meaning: ∀ s (P(s)) evaluates to True if every single tuple s in the universe satisfies condition P(s).
• Used for queries involving phrases like “For all courses”, “Every department”, or “All projects”.

Relationship Between Quantifiers (De Morgan’s Laws):

In mathematical logic and database query engines, any expression written with ∀ can be converted into an equivalent expression using ∃ and NOT (¬):

• ∀ s (P(s)) ≡ ¬ (∃ s (¬ P(s)))
  (Saying “All students passed” is mathematically identical to saying “There does NOT exist any student who did NOT pass!”).
• ∃ s (P(s)) ≡ ¬ (∀ s (¬ P(s)))

5. Free vs. Bound Variables in Relational Calculus

• Bound Variable: A variable that is quantified using either ∃ or ∀ (e.g., ∃ s (...) means s is a bound variable).
• Free Variable: A variable that is NOT quantified (e.g., t in { t | P(t) } is the free variable that represents the output answer tuples).

💡 DAVV Exam Preparation Tips

5-Mark Question: “What is Tuple Relational Calculus (TRC)? Explain the Target list and Qualifying statement with an example.”

• Define TRC as a non-procedural / declarative query language based on first-order predicate calculus.
• Write down the standard syntax { t | P(t) }.
• Explain the Target list t and the Qualifying predicate formula P(t) with a simple STUDENT query.

10-Mark Question: “Explain the Existential Quantifier (∃) and Universal Quantifier (∀) in Tuple Relational Calculus. State De Morgan’s laws connecting them. Write TRC expressions for:

1. Find names of employees earning > 50,000.
2. Find employees working in ‘IT’ department.”

• Define both quantifiers with mathematical notation.
• State the equivalence: ∀ s (P(s)) ≡ ¬ (∃ s (¬ P(s))).
• Write Query 1: { t | ∃ e (e ∈ EMPLOYEE ∧ e[Salary] > 50000 ∧ t[Name] = e[Name]) }.
• Write Query 2: { t | ∃ e (e ∈ EMPLOYEE ∧ t[Name] = e[Name] ∧ (∃ d (d ∈ DEPARTMENT ∧ d[Dept_No] = e[Dept_No] ∧ d[Dept_Name] = 'IT'))) }.