A parallel algorithm for relational database normalization

The problem of database normalization in a parallel environment is examined. Generating relation schemes in third normal form is straightforward when given a set of functional dependencies that is a reduced cover. It is shown that a reduced cover for a set of functional dependencies can be produced in parallel. The correctness of the algorithm is based on two important theorems. it is demonstrated that the companion third normal form algorithm can be easily translated into a parallel version. The performance of the two algorithms is compared to the performance of their serial counterparts. The standard serial algorithms for computing minimal covers and synthesizing third normal form relations are presented. The parallel algorithms and their rationale are discussed