- Information algebra
Classical
information theory goes back toClaude 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 algebra s Phi,D),, where Phi, is asemigroup , representing combination or aggregation of information, D, is alattice of domains (related to questions) whosepartial order reflects the granularity of the domain or the question, and amixed 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 system s: Constraints form an information algebra Harv|Jaffar|Maher|1994.
*Semiring valued algebra s: 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 algebra s: Harv|Bergstra|Heering|Klint|1990;Harv|de Lavalette|1992.
*Linear system s: 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 thathbox{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 subsetysubseteq x, the restriction f [y] , is defined to be they,-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 byd(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::Rowtie 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= egin{matrix} exttt{name} & exttt{age} \ exttt{A} & exttt{34} \ exttt{B} & exttt{47} \ end{matrix}qquad S= egin{matrix} exttt{name} & exttt{income} \ exttt{A} & exttt{20'000} \ exttt{B} & exttt{32'000} \ end{matrix},Then the join of R, and S, is::Rowtie S= egin{matrix} exttt{name} & exttt{age} & exttt{income} \ exttt{A} & exttt{34} & exttt{20'000} \ exttt{B} & exttt{47} & exttt{32'000} \ end{matrix},A relational database with natural join owtie, as combination and the usual projection pi, is an information algebra.The operations are well defined since
- d(Rowtie S)=d(R)cup d(S),
- If xsubseteq d(R),, then d(pi_x(R))=x,.
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.htmlHarvard 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
Wikimedia Foundation. 2010.