Although the senses of “DB” and “OO” that we are using are advanced only as working definitions, they are not without foundation. Before we had databases, we had persistent data stores (files), accessed by multiple users; and we had all the problems of such access: concurrent updates, deadlock handling, recovery, and so forth. Databases, such as IBM’s Information Management System (IMS), were introduced to handle a quite different problem: the sharing of data between different applications; or, as we would now say, the same data in different views. IMS was not entirely successful in this respect. It was, to a large degree, in reaction to its shortcomings that EF Codd proposed his Relational model.[2]

The use of encapsulation and abstract data types clearly provides data representation independence. Thus Bertino and Martino: Encapsulation provides a form of “logical data independence” and means that the implementation of objects can be modified, while the applications that use them remain unchanged. Also: The reason behind [encapsulation] was ... to make a clear distinction between the specification and the implementation of an operation.[4]

Notice how this distinction solves the problem: the specification language is radically weakened, so that it cannot refer to representation at all. Representation independence was briefly proposed by Codd in [2], and Relational domains may be understood as data types; but current Relational DB systems do not provide acceptable data typing and representation independence. However, the Relational model and the algebra and calculi are entirely orthogonal to data typing – at least, to atomic data typing. There is a lacuna in the model; but we understand how it can be filled.

A program may be access dependent either operationally or structurally. If the program explicitly states the means of access to its data – the index to be used, navigation sequences, etc. – then it is operationally access dependent. Relational systems provide operational access independence, again, by radical weakening. They make a clear distinction between the specification and the implementation of data access. For instance, SQL data access statements provide no facility for access methods or paths to be specified (they are determined, outside the program, by the optimiser). Structural access dependence is secondary to data organisation dependence; thus, for example, access to data in a repeating group must be through access to the record containing the group.

On the face of it, sending messages to objects must entail operational access dependence. If, for instance, an operation of n parameters cannot be simply invoked, say by CALL OP (P1, P2, ... Pn), but must be sent to one of the parameters, say by MSG P1 OP1 (P2, ... Pn) or MSG P2 OP2 (P1, P3, ... Pn) or so on, then access to the value(s) returned by the operation – which might involve database access – is specified as going via P1, or via P2, or so forth. It then becomes the responsibility of the programmer to ensure optimal performance, because any automatic optimiser is precluded from, for example, accessing P2 before P1 if the message is specified as going to P1. (If an optimiser could effectively convert a “MSG P1” to the functionally equivalent "MSG P2", there would be no point in the programmer determining to which object a message was to be sent: they might just as well code the old-fashioned “CALL”.) But a system could be OO, in our sense, even if it did not use messages to force asymmetry on the inherently symmetrical. (The parallelism is obvious between, on the one hand, “flat” CALLs and “hierarchical” messages and, on the other, records in a Relational DB and those in IMS; again, see [2].) Suppose that P2, P3, ... Pn, instead of being parameters, were components of P1, and encapsulated within it. The invocation would reduce to “CALL OP P1” (or to “MSG P1 OP1”, it matters not). P2, P3, etc. would still be accessible only through P1. There would still be access dependence, but caused by asymmetry of data structure rather than by asymmetry of operation.

There are two aspects to data organisation independence: sequence and structure. The problem of sequence is, once more, solved by radical weakening. The conceptual database admits no sequencing; and nor does the DML, except “at the last moment”: data can be sequenced to form a view. Indeed, given that the DML operations are closed over minimally structured data, sequencing is the only extra mechanism available to create the more complex structures needed in views. Data structure independence, however, cannot be achieved by radical weakening: we can exclude from the conceptual database and from the DML all reference to representation, access, and all but last minute sequencing. But even conceptual data must have some structure; we cannot get by with atomic data items alone. So we weaken the system as much as possible; we admit only minimal structuring. This means that we need to simplify – to weaken – even the Relational Model.

By “field” we understand an atomic data item. A data item is taken as atomic if no definable updateable view of it contains less than all of it. (An atom is permitted to be of any size, so a moving picture that took an hour to show might be an atom. But, in that case, no view could allow update of only a single frame or sequence from it.) A field is constituted, i.e. characterised, by a designation (column name) and a value: if f is a field and g is a field, then f is the same field as g if and only if f has the same designation as g and f has the same value as g.

