Finding Compact Scheme Forests in Nested Normal Form Is NP-Hard

AbstractIn traditional relational databases, the data are stored in "flat" tables. Query processing performance is dominated by the cost of joining such tables. By contrast, nested relational structures can avoid joins. If, however, such structures are decomposed into nested normal form (NNF) then the number of normal scheme trees in the resulting nested scheme forest may dominate query processing performance. Thus, minimizing the number of such trees is an important design goal. We prove that the problem of finding a succinct NNF scheme forest is NP-hard even for the class of sets of unary multivalued dependencies, which is a subclass of the class of split-free sets of multivalued dependencies