Beyond the table: document, key-value, graph and wide-column stores

The relational model began as a claim about independence, and this lecture turns on a claim that looks like its opposite. A key-value, document, graph or wide-column store is built around one access pattern, fixed before the first record is written. It is fast exactly where that pattern holds.

Leavitt (2010) reported on the rise of these stores, then called NoSQL, and asked whether they would live up to their promise. This sixth unit answers that question in design terms. Every gain such a model offers comes from fixing the common access pattern in advance. The price is paid in the joins, constraints and consistency guarantees the relational model would have enforced.

A model is a bet placed on one access pattern

Cattell (2011) surveyed the field shortly after the non-relational stores appeared and gave the unit its frame. The stores he examines were designed to scale simple transaction processing over many servers. He contrasts them on data model, consistency, storage, durability, availability and query support, noting that they typically sacrifice some of these dimensions.

Sadalage and Fowler (2012) name the practice that follows. Polyglot persistence keeps different stores for different access patterns inside one system, matching each store to the shape of the reads and writes it serves.

Davoudian, Chen and Liu (2018) then showed that the choices are coupled rather than independent. Their survey organises NoSQL stores by four non-orthogonal design principles, namely data model, consistency model, data partitioning and the CAP theorem. Because the principles are non-orthogonal, changing the data model to fit an access pattern changes what consistency the store can offer.

Each family fixes one access pattern and pays for the others

A key-value store exposes lookup by a single key and little else. Cattell (2011) places it at the far end of his query-support axis. Because the only operation to optimise is key access, the store can be partitioned and replicated cheaply.

A document store keeps a whole document as the unit of retrieval, which suits a screen that reads and writes one thing at a time, and which makes every fetch heavy on a metered mobile connection. The cost arrives when the same fact belongs to many documents, because embedding it duplicates it and referencing it reintroduces the joins the model was meant to avoid. Sadalage and Fowler (2012) set this out as the trade a document store makes.

A worked case shows the price. An order system stores each order as one document and embeds the customer's delivery address inside it, because every screen that shows an order also shows where it went. When the customer moves, the current address belongs in exactly one place while the copies in past orders are historical facts that must not change, so the design has to distinguish the address as it stood then from the address today. A relational schema would have stored the customer once, and the question of what a historical order records would have been forced into the open at design time. The case is constructed to show the mechanism rather than to score the models: embedding a fact that also lives elsewhere makes the schema decide, silently, which copy is the record.

A graph model fixes traversal instead. Angles and Gutierrez (2008) survey models in which schema and instances are both graphs and manipulation uses graph-oriented operations, tracing them from the 1980s through decline and revival. Vicknair and colleagues (2010) state the gain. They found the relational system efficient unless the data required joins of large tables. The graph store was faster for the query shape it was built for. Set operations, cheap in a relational model, become the awkward case.

A wide-column store groups columns into families so that a large and sparse table can be scanned by row key. Cattell (2011) and Davoudian and colleagues (2018) both place the family on the same axes as the others. The habit of combining any column with any other through a join is the property it trades away.

A vector store fixes similarity rather than identity. Pan, Wang and Li (2024) survey over twenty commercial vector systems, all built within five years, and name the obstacles they share: ambiguous semantic similarity, large vectors, expensive comparison, and no structural properties to index. The access pattern is a nearest-neighbour query over embeddings, and the guarantees given up are the ones the other families trade.

The price is paid in joins, constraints and consistency

The relational model enforces two things a fixed access pattern cannot keep for free. One is the join, which lets a question combine facts that were never meant to be read together. The other is the constraint, which the model names and checks and which a store built around one pattern does not police. Where a rule cannot be named as a constraint, it moves into application code, which is where the independence claim of the first unit does not reach.

