Theoretical foundation of algebraic optimization utilizing unnormalized relations

Abstract

Unnormalized (NF²) relations, not conforming to the first normal form condition (1NF) of the relational model have been proposed recently for a variety of new applications. In this paper we extend NF² relational theory in a way that it becomes possible to use NF² relations as storage structures for conventional 1NF relational database interfaces. Physical clustering of precomputed joins can be achieved this way without introducing redundancy. However, applying transformation rules to internal relations straightforwardly, will still yield unnecessary join operations. With the equivalence rules introduced here we prove that efficient algebraic optimization can be performed using standard (1NF) techniques. Particularly, all redundant joins can be properly removed.