About this Computer Science article
Towards Tractable Algebras for Bags by Stéphane Grumbach; Tova Milo is a Computer Science article available to read on EtoBox.
Bags, i.e., sets with duplicates, are often used to implement relations in database systems. In this paper, we study the expressive power of algebras for manipulating bags. The algebra we present is a simple extension of the nested relation algebra. Our aim is to investigate how the use of bags in the language extends its expressive power and increases its complexity. We consider two main issues, namely (i) the impact of the depth of bag nesting on the expressive power and (ii) the complexity and the expressive power induced by the algebraic operations. We show that the bag algebra is more expressive than the nested relation algebra (at all levels of nesting), and that the difference may be subtle. We establish a hierarchy based on the structure of algebra expressions. This hierarchy is shown to be highly related to the properties of the powerset operator.
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Stéphane Grumbach; Tova Milo
- Publisher
- Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0022-0000)
- Published
- 1996
- Language
- EN
- Field
- Computer Science (Physical Sciences)