CMSC724: A History of Data Models

Instructor: Amol Deshpande

This chapter is a guided summary of Stonebraker and Hellerstein’s What Goes Around Comes Around, together with the class discussion around it. It is deliberately a summary with pointers rather than a full treatment — the paper is short, well written, and worth reading directly.

There is also a recent addendum, What Goes Around Comes Around… And Around by Stonebraker and Andy Pavlo, which covers data models and the broader history of databases over the last twenty years. Read both; the newer paper starts where the older one leaves off.

Passages marked as editorial extensions were written by the notes generator and go beyond the source slides and class discussion.

1. What a Data Model Is Trying to Do

The goals a data model is trying to satisfy

The goal is to choose a good data model for the data. Three criteria:

It must be sufficiently expressive — it should be able to capture the real-world data you have. Otherwise it is not much use.
It must be easy to use, which in practice means supporting physical and logical data independence.
It must lend itself to good performance.

For reasons that become clear once you have worked on these topics for a while, the relational model fits all three unusually well. That is a large part of why it is still here 55 years after it was proposed, and why most database systems gravitate toward it over time.

There are many similarities across models, and a great deal of convergence over the last two decades. There are also orthogonal issues to keep in mind — schema maintenance and evolution, and data integration and reconciliation — which are possibly a much bigger headache in practice, and which no choice of data model solves for you.

The open question worth carrying through the chapter: there is no real doubt that relational is the best low-level model. Should it continue to be the high-level model as well?

2. Data Independence: What Codd Was Reacting To

Codd’s examples of physical data dependence

Codd’s 1970 paper opens by cataloguing the ways in which applications of the day were coupled to storage decisions. It is worth being specific, because these are the concrete failures that motivated everything after.

Picture a database with several application programs written against it — back then they were called programs rather than applications, but the same thing. Three kinds of dependence:

Ordering dependence. How records were sorted was hard-coded into the applications; the programs were written assuming a particular sort order. That meant you could not reorder the data without possibly breaking every program. Today we do not even think about this — when we write a SQL query we are not concerned with how the data is sorted, and generally do not know whether it is sorted at all.

Indexing dependence. Which indexes were present was hard-coded, which meant you could not easily add a new index, and definitely could not delete an existing one.

Access path dependence. Dependence on the specific hierarchy or network structure chosen. This one is specific to the hierarchical and network models, and it turns out to be the one that survives into the present day.

Against these sits logical data independence: the ability to change the schema — add an attribute, combine two tables — without affecting external applications or APIs. In relational systems this can be achieved to some extent through views.

The general goal: applications should not hard-code any of these decisions, so that the decisions can be changed easily.

An exercise: authors and books in JSON

Access path dependence is easiest to see if you re-derive it in a modern setting. Suppose you want to store information about authors, books, and who wrote what.

In the relational model this is straightforward: an authors table, a books table, and a third table with two columns connecting them.

In a JSON database like MongoDB, the first thing most people reach for is nesting:

{ "author": "author1", "books": [ {…book1…}, {…book2…} ] }
{ "author": "author2", "books": [ {…book3…}, {…book4…} ] }

There are two problems, and only one of them is the obvious one.

The obvious problem is duplication. If a book has two authors, and the full book record — title, publication date, and so on — is embedded under the author, then that information has to be stored in two places and kept consistent in both.

The second problem is access path dependence. Any program written on top of this structure assumes an author-to-book hierarchy. Flipping it to books-containing-authors has exactly the same problem in the other direction. This is precisely what Codd identified in the context of the hierarchical model, translated into JSON.

The third option is to keep two collections and store book IDs inside the author document — effectively keeping pointers. This is better, but note what it costs. You now need a join, and MongoDB did not support joins in the beginning, which meant pulling both collections out and joining in application code. And it still has access path dependence: your program has to know that authors carry an array of book IDs rather than the other way round.

There is also a subtler point that comes up repeatedly with hierarchical structures: in the nested version, you cannot store a book that has no author, because your entry point is the author.

