# Information algebra

The term "information algebra" refers to mathematical techniques of information processing. Classical information theory goes back to Claude Shannon. It is a theory of information transmission, looking at communication and storage. However, it has not been considered so far that information comes from different sources and that it is therefore usually combined. It has furthermore been neglected in classical information theory that one wants to extract those parts out of a piece of information that are relevant to specific questions.

A mathematical phrasing of these operations leads to an algebra of information, describing basic modes of information processing. Such an algebra involves several formalisms of computer science, which seem to be different on the surface: relational databases, multiple systems of formal logic or numerical problems of linear algebra. It allows the development of generic procedures of information processing and thus a unification of basic methods of computer science, in particular of distributed information processing.

Information relates to precise questions, comes from different sources, must be aggregated, and can be focused on questions of interest. Starting from these considerations, information algebras Template:Harv are two-sorted algebras $(\Phi ,D)\,$ , where $\Phi \,$ is a semigroup, representing combination or aggregation of information, $D\,$ is a lattice of domains (related to questions) whose partial order reflects the granularity of the domain or the question, and a mixed operation representing focusing or extraction of information.

## Information and its operations

More precisely, in the two-sorted algebra $(\Phi ,D)\,$ , the following operations are defined

Additionally, in $D\,$ the usual lattice operations (meet and join) are defined.

## Axioms and definition

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

## Models of information algebras

Here follows an incomplete list of instances of information algebras:

### Worked-out example: relational algebra

$\pi _{y}(R):=\{f[y]\mid f\in R\}.\,$ $R\bowtie S:=\{f\mid f\quad (x\cup y){\hbox{-tuple}},\quad f[x]\in R,\;f[y]\in S\}.\,$ $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}}\,$ $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 $\bowtie \,$ as combination and the usual projection $\pi \,$ is an information algebra. The operations are well defined since

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

semigroup
$(R_{1}\bowtie R_{2})\bowtie R_{3}=R_{1}\bowtie (R_{2}\bowtie R_{3})\,$ and $R\bowtie S=S\bowtie R\,$ transitivity
If $x\subseteq y\subseteq d(R)\,$ , then $\pi _{x}(\pi _{y}(R))=\pi _{x}(R)\,$ .
combination
If $d(R)=x\,$ and $d(S)=y\,$ , then $\pi _{x}(R\bowtie S)=R\bowtie \pi _{x\cap y}(S)\,$ .
idempotency
If $x\subseteq d(R)\,$ , then $R\bowtie \pi _{x}(R)=R\,$ .
support
If $x=d(R)\,$ , then $\pi _{x}(R)=R\,$ .

## Connections

Valuation algebras
Dropping the idempotency axiom leads to valuation algebras. These axioms have been introduced by Template:Harv to generalize local computation schemes Template:Harv from Bayesian networks to more general formalisms, including belief function, possibility potentials, etc. Template:Harv. For a book-length exposition on the topic see Template:Harvtxt.
Domains and information systems
Compact Information Algebras Template:Harv are related to Scott domains and Scott information systems Template:Harv;Template:Harv;Template:Harv.
Uncertain information
Random variables with values in information algebras represent probabilistic argumentation systems Template:Harv.
Semantic information
Information algebras introduce semantics by relating information to questions through focusing and combination Template:Harv;Template:Harv.
Information flow
Information algebras are related to information flow, in particular classifications Template:Harv.
Tree decomposition
...
Semigroup theory
...

## Historical Roots

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