ASSOCIATION ALGEBRA - A MATHEMATICAL FOUNDATION FOR OBJECT-ORIENTED DATABASES

The application of the object-oriented (O-O) paradigm in the database management field has gained much attention in recent years. Several ex perimental and commercial O-O database management systems have become available. However, the existing O-O DBMS's still lack a solid mathema tical foundation for the manipulation of O-O databases, the optimizati on of queries, and the design and selection of storage structures for supporting O-O database manipulations. This paper presents an associat ion algebra (A-algebra) to serve as a mathematical foundation for proc essing O-O databases, which is analogous to the relational algebra use d for processing relational databases. In this algebra, objects and th eir associations in an O-O database are uniformly represented by assoc iation patterns which are manipulated by a number of operators to prod uce other association patterns. Different from the relational algebra, in which set operations operate on relations with union-compatible st ructures, the A-algebra operators can operate on association patterns of homogeneous and heterogeneous structures. Different from the tradit ional record-based relational processing, the A-algebra allows very co mplex patterns of object associations to be directly manipulated. In t his paper, the pattern-based query formulation and the A-algebra opera tors are described. Some mathematical properties of the algebraic oper ators are presented together with their application in query decomposi tion and optimization. The completeness of the A-algebra is also defin ed and proven. The A-algebra has been used as the basis for the design and implementation of an object-oriented query language, OQL, which i s the query language used in a prototype Knowledge Base Management Sys tem OSAM.KBMS.