Is logical data independence any better in relational systems? Only somewhat. Physical data independence — changing sort orders and storage layouts without touching applications — is largely achieved. Logical data independence is harder even for relational databases, because the fact that there are three tables is itself hard-coded into the application: the SQL queries are written against those three tables, and merging or restructuring them will change the application. Views help, but achieving real logical data independence requires discipline.

3. The Hierarchical Model: IMS

IMS: record types arranged in a hierarchy

IMS, built by IBM for the Apollo program, is the canonical hierarchical system. Its main constructs are a record type (a schema), an instance (which must obey the schema), and keys to uniquely identify records.

Record types must be arranged in a hierarchy. Record instances are stored using that same hierarchy, and records with the same parent are stored as a linked list in a specific order.

The running example throughout the paper is suppliers and parts — the same example Codd used in 1970, which Stonebraker continues to use. In a supplier-over-part hierarchy, each supplier record points to a list of supplies, and the part information is embedded inside each of those. So a part supplied by two different suppliers has its details duplicated in both places. And if you update it in one place, someone has to make the change in the other — IMS would do this for you, but fundamentally the work has to happen. This is the repeated-information problem, and the theory of normalization was developed precisely to handle it, because repeated information means the potential for inconsistency.

The other structural limitation is the existence dependency already noted: you cannot store a part that no supplier supplies.

IMS’s query language and storage options

The language, DL/1, was record-at-a-time. Programmers had to keep track of “currency” indicators in their own programs, which leads to complex edge cases. Code looked roughly like: get the unique supplier, then within that supplier get all parts with colour red — so the hierarchy was encoded directly in the query code.

There were multiple storage options — sequential, B+-tree, hashing — and whatever option you chose had to be reflected in your code, because some constructs were not available under some options. You could not use get-next on hashed storage, for instance. So physical independence was broken there too, though IMS did support some physical data independence in that DL/1 was written against the logical hierarchy to a degree.

Several hacks were added later to support non-tree-structured data, which added considerably more complexity. By that time relational databases were arriving, and there was not much further innovation in this space.

The lessons, and why they are current

What we learned, and where the same issues appear today

Three lessons the paper draws:

Physical and logical data independence are highly desirable.
Tree-structured data models are restrictive — not general enough, and hard to modify.
Manual query optimization is unlikely to work over the long term.

And then the observation that makes this history worth reading: we see the same issues with the JSON and XML databases of today. No logical data independence — the hierarchies get hard-coded into queries. Significant physical data independence, though, which is the genuine improvement: ordering and indexes are no longer hard-coded into the language.

It is worth naming why this chapter is on the syllabus at all, since a history of superseded models could easily be an antiquarian exercise.

The claim is not that JSON databases are hierarchical databases repeated. It is that the specific failure mode has an invariant cause: any model whose primary structuring device is containment forces the application to commit to one containment order, and that commitment leaks into every query written against it. IMS made you commit to supplier-over-part; MongoDB makes you commit to author-over-book. The physical-independence problems were solved by better engineering. The logical-independence problem was not solved, because it follows from the shape of the model rather than from the implementation.

Which is why “we already learned this” is a substantive criticism rather than a territorial one.

4. The Network Model: CODASYL

CODASYL: a directed graph model with record-at-a-time access

CODASYL replaced the tree with a directed graph data model, still with a record-at-a-time data manipulation language. It has fewer restrictions than IMS — three-entity relationships, for example, are difficult for a strict hierarchy and fine for a graph.

But it is much more complex for the programmer. Charlie Bachman’s Turing Award lecture was titled The Programmer as Navigator, which is an accurate description of the work: you kept track of a set of “currency” pointers and manipulated them through the data to get where you wanted. Reading CODASYL programs today, it is genuinely surprising that this was regarded as an improvement on the hierarchical model — but it is hard to put ourselves back in that era, and a great many smart people thought it was a good idea. Codd looked at it and concluded it did not make sense.

Other limitations: limited physical or logical data independence, and it was harder to bulk-load data.

The modern connection: CODASYL is very similar to today’s property graph model. The differences are that current graph databases show significantly more physical and logical data independence, depending on the implementation — and that you need to enforce schemas, which many graph databases today do not.

Two qualifications worth carrying forward. First, many of the identified limitations of CODASYL were really about the language and some implementation choices rather than the model itself. Second, it bears a strong resemblance to the entity-relationship model at the conceptual level — though the E/R model never really had an implementation or a query language, which makes them hard to compare directly.

5. The Relational Model

Codd’s motivation, as the paper reports it: “IMS programmers were spending large amounts of time doing maintenance on IMS applications when logical or physical changes occurred.” The proposal follows directly from that diagnosis:

Store the data in a simple data structure — tables. All the data is tabular anyway.
Access it through a high-level, set-at-a-time DML — relational algebra, later SQL.
Mandate no physical storage design. Each system can do its own and change it as needed. As long as you support the language, we are fine with it.

The wins over what came before: three-entity relationships are easy to represent, where they are difficult for the network model. There are no existence dependencies of the kind that plagued the hierarchical model.

The cons the paper lists: transitive closure is awkward (though in practice transitive closure does not get used all that often, so it is not clear how much this mattered); performance, initially — this was the single biggest argument against the model, and it was resolved fairly quickly, because it turns out not to be that difficult to implement the model efficiently; and the language was initially too complex and mathematical, since Codd was a logician who proposed an algebra rather than a usable language. People designed usable languages fairly quickly afterwards, essentially by giving names to the symbols — calling \(\sigma\) “select” and so on.

The debates

The 1970s debates between the relational and CODASYL camps

The arguments on each side are worth reading in full, partly because they are a good example of how technical disputes actually go.

Relational advocates: nothing as complex as CODASYL can possibly be a good idea; CODASYL does not provide acceptable data independence; record-at-a-time programming is too hard to optimize; and CODASYL and IMS are not flexible enough to represent common situations easily.

CODASYL advocates: COBOL programmers cannot possibly understand these new-fangled relational languages; it is impossible to implement the relational model efficiently; and CODASYL can represent tables anyway, so what is the big deal?

Both camps moved toward each other over time — relational systems got user-friendly languages (SQL, QUEL) and efficient implementations. The debates in the mid-1970s were fierce; some of the transcripts survive and are worth skimming.

According to the authors, the debate was effectively settled by the mini-computer revolution and by IBM announcing new relational products — plus the non-portability of CODASYL engines. That last mechanism is the interesting one: IBM was, relative to its era, larger than Google or Apple are now; it had IMS and it had the biggest customers; and when it declared that its next product would be relational, that declaration settled the argument. When mini-computers arrived and people needed to develop for them, building something new made more sense than porting a CODASYL engine.

The best single piece of testimony is from Don Chamberlin, an early CODASYL advocate who went on to co-invent SQL:

“He (Codd) gave a seminar and a lot of us went to listen to him. This was as I say a revelation for me because Codd had a bunch of queries that were fairly complicated queries and since I’d been studying CODASYL, I could imagine how those queries would have been represented in CODASYL by programs that were five pages long that would navigate through this labyrinth of pointers and stuff. Codd would sort of write them down as one-liners. These would be queries like, ‘Find the employees who earn more than their managers.’ He just whacked them out and you could sort of read them, and they weren’t complicated at all, and I said, ‘Wow.’ This was kind of a conversion experience for me, that I understood what the relational thing was about after that.”

6. The Entity-Relationship Model

The E/R model represents entities and relationships, and the connections between them, explicitly. It has constructs for the cardinalities of relationships, derived attributes, multi-valued attributes, primary keys, and so on. It is a good deal easier to read than a relational schema.

Historically it comes after the relational model, even though courses usually teach it first because it is the higher-level model.

It had no real uptake as the physical data model used by a database. It has a lot of similarities to CODASYL, and it is easy to map to relational — which is precisely why it did not need to be implemented directly.

