GATE CS 2014 Set 3 Q21 — Relational Model: Relational Algebra

To optimize the given relational algebra expression, we can apply standard heuristic optimization rules for relational algebra:

1. Selection Cascading (Combining Selections):
Consecutive selection operations can be combined into a single selection using the logical AND ($\\wedge$) operator: $$\\sigma_{F1}(\\sigma_{F2}(r)) \\equiv \\sigma_{F1 \\wedge F2}(r)$$ This reduces the number of passes or evaluations needed for filtering rows.

2. Projection Cascading (Eliminating Redundant Projections):
For nested projection operations $\\pi_{X}(\\pi_{Y}(R))$, if the set of attributes $X$ is a subset of $Y$ ($X \\subseteq Y$), then the intermediate projection onto $Y$ is redundant because the outer projection onto $X$ will ultimately discard any extra attributes in $Y$.
Given that $A1 \\subset A2$, we have: $$\\pi_{A1}(\\pi_{A2}(R)) \\equiv \\pi_{A1}(R)$$ Applying this to our expression where $R = \\sigma_{F1 \\wedge F2}(r)$ gives: $$\\pi_{A1}(\\pi_{A2}(\\sigma_{F1 \\wedge F2}(r))) \\equiv \\pi_{A1}(\\sigma_{F1 \\wedge F2}(r))$$

Thus, the optimized relational algebra expression is $\\pi_{A1}(\\sigma_{(F1 \\wedge F2)}(r))$, which corresponds to Option A.