Bogatyreva J. Multisets theory and its applications

The thesis is devoted to development of the theory of multisets and its applications. Properties of well-known operations on multisets are investigated: idempotency, commutativity, associativity, distributivity, absorption laws, monotonicity, analogs of de Morgan and double negation laws. The lattice of multisets is constructed and enclosed in two complete lattices of the multisets. The second complete lattice is obtained by generalization of the multiset concept (by allowing infinite multiplicity of elements) and is used to define denotation semantics of recursive queries of SQL-like languages. The problem of completeness for multiset primitive program algebra is solved, thereby computability on multisets is specified. The results obtained in the thesis are applicable for: specifications of tables with duplicate rows in modern databases and manipulations over such tables; defining denotation semantics of the recursive form of CTE-expressions of modern SQL-like languages; specifications of calculations on DNA in biocomputer science.