OBJECT-ORIENTED DATABASE MANAGEMENT SYSTEMS

Object-Oriented Database Management Systems (OODBMSs) have been developed to support new kinds of applications for which semantic and content are represented more efficiently with the object model. Therefore, the OODBMSs present the two main problems:

• Impedance mismatch. It is basically due to two reasons. Firstly, the no suitable abstractions of the operating systems, so when a client object has to invoke a method that is offered by a server object, and both objects are not into the same address space, it is necessary to use the mechanisms that are offered by the operating system, and these mechanisms do not became proper to the object-oriented paradigm since they are oriented to communicate processes. In order to solve this problem an intermediate software is included (e.g. COM or CORBA).

  In the second place, an impedance mismatch is also caused every time that the object-oriented applications need to use the operating system services. The interface services are close to the procedural paradigm, generally in the shape of system calls. A solution can be the use of adaptation layers which encapsulate the operating system interface by means of a class library (e.g. MFC library).

• Interoperability problem between object models. Although different system elements use the object-oriented paradigm, an interoperability problem can exist between them. So, an application implemented using the C++ language, with the C++ object model, can easily interact with its objects, but when it wants to use objects that have been created with another programming language or another object-oriented database an interoperability problem appears. It is due to the fact that an object model for an element is not necessarily compatible with the object model of other elements. This problem can be solved adding software layers, again. So, CORBA defines a proper object model with basic data types, and a mapping is specified between the object model of each language and its interface into the CORBA model.

Besides, object-orientation is reduced to wrappers in quite a number of commercial DBMSs (Persistence, UniSQL, Illustra, Omniscience, etc.). These systems, named "object-relational", are based on traditional relational models. In these cases the impedance mismatch is again reduced adding a software layer that is the responsible for the assembling/disassembling of objects into tables.

Object-Oriented Integral System

As mentioned, the interoperability problem and the impedance mismatch can be solved generating a proliferation of additional software layers that reduce system portability and flexibility. In fact, extra complexity is introduced in the system, further reducing global system performance.

Another approach in order to solve these problems is based on the construction of a homogeneous system in which all elements share the same object-oriented paradigm: an Integral Object-Oriented System. Oviedo3 is a research project that tries to build an experimental integral object-oriented system based on that foundation. All components: user interfaces, applications, languages, compilers, databases, …and the operating system itself share the same object-oriented paradigm.

The object-oriented operating system(SO4) provides only one abstraction: objects. Objects can only create new objects from a class or send messages to others. One technique to structure an OOOS aimed to support an integral object-oriented system which offers many advantages is to use an object-oriented abstract machine as the substrate of the OOOS. This machine offers the basic object model and support to all objects of the rest of the system.

Figure 1: Components of the Oviedo3 System, shown in logical order of development.

The OODBMS of the Oviedo3 system, named BDOviedo3, is highly integrated with the abstract machine and the operating system. It shares with them the same object-oriented paradigm. Furthermore, the OODBMS will take advantage of some important features that the operating system transparently achieves like: persistence, concurrency, distribution and security. BDOviedo3 will provide a query processing based on an indexing mechanism that is being currently constructed.

BDOviedo3, the OODBMS

BDOviedo3 is the OODBMS for the Oviedo3 system. As it is an OODBMS provides the features of an object model and all capabilities of a DBMS. The BDOviedo3 object model is the abstract machine object model, and some DBMS capabilities (such as concurrency, persistence, etc.) are supplied by the operating system.

BDOviedo3 is a pure OODBMS. Applications development uses object-oriented analysis and design tools. Then, modeled objects can be directly translated into object-oriented programming languages objects, and finally objects can be directly stored in the database using the abstract machine persistence system.

Nowadays, there are a number of OODBMS (Thor, Poet, ObjectStore, Ode, etc.) and persistent storage managers (Shore, Texas, PSE, etc.). Some of them are commercial as well as research projects of different universities. Shore is a persistent object system, expanding on the basic capabilities of Exodus, that represents a merger of object-oriented database and file system technologies. Texas is an object-oriented persistent storage implemented as a C++ library. Thor is an OODBMS that is intended to run on a heterogeneous collection of machines connected by a communications network. It provides a universe of objects that can be shared by programs written in different programming languages. Poet and ObjectStore are commercial OODBMS that work on C++ and include version-control mechanism, transaction management, etc. Poet works on Java too. Nevertheless, we think that the structure and features mentioned before (abstract machine and operating system) are very suited for an OODBMS and worth to research.

