This paper is a logical continuation of research devoted to the actual problem of developing the theoretical foundations of table (relational) databases. The issue of using multisets in table databases is important and relevant. Many database-oriented languages require a relational model with multiset semantics. There are many applied problems, the feature of which is multiplicity and repeatability of data. For example, these are sociological polls of different population groups, calculations on DNA, and others. In this context, the question of constructing a tuple calculus for a multiset table algebra is considered, in which the concept of a table is refined using the concept of a multiset. In the article, the formalization of tuple calculus for multiset table algebra is carried out. The alphabet, and the syntax of terms, atoms, and formulas are defined. A set of legal formulas is introduced through the concept of the free and bound variable. The concept of a scheme and set of attributes with which a tuple variable occurs in a formula are also introduced. The definition of tuple calculus expression for multiset table algebra is given, according to which it is a multiset of tuples that satisfy the condition defined by the legal formula. The article provides rules for determining the number of tuple duplicates in the resulting multiset. Another important result consists in proving that constructed tuple calculus is as expressive as multiset table algebra. This research opens up new possibilities for database theory development and may be useful for information technology and database professionals. It contributes to a deeper understanding of construction query principles, an important aspect of modern computer science and industry.
Relational calculus underlies most relational query languages, specifying only the expected result, while relational algebra involves constructing a relational expression and performing operations.
• •
Tuple calculus (E. Codd) which operates on table tuples [
Domain calculus (M. Lacroix, A. Pirotte) which focuses on table domains [
The clarification of the concept of relation in terms of naminal sets was carried out by V.N.
Redko, Yu.Y. Bron, D.B. Buy, and S.A. Polyakov [
Additionally, in the work [4] multiset table algebra is constructed, which extends database capabilities through multisets. The signature of multiset table algebra is supplemented with new operations: inner and outer join operations, semijoin operations, and aggregate operations.
In [5, 6] the theorem-plural and logical-algebraic methods found that 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. Thus, multiset table algebra is not a wider formalism then table algebra of infinite tables
Many database-oriented languages, such as SQL, require a relational model with multiset semantics. However, the traditional tuple (domain) calculi do not support queries that produce tables with duplicates. Therefore, there is a need to develop a calculus for multiset table algebra.
The research aims to construct a tuple calculus for multiset table algebra and to show that it is no less expressive than multiset table algebra.
Many languages oriented towards working with databases require a relational data model with
multiset semantics because, firstly, relations that allow duplicates are useful in many applied fields
where duplicate objects may exist; secondly, in the relational data model, removing duplicates after
performing projection and union operations implies merging identical elements or performing other
labor-intensive actions. Various researchers have focused on the utilization of multisets in
databases, including Paul Grefen and Rolf A. de By [7, 8], G. Lamperti, M. Melchiori, and M. Zanella
[9], G. Garcia-Molina, J. Ullman, and J. Widom [10, 11], A. Silbeschatz, H. Korth, and S. Sudarshan
[12], D.B. Buy, S.A. Polyakov, Yu.Y. Brona, and V.N. Redko [
Let's start by considering the key terms of multisets based on sources [
Let be an arbitrary set. A multiset with basis is a function
: → , where = {1, 2, … } is the set of natural numbers.
Let be the universe of elements of multiset bases. A characteristic function of multiset is a function !: → !, the values of which are specified by the following piecewise schema: ! = if ∈ 0, else for all d ∈ D . Here is the range of definition of multiset as a function ( = ! – basis of multiset ).
The empty multiset ∅! is defined as a multiset which basis is an empty set.
The 1-multisets are multisets whose range of values is the empty set or a single-element set {1}. These multisets are the analogues of ordinary sets.
The operations over multisets are defined in terms of characteristic functions in monograph [
Let's examine the main concepts and statements of multiset table algebra, based on the monograph [4]. In this case, under relation, understand a multiset, in particular, infinite.
Let's consider two sets: is the set of attributes, and is the universal domain.
A scheme will be defined as any arbitrary finite set of attributes ⊆ . A tuple of the scheme is a nominal set on pair , . The projection of this nominal set for the first component is equal to . We will use the following notations: () is the set of all tuples of the schema , and is the set of all tuples.
A table of the scheme ( ⊆ ) is a pair where the first component is an arbitrary multiset, the basis of which Θ() is the set of tuples of the same scheme and the second component is a scheme of the table.
The set of all table on scheme is designated as Ψ() and the set of all table is designated as Ψ = ! Ψ( ).
The notation (, ) represents the number of duplicate tuple in the multiset . A multiset can also be written as {!!!, … , !!!}, where ! = (!, ), = 1, … , , and Θ = {!, … , !} is a of the multiset .
Under multiset table algebra is understood an algebra
, , , Ω!,! , where is the set of all tables, Ω!,! = {⋃!!"", ⋂!!"",\!!"", !,!, !,!, ⨂!!,!!, !,! , ~!}!!∈,!!, !,!!∈,!!!⊆ is the signature, , Ξ are the sets of parameters. The signature Ω!,! contains operations of multiset (union ⋃!!"", intersection ⋂!!"" , difference \!!"") and special operations (selection !,! , projection !,! , join ⨂ , renaming !,!, and active complement ~! ).
!!,!!
Multiset table algebra is also filled up with additional operations such as inner join (Cartesian join, natural join, join using attributes and join on predicate), outer join (outer left join, outer right join, outer full join and union join), semijoin and aggregate operations (Sum, Avg, Max, Min, Count). The special element NULL is inserted in the universal domain for to define of outer join and outer set operations. The operations of signature Ω!,! and a formal mathematical semantics of additional operations are defined in [4].
The following statement holds.
Theorem 1. Any expression of the multiset table algebra can be replaced with an equivalent expression that uses only the operations of selection, join, projection, union, difference, and renaming.
Proof. To prove the first statement, we will show that the operations of intersection and active complement can be expressed through other operations of multiset table algebra. The operation of multiset intersection can be replaced by the difference [13]: !, ⋂!"" !, = !, \!!""( !, \!"" !, ).
! !
The operation of active complement is expressed through the operations of projection, difference, and join (by definition): ∼! ,
! = , \!"" , , where , = !! ,! ,
⨂ … ⨂ {!!},{ !} {!!,…,!!!!},{!!} !! ,! , , and = !, … , ! is a scheme of the table , .
According to the proof, the operations of intersection and active complement are derived from other operations in the signature of multiset table algebra and can henceforth be excluded from consideration. 4. Tuple Calculus for Multiset Table Algebra
The basis of relational calculus is the calculus of first-order predicates. We will start the construction of tuple calculus for multiset table algebra with the definition of the alphabet.
The alphabet of tuple calculus for multiset table algebra consists of: • a set of attributes and universal domain ; • a set of object variables (tuple variables) !, !, …; • a set of object constants !, !, …; • a set of function symbols !!!, !!!, … , ! ≥ 1; • a set of predicate symbols !!!, !!!, … , ! ≥ 1; • a set of symbols of constant tables , ; • a set of symbols of variable tables , ; • the signs of logical operations ¬, ⋀, ⋁, and quantifiers ∀, ∃; • punctuation marks – parentheses () and commas.
The universal domain is the domain of interpretation of object constants, and the set of all tuples over is the domain of interpretation of object variables.
We will use • as syntactic variable, the domain of change of which is the set of variables; • as syntactic variable, the domain of change of which is the set of function symbols; • as syntactic variable, the domain of change of which is the set of predicate symbols; • as syntactic variable; • as syntactic variable, the domain of change of which is the set of attributes.
Terms and formulas are distinguished among the words written using alphabet symbols. Let us define these syntactic objects by induction on their length.
The following expressions are terms: a) is a term; b) () is a term; c) if !, … , ! are terms and is a function symbol of arity then !, … , ! is a term; d) there are no terms other than those specified in points a)-c).
Further in the text, is a syntactic variable, the domain of change of which is the set of terms. Let's define the formulas, starting with atomic formulas (atoms), which come in three types: а1. For any constant table , and for any tuple variable , !() is an atom. !() stands for ∈ , . а2. For any variable table , and for any tuple variable , !() is an atom. !() stands for ∈ , . а3. For any terms !, … , !, and for any predicate of arity on the universal domain , !, … , ! is an atom. f1. Let's construct formulas from atoms using the logical connectives ¬, ⋀, ⋁, quantifiers ∀, ∃, and parentheses. f2. Every atom is a formula. f3. If and are formulas, then ¬, ⋀, ⋁ are formulas. f4. If is a tuple variable, is a formula, ⊆ is a scheme, then ∀(), ∃() are formulas. f5. If is a formula, then () is a formula.
f6. There are no other formulas besides those specified in points f1-f4.
We will use , and as syntactic variables, the domain of change of which is the set of formulas.
Let's define the class of legal formulas, using the concepts of free and bound variables, the scheme ℎ(, ) for tuple variable , and the set of attributes with which tuple variable occurs in a formula , (, ). The expressions ℎ(, ) and (, ) are defined if the tuple has at least one free occurrence in the formula . Additionally, the including (, ) ⊆ ℎ(, ) holds if these expressions are defined.
We will define expression for terms first: 1. if = , then , = ∅; 2. if = (), then , = {}, аnd , () = ∅, where ≠ ; 3. if = !, … , ! , where ! are terms then , = !!!! , . In other words, , is the set of attributes that the scheme of the tuple must have. Consider the cases where is an atomic formula, then а1. if = !(), then is free in and ℎ , = , = ; а2. similarly if = !(), then is free in and ℎ , = , = ; а3. if = !, … , ! , where ! are terms, and !, … , ! are all variables of these terms, then this tuple variables are free in formula , ℎ !, is undefined, and !, = !!!! !, ! , = 1, … , .
Atomic formulas are all legal. The construction of all legal formulas proceeds by induction on the length of formulas. Assume and are both legal formulas.
f1. If = ¬, then is legal, and all occurrences of variables in free or bound as they are in . For every tuple that occurs free in , ℎ , ≃ ℎ , and , = , , where ≃ is a generalized equality, meaning that both sides of the equality are either undefined or defined and have equal values [14]. f2. If = ⋀ or = ⋁, then all occurrences of variables in are free or bound as their corresponding occurrences are in and . Assume variable occurs free in subformulas and/or . Define the scheme, and the set of attributes with which tuple variable occurs in a formula for formula . Next cases take place.
a. The schemes of formulas ℎ , and ℎ , are both defined.
Formula is legal if equality ℎ , = ℎ , holds. According to the definition ℎ , = ℎ , . b. The scheme is defined for only one subformula. Assume ℎ , is defined, and ℎ , is undefined. Formula is legal if including , ⊆ ℎ , holds. According to the definition ℎ , = ℎ , . c. The scheme is undefined for both subformulas, then formula is legal but ℎ , is undefined.
In all these three cases , = , ∪ , . f3. If = ∃() then must occur free in for to be legal. Furthermore, if ℎ , is defined, then equality ℎ , = must hold if including , ⊆ is held. ℎ , and , are not defined, since does not occur free in . Any occurrence of a variable ≠ is free or bound in as it was in .
If occur free in , then ℎ , ≃ ℎ , and , = , . f4. If = ∀(), then all restrictions and definitions are the same as in f3. f5. If = (), then is legal, and free and bound variables, ℎ and are the same as for .
In other words, the equality , = means that for a specific interpretation of the formula , when the variable takes on a value in the form of a tuple of the scheme ′, the inclusion ⊆ ′ must hold.
Expressions of tuple calculus for multiset table algebra have the form
{! |()}, where: 1. The formula is legal. 2. The variable is the only variable that occurs free in the formula .
3. If ℎ , is defined, then ℎ , = , otherwise , ⊆ . 4. is the number of duplicates of the tuple .
It is worth emphasizing that the result of executing the query defined by the expression {! |()} is a multiset of tuple described by the expression ().
Let be a legal formula, ⊆ . Then substituted for in formula is the formula (/). The value of the formula (/) is determined by modifying each atom from according to the following rules: а1. Let the tuple variable in !!() be free in formula . By the definition of an legal formula, we have the inclusion ′ ⊆ . Atom !!() acquires the value of true at substituted for , if |′ ∈ (), otherwise, atom !!() acquires the value of false. а2. Let the tuple variable in !!() be free in formula . By the definition of an legal formula, we have the inclusion ′ ⊆ . Atom !!() acquires the value of true at substituted for , if |′ ∈ (), otherwise, atom !!() acquires the value of false. а3. Let the tuple variable in = !, … , ! be free in formula , then at substituted for , replace (!) by ! ∈ , where !, ! ∈ (! is value of attribute ! in tuple ). Atom !, … , ! acquires the value of true, if predicate is true on the proper values, otherwise atom acquires the value of false.
The set of values of truth of all atoms of formula is called interpretation. Let be a legal formula with no free tuple variables. The interpretation of formula is defined as follows. f1. If = ¬, then must have no free variables. The formula is true, if is false, and it is false, if formula is true. f2. If = ⋀ or = ⋁, then neither or Q have free variables. If = ⋀, then is true exactly when and are both true, otherwise, is false. If = ⋁, then is false exactly when and are both false, otherwise, is true. f3. If = ∃(), then is the only variable that occurs free in . The formula is true, if there is at least one tuple ∈ () such that formula (/) is true, otherwise, formula is false. f4. If = ∀(), then is the only variable that occurs free in . The formula is true, if for every tuple ∈ () formula (/) is true, otherwise, formula is false. If = (), then is true, if formula is true and is false, if is false.
Let = {! |()} be a tuple calculus expression. The value of expression is the table , of multiset table algebra containing every tuple ∈ () such that formula (/) is true. The number of duplicates of the tuple in the table , is determined as follows: 1) if = !(), then = , = (, ); 2) if = !(), then = , = (, ); 3) if = !, … , ! , where ! are terms, = 1, , and !, … , ! are all variables of these terms, then = , = !!∈! ! ,!!|!!!! ′, , !,…,! !!"#$ where , is the table to which the query is constructed, ! = ! !!! (!, !), = 1, ; 4) if = ¬ and the formula generates duplicates of the tuple , then 5)
= , = (, ())−, where () is a multiset of the table ( , ) which is the saturation of the table , , which is the value of the expression {! |()}, and − = − ≥ ; 0 < 6) if = ⋀, the formula generates duplicates of the tuple , and the formula generates duplicates of the tuple , then = , = min (, ); 7) if = ⋁ , the formula generates duplicates of the tuple , and the formula generates duplicates of the tuple , then = , = + ; 8) if = ∃() and the formula generates duplicates of the tuple , then = , = . 9) if = ∀() and the formula generates duplicates of the tuple , then = , = . 10) if = () and the formula generates duplicates of the tuple , then = , = .
Theorem 2. If is a multiset table algebra expression, then it is possible effectively to build equivalent to it expression of tuple calculation.
Proof. According to Theorem 1, in the proof, it is sufficient to consider expressions of multiset table algebra that contain only the operations of union, difference, selection, projection, join, and renaming. We will prove this theorem by mathematical induction on the number of operations in the expression .
Basis. In this case, the expression does not contain any operations. There are two cases. First case. If = , is constant table, where is a multiset of the scheme , then = {! |!()}.
Second case. If = , is variable table, then = {! |!()}.
Induction. Assume the theorem holds for any multiset table algebra expression with fewer than operators. Let have operators. There are six cases.
Case 1 (union). = ! !!"" !, where expressions ! and ! each have less than operators. By the inductive hypothesis we can find tuple calculus expressions {! |()} and {! |()} equivalent to ! and ! respectively. The values of these expressions are tables in which the tuple appears and times, respectively. Then is {! |()⋁()}, where = + .
!
Case 2 (difference). = !\!""!, where expressions ! and ! each have less than operators. Tuple calculus expressions {! |()} and {! |()} are equivalent to ! and ! respectively as in Case 1. Then = {! |()⋀¬()}, where = −.
Case 3 (selection). = !,!(!), where expression ! has less than operators. Let {! |()} be tuple calculus expression equivalent to !. Then = {! |()⋀( ! , … , ! )}, where = {!, … , !} is the scheme of table that is the value of expression !. The number of duplicates of the tuple in the output table does not change, therefore = . Assume that predicate-parameter of select is defined = , ∈ (), where is a predicate symbol of as = ⇔ ! , … , ! arity . □
Case 4 (projection). = !,!(!).
Let {! |()} be tuple calculus expression equivalent to !. = {! ⋂ |∃()(()⋀ !∈!⋂! = )}, where = !∈!⋂! ! ! ! .
Case 5 (join). = ! ⨂ !.
!!,!! Tuple calculus expressions {! |()} and {! |()} are equivalent to ! and ! respectively Then is {! !⋃! |∃(!)∃(!)( ()⋀ !∈!! = ⋀ = ×. □
!∈!! = )}, where
Case 6 (renaming). = !,!(!), where : → is injective function that renames attributes. Let {! |()} be tuple calculus expression equivalent to !. Then = {! ! |∃()(()⋀ !∈!\!"#$ = ⋀ !∈!⋂!"#$ = () )}, where ! = \⋃[], and = .
The fundamental data object in the SQL language is not the classical relation of E. Codd but rather a table. Moreover, SQL tables do not contain sets of tuples but multisets of tuples, meaning duplicates are allowed. The basic SQL operators are not relational operators in the strict sense but are analogs of relational operators designed to work with multisets. When creating a new table using a query, an SQL system typically does not remove duplicate tuples but returns a result in which the same tuple can appear multiple times. To exclude duplicates, the keyword DISTINCT must be placed after the SELECT operator.
Let's demonstrate the appropriateness of constructing tuple calculus for multiset table algebra with the following example.
Example 1. Consider the table Scores, , where the scheme = {№, Name, Topic 1, Topic 2,
Topic 3, Quiz} (see Table 1).
Student 1 Student 2 Student 3 Student 4 Student 5 Student 6 Student 7 The answer to the question "What scores did the first five students get for the quiz?" in SQL would look like this:
The result is a table Quiz, ! , where the schema ! = Quiz , which contains duplicate values (see Table 2).
It is impossible to implement this query in terms of classical tuple calculus, since the result will be a set of tuples, not a multiset (as expected), meaning duplicates will not be considered in the result.
In the tuple calculus for multiset table algebra, the expression equivalent to this query will have the form: {!(Quiz) | ()(Scores ⋀ (№) = 1⋁ (№) = 2⋁(№) = 3⋁(№) = 4 ⋁(№) = 5)⋀ ⋀(Quiz) = (Quiz))}.
The result described by this tuple calculus expression is similar to the result obtained when executing the corresponding query in SQL.
Example 2. Consider the table Results, ′ , where the scheme ′ = { №, Name, Total, ECTS} (see Table 3).
Let's consider the query "How many points for the quiz have students who scored more than 83 points in total?".
We will write the corresponding expression of multiset table algebra, assuming that we only need to know the quiz scores: = !"#$
Scores, !⨂,!!!"#$%!!" Results, ′ .
The result is a table Query, {Quiz} , which contains duplicate values (see Table 4).
From Table 4, it is clear that only two students in total have more than 83 points. Let’s write the tuple calculus expression equivalent to this algebraic expression.
Tuple calculus expressions {! |Scores()} and {! ′ |()} are equivalent to Scores, and Results, ′ respectively, where = {№, Name, Topic 1, Topic 2, Topic 3, } and ′ = { №, , , }.
{! ! |Results ⋀ Total > 83}
!"#$%!!" Results, ′ .
Its value is a table without duplicates because table Results, ′ does not have duplicates. Tuple calculus expressions which equivalent to algebraic expression
Scores, !⨂,!!!"#$%!!" Results, ′ is {!!!×! ⋃! |∃()∃(′)(Scores ⋀Results ⋀ Total > 83⋀ № № ⋀ Name = Name ⋀ № = № ⋀ Name = Name )}. =
Since there are no duplicate tuples in the tables Scores, and Results, ′ , there will also be no duplicate tuples in the resulting table after the join.
Finally, the tuple calculus expression equivalent to the algebraic expression has the form: {({}⋂(⋃!))|∃ ⋃! (∃ ∃ ! ⋀ ⋀ > ⋀ № = № ⋀ = ⋀ № = № ⋀ = )}.
In the table obtained after the join, the tuple appears once. Therefore, in the output table, the number of duplicates of the tuple is =
∈{}⋂(⋃!) ! .
The result is a table Query, {Quiz} , where , Query = 1 + 1 = 2, = { , 20 }. The corresponding SQL query has the form:
Thus, as can be seen from the examples, the constructed tuple calculus for multiset table algebra allows for the adequate formalization of query languages, particularly SQL, considering the multiset semantics embedded in them.
The article proposes a tuple calculus for multiset table algebra. The alphabet, syntax of terms, atoms, and formulas of the tuple calculus are defined. Using the concept of free and bound tuple, the notion of scheme, and the set of attributes with which a tuple appears in formulas, a class of legal formulas is introduced. It is shown that the proposed tuple calculus is no less expressive than multiset table algebra. An example demonstrates the feasibility of constructing tuple calculus for multiset table algebra, considering that query languages oriented towards database work imply the repeatability of elements in a table.
The next research challenge is to establish the corresponding dual result. [4] D.B Buy, I.M. Glushko, Calculi and extensions of table algebras signature. Nizhyn: NDU im. M.
Gogol, 2016. [in Ukrainian] [5] I.Glushko, About relationship between table algebra of infinite tables and multiset table algebra, in CEUR Workshop Proceedings, 2139, 2018, pp. 159–163. [6] I. Lysenko, Extended table algebra, extended multiset table algebra, and their relationship, in: Proceedings of International Conference on Software Engineering “SoftEngine 2020”, 2020, pp 28-32. [7] Paul W.P.J. Grefen, Rolf A. de By, A Multi-Set Extended Relational Algebra. A Formal Approach to a Practical Issue, in: Proceedings of 10th International Conference on Data Engineering, ICDE, 1994, pp. 80-88. [8] Paul W.P.J. Grefen, J. Flokstra, Extending a Multi-Set Relational Algebra to a Parallel
Environment, in: Distributed and Parallel Databases, Vol 4. (1996) 81-99. [9] G. Lamperti, M. Melchiori, M. Zanella, On Multisets in Database Systems, in Multiset Processing: Mathematical, Computer Science, and Molecular Computing Points of View, number 2235 in Lecture Notes in Computing Since (2001)147-215. [10] H. Garcia-Molina, J.D. Ullman, J. Widom, Database Systems: The Complete Book, 2nd. ed.,
Prentice Hall, 2008. [11] J.D. Ullman, J. Widom.Ullman, A First Course in Database Systems, 3rd ed., Prentice Hall, 2007. [12] A. Silbeschatz, H. Korth, S. Sudarshan, Database System Concepts, 6th ed. McGraw-Hill, 2011. [13] J.A. Bogatyreva, Multisets theory and its applications. Ph.D. thesis, Kyiv National Taras
Shevchenko University, 2011. [in Ukrainian] [14] N.Cutland, Computability. An introduction to recursive function theory, Cambridge University Press, 1980.