Information algebra

Let ${\displaystyle {\mathcal {A}}}$ be a set of symbols, called attributes (or column names). For each ${\displaystyle \alpha \in {\mathcal {A}}}$ let ${\displaystyle U_{\alpha }}$ be a non-empty set, the set of all possible values of the attribute ${\displaystyle \alpha }$. For example, if ${\displaystyle {\mathcal {A}}=\{{\texttt {name}},{\texttt {age}},{\texttt {income}}\}}$, then ${\displaystyle U_{\texttt {name}}}$ could be the set of strings, whereas ${\displaystyle U_{\texttt {age}}}$ and ${\displaystyle U_{\texttt {income}}}$ are both the set of non-negative integers.

Let ${\displaystyle x\subseteq {\mathcal {A}}}$. An ${\displaystyle x}$-tuple is a function ${\displaystyle f}$ so that ${\displaystyle {\hbox{dom}}(f)=x}$ and ${\displaystyle f(\alpha )\in U_{\alpha }}$ for each ${\displaystyle \alpha \in x}$ The set of all ${\displaystyle x}$-tuples is denoted by ${\displaystyle E_{x}}$. For an ${\displaystyle x}$-tuple ${\displaystyle f}$ and a subset ${\displaystyle y\subseteq x}$ the restriction ${\displaystyle f[y]}$ is defined to be the ${\displaystyle y}$-tuple ${\displaystyle g}$ so that ${\displaystyle g(\alpha )=f(\alpha )}$ for all ${\displaystyle \alpha \in y}$.

A relation ${\displaystyle R}$ over ${\displaystyle x}$ is a set of ${\displaystyle x}$-tuples, i.e. a subset of ${\displaystyle E_{x}}$. The set of attributes ${\displaystyle x}$ is called the domain of ${\displaystyle R}$ and denoted by ${\displaystyle d(R)}$. For ${\displaystyle y\subseteq d(R)}$ the projection of ${\displaystyle R}$ onto ${\displaystyle y}$ is defined as follows:

${\displaystyle \pi _{y}(R):=\{f[y]\mid f\in R\}.}$

The join of a relation ${\displaystyle R}$ over ${\displaystyle x}$ and a relation ${\displaystyle S}$ over ${\displaystyle y}$ is defined as follows:

${\displaystyle R\bowtie S:=\{f\mid f\quad (x\cup y){\hbox{-tuple}},\quad f[x]\in R,\;f[y]\in S\}.}$

As an example, let ${\displaystyle R}$ and ${\displaystyle S}$ be the following relations:

${\displaystyle R={\begin{matrix}{\texttt {name}}&{\texttt {age}}\\{\texttt {A}}&{\texttt {34}}\\{\texttt {B}}&{\texttt {47}}\\\end{matrix}}\qquad S={\begin{matrix}{\texttt {name}}&{\texttt {income}}\\{\texttt {A}}&{\texttt {20'000}}\\{\texttt {B}}&{\texttt {32'000}}\\\end{matrix}}}$

Then the join of ${\displaystyle R}$ and ${\displaystyle S}$ is:

${\displaystyle R\bowtie S={\begin{matrix}{\texttt {name}}&{\texttt {age}}&{\texttt {income}}\\{\texttt {A}}&{\texttt {34}}&{\texttt {20'000}}\\{\texttt {B}}&{\texttt {47}}&{\texttt {32'000}}\\\end{matrix}}}$

A relational database with natural join ${\displaystyle \bowtie }$ as combination and the usual projection ${\displaystyle \pi }$ is an information algebra. The operations are well defined since

• ${\displaystyle d(R\bowtie S)=d(R)\cup d(S)}$
• If ${\displaystyle x\subseteq d(R)}$, then ${\displaystyle d(\pi _{x}(R))=x}$.

It is easy to see that relational databases satisfy the axioms of a labeled information algebra:

semigroup

${\displaystyle (R_{1}\bowtie R_{2})\bowtie R_{3}=R_{1}\bowtie (R_{2}\bowtie R_{3})}$ and ${\displaystyle R\bowtie S=S\bowtie R}$

transitivity

If ${\displaystyle x\subseteq y\subseteq d(R)}$, then ${\displaystyle \pi _{x}(\pi _{y}(R))=\pi _{x}(R)}$.

combination

If ${\displaystyle d(R)=x}$ and ${\displaystyle d(S)=y}$, then ${\displaystyle \pi _{x}(R\bowtie S)=R\bowtie \pi _{x\cap y}(S)}$.

idempotency

If ${\displaystyle x\subseteq d(R)}$, then ${\displaystyle R\bowtie \pi _{x}(R)=R}$.

support

If ${\displaystyle x=d(R)}$, then ${\displaystyle \pi _{x}(R)=R}$.