2
$\begingroup$

The five basic operator select, project, cross, union and diff in relational algebra are independent of each other. I'm trying to formally prove this statement but can only progress for cross product as it would have columns greater than the rest which cannot be made possible by others. But can't think of anything for Select etc.

$\endgroup$
6
$\begingroup$

Here are some hints:

  • Select: consider the relation $\{(1),(2)\}$.
  • Project: number of columns can't decrease.
  • Cross product: number of columns can't increase.
  • Union: consider the database $\{(1)\},\{(2)\}$ with identical attributes.
  • Difference: similar to union.
$\endgroup$
  • $\begingroup$ Can you elaborate more about the relation {(1),(2)} part, could not understand that, is it possible to prove this mathematically? $\endgroup$ – gizgok Sep 3 '12 at 6:39
  • $\begingroup$ Use mathematical induction. The point is that you can't get $\{(1)\}$ or $\{(2)\}$ without using select. $\endgroup$ – Yuval Filmus Sep 3 '12 at 14:19
  • $\begingroup$ Can't {(1)} be obtained via difference of {(1),(2)} and {(2),(3)}? How would one guarantee {(2),(3)} hasn't been obtained somehow at prior induction step? $\endgroup$ – Tegiri Nenashi Sep 4 '12 at 18:00
  • $\begingroup$ @Tegiri You're right that $\{(1)\}$ can be obtained via the difference of $\{(1),(2)\}$ and $\{(2),(3)\}$. Fortunately, there is no row $(3)$ anywhere in the database. $\endgroup$ – Yuval Filmus Sep 4 '12 at 21:15
  • 1
    $\begingroup$ @Tegiri Regarding your first point, perhaps one can argue that selection is join, but the formal definition is different. Regarding your second point, you're right, it does look more complicated, since all tables can be produced using the other four operations. Presumably some functions cannot be realized without set difference. $\endgroup$ – Yuval Filmus Sep 4 '12 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.