Design of relational database schemes by deleting attributes in the canonical decomposition (Q1096418)

The paper deals with the construction (``decomposition'') of a relational database scheme, starting from some user-defined sets of attributes (U) and functional dependencies (F). The algorithm presented is attribute- based and it is an extension of Jou's algorithm [\textit{J. H. Jou}, Theory of functional relation schemes in relational databases, TR. C5-80-10, Dep. Comput. Sci., Vanderbilt Univ., Nashville, Tennessee (1980)], in the sense that the relation schemes in the decomposition are in the third normal form. Much more, the method invariantly preserves three basic properties of the schemes (``object-faithful'', ``Fd-faithful'' and ``strongly normative''), and it can be extended to achieve the lossless join property and minimality of the number of relation schemes. Roughly speaking, it produces an initial design that is directly based on the semantic information supplied by F and this decomposition is then stepwise ameliorated by local transformations (deletion to the so-called ``abnormal nonprime attributes''). The algorithm works in time \(O(| U|^ 3\cdot | F|^ 6)\). The paper is almost self-contained and examples and comparisons with other existing (dependency-oriented) methods are provided.