The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 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))$
asked in Databases by Veteran (106k points)
retagged | 866 views

3 Answers

+27 votes
Best answer

(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.

answered by Loyal (3.4k points)
edited by
+1 vote
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.
answered by Loyal (3.8k points)
0 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 .

answered by Boss (7.8k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,732 questions
39,309 answers
36,733 users