Information Algebra Article Index for
Information 		Website Links For
Information 		 

Information About

Information Algebra
  CATEGORIES ABOUT INFORMATION ALGEBRA
   
algebraic information theory
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



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 Algebra s (\Phi,D)\,, where \Phi\, is a Semigroup , representing combination or aggregation of information, D\, is a Lattice of Domain s (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


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

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


MODELS OF INFORMATION ALGEBRAS


Here follows an incomplete list of instances of information algebras:
  • .

  • Constraint System s: Constraints form an information algebra .

  • Semiring Valued Algebra s: 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 Algebra s: ;.

  • Linear System s: 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 \alpha\in{\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}= \{ exttt{name}, exttt{age}, exttt{income}\}\,, then U_{ exttt{name}}\, could
be the set of strings, whereas U_{ exttt{age}}\, and U_{ exttt{income}}\, are both
the set of non-negative integers.

Let x\subseteq{\mathcal A}\,. An x\,-tuple is a function f\, so that
\hbox{dom}(f)=x\, and f(\alpha)\in U_\alpha\, for each \alpha\in x\, The set
of all x\,-tuples is denoted by E_x\,. For an x\,-tuple f\, and a subset
y\subseteq x\, the restriction f {Link without Title} \, is defined to be the
y\,-tuple g\, so that g(\alpha)=f(\alpha)\, for all \alpha\in 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 y\subseteq d(R)\, the projection of R\, onto y\, is defined
as follows:
:\pi_y(R):=\{f {Link without Title} \mid f\in R\}.\,
The join of a relation R\, over x\, and a relation S\, over y\, is
defined as follows:
:R\bowtie S:=\{f\mid f \quad (x\cup y)\hbox{-tuple},\quad f {Link without Title} \in R,
\;f {Link without Title} \in S\}.\,
As an example, let R\, and S\, be the following relations:
:R=
\begin{matrix}
exttt{name} & exttt{age} \
exttt{A} & exttt{34} \
exttt{B} & exttt{47} \
\end{matrix}\qquad
S=
\begin{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:
:R\bowtie S=
\begin{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 \bowtie\, as combination and the usual projection \pi\, is an information algebra.
The operations are well defined since

  • d(R\bowtie S)=d(R)\cup d(S)\,

  • If x\subseteq 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_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 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 : ...


HISTORICAL ROOTS

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


REFERENCES


  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












  Sophia-Antipolis, France, June 27-29, 1984, Proceedings Volume 173 of Lec-


  {{Harvard Reference Given1 S L Surname1= Lauritzen Given2=D JSurname2=Spiegelhalter Title=Local computations with probabilities on graphical structures and their application to expert systems Journal= J Royal


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


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


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