Towards tractable algebras for bags
Towards tractable algebras for bags
复制标题
面向袋子的易处理代数
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Tova Milo
中科院分区：
文献类型：
--
作者：
S. Grumbach;Tova Milo
包，即具有重复项的集合，通常用于在数据库系统中实现关系。在本文中，我们研究了操纵袋的代数的表达能力。我们提出的代数是嵌套关系代数的简单扩展。我们的目的是研究语言中包的使用如何扩展语言的表现力，并增加语言的复杂性。我们考虑了两个主要问题，即(i)袋嵌套深度与表达能力之间的关系，以及（ii）代数运算及其复杂性和表达能力之间的关系。我们展示了袋代数比嵌套关系代数更具表现力（在所有嵌套级别上），并且差异可能是微妙的。我们根据代数表达式的结构建立了一个层次结构。这个层次结构与幂集操作符的属性高度相关。
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 relationship between the depth of bag nesting and the expressive power, and (ii) the relationship between the algebraic operations, and their complexity and expressive power. 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.