Restructuring partitioned normal form relations without information loss

Nested relations in partitioned normal form (PNF) are an important subclass of nested relations that are useful in many applications. In this paper we address the question of determining when every PNF relation stored under o ne nested relation scheme can be transformed into another PNF relation stor ed under a different nested relation scheme without loss of information, re ferred to as the two schemes being data equivalent. This issue is important in many database application areas such as view processing, schema integra tion, and schema evolution. The main result of the paper provides two chara cterizations of data equivalence for nested schemes. The first is that two schemes are data equivalent if and only if the two sets of multivalued depe ndencies induced by the two corresponding scheme trees are equivalent. The second is that the schemes are equivalent if and only if the corresponding scheme trees can be transformed into the other by a sequence of application s of a local restructuring operator and its inverse.