Relationship between Extended Table Algebra of Infinite Tables and Extended Multiset Table Algebra

Abstract

The paper is focused on some theoretical questions of the table databases. The methodological basis of the research is a compositional approach to programming, the core of which is to consider special algebras. Two mathematical formalisms such as extended table algebra of infinite tables and extended multiset table algebra are considered. Their signatures are supplemented by additional operations such as inner and outer joins, semijoin and aggregate operations. Basic definitions referring to these formalisms are given.

This article deals with the topic of the relationship between extended table algebra of infinite tables and extended multiset table algebra. Taking into consideration the fact that the first component of a table of extended table algebra of infinite tables is a set of tuples, and therefore a 1-multiset, the question arises whether the extended table algebra of infinite tables is subalgebra of extended multiset table algebra. This research is devoted to this question.

The first thing that needed to be established is that the set of all tables of extended table algebra of infinite tables is a subset of the set of all tables of extended multiset table algebra. Then, applying the set-theoretic and logical-algebraic methods, it is proved that the extended table algebra of infinite tables is not closed with respect to some signature operations of the extended multiset table algebra. Thus, table algebra of infinite tables does not form subalgebra of multiset table algebra since it is not closed with respect to the union, projection and active complement. So multiset table algebra is not a wider formalism then table algebra of infinite tables.

The obtained results can be applied to the development of query languages for table databases and software with table databases.