Normalisation in the Presence of Lists

Link, S. and Hartmann, S.

    In the relational data model (RDM), normal forms are conditions for elation schemata that a database design should satisfy to ensure an absence of processing difficulties with the database. One prime example of such a normal form is the Boyce-Codd normal form guaranteeing the absence of redundancies and update anomalies caused by functional dependencies (FDs). Many different data models have been introduced over the years trying to capture data beyond relational structures. The success of those advanced data models will depend, in particular , on the study of normal forms. IN fact, finding a unifying framework and extending achievements of relational databases to deal with advanced database features such as complex object types are currently two major challenges in database design (Biskup 1995, Biskup 1998). Such a unifying approach, capturing various different data models at a time, can be based on the type systems underlying the various data models. In the present paper, we study normalization in the presence of base, record and finite list types. Nested lists are used as a data structure whenever order matters. List types are therefor supported by many advanced data models such as genomic sequence, deductive and object-oriented data models including XML. On the basis of a finite axiomatisation of FDs in the presence of lists the Nested List Normal Form (NLNF) is proposed as a weaker normal form than BCNF. This proposal is semantically justified by formally proving the LNF is equivalent to the absence of redundancy. Moreover, NLNF is equivalent to the absence of strong insertion and most forms of replacement anomalies, and sufficient for the absence of all types of update anomalies.
Cite as: Link, S. and Hartmann, S. (2004). Normalisation in the Presence of Lists. In Proc. Fifteenth Australasian Database Conference (ADC2004), Dunedin, New Zealand. CRPIT, 27. Schewe, K.-D. and Williams, H. E., Eds. ACS. 49-60.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS