Multilevel nested relational structures

摘要

We consider relations not in first normal form, i.e., a data item in a relation may itself be a relation, and extend the relational algebra to include the restructuring operators NEST and UNNEST. Algebraic characterizations are given for the classes of normalization-lossless relations (obtainable by restructuring flat relations), the nested flat relations (obtainable by applying NEST operations to a flat relation) and the permutable nested relations (the result is independent of the order of nesting). Polynomial-time recognition algorithms are also given for the latter two classes.