Maximal decomposition of information

Let ${\displaystyle S}$ be a relational database schema.

${\displaystyle C\left(S\right)}$ (the extension of the database constraint) can be regarded as a non-empty relation so we can consider its unique prime Cartesian factorisation.

Claim: For any schema ${\displaystyle S}$ there exists a schema ${\displaystyle S\prime }$ which is information equivalent to ${\displaystyle S}$ where the cardinality of every finite prime Cartesian factor of ${\displaystyle C(S\prime )}$ is a prime number.

This implies the bag of integers which are the cardinalities of the prime Cartesian factors of ${\displaystyle C(S\prime )}$ equals the bag of prime number factors of ${\displaystyle \left|C\left(S\right)\right|}$.

Note that the bag of prime number factors of any positive integer is uniquely determined, by the Fundamental theorem of arithmetic [].

${\displaystyle S\prime }$ represents a schema having maximal decomposition - i.e. into the most parts which can be updated independently.

Proof

The following is an outline of a constructive existential proof which involves relational expressions for each relvar in ${\displaystyle S\prime }$ that are defined in terms of the relvars of ${\displaystyle S}$:

Let ${\displaystyle F_1,...,F_n}$ be the prime number factors of ${\displaystyle N=\left|C\left(S\right)\right|}$ (the order doesn't matter)

Let the ${\displaystyle N}$ database values in ${\displaystyle C\left(S\right)}$ be organised into an ${\displaystyle n}$ dimensional array of size ${\displaystyle \prod _{j=1}^n{F}_j=N}$ (again, the order doesn't matter).

For ${\displaystyle j}$ in ${\displaystyle 1..n}$ and ${\displaystyle i}$ in ${\displaystyle 1..Fj}$, let ${\displaystyle B_{ij}}$ denote the subset of ${\displaystyle C\left(S\right)}$ corresponding to the set of database values in the ith slice of the jth component of the n-dimensional array (a slice has ${\displaystyle n-1}$ dimensions).

For ${\displaystyle j}$ in ${\displaystyle 1..n}$ and ${\displaystyle i}$ in ${\displaystyle 1..F_j}$, let ${\displaystyle T_{ij}=\bigcup \{matches\left(d\right)\mid d\in B_{ij}\}}$ where ${\displaystyle matches\left(d\right)}$ evaluates to DEE if the dbvar for schema ${\displaystyle S}$ has value ${\displaystyle d}$, otherwise DUM. See how it can be defined here.

Note that ${\displaystyle T_{ij}}$ evaluates to DEE if the value of the dbvar for ${\displaystyle S}$ is in slice ${\displaystyle B_{ij}}$, otherwise DUM.

Let ${\displaystyle x}$ be some attribute name. For ${\displaystyle j}$ in ${\displaystyle 1..n}$, let schema ${\displaystyle S\prime }$ have relvar ${\displaystyle R_j\prime }$ which is defined in terms of the relvars of ${\displaystyle S}$ using the expression

${\displaystyle R_j\prime =\bigcup \{T_{ij}\bowtie }$ REL { TUP { (${\displaystyle x}$ ${\displaystyle i}$) } }${\displaystyle \mid i\in 1..F_j\}}$

(this expression evaluates to REL { TUP { (${\displaystyle x}$ ${\displaystyle i}$) } } where the dbvar of ${\displaystyle S}$ is in slice ${\displaystyle B_{ij}}$)

Note that for every database value each relvar ${\displaystyle R_j\prime }$ of ${\displaystyle S\prime }$ has exactly one tuple with one attribute. This follows because any database value (i.e. element of ${\displaystyle C\left(S\right)}$) lies in exactly one slice of the jth coordinate. The UNION over the JOINs picks out exactly one of the TUP { (${\displaystyle x}$ ${\displaystyle i}$) }. There are ${\displaystyle F_j}$ slices for the jth component and hence ${\displaystyle F_j}$ possible values of ${\displaystyle R_j\prime }$.

It is easy to see that a combination of the values of the ${\displaystyle R_j\prime }$ corresponds to one of the elements of the n-dimensional array and hence to one of the database values in ${\displaystyle C\left(S\right)}$.

Example 1

Let there be three lights coloured red, green and blue which can be on or off. There are ${\displaystyle 2^3=8}$ world situations which need to be recorded.

Let schema ${\displaystyle S_1}$ have a single relvar with the predicate: The light with colour [COLOUR] is on.

Let schema ${\displaystyle S_2}$ have three relvars with the following predicates:

1. The red light is on.
2. The green light is on.
3. The blue light is on.

${\displaystyle S_1}$ and ${\displaystyle S_2}$ are information equivalent. ${\displaystyle S_2}$ is an example of a schema with maximal decomposition.

Example 2

Let there be three lights coloured red, green and blue which can be on or off, except they cannot be all off or all on. There are ${\displaystyle 6}$ world situations which need to be recorded.

The prime factorisation of ${\displaystyle 6}$ is ${\displaystyle 2\times 3}$. A maximally decomposed schema can be achieved with the following two predicates:

1. A single light is on.
2. The light with colour [COLOUR] is the only light in its state.

Example 3

See maximal decompositon of two monadic relations with an IND constraint.