What it is used for today, thirty-five to forty years later, is initial schema design. You draw the diagram and map it to a relational schema. It fits that use case well, because normal forms are too difficult to work with directly and do not address the question of how to get started.

The connection to modern practice: ORM frameworks like Ruby on Rails and Python Django are E/R models in disguise. Those frameworks explicitly model object types and relationships between them; they are very widely used by application programmers; and they are typically mapped to an RDBMS at the back end — not always faithfully. Django is the most explicit about it, using language that maps closely onto E/R vocabulary. They are also similar to property graphs, assuming schemas are enforced.

A position worth arguing with: in my opinion the E/R model should be resurrected as the primary model for relational databases. Maintenance of relational schemas is too hard, and changes made over time lead to un-normalized schemas with many problems.

The mechanism is worth spelling out, because it is the subject of one of our readings. The initial schema is usually good, because it came out of the E/R design exercise. But once you start making changes, you lose that structure — because the changes are made to the relational schema, not to the E/R diagram you started from. And the relational model imposes no constraints on you: if you were forced to work in the E/R model you would have to follow its constructs, whereas in the relational model you can do whatever you want. This is a large part of why schema change is a major problem in practice. See “Database Decay” (Stonebraker et al.), which we discuss next week.

7. Semantic and Object-Oriented Models

Semantic data models

The 1980s produced many proposals aimed at applications that were not a good fit for relational — CAD, text management, time, graphics. A representative example is GEM (Zaniolo, 1983), which offered:

Set-valued attributes — for instance, the available colours of a part.
Cascaded dot notation — supply.part.color, the same thing ORMs give you.
Inheritance hierarchies.

Two of these three are now part of the relational world: relational systems support arrays (though not as well as GEM did), and the cascaded dot notation is there. Inheritance hierarchies are the one that did not make it. A hierarchy of person → instructor / student, with instructor further split into lecturers and tenure-track, is a natural structure that the relational model has no notion of. It requires you to map the hierarchy onto a set of relations — either one relation with a type flag, or a separate table per entity type — and both have pros and cons. Either way, the relational model requires you to make that decision, where E/R and GEM would have represented it directly.

The paper’s verdict is that these models offered no real improvement over relational in either functionality or performance, and that some of the key constructs could simply be added to the relational model, which is what happened.

Object-oriented databases

The motivating problem is the impedance mismatch: how data is represented in memory, typically as objects, versus how it is stored, in a normalized relational schema. You end up mapping back and forth constantly, and that mapping is expensive and painful to maintain. ORM frameworks handle it for you — but that just shifts the problem rather than removing it.

Object-oriented databases said: let us define classes and store the objects directly. What they became, essentially, is persistent programming languages. When a program quits, its objects are gone unless you serialize them — and serialization is expensive and loses the benefits of object storage, because every load requires deserialization. If an object is megabytes or gigabytes in size, that cost is significant, and ideally you would deserialize only the parts you need. That is the problem these systems solved, and it is not an easy one. Pointer swizzling — translating between in-memory pointers and on-disk references — is the interesting technical challenge here, and there are genuinely nice ideas in that literature.

Why they did not succeed:

Weak support for transactions and queries. They were largely single-user systems, and the DBMS had to run in the same address space as the application — for both historical and technical reasons.
No major additional functionality for most applications, which made it a niche market.
No standards, and they were too tied to a single programming language.

They bear many similarities to today’s graph databases — OrientDB is basically an object store — though graph databases tend to have a clearer logical model and a clear query language, which object-oriented databases did not.

How do object-oriented databases differ from ORMs? The lines blur, but object-oriented databases let you create objects and link them directly, which makes them more similar to graph databases than to ORMs. ORMs never had that; they sit on top of a relational system. You could reasonably ask why nobody put an ORM framework on an object-oriented database — that is a fair question, and simply not what those systems did. Their abstractions were different.

Object-relational databases

Object-relational: user-defined types, operators, functions, and indexes

This is the one that succeeded, in the sense that it produced significant lasting changes to relational databases. The motivation was the need to represent more complex data types — locations, rectangles, complex numbers. You can do this in the relational model to some extent, but it is painful and error-prone.

Postgres, the Berkeley research project led by Stonebraker, was the first real implementation, and it used geographic information systems as its motivating application — storing points and rectangles. The proposal was:

User-defined types. Fundamentally this is what it comes down to: before this, relational databases had a fixed set of types — integers, character arrays, floats.
User-defined operators, so you could change what + means on your types.
User-defined functions to work on those types — for example, to test whether a point lies inside a rectangle. Instead of writing out the coordinate arithmetic by hand every time, you write contains(rect, point).
User-defined indexes, since B+-trees do not work well on spatial data. This was a genuinely cool idea that never went anywhere, because they are very hard to make work.

All of this was in the original Postgres paper, which is remarkable in retrospect. User-defined types and user-defined functions are now near-universal.

The paper singles out UDFs as the major long-term benefit, for a reason that is not about data modelling at all: by putting code in the database, you avoid many round trips between client and server. Without stored procedures, running several SQL statements means several round trips; with a UDF, it is one call, everything happens server-side, and the result comes back.

The distinction to keep clear: object-relational did not change anything about the relational model. It allowed the data types to be more complex. You still do not have arbitrary pointers — which is exactly what object-oriented databases struggled with. Today’s relational databases really ought to be called object-relational databases; they are not pure relational.

8. Semi-Structured Data: XML and JSON

Flexible schemas: “schema later” and “schema on read”

Around 2000, when this article was first written, XML was extremely popular in both industry and academia. Anywhere you see XML in this discussion, you can substitute JSON; for these purposes they are essentially identical.

The main claimed benefit was flexible schemas — “schema later” or “schema on read”. Rather than requiring a schema in advance, you impose it when reading, or you make it part of the data itself. Relational databases will reject any data that does not conform to the schema; these systems will not.

This is easy to state and hard to use, because of semantic heterogeneity. And these databases genuinely do support easy schema evolution, which is a real benefit especially in early application development.

Why “self-describing” does not deliver what it promises

The rhetoric at the time was that XML is self-describing — you read the XML and it makes sense. Consider a document with a field:

<wages>2000</wages>

What does that mean? It tells me the number 2000 refers to this person’s income. It does not tell me whether that is 2000 dollars, 2000 euros, or 2000 rupees; nor whether it is per week, per day, or per hour. Which means that if I receive two such documents from two different sources, I do not know whether the two wages values are even in the same unit, and I cannot meaningfully compare them.

So attaching attribute names to the data does not solve the problem. You can read it — it is text — but you still need an interpretation on top of it. In other words, you need a schema: a shared understanding of what the fields mean. The early XML work said schemas were not needed, and it turned out that without one you genuinely do not know what to do with the data.

There were attempts to standardize field names — XML namespaces were a big deal at the time, and people tried to come together to define namespaces for specific application domains. That effort is very complicated and largely did not go anywhere, though namespaces do exist for some domains.

Isn’t this equally true of relational databases? Yes and no. Semantic heterogeneity does have to be resolved at the application layer either way. But when a relational database has a wages field, there is an assumption that someone has clearly defined what that field means. That interpretation may not live in the database itself — a real limitation — but it is usually written down somewhere.

The difference is in what is being claimed. Relational databases are not pretending to solve the problem; they are saying that if you want to put wages in this column, make sure it conforms to whatever semantic interpretation has been agreed. The XML pitch was that you could send someone a document and they could make sense of it, and that pitch was false.

Constructs, and what actually happened

The main constructs, then and now:

“Self-describing” — attribute names are part of the data.
Hierarchical format — so they look a great deal like hierarchical databases.
Links to other records, like CODASYL.
Set-valued attributes, which lead to a more complex language.

One technical correction worth making: XML and JSON are not really set-valued, they are array-valued — position matters. In a set-valued attribute you do not care about ordering; in an array you do.

