# SQL, optimizing a select statement in relational algebra

is it possible to rewrite the following sql statement $\pi_{R.a,S.d} (\sigma_{R.b = "d" \land S.d \geq 100 \lor T.d \geq 200}((R\times S)\times T))$ ?

My problem is, i dont know if it is possible to split $\sigma_{R.b = "d" \land S.d \geq 100 \lor T.d \geq 200}$ to $\sigma_{R.b = "d"} \land \sigma_{S.d \geq 100 \lor T.d \geq 200}$,because the rules say i can split $\sigma_{x \land y}$ to $\sigma_{x} \land \sigma_{y}$ but i am not allowed to split $\sigma_{x \lor y}$.

Relations R(a,b,c), S(b,d) with a,d are integers, b,c,d are strings.

Edit: It is important to use brackets to specify which bool statements are compared, also if you have a statement that uses $\land and \lor$ you are not allowed to not write the brackets, that was my major mistake. correct formular $\pi_{R.a,S.d} (\sigma_{(R.b = "d" \land S.d \geq 100) \lor T.d \geq 200}((R\times S)\times T))$

In this case we are not allowed to split the $\sigma$ statement because we are bound to the $\lor$.

We could split the $\sigma$ if the statement would be:

$\pi_{R.a,S.d} (\sigma_{R.b = "d" \land (S.d \geq 100 \lor T.d \geq 200)}((R\times S)\times T))$ to $\pi_{R.a,S.d} (\sigma_{S.d \geq 100 \lor T.d \geq 200}((\sigma_{R.b = "d"}(R)\times S)\times T))$ Which would lead to a smaller kartesian product. At the end: What we are seeking is to bring the $\sigma$ as close to the leafs as possible to reduce our kartesian produkt

• What do you mean by "rewrite"? May 22, 2017 at 10:13
• Rewrite to what end? Changes are there are many equivalent statements; which do you prefer? May 22, 2017 at 10:16
• @YuvalFilmus sorry if i unclear, by rewrite i mean a more optimized form of the statement. May 22, 2017 at 18:19
• Firstly, this is not a "SQL statement". It's an expression in Relational Algebra, except using SQL-style dot-prefix attribute naming. Sorry, @normaluser221, but "optimized" for what purpose? Are you going to execute this statement? On what platform? What is your full schema? What are the cardinalities of the relations? Do those relations R, S, T have disjoint headings? Are you sure the cart product is valid? Why do you think that the formula is sub-optimal? I could go on ... Is this homework?
– AntC
May 23, 2017 at 2:31
• @YuvalFilmus I will edit my question with all information needed. We dont get any exercise sheets for the relational algebra part of our lecture, thats why learning becomes a bit difficult. May 23, 2017 at 17:00

I suspect this is a homework question.

Edit: OK, you're trying to invent your own homework. Well done for trying. You might have bitten off too much.

We need first to sort out the headings of your relations. As per my comment above, Cartesian product must have no attributes in common between operands. I'll assume headings: R(a,b), S(c,d), T(e,f) -- that is, no b in common between R, S; no d in common between S, T. Then I don't need to put the dot-prefix on attribute names. Your question becomes:

$\pi_{a,d} (\sigma_{(b = "d" \land d \geq 100) \lor f \geq 200}((R\times S)\times T))$

(If you do want attributes in common, then instead of $\times$, use Natural Join $\bowtie$. And the whole point about Natural Join (a beautiful operation, at the heart of the Relational Model) is that it 'commons up' the attribute names. So you still don't need the dot-prefix.

And what it's trying to teach you is that the Boolean operators (AND /\, OR \/) within a Select expression (sigma) are equivalent to certain set operators over the relations.

Edit: OK you've shown one equivalent for $\land$, which is to push the $\sigma$ inside the $\times$. More usually, you'd use set intersection $\cap$.

Yes you are allowed to 'split' a selection that is a disjunction (your sigma x\/y). Think about what is the set-theoretic operator that's equivalent to disjunction.

Edit: The set-theoretic operator is union $\cup$. For both intersection and union, we need the headings of the operands to be the same -- that is, the full Cartesian product.

Also beware: what's the relative precedence of the disjunction vs the conjunction in that sigma expression?

Edit: OK, you've answered that. So the outermost operator is $\lor$. Let's rewrite that to $\cup$ between relation values:

$\pi_{a,d} (\sigma_{(b = "d" \land d \geq 100)}((R\times S)\times T) \cup \sigma_{(f \geq 200)}((R\times S)\times T))$

Now in the left operand of $\cup$ we have a $\sigma$ with a $\land$. We can push that inside, as you've already shown. Similarly in the right operand we can push the $\sigma$ inside:

$\pi_{a,d} ( ((\sigma_{(b = "d")}R\times \sigma_{(d \geq 100)}S)\times T) \cup ((R\times S)\times \sigma_{(f \geq 200)}T))$

But notice in the right operand of $\cup$, we still have bare $(R \times S)$. So the union is going to include every (a,b) pair from S, and every (c,d) pair from R. (I suggest you try that out with a few sample sets of attribute values for those relations.) Your outermost projection, just takes a from R and d from S. So all the business with the $\sigma$s and $\land$, $\lor$ is rather pointless. And relation T is superfluous.

The most reduced form of your formula is:

$\pi_{a,d}(R \times S)$

Or even:

$(\pi_{a}(R)) \times (\pi_{d}(S))$

• you are correct, i had to write the brackets that would answer my question by itself. We have to learn the relational algebra part without any exercise sheets thats why i have to create my own expressions and optimize them. May 23, 2017 at 17:27
• i really thank you for the explanation! i didnt know we could use the set operations, which give use a even more reduced statement! May 28, 2017 at 8:04