Tuple relational calculus: quantifiers and safety
Goals and relation vocabulary
Translate “some,” “none,” and “every” into tuple predicates and reject queries that range over an unbounded universe. Prerequisites: relational algebra and elementary predicate logic. We use finite, non-null, set-valued relations Student(sid,name), Course(cid), Enrol(sid,cid). Tuple relational calculus (TRC) specifies a property of the result rather than an operator sequence.
Write {t | P(t)} for the set of result tuples t satisfying predicate P. An atom Student(s) says s is a tuple in Student. Equality s.sid=e.sid compares attributes. ∃e means there exists a tuple e satisfying the following predicate; ∀c means every tuple c in the quantifier's universe must satisfy it. Parentheses and guards make scope explicit. In examples where output has only sid, its schema is stated as t(sid).
1. Free and bound tuple variables
In {t(sid) | ∃s(Student(s) ∧ t.sid=s.sid)}, s is bound by ∃ and t is free in the predicate, determining the output. The relation guard Student(s) restricts useful witnesses to stored students. Renaming a bound variable consistently does not change a query. Confusing output t with a bound variable can change its meaning or leave the result unspecified.
To return entire student tuples satisfying a condition, {s | Student(s) ∧ condition(s)} is convenient. To return only their ids, use an output tuple t(sid) tied to a matching student id. TRC set semantics remove duplicate results, even if multiple witnesses satisfy the existential predicate.
2. Existential queries and joins
Students enrolled in A can be expressed as:
{s | Student(s) ∧ ∃e(Enrol(e) ∧ e.sid=s.sid ∧ e.cid=A)}.
Worked instance: Student={(1,Ana),(2,Bob),(3,Chen),(4,Dev)} and Enrol={(1,A),(1,B),(2,A),(3,C)}. Students 1 and 2 have witnesses with cid=A; students 3 and 4 do not. Result is the full tuples (1,Ana),(2,Bob). Extra witnesses would not duplicate a student tuple.
Students with no enrollments use a negated existence:
{s | Student(s) ∧ ¬∃e(Enrol(e) ∧ e.sid=s.sid)}.
Only (4,Dev) qualifies. Notice the positive Student(s) guard remains outside the negation. We are finding stored students without a match, not arbitrary tuples outside Enrol.
3. Universal queries: no counterexample
For every course in Course, student s must have a matching enrollment:
{s | Student(s) ∧ ∀c(Course(c) → ∃e(Enrol(e) ∧ e.sid=s.sid ∧ e.cid=c.cid))}.
The Course(c) guard is inside an implication. Tuples not in Course impose no requirement. Replacing the implication with Course(c) ∧ ... under an unrestricted ∀ would wrongly require every tuple in the universe to belong to Course.
Use the logical identity ∀c(A(c)→B(c)) ≡ ¬∃c(A(c)∧¬B(c)) to obtain:
{s | Student(s) ∧ ¬∃c(Course(c) ∧ ¬∃e(Enrol(e) ∧ e.sid=s.sid ∧ e.cid=c.cid))}.
Worked trace with Course={A,B}: student 1 has no missing course and passes; student 2 is missing B; student 3 misses A and B; student 4 also misses both. Only student 1 qualifies. If Course is empty, every stored student qualifies, including student 4, because no counterexample course exists. If the requirement additionally says “and takes at least one course,” add a separate existential enrollment condition.
4. Safety and domain independence
The unrestricted query {t | ¬Student(t)} is unsafe for the intended finite relational setting: it can enumerate all possible tuples outside the stored relation. Its result can grow when the ambient domain grows, even though stored data has not changed. By contrast {s | Student(s) ∧ ¬∃e(Enrol(e) ∧ e.sid=s.sid)} returns a subset of a finite stored relation and expresses a domain-independent query.
A practical discipline is to range result values over stored data or explicit constants, bind witness variables through positive relation atoms, and use guarded negation/quantifiers. This is a useful safe-writing discipline, not a complete decision algorithm for arbitrary first-order formulas. Output values need not already occur in stored data if they are explicitly introduced constants; do not overstate safety as “no constants allowed.” Safe/domain-independent calculus has the expressive power of relational algebra for the standard relational setting; unrestricted calculus is not the intended executable query language.
5. Common mistakes and checking procedure
- State the output schema and candidate domain.
- Guard stored candidates with a positive relation atom.
- Decide whether one witness, no witness, or no counterexample is required.
- Parenthesize the scope of each quantifier and check attribute comparisons.
- Test empty input, empty requirement relation, and a candidate with no matches.
“Every student takes some course” permits a different course for each student: ∀s∃c under appropriate guards. “Some course is taken by every student” uses ∃c∀s and requires one common course. Quantifier order is substantive.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. In {t(sid) | ∃s(Student(s) ∧ t.sid=s.sid)}, which variable is bound by a quantifier?
A. t only B. s only C. Both t and s D. Neither
Answer: B
A: t is the free output variable in the predicate.
B: The existential quantifier binds s.
C: The output variable is not bound by ∃s.
D: s is explicitly bound.
P02. “No matching enrollment exists” is expressed using:
A. An unguarded output complement B. Negated existential matching predicate C. Existence of any unrelated enrollment D. An equality of relation names
Answer: B
A: That can include arbitrary tuples outside stored candidates.
B: ¬∃ states that no witness satisfies the match.
C: An unrelated witness says nothing about this student.
D: Relation names are not the required tuple condition.
P03. Which is logically equivalent to ∀x(P(x)→Q(x))?
A. ∃x(P(x)∧Q(x)) B. ¬∃x(P(x)∧¬Q(x)) C. ∀x(P(x)∧Q(x)) D. ¬∃x(P(x)∧Q(x))
Answer: B
A: One successful witness is insufficient for every P.
B: There is no P witness that violates Q.
C: This wrongly requires P for every domain value.
D: This forbids successful P-and-Q witnesses.
P04. All stored students are candidates. If the required Course relation is empty, who satisfies “enrolled in every required course”?
A. No students B. Only students with enrollment rows C. Every stored student D. Every possible tuple in the universe
Answer: C
A: There is no counterexample course.
B: The condition does not separately require an enrollment.
C: Vacuous truth applies to all stored candidates.
D: Student membership still bounds the output.
P05. Why is {t | ¬Student(t)} unsafe in an unrestricted tuple universe?
A. It uses a relation name B. It may return unbounded tuples outside stored data C. It always returns zero rows D. It contains an existential quantifier
Answer: B
A: Relation membership is normal in safe queries.
B: Its complement depends on the ambient universe.
C: Many tuples can lie outside Student.
D: No existential quantifier appears in this formula.
P06. Which requirement needs one common course shared by every student?
A. Every student takes some course B. Some course is taken by every student C. Some student takes some course D. No student takes any course
Answer: B
A: The chosen course may vary between students.
B: The existential course is chosen before the universal student.
C: This asks for only one enrollment witness.
D: This forbids enrollments rather than seeking a common course.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in