Relational Algebra: Fundamental & Extended Relational Operations, Query Trees, and Optimization Heuristics

1. Relational Algebra: Procedural Foundations & Theoretical Role

Relational Algebra is a formal procedural query language that takes one or two relations as input and produces a new relation as its output. It is characterized as procedural because an algebraic expression prescribes the step-by-step computational sequence of operations required to compute the query result. In modern database management systems, relational algebra serves as the internal intermediate language into which declarative SQL queries are compiled and mathematically optimized.

2. The Five Fundamental Relational Operators

Any relational query can be formulated using a minimal canonical set of fundamental operators:

• Selection ((sigma)): A unary operator that filters horizontal tuples from a relation satisfying a specified predicate condition:
  $$\boxed{\[ \sigma_{\text{Salary} > 50000 \land \text{Dept} = 'IT'}(\text{EMPLOYEE}) \]}$$
• Projection ((pi)): A unary operator that selects specified vertical columns, stripping all unselected columns and automatically eliminating duplicate tuples:
  \[ \pi_{\text{EmpName}, \text{Salary}}(\text{EMPLOYEE}) \]
• Cartesian (Cross) Product (( imes)): A binary operator pairing every tuple of relation (R) with every tuple of relation (S). If (R) has (n) tuples and (S) has (m) tuples, (R imes S) yields (n imes m) tuples.
• Set Union ((cup)) & Set Difference ((-)): Valid strictly when relations are Union-Compatible (identical degree and pairwise identical attribute domains).
• Rename (( ho)): Unary operator providing temporary alias names to relations and attributes: ( ho_{S(A_1, A_2)}(R)).

3. Extended Relational Operators: Joins & Division

For operational conciseness, extended operators synthesize combinations of fundamental operators: