Compact scheme forests in nested normal form

Abstract

In the context of data base design for nested relational structures, update anomalies can be avoided if the nested scheme forest composed of scheme trees is in nested normal form (NNF) with respect to the associated set of data dependencies. In practice, minimizing the number of normal scheme trees in the nested scheme forest, which is in NNF, will also be an important design goal. This is because the number of computationally expensive join operations that are required in order to answer a given query is related to the number of normal scheme trees that must be used in the query expression.

We prove that the problem of finding a succinct NNF scheme forest is NP-complete for a subclass of the class of split-free sets of multivalued dependencies.

Keywords:

• Relational database
• nested relations
• normalization
• complexity

C.R. Categories:

• H.2.1