What's the difference between the Cartesian product in set theory and in relational algebra?

The Cartesian product in set theory is defined as:

$$A \times B = \{(a, b) \mid (a \in A) \land (b \in B)\}$$

I think this is exactly how it works in relational databases, but Wikipedia tries to make a difference that I don't understand:

$$ R \times S := \{ (r_1,r_2,\dots,r_n,s_1,s_2,\dots,s_m) \mid (r_1,r_2,\dots,r_n) \in R, (s_1,s_2,\dots,s_m) \in S \} $$

  • 1
    $\begingroup$ Why do you think those are the same? Why not just work through an example? A & B are sets of values, but R & S are sets of tuples of values. $\endgroup$ – philipxy May 6 '17 at 6:36
  • 1
    $\begingroup$ Relations in the relational algebra are not the ordered-tuple relations of math & "binary relations". It is a different theory. RA-style relations involve sets of n-ary tuples; frequently the tuples are unordered with tagged elements, and usually the sets are paired with headings. $\endgroup$ – philipxy May 6 '17 at 6:40

The Wikipedia definition merely "opens the parentheses". Using the pure set-theoretic definition, we would expect $$ ((r_1,r_2,\dots,r_n),(s_1,s_2,\dots,s_m)) $$ instead of $$ (r_1,r_2,\dots,r_n,s_1,s_2,\dots,s_m). $$ Assuming $R,S$ are both relations over the same universe $U$, the Wikipedia definition ensures that $R \times S$ is an $(n+m)$-ary relation over $U$. Under the set-theoretic definition, we get a binary relation over $U^n$ when $n = m$, and a unary relation over $U^n \times U^m$ in general.

We often write $U^n \times U^m = U^{n+m}$, but this isn't in general an equality of sets (it might be in some special cases, depending on the exact definition of $U^n$). Rather, we identify $U^n \times U^m$ with $U^{n+m}$, that is, we ignore the difference (this informal notion can be formalized). The difference between $R \times S$ as sets and as relations is similar – we identify the two objects although they are "physically" different.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much for your answer Yuval. I edited my question: the link to Wikipedia was wrong. I'm just learning about binary relations and I thought they are possible even when n != m (If I understand correctly and n and m are the cardinals of R and S). For example I thought this was correct: A = {2, 4} and B = {1, 2, 3, 4, 5} A binary relation "less than", R = {(2,3), (2,4), (2,5), (4,5)} Although I know about the universal set U, I get a bit lost when I read U^n So please correct me if my understanding about binary relations is wrong. $\endgroup$ – Víctor May 5 '17 at 21:58
  • 1
    $\begingroup$ Yes, it depends on the definition of relation. In many contexts we want a n $n$-ary relation to be a subset of $U^n$ for some set $U$, whereas is other contexts this is not so important. $\endgroup$ – Yuval Filmus May 5 '17 at 22:02

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.