Dictionary Thesaurus Word Dynamo Quotes Reference Translator Spanish

Information algebra

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 grasps a lot of 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 algebra

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 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

Combination :

otimes: Phi otimes Phi rightarrow Phi,~ (phi,psi) mapsto phi otimes psi,

Focussing :

Rightarrow: Phi otimes D rightarrow Phi,~ (phi,x) mapsto phi^{Rightarrow x},

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

Axioms and definition

The axioms of the two-sorted algebra $(Phi,D),$ , in addition to the axioms of the lattice $D,$ :

Semigroup :

Phi,

is a commutative semigroup under combination with a neutral element (representing vacuous information). Distributivity of Focusing over Combination :

(phi^{Rightarrow x} otimes psi)^{Rightarrow x} = phi^{Rightarrow x} otimes psi^{Rightarrow x},

To focus an information on

x,

combined with another information to domain

x,

, one may as well first focus the second information to

x,

and combine then. Transitivity of Focusing :

(phi^{Rightarrow x})^{Rightarrow y} = phi^{Rightarrow x wedge y},

To focus an information on

x,

and

y,

, one may focus it to

x wedge y,

. Idempotency :

phi otimes phi^{Rightarrow x} = phi,

An information combined with a part of itself gives nothing new. Support :

forall phi in Phi,~ exists x in D,

such that

phi = phi^{Rightarrow x},

Each information refers to at least one domain (question).

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

Order of information

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

Labeled information algebra

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

Labeling :

d(phi,x) = x ,

Combination :

(phi,x) otimes (psi,y) = (phi otimes psi,x vee y)~~~~,

Projection :

(phi,x)^{downarrow y} = (phi^{Rightarrow y},y),

for

y leq x,

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 .
Semiring valued algebras: C-Semirings induce information algebras ;;.
Logic: Many logic systems induce information algebras . Reducts of cylindrical algebras or polyadic algebras are information algebras related to predicate logic .
Module algebras: ;.
Linear systems: Systems of linear equations or linear inequalities induce information algebras .

Worked-out Example: Relational Algebra

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

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

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

pi_y(R):={f[y]mid fin R}.,

The join of a relation

R,

over

x,

and a relation

S,

over

y,

is defined as follows:

Rbowtie S:={fmid f quad (xcup y)hbox{-tuple},quad f[x]in R,

;f[y]in S}., As an example, let

R,

and

S,

be the following relations:

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

R,

and

S,

is:

Rbowtie 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

$d(Rbowtie S)=d(R)cup d(S),$
If $xsubseteq d(R),$ , then $d(pi_x(R))=x,$ .

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

(R_1bowtie R_2)bowtie R_3=R_1bowtie(R_2bowtie R_3),

and

Rbowtie S=Sbowtie R,

transitivity : If

xsubseteq ysubseteq d(R),

, then

pi_x(pi_y(R))=pi_x(R),

. combination : If

d(R)=x,

and

d(S)=y,

, then

pi_x(Rbowtie S)=Rbowtiepi_{xcap y}(S),

. idempotency : If

xsubseteq d(R),

, then

Rbowtiepi_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 to generalize local computation schemes from Bayesian networks to more general formalisms (including belief function, possibility potentials, etc.) . Domains and Information Systems: Compact Information Algebras are related to Scott domains and Scott information systems ;;. Uncertain Information : Random variables with values in information algebras represent probabilistic argumentation systems . Semantic Information : Information algebras introduce semantics by relating information to questions through focusing and combination ;. Information Flow : Information algebras are related to information flow, in particular classifications . Tree decomposition : ... Semigroup theory : ...