The only data structure admitted is the record, which is a simple aggregate of one or more fields, “simple” in the sense that the aggregate of two records is merely the record that comprises all their fields. A record is constituted by its fields: if q is a record and r is a record, q is the same record as r if and only if q comprises all and only the fields that r comprises. Some records are distinguished as kept (“base” records, those held – conceptually – in the DB, in contrast to those merely derivable in views or queries). Most kept records are flat (not having two fields of the same designation); we shall ignore non-flat records, which are almost never needed.

Records are designated by common names or titles (expressions of the DML). Such a name, e.g. INVOICE, designates each of many records (each invoice record). “File-at-a-time” processing is obtained by specifying a query using such a name (or names), and performing the query on each of the records designated by that name (or names).

This is the heart of Codd’s proposal: all kept data is to be held as normal records without repeating groups and in no other structure. (The simplified model allows repeating fields – i.e. it allows non-flat records – but not repeating groups.) It is not proposed that each data entity is to be held as a single normal record. Obviously, an ACCOUNT, comprising a header and multiple postings, cannot be held as a single normal record. What has been removed from Codd’s original proposal is the extra structure, the relation, which (1) serves to attach a “relation name”, via a collection of normal records (the relation), to each of its contained records, and (2) imposes “union compatibility”, i.e. common format, on those records. (Two records are of common format if for each field in either there is a field of the same designation in the other.) We reject union compatibility; we do not impose common format on commonly named records. But we impose the constraint that if a record is designated by a record name then it is shown to be so designated by the data in the kept records of the DB. (To take a simple example, the name “INVOICE” might be applied to all and only the kept records containing a field designated “Invoice Number”.) So record names (“relation names”), convey no extra information in the simplified model; they are inessential, in the sense of Date.[5]

The well-known relational DML operations – restriction, projection, join, and so on – are applicable to the records here proposed. The union operator (unconstrained), when applied to two record names, gives a title that designates each record designated by either of the names. For most purposes, therefore, the proposed simplification is equivalent to the original Relational model; so comparisons with the OO approach will be made here with the original, except where there is particular need to to refer to the simplified model.

If excessive structure leads to data structure dependence and to structural access dependence, we should observe these, to some degree, in a Relational system. If we could construct, external to a program, the data view that it required, then the program would need to issue no data input commands. It could be input-event-driven: the view would be presented to it, one or more records at a time, and the program would then be “driven” (invoked). Such programs, sometimes termed “pseudo-conversational”, effectively remain active (retain their state) between invocations (they are co-routines, or subroutines with a passed “state” parameter). Notice that this approach avoids the so-called “impedence mismatch” between DMLs and programming languages. Little access dependence is introduced if a program, instead of being driven in this way, reads its sole input file in a single major loop. (This account discusses only input; similar, and interacting, effects pertain to output.)

Consider a program that reads two or more input data streams, a common occurrence when transaction data is processed against master data. The program must now determine the sequence in which it accesses those streams. In effect, it is – to some extent – building its own view, and therefore it is access-dependent. (Of course, programs that use direct access, navigation, etc. also build their own views; which is why they are even more access-dependent.) To achieve access independence, the input data streams should be merged into a single view. But in a Relational system this cannot be done if (as so often) the records in the data streams are of different formats – not union compatible. So, to this small degree, the excessive complexity of Relational systems does give rise to data dependence. The simplified model, by contrast, allows a view to contain normal records, of any formats, in any sequence. The added flexibility in view construction comes from the abandonment of the higher level structure, the relation (a set of uniform normal records).

Bertino and Martino make a partcularly telling criticism of the Relational Model in [4]: [its] constructors are not orthogonal as [the] set constructor can be applied only to tuples and the tuple constructor can be applied only to atomic values. There are, perhaps, two effective responses to this criticism. The first is that the Relational model has only one constructor, which can be informally defined as “set of uniform tuples”. Formally there is no “tuple” constructor, and no “set” constructor; there is only a “relation” constructor. But this does not quite meet the orthogonality objection. Full orthogonality would demand that if we have atomic values and a “relation” constructor, then we should have relations of atomic values, and relations of relations, and so on: we should admit nested relations.

The second response is to admit a “record” constructor (a simple aggregator), but to dismiss “set” as a façon de parler, merely a way to attach a common name, or predicate, to a number of objects (just as “is a member of the set of dogs” simply means “is a dog”, or “bears the common name, ‘dog’”). In effect, this is what we do in the simplified model. But what of the rejoinder: if we allow records (of fields), we should allow records of records, and so on? So we do. Firstly, a field is a record: a record with no proper part (no part other than its entirety). Secondly, as records are simple aggregates, a record of records is permitted; but it is merely a record. The aggregate (record) of, say, records q and r, is that record that comprises all and only the fields that are part of q or part of r. So, contrary no doubt to its original intention, this elegant criticism is best answered not by making the Relational model more complex, but by applying the same simplification that makes it data structure independent.

