557 views

What is the optimized version of the relation algebra expression $\pi_{A1}(\pi_{A2}(\sigma_{F1}(\sigma_{F2}(r))))$, where $A1, A2$ are sets of attributes in $r$ with  $A1 \subset A2$ and $F1,F2$ are Boolean expressions based on the attributes in $r$?

1. $\pi_{A1}(\sigma_{(F1 \wedge F2)}(r))$
2. $\pi_{A1}(\sigma_{(F1 \vee F2)}(r))$
3. $\pi_{A2}(\sigma_{(F1 \wedge F2)}(r))$
4. $\pi_{A2}(\sigma_{(F1 \vee F2)}(r))$
edited | 557 views

(A) πA1(σ(F1∧F2)(r))

since A1 is subset of A2 will get only A1 attributes as it is in the outside, so we can remove project A2.

Two Selects with boolean expression can be combined into one select with And of two boolean expressions.

edited

The Relational Algebra expression in the question above, does 4 operations, step by step ( innermost braces first ) .

1. Select those tuples from relation r which satisfies
expression/condition F1, say the result of this
operation is set A.

2. Select those tuples from set A which satisfies
expression/condition F2, say the result of this
operation is set B.

3. Select attrributes set A2 from set B, say the
result of this operation is set C.

4. Select attrributes set A1 from set C, say the
result is set D which is the final result.

Now to optimize this expression, we can combine operations/steps 1 and 2 by AND operator between F1 and F2 condition, like F1 ^ F2, and instead of selecting first attribute set A2, we can directly select attribute set A1 from the result of the combined operation, which is represented by expression in Option A .

In the last we have to project A1 so why project A2 so it can minimized to directly projecting the A1 and two boolean expression can be joined with the
AND condition.