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 are two-sorted algebras formula_1, where formula_2 is a semigroup, representing combination or aggregation of information, formula_3 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 formula_1, the following operations are defined
Additionally, in formula_3 the usual lattice operations (meet and join) are defined.
Axioms and definition.
The axioms of the two-sorted algebra formula_1, in addition to the axioms of the lattice formula_3:
A two-sorted algebra formula_1 satisfying these axioms is called an Information Algebra.
Order of information.
A partial order of information can be introduced by defining formula_9 if formula_10. This means that formula_11 is less informative than formula_12 if it adds no new information to formula_12. The semigroup formula_2 is a semilattice relative to this order, i.e. formula_15. Relative to any domain (question) formula_16 a partial order can be introduced by defining formula_17 if formula_18. It represents the order of information content of formula_11 and formula_12 relative to the domain (question) formula_21.
Labeled information algebra.
The pairs formula_22, where formula_23 and formula_16 such that formula_25 form a labeled Information Algebra. More precisely, in the two-sorted algebra formula_26, the following operations are defined
Models of information algebras.
Here follows an incomplete list of instances of information algebras:
Worked-out example: relational algebra.
Let formula_27 be a set of symbols, called "attributes" (or "column
names"). For each formula_28 let formula_29 be a non-empty set, the
set of all possible values of the attribute formula_30. For example, if 
formula_31, then formula_32 could
be the set of strings, whereas formula_33 and formula_34 are both
the set of non-negative integers.
Let formula_35. An "formula_21-tuple" is a function formula_37 so that
formula_38 and formula_39 for each formula_40 The set
of all formula_21-tuples is denoted by formula_42. For an formula_21-tuple formula_37 and a subset
formula_45 the restriction formula_46 is defined to be the
formula_47-tuple formula_48 so that formula_49 for all formula_50.
A "relation formula_51 over formula_21" is a set of formula_21-tuples, i.e. a subset of formula_42.
The set of attributes formula_21 is called the "domain" of formula_51 and denoted by
formula_57. For formula_58 the "projection" of formula_51 onto formula_47 is defined
as follows:
The "join" of a relation formula_51 over formula_21 and a relation formula_64 over formula_47 is
defined as follows:
As an example, let formula_51 and formula_64 be the following relations:
Then the join of formula_51 and formula_64 is:
A relational database with natural join formula_73 as combination and the usual projection formula_74 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:
Historical Roots.
The axioms for information algebras are derived from 
the axiom system proposed in (Shenoy and Shafer, 1990), see also (Shafer, 1991).