Equivalence of the relational algebra and calculus for nested relations

AbstractThe relational model is extended to include nested structures. This extension is formalised using the distinction between a tuple scheme and a relation scheme. The algebra and calculus languages are defined for this model. It is shown that the restricted powerset is a derived operation in the algebra and the full powerset is expressible by a safe formula in the calculus. Since the full powerset cannot be derived from the algebra operations, there does not exist a complete equivalence between the calculus and the algebra. In other words, given any algebra expression, there is a safe calculus formula with equivalent expressive power. Conversely, given any safe calculus formula and a bound on the cardinality of the database instance, there is a corresponding equivalent algebra expression. The relational algebra is then augmented with programming constructs and this augmented algebra is shown to be equivalent in expressive power to the relational calculus for nested relations