A Multi-Set Extended Relational Algebra - A Formal Approach to a Practical Issue

P.W.P.J. Grefen, R.A. de By

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

39 Citations (Scopus)
472 Downloads (Pure)


The relational data model is based on sets of tuples, i.e. it does not allow duplicate tuples an a relation. Many database languages and systems do require multi-set semantics though, either because of functional requirements or because of the high costs of duplicate removal in database operations. Several proposals have been presented that discuss multi-set semantics. As these proposals tend to be either rather practical, lacking the formal background, or rather formal, lacking the connection to database practice, the gap between theory and practice has not been spanned yet. This paper proposes a complete extended relational algebra with multi-set semantics, having a clear formal background and a close connection to the standard relational algebra. It includes constructs that extend the algebra to a complete sequential database manipulation language that can either be used as a formal background to other multi-set languages like SQL, or as a database manipulation language on its own. The practical usability of the latter option has been demonstrated in the PRISMA/DB database project, where a variant of the language has been used as the primary database language.
Original languageEnglish
Title of host publicationProceedings of the 10th International Conference on Data Engineering (ICDE 1994)
Place of PublicationLos Alamitos, CA
Number of pages9
ISBN (Print)0-8186-5402-3
Publication statusPublished - Feb 1994
Event10th International Conference on Data Engineering, ICDE 1994 - Houston, United States
Duration: 14 Feb 199418 Feb 1994
Conference number: 10


Conference10th International Conference on Data Engineering, ICDE 1994
Abbreviated titleICDE
Country/TerritoryUnited States


Dive into the research topics of 'A Multi-Set Extended Relational Algebra - A Formal Approach to a Practical Issue'. Together they form a unique fingerprint.

Cite this