Normal forms and relational database operators

Abstract

We discuss the relationship between normal forms in a relational database and an allowed set of relational operators. We define "projection-join normal form" (PJ/NF), which is the ultimate normal form when only projection and join are allowed. Aho, Beeri and Ullman made the counterintuitive discovery that there is a relation schema with a valid decomposition into three of its projections without the decomposition being equivalent to a cascade of decompositions, each into two projections. Because of this possibility, there exist bizarre relation schemata that are in fourth normal form but not in PJ/NF. We also discuss issues associated with allowing the union operator.