More precisely, in the two-sorted algebra ${\displaystyle (\Phi ,D)}$ , the following operations are defined

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

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

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

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

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

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 (Jaffar & Maher 1994).
• Semiring valued algebras: C-Semirings induce information algebras (Bistarelli, Montanari & Rossi1997);(Bistarelli et al. 1999);(Kohlas & Wilson 2006).
• Logic: Many logic systems induce information algebras (Wilson & Mengin 1999). Reducts of cylindric algebras (Henkin, Monk & Tarski 1971) or polyadic algebras are information algebras related to predicate logic (Halmos 2000).
• Module algebras: (Bergstra, Heering & Klint 1990);(de Lavalette 1992).
• Linear systems: Systems of linear equations or linear inequalities induce information algebras (Kohlas 2003).

Worked-out example: relational algebra edit

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

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

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

${\displaystyle \pi _{y}(R):=\{f[y]\mid f\in R\}.}$ 

The join of a relation ${\displaystyle R}$  over ${\displaystyle x}$  and a relation ${\displaystyle S}$  over ${\displaystyle y}$  is defined as follows:

${\displaystyle R\bowtie S:=\{f\mid f\quad (x\cup y){\hbox{-tuple}},\quad f[x]\in R,\;f[y]\in S\}.}$ 

As an example, let ${\displaystyle R}$  and ${\displaystyle S}$  be the following relations:

