Classification of nested tables under deeply nested algebra

A variety of nested relational algebra can be classified into the shallowly nested algebra and the deeply nested algebra. The former restricts application of operations to the outermost level of nested relations, while the latter allows direct manipulation of internal table structures. Most theoretical studies on nested relations have been done based on the shallowly nested algebra because of its logical simplicity. However, data manipulation can be expressed more succinctly under the deeply nested algebra. Several interesting subclasses of nested relations were identified under the shallowly nested NEST and FLAT operations. The authors study classification of nested relations under the deeply nested NEST/FLAT, and prove that each subclass defined under the deeply nested NEST/FLAT is equal to its counterpart defined under the shallowly nested NEST/FLAT. The discussion is based on the study of commutativity of the deeply nested NEST/FLAT and clarifies their important properties