Document-Oriented Databases and NoSQL

What is a document database?

A document-oriented database (also called an aggregate-oriented database) stores data in the form of semi-structured objects — typically JSON or XML documents. Each document is a self-contained aggregate that bundles related data together.

Denormalised data is not directly semantically related to the key under which it is stored. For example, a movie document might contain embedded arrays of actors, directors, and genres — even though these are conceptually separate entities.

Why denormalise?

A denormalised schema enables rapid retrieval: one or two key lookups pull in much or all of the data likely to be needed by the application. Once the document is in memory, all sorts of fast, local operations (filtering, projection, join-like composition) can be performed in an application-specific way.

Traditional RDBMS (normalised):
  SELECT * FROM movies JOIN cast ON ... JOIN people ON ...
  → Many disk seeks, index traversals

Document DB (denormalised):
  db.movies.find({movie_id: 'tt0111161'})
  → One lookup, all data in hand

Query languages

Document databases support diverse query styles:

Query type	Example
Unstructured text search	Full-text search over plot summaries, trivia, goofs
Tag/key-value queries	Find all movies with genre: 'Sci-Fi' and year > 2010
Application-specific compositions	Python code that iterates over embedded casts, filtering and transforming

Standards exist — XPath for XML, JSONPath for JSON — but in practice, using general high-level languages to formulate queries was common. The ideal, however, is to write queries in a declarative language: imperative programming can defeat future automated query optimisation.

Inverted indices and re-normalisation

The “database” itself may support a variety of inverted indices — mapping from field values back to the documents that contain them — or even re-normalised copies of the data. This enables efficient queries on fields that are not the primary key.

Key nestings and replication

To support rapid retrieval using different keys, data may be precomputed and stored under multiple nesting structures. A movie might be stored:

1. Keyed by movie_id, with cast embedded.
2. Keyed by person_id, with filmography embedded.

This replication factor multiplies with any replication already present from denormalisation:

$\text{Total storage} = \text{base data} \times \text{denormalisation factor} \times \text{nesting replication factor}$

Document vs. relational

	Relational (RDBMS)	Document (NoSQL)
Schema	Enforced by DBMS	Implicit, application-level
Normalisation	Encouraged, formalised	Optional; often denormalised
Joins	Performed by DBMS at query time	Pre-computed by embedding
Query language	SQL (declarative, standardised)	Varied; often programmatic
Use case	Structured, related data with integrity constraints	Semi-structured aggregates; rapid single-lookup retrieval

Summary

• Document databases store denormalised aggregates (JSON/XML documents).
• Denormalisation trades storage space and write complexity for read performance.
• Query languages range from declarative standards to imperative application code.
• Data may be replicated under multiple key nestings to support different access patterns.
• The replication factor compounds: denormalisation × multiple nestings.