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 Harv|Kohlas|2003 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

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 .
*Constraint systems: Constraints form an information algebra Harv|Jaffar|Maher|1994.
*Semiring valued algebras: C-Semirings induce information algebras Harv|Bistarelli|Montanari|Rossi1997;Harv|Bistarelli|Fargier|Montanari|Rossi|Schiex|Verfaillie|1999;Harv|Kohlas|Wilson|2006.
*Logic: Many logic systems induce information algebras Harv|Wilson|Mengin|1999. Reducts of cylindrical algebras Harv|Henkin|Monk|Tarski|1971 or polyadic algebras are information algebras related to predicate logic Harv|Halmos|2000.
*Module algebras: Harv|Bergstra|Heering|Klint|1990;Harv|de Lavalette|1992.
*Linear systems: Systems of linear equations or linear inequalities induce information algebras Harv|Kohlas|2003.

Worked-out Example: Relational Algebra

Let $\{mathcal\; A\},$ be a set of symbols, called attributes (or columnnames). For each $alphain\{mathcal\; A\},$ let $U\_alpha,$ be a non-empty set, theset of all possible values of the attribute $alpha,$. For example, if $\{mathcal\; A\}=\; \{\; exttt\{name\},\; exttt\{age\},\; exttt\{income\}\},$, then $U\_\{\; exttt\{name,$ couldbe the set of strings, whereas $U\_\{\; exttt\{age,$ and $U\_\{\; exttt\{income,$ are boththe 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 setof 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 definedas follows::$pi\_y(R):=\{f\; [y]\; mid\; fin\; R\}.,$The join of a relation $R,$ over $x,$ and a relation $S,$ over $y,$ isdefined as follows::As an example, let $R,$ and $S,$ be the following relations::Then the join of $R,$ and $S,$ is::A relational database with natural join as combination and the usual projection $pi,$ is an information algebra.The operations are well defined since

• If $xsubseteq\; d(R),$, then $d(pi\_x(R))=x,$.

It is easy to see that relational databases satisfy the axioms of a labeledinformation algebra:; semigroup : and ; 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 .; idempotency : If $xsubseteq\; d(R),$, then .; 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 Harv|Shenoy|Shafer|1990 to generalize "local computation schemes" Harv|Lauritzen|Spiegelhalter|1988 from Bayesian networks to more general formalisms (including belief function, possibility potentials, etc.) Harv|Kohlas |Shenoy|2000.; Domains and Information Systems: "Compact Information Algebras" Harv|Kohlas|2003 are related to Scott domains and Scott information systems Harv|Scott|1970;Harv|Scott|1982;Harv|Larsen|Winskel|1984.; Uncertain Information : Random variables with values in information algebras represent "probabilistic argumentation systems" Harv|Haenni|Kohlas|Lehmann|2000.; Semantic Information : Information algebras introduce semantics by relating information to questions through focusing and combination Harv|Groenendijk|Stokhof|1984;Harv|Floridi|2004.; Information Flow : Information algebras are related to information flow, in particular classifications Harv|Barwise|Seligman|1997.; 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).

References

Harvard reference | Given=Gerard R. Renardel | Surname=de Lavalette | Chapter= Logical semantics of modularisation | Editor=Egon Börger, Gerhard Jäger, Hans Kleine Büning, and Michael M. Richter | Title=CSL: 5th Workshop on Computer Science Logic | Pages=306–315 | Publisher=Volume 626 of Lecture Notes in Computer Science, Springer | Year=1992 | ISBN=3-540-55789-X
URL=http://citeseer.ist.psu.edu/484529.html

Harvard reference | Given1=K. G. | Surname1=Larsen | Given2=G. |Surname2=Winskel | Chapter=Using information systems to solve recursive domain equations effectively | Editor=Gilles Kahn, David B. MacQueen, and Gordon D. Plotkin | Title=Semantics of Data Types, International Symposium, Sophia-Antipolis, France, June 27-29, 1984, Proceedings | Volume=173 of Lec- ture Notes in Computer Science | Pages=109–129 | Location=Berlin | Year= 1984 | Publisher=Springer

Harvard reference | Given1=S. L. | Surname1= Lauritzen |Given2=D. J.|Surname2=Spiegelhalter | Title=Local computations with probabilities on graphical structures and their application to expert systems | Journal= J. Royal Statis. Soc. B |Volume= 50 | Pages=157–224 | Year= 1988

Harvard reference | Given=Dana S. | Surname= Scott | Title= Outline of a mathematical theory of computation | Publisher=Technical Monograph PRG–2, Oxford University Computing Laboratory, Programming Research Group | Year=1970

Harvard reference | Given1=P. P. | Surname1=Shenoy | Given2=G. | Surname2=Shafer | Chapter=Axioms for probability and belief-function proagation | Editor=Ross D. Shachter, Tod S. Levitt, Laveen N. Kanal, and John F. Lemmer | Title= Uncertainty in Artificial Intelligence 4 | Volume= 9 | Journal= Machine intelligence and pattern recognition |Pages = 169–198 | Place=Amsterdam | Year= 1990 | Publisher=Elsevier | ISBN= 0-444-88650-8

Harvard reference | Given1=Nic | Surname1=Wilson |Given2= Jérôme | Surname2= Mengin | Chapter=Logical deduction using the local computation framework | Editor=Anthony Hunter and Simon Parsons, | Title=Symbolic and Quantitative Approaches to Reasoning and Uncertainty, European Confer- ence, ECSQARU’99, London, UK, July 5-9, 1999, Proceedings, volume 1638 of Lecture Notes in Computer Science | Pages= 386–396 | Publisher= Springer | Year= 1999 | ISBN = 3-540-66131-X | URL = http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=1638&spage=0386