Bag algebra is a branch of algebra that studies algebraic structures over multisets (also called bags). It provides a formal framework for operations such as bag union, bag intersection, bag sum, and scalar multiplication, often governed by laws like commutativity, associativity, and distributivity. Originally developed in the context of database theory and formal semantics, bag algebra is used to model queries that preserve duplicate information, in contrast to set-based operations. The underlying algebraic structure typically corresponds to a commutative monoid or a semiring, with applications in computer science, combinatorics, and linguistic analysis.

1 Definition and basic concepts

1.1 Multisets (bags)

A multiset is a generalization of a set that allows multiple instances of the same element. Formally, a multiset \(M\) over a universe \(U\) is a function \(\chi_M : U \to \mathbb{N}\) (where \(\mathbb{N}\) includes zero) assigning a *multiplicity* to each element. The notation \(\{a, a, b\}\) denotes a multiset with multiplicities: two copies of \(a\) and one of \(b\).

1.2 Bag cardinality and characteristic function

The cardinality of a bag \(M\) is the total number of elements counted with multiplicity: \(M= \sum_{x\in U} \chi_M(x)\). The characteristic function of a bag is precisely the multiplicity function \(\chi_M\). For a set, the characteristic function takes only values 0 or 1; for bags it can be any natural number.

1.3 Basic operations

1.3.1 Bag sum

The bag sum (or multiset sum) of two bags \(A\) and \(B\), denoted \(A \uplus B\), is defined by addition of multiplicities: \(\chi_{A \uplus B}(x) = \chi_A(x) + \chi_B(x)\). For example, \(\{a, a\} \uplus \{a, b\} = \{a, a, a, b\}\).

1.3.2 Bag union (max operation)

Bag union \(A \cup B\) takes the maximum multiplicity for each element: \(\chi_{A \cup B}(x) = \max(\chi_A(x), \chi_B(x))\). For \(\{a, a\}\) and \(\{a, b\}\), the union is \(\{a, a, b\}\).

1.3.3 Bag intersection (min operation)

Bag intersection \(A \cap B\) takes the minimum multiplicity: \(\chi_{A \cap B}(x) = \min(\chi_A(x), \chi_B(x))\). Continuing the example, the intersection of \(\{a, a\}\) and \(\{a, b\}\) is \(\{a\}\).

1.3.4 Scalar multiplication

Scalar multiplication multiplies every multiplicity of a bag by a natural number \(n\): \(\chi_{n \cdot A}(x) = n \cdot \chi_A(x)\). For instance, \(2 \cdot \{a, b\} = \{a, a, b, b\}\).

1.4 Algebraic laws

1.4.1 Commutativity and associativity

All basic operations (sum, union, intersection, scalar multiplication) commute and associate where appropriate. For instance, bag sum is commutative and associative; bag union and intersection are also commutative and associative.

1.4.2 Distributivity of sum over union

Bag sum distributes over bag union in the sense that \(A \uplus (B \cup C) = (A \uplus B) \cup (A \uplus C)\). However, note that union does not generally distribute over sum. More precisely, distributivity holds when the operations are interpreted in the semiring of natural numbers with addition and max.

2 Algebraic structures of bags

2.1 Commutative monoid under bag sum

The set of all bags over a fixed universe, together with the empty bag \(\emptyset\) (zero multiplicities) and bag sum, forms a commutative monoid. Associativity, commutativity, and the identity element (empty bag) are satisfied. This monoid is isomorphic to the direct sum of countably many copies of \(\mathbb{N}\).

2.2 Semiring structure

2.2.1 The semiring of natural numbers

The natural numbers \(\mathbb{N}\) with addition and multiplication form a semiring. Bag sum corresponds to addition, and scalar multiplication corresponds to multiplication by a natural number. Bag union and intersection correspond to max and min operations, which also form a semiring (\(\max\) as addition, \(\min\) as multiplication) known as the tropical semiring when using real numbers; here it is the \(\mathbb{N}\)-max-min semiring.

2.2.2 Bag algebra as a semiring module

Bags can be viewed as vectors over the semiring \(\mathbb{N}\). The bag algebra is a module over the semiring \(\mathbb{N}\) (or over the max-min semiring) when considering operations like linear combinations (bag sums and scalar multiplications). This perspective unifies bag operations with linear algebra.

2.3 Relationship with group theory

2.3.1 Cancellation and differences

Unlike integers, bags under sum do not allow subtraction in general because multiplicities cannot be negative. Cancellation holds: if \(A \uplus B = A \uplus C\) then \(B = C\). However, a difference operation (bag subtraction) is only defined when one bag is contained in another (i.e., each multiplicity of the subtrahend is ≤ that of the minuend). This leads to the concept of partial subtraction and the monus operation.

3 Extended operations and properties

3.1 Bag difference and complement

3.1.1 Relative difference

The relative difference (or bag difference) \(A \setminus B\) is defined when \(B \subseteq A\) (multiplicity-wise): \(\chi_{A \setminus B}(x) = \chi_A(x) - \chi_B(x)\). If the condition is not satisfied, the operation is undefined in the usual sense.

3.1.2 Monus operation

