Information algebra

Axioms and definition

The axioms of the two-sorted algebra ${\displaystyle (\mathrm{\Phi },D)}$, in addition to the axioms of the lattice ${\displaystyle D}$:

A two-sorted algebra ${\displaystyle (\mathrm{\Phi },D)}$ satisfying these axioms is called an Information Algebra.

Order of information

A partial order of information can be introduced by defining ${\displaystyle \varphi \le \psi }$ if ${\displaystyle \varphi \otimes \psi =\psi }$. This means that ${\displaystyle \varphi }$ is less informative than ${\displaystyle \psi }$ if it adds no new information to ${\displaystyle \psi }$. The semigroup ${\displaystyle \mathrm{\Phi }}$ is a semilattice relative to this order, i.e. ${\displaystyle \varphi \otimes \psi =\varphi \vee \psi }$. Relative to any domain (question) ${\displaystyle x\in D}$ a partial order can be introduced by defining ${\displaystyle \varphi {\le }_x\psi }$ if ${\displaystyle {\varphi }^{\Rightarrow x}\le {\psi }^{\Rightarrow x}}$. It represents the order of information content of ${\displaystyle \varphi }$ and ${\displaystyle \psi }$ relative to the domain (question) ${\displaystyle x}$.

Labeled information algebra

The pairs ${\displaystyle (\varphi ,x)}$, where ${\displaystyle \varphi \in \mathrm{\Phi }}$ and ${\displaystyle x\in D}$ such that ${\displaystyle {\varphi }^{\Rightarrow x}=\varphi }$ form a labeled Information Algebra. More precisely, in the two-sorted algebra ${\displaystyle (\mathrm{\Phi },D)}$, the following operations are defined

Models of information algebras

Here follows an incomplete list of instances of information algebras:

• Relational algebra: The reduct of a relational algebra with natural join as combination and the usual projection is a labeled information algebra, see Example.
• Constraint systems: Constraints form an information algebra (Jaffar & Maher 1994).
• Semiring valued algebras: C-Semirings induce information algebras (Bistarelli, Montanari & Rossi1997);(Bistarelli et al. 1999);(Kohlas & Wilson 2006).
• Logic: Many logic systems induce information algebras (Wilson & Mengin 1999). Reducts of cylindric algebras (Henkin, Monk & Tarski 1971) or polyadic algebras are information algebras related to predicate logic (Halmos 2000).
• Module algebras: (Bergstra, Heering & Klint 1990);(de Lavalette 1992).
• Linear systems: Systems of linear equations or linear inequalities induce information algebras (Kohlas 2003).

Worked-out example: relational 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 α. For example, if ${\displaystyle \mathcal{A}=\{\text{name},\text{age},\text{income}\}}$, then ${\displaystyle U_{\text{name}}}$ could be the set of strings, whereas ${\displaystyle U_{\text{age}}}$ and ${\displaystyle U_{\text{income}}}$ are both the set of non-negative integers.

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

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

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

The join of a relation R over x and a relation S over y is defined as follows:

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

As an example, let R and S be the following relations:

${\displaystyle R=\begin{array}{|cc|}\hline \text{name}& \text{age}\\ \text{A}& \text{34}\\ \text{B}& \text{47}\\ \hline\end{array}S=\begin{array}{|cc|}\hline \text{name}& \text{income}\\ \text{A}& \text{20,000}\\ \text{B}& \text{32,000}\\ \hline\end{array}}$

Then the join of R and S is:

${\displaystyle R\bowtie S=\begin{array}{|ccc|}\hline \text{name}& \text{age}& \text{income}\\ \text{A}& \text{34}& \text{20,000}\\ \text{B}& \text{47}& \text{32,000}\\ \hline\end{array}}$

A relational database with natural join ${\displaystyle \bowtie }$ as combination and the usual projection π 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}$.

Connections

Valuation algebras

Dropping the idempotency axiom leads to valuation algebras. These axioms have been introduced by (Shenoy & Shafer 1990) to generalize local computation schemes (Lauritzen & Spiegelhalter 1988) from Bayesian networks to more general formalisms, including belief function, possibility potentials, etc. (Kohlas & Shenoy 2000). For a book-length exposition on the topic see Pouly & Kohlas (2011).

Domains and information systems

Compact Information Algebras (Kohlas 2003) are related to Scott domains and Scott information systems (Scott 1970);(Scott 1982);(Larsen & Winskel 1984).

Uncertain information

Random variables with values in information algebras represent probabilistic argumentation systems (Haenni, Kohlas & Lehmann 2000).

Semantic information

Information algebras introduce semantics by relating information to questions through focusing and combination (Groenendijk & Stokhof 1984);(Floridi 2004).

Information flow

Information algebras are related to information flow, in particular classifications (Barwise & Seligman 1997).

Tree decomposition

Information algebras are organized into a hierarchical tree structure, and decomposed into smaller problems.

Semigroup theory

...

Compositional models

Such models may be defined within the framework of information algebras: https://arxiv.org/abs/1612.02587

Extended axiomatic foundations of information and valuation algebras

The concept of conditional independence is basic for information algebras and a new axiomatic foundation of information algebras, based on conditional independence, extending the old one (see above) is available: https://arxiv.org/abs/1701.02658

Historical Roots

The axioms for information algebras are derived from the axiom system proposed in (Shenoy and Shafer, 1990), see also (Shafer, 1991).