Advantages Taken by Building on the Operating System and the Abstract Machine

The existence of an object-oriented operating system and ultimately of an object-oriented abstract machine provides a set of benefits for the construction of the OODBMS:

• Facilitates its construction. So, the database engine can take advantage of some operating system capabilities, such as: security, persistence, distribution and concurrency, building on them incrementally by means of the object-orientation present in the system.

• Seamless integration with the rest of the system. The OODBMS is not an individual element inside this integral system, like in conventional operating systems. The OODBMS is an integral part of the computation environment. Database objects are objects just like other objets in the system (operating system or user ones). The database only offers convenient access to them. The system is composed of a set of homogeneous objects. The OODBMS can be seen as playing the part of the file system in conventional operating systems, but with database capabilities. The database would not be used in isolation, but as a management system encompassing all objects in the system. For example, a user would find any object uniformly by querying the database.

• Performance increase. It is not necessary to add new software layers to conventional operating systems to fill the semantic gap between operating system abstractions and objects. The integral system is already object-oriented.

• Productivity increase. Building database applications on this system is more productive, since it is not necessary for the programmer to change paradigms. Database and operating system share the same object-oriented paradigm, which is used uniformly in the system. For example, the same query language would be applied to database programming and user interface search tasks.

BDOviedo3 Architecture

The BDOviedo3 OODBMS has been structured into three major modules (Figure 2). A first prototype has been developed. Some of its features are briefly described in the next sections. More advanced features of the OODBMS, such as schema evolution, object versioning, etc. will be considered in future prototypes.

Figure 2: BDOviedo3 Architecture.

• Engine. This module has two main objectives:

  • Query processing. The basic and more complex purpose of this module is the construction of the query-evaluation engine.

  • Storage Management. It is primarily focused on transaction management.

• Languages. The database languages (definition, manipulation and query) for the OODBMS are specified in this module.

• Visual Tools. The main scope of this module is the construction of a visual development environment that allows to interact easy and in an efficient way with the database for a large number of users as possible.

The Engine

This module has two basic functions, query processing and storage management, that will be described in the next paragraphs.

Query Processing

The majority of techniques for processing relational queries need to be extended, and some new techniques need to be developed for processing and optimizing object-oriented database queries. As, OODBMS queries can involve different data types (it makes the design of an object algebra harder), path expressions (an object may have references to other objects) and methods (which make difficult to estimate the cost of executing a query). The existence of class hierarchy represents another problem for the query processor.

Despite the above differences between relational and object-oriented query processing, methodologies for processing relational queries can be adopted for processing object-oriented queries. There are basically two such methodologies, algebra-based optimization and cost estimation-based optimization.

Algebra-based optimization consists of primarily two steps. In the first step, the input query is expressed in an algebraic expression, which is then transformed into a semantically equivalent but more efficient expression using equivalence transformation rules. In the second step, physical characteristics of the database such as the existence of fast access paths and database statistics are taken into consideration to generate a concrete and efficient execution plan for the algebraic expression obtained in the first step. The advantages of this methodology include extensibility and a relative easiness for implementation. The main drawback is that the search space for optimization in the second step is limited by the algebraic expression generated in the first step. So, there is a good possibility that the resulting execution plan is not close to an optimal plan.

The cost estimation-based optimization methodology tries to combine the above two steps as follows. The equivalence transformation rules are used to systematically transform the initial algebraic expression to all reasonable and equivalent expressions, and for each such expression, the cost of its best execution plan is estimated using the physical characteristics of the database. Eventually, the execution plan with the lowest estimated cost is selected for actual execution. The cost estimation-based approach is usually more effective than the algebra-based approach. This is the approach that is being analyzed for BDOviedo3 OODBMS query processing.

Indexing Techniques

An important issue related to query languages concerns optimization techniques and access structures able to reduce query processing costs. Indexes contribute significantly to the efficient processing of database queries. Indexing techniques for OODBMSs can be classified as structural and behavioral.

Structural indexing is based on object attributes. It is very important because most object-oriented query languages allow query predicates to be issued against object attributes. Structural indexing techniques proposed so far can be classified into three categories: the first category providing support for nested predicates or aggregation hierarchy (such as Nested index, Path index, Multiindex, etc.). The second, supporting queries issued against an inheritance hierarchy (such as CH_Tree, H_tree, etc.). The last category supporting for both class hierarchies and composition hierarchies (i.e. Nested Inherited index).