Pokorny (2013) records the third price. Studying NoSQL architectures and features in a cloud context, he notes their horizontal scalability and a concurrency model mostly weaker than ACID transactions. Weaker concurrency is part of the model choice rather than an implementation detail a later version will repair. Cattell (2011) reaches the same point by listing consistency among the dimensions his stores sacrifice.

Reviewing data management in cloud environments, Grolinger and colleagues (2013) argue that traditional relational databases were designed in a different hardware and software era. They review how NoSQL and NewSQL stores address the scale requirements of big data. The model choice is entangled with deployment, so the bet is also operational.

The case for a non-relational model is narrower than its promise

Vicknair and colleagues (2010) supply the case in which it pays. The graph store won on the traversal-shaped query, while the relational store won elsewhere on the same data.

Parker, Poe and Vrbsky (2013) compared MongoDB with a relational database for a modest amount of structured data, where the usual big-data argument does not obviously apply. They found the document store as good or better except on aggregate functions, which the relational engine won. It lost on the operation its shape does not serve, which is the discount this unit applies to any claim that a newer model is simply better.

Angles (2012) adds a finer grain. His comparison of current graph database models covers storage, querying and data-modelling features, and shows the family is itself a set of models with different trade-offs.

Contested question: a trade-off, or one coin with two faces?

The literature disagrees about whether the models are rivals at all.

The first position holds that the non-relational gains are overstated. Stonebraker (2010) considers several performance arguments made in favour of NoSQL databases, finds them insufficient, and defends the relational store against the claim that it cannot scale. On this reading the bet is placed against a model that already performs well enough, so it buys less than it costs.

The second position holds that the two families are not opposed. Meijer and Bierman (2011) argue that SQL and NoSQL are two sides of the same coin and present a co-relational model treating both as special cases. If the models are unifiable, the access-pattern bet is a difference of surface syntax rather than a design trade-off. That is the strongest challenge the thesis has to answer.

The third position holds that the binary dispute misdescribes the field. Pavlo and Aslett (2016) examine what is genuinely new in NewSQL systems and separate the technical claims from the marketing use of the term. Because current systems span both families, the question of SQL against NoSQL is too coarse to guide a design.

The fourth position, and the one this unit defends, holds that the choice is real and is made per feature. Davoudian and colleagues (2018) present the stores as coupled design choices, and Sadalage and Fowler (2012) make polyglot persistence the operational consequence. One system can legitimately hold several models, and the bet is placed for each access pattern separately.

What would settle it is a head-to-head evaluation on a named access pattern. The evaluation would report the constraints, joins and consistency outcomes the losing store cannot express. It would also report the cost of reproducing them in application code. Vicknair and colleagues (2010) and Parker, Poe and Vrbsky (2013) are single-case steps in that direction. Neither carries the constraint-and-consistency ledger that would separate a genuine trade-off from a difference of syntax.

Rate each side by its evidence. Stonebraker (2010) argues against a set of performance claims, reasoning rather than a measurement. Meijer and Bierman (2011) construct a co-relational model, and a shared semantics is not a shared cost. Pavlo and Aslett (2016) classify systems instead of testing them, and Davoudian and colleagues (2018) survey the design space. The strongest objection is that a shared semantics removes the trade-off at the level this unit defines it, so the access-pattern bet may belong to today's engines rather than to the models. While the dispute is open, a designer writes down what each feature must give up before choosing a store for it.

Where the argument is heading

Bizer, Heath and Berners-Lee (2009) describe Linked Data, the best practices for publishing and connecting structured data on the web, and report the growth of the Web of Data into a global data space. This is a model that answers the question without a single store, because relationships are published as links between sources rather than enforced inside one schema. Alongside it, Pavlo and Aslett (2016) show the families converging. The open question the sources here do not close is whether the access-pattern bet is a temporary cost of immature tooling, or a durable property of fixing a read shape in advance. The co-relational argument of Meijer and Bierman (2011) implies the first. The survey evidence of Cattell (2011) and Davoudian and colleagues (2018) supports the second.

The sources this unit rests on

