Data Models: Relational, Document & Graph

Module Overview

A data model is an abstract mathematical framework defining how data is structured, stored, and operated upon within a database management system. In this installment of the Database Systems curriculum, we compare the dominant paradigm—Edgar F. Codd's Relational Model—against modern NoSQL and NewSQL architectures: JSON Document stores, high-throughput Key-Value maps, and topological Property Graph databases. We examine the exact tradeoffs in schema rigidity, query expressiveness, horizontal partitioning, and relational integrity.

1. Historical Evolution of Conceptual Data Models

Data representation in computer science has evolved across distinct structural epochs:

Hierarchical Model (1960s, e.g., IBM IMS): Data arranged in strict parent-child tree hierarchies. Records could have only one parent, rendering many-to-many relationships complex, requiring redundant duplicate trees.
Network Model (1970s, CODASYL DBTG): Permitted records to have multiple parents via named set pointers. Traversals were imperative and required software engineers to manually write pointer-chasing navigation code.
Relational Model (1970, E.F. Codd): Abstracted data storage into mathematical relations (tables) and declarative first-order logic queries, divorcing conceptual manipulation from physical pointer structures.
NoSQL & Multi-Model Revolution (2000s–Present): Emerged to accommodate extreme web-scale horizontal partitioning, unstructured documents, low-latency key lookups, and rich relationship traversals.

2. The Relational Model: Mathematical Foundations

Formulated at IBM Research in 1970, the relational model is grounded in mathematical set theory and first-order predicate logic.

Core Relational Constructs

Relation (Table)

A subset of the Cartesian product of a list of attribute domains: $R \subseteq D_1 imes D_2 imes \dots imes D_n$. A relation contains no duplicate rows and maintains no inherent ordering among tuples.

Tuple (Row / Record)

An ordered sequence of values $(v_1, v_2, \dots, v_n)$ where each value $v_i \in D_i$. Tuples represent discrete real-world entity instances or relationships.

Attribute (Column / Field)

A named role played by a specific domain $D$ within relation schema $R(A_1: D_1, \dots, A_n: D_n)$. Values within an attribute must be atomic (First Normal Form).

Integrity Constraints

Entity Integrity: Primary keys cannot contain NULL values. Referential Integrity: Foreign key values must match an existing primary key value in the referenced relation or be NULL.

3. Modern Non-Relational (NoSQL) Data Models

A. Document Model (e.g., MongoDB, Couchbase)

Encapsulates data in self-describing, hierarchical JSON or BSON documents. Instead of decomposing data across dozens of normalized tables connected by foreign key joins, related nested structures (e.g., line items inside an order) are embedded directly within the root document.

text

12345678910

{
  "_id": "ord_99214",
  "customer_id": "cust_441",
  "placed_at": "2026-03-31T14:22:00Z",
  "items": [
    { "sku": "SSD-2TB-NVME", "qty": 1, "unit_price": 149.99 },
    { "sku": "RAM-DDR5-32GB", "qty": 2, "unit_price": 99.50 }
  ],
  "shipping_address": { "city": "Seattle", "state": "WA", "postal": "98101" }
}

Advantage: Eliminates expensive multi-table joins on reads; provides high schema polymorphism. Disadvantage: Redundancy when data is shared; multi-document consistency requires distributed transaction protocols.

B. Key-Value Model (e.g., Redis, AWS DynamoDB)

The simplest storage paradigm: an associative array where opaque byte arrays (or specialized data structures like hashes, lists, or sets) are indexed solely by a unique alphanumeric partition key. The engine treats values as black boxes without schema introspection.

Advantage: Constant-time $O(1)$ lookups and trivial horizontal sharding via hash rings. Disadvantage: Cannot query on value attributes without maintaining external secondary indexing tables.

C. Graph Model (e.g., Neo4j, Amazon Neptune)

Represents data as Nodes (entities), directed Edges / Relationships (connections), and Properties (key-value metadata attached to nodes or edges). Relationships are first-class persistent pointers on disk (index-free adjacency).

text

123

// Cypher Query Language traversal
MATCH (p:Person {name: "Ada Lovelace"})-[:CONTRIBUTED_TO]->(proj:Project)<-[:MAINTAINS]-(colleague:Person)
RETURN colleague.name, proj.title;

Advantage: Deep recursive pathfinding and variable-length traversals run in $O(k)$ time relative to local subgraph density, avoiding the catastrophic combinatorial explosion of relational recursive joins.

4. Architectural Tradeoff Matrix

Model	Data Structure	Query Language	Horizontal Scaling	Primary Use Case
Relational	2D Tables / Relations	Declarative SQL	Complex (Sharding, 2PC)	OLTP transactions, financial ledgers, strict integrity.
Document	JSON / BSON Trees	MQL / JSON Path	Native Sharding	Content management, product catalogs, rapid prototyping.
Key-Value	Hash Map Pairs	Get / Put / Delete APIs	Seamless (Consistent Hash)	Session stores, caching, user shopping carts, rate limits.
Graph	Nodes & Adjacency Edges	Cypher, Gremlin, SPARQL	Challenging (Partition cuts)	Social networks, fraud detection, recommendation graphs.

Next in Curriculum

Having explored the structure of relations, in Part 3: Relational Algebra: Selection, Projection, Joins & Set Operations, we study the procedural mathematical algebra that forms the theoretical core of all relational query optimizers.