Theory of unnormalized relational structures (database, normalization)
Dirk Van Gucht · 1985
Motivated by the trend to integrate new functions into data base systems, Jaeschke and Schek, and Fischer and Thomas developed an extension of Codd's relational data base model. In this model data is represented as unnormalized relational structures, in which the tuple entries are not required to be atomic data values (as is the case in Codd's first-normal-form model), but can be unnormalized structures themselves. Besides the classical relational operators this model contains two important data restructuring operators, the NEST and UNNEST operators. Given the naturalness of the unnormalized relational model, we conduct an in-depth study of the set-theoretic and algebraic properties of unnormalized relational structures and the extended relational algebra. Since unnormalized structures are being used in different contexts, ranging from the physical organization of data to output formats of data, we introduce a classification of unnormalized structures in terms of their set-theoretic characteristics. We consider the following subclasses of structures: the normalization lossless structures, the nested relations, the permutable nested relations, and the hierarchical structures. We give nontrivial characterizations of nested relations, permutable nested relations and hierarchical structures, and polynomial-time recognition algorithms for these classes. Besides analyzing various special subclasses of structures, we also study the properties of the corresponding underlying normalized relations. Characterizations are obtained for relations which are the result of unnesting permutable nested relations or hierarchical structures. It turns out that there is a strong relationship between properties of structures and dependency theory. We therefore analyze some special dependencies which occur in this context. In particular we give a complete axiom system for the multivalued and weak multivalued dependencies. Since dependencies can be used to specify the semantics of a data application, we relate our results to a number of interesting data base design questions.