SEMANTICS FOR NULL EXTENDED NESTED RELATIONS

The nested relational model extends the flat relational model by relax ing the first normal form assumption in order to allow the modeling of complex objects. Much of the previous work on the nested relational m odel has concentrated on defining the data structures and query langua ge for the model. The work done on integrity constraints in nested rel ations has mainly focused on characterizing subclasses of nested relat ions and defining normal forms for nested relations with certain desir able properties. In this paper we define the semantics of nested relat ions, which may contain null values, in terms of integrity constraints , called null extended data dependencies, which extend functional depe ndencies and join dependencies encountered in flat relational database theory. We formalize incomplete information in nested relations by al lowing only one unmarked generic null value, whose semantics we do not further specify. The motivation for the choice of a generic null is o ur desire to investigate only fundamental semantics which are common t o all unmarked null types. This leads us to define a preorder on neste d relations, which allows us to measure the relative information conte nt of nested relations. We also define a procedure, called the extende d chase procedure, for testing satisfaction of null extended data depe ndencies and for making inferences by using these null extended data d ependencies. The extended chase procedure is shown to generalize the c lassical chase procedure, which is of major importance in flat relatio nal database theory. As a consequence of our approach we are able to c apture the novel notion of losslessness in nested relations, called he rein null extended lossless decomposition. Finally, we show that the s emantics of nested relations are a natural extension of the semantics of flat relations.