CMSC724: Introduction — Motivation, Definitions, and a Brief History
Instructor: Amol Deshpande
1. Why Study Databases?
The short answer is that there is an enormous and continuously growing amount of data in the world, and database systems are the systematic way we have developed for managing it. That answer is true but unsatisfying, so it is worth understanding where the field came from and why it is still an active research area sixty years later.
Databases arose out of a concrete operational need. If you go back to the early 1960s, the earliest systems that we would recognize as databases were built for military, aerospace, and large enterprise applications — organizations that had accumulated large volumes of data and needed some way for many different people to build programs against it. Until that point, data lived on punch cards and magnetic tape, and each programmer wrote their own code directly against that physical representation. That approach works for one person and one program. It does not work once you have a team of people, several applications, and a shared data set that all of them need to read and modify. The moment data becomes shared, you need something in the middle: a store of data that many different applications, many different programs, and many different people can access without each of them having to know how the bytes are arranged.
The early literature actually called these systems “data banks” — the phrase appears in the title of Codd’s foundational paper — before the field settled on “database.”
There is a second reason to study databases, which is more specific to a graduate course. There was a period in the late 1990s and early 2000s when it genuinely seemed as though the core database problems had been solved. Relational systems worked, SQL was standardized, transactions were well understood, and the sense in parts of the community was that the interesting work was done. That turned out to be spectacularly wrong. The last twenty years have produced more architectural innovation than the preceding thirty, and this course reflects that: most of the papers we read are from after 2000. The foundations laid in the 1970s and 1980s remain essential, but the specific techniques and systems from that era were designed around hardware assumptions — expensive memory, slow random disk access, single machines — that no longer hold. It is genuinely difficult to reason about a system designed for 1985 hard disks in the same breath as a cloud-native system built on object storage and SSDs.
So the field is not finished. Understanding why it is not finished, and what the open problems look like, is one of the goals of this course.
2. What Actually Makes Something a “Database”?
If you ask a room of graduate students to name databases they have used, you get a list that looks something like this: MongoDB, SQLite, PostgreSQL, MySQL, Redis, Cassandra, Hadoop MapReduce, Spark, DuckDB, Snowflake, Redshift, Aurora, Oracle, SQL Server, DB2, Neo4j, Pinecone, etc. — and, if you push a little, Amazon S3.
That list immediately raises an important definitional question: what makes any of these a database, and what distinguishes them from each other? Some of the items are not databases at all under most definitions. Hadoop is an ecosystem rather than a system (Hadoop MapReduce is the specific thing). FAISS is a vector index library, not a data store. S3 is an object store that behaves in many respects like a file system. And yet the boundaries are blurry enough that the question is worth taking seriously rather than waving away.
The five user-facing questions
A useful working answer is that the type of a database is defined by what it exposes to its users, not by how it is built:
- Data model. What are the primitives? Relations? JSON documents? Key-value pairs? A graph? A set of opaque objects?
- Query language or programming framework. SQL, a MongoDB query expression, a Spark RDD/DataFrame program, or nothing more than
get/put. - Transactions and update support. What can you update atomically, and what happens when two clients update the same thing at once?
- Performance guarantees and focus. Is this optimized for point lookups, for scans, for low-latency writes? Is it single-node, parallel, or geo-distributed?
- Consistency guarantees. What does a reader see after a writer commits?
Apply these to the list above and the structure becomes clear. SQLite, PostgreSQL, Oracle, SQL Server, and DB2 all expose essentially the same thing: the relational model, SQL, and transactions. They do not support identical SQL — SQLite supports a fairly limited dialect while PostgreSQL and Oracle have accumulated decades of language features — but they support recognizably the same language over recognizably the same model. Redis and HBase, by contrast, expose a key-value interface: you put a value under a key and get it back by key. There is no query language in the usual sense. S3 is also broadly a key-value store, though the difference in intended object size — S3 is designed for large objects, Redis and HBase for small ones — has enormous consequences for how each is built internally.
Small differences in the exposed contract propagate into very different implementations – this is a theme we will see throughout, and being able to recognize this is a key learning outcome of this course.
Transactions are where these systems diverge most visibly. Relational databases are mature here; supporting fine-grained, efficient, correct updates is one of the things they do really well. MongoDB, for most of its history, did not: it offered very weak guarantees around updates, and even today its transactional support is more limited than a relational system’s. S3 has its own peculiarities but does provide atomic put, which matters enormously — if two clients write the same key simultaneously, the output is well-defined – guaranteeing this is not a trivial engineering problem.
The distinction that people keep collapsing
Notice what is not on that list: storage layout, indexing structures, query execution strategy, the target hardware environment. Those are implementation concerns. They are enormously important — we will spend most of the semester on them — but they do not define what kind of database a system is. When you say “PostgreSQL is a relational database,” you are making a claim about its interface, not about how it lays out pages on disk.
This distinction between the user-facing abstraction and the implementation is one that even researchers in this field collapse routinely. The most persistent example is graph databases. People frequently define a graph database as a system that stores explicit pointers between records. But that is an implementation choice. Whether you materialize pointers between records or reconstruct relationships from a row-oriented store is a decision about performance, not about what the system is. What makes a graph database a graph database is the data model it exposes (usually property graph or RDF), and the query language you write against it (Cypher, SparQL). Keep the two separate; a great deal of confused writing about data systems comes from conflating them.
We will return to this framework repeatedly. It is, essentially, a restatement of data independence — the idea that applications should be insulated from how data is stored — applied at the level of comparing whole systems rather than individual schemas.
3. The Modern Landscape
It is worth spending a few minutes with Matt Turck’s annual “Data & AI Landscape,” which has been published in some form for the better part of a decade – just to appreciate the sheer breadth of activity in this space.
The infrastructure portion alone contains dozens of companies working on storage, on massively parallel analytics systems (Teradata, founded 1979, sits alongside Vertica and Greenplum and a dozen others), on data lakes and warehouses — a category that barely existed a decade ago and has since exploded — on streaming and in-memory processing, on relational, NoSQL, NewSQL, real-time, graph, and vector databases, and on the whole ETL and data-preparation layer that sits upstream of any of it. Much of this is startup activity from the last ten years.
The other observation worth making is that a large fraction of the activity in this landscape has nothing to do with AI. There is a substantial AI segment, but the non-AI data infrastructure segment is at least as large and is growing on its own terms. This is a very active area to be working in right now, independent of what is happening in machine learning.
4. A Brief History: 1960s Through the 1990s
The 1960s: hierarchical and network models
The first systems appeared in the early 1960s, motivated by shared “data banks” in military and aerospace applications. The dominant data models were the hierarchical model and the network model, the latter codified by CODASYL — the same committee responsible for COBOL, which also dates from this era and, amusingly, remains widely deployed enough that COBOL maintenance might be among the last programming jobs to be automated away.
IBM built IMS (Information Management System), a hierarchical database, for the Apollo space program, and then sold it to everyone else. IMS is still in production today; the understanding is that it remains a backbone of significant parts of the banking industry, because that infrastructure — ATM networks and the settlement systems behind them — was built decades ago and there has never been a sufficiently compelling reason to replace it. IBM still maintains and supports it.
The defining characteristic of these models, from a modern standpoint, is that querying them required navigating explicit structural links: you told the system how to get to the data, following parent-child or owner-member relationships, one record at a time. Your program was written against the structure of the storage.
The 1970s: the relational paradigm shift
In 1969, Ted Codd — a logician at IBM San Jose — circulated an internal report proposing the relational model, published the following year in CACM as “A Relational Model of Data for Large Shared Data Banks.” It is about as close to a genuine paradigm shift as this field has produced, and people who were around at the time describe it that way.
Codd had watched people struggle with COBOL and with the navigational models, and his argument was essentially that there was a much simpler way to think about data. The paper is, in form, a theory paper. It defines an algebra (which eventually led to SQL), and it introduces the notions of keys and normal forms. We do not read it in this course, but it is worth reading on your own once your background is fresh — it is striking how much of modern practice Codd anticipated, and how clean the model looked against the alternatives of the day.
The response was fast. Two research prototypes appeared: INGRES at Berkeley (Stonebraker and Wong) and System R at IBM. Both contributed enormously, but System R produced the larger share of the systems innovations that survive today:
- Query optimization. Selinger et al.’s 1979 paper, “Access Path Selection in a Relational Database Management System,” introduced cost-based optimization with dynamic programming over join orders. Essentially every subsequent paper on query optimization cites it. We will read the ideas in it later in the semester.
- Transactions. The concepts underlying what we now call the ACID properties were worked out in this period, notably in Jim Gray’s 1976 work on granularity of locks and degrees of consistency. (The acronym ACID came later, from Härder and Reuter in 1983.) Gray’s work on transaction processing was a major part of what earned him the Turing Award.
Also in this decade, Peter Chen proposed the Entity-Relationship model (1976), which remains the standard vocabulary for conceptual database design.
The commercial consequence: System R led to IBM DB2, one of the dominant systems for decades. It also, less directly, led to a 1977 startup called Software Development Laboratories, founded by people who had read the published System R papers. Its flagship product was Oracle, and the company eventually renamed itself after it.
There is a lesson in why Oracle won the market despite arguably weaker technology early on: IBM had to care about mainframe compatibility and about not disrupting its existing customers, and that slowed it down enormously. The startup had no such constraints. It shipped features fast and captured the market. This pattern — an incumbent constrained by compatibility obligations losing to a faster-moving entrant with a clean slate — recurs throughout the history of this field, and it is worth watching for as we read papers about newer systems.
The 1970s also saw fierce debates between the relational and CODASYL camps, each convinced the other was fundamentally wrong. The relational side won, and the reason is worth stating precisely: it was not primarily about performance (early relational systems were slower), it was about data independence. The navigational models required applications to encode the physical access path; the relational model let you say what you wanted and left the how to the system. That decoupling is what made everything after it — optimizers, index selection, changing storage layouts without rewriting applications — possible.
The 1980s: consolidation and richer models
DB2 shipped in 1983, and SQL was standardized in 1986. This is also the decade of “the relational model is too simple” — many proposals for richer semantic models, object-oriented databases, and object-relational databases. Almost none of them succeeded commercially. That is a data point worth holding onto, because the same argument gets made every few years about whatever the current model is, and it fails for the same reason each time: richer models are harder to query, harder to optimize, and harder to reason about, and the added expressiveness usually does not pay for that.
Postgres — “post-INGRES” — was started by Stonebraker at Berkeley in 1986. Its long-term influence has come more from the project and codebase than from its specific research ideas. In fact, when the open-source community picked it up, they ripped out both the original query language and the original storage engine. Stonebraker’s 1987 paper on the Postgres storage system is a fascinating read, but the design was far ahead of what the hardware of the time could support; it worked as a research prototype and never made sense in production at that time.
The 1990s: the web changes the shape of the problem
The World Wide Web arrived (1989) and the pace of everything accelerated. Several threads ran in parallel:
- Parallel databases emerged in the late 1980s and early 1990s, tracking the hardware trend toward multi-machine deployments.
- Data mining and OLAP. With transactional data collection largely solved, organizations started asking the next question: what can we learn from this? Business reporting and analytical query processing became a distinct workload with distinct requirements.
- Middleware and the client-server model. You cannot connect an end user directly to a database – both from a usability perspective (would the analysts write SQL?) and more importantly, from security perspective. So a layer grew in between: application servers, connection pooling, business logic. This became a large industry in its own right and shapes the architecture we will study later.
- PostgreSQL forked from the Postgres codebase in 1996. The Berkeley group had finished with the project, cleaned it up, and released it under a permissive license; others picked it up and kept going. Thirty years later, PostgreSQL is arguably the best general-purpose database system available for a very wide range of use cases — an outcome that would have been hard to predict from a released-and-abandoned research prototype.
- XML became a data management problem in the late 1990s, and data integration emerged as a central open problem. Data integration has the distinction of being the problem that everyone assumed would never be solved: combining data from heterogeneous sources and making it usable is quite hard, and it stayed hard for twenty-five years. It is one of the few places where large language models may actually be changing the calculus, which we will come back to.
5. A Brief History: 2000s to Today
2000–2005: two architectural shifts
Around the turn of the millennium a cluster of data warehousing and analytics companies appeared more or less at once — Aster Data, Greenplum, Vertica, Kickfire, Netezza, ParAccel, and others. Most were built on or around PostgreSQL, with parallelism layered on top. Two architectural changes distinguish this generation, and both are consequences of hardware:
Columnar storage. MonetDB (CWI) and C-Store (which became Vertica) demonstrated that laying data out column-by-column rather than row-by-row is dramatically better for analytical queries, which typically touch few columns of many rows. This is one of the biggest architectural shifts in the history of the field, and we will spend real time on it when we get to storage models.
Shared-nothing architectures. As data centers became commonplace, these systems were built to use many independent commodity machines in parallel — each with its own CPU, memory, and disk — rather than one very large machine with many processors.
At the same time, main memory got big. It is easy to forget how recent this is. In the 1990s we talked about memory in megabytes; in the early 2000s in gigabytes; by the late 2000s many-gigabyte servers were routine. That shift enabled a second, independent architectural change: main-memory OLTP systems. Transaction processing systems could be redesigned around the assumption that the working set fits in RAM, which invalidates a great many design decisions inherited from the disk era.
So the 2000s produced two divergent architectural shifts from the previous thirty years: column stores for analytics, and in-memory processing for transactions. (This course will not spend much time on OLTP — CMSC 624 covers transactions in depth — but the architectural point matters.)
2006–2010: MapReduce, key-value stores, and documents
Google’s MapReduce paper (2004) and the Hadoop project that followed it at Yahoo (and quickly went open source) reframed large-scale data processing around a deliberately impoverished programming model (just two primitives: map and reduce) that was easy to parallelize and easy to make fault-tolerant.
Then came the key-value store explosion. Google’s Bigtable paper, Amazon’s Dynamo, Facebook’s Cassandra, LinkedIn’s Voldemort, Apache HBase as an open Bigtable implementation — at one point there were somewhere between fifty and a hundred of these. The reason is simple: key-value stores are easy to build, so every company built one. They subsequently consolidated, because it eventually became apparent that they were not meaningfully different from one another.
MongoDB launched in 2009 as a document database, and its success is worth understanding, because it is a case study in what actually drives adoption. It was not technically superior — it offered no ACID guarantees, weak durability, and you could genuinely lose data. What it offered was the removal of an impedance mismatch. JavaScript had become the dominant application language, applications manipulated JSON objects, and JSON objects were what developers needed to persist. With PostgreSQL you had to define a schema up front, convert your JSON object into a relational tuple to store it, and reconstruct the object on the way out. MongoDB let you take the object and throw it in. The benefit in simplicity and time-to-first-working-prototype was so large that it dominated a segment of the market for years, despite the weak guarantees.
It is also a case study in the limits of that strategy. Between roughly 2010 and 2016 there was a steady stream of “why we migrated from MongoDB to PostgreSQL” blog posts from teams that had hit scaling or correctness walls. That has largely stopped — MongoDB is a much more mature system now, fifteen years on, and there is far less reason to migrate away. But note how it matured: by adding back the guarantees it had originally discarded.
Graph databases also date from this period (Neo4j, 2007), but have had substantially less impact than document databases.
The 2010s: the cloud
The defining change of the 2010s is that you stopped having to own the hardware. Cloud-hosted data warehouses (Snowflake, Redshift) and cloud-hosted transactional systems (Aurora, CosmosDB, CockroachDB) took over. Every system before this required you to provision and operate your own machines; these systems provide them. That is a business-model change with deep architectural consequences — the separation of storage from compute, which cloud warehouses pioneered, is a genuine technical innovation and not just a pricing decision.
Apache Spark emerged in the early 2010s and has been highly influential. The data lake term was coined in 2011 and the pattern is now widespread, with Databricks the most prominent example.
The store-type landscape also diversified: fewer key-value stores (consolidation), but more of everything else — graph stores became more common, time-series databases went from essentially nonexistent to several widely used systems in a very short span, multi-model databases were proposed (though never became common), and vector databases rose sharply and appear already to be on their way back down as vector indexing gets absorbed into general-purpose systems.
The 2020s: where we are now
The last few years are harder to characterize while we are inside them. Blockchain-based data management attracted interest but has not gone anywhere in practice. There is substantial work on machine learning for databases — auto-tuning, learned indexes, natural language to SQL — which has real industrial traction. There is a mirror-image line of work on databases for machine learning, building ML support into the database, which as far as I can tell essentially nobody uses.
One active recent direction is LLMs for analytics over unstructured data, and it deserves attention because it is changing the tractability of problems that were previously considered intractable. Entity resolution — deciding whether two company names refer to the same company — is a canonical example: a genuinely hard problem that resisted decades of work, and one that now looks approachable. The open challenge is engineering around the failure modes of LLMs, particularly hallucination, in a setting where users expect a database to give correct answers.
Over the course of this semester, we will try to identify other promising research directions in this space.
6. Data Management Today
Two facts hold simultaneously. First, a large fraction of the world’s data still lives in traditional relational database systems, and this remains an active research area — performance, energy efficiency, new functionality, and adapting to a changing hardware spectrum are all live problems.
Second, a great deal of data does not live in a traditional DBMS, for a variety of entirely legitimate reasons: stream processing systems for real-time analytics, special-purpose data warehouses (most of which started from some RDBMS), batch analysis frameworks like MapReduce and Spark over distributed file systems, key-value stores (essentially persistent distributed hash tables), document stores for JSON and XML, graph databases, scientific and ML data management, and vector stores.
We focus on fundamentals in this course, primarily because we see the same ideas keep getting reinvented, and often the same mistakes get made along the way. Two patterns illustrate this vividly.
Everyone eventually implements (some variation of) SQL. Spark began as an explicitly non-SQL framework and now, anecdotally, most Spark usage goes through its SQL interface. MongoDB’s query language has converged toward something SQL-shaped. Cassandra and CouchDB both grew SQL variants. Vector databases are already adding query languages. Declarative querying over a schema keeps winning, and it wins for the same reason it won in the 1970s: it decouples what the user asks for from how the system computes it.
Everyone eventually implements transactions. A striking number of systems launched with the claim that ACID was unnecessary overhead, and quietly added it back once they were mature enough for people to run serious workloads on them. The intermediate stage was usually eventual consistency, a phrase that dominated the 2008–2015 period and functioned largely as a way to say “we provide some consistency” without committing to what. My blunt assessment is that as deployed, the term often carried no operational meaning: read the papers and try to extract a precise guarantee and you frequently cannot. There is serious formal work on weak consistency models — the CALM theorem, CRDTs, and Bailis’s work on quantifying eventual consistency all postdate the marketing usage — but the term as used in that era was mostly a placeholder for “we haven’t solved this.” Most of those systems now support standard ACID guarantees.
So a large body of technique developed over thirty or forty years in the relational world got rediscovered, in compressed form and often less carefully, in the NoSQL world. Learning the originals is a good way to avoid repeating the exercise.
7. What This Course Covers
The focus is a deeper study of relational systems than an undergraduate course provides. That is a deliberate choice, made after several iterations of this course: rather than survey many system families shallowly, we go deep on relational systems and treat other families in terms of how and why they diverge.
Concretely, the plan for the semester: - Background and overview (1 week) — this module - Data models and programming abstractions (2 weeks) — how the user-facing layers are built and the range of ways people have built them - Storage models (2 weeks) — including revisiting old design decisions, such as laying out data column-by-column instead of row-by-row, and fully in-memory processing - Query processing and optimization (5 weeks) — the largest block, and where we go deepest - Streaming data management and dataflow systems (2 weeks)
We will cover MapReduce-style systems and touch on key-value stores (with a focus on their consistency issues); semi-structured stores and graph databases if time permits. Data warehousing systems are not treated separately, because they are relational systems and much of what we discuss applies directly.
The reading is a blend of classic papers and ongoing research, weighted toward the latter. The reference book is Readings in Database Systems, 5th edition (Bailis, Hellerstein, Stonebraker), freely available at redbook.io; its overview chapters are excellent and short, and are worth reading even where we do not read the corresponding papers.
Learning goals
The goal is to prepare you for data management research, broadly defined — which includes recognizing data management issues when they arise in other fields. Specifically, by the end of the semester you should be able to:
- Read, understand, and critique a data management paper.
- Given a new application domain, ask the right questions to identify the key data management issues and propose appropriate solutions.
- Identify flaws in a proposed design.
- Reason about abstraction (independence) layers and where they should be drawn for a given domain.
- Have enough familiarity with how large-scale data systems are built to start using any of them and to reason — at least superficially — about the performance you observe from a deployed system.
That fourth goal is worth flagging: the ability to reason about where to draw an abstraction boundary is the single most transferable skill in this course, and it is exactly what the five-question framework in Section 2 is training.
8. Some Thoughts on Current State of the Field
A few observations that will recur throughout the semester, offered as open questions rather than settled conclusions.
There are too many specialized systems. There has been some consolidation, but the number of distinct data management systems in play far exceeds the number of genuinely distinct designs. Many of them are not meaningfully different from one another. This is a long-term structural problem for the field, not just an aesthetic complaint.
Specialization produces silos. What you see inside real enterprises is many data stores in simultaneous use that cannot talk to each other. The obstacle is not networking — it is that they do not speak the same schema, so one system has no idea what to do with another’s data. This is the data integration problem, resurfacing as an operational problem rather than a research one.
The standard remedies mostly relocate the problem. Federated query systems that sit on top of multiple stores shift the difficulty rather than removing it. Building an API layer over a system you cannot query directly solves an immediate need and adds long-term complexity; each such layer is another place where semantics can drift.
Security, privacy, and governance get worse, not better. These are, arguably, the largest challenges facing the data industry, and proliferation makes each of them harder. It is much easier to reason about access control, retention, and lineage in one system than across fifteen. We will not cover these topics directly, but keep them in view when evaluating architectures — a design that is elegant on performance grounds and ungovernable in practice is not a good design.
Relational-like models, schemas, and declarative languages keep proving to be the winning combination. This is the most reliable prediction in the field. Build a new system with a new model and a new interface, and within a few years users will ask for schemas and a query language, and you will end up supporting them. The interesting research question is not whether this happens — it does — but why: what is it about that particular combination that makes it the attractor? A good answer probably has to do with the fact that a schema is what makes optimization possible at all, and that declarative interfaces are what let the implementation evolve underneath a stable contract. That is data independence again, and it is the thread running through everything in this course.
9. What Comes Next
The next chapter reviews the background material this course assumes — essentially, a summary of CMSC 424. If those concepts are fresh, you can skim it; if not, it identifies specifically what to brush up on and where.
After that we turn to the architecture of a traditional database system, following Hellerstein, Stonebraker, and Hamilton’s Architecture of a Database System (2007). That paper answers the questions that undergraduate courses tend to leave open: not what a transaction is, but how a database system actually implements one when the operating system underneath it will not give it the control it needs.