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 (Non First Normal Form) relations. It has been realized for some time that 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
[Lecluse et al. 1988] and Gemstone [Maier et al. 1986].