Unique prime Cartesian factorisation of a relation
Let 1 denote the relation DEE which represents the identity for Cartesian product. A prime relation is a non-empty relation not equal to 1 which can only be Cartesian-factorised into 1 and itself.
A prime relation is analogous to a prime number, including the notion of a unique prime factorisation.
In number theory, the unique prime factorisation of the integers greater than
0 is such an important theorem that it is referred to as the
Fundamental theorem of arithmetic [
].
Theorem: every non-empty relation R has a unique prime Cartesian factorisation:
\(R = R_1 ⨯ R_2 ⨯ ... ⨯ R_n\)
\(R_1,...,R_n\) are the prime factors of \(R\). If \(R\) is infinite then at least one of the prime factors is infinite.
In the following example \(R_1\) and \(R_2\) are the prime factors of \(R\).
| \(R\) | \(=\) | \(R_1\) | \(⨯\) | \(R_2\) | ||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
No equivalent for natural join
It's clear that this doesn't apply to joins (even though join generalises Cartesian product and is also commutative and associative and has identity DEE). For example, the fact that \(r⋈r = r\) is a showstopper. By contrast, Cartesian product forces the factors to be "smaller" because the factors involve a partitioning of the set of attributes, and it is noteworthy that something along these lines is used in Euclid's proof that there exists a prime factorisation of any integer. However the proof assumes integers are well-ordered which doesn't apply to relations, so the proof doesn't apply as written.
Proof
The proof is reasonably complex. It makes use of many properties of the relational algebra, and the fact that the naturals are well-ordered. There is a proof that a prime factorisation exists and a proof that it is unique if it exists.