Behavioral indexing aims at providing efficient execution for queries containing method invocations. It is based on pre-computing or caching method results and storing them into an index. The major problem of this approach is how to detect changes to objects that invalidate the results of a method.

Indexing Techniques Supporting Queries Issued Against an Inheritance Hierarchy

Next, some indexing techniques in order to speed up the associative search for supporting queries against inheritance hierarchy are described. These techniques are based on the fact that an instance of a subclass is also an instance of its superclass. As a result, the access scope of a query against a class generally includes not only its instances but also those of all its subclasses. A query may also be formulated explicitly against a class and some of its subclasses. In order to support the superclass-subclass relationship efficiently, the index must achieve two objectives. First, the index must support efficient retrieval of instances from a single class. Second, it must also support efficient retrieval of instances from classes in a hierarchy of classes. These techniques are briefly stated because are being used in the first prototype of BDOviedo3.

CH- Tree: One Index Tree for All the Classes of a Class Hierarchy

Kim proposed a scheme, called CH-Tree (Class Hierarchy Tree), based on B+-trees. A CH-Tree maintains only one index tree for all the classes of a class hierarchy. A performance study shows that the indexing scheme of one index for all classes in a class hierarchy performs better than the indexing scheme that supports one index for each class. However, a major drawback of the CH-Tree is that it does not support the superclass-subclass relationship naturally. Searching for values in a single class is treated in the same way as searching for values in a hierarchy of classes. This scheme is now implemented for BDOviedo3 as it is the most used scheme in OODBMSs.

Ramaswamy proposed an alternative to CH-Tree called CD (Class Division). It is viewed as an extension of CH-Tree. It consists of the index built for the root of the hierarchy (this is CH) plus some other indexes that allow speeding-up range queries.

H- Tree: An Index Tree for Each Class of a Class Hierarchy

In an index called H-Tree (Hierarchy Tree) is proposed. An H-Tree structure is maintained for each class of a class hierarchy and these trees are nested according to their superclass-subclass relationships. When indexing an attribute, the H-Tree of the root class of a class hierarchy is nested with the H-Trees of all its immediate subclasses, and the H-Trees of the subclasses are nested with H-Trees of their respective subclasses and so forth. The nesting supports efficient traversal of the nested H-Trees by enabling traversal of a nested H-Tree to start at appropriate subtrees via the links maintained in its superclass’s H-Tree. In addition, a nested H-Tree can also be accessed independent of its superclass’s H-Tree. The difficult for dinamizing this scheme is the major drawback.

In and other structural indexing schemes, such as Multiindex, Nested Inherited Index, etc. are analyzed. Even the cost for retrieval, delete and insert operations is evaluated. These schemes are being considered for future versions of BDOviedo3.

Figure 3: Indexing Mechanism class diagram.

The Indexing Mechanism of Oviedo3

Thus, BDOviedo3 provides an indexing mechanism (Figure 3) with the following basic features:

• Different indexing schemes. The system allows different indexing schemes (CH-Tree, H-Tree, etc.). Initially, CH-Trees are considered in the first prototype that is being developed. However, the class hierarchy designed for the implementation of the BDOviedo3 indexing mechanism allows easily adding new schemes.

• It is generic. It implies that the indexing can be performed over any data type (not simple types only). In order to get it the mechanism allows to define comparison operators users-defined.

Storage Management

Disk space management and main memory management are storage manager functions of a DBMS. In BDOviedo3 OODBMS this functionality is basically supplied by the persistence system of the abstract machine. The persistence system itself stores in disk and brings back to memory the persistent instances transparently. A pagination plus segmentation technique with a configurable page size is used for speeding-up the swapping between volatile and persistent memory. This storage system can be improved, for example, with some clustering techniques. These possibilities will be considered in next BDOviedo3 prototypes.

Transaction Management

The basic function of the transaction manager is to guarantee the appropriate processing of concurrent transactions. OODBMSs need more powerful techniques than the traditional techniques (i.e. locking).

The first prototype that has been developed does not consider in detail the transactions management. It will be dealt in a more advanced stage of the system.

The Languages

OODBMSs try to integrate the database languages with the programming languages (different traditionally) in order to provide a single syntax with a unified model and type system. It makes database objects appear as programming language objects. This is the scope of the standard suggested by ODMG (Object-Oriented Database Management Group).

ODMG 2.0 Standard

