Relational Algebra, Tuple Calculus & The Division Operator

SQL is a declarative language: you write WHAT data you want, not HOW to retrieve it. To optimize and execute your query, the database query engine translates SQL into Relational Algebra expressions.

Relational Algebra is a procedural query language where queries are composed of algebraic operators applied to relations, producing new relations as results. Because relations are formal mathematical sets of tuples, Relational Algebra provides the mathematical guarantee of closure (the output of any operation is itself a relation), enabling arbitrary nesting and algebraic optimization.

The 5 Primitive Operators:

1. Selection (σ_p(R)): Filters rows satisfying predicate p. Preserves degree (number of columns); reduces cardinality (number of rows).

2. Projection (π_{A1, A2}(R)): Extracts specified columns and eliminates duplicate rows. Reduces degree; preserves or reduces cardinality.

3. Cartesian Product (R × S): Pairs every tuple of R with every tuple of S. Degree = deg(R) + deg(S); Cardinality = |R| × |S|.

4. Set Union (R ∪ S): Combines tuples from union-compatible relations (same degree and domain-compatible attributes).

5. Set Difference (R - S): Returns tuples present in R but absent in S.

High-Yield Derived Operators:

• Natural Join (R ⋈ S): Cartesian product followed by equality selection on all common attribute names, projecting out duplicate column names.

• Theta Join (R ⋈_θ S): σ_θ(R × S).

• Division Operator (R ÷ S): Answers queries involving the universal quantifier 'FOR ALL' (e.g., 'Find students who enrolled in all courses taught by Dr. Rao').