SBA: Abstract Object Store Models

Abstract Object Store Models

As we have argued in the section devoted to syntax, semantics and pragmatics of query languages, we have to define data structures stored in an object database in an abstract way, but with the algorithmic precision. Our definition should be sufficiently universal to cover all features that can occur in object-oriented databases and XML repositories.

However current object models tend to be very complex, with many non-intuitive notions. Moreover, each object-oriented standard, programming language or database management system introduces an own object model, with very specific concepts that sound similar, but frequently have totally incompatible meaning. This concerns such popular concepts as class, inheritance, interface, type, and others. Nowadays XML technologies also contribute to this complexity. Although basically the XML model is not object-oriented, it introduces complex hierarchical objects, with a lot of own notions, especially in RDF, in XML Schema, in RDF Schema and in the family of technologies called Web Services. The ODMG standard for object-oriented databases involves many notions such as objects, literals, types, sub-types, interfaces, classes, inheritance, methods, overriding, polymorphism, collections (various kinds), structures, relationships, operations, exceptions, and others. The SQL-99 standard is even more complex, because it involves similar concepts and additionally mixes them with nested relations having a lot of peculiarities, abstract data types (ADT-s) and other features.

Unfortunately for current technologies (and fortunately for SBA) the majority of this complexity is caused by secondary features and lack of attempts to generalize, simplify the ideas, and to avoid redundant notions. For instance, one can introduce both classes and ADT-s, but conceptually the notions are the same. Similarly, the ODMG standard introduces both sets and bags as collections, but sets could be removed as a particular case of bags. If we assume the object relativism principle, then there is no need to distinguish objects and attributes. There are more such redundancies which stem from various streams of research and development, and some historical dust around the object-oriented notions that has been collected for years.

Now it is the time for cleaning the dust. For description of semantics of query languages the complexity of the underlying data model is a very negative factor. A consequence of the complexity of the object model is the complexity of a query language concerning its syntax, semantics and pragmatics. Complexity of semantics implies much more difficult implementation and optimization. In particular, due to complexity of SQL-99 many professional doubt if it is entirely implementable. Optimization of queries and programs in SQL-99 will be very challenging and in many cases impossible due to chaotic language design decisions and unknown interaction between various data structures and language’s constructs. Complexity of pragmatics leads to long documentation, extensive user manuals, long training time, long application development time and more chances for errors.

Complex semantics is also more difficult for keeping consistency. According to the conceptual closure principle, each feature of an object model must be reflected in syntax, semantics and pragmatics of a language addressing the model. The precise semantics of the language requires defining all states according to the model (the set State). The complexity of the object model causes the complexity of the set State and consequence, the complexity of definition of semantics. This leads to more difficulties during formal analysis of the semantics, decreasing the potential for query optimization, much more challenging strong type checking, and much more difficult the control over completeness and mutual interaction between different constructs of the language. A complex object model causes also the “metamodel management nightmare” (after Won Kim), that can be observed e.g. in the ODMG standard[1].

Currently, the commercial world neglects or ignores the problem of the complexity of the object model and its influence on the complexity of semantics and pragmatics. The claims that for SQL-99 or ODMG OQL one can easily build a formal model are not justified at all; they belong to the marketing offices liars’ game rather than to honest and technically sound assertions. Languages are designed with no care about minimality and consistency of introduced constructs. All the commercial proposals of standards are underspecified. Holes in the specifications cause that implementations of the proposals cannot be compatible. These circumstances, together with ad hoc extensions introduced by software manufacturers, to a big extent undermine the sense of the standards.

For these reasons there is necessity to simplify object models by developing such abstractions over them that cover all the required features introduced in practical languages by minimal set of notions. We remind that just the simplicity of the relational model was the source of its success, because make it possible to reason about various properties and language constructs in intuitive and formal ways.

In contrast to the relational model, object models must be more complex for better conceptual modeling capabilities (what is just the essence of the object-orientedness). It is difficult to crate a single model that would be at the same time simple and covering all the features of object models. There are also some didactic reasons: a lot of features can be explained on a very simple (but still quite universal) model, and then, next and next features can be added by generalization of this simple model. For these reasons SBA is based not on a single object store model, but on the family of models that are enumerated AS0, AS1, AS2 and AS3[2]; a model with a higher number introduces more sophisticated features. The list of models is of course open - there are a lot of possibilities to make variants of them or introduce new features. However, the list is complete in this sense that - according to the best of our knowledge - there is no feature or notion of currently used or proposed in practice object languages and systems that would be not covered by some of these store models. All the store models AS0, AS1, AS2 and AS3 are based on the same few formal primitives.

