Disclaimer: This survey is not finished work, and its discussion may not even reflect my current beliefs. It has been put online as a service to the web community, and should be useful as at least the references are correct!

1. Introduction
   
2. Background
   
   1. Object Data Model
   2. Object Ownership and Sharing
   3. Query Predicates
   4. Query Side Effects
   5. Query Algebras and Calculi
   6. Divergence from SQL
   7. Proposed Query Languages
3. Current Status
   
   1. ODMG-93 OQL
   2. Object SQL or SQL3
   3. Some Examples
4. Future Directions
   
   1. Candidate Research Problems
   2. Facing Up to Reality
   3. Prospects
5. Annotated References
   

Since those words were written this perception has completely vanished from the OODBMS community. A good query language is now recognized as one of the cornerstones of an OODBMS alongside a sound object-oriented data model with unique object identifiers (OIDs). This change of perception is primarily a result of the OODBMS community coming to two important conclusions:

• The alternatives to a query language are mostly throwbacks to the representation-specific CODASYL queries of first generation DBMSs.
• Users really demand an SQL-like declarative query language.

Early efforts at OODBMSs, and query languages for them, centered around making particular object-oriented programming languages persistent. A good example of this is the O++ Database Programming Language [Agr93], which, not surprisingly, is an extension of C++ with support for persistent objects. These persistent languages provided support for user queries through the programming language itself, or simple preprocessor extensions of it. The queries written in these languages were therefore completely non-declarative, indeed usually involving intricate pointer traversal through object members, and completely specific to the internal representation of objects. Even so, as mentioned before, there were many which believed that this was a sufficient querying capability for OODBMSs.

Once the first generation of OODBMS systems had stabilized the OODBMS community realized that better querying capabilities were needed. The discussion in [Ber92] covers the issues recognized at that time as being important in a declarative object-oriented query language. The following subsections look at these issues in some detail.

2.1. Object Data Model

• Classes: Objects are instances of classes, or meta-objects. Classes should be able to have members and methods which are the same for all objects of that class.
• Object Identity: Each object should have a unique object identifier (OID).
• Complex Objects: Objects can be composed of other objects, or various type of collections of other objects (e.g. sets, bags).
• Inheritance: Classes can inherit members and methods from one (or many) other classes.
• Polymorphism: Inherited methods can be overridden and late-binding of method calls can occur based on the object class.

These issues can be resolved by annotating object references with attributes indicating whether the object is owned and/or sharable, and by controlling sharing through a rule system. However, if not done properly, this can lead to the OODBMS equivalent of invalid pointers, and a complete solution may require the OODBMS to do some sort of garbage collection.

As a final point on the object data model, ownership and sharing, the Objects versus Values issue should be mentioned. Some data models distinguish the two and provide special handling for values, with values being structures containing basic data, e.g. the two floats of a complex number. Other data models, most notably [Sar92], treat values as a special unnamed non-sharable object with no methods, providing a simple specification of the structure of a tuple.

2.3. Query Predicates

• Object Equality:. A predicate should be able to use several equality comparisons on objects, most notably equality of OIDs, shallow equality and deep equality. Similar issues surface in object copying, see [Bak93] for an authoritative discussion.
• Object Members: A predicate should be able to query visible members of objects (and classes), perhaps through automatically generated methods, for several conditions, e.g. equality for all members, and membership, inclusion and quantifiers for collection members.
• Method Invocation: We would like to be able to use object (and class) methods in our query predicates. Side effects are an important issue in their use, as discussed below.
• Path Expressions: An expression in a predicate should be able to specify an object by a path of (recursive) object members or methods, e.g. P.name().last = P.mother.name().last. This is an important property of OODBMS queries which is cumbersome to do in conventional relational systems (through the use of joins).
• Class Hierarchy: Predicates should be able to query objects for their place in the class hierarchy, e.g. through IS-A or CLASS-NAME predicates. The issues regarding such queries can be quite complex, depending on the data model, e.g. if multiple inheritance is allowed, or overloading methods with unrelated types as arguments.
• Class Joins We would like to be able to specify queries over joins of classes, e.g. over all Persons and all Vehicles, and we would like to be able to return tuples, of joined class type, as results from queries, e.g. tuple(person, vehicle).
• Recursive Queries An object-oriented query predicate should at least be able to do simple recursion, e.g. to specify all managers of an employee, the managers themselves being employees.

