By Won Kim
Confusion reigns as the supervendors tout their respective universal servers, but what describes a true object relational database system?
The era of object/relational database technology began in 1992 with the release of the UniSQL/X unified relational and object-oriented database system. Hewlett-Packard soon followed with OpenODB (later Odapter), an object-management layer built on top of its AllBase relational database (RDB) system. In 1993, Montage Systems (later Illustra) shipped the first commercial version of object/relational Postgres, which placed almost total emphasis on multimedia data management.
These three vendors soon attracted the attention of the trade press and industry analysts. Informix acquired Illustra Technology (mostly for Illustra's DataBlade database extensibility technology), and today, the giant vendors of relational database systems-Oracle, Informix, Sybase, IBM, and Microsoft-have all announced plans to transform their RDB products into object/relational database (ORDB) servers by late 1997. As a result, confusion is sure to reign in the ORDB marketplace for a few reasons.
First of all, because of Informix's acquisition of Illustra and subsequent marketing of DataBlades, an inordinate weight has been placed on the role of data type extensibility in ORDB technology. Second, the measure of a product's "object/relational (OR) completeness"-the degree of its support for OR modeling and management capabilities-is a potentially serious area of perplexity.
A baseline set of requirements a product must satisfy before it can be qualified as an ORDB would alleviate this confusion. Furthermore, it would help customers determine OR completeness should they prefer to license a product that supports 90 percent of these requirements over one that supports only 50 percent.
In this article, I propose a practical metric for OR completeness that can be used as a guideline for determining whether a product is truly an ORDB. This metric comprises seven major categories, each containing primary and secondary capabilities prioritized from "most important" to "least important." These categories include data model, query language, mission-critical database services, object-oriented computational model, performance and scalability requirements, database tools, and what I call "harnessing the power."
The Core Object Model1 defined by the Object Management Group (OMG) comprises the relational data model as well as the core object-oriented modeling concepts of object-oriented programming languages. As such, the OMG model should be the standard. The object model in the emerging SQL3 standard differs somewhat from that of OMG, but the concepts discussed here should apply to SQL3 as well.
1. Class, instance, attribute, method, and integrity constraints
In an OR-complete ORDB, the data model must include the notion of a class (or type) having attributes, methods, and integrity constraints. A class serves as a template for instances that may be created sharing its attributes and methods. The domain of an attribute may be a primitive type of data, an abstract data type, or a reference to a class. An attribute may be atomic or set-valued; a set-valued attribute may have zero or more values. A method is a function that applies to each instance of a class, performing computations based on the values in the attributes. Integrity constraints include primitive constraints supported in RDBs such as the NULL-value specification for an attribute, the UNIQUE constraint for instances of a class, and the PRIMARY KEY constraint on one or more attributes in a class.
2. OID per instance
An instance of a class has a unique and immutable object identifier (OID). The user may submit an OID to the database system to fetch the corresponding instance.
3. Encapsulation
The user should be able to write a method and attach it to a class. An attribute of a class may be regarded as a special method with read-and-update interfaces only.
The language in which a method is written must be a combination of ObjectSQL and a host language. The host language may be a full programming language such as C or C++, or it may be a restricted language much like that used to write stored procedures in RDBs.
4. Multiple inheritance hierarchy of classes and name-conflict resolution
The user must be able to create a class as a subclass of one or more existing superclasses. A subclass inherits attribute specifications and method specifications from all superclasses (multiple inheritance). However, if two or more superclasses have an attribute or method with the same name but different specifications, a "name conflict" will arise.2 Although name conflict makes it problematic, multiple inheritance remains the accepted standard. As a result, an ORDB should support multiple inheritance where a subclass has one or more superclasses.
5. Class reference as domain of an attribute (OID-based object references)
If the domain of an attribute is a reference to a class, the database system actually stores the OID of an instance of the referenced class in the attribute.
An OID is usually implemented as a logical identifier of an object rather than its physical address. Therefore, the use of OIDs in an ORDB (and for that matter, in an OODB) does not require a return to the use of physical pointers in hierarchical and Codasyl databases.
6. Set-valued attributes
A set-valued attribute may store zero or more values and make individual values available for access or update by the user. In RDBs, an attribute may store one value at most; even if it stores more than one value, all values are available to the user as an atomic unit-that is, as a single glob.
A set-valued attribute may hold a standard set (a set with no duplicate elements), a multiset (a set that may include duplicate elements), or a sequence (a multiset in which each element is associated with an ordering within the set).
7. Abstract data types (ADTs)
An ADT is constructed by combining primitive data types. A simple example is a "point" data type that is constructed by combining x and y coordinates, each of which is represented by a floating-point number data type.
An ADT is a special case of a class reference and primitive alphanumeric data type. Like a primitive alphanumeric data type, the value of an ADT is directly stored in the attribute. Like a class reference, it is not a primitive data type. Furthermore, like classes, the users may organize ADTs in an inheritance hierarchy. When the domain of an attribute is a class reference, the database system stores the OID of a referenced instance, which introduces a level of indirection in accessing the referenced instance. The direct storage of the value of an ADT removes this indirection. However, because the value of an ADT is directly stored in an attribute, unlike an instance referenced through its OID, it cannot be shared by more than one instance.
8. Inheritance hierarchy of classes as domain
The set-inclusion semantics associated with an inheritance hierarchy of classes mean that instances of a subclass logically belong to its superclass. For example, if a class Employee is a subclass of a class Person, instances of Employee logically belong to Person (in other words, employees are persons). If the domain of an attribute is specified to be a reference to a class, the domain may include not only references to the instances of the specified class but also to all instances of the inheritance class hierarchy rooted at the class.
9. Class attributes, class methods
An instance of a class is clearly an object. But should a class be treated like an object as well? The answer is yes: Carrying the "everything is an object" philosophy one logical step beyond instances is a good idea, because the user should be allowed to specify attributes and methods that apply to a class, not just to an instance of the class. A class attribute may hold a value that describes the class or all instances of the class collectively, and a class method applies to the class object itself (on the values stored in the class attributes in particular).
Important uses of class attributes (and class methods) include modeling aggregate properties of all instances of a class (average weight of all Automobile instances, for example), the value of an attribute that is the same in all instances (the number of wheels in an Automobile), or the default value of an attribute (to be overridden on an instance-by-instance basis; for example, where the default color of the Automobile body is concerned).
An ORDB must support an ObjectSQL (a database language that's a minimal extension to the relational SQL standard) and its corresponding APIs (function calls). The extensions to SQL are necessary for reading and updating objects that are defined and created using the object modeling capabilities summarized previously. If the user does not need any object modeling capabilities to design the database, SQL should be used. In other words, the ObjectSQL language must be strictly backward compatible with SQL.
Two proposals are on the table for a standard ObjectSQL: SQL3 and Object Query Language (OQL). Efforts to merge the languages into a single international standard are ongoing. The SQL3 standard being formulated by the ANSI X3H2 Committee includes object extensions to the SQL-92 RDB standard. OQL, proposed as part of the evolving Object Data Management Group (ODMG) efforts to standardize object database access languages, is not yet fully compatible with SQL3.3,4
1. SQL-92
Because the current SQL standard is the SQL-92 specification, the ObjectSQL for ORDBs should start with SQL-92 and extend it with query capabilities corresponding to the object-modeling capabilities that the user can use to design the database. Fundamental capabilities of the SQL standard include single-table query statements, multitable joins, nested subqueries, queries with the GROUP BY, HAVING, and ORDER BY options, and queries involving the set union/difference/intersection of queries.
2. Query involving nested objects
If the user creates a class (class-1) with an attribute whose domain is a reference to another class (class-2), and creates instances of the classes, the database system will store the OID of an instance of class-2 in the attribute of class-1, thereby linking an instance of class-1 to an instance of class-2. The user should be able to issue a query that retrieves instances of class-1 on the basis of search conditions on instances of class-2, or to fetch instances of class-2 linked to instances of class-1 (satisfying search conditions on instances of class-1). A query construct known as a "path expression" would enable the user to specify search conditions on a sequence of classes linked through the domains of attributes.5
3. Query involving set-valued attributes
If the user defines a set-valued attribute and inserts a set of values in the attribute, the user should be able to retrieve and update any element or any subset of the set individually or collectively. The user should be able to express this capability as part of the ObjectSQL query statement. The "derived table" construct in SQL-92 is a good basis for supporting this capability, but it currently lacks the facility to fully manipulate set elements.
4. Query involving methods/functions in search predicates
The user should be able to include a method anywhere a function or attribute may legitimately appear in a query statement. The database system should load and execute the method and return the result for use in completing query execution.
5. Query involving an abstract data type
The user should be able to include a search condition on any attribute regardless of its domain. Just as the user of an RDB may write a query with a search condition on any attribute in a table, an ORDB user should be able to write a query with a search condition on an attribute whose domain is an ADT.
6. Views
A "view" is a subset of a database that satisfies user-defined query conditions; its contents are created when the query defining it is evaluated. In RDBs, a view is logically equivalent to a table in that the user may issue a query against a view or grant and revoke authorizations on a view.
In ORDBs, views are not equivalent to classes, although they're needed for the same reasons. Just as with RDBs, ORDB users should be able to issue a query against a view as well as grant and revoke authorizations on a view. A view may be defined by specifying query conditions that account for object extensions.
7. Query involving an inheritance hierarchy
As I discussed previously, the set-inclusion semantics (or the IS-A relationship) associated with an inheritance hierarchy of classes means that a class may "logically include" all of its own instances and all instances of all of its subclasses. Therefore, a query against a class may have to be evaluated against all instances of that class or against all instances of an inheritance hierarchy rooted at that class. The user should be able to specify the desired result. Furthermore, it's often useful to exclude some of the classes in an inheritance hierarchy from query evaluation.
The object extensions to the relational model have far-reaching consequences on database architecture.6 In other words, to fully account for object extensions in an RDB, new components must be added and existing major components modified. For example, the fact that an ObjectSQL query may include a path expression in its search conditions means that the query optimizer must be extended to account for the expression. Furthermore, users may submit OIDs to fetch corresponding objects, so the database system should be able to maintain an extensible hash table for mapping OIDs to physical addresses of objects. And the fact that users may wish to share large documents as objects suggests that authorization should occur at the object level rather than the attribute or table level supported by RDBs.
Some of the required capabilities of an extended RDB are to follow. Database services such as crash recovery, replication service, and fault tolerance are not discussed here, because object extensions have no impact on them. (However, I categorize recovery as a primary capability and fault tolerance and replication service as secondary capabilities.)
1. Automatic query optimization and query processing
The query optimizer in ORDBs must include all key techniques incorporated in RDB query optimizers, including the generation of all reasonable query execution plans, selection of an optimal plan based on estimation of expected query execution costs, the use of query-execution access methods (indexes and sorting), joins via the nested-loop or sort-merge algorithms, and use of database statistics in cost estimation.
A query containing a path expression is often best evaluated by a straight depth-first search technique in recursively following OIDs that reference objects. In other words, an ORDB should not attempt to process a query containing a path expression using the conventional nested-loop or sort-merge join techniques. Therefore, the query optimizer in an RDB must be extended to account for the processing of a path expression in an ORDB query. An ORDB must also implement a storage and access mechanism for values in a set-valued attribute.
A method may be executed on the client or server (or both) in a client/server architecture. The query optimizer in an ORDB must generate a query-execution plan for minimizing data transfer between client and server when executing a query that includes a method. It is very difficult to design a query optimizer that automatically estimates the selectivity of a search condition (the proportion of the number of objects satisfying a search condition in relation to all objects in the search space of a query) involving a method. At the very least, the query optimizer must be designed to minimize the amount of data fetched from the database by prioritizing search conditions, with those involving methods having first priority.
2. Indexing on abstract data types
RDBs enable users to create indexes that make the query processor limit database search space to a minimum. These databases use a B+ tree structure to organize the indexes. But indexes have been used only for alphanumeric data-that is, only on attributes whose domains are alphanumeric data types. Extending the concept of indexing to attributes whose domains are any user-defined ADTs is an important goal. For spatial data (such as rectangles and lines), index structures such as R-trees (and their variants), grid files, and k-d trees are well known.
3. Concurrency control
ORDBs must fully support all the techniques that have been incorporated into RDBs, including two-phase locking, lock acquisition and release protocols, granularity locking, hierarchy locking, logical locking and physical locking, and lock modes.
Object extensions require a couple of additions. Supporting a query involving an inheritance hierarchy of classes, and dynamic evolution of such a hierarchy, requires extensions to the lock-based concurrency control mechanism currently supported in RDBs. Simply put, an inheritance hierarchy rooted at a particular class should be locked as a unit to avoid certain undesirable situations.7
The fact that an ORDB user can submit an OID to access a single object means that a single object-rather than a single disk page or class-should be the smallest unit of locking in an ORDB.
4. Authorization
An ORDB must support the full authorization mechanism supported in RDBs, including authorization on an attribute, class, or view; recursive granting and revoking of authorizations; granting of authorization on individuals, groups, or the public; authorization on resources; and so on.
Object extensions suggest the addition of authorization involving the execution of methods and authorization on a single object. The fact that an ORDB user can submit an OID to access a single object is an important departure from a basic tenet of RDBs: Queries can't be written against single records in a table, only against the table itself. In contrast, the smallest unit of access in an ORDB (and OODB) is a single object. Thus, as with locking, a single object should be the smallest unit of authorization in an ORDB.
5. Triggers
Triggers are as important for ORDBs as they are for RDBs. But object extensions do not require any significant additions other than the ability to invoke methods as part of the triggered actions.
6. Stored procedure
Methods in ORDBs are attached to specific classes and inherited into subclasses. Furthermore, methods may execute on the client as well as the server. Stored procedures are as important in ORDBs as they are in RDBs. In an RDB, a stored procedure is not attached to any table and is therefore not inherited from one table to another. But in an ORDB, a stored procedure may be regarded as a server-based method attached to the database as a whole, not to any particular class.
7. Dynamic schema evolution
RDBs let users make dynamic changes to the database schema; these changes are typically limited to adding or dropping a table and adding or dropping a table attribute. An ORDB schema has more constructs than an RDB schema, and as such, more elements of the schema may have to be dynamically changed. These elements include adding and dropping a method to a class, adding and dropping a superclass/subclass relationship between two classes, and even changing the domain of an attribute.2
8. Mandatory security
Support for mandatory security has always been an important issue for government and military users of database systems. The object extensions in ORDBs make this goal much more difficult than for RDBs. The difficulties arise primarily from the use of methods and OIDs.
Various applications-such as computer-aided analysis, design, simulation, and testing-can perform operations on a large amount of data in memory. These applications manage a large number of objects and must perform extensive computations very quickly, so objects must be in memory and prelinked. OODBs are designed to meet the performance demands of such applications with the added assumption that they're written in an object-oriented programming language.
To support fast navigational access to memory-resident objects, OODBs provide the ability to automatically manage a large number of objects in memory (called a "live cache" or "object buffer pool"). Specifically, OODBs automatically convert the storage format of objects between the database format and the memory format, convert the OIDs stored in objects to memory pointers when objects are loaded into memory (the conversion process is often called "pointer swizzling"), and flush (write) objects updated in memory to the database when the transaction that updated them finishes. The dangers of exposing memory pointers to the applications can be minimized by exposing pointers to descriptors for memory pointers, rather than memory pointers to objects.
RDBs do not support pointer swizzling or live cache management. Therefore, RDB applications must resort to explicit queries that either join two tables or at least search a table to emulate simple navigation of objects. Furthermore, RDB applications must also propagate updated records to the database one at a time via the RDB interface.
In ORDBs, ObjectSQL query statements and API function calls can be used in combination. An ObjectSQL query may be used to load objects in the query result in the live cache; subsequent API calls may load additional objects referenced by the objects already in the cache. In this process, object format transformation, pointer swizzling, transfer of objects from database to the live cache, and garbage collection and swapping of objects between the live cache and database should all happen automatically. The End Transaction statement will automatically flush updated objects to the database.
ORDBs should be targeted to those database market segments in which pure RDBs are not a good fit due to deficiencies in complex data modeling and multimedia data management, as well as in those segments that OODBs fail to satisfy because of poor scalability or mission-critical database services.
Required performance requirements for an ORDB are described as follows. Because the performance of a database system ultimately determines its acceptance, these requirements are primary capabilities.
Scalability is closely related to performance; the performance (throughput and/or response time) of a database server should scale gracefully as more disks and processors are added. To support large databases and a large number of users, ORDBs must also match the level of scalability that RDBs have recently achieved. Major RDBs now run on a three-tier client/server architecture and are connected to TP monitors (Tuxedo, Encina, TopEnd) to support a large number of users. For increased throughput, RDBs run on symmetric multiprocessors (SMPs), clusters, and even massively parallel processors (MPPs). RDBs also employ parallelism techniques such as a multiple server process architecture (in which each process controls multiple threads), asynchronous disk I/O, parallel I/O, parallelization of a query, and parallelization of database utility functions (index build, backup, restore, database compaction, database statistics update, and bulk load).
All these scalability techniques are important and should ultimately be incorporated into ORDBs. However, because some should be incorporated before others, they can be classified into primary and secondary categories. (Support for MPPs may not be necessary given recent advances in SMP and cluster technology.)
RDB users have learned that they need a variety of database tools-aside from the bare database server with its SQL and API interface-to support the application development cycle. These tools include:
In general, tools for ORDBs should extend the functionality of comparable RDB tools to account for the object-modeling extensions to the RDB. In the absence of ORDB-specific tools, at the very least ORDBs should be interfaced to popular third-party RDB products to exploit or account for object-modeling capabilities.
The following summarizes necessary object extensions to the functionality available in RDB database tools. The object modeling capabilities that are most important and relevant from the perspective of users are set-valued attributes, ADTs, and nested objects; inheritance hierarchy and methods are not as important. Because database tools have become an integral part of an application development environment, most of their capabilities are primary ones. And because database tools in general have numerous features for functionality and usability, I will not classify them here beyond indicating the types of tools and object capabilities for which they should account.
A database browser/designer must enable the users to edit and view an ORDB schema that accounts for an inheritance hierarchy of classes-a class forming a nested hierarchy of classes via attributes whose domains are references to other classes, set-valued attributes, methods, and ADT-valued attributes.
A query generator must enable the users to construct object extensions to SQL and view the results of queries that return set-valued attributes, ADT-valued attributes, nested objects, and instances from an inheritance hierarchy of classes.
A 4GL development tool must enable the users to design screens that deal with set-valued attributes, ADT-valued attributes, and nested objects.
A database administration tool must be extended to recognize at least query-execution plans that account for path expressions, methods, and inheritance hierarchy, as well as the live cache resource.
The ODBC standard developed by Microsoft and Apple is used as the RDB interface for a variety of PC-based applications. If these applications are to be upgraded to use some of the object extensions in ORDBs, ODBC must be enhanced to account for such extensions.
Today, Web browsers and Web authoring tools are effecting significant change in application development environments. This change may obviate the need for some of the tools that have been part of the traditional application development environment.
The object extensions in ORDBs have at least two important benefits for database users beyond the additional data modeling and management capabilities I've described: database extensibility and heterogeneous database fusion.
Database extensibility has received a lot of publicity under the names DataBlades, Database Extenders, and Data Cartridges. Heterogeneous database fusion has received relatively less exposure but is just as powerful. However, because both capabilities lie outside the scope of an ORDB server, I regard them as secondary.
1. Database extensibility
Database extensibility has been oversold by Illustra and Informix, to the point that some people believe that adding DataBlades or other "extenders" to an RDB makes it an ORDB. Of course, adding DataBlades to a database server is not a bad thing-on the contrary. But don't lose sight of the fact that an ORDB must provide most of the data modeling and management capabilities I've described, and that DataBlades are simply secondary capabilities that make an ORDB even more powerful and useful.
In general, database extensibility implies the ability to add any new capability (query-processing algorithms, new lock modes, and new access methods, for example) to a commercial database server. However, for most practical purposes, extensibility actually involves the ability of users (not vendors) to add new data management modules, data types (classes), and operations (methods). A new data management module can be a third-party data source (image or text files) or an engine for managing the data source (an image pattern search engine or a full-text retrieval engine). The objective of database extensibility is to bring all of the benefits of a database server (including query processing and locking) to the management of the new data made available to users.
The ability to add new types of data and operations is merely a logical consequence of the object-oriented paradigm, which enables the creation of new classes with attributes and methods while inheriting from existing classes. Thus the practical importance of database extensibility lies not just in the users' ability to add new data management modules or new types of data, but also in the availability of a fairly extensive function library for specific types of data that vendors (not users) provide. The functions associated with a particular type of data may be classified under "application" or "access method": Application functions perform application logic on the data retrieved from the database; access method functions perform the storage, search, and maintenance of the data in the database.
Application functions are legitimate and useful features that application developers should be able to add to the vendor-supplied function library. Although nonvendors can add some types of third-party access methods (image pattern search indexing and full-text search indexing, for example), it is generally difficult if not impossible to add access methods for arbitrary types of data.
For example, suppose that a user wants to add an R-tree index to an ORDB server as an access method for supporting geometry data. How will the query optimizer in the ORDB recognize that an R-tree index now exists? Even if the query optimizer recognizes it, how will it know the R-tree index's selectivity in optimizing a geometry query? Furthermore, how will the transaction manager perform the recovery and concurrency control functions associated with R-tree index pages in cases of concurrent access, index page split and merging, and system crash?
2. Heterogeneous Database Fusion
The ORDB model is by definition a "combination" of the relational data model and an object model. The object model includes key data modeling concepts used in hierarchical and Codasyl databases such as repeating group (set-valued attributes) and pointer-based navigation (OID-based navigation). Therefore, the ORDB model is ideal for a global schema that unifies (integrates) the schemas of all existing heterogeneous databases, including RDBs, OODBs, hierarchical databases, Codasyl databases, and even flat files.
An ORDB that is extended with the following capabilities meets the requirements of a multidatabase system (MDBS) for database fusion.8, 9
An MDBS is logically a full generalization of a gateway; physically, it controls multiple gateways through which remote databases are managed. An MDBS may have its own database as well; for example, the data retrieved from remote databases may be stored in the native database of the MDBS-the essence of data warehouses or data marts. In any case, an MDBS presents the multiple remote databases as a single "virtual" database to its users.
REFERENCES
1. Object Management Group. "The Common Object Request Broker: Architecture and Specification." Framingham, Massachusetts, 1991.
2. Banerjee, J., W. Kim, H. Kim, and H. Korth. "Semantics and Implementation of Schema Evolution in Object-Oriented Databases." Proc. ACM SIGMOD Intl. Conf. on Management of Data, San Francisco, 1987.
3. Object Data Management Group. "Object-Oriented Database Standard." Benjamin Kaufmann, 1993.
4. Kim, W. "Observations on the ODMG-93 Proposal for an Object-
Oriented Database Language." ACM SIGMOD Record, March 1994.
5. Kifer, M., W. Kim, and Y. Sagiv. "Querying Object-Oriented Databases." Proc. ACM SIGMOD Intl. Conf. on Management of Data, San Diego, 1992.
6. Kim, W. Introduction to Object-Oriented Databases. MIT Press, 1990.
7. Garza, J. F., and W. Kim. "Transaction Management in an Object-Oriented Database System." Proc. ACM SIGMOD Intl Conf. on Management of Data, Chicago, 1988.
8. Batini, C., M. Lenzerini, and S. Navathe. "A Comparative Analysis of Methodologies for Database Schema Integration." ACM Computing Surveys, December 1986.
9. Litwin, W., L. Mark, and N. Roussopoulos. "Interoperability of
Multiple Autonomous Databases." ACM Computing Surveys, September 1990.
Won Kim is the founder of UniSQL Inc. (Austin, Texas), as well as
the current chairman of the ACM SIGMOD, editor-in-chief of the ACM's Transactions
on Database Systems, and an ACM Fellow. Dr. Kim is also the author of Introduction
to Object-Oriented Databases (MIT Press, 1990) and editor of Modern Database
Systems (Addison-Wesley, 1995).