GATE CS 2001 Q1.25 — Relational Model: Relational Algebra

The given relational algebra expression is:

$$\sigma_{A=a}(r \bowtie s)$$

We are given that $A$ is an attribute in the schema $R$ of relation $r$.

According to the heuristic query optimization rules in relational algebra, a selection operation $\sigma_{C}$ can be pushed down through a join $\bowtie$ if the selection condition $C$ involves only the attributes of one of the relations.

Since the selection condition $A = a$ only references the attribute $A$, which belongs to the schema $R$ of relation $r$, we can apply the selection directly to $r$ before performing the join:

$$\sigma_{A=a}(r \bowtie s) \equiv \sigma_{A=a}(r) \bowtie s$$

This optimization reduces the size of the relation $r$ before the join operation, making the query evaluation more efficient while producing the exact same result.

Thus, the expression is always equal to $\sigma_{A=a}(r) \bowtie s$.