${\displaystyle 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 ${\displaystyle R}$  and ${\displaystyle S}$  is:

${\displaystyle R\bowtie 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 ${\displaystyle \bowtie }$  as combination and the usual projection ${\displaystyle \pi }$  is an information algebra. The operations are well defined since

• ${\displaystyle d(R\bowtie S)=d(R)\cup d(S)}$ 
• If ${\displaystyle x\subseteq d(R)}$ , then ${\displaystyle d(\pi _{x}(R))=x}$ .

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

semigroup

${\displaystyle (R_{1}\bowtie R_{2})\bowtie R_{3}=R_{1}\bowtie (R_{2}\bowtie R_{3})}$  and ${\displaystyle R\bowtie S=S\bowtie R}$ 

transitivity

If ${\displaystyle x\subseteq y\subseteq d(R)}$ , then ${\displaystyle \pi _{x}(\pi _{y}(R))=\pi _{x}(R)}$ .

combination

If ${\displaystyle d(R)=x}$  and ${\displaystyle d(S)=y}$ , then ${\displaystyle \pi _{x}(R\bowtie S)=R\bowtie \pi _{x\cap y}(S)}$ .

idempotency

If ${\displaystyle x\subseteq d(R)}$ , then ${\displaystyle R\bowtie \pi _{x}(R)=R}$ .

support

If ${\displaystyle x=d(R)}$ , then ${\displaystyle \pi _{x}(R)=R}$ .

Valuation algebras

Dropping the idempotency axiom leads to valuation algebras. These axioms have been introduced by (Shenoy & Shafer 1990) to generalize local computation schemes (Lauritzen & Spiegelhalter 1988) from Bayesian networks to more general formalisms, including belief function, possibility potentials, etc. (Kohlas & Shenoy 2000). For a book-length exposition on the topic see Pouly & Kohlas (2011).

Domains and information systems

Compact Information Algebras (Kohlas 2003) are related to Scott domains and Scott information systems (Scott 1970);(Scott 1982);(Larsen & Winskel 1984).

Uncertain information

Random variables with values in information algebras represent probabilistic argumentation systems (Haenni, Kohlas & Lehmann 2000).

Semantic information

Information algebras introduce semantics by relating information to questions through focusing and combination (Groenendijk & Stokhof 1984);(Floridi 2004).

Information flow

Information algebras are related to information flow, in particular classifications (Barwise & Seligman 1997).

Tree decomposition

Information algebras are organized into a hierarchical tree structure, and decomposed into smaller problems.

Semigroup theory

...

Compositional models

Such models may be defined within the framework of information algebras: https://arxiv.org/abs/1612.02587

Extended axiomatic foundations of information and valuation algebras

The concept of conditional independence is basic for information algebras and a new axiomatic foundation of information algebras, based on conditional independence, extending the old one (see above) is available: https://arxiv.org/abs/1701.02658

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

• Barwise, J.; Seligman, J. (1997), Information Flow: The Logic of Distributed Systems, Cambridge U.K.: Number 44 in Cambridge Tracts in Theoretical Computer Science, Cambridge University Press
• Bergstra, J.A.; Heering, J.; Klint, P. (1990), "Module algebra", Journal of the ACM, 73 (2): 335–372, doi:10.1145/77600.77621, S2CID 7910431
• Bistarelli, S.; Fargier, H.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G. (1999), "Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison", Constraints, 4 (3): 199–240, doi:10.1023/A:1026441215081, S2CID 17232456, archived from the original on March 10, 2022
• Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca (1997), "Semiring-based constraint satisfaction and optimization", Journal of the ACM, 44 (2): 201–236, CiteSeerX 10.1.1.45.5110, doi:10.1145/256303.256306, S2CID 4003767
• de Lavalette, Gerard R. Renardel (1992), "Logical semantics of modularisation", in Egon Börger; Gerhard Jäger; Hans Kleine Büning; Michael M. Richter (eds.), CSL: 5th Workshop on Computer Science Logic, Volume 626 of Lecture Notes in Computer Science, Springer, pp. 306–315, ISBN 978-3-540-55789-0
• Floridi, Luciano (2004), "Outline of a theory of strongly semantic information" (PDF), Minds and Machines, 14 (2): 197–221, doi:10.1023/b:mind.0000021684.50925.c9, S2CID 3058065
• Groenendijk, J.; Stokhof, M. (1984), Studies on the Semantics of Questions and the Pragmatics of Answers, PhD thesis, Universiteit van Amsterdam
• Haenni, R.; Kohlas, J.; Lehmann, N. (2000), "Probabilistic argumentation systems" (PDF), in J. Kohlas; S. Moral (eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, Dordrecht: Volume 5: Algorithms for Uncertainty and Defeasible Reasoning, Kluwer, pp. 221–287, archived from the original on January 25, 2005
• Halmos, Paul R. (2000), "An autobiography of polyadic algebras", Logic Journal of the IGPL, 8 (4): 383–392, doi:10.1093/jigpal/8.4.383, S2CID 36156234
• Henkin, L.; Monk, J. D.; Tarski, A. (1971), Cylindric Algebras, Amsterdam: North-Holland, ISBN 978-0-7204-2043-2
• Jaffar, J.; Maher, M. J. (1994), "Constraint logic programming: A survey", Journal of Logic Programming, 19/20: 503–581, doi:10.1016/0743-1066(94)90033-7
• Kohlas, J. (2003), Information Algebras: Generic Structures for Inference, Springer-Verlag, ISBN 978-1-85233-689-9
• Kohlas, J.; Shenoy, P.P. (2000), "Computation in valuation algebras", in J. Kohlas; S. Moral (eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning, Dordrecht: Kluwer, pp. 5–39
• Kohlas, J.; Wilson, N. (2006), Exact and approximate local computation in semiring-induced valuation algebras (PDF), Technical Report 06-06, Department of Informatics, University of Fribourg, archived from the original on September 24, 2006
• Larsen, K. G.; Winskel, G. (1984), "Using information systems to solve recursive domain equations effectively", in Gilles Kahn; David B. MacQueen; Gordon D. Plotkin (eds.), Semantics of Data Types, International Symposium, Sophia-Antipolis, France, June 27–29, 1984, Proceedings, vol. 173 of Lecture Notes in Computer Science, Berlin: Springer, pp. 109–129
• Lauritzen, S. L.; Spiegelhalter, D. J. (1988), "Local computations with probabilities on graphical structures and their application to expert systems", Journal of the Royal Statistical Society, Series B, 50: 157–224
• Pouly, Marc; Kohlas, Jürg (2011), Generic Inference: A Unifying Theory for Automated Reasoning, John Wiley & Sons, ISBN 978-1-118-01086-0
• Scott, Dana S. (1970), Outline of a mathematical theory of computation, Technical Monograph PRG–2, Oxford University Computing Laboratory, Programming Research Group
• Scott, D.S. (1982), "Domains for denotational semantics", in M. Nielsen; E.M. Schmitt (eds.), Automata, Languages and Programming, Springer, pp. 577–613
• Shafer, G. (1991), An axiomatic study of computation in hypertrees, Working Paper 232, School of Business, University of Kansas
• Shenoy, P. P.; Shafer, G. (1990). "Axioms for probability and belief-function proagation". In Ross D. Shachter; Tod S. Levitt; Laveen N. Kanal; John F. Lemmer (eds.). Uncertainty in Artificial Intelligence 4. Vol. 9. Amsterdam: Elsevier. pp. 169–198. doi:10.1016/B978-0-444-88650-7.50019-6. hdl:1808/144. ISBN 978-0-444-88650-7. {{cite book}}: |journal= ignored (help)
• Wilson, Nic; Mengin, Jérôme (1999), "Logical deduction using the local computation framework", in Anthony Hunter; Simon Parsons (eds.), Symbolic and Quantitative Approaches to Reasoning and Uncertainty, European Conference, ECSQARU'99, London, UK, July 5–9, 1999, Proceedings, volume 1638 of Lecture Notes in Computer Science, Springer, pp. 386–396, ISBN 978-3-540-66131-3