Complex objects: theory and practice from a data- and knowledge-engineering perspective, as seen in and from Yellowstone Park

Abstract Complex Objects as introduced by Bancilhon and Khoshafian, more than ten years ago, can be considered as extensions of tuples in a relational database. Their structure is a tree where the leaf nodes are constants and the inner nodes are either sets or tuples. There is one operation defined, ⩽, which determines whether one complex object is contained in another one. A query of the form: is a piece of information x contained in a database DB, can simply be formulated as ‘ x ⩽ DB’. On the basis of the ⩽ operation a lattice is defined. The lower upper bound of two complex objects x and ν is the operator, ‘+’ which will be shown to be equivalent to the operation ‘adding x to y ’. Similarly a ‘∗’ operation being the greatest lower bound can be defined for two complex objects and determines the information common to the two objects. It will also be shown that rules can be introduced very easily. By means of this the notions of deductive databases and data mining can be defined in a natural way.