EXTENDING A MULTI-SET RELATIONAL ALGEBRA TO A PARALLEL ENVIRONMENT

Parallel database systems will very probably be the future for high-pe rformance data-intensive applications. In the past decade, many parall el database systems have been developed, together with many languages and approaches to specify operations in these systems. A common backgr ound is still missing, however. This paper proposes an extended relati onal algebra for this purpose, based on the well-known standard relati onal algebra. The extended algebra provides both complete database man ipulation language features, and data distribution and process allocat ion primitives to describe parallelism. It is defined in terms of mult i-sets of tuples to allow handling of duplicates and to obtain a close connection to the world of high-performance data processing. Due to i ts algebraic nature, the language is well suited for optimization and parallelization through expression rewriting. The proposed language ca n be used as a database manipulation language on its own, as has been done in the PRISMA parallel database project, or as a formal basis for other languages, like SQL.