A new normal form for nested relations

Reviewer: Jane B. Grimson

Relational databases were developed initially for storing conventional data. However, the inherent simplicity of the relational model encouraged those who had to manage large volumes of nonconventional, often unstructured, data (e.g., in the fields of computer-aided design, office information systems, etc.) to examine the applicability of the model to their particular environments. This led to the development of a variety of rather awkward mapping techniques from these databases onto relational databases. It has been realized that such an approach is not always desirable or, indeed, feasible and a number of researchers have been examining alternative methods. One particular difficulty arises from the fact that many of these nonconventional databases are not in first normal form, and to convert them artificially, as it were, into first normal form introduces a degree of artificiality and a lack of flexibility into the applications. This paper addresses this issue and presents a new normal form for such nested relations. The authors introduce the concept of a normal scheme tree for the representation of the normalized nested relations. The aim of the tree is to preserve the multivalued dependencies of the database and also to reduce redundancy and avoid anomalies. An algorithm for decomposing relations into nested normal form is presented. The authors are currently working on the incorporation of functional dependencies as well as multivalued dependencies into their model. The authors adopt a purely theoretical approach to the problem, and clearly the sound and thorough mathematical treatment of their work is essential. The next step must surely be to examine the practical issues associated with the storage, retrieval, and update of a database whose relations are in nested normal form.