<p>Here are some hints:</p>

<ul>
<li>Select: consider the relation $\{(1),(2)\}$.</li>
<li>Project: number of columns can't decrease.</li>
<li>Cross product: number of columns can't increase.</li>
<li>Union: consider the database $\{(1)\},\{(2)\}$ with identical attributes.</li>
<li>Difference: similar to union.</li>
</ul>

CC BY-SA 3.0
2012-09-03T06:39:55.327Z
Can you elaborate more about the relation {(1),(2)} part, could not understand that, is it possible to prove this mathematically?
gizgok
CC BY-SA 3.0
2012-09-03T14:19:49.183Z
Use mathematical induction. The point is that you can't get  $\{(1)\}$ or $\{(2)\}$ without using select.
Yuval Filmus
CC BY-SA 3.0
2012-09-04T18:00:01.940Z
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?
Tegiri Nenashi
CC BY-SA 3.0
2012-09-04T21:15:40.000Z
@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.
Yuval Filmus
CC BY-SA 3.0
2012-09-04T21:16:47.237Z
@Tegiri As for your second question, the way the induction works is that you assume that no $t$ operations produce (say) $\{(2),(3)\}$, and you prove that no $t+1$ produce it. In this case, you will prove by induction that the only databases obtained are $\{(1),(2)\}$ and $\emptyset$.
Yuval Filmus
CC BY-SA 3.0
2012-09-04T21:33:43.213Z
@Yuval But then, the induction proof has to cover not only my "counterexample" tuple but all similar tuples. Besides, one can argue that selection is join; in our example $\sigma_{x=1} \{(1),(2)\}$ is join of {(1),(2)} with unary "x=1", which is exactly {(1)} which you suggested not present in the database.
Tegiri Nenashi
CC BY-SA 3.0
2012-09-04T22:01:26.193Z
@Yuval I may concede selection case, but let's consider set difference. Given the database {(1),(2)},{(2)} I'd suggest $\{(1),(2)\}- \{(2)\} = \sigma _{x \le 1} \{(1),(2)\} $, so the proof must be more elaborated then just examining database with couple relations?
Tegiri Nenashi
CC BY-SA 3.0
2012-09-04T22:36:52.707Z
@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.
Yuval Filmus
CC BY-SA 3.0
2012-09-03T05:13:53.507Z
2012-09-03T05:13:53.507Z
Yuval Filmus
<p>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.</p>

<db.databases><algebra>
How to go about proving the basic operators in relational algebra are independent of each other?
gizgok
# How to go about proving the basic operators in relational algebra are independent of each other?

(Asked by: username_0 on 2012-09-02)

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.

**Tags:** db.databases, algebra


---

## 1 answers

### Answer by username_1 on 2012-09-03. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: Can you elaborate more about the relation {(1),(2)} part, could not understand that, is it possible to prove this mathematically?  
> **username_1**: Use mathematical induction. The point is that you can't get  $\{(1)\}$ or $\{(2)\}$ without using select.  
> **username_2**: 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?  
> **username_1**: @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.  
> **username_1**: @Tegiri As for your second question, the way the induction works is that you assume that no $t$ operations produce (say) $\{(2),(3)\}$, and you prove that no $t+1$ produce it. In this case, you will prove by induction that the only databases obtained are $\{(1),(2)\}$ and $\emptyset$.  
> **username_2**: @Yuval But then, the induction proof has to cover not only my "counterexample" tuple but all similar tuples. Besides, one can argue that selection is join; in our example $\sigma_{x=1} \{(1),(2)\}$ is join of {(1),(2)} with unary "x=1", which is exactly {(1)} which you suggested not present in the database.  
> **username_2**: @Yuval I may concede selection case, but let's consider set difference. Given the database {(1),(2)},{(2)} I'd suggest $\{(1),(2)\}- \{(2)\} = \sigma _{x \le 1} \{(1),(2)\} $, so the proof must be more elaborated then just examining database with couple relations?  
> **username_1**: @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.  

---