Not all OODBMS systems enforce this rule in the same way. Some do not enforce it at all, allowing the user to call any methods in queries, without specifying the resulting behavior, others allow insertion but not deletion or modification, while yet others do not allow method calls in queries at all. A happy medium would seem to be to allow the evaluation of side-effect-free methods in user queries, although this requires the method implementation or definition language to be able to express side effect ``freeness''.

2.5. Query Algebras and Calculi

An important additional constraint on an object-oriented query language, and its associated algebra and calculus, is that the language be closed. This means that the results of queries need to representable in the database, and thereby processable by other queries, allowing the nesting and recursion of queries.

It can be argued that the success of the relational database model has been largely due to its sound closed relational algebra and rewrite calculus. Therefore there is a consensus in the database community that any ``real'' OODBMS, or, more generally, any next-generation database system, needs to have both and algebra and a calculus.

There have been several algebras and calculi proposed for OODBMSs, e.g. those in [Ala89], [Str91], [Ber92], [Fer93], [Leu93], [Fer95] and [Cer95], most of which focus on algebras and calculi suitable for efficient optimization of queries (see chapter 29).

2.6. Divergence from SQL

• Values: In an RDBMS the atomic data element is a value, with no concept of identity. OODBMS have to provide objects with OIDs and have to deal with complex semantics of equivalence and copying.
• Members: An OODBMS object can have members which contain references, even collections of references to other objects. In an RDBMS this needs to be done by adding relations and performing numerous joins. The concepts of ownership and sharing need to be enforced with an external rule system in an RDBMS.
• Methods: Methods are not supported at all in traditional RDBMSs. Some third-generation RDBMS, such as POSTGRES, provide query expression as a datatype, but this is very kludgey and difficult to typecheck and optimize.
• Derived Data: Derived data, in the terminology of DAPLEX [Shi81], is fully supported with methods in OODBMS. RDBMSs have some limited support for derived data through the use of views, which are a form of query.
• Class Hierarchy: The notion of inheritance relations between relations is not supported at all in traditional RDBMSs, while fully supported in all OODBMSs.
• Joins: OODBMSs queries can preform joins on complex objects using several types of equivalence, while RDBMSs can only perform joins on simple atomic attributes.
• Recursion: OODBMSs queries support at least simple linear recursion, supported by a simple notation in the query language, while SQL and most other RDBMS query languages do not support recursion at all.
• Extendibility: OODBMS query languages are infinitely extensible in the number of types supported, through inheritance, and the predicates supported, through member functions. RDBMS, with their SQL, are not extensible at all.

The proposals in the literature, which, as can be seen, tend to be named OQL, include the following ones:

• OQL [Ala89]: This proposal allows only subdatabases to be returned from queries, thus ensuring closure, but disallowing creation of new objects or values.
• O2 [Deu90]: This is another early proposal, distinguishing between values and objects, but supports the creation of new values and is closed with an SQL-like syntax. Had much influence on ODMG-93 OQL.
• EXCESS [Car87]: This proposal has more powerful ownership and sharing features than O2, but is similar in most other respects.
• OQL [Sar92]: This is a very elegant proposal, straddling the bridge between algebra and query language. This OQL avoids the dichotomy of values versus objects, is proved closed and complete, supports recursive queries, has support for complex ownership and sharing, and can be used to implement all the other user-level query languages listed here.
• ODMG-93 OQL [Cat96]: This proposal, which is a combination of O2 and SQL, is described in detail in subsection 3.1.

• Object Meta Data: Meta data about classes, types, operations etc., are available as objects in the database.
• Collections: There are three types of object collections, sets, lists and arrays, each with the usual semantics.
• Class Objects: Each class has a set object containing all instances of that class.
• Objects vs. Values: Queries may return objects in the database, or new values (tuples). There is a clear distinction between the two.
• Closure: The query language is closed, with the capability of querying results of queries.
• Ownership: Only simple types of ownership are supported, with objects owning values.
• Methods: A query can invoke methods in its predicates, and chain them into path expressions.
• Language Ties: The ODMG-93 document specifies how to adapt its data model and query language for use with two general purpose programming languages, C++ and SmallTalk. This is specified in great detail for the two languages, ensuring that all implementations of ODMG-93 are identical in this respect.

The current direction of the standards committee seems to be to make SQL3 a superset of ODMG OQL, with a slightly restricted data model, while retaining all the features of SQL92. A subset of SQL3, combined with POSTQUEL, has actually been implemented in POSTGRES95, a derivative of POSTGRES.

