retagged
10,685 views
43 votes
43 votes

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))$
retagged

3 Answers

Best answer
50 votes
50 votes
(A) $\pi_{A1}(\sigma_{F1 \wedge 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 by
5 votes
5 votes
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.
3 votes
3 votes

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 .

Answer:

Related questions

39 votes
39 votes
4 answers
3
go_editor asked Sep 28, 2014
13,037 views
A prime attribute of a relation scheme $R$ is an attribute that appearsin all candidate keys of $R$in some candidate key of $R$in a foreign key of $R$only in the primary ...
37 votes
37 votes
11 answers
4