Are intersection and union redundant? Possibility to get smaller output without negation?

Question

I've just started learning relational algebra, so I'm reading a lot of articles for this topic. Not so long ago I've encountered two statements that seem to be quite weird to me.

1. ∩ and ∪ (intersection and union) are in fact redundant in relational algebra and you can rewrite any expression without them.

2. You can't get a smaller result without using negation. So expressions without it are always monotone

There were no explanation for those, so I'm not sure if those are true. Could you give some examples?

Answer 1

Regarding the first question, as you have said in the comments, you can define a relational algebra intersection with other relational algebra operators. Anyway, relational-algebra union is usually considered a relational algebra basic operator (that cannot be defined with other relational algebra operators).

Regarding monotonicity, we say that a query is monotone if the results of the query increases with the size of the database. More formally, a query $q$ is monotone if and only if, for any given database states $D_1$, $D_2$, where $D_1 \subseteq D_2$, we have $q(D_1) \subseteq q(D_2)$.

For instance, a monotone query might be: "All departments with at least one employee". Indeed, if you have a database state $D_1$ with 1 department with at least one employee (e.g. 'MarketingDepartment'), you know, for sure, that any $D_2 \supseteq D_1$ will still bring you such 'MarketingDepartment', and possibly more (since $D_2$ might have more departments with at least one employee).

A non-monotone query might be: "All departments with NO employee". Indeed, if you have a database state $D_1$ with 1 department with no employee (e.g. 'MarketingDepartment'), you can build a database $D_2 \supset D_1$ where 'MarketingDepartment' $\not\in q(D_2)$. Indeed, in $D_2$ you can add some employee for the 'MarketingDepartment', making 'MarketingDepartment' not satisfy your condition.

In relational-algebra, non-monotonic queries are defined through the set-difference operator (in the previous case: Department $\setminus$ $\pi_{dept}$ Employee). If a relational-algebra query has no set-difference operator involved, it is mononote.