3.3. Some Examples

     SELECT car 
     FROM car IN Cars 
     WHERE car.car_manufacturer.country = "Germany"

     SELECT o 
     FROM u IN Users.users,
          o IN u.orders 
     WHERE o.date.month = 4
           AND o.date.year = 1996

     SELECT component
     FROM car_manufacturer IN CarManufacturers,
          car IN car_manufacturer.cars,
          principal_characteristic IN car.characteristics,
          component IN principal_characteristic.components 
     WHERE car_manufacturer.name == "Mercedes"
	   AND car.name == "500"
	   AND principal_characteristic.name = "Engine"
	   AND component.name like "Air*"

     SELECT distinct struct( n: p.name )
     FROM p IN Employees
     WHERE p.age > 50

It must first be stated that any future research in OODBMS query languages is most likely to take place in industry, rather than academia. This has historically been the case with RDBMS query languages, with SQL, QBE etc., being developed in industry and is very likely to be the case in the future for OODBMS query languages. Academic researchers, in fact, have explicitly stated (see [Car87]) that they do not want the task of developing query languages, and the quick universal acceptance of ODMG-93 OQL serves as proof of this fact. Academic research in algebras and calculi, however, will probably continue undaunted for a while, as a part of query optimization.

4.1. Candidate Research Problems

This situation is probably not likely to change to a great extent in the near future, at least not in the conventional database setting. Users and managers of databases are used to SQL-like queries and are quite satisfied with the support OQL gives them, even if they may be unsatisfied with the speed of the query processing.

The area which may become important in research on OODBMS query languages is that of queries by end-users, people who may not even be really aware that they are accessing a database. As object-oriented techniques continue to proliferate in all areas of computing, the need to query large collections of objects will become a major issue for end users. Research in this area will be closely tied to that of research in user interfaces, since the query language will be a part of the user interface for the end users. The following is a list of possible candidate topics:

1. A New Super-Duper OODBMS Query Language: The construction and universal acceptance of a new theoretically sound and complete OODBMS query language with more expressive power and without the inherited problems from SQL (which OQL has) is without a doubt a worthy topic.
2. Polishing ODMG-93 OQL: There are several areas where the language is not very strong, especially in its objects-vs-values dichotomy and its lack of support for complex ownership.
3. Connection to Rule Systems: Queries and updates are bound to trigger rules, and vice-versa. There needs to be a better synergy between the two, e.g. through a similar syntax and tight integration.
4. Graphical Query Construction: Construction of queries via a graphical interface, either in a constructive OQL like query-tree format, or in a drag-and-drop Query-by-Example associative graphs format of some sort, is likely to be successful as an ad-hoc query builder for end users, just as QBE has been for RDBMSs.

1. Demand for the research.
2. The possible benefits from the research.
3. The likelihood of major discoveries.
4. The likely time span of the research.

This situation forces us to eliminate candidate 1, the construction of a completely new query language. There simply isn't any motivation for it in the OODBMS community. There isn't much demand for the research, the benefits for actual users are not major, the possibility of major breakthroughs is very small and the time span of the research is probably long, since all new languages have to be implemented and used to be fully evaluated.

Candidate 2 also fails most of our criteria, but is likely to be realized even so, given its incremental nature. There will undoubtedly be future versions of ODMG OQL and those versions will be modified in ways dictated by the user community. These incremental changes will be done almost automatically as OODBMSs mature and develop.

The interfacing of query languages with rule systems, candidate 3, is an area where there isn't really much demand as of yet, since there are very few databases which provide good support for rule systems. There is however already much demand for such systems and they will therefore probably be incorporated into OODBMSs in the near future. When this happens there will undoubtedly be demand for tighter integration with the query language. There are however no major benefits to be gained from this research, nor major discoveries in sight, and a simple de-facto standard is likely to be developed and accepted over a fairly short period of time.

The last candidate is the most promising one. The demand for research on the issue may not be overwhelming at this time, but its time is undoubtedly ripe. In the near future millions of users worldwide will be working with most of their data in terms of objects, be it within application software like CAD systems or spreadsheets, or just in the file storage system. As computers become networked onto the World Wide Web they will have access to more and more information, most of which can be viewed as objects of different types and interconnections.

There are currently no really good methods for querying by end users of object-oriented information, the most popular solutions being the glorified GREP query-by-keyword systems which do full-text searches on the data. The benefit of an end-user query system which allows the user to build non-trivial queries which make use of the full object types and interconnections are tremendous.

This is likely to be a somewhat long-term research project, as user-interface research doesn't usually live up to its full potential until decades after the initial work on it started (e.g. the mouse and GUI). Also the likelihood of any major discoveries seems small, the best one could hope for is an easily used graphical object-oriented equivalent of Query By Example. Even so this is a very important research area since any advances, however small they may seem, are likely to effect the every day work of millions of users.

