Types of databases: relational, column, document, graph and time-series

Updated September 2026: corrected the relational algebra, the columnar and document database sections, and the time-series models.

Database systems sit underneath almost every modern application, storing and managing data so that it can be found and changed quickly. The word "database" is often used generically, but there are several types, each with its own characteristics and uses. This post covers the most common ones: relational, column-based, document, graph and time-series databases.

Relational databases

Relational databases organise data so that each piece can be identified and accessed in relation to other data in the database. They're usually managed with Structured Query Language (SQL), a domain-specific language for working with databases. The relational model organises data into tables, which can be linked, or related, through keys.

Practical application

Relational databases are used almost everywhere. In e-commerce, for instance, one table could store product information, such as product ID, name and price, while another tracks customer purchases. When a customer buys something, an SQL transaction can record the order and reduce the stock level of the purchased items together, so the inventory stays up to date.

Foundation

The relational model, proposed by E. F. Codd in 1970, is grounded in set theory and predicate logic. In the model, a relation (a table) is a set of tuples, and queries are built from the operations of relational algebra:

• The SELECT list of an SQL query corresponds to projection ($\pi$), which picks columns.
• The WHERE clause corresponds to selection ($\sigma$), which filters rows. Selection is a filter, not an intersection.
• A JOIN is a Cartesian product followed by a selection:

$$R \bowtie_{\theta} S = \sigma_{\theta}(R \times S) = \{\, (r, s) \mid r \in R \land s \in S \land \theta(r, s) \,\}$$

• UNION, INTERSECT and EXCEPT are the set operations union, intersection and difference.

One caveat: SQL tables are really bags (multisets), not sets, because they can contain duplicate rows. UNION removes duplicates, while UNION ALL keeps them.

This precise model is what lets the database enforce integrity rules such as primary keys and foreign keys, and lets query optimisers rewrite a query into an equivalent form that runs faster.

Column-based databases

Traditional relational databases store data row by row; column-based databases store it column by column. This suits analytical queries that read a few columns across many rows, and it's common in data warehouses and large-scale analytics. Storing similar values together also makes compression very effective.

Practical application

Imagine a weather monitoring system that collects large amounts of data, such as temperature, wind speed and humidity, from many cities. A column-based database can answer questions about one attribute quickly, for example the average temperature across all cities over a range of dates, because it only reads the temperature column.

Foundation

The underlying model isn't very different from the relational one; what changes is the physical layout. For a table with $m$ rows and columns $C_1, C_2, \ldots, C_n$, each column is stored as its own array:

$$C_j = [\, x_{1j}, x_{2j}, \ldots, x_{mj} \,]$$

Because each array holds values of one type, often with many repeats, columnar databases use techniques such as run-length encoding, dictionary encoding and bitmap indexes, and they process whole blocks of a column at once (vectorised execution), which uses modern CPUs efficiently.

Document databases

Document databases are designed to store, retrieve and manage semi-structured data. Each record, or "document", holds all of its own information, which makes documents easy to change and the database easier to scale horizontally. Common formats include JSON (or binary forms of it) and XML.

Practical application

Suppose you're building a blogging platform. In a document database, each blog post, with its metadata, comments and even author information, could be stored as a single nested document. You don't need complex joins to fetch everything about a post.

Foundation

There's no single mathematical theory behind document databases in the way that relational algebra underpins relational ones. Each document is a tree of nested fields and values, and databases index chosen fields, usually with B-trees and sometimes with hash indexes, so that queries don't have to scan every document. Similarity search using vector space models and measures like cosine similarity is a separate feature that some databases offer, not the basis of document storage:

$$\text{cosine}(A, B) = \frac{A \cdot B}{\lVert A \rVert \, \lVert B \rVert}$$

Graph databases

Graph databases store data as nodes, edges and properties. They're good at managing highly connected data and complex relationships, which makes them useful for social networks, recommendation systems and semantic web applications.

Practical application

If you're running a recommendation engine for a bookshop, a graph database is a good fit. Each book could be a node, and edges could represent relationships such as "similar genre to" or "written by the same author", so you can write detailed queries that recommend books on several criteria at once.

Foundation

Graph databases draw heavily on graph theory. A graph $G$ is a set $V$ of vertices and a set $E$ of edges, $G = (V, E)$. Many graph databases store each node with direct references to its neighbours (index-free adjacency), so following a relationship doesn't need an index lookup. Traversal algorithms such as depth-first and breadth-first search, and shortest-path algorithms such as Dijkstra's, are central to how they're queried. For a weighted graph, the shortest-path distance between two vertices is the smallest total weight of any path between them:

$$d(u, v) = \min_{P \,\in\, \text{paths}(u, v)} \; \sum_{e \in P} w(e)$$

Dijkstra's algorithm finds these distances when all the weights are non-negative.

Time-series databases

Time-series databases (TSDBs) are optimised for timestamped data. They're common in monitoring, Internet of Things (IoT) devices and analytics on data as it arrives. Time is the primary axis, and these databases are fast at queries over time ranges and at aggregations.

Practical application

A time-series database suits financial market data. It can store prices with timestamps and quickly answer queries about recent trends, moving averages or volatility over a given period.

Foundation

Inside the database, the important techniques are about storage: data is partitioned by time, timestamps are compressed with delta-of-delta encoding and floating-point values with XOR-based compression (both popularised by Facebook's Gorilla paper in 2015), and retention policies and downsampling keep old data small.

The analysis itself usually runs on the data rather than inside the storage engine. Fourier transforms move time-domain data into the frequency domain, discrete wavelet transforms support multi-resolution analysis, and statistical models are used for forecasting. A common one is the ARMA(p, q) model:

$$X_t = c + \varepsilon_t + \sum_{i=1}^{p} \varphi_i X_{t-i} + \sum_{i=1}^{q} \theta_i \varepsilon_{t-i}$$

Here $\varepsilon_t$ is white noise, $c$ is a constant, and $\varphi_i$ and $\theta_i$ are model parameters. ARIMA(p, d, q), the auto-regressive integrated moving average model, applies the same ARMA model to the series after differencing it $d$ times (for $d = 1$, to $X_t - X_{t-1}$), which handles data with a trend.