Relational Foundations

Relational Calculus and Declarative Queries

Relational calculus describes a result by a predicate its tuples must satisfy rather than by a sequence of operators. This declarative foundation explains why SQL can state conditions with EXISTS, NOT EXISTS, and quantified comparisons while an optimizer chooses the procedure.

Tuple relational calculus ranges variables over tuples; domain relational calculus ranges variables over attribute values.
Existential quantification asks whether at least one binding makes a predicate true; universal quantification requires every binding to do so.
Universal conditions can be rewritten with existence and negation.
Safe, domain-independent expressions restrict outputs to values grounded in the database rather than ranging over an unbounded universe.
Relational algebra and safe relational calculus are equivalent in expressive power, even though one is operational in form and the other declarative.
Declarative meaning permits many valid physical plans; SQL clause order is not an instruction to execute nested loops in textual order.

A predicate, not a traversal recipe

The request “students enrolled in some database course” can be read as a predicate over a candidate student tuple s: include s if there exists an enrollment e and course c such that their identifiers match and c.subject = 'Database'. Nothing in that statement chooses an index, join algorithm, or evaluation order.

Quantifiers in query reasoning
Intent	Logical shape	SQL idiom
At least one match	`∃x P(x)`	`EXISTS (SELECT … WHERE P)`
No match	`¬∃x P(x)`	`NOT EXISTS (SELECT … WHERE P)`
Every x satisfies P	`∀x P(x)`	`NOT EXISTS (x WHERE NOT P(x))`
A implies B	`¬A ∨ B`	A disjunction or equivalent filtered anti-condition

Students with at least one database enrollment

SELECT s.student_id, s.name
FROM student AS s
WHERE EXISTS (
  SELECT 1
  FROM enrollment AS e
  JOIN course AS c ON c.course_id = e.course_id
  WHERE e.student_id = s.student_id
    AND c.subject = 'Database'
)