On Multisets in Database Systems

Database systems cope with the management of large groups of persistent data in a shared, reliable, effective, and efficient way. Within a database, a multiset (or bag) is a collection of elements of the same type that may contain duplicates. There exists a tight coupling between databases and multisets. First, a large varietyof data models explicitly support multiset constructors. Second, commercial relational database systems, even if founded on a formal data model which is set-oriented in nature, allows for the multiset-oriented manipulation of tables. Third, multiset processing in databases may be dictated by efficiency reasons, as the cost of duplicate removal may turn out to be prohibitive. Finally, even in a pure set-oriented conceptual framework, multiset processing may turn out to be appropriate for optimization of query evaluation. The mismatch between the relational model and standardized relational query languages has led researchers to provide a foundation to the manipulation of multisets. Other research has focused on extending the relational model by relaxing the first normal form assumption, giving rise to the notion of a nested relation and to a corresponding nested relational algebra. These two research streams have been integrated within the concept of a complex relation, where different types of constructors other than relation coexist, such as multiset and list. Several other database research areas cope with multiset processing, including view maintenance, data warehousing, and web information discovery.