In a Relational system (in theory) an open collection of atomic data types is admitted. But the notion of atomicity requires elaboration. No concept of absolute atomicity is proposed.

What is proposed is that a data item be taken as atomic if and only if, in each updateable view definable in the system, either it does not appear or it appears in its entirety. (Naturally, this means that the addition of new capabilities to a system might make a formerly atomic data item non-atomic, and an analyst with some foresight might properly allow for this possibility). But we need to distinguish carefully here between specification and implementation. We might have Complex Number, Rational Number, and Date specified as atomic data types; implemented as, say, Modulus and Angle, Pair of Integers, and Year and Day, respectively. Such non-atomic implementations (as structure) are not pertinent to atomicity. They should be (we will assume they are) hidden by encapsulation of the data types.

We still, alas, face a problem, which we might term perverse atomicity. Consider these data types:

COMPLEX

A complex number, say x+yi, implemented as the pair (x, y)
 

INTEGER

A signed integer, say n, implemented as the pair (n², SIGN n)
 

INTPAIR

An ordered pair of integers, (j, k), thus implemented.

The proposed definition of atomicity does not help. Given an integer, n, we might well have one view containing n, another containing SIGN n, and another containing SQUARE n; just as we might have views containing an integer pair, p, FIRST p, and SECOND p. To the writer’s knowledge there is no way to make a formal distinction between componency and other kinds of operation. However, we can make one reasonable remark, and propose an informal test. It may not be a provable breach of the atomicity rule to have a perversely atomic data type, a data type that is actually a structure but claimed (merely technically to avoid breach of the rule) to be atomic. But if keeping the rule is of any advantage, that advantage will be lost if the rule is effectively (albeit not technically) breached. The intended advantage is the simplicity of the DML: only one structure is permitted, and therefore only one way to specify creation, amendment, deletion, and querying of data structures is provided. The user, or programmer, never needs to worry about how to access a component of a structure: so they cannot choose the wrong method. The analyst never needs to worry about the structure to choose; because no choice is available, no choice is wrong; such is weakness.

We may not be able formally to test for perverse atomicity; but, in a word, avoid it. Here is an informal test: list the plausible components (e.g. RE, SECOND, SQUARE), omitting any that vary only passively (as a result of changing other components); so omit CUBE of INTEGER if there is no operation to set the cube, omit the SUM of the elements of INTPAIR. A component is then a genuine component if it can be modified, while leaving all other components unchanged: if there is such a component, the data item is non-atomic.

Thus, if we reckoned the components of COMPLEX to be the real, the imaginary, the modulus, and the angle, we would find that none of them could be modified while leaving all the others unchanged. By contrast, INTPAIR appears to have only two components, and either can be modified without changing the other: it is a structure. Suppose it were claimed that the sum over INTPAIR were a component: obviously modification of either integer would not leave it unchanged. Does that sum vary only passively (as either integer is modified)? If so, it is not a component. But suppose we had defined on INTPAIR an operation that set the sum of the pair, j+k, and accordingly modified j and k, so that either j=k or j+1=k: then INTPAIR would indeed be atomic. But it would not be merely a pair of integers; it would be a different data type, albeit implemented as a pair of integers.

An object in an OO system, it should be noted, is in specification atomic (perhaps perversely atomic). It is sometimes said that an object comprises methods and state variables. But, as the state is encapsulated (so its representation as a number of variables is irrelevant) there is no reason why we should say that it is specified as more than one variable. Consider two objects of identical behaviour; perhaps one is implemented with a single state variable and the other with multiple state variables. But we cannot say that the one is (possibly perversely) atomic and the other is not: either both are atomic or neither is, for they are of the same kind: they have the same behaviour. And as each conceivable component of such an object is available only by applying some operation to the entire object – because objects do not come in parts – it is (either properly or perversely) atomic. As a consequence, there are strict constraints on any compromise between OO and Relational DBs. An object is permitted as a value in a Relational DB only if it is atomic (properly, not perversely). That rules out a lot of objects.

