A comparison between algebraic query languages for flat and nested databases (Q1177142)

The authors present a deep comparision of the expressive power of query formalisms for flat and nested relational database models. Nested relation databases and their foundations have found much attention in the last years. The paper considers two query algebras for them, namely the nested algebra and the powerset algebra, and compare them mutually as well as to the flat relational algebra. After the introductional section, the second section introduces the nested relational database model and basic algebra operators for manipulating nested relations. The notions of schema and nested relation instances as well as the semantics of query algebra operators are defined in terms of set-theoretic concepts. The third section presents the comparison between the nested algebra and the powerset algebra. The authors show that either the nest or the difference operator can be removed as a primitive operator from the powerset algebra. The powerset algebra is shown to be equivalent to the nested algebra either extended by a least fixpoint operator or a while operator. The last section gives a brief comparison of several query languages both for the flat and the nested case. Similarities and differences between query languages for the flat and the nested case are discussed.