On fast and space-efficient database normalization : a dissertation presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Information Systems at Massey University, Palmerston North, New Zealand

Abstract

A common approach in designing relational databases is to start with a relation schema, which is then decomposed into multiple subschemas. A good choice of sub- schemas can often be determined using integrity constraints defined on the schema. Two central questions arise in this context. The first issue is what decompositions should be called "good", i.e., what normal form should be used. The second issue is how to find a decomposition into the desired form. These question have been the subject of intensive research since relational databases came to life. A large number of normal forms have been proposed, and methods for their computation given. However, some of the most popular proposals still have problems: - algorithms for finding decompositions are inefficient - dependency preserving decompositions do not always exist - decompositions need not be optimal w.r.t. redundancy/space/update anomalies We will address these issues in this work by: - designing effcient algorithms for finding dependency preserving decompositions - proposing a new normal form which minimizes overall storage space. This new normal form is then characterized syntactically, and shown to extend existing normal forms.