The basic features of the introduced store models are the following:

AS0 Store Model: the simplest model that we have introduced. It covers complex hierarchical objects and pointer links between objects. It does not deal with classes, roles, inheritance, interfaces and encapsulation. AS0 covers pure relational data structures, nested relational structures, the structures implied by XML and RDF, and features that are assumed in the models referred to as semi-structured.
AS1 Store Model: augments AS0 with concepts of class, static inheritance and multiple inheritance, in the most common understanding that is relevant to object databases.
AS2 Store Model: augments (and a bit modifies) AS1 with the concept of dynamic object roles and dynamic inheritance (between objects).
AS3 Store Model: augments AS1 or AS2 with encapsulation (subdivision of properties of objects and classes into public and private).

This family of models is rich enough to have a hope that some next conceptual feature of object-oriented artifacts will not create a new quality for semantics of defined query/programming languages. The most important is to understand the assumptions of SBA and the SBQL semantics for the simplest AS0 model. After that, it is quite easy and natural to extend the semantics to higher-order store models.

We have to warn the readers that our store models are not the same as data models. Store models are formal constructs and have almost nothing in common with concepts, ideological constraints and rhetoric, mathematical decorations, beliefs and stereotypes that are usually associated with data models. A store model is simply an abstract view on data structured stored in the database (and in other media) and is orthogonal to any ideologies such as the relational model or XML. Lack of a formally precise store model causes that the definition of semantics will be always vague and obscure; not clear for the developers and programmers of a query language engine. In our opinion, this is the case of ODMG and SQL-99 standards, which do not present the formal store model for objects explicitly, but explain them informally by other (also sometimes obscure) notions, such as types, classes, ADTs, etc.

In all the introduced store models we use the same three elementary notions:

Internal object identifier. In our intention it is assigned automatically by the system and has no semantics in the external world. This is only intention, not requirement; in fact, however, we are not interested in how identifiers are generated and what internal form they have. For each object stored in the object store its internal object identifier is unique. An internal object identifier will be used to identify internally an object from the object store, in particular, it will be used as a reference or pointer to an object. As another intention we assume that the access to an object via its identifier is very fast. In programming languages internal identifier is usually a memory address, or some base address plus offset. In SBA, however, we do not deal with the form or construction of identifiers and assume that the application programmer never uses it explicitly in some writable or printable form. The set of all internal identifiers we denote I, elements of this set will be denoted i, i₁, i₂,... .
External object name. In contrast to internal object identifiers, external object names are explicitly assigned to objects by a database designer, a database administrator, an application programmer, or another human agent. The external object name usually bears some external business semantics of the object, is closely related to conceptual modeling of business applications and is a part of the corresponding business model e.g. determined in UML. For instance, such names can be: Person, Customer, Department, salary, deptName, job, employs, etc. In contrast to internal object identifiers, external object names need not be and usually are not unique. For instance, there may be many objects named Person and many objects named employs, on the same hierarchy level and within the same collection. In general, an object can possess many external names, assuming inheritance and the substitutability principle. For example an object named Student has also the name Person. More freedom and specific discipline in assigning names to objects is offered by the object store model AS2. The set of all external object names we denote N, elements of this set will be denoted n, n₁, n₂,... . In examples we use explicit object names like Person, salary, etc.
Atomic object value. It is the value stored within an object that from the point of the defined semantics of a query language cannot be subdivided into smaller parts. For instance, numbers 2, 3.14 and strings “Doe”, “Hello, World!” are atomic object values. We are not interested in the size of such a value - it can be a one-byte value, can contain dozens of bytes, can be a jpg file having several hundreds kilobytes, or a DVD file having the volume of some gigabytes. Bodies of procedures, functions and methods are also atomic object values. So far we are not interested in the types of values. This issue is important, but the semantics of a query language can be explained without referring to atomic types. We will deal with the types much later, when we explain the strong type checking mechanisms. The set of all atomic object values we denote V, elements of this set will be denoted v, v₁, v₂,... . In examples we use explicit self-explained literals denoting the values.

Last modified: December 31, 2007

[1] However, we disagree with Won Kim that this can be an argument of favor of object-relational models. In our opinion, the SQL-99 object model leads to the much more painful “metamodel management nightmare”.

[2] Originally, AS0, AS1, AS2 and AS3 were denoted M0, M1, M2 and M3, correspondingly. The change was caused by a clash with the notation used by OMG for different UML (meta) models.