Foundation for Object-Oriented Databases
Stanley Y. W. Su, Mingsen Guo, Herman X. Lam · 1993
The application of the object-oriented (0-0) para- digm in the database management field has gained much attention in recent years. Several experimental and commercial 0-0 data- base management systems have become available. However, the existing 0-0 DBMS's still lack a solid mathematical foundation for the manipulation of 0-0 databases, the optimization of queries, and the design and selection of storage structures for supporting 0-0 database manipulations. This paper presents an association algebra (A-algebra) to serve as a mathematical foundation for processing 0-0 databases, which is analogous to the relational algebra used for processing relational databases. In this algebra, objects and their associations in an 0-0 data- base are uniformly represented by association patterns which are manipulated by a number of operators to produce other association patterns. Different from the relational algebra, in which set operations operate on relations with union-compatible structures, the A-algebra operators can operate on association patterns of homogeneous and heterogeneous structures. Different from the traditional record-based relational processing, the A- algebra allows very complex patterns of object associations to be directly manipulated. In this paper, the pattern-based query formulation and the A-algebra operators are described. Some mathematical properties of the algebraic operators are presented together with their application in query decomposition and opti- mization. The completeness of the A-algebra is also defined and proven. The A-algebra has been used as the basis for the design and implementation of an object-oriented query language, OQL, which is the query language used in a prototype Knowledge Base Management System OSAM*.KBMS.