XML became popular early as an on-the-wire format, a role JSON now occupies. It is text-based, so it goes through firewalls; it is not proprietary. JSON is widely used for APIs today, though many legacy systems still use XML — Salesforce’s primary API interface is XML. For large volumes of data, formats like Parquet are more common, and Parquet is best understood as storing a large collection of JSON-like records. (We will come back to it when we read the Dremel paper.)

From the Red Book’s background chapter, written roughly a decade later: XML did not take over. The reasons:

Too complex, especially the query languages. XPath was simple and became widely used; XQuery was the real language that supported joins, and it was so complex you could barely follow what was going on.
Inefficient implementations, particularly for indexes. Nobody implemented XML efficiently.
No compelling use cases.

JSON is more popular and very similar. It is good for sparse data, and can be handled by adding a JSON data type to the database. Schema-on-read is basically just a projection onto the few attributes you care about. And it still does not solve semantic heterogeneity.

Document databases succeeded where XML did not, and the reason is instructive: they had a real use case, they did it really well, and they did not pretend to do much else. None of them had query languages initially; MongoDB added one much later. It was a storage and retrieval mechanism, and that was enough. JSON databases like MongoDB are here to stay — they are functional, quite mature, and work well for their use cases.

Can two records with different structures live in the same collection? Yes — you can throw both into MongoDB with no issue, unless you are enforcing schemas. In any real use of MongoDB you typically find schemas being enforced anyway, via a validation phase or a layer on top. MongoDB has decoupled the decision: the system itself does not care, but most usage puts schema enforcement above it.

What happens if you query a field a document does not have? In MongoDB you get a null back, and your application has to decide what that means.

9. The Modern Zoo

Quite a few data models emerged from the NoSQL world, but by and large they map closely onto one of the ones already discussed.

Document data model — JSON, XML. Covered above; popular today.

Key-value. It is debatable whether this even counts as a data model. The interface is put(key, value) and get(key). A great deal of the variation is in what the “value” is and how it is manipulated: some key-value stores do not interpret the value at all, others do — Cassandra does a good job of storing time-series-like values. The key point is that key-value stores were never trying to be full-fledged databases. Their goal was to store billions of key-value pairs, and that is what they did. Query languages were layered on later.

Graph data models. There are a few. RDF is a collection of triples: source node, target node, and edge label, each a single value — so an RDF database is a set of edges. Property graphs have more structure: nodes can carry a label plus an arbitrary set of properties, and so can edges, and you can query on those properties. Neo4j’s Cypher is the best-known property graph language. As with document databases, the schema question arises: my sense is that any real use of graph databases puts a schema on top, and there is a recent proposal defining a notion of schema for property graphs.

Column families, as in Cassandra — puts a little more structure on key-value by storing the values themselves as columns of information.

Array data models, proposed for scientific data management. The key abstraction is an array or matrix; the key operations are slicing, subsetting, and filtering. SciDB was the main effort here, dating from around the late 2000s. These never caught on as general-purpose databases, or even as a significant niche, because the operators needed in scientific data management tend to be very specific to each application, which makes a general-purpose system hard to build. There is renewed interest in matrix-oriented interfaces now because of machine learning, though not much of it is database work.

10. Takeaways

Pulling the history together:

The relational model, and models like it, are what we keep ending up with. Not because the alternatives were bad ideas, but because the criteria in Section 1 are hard to satisfy simultaneously and relational satisfies them well.

Schemas are really important. People resist this, but without schemas you cannot do much with large collections of data. This comes up again and again — in the XML story, in the MongoDB story, in graph databases now proposing schema standards.

Semantic heterogeneity is not solved by any of these models. XML did not solve it, JSON does not solve it, and it is a genuinely hard problem that has to be addressed separately.

And the historical pattern the paper is really about: the arguments recur. Each generation proposes a richer, more flexible model; discovers that flexibility costs optimizability and logical independence; and rebuilds the things it discarded. Knowing the earlier round is the cheapest way to skip some of the next one.