• Angles, R. (2012). A comparison of current graph database models. Angles compares current graph database models on storage, querying and data-modelling features as the graph field consolidated.
• Angles, R. and Gutierrez, C. (2008). Survey of graph database models. The authors survey models in which schema and instances are both graphs and manipulation uses graph-oriented operations.
• Bizer, C., Heath, T. and Berners-Lee, T. (2009). Linked data: the story so far. The authors present the principles of Linked Data, the best practices for publishing and connecting structured data on the web. It carries the alternative to a single store, where relationships are links across sources.
• Cattell, R. (2011). Scalable SQL and NoSQL data stores. Cattell contrasts SQL and NoSQL stores on data model, consistency, storage, durability, availability and query support, noting that they sacrifice some dimensions. Scale in one access pattern is bought by giving up a guarantee elsewhere.
• Davoudian, A., Chen, L. and Liu, M. (2018). A survey on NoSQL stores. The authors organise NoSQL stores by four non-orthogonal design principles, namely data model, consistency model, data partitioning and the CAP theorem. Because the principles are non-orthogonal, the bet is placed on several coupled choices at once.
• Grolinger, K., Higashino, W. A., Tiwari, A. et al. (2013). Data management in cloud environments. The authors argue that relational databases were designed in a different hardware and software era, and review how NoSQL and NewSQL stores address the scale requirements of big data. The model choice is entangled with deployment.
• Leavitt, N. (2010). Will NoSQL databases live up to their promise? Leavitt reports on the rise of non-relational databases, now frequently called NoSQL, adopted by organisations collecting large amounts of unstructured data. It supplies the popular claim the unit scrutinises.
• Meijer, E. and Bierman, G. (2011). A co-relational model of data for large shared data banks. Meijer and Bierman argue that SQL and NoSQL are two sides of the same coin and present a co-relational model treating both as special cases. It is the strongest counter-position to the thesis.
• Pan, J. J., Wang, J. and Li, G. (2024). Survey of vector database management systems. Surveys over twenty commercial vector systems and the techniques built for them, covering similarity scores, quantization and partitioning for indexing, and operators for queries that search attributes and vectors together. It adds a family the unit's older surveys predate, fixing nearest-neighbour search over embeddings as the access pattern. It is a survey, not a benchmark.
• Parker, Z., Poe, S. and Vrbsky, S. V. (2013). Comparing NoSQL MongoDB to an SQL DB. The authors compare MongoDB with a relational database for a modest amount of structured data, where the usual big-data argument does not obviously apply, and find the document store equally as well or better except on aggregate functions. Any loss is specific to the operation the model does not serve, not to the model itself.
• Pavlo, A. and Aslett, M. (2016). What's really new with NewSQL? The authors examine what is genuinely new in NewSQL systems and separate the technical claims from the marketing use of the term.
• Pokorny, J. (2013). NoSQL databases: a step to database scalability in web environment. Pokorny studies the features of NoSQL databases in a cloud context, particularly their horizontal scalability and a concurrency model mostly weaker than ACID transactions. Weaker concurrency is part of the model choice, not an implementation detail.
• Sadalage, P. J. and Fowler, M. (2012). NoSQL Distilled: a brief guide to the emerging world of polyglot persistence. This guide names polyglot persistence, the practice of using different stores for different access patterns within one system. Only the publisher metadata and the book's landing page were verified, so it is cited for the practice and its argument.
• Stonebraker, M. (2010). SQL databases v. NoSQL databases. Stonebraker considers several performance arguments made in favour of NoSQL databases, finds them insufficient, and defends the relational store against the claim that it cannot scale.
• Vicknair, C., Macias, M., Zhao, Z. et al. (2010). A comparison of a graph database and a relational database: a data provenance perspective. The authors compare a graph database with a relational database through a data provenance example, finding the relational system efficient unless the data require joins of large tables and the graph store faster for the query shape it was built for.