It should be noted that an encapsulated structured abstract data type does not have encapsulated structure, merely encapsulated representation. Indeed, it is precisely the public part (the non-encapsulated specification) of such a date type that exhibits its structure. So if such a data type is of a well-known structure (such as a list), it will be demonstrably of that structure. It should be stressed that if an object, even of such a demonstrably structured type, clearly passes the test for atomicity then it is, for DB purposes, an atom. Thus, for example, a stack of tasks, if it appears in each view either in its entirety or not at all, counts as an atom: nothing is to be gained by splitting it within the conceptual database.

Few OO authors appear to address the question of data structure independence, but the general impression given is of preparedness to abandon it in order to achieve other ends. Honourable exceptions are Gray, Kulkarni, and Paton – with an index entry for witness. But even they remark that the emphasis in an OODB is on building complete applications, rather than on designing a schema that application programs can use later. As such schemata are traditionally designed to be structure independent – to allow for both anticipated and unanticipated applications – this remark may indeed imply some abandonment of structure independence.[6]

Meyer discusses whether software design should be based on functions (in effect, applications) or on data. He attempts to justify basing system structure on data structure. His argument is – and this is well shown – that [i]n the evolution of a system, the functions performed tend to be the most volatile part. A successful system will soon be asked to perform new tasks.... If the architecture is overly based on the functions, it seems impossible to ensure that system evolution will be ... smooth ... But, Meyer argues, [m]uch more persistency may be found in the classes of data [the system] manipulates ... This is the key argument for using them, rather than the tasks, as the principal guide for system structuring.[7]

But Meyer fails to distinguish between data content and structure. The data structures of a system are the views of the system’s data taken by applications (functions or tasks); and, inevitably, these are almost as volatile as the applications themselves. The stability that Meyer seeks is to be found in the data content (i.e. data content type, not necessarily in the individual values of fields). This is why we want a conceptual database with minimal structure. We must avoid burying deep in some structure, for some application, data that might be wanted in a different structure, for a different (perhaps unanticipated) application. Normal data avoids deep interment.

Some authors seem to go beyond a mere willingness to sacrifice data structure independence: they are, it appears, actually opposed to it, or at least to the minimality of structuring that it entails. For some data, this may be quite correct, namely data that is restricted (and will remain restricted) to a single structure: but such data is, on our definition, atomic. In [4], Bertino and Martino say of some applications that they have data whose structure and whose relationships with other data cannot be mapped directly back onto the tabular structure of the relational model. But it is difficult to identify the sting of this criticism: what is a “direct” mapping? could an “indirect” mapping be specified? is the problem that an object would have to be specified as multiple normal records of different format? On the face of it, it seems unlikely that there is any data that cannot be specified as a collection of normal records. Bertino and Martino also make a more specific criticism, which may be an elaboration of the above: representing a complex object in the relational model means the object has to be subdivided into a large number of tuples. Then a considerable number of join operations have to be carried out so that the object can be rebuilt ... But the representation of a complex object in any system requires its analysis (“subdivision”) into a large number of smaller objects (that is, surely, what “complex” means). And consequently the definition, or specification, of the complex object in terms of those small components inevitably requires a considerable number of operations of synthesis of some kind. It is a merit of the Relational model that it uses only one way to structure such components.

Hughes says that inadequacies in the relational model quickly become apparent when it is applied to complex, highly structured application domains.... it is impossible to represent and maintain control over situations involving large numbers of interrelated, complex entities. And he too objects to the use of joins: In the relational model the relationship “reserves” [between Person and Flight] would be represented by a relation containing the key attributes of the entities “Person” and “Flight” ... thus the information about a reservation is scattered across several relations. If we require the source or destination airports of a particular reservation we must perform a join ... Oddly enough, in view of Hughes’ objection to “scattering” of data, at another point he remarks that in an object-oriented database environment the physical description of a conceptual object [need] not be stored at a single physical location.... an object may be physically partitioned, on the basis of frequency of use, in order to enhance performance.[8]

There may be one of two possible confusions here. Some writers may think that the Relational approach requires any data that is anywhere treated as a structure to be specified as multiple values in a Relational database. Not so: a single field may contain such data (e.g. a complete document or drawing) as long as it is, in the sense defined above, atomic. The other possible confusion is between specification and implementation, and it may be that Bertino and Martino are speaking of implementation when they say that join operations have to be carried out, and likewise Hughes when he says that we must perform a join. But this is to misunderstand the Relational model (although it reflects some current Relational systems): nothing whatsoever prevents frequently joined conceptual records being physically stored ready-joined. Alternatively, or additionally, records that are usually accessed together (whether joined or not) may be clustered – held in physical proximity. In any DB there will be anticipated joins, data that – in Hughes’ words – may be accessed without explicit joins. And there will be unanticipated joins, both for human users and for new, ad hoc, or experimental (e.g. prototype) programs. A DB system needs to support both kinds of join, preferably with a similar specification but different implementations (they have the same semantics, but different pragmatics).