4.3. Prospects

Candidate 3, the development of a good end-user OODBMS query mechanism, will not resolve itself by incremental changes to existing technology. Its development requires strong industrial backing and very possibly paradigm shifts from existing query mechanism. The best setting for this research and development would probably be an industrial research lab with top-notch database and user interface researchers, generous funding and well defined goals. Optimally there should be several such groups at several companies exploring different approaches.

Undoubtedly there is a better intuitive way of querying OODBMSs through graphical QBE-like interfaces than the form-based GREP utilities of today. Therefore we must conclude that the chances of the research being successful are very high. It is easy to measure this success; if the majority of end users in 5 to 10 years are using a powerful and intuitive query mechanism to perform searches on their local and non-local data our goals have been accomplished.

This paper describes the authors experience in the design, implementation and continued development of O++, written very late in the project. O++ is a good representative of very early OODBMSs.

Alashqur, A.M., Su, S.Y.W. and Lam, H., ``OQL: A Query Language for Manipulating Object-Oriented Databases'', Proceedings of the Fifteenth International Conference on Very Large Data Bases, Amsterdam, Holland, August 1989.

This paper describes an OODBMS query language, OQL (not to be confused with other OQLs), which achieves closure by returning a subdatabase as the result of queries.

Atkinson, M. P., Bancilhon, F., DeWitt, D., Dittrich, K., Maier, D., and Zdonik, S., `` The Object-Oriented Database System Manifesto'', Proc. First International Conference on Deductive and Object-Oriented Databases, Kyoto, Japan, December 1989.

This paper summarizes the (somewhat unformed) very early views and expectations of OODBMSs. The paper should not be read as a description of the current view of OODBMSs, but rather as an historical document giving insight into the motivation and early foundation of OODBMS research.

Baker, H., `` Equal Rights for Functional Objects or, The More Things Change, The More They Are The Same'', OOPS Messenger, Vol. 4, No. 4, pp. 1 - 26, October, 1993.

This paper gives a good overview of the problem of determining object equality, describes most of the previous work in the area, and gives a ``perfect'' algorithm for performing the comparison.

Bertino, E., Negri, M., Pelagatti, G. and Sbattella, L., ``Object-Oriented Query Languages: The Notion and Issues'', IEEE Transactions on Knowledge and Data Engineering, Vol. 4, No. 3, pp. 223, June 1992.

This paper is an excellent discussion of the issues involved in the design and implementation of an object-oriented query language. The paper was written at a time (1989) when the OODBMS community was just realizing the importance of query languages, even though it was not published until much later.

Carey, M.J., DeWitt, D.J., Vandenberg, S.L., `` A Data Model and Query Language for EXODUS'', Technical Report CS-TR-87-734, University of Wisconsin, Madison, 1987.

This paper describes an early attempt at a declarative query language, EXCESS, for the research OODBMS EXODUS.

The Object Database Standard: ODMG-93, Release 1.2, edited by R.G.G. Cattell, ISBN 1-55860-396-4, Morgan Kaufmann Publishers, 1996.

Contains the Object Database Management Group specification of OQL, an Object Query Language based on the query language of O2 [Deu90]. This OQL is today's (1996) definitive object-oriented query language, supported by most commercial OODBMSs, as well as most research OODBMSs, such as Thor.

Deux, O., et al., ``The Story of O2'', IEEE Transactions on Knowledge and Data Engineering, Vol. 2., No. 1, pp. 91, March 1990.

This paper describes O2 (O subscript 2), an early OODBMS system. The system has had far reaching influences on OODBMSs, most notably on the query language ODMG-93 OQL, [Cat96]. The query language of O2 is a simple closed extension of SQL allowing construction of new values as results of queries, while distinguishing between objects and values.

Sarkar, M., Reiss, S. P., `` A Data Model and A Query Language for Object-Oriented Databases'', Technical Report CS-92-57, Brown University, December 1992.

This paper presents a fairly advanced query language (and an associated algebra), called OQL (again, do not confuse this with other OQLs), which is more expressive than previous algebras while maintaining closure of query results and allowing such things as recursive queries.

Shipman, D., ``The Functional Data Model and the Data Language DAPLEX'', ACM Transactions on Database Systems, Vol. 6, No. 1, pp. 140, March 1981.

This paper describes the highly influential early semantic data model and query language DAPLEX. The ideas presented in this paper, in the setting of a functional data language, have influenced all later advanced query languages, especially object-oriented ones.