The monus (or truncated subtraction) is defined for all bags: \(\chi_{A \dot{-} B}(x) = \max(\chi_A(x) - \chi_B(x), 0)\). This yields a proper bag even when \(B\) has larger multiplicities, and corresponds to a natural ordering.

3.2 Bag ordering and lattices

3.2.1 Partial order under bag containment

A bag \(A\) is contained in bag \(B\) (written \(A \subseteq B\)) if \(\chi_A(x) \leq \chi_B(x)\) for all \(x\). This defines a partial order (not total, unless the universe is a singleton).

3.2.2 Lattice structure (union and intersection)

Under the partial order of containment, bag union (max) and bag intersection (min) give the join and meet operations. The set of all bags over a fixed universe thus forms a distributive lattice, with the empty bag as bottom and the bag with infinite multiplicities as top (if allowed; otherwise no top element for finite bags).

3.3 Bag homomorphisms

3.3.1 Preserving sum and scalar product

A bag homomorphism between two bag algebras (over possibly different universes) is a function \(f\) that commutes with bag sum and scalar multiplication: \(f(A \uplus B) = f(A) \uplus f(B)\) and \(f(k \cdot A) = k \cdot f(A)\). Such homomorphisms map bags to bags and respect the monoid structure.

3.3.2 Weight functions

A common example of a bag homomorphism is a weight function \(w : U \to \mathbb{N}\) extended linearly to bags: \(w(M) = \sum_{x} w(x) \cdot \chi_M(x)\). This maps the bag monoid to the additive monoid of \(\mathbb{N}\) and is often used in counting applications.

4 Applications

4.1 Database query evaluation

4.1.1 SQL bag semantics (multiset operations)

Relational database systems often treat query results as bags (multisets) rather than sets, because SQL’s default behaviour retains duplicates. Bag algebra provides a formal foundation for operations like UNION ALL (bag sum), INTERSECT ALL (bag intersection using min), and EXCEPT ALL (monus). It enables precise query evaluation and optimization.

4.1.2 Cost models for duplicate handling

Bag operations affect query execution cost: bag sum increases cardinality, whereas bag union may reduce it. Cost models for database optimizers incorporate bag algebra to estimate intermediate result sizes and choose efficient join orders or duplicate elimination strategies.

4.2 Formal languages and automata

4.2.1 Multiset grammars

A multiset grammar (or bag grammar) generates multisets rather than strings. Productions replace one multiset of symbols with another, and the derivation yields a multiset of terminal symbols. Such grammars are useful for modeling chemical reactions, parallel processes, and resource allocation.

4.2.2 Bag automata

Bag automata (or multiset automata) are finite automata that read multisets of symbols instead of sequences. The transition function depends on the current multiset of remaining symbols. They characterize commutative regular languages and are related to Petri nets.

4.3 Counting and combinatorics

4.3.1 Generating functions for bags

The number of bags of size \(n\) drawn from a universe of \(k\) types is given by the coefficient of \(x^n\) in \(\prod_{i=1}^k (1 - x)^{-1} = (1-x)^{-k}\). More generally, generating functions for bags use the theory of the monoid \(\mathbb{N}^k\).

4.3.2 Multiset permutations and combinations

A multiset permutation is a linear arrangement where duplicates are allowed; the number of distinct permutations of a multiset with multiplicities \(n_1, n_2, \dots\) is \(\frac{n!}{n_1! n_2! \cdots}\). Multiset combinations count selections with repetition, given by \(\binom{n+k-1}{k}\). These combinatorial objects are fundamental to bag algebra.

5.1 Fuzzy bag algebra

In fuzzy bag algebra, multiplicities are replaced by membership degrees in a fuzzy set (e.g., values in \([0,1]\)). Operations like fuzzy bag union use max of degrees, and sum uses bounded addition. This extends bag theory to model uncertainty.

5.2 Probabilistic bag algebra

Probabilistic bag algebra assigns probabilities to elements or to bags themselves. The multiplicity function becomes a random variable, and operations are defined in distribution. Applications include probabilistic databases and stochastic modeling.

5.3 Ordered and graded bags

Ordered bags and graded bags introduce an ordering or a grade (e.g., timestamps) on the copies of each element. This adds an extra dimension to the algebraic structure, connecting to sequences and vector spaces.

5.4 Connections to linear algebra and tropical geometry

Bag algebra over the tropical semiring (max-plus or min-plus) aligns with tropical geometry, where bag union corresponds to addition and bag intersection to multiplication. The semiring \(\mathbb{N}\) with addition and multiplication connects to classical linear algebra over the natural numbers (commutative monoids). Homomorphisms of bag algebras are analogous to linear maps over semirings.

6 See also

7 References

  • Blizard, W. D. (1988). Multiset theory. *Notre Dame Journal of Formal Logic*, 30(1), 36–66.
  • Grätzer, G. (2011). *Lattice Theory: Foundation*. Birkhäuser.
  • Libkin, L. (2004). *Elements of Finite Model Theory*. Springer. (Chapter on bag semantics)
  • Mac Lane, S. (1971). *Categories for the Working Mathematician*. Springer. (For monoid and semiring perspective)
  • Peterson, J. L. (1981). *Petri Net Theory and the Modeling of Systems*. Prentice-Hall. (Bag automata and multiset grammars)