next up previous
Next: 8 History and Current Up: Schema and Tuple Trees: Previous: 6 Presentation

7 Related Work

Schema and tuple trees are related to nested relations and object-oriented databases. Nested relations [Makinouchi 1977, Jaeschke & Schek 1982] are relations that have non-atomic attributes, that is, they are not in the First Normal Form (1NF). Nested relations are also called tex2html_wrap_inline681 (Non First Normal Form) relations. It has been realized for some time that tex2html_wrap_inline681 relations can be decomposed into 1NF relations [Korth & Silberschatz 1991].

Other researchers have used the term scheme tree in a way different from ours. For example, they can represent nested relations, where the nodes are pairwise-disjoint sets of non-nested attributes and the edges represent multivalued dependencies [Ozsoyoglu & Yuan 1987]. Some implementations of nested relations include AIM-P [Pistor & Dadam 1989], VERSO [Schoil et al. 1989], ANDA [Deshpande & Gucht 1989], and DASDBS [Schek & Scholl 1989]. These implementations appear to use linked tables as the underlying data structure, although DASDBS seems to perform some optimization by storing related rows within a table close together.

Object-oriented databases [Kroha 1993, Korth & Silberschatz 1991] mix object-oriented programming practices with databases. Typically, objects are schemas written in a fashion similar to a C++ class containing members such as constructors, methods, and variables. Objects may be derived from other objects through inheritance. Since object-oriented databases allow arbitrary recursive structures, it can be quite difficult to map them into the relational model. Object-oriented programming techniques can be used without inheritance or extensible data types in a relational database [Premerlani et al. 1990]. Typically, object-oriented databases are used for applications that do not fit the relational model well, such as CAD (computer aided design). Some implementations of object-oriented databases include tex2html_wrap_inline687 [Lecluse et al. 1988] and Gemstone [Maier et al. 1986].

Herrin Software Development, Inc.