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?

  • 1
    $\begingroup$ Can you share source/page? $\endgroup$ – zkutch Sep 20 '20 at 20:01
  • $\begingroup$ Can't find it again :( Though I've found the answer for the first part: There are only five operations, using which we can express everything: operation of union, subtraction, product, projection and selection We can define an intersection as a difference of sets of tuples for instance: p(A) Intercetion q(A) = p(A) - (p(A) - s(A)), $\endgroup$ – Aldres Sep 20 '20 at 20:21
  • $\begingroup$ (In COMPUTERSCIENCE posts (and quite some places all over SE), you can use $L^AT_EX$ like $\cap$ and $\cup$ for $\cap$ and $\cup$.) $\endgroup$ – greybeard Sep 21 '20 at 7:12
  • $\begingroup$ Your "negation" doesn't make sense since that's not a relational operator. What are you trying to say? Also define "smaller". PS Please clarify via edits, not comments. Comments are ephemeral. PS There are many RAs (relational algebras). They differ in operators & even what a relation is. So when you ask about one, you need to give sufficient details. $\endgroup$ – philipxy Oct 8 '20 at 5:16

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.


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.