We say that the Relational model admits only one data structure. But this must, of course, be understood as: only one primitive structure. Clearly, if “set”, “array”, “list”, “tree”, etc. can be defined on “record”, along with any atomic data types, then – in that sense – we can have sets, arrays, lists, trees, etc. in a Relational system. And we can. Suppose that we have three-field normal records of the following format, where “x” is the name of some structure, e.g “ARRAY-OF-INTEGER”:

x-ELEMENT:    x-ID   INDEX-IN-x   ELEMENT-IN-x

By using various data types for INDEX-IN-x, we can obtain a variety of structures: the data type of INDEX-IN-LIST, where an element may be inserted at any point in a list, would be dense and totally ordered; that of INDEX-IN-LATTICE would be partially ordered; the field would be omitted entirely for a SET. Structures of structures are easily obtained: in general, to get an u OF x, we draw the values of ELEMENT-IN-u from those in x-ID.

Now, it might be thought that an implementation of, say, such a set of lists of arrays of integers, would be peculiarly inefficient in both storage space and accessing time. Not so: that deeply nested structure is (when we unwrap its definition) specified as a collection of records. But it may be implemented any way we choose. The major constraint imposed by the Relational model is that there must be an implementation on that data of the DML operators, which are specified on its conceptual component records.

Consequently, the Relational model (simplified version) excludes neither the specification of complex structures of data, nor their efficient implementation. It demands merely that any such structure be defined on the “record” constructor and the available atomic data types; so that its components are accessible using the DML. And we have seen why such deeply nested structures should be specified as normal records: because their components may need to be incorporated in some updateable view that does not encompass the nested structure in its entirety. And if none of the components of such a nested structure is (and none ever will be) incorporated in such a view, then the nested structure is, in respect of the DB, an atom – not a structure at all.

In order to specify a structure-independent storage system for persistent data that is shared between different applications, it is necessary to employ only minimal structuring, i.e. somewhat weaker than that of the Relational model, and much weaker than that of any object-oriented system. A simplified data model, admitting an open collection of atomic data types, and simple aggregation as its sole constructor (of “records”), provides this minimal structuring; and it achieves the orthogonality of structure that the Relational model lacks.

“Atomicity” of data items is defined by reference to the updateable views in which they appear: a data item is atomic if it invariably appears entire in these views. An informal test for “perverse” atomicity of a data item (i.e. atomicity claimed for a structure) is proposed: the item is non-atomic if one of its putative components can be modified while leaving all the others unchanged.

The specification of object-oriented persistent data stores appears to require sacrifice (willing or unwilling) of data structure independence. But the justification of this sacrifice seems to be based, in some measure, on confusion between specification and implementation.

Although the simplified Relational model admits only one primitive constructor, it appears that the other constructors we need can be defined within the model. Complex structures that are specified in such a way can be both physically stored and presented in views, in all their complexity. But they must, on demand, be reducible to, and manipulable as, simple records. However, this need have no impact on the efficiency of their most frequent usage. Moreover, the proposed definition of atomicity has the consequence that if a complexly structured data item never requires restructuring, it can be treated as a single field without loss of structure independence.

The demands that have led to the proposal of object-oriented databases, and the concomitant criticisms made of the Relational model, urgently need re-examination, with particular reference to the long-recognised requirements for data independence.

[1]

DR Howe: Data Analysis for Data Base Design, 2nd Edn, Edward Arnold 1989
 

[2]

EF Codd: A Relational Model of Data for Large Shared Data Banks, Communications of the ACM 13, No 6 (June 1970)
 

[3]

David A Watt: Programming Language Concepts and Paradigms, Prentice Hall 1990
 

[4]

Elisa Bertino and Lorenzo Martino: Object-Oriented Database Systems Concepts and Architectures, Addison-Wesley 1993
 

[5]

CJ Date: An Introduction to Database Systems Volume I Fifth Edition, Addison-Wesley 1990
 

[6]

Peter MD Gray, Krishnarao G Kulkarni, and Norman W Paton: Object-Oriented Databases, Prentice Hall 1992
 

[7]

Bertrand Meyer: Object-oriented Software Construction, Prentice Hall 1988
 

[8]

John G Hughes: Object-Oriented Databases, Prentice Hall 1991