ODMG proposes to transparently extend an object-oriented programming language with persistent data, concurrency control, data recovery, associative queries, and other database capabilities. It specifies the syntax for an object definition language (ODL) and an object query language (OQL). However, it doesn’t believe exclusively in a universal database manipulation language (DML) syntax. Instead, the DML defines standard bindings of OODBMSs to object-oriented programming languages such as C++, Java or Smalltalk.

ODL is not intended to be a full programming language. It defines the characteristics of types, including their properties and operations. ODL defines only the signatures of operations and does not address the definition of the methods that implement those operations. Its major objective is to support the portability of database schemes across conforming OODBMSs. The C++, Smalltalk, and Java ODL bindings are designed to fit smoothly into the declarative syntax of their host programming language.

The query language proposed by ODMG (OQL) is not computationally complete. It provides declarative access to objects with a like-SQL syntax and provides high-level primitives to deal with sets of objects (although it is not restricted to this collection construct). OQL can be invoked from within programming languages for which an ODMG binding is defined. Conversely, OQL can invoke operations programmed in these languages.

BDOviedo3 Applies the Standard

Some OODBMSs propose an object database language. For example, Thor proposes the Theta language, Ode proposes the O++ language (a C++ extension), etc. However, the languages for BDOviedo3 will follow as much as possible the ODMG 2.0 specification. Therefore, it is convenient to keep in mind the following points:

• The base object-oriented programming language for the database languages (ODL, OML and OQL) must be selected. This language can be C++, Java, etc. But, it is possible to use an object-oriented language (C++ Oviedo3) designed for Oviedo3 because when it is compiled Carbayón object code for the abstract machine is already generated. The C++ Oviedo3 language takes advantage of some abstract machine features.

• The BDOviedo3 OML will be created by extending the C++ Oviedo3 language with the database capabilities (i.e. queries, transactions…). Any database manipulation program implemented with this language will generate Carbayon object code when compiled.

Class Professor {   attribute string FirstName;   attribute string LastName;   attribute short Age;   short GetAge();   relationship set Teaches inverse Section::Is_Taught_By; }; Class Section {   attribute short Number;   short GetNumber();   relationship Professor Is_Taught_By inverse Professor::Teaches; };

Figure 4: ODL specification in the BDOViedo3 System.

• The ODL and OQL specifications can be directly translated to the abstract machine language. A translation to C++ Oviedo3 intermediate language can be made too. The first option is used in the current prototype (Figure 4 and Figure 5) .

• The object code will be linked with the BDOviedo3 engine that will supply all DBMS capabilities.

Class Professor   AGGREGATION     /* class attributes */     LastName:String;     FirstName:String;     Age:Integer;     /* relationship attributes */     Teaches:Tset;   METHODS   FieldbyName(ParamName:String):Object;   REFS     Bres:Bool;   INSTANCES     Param1str:String('LastName');     Param2str:String('FirstName');     Param3str:String('Age');   CODE     ParamName.Equal(Param1str):bRes;     JFD bRes, Label1;     Assign rr, LastName;     Jmp Fend;     Label1:     ParamName.Equal(Param2str):bRes;     JFD bRes, Label2;     Assign rr,FirstName;     Jmp FEnd;     Label2:     ParamName.Equal(Param3str):bRes;     JFD bRes, Label3;     Assign rr, Age;     Jmp FEnd;     Label3:     FEnd:     Exit;   ENDCODE   /* class methods */   GetAge():Integer   CODE   ENDCODE ENDCLASS

Figure 5: Carbayón code generated from the ODL specification of the Professor Class.

Final Conclusions

The combination of an object-oriented abstract machine offering object support with an object-oriented operating system implemented as a set of objects is a promising way of structuring object-oriented integral systems. Furthermore, it facilitates the construction of an integrated OODBMS. Advantages such as portability, language independence and impedance mismatch removal are complemented with the improvement and ease of implementation of the funcionality of the OODBMS.

BDOviedo3 is a pure OODBMS, the objects defined with an object-oriented programming language are allowed to be directly stored into the database (using the abstract machine persistence system). Besides, BDOviedo3 system can be customized. The indexing mechanism, the cost functions for queries, etc. can be selected, in order to comparisons between different strategies can be made.

We expect to find many difficulties when we integrate the different mechanisms which compose the system. Nevertheless we believe this mixture of properties is very promising and it will be worth building a system like this.

Keep in mind, our main aim was the building of a prototype in which the primary elements of the system work. Subsequently, other aspects, such as transactions management, schema evolution, versioning, etc. will be considered.

See Also

• Agenda.

• Links.

• Publications.

• Prototypes.