Data Models and Query Languages

Data models are layers of abstraction

Most applications stack one data model on another; each layer hides the complexity below it behind a clean model.

Fullscreen

Declarative vs imperative query languages. SQL, Cypher, SPARQL, and Datalog are declarative: you describe what you want (conditions, sorting, grouping), and the query optimizer decides how (which indexes, join algorithms, order). Imperative code (Python, Java) tells the machine the exact steps. Declarative wins because it is more concise and lets the database improve performance (e.g., parallelize across cores/machines) without changing your queries.

---

Relational vs Document Models

• Relational model (Codd, 1970): data as relations (tables) of tuples (rows), unordered. RDBMS + SQL dominated from the mid-1980s and still rule business analytics.
• A parade of challengers came and went: network/hierarchical models (1970s–80s), object databases (late 80s–early 90s), XML databases (early 2000s). SQL absorbed many of their ideas (XML, JSON, graph support).
• NoSQL (2010s): not one technology but a cluster of ideas, new data models, schema flexibility, scalability, open source. NewSQL aimed for NoSQL scalability plus relational guarantees. Both terms have faded as their ideas were absorbed.
• The lasting legacy of NoSQL is the document model (usually JSON), popularized by MongoDB/Couchbase, though most relational DBs now support JSON too.

The object-relational mismatch

• Most app code is object-oriented; storing objects in tables needs an awkward translation layer, the impedance mismatch (term borrowed from electronics).
• ORMs (ActiveRecord, Hibernate) cut boilerplate but are criticized:
  • Can't fully hide the two models; you still think in both.
  • Mostly OLTP-only; analysts still face the raw relational schema.
  • Often relational-only (weak support for search/graph/NoSQL).
  • Auto-generated schemas can be awkward or inefficient.
  • Easy to write inefficient queries, the N+1 query problem: fetching N comments, then one query per comment for its author = N+1 queries instead of a single join. Fix: tell the ORM to fetch authors together (a join).
• ORM upsides: reduce inevitable translation boilerplate, can cache query results, help with schema migrations.

The document model for one-to-many relationships

Example: a LinkedIn-style résumé. The relational approach shreds it into separate tables (positions, education, contact_info) linked by foreign keys. The document approach stores it as one JSON document.

Fullscreen

• One-to-many relationships form a tree, which JSON makes explicit.
• JSON has better locality: to load a profile you read one document, not a multi-way join across tables.
• Sometimes called one-to-few, fine to embed a résumé's few positions. But for a genuinely large number of related items (e.g., thousands of comments on a celebrity post), embedding is unwieldy, so the relational/separate-table approach is better.

Normalization, denormalization, and joins

Storing region_id (an ID) instead of the text "Washington, DC" is normalization: human-meaningful info lives in one place; everything else references it by ID.

Why prefer an ID:

• Consistent spelling/style; avoids ambiguity (DC the city vs the state).
• Easy global updates (change the name in one place).
• Localization (translate the canonical list).
• Better search (the canonical region can encode "East Coast").
• Crucially: an ID never needs to change, because it has no human meaning. Anything human-meaningful might change, and if duplicated, every copy must be updated.

Normalization requires a join on every display query to resolve the ID to something readable.

Fullscreen

• General rule: normalized = faster writes, slower reads (joins); denormalized = faster reads, costlier writes (more copies, more disk, inconsistency risk). View denormalization as a form of derived data, you must maintain the copies.
• Crash mid-update threatens consistency; atomic transactions (Ch. 8) or stream processing (Ch. 12) help.
• Normalization suits OLTP (fast reads and writes). Analytics often prefers denormalization (bulk updates, read-dominated). At small/moderate scale, normalize; at very large scale, join cost can become a problem.
• Document DBs can store both, but lean denormalized, JSON makes adding fields easy, and many document DBs have weak join support (some have none, forcing app-side joins; MongoDB offers $lookup in aggregation pipelines).

Denormalization in the social-network case study. The materialized timeline is a cache of the expensive posts-follows join. But X stores only post IDs + sender IDs in the timeline, not post text, because likes/replies/usernames/photos change constantly. On read, the service hydrates the IDs (a join in application code) to fetch current content. Lesson: read-time joins are not inherently an obstacle to scale, ID hydration parallelizes well and its cost is independent of follower count. The most scalable design often denormalizes some things and leaves others normalized, based on how often data changes and read/write costs.

Many-to-one and many-to-many relationships

Fullscreen

• Many-to-one: many people live in one region.
• Many-to-many: a person worked at several orgs; an org has many employees. In relational, model with an associative table / join table (each row links one user ID to one org ID).
• These don't fit neatly in a single self-contained document → they favor a normalized representation (documents reference other documents by ID).
• Querying both directions ("orgs this person worked at" vs "people who worked at this org") needs either denormalized ID lists on both sides (risk of inconsistency) or a normalized store + secondary indexes on both columns (Ch. 4). Many document/relational DBs can index fields inside JSON arrays.

Stars and snowflakes: schemas for analytics

Data warehouses are usually relational and use conventions tuned for analysts: star schema, snowflake schema, dimensional modeling, and one big table (OBT).

Fullscreen

• Fact table at the center: one row per event (a sale, a click). Holds measures (numeric attributes like price/cost) and foreign keys to dimension tables. Can grow to petabytes.
• Dimension tables are the who/what/where/when/how/why of each event (e.g., dim_product with SKU, brand, category). Often very wide (100+ columns).
• Star = fact in the middle, dimensions radiating like rays. Snowflake = dimensions further normalized into subdimensions (more normalized, but star is usually preferred for analyst simplicity).
• Mostly many-to-one relationships. A multi-item purchase isn't modeled explicitly, it's just multiple fact rows sharing a customer/store/timestamp.
• One big table (OBT) folds dimensions into denormalized fact columns (precomputed joins), more storage, sometimes faster queries. Denormalization is safe here because analytics data is an immutable historical log.

When to use which model

• Use document if your data is a tree of one-to-many relationships loaded all at once. Shredding such data into many tables yields cumbersome schemas and code.
• Document limitations: you can't directly reference a nested item ("the 2nd position of user 251"); relational lets you reference anything by ID. Good for reorderable lists (drag-and-drop to-do/issue trackers) via a JSON array; relational has no standard way (tricks: integer sort column with renumbering, linked list of IDs, or fractional indexing).

Schema flexibility: schema-on-read vs schema-on-write

• Document DBs / JSON usually enforce no schema. "Schemaless" is misleading, there's an implicit schema the reading code assumes.
• Schema-on-read = structure interpreted when data is read (like dynamic/runtime typing). Schema-on-write = explicit schema enforced on write (like static/compile-time typing). Neither is a clear winner.
• Changing data format:
  • Document: just start writing the new shape; reading code handles old documents (e.g., split name into first_name at read time).
  • Relational: a migration (ALTER TABLE … ADD COLUMN is fast; the backfilling UPDATE rewrites every row and can be slow; online-migration tools exist but are operationally tricky).
• Schema-on-read shines when data is heterogeneous (many object types, or structure controlled by external systems). When records share one structure, an explicit schema documents and enforces it. (Schema evolution → Ch. 5.)

Data locality for reads and writes

• A document is stored as one continuous string (JSON/XML/BSON). Locality helps when you need most of the document at once.
• But: the DB usually loads the whole document even if you need a small part, and updates usually rewrite the whole document. So keep documents small and avoid frequent small updates.
• Locality isn't document-only: Spanner offers interleaved (nested) rows in a relational model; Oracle has multi-table index cluster tables; Bigtable-style wide-column stores (HBase, Accumulo) use column families for the same purpose.

Query languages for documents, and convergence

• Document query options vary: key-value by primary key, secondary indexes, or rich languages, XQuery/XPath (XML), JSON Pointer/JSONPath, MongoDB's aggregation pipeline (JSON-syntax equivalent to a subset of SQL; e.g., $match + $group to count sharks per month).
• Convergence: relational DBs added JSON types/operators/indexing; document DBs added joins, secondary indexes, declarative queries. Relational–document hybrids are powerful. (Codd's original relational model even allowed nonsimple domains, nested relations as values, anticipating JSON by 30+ years.)

---

Graph-Like Data Models

When many-to-many relationships dominate and connections get complex, model the data as a graph: vertices (nodes/entities) + edges (relationships/arcs).

Examples: social graphs (people ↔ acquaintances), the web graph (pages ↔ links; PageRank), road/rail networks (junctions ↔ roads; shortest-path). Representations: adjacency list (each vertex stores neighbor IDs, good for traversal) vs adjacency matrix (good for ML). Graphs can be heterogeneous, one graph storing many vertex/edge types (Facebook's single graph; search-engine knowledge graphs, Wikidata).

Two models discussed: property graph (Neo4j, Memgraph, KùzuDB) and triple store (Datomic, AllegroGraph, Blazegraph). Query languages: Cypher, SPARQL, Datalog, GraphQL, plus SQL.

Running example (Lucy from Idaho, Alain from Saint-Lô, married, living in London):

Fullscreen

Property graphs

Each vertex: unique ID, a label (type), sets of incoming + outgoing edges, and a collection of properties (key-value). Each edge: unique ID, tail vertex (start), head vertex (end), a label (relationship kind), and properties.

You can model it as two relational tables (vertices, edges) with JSON properties and indexes on tail_vertex and head_vertex. Key aspects:

• Any vertex can connect to any other, no schema restricting relationships.
• You can efficiently traverse both directions (incoming and outgoing edges).
• Different labels let you store many kinds of info in one clean graph.

Limitation: an edge connects exactly two vertices, whereas a relational join table can express 3-way (higher-degree) relationships. Workaround: add a vertex per join-table row, or use a hypergraph.

Graphs excel at evolvability, they naturally accommodate irregular structure (France's départements/régions vs US counties/states, a country within a country, varying granularity) and are easy to extend with new facts (e.g., allergens linked to people and foods).

Cypher

A declarative property-graph language (originally Neo4j, now openCypher; basis of the 2024 GQL ISO standard). Uses arrow notation: (idaho) -[:WITHIN]-> (usa) creates an edge. A MATCH clause finds patterns; :WITHIN*0.. means "follow a WITHIN edge zero or more times" (like * in a regex). The "people who emigrated US → Europe" query is ~4 lines.

Graph queries in SQL

You can store graph data relationally and query with SQL, but graph traversal means a variable number of joins (you don't know in advance how many WITHIN hops). Cypher's :WITHIN*0.. becomes a recursive common table expression (WITH RECURSIVE). The same query that was 4 lines in Cypher takes ~31 clumsy lines in SQL. Oracle calls its version hierarchical; other graph languages include GSQL and PGQL.

Triple stores and SPARQL

Fullscreen

• A triple store stores everything as (subject, predicate, object), e.g., (Jim, likes, bananas). Mostly equivalent to a property graph with different words.
  • Object = a primitive value → predicate/object behave like a property key/value.
  • Object = another vertex → predicate is an edge, subject is tail, object is head.
• Turtle (a subset of Notation3) is a readable triple syntax. Triples come from the Semantic Web (early-2000s effort that mostly didn't pan out, but its legacy lives in JSON-LD, biomedical ontologies, Open Graph protocol, Wikidata, Schema.org). The data model is RDF (Resource Description Framework); in RDF, subjects/predicates/objects are often URIs so different parties' data can be combined without naming conflicts.
• SPARQL ("sparkle") = query language for RDF triple stores. Predates Cypher (Cypher borrowed its pattern matching), so they look similar; ?person :bornIn / :within* / :name "United States" mirrors the Cypher pattern. RDF doesn't distinguish properties from edges (both are predicates).

Datalog

• Older (1980s academic), a subset of Prolog, relational-based, underused but very expressive for complex/recursive queries. Used by Datomic, LogicBlox, CozoDB, LinkedIn's LIquid.
• Data = facts (location(2, "United States", "country")). You write rules (head :- body) that derive virtual tables (like SQL views) from facts; rules can reference other rules and recurse (enabling graph traversal). You build a query up rule by rule, like composing functions, a different style from SELECT-first languages.

GraphQL

• Deliberately restrictive, intended for OLTP: lets a client (mobile/web frontend) request a JSON document shaped exactly like its UI needs, no more, no less.
• Lets clients change queries without server API changes. Costs: tooling to map GraphQL onto internal REST/gRPC services, plus authorization, rate-limiting, and performance concerns.
• Limited because queries come from untrusted clients: no recursion, no arbitrary search conditions (to prevent denial-of-service) unless the service explicitly offers them.
• Accepts duplication in responses (e.g., repeating a sender's name, embedding the replyTo content) to keep UI rendering simple. The server can store data normalized and resolve the declared joins. Despite the name, GraphQL runs on any database (relational, document, or graph).

---

Event Sourcing and CQRS

So far data is queried in the same form it's written. But sometimes no single representation serves all read patterns. Idea: write in one form, derive read-optimized representations from it.

Fullscreen

• Event log: the simplest write-optimized form, append a self-contained, timestamped, immutable event. Never change/delete; only append (later events may supersede earlier ones).
• Event sourcing: use the event log as the source of truth; every state change is an event.
• CQRS (Command Query Responsibility Segregation): keep separate read-optimized materialized views (a.k.a. projections / read models), derived from the write-optimized log.
• Command vs event: an incoming request is a command; once validated (enough seats), it becomes a fact and an event is appended. The log holds only valid events, and view-builders may not reject events. Name events in the past tense ("seats were booked"), they record what happened.
• vs a star-schema fact table: both are collections of past events, but fact rows share columns and are unordered, whereas events can have many types and their order matters.

Advantages:

• Events communicate intent ("booking was canceled" vs a tangle of row mutations).
• Views are reproducible, delete and recompute from the log with the same code (great for fixing view bugs).
• Multiple views, any data model, denormalized for fast reads; can be in-memory and recomputed on restart.
• Easy to add a new view or new event types/properties later (old events stay unmodified); chain new behaviors off existing events (offer a canceled seat to the waitlist).
• A written-in-error event is reversed by a deletion event (downstream views self-correct), reducing irreversibility.
• The log doubles as an audit log (valuable in regulated industries).
• Logs handle high write throughput (sequential writes) and absorb bursts while views catch up.

Downsides:

• External/nondeterministic data: event processing must be deterministic, include the exchange rate in the event (or query a fixed historical value), don't fetch a live rate.
• Immutability vs GDPR deletion: can't simply delete from an append-only log. Options: keep personal data outside the event, or crypto-shredding (encrypt with a deletable key), but that complicates recomputation.
• Reprocessing side effects: don't resend confirmation emails every time you rebuild a view.
• Tools: EventStoreDB, MartenDB (on PostgreSQL), Axon Framework; or Kafka as the log with stream processors maintaining views (Ch. 12). The key requirement: all views must process events in the same order as the log, not trivial in a distributed system (Ch. 10).

---

DataFrames, Matrices, and Arrays

Mostly an analytics/scientific model, rare in OLTP. Supported by R, Pandas, Spark, Dask, ArcticDB.

Fullscreen

• A DataFrame looks like a table/spreadsheet and supports relational-like bulk ops (filter, group, aggregate, apply, merge = DataFrame's word for join). But it's manipulated imperatively through a series of commands ("wrangling"), usually on a data scientist's local copy, matching their incremental workflow.
• DataFrame APIs go far beyond relational ops, often transforming relational data into a matrix / multidimensional array (the input form for many ML algorithms). Example: a movie-ratings table pivoted into a sparse matrix (rows = users, cols = movies), too wide for a relational DB, but easy for NumPy/sparse arrays.
• Non-numeric data is encoded into numbers: scaling dates to floats, one-hot encoding for categorical values (a 0/1 column per category, generalizing to multi-category items).
• Once it's a numeric matrix, it's amenable to linear algebra (the basis of ML). Array databases (TileDB) specialize in large numeric arrays (geospatial raster, medical imaging, astronomy). DataFrames also serve financial time-series, and exist in Spark/Flink (Ch. 11).

---

Real-world examples and analogies

• Relational vs document, spreadsheet tabs vs a stapled packet. Relational keeps each entity in its own clean tab and references across tabs by ID (great for shared, cross-cutting data). A document is a stapled packet with everything for one record together, fast to grab whole, awkward if many records need to share an updatable fact.
• Normalization, one phone book vs writing the address on every letter. Normalized: everyone's address lives in one phone book; letters just say "see entry 251." If someone moves, you edit one entry. Denormalized: you wrote the address on a thousand letters, fast to read each letter, but a nightmare to update.
• N+1 problem, asking each guest their name one at a time. Instead of getting the full guest list in one go (a join), you fetch the list, then walk up to each of the N guests separately. N+1 trips when one would do.
• Star schema, a receipt and its reference shelves. The fact table is a stack of receipts (one row per sale). The dimension tables are reference shelves (product catalog, store directory, calendar) that the receipts point to so you can describe each sale's who/what/where/when.
• Schema-on-read vs schema-on-write, clearing customs. Schema-on-write is a strict customs officer checking every item against rules as it enters the country (the DB). Schema-on-read waves everything through and inspects only when you actually use an item, flexible, but you might discover surprises later.
• Graph model, a city subway map. Stations (vertices) and lines (edges) where "how many stops to get there" varies, exactly the variable-length traversal graphs handle and relational joins struggle with.
• Cypher vs SQL for graphs, GPS vs hand-written directions. "Get me anywhere within the US" in Cypher is one tidy instruction (:WITHIN*0..); the SQL recursive-CTE version is a page of turn-by-turn directions for the same trip.
• Triple store, sentences. Everything is a tiny sentence: subject, verb, object ("Lucy bornIn Idaho"). Stack enough sentences and you have a whole knowledge base.
• Event sourcing, a bank statement vs a balance. A balance (mutable state) tells you the number now; a statement (event log) records every deposit and withdrawal. From the statement you can always recompute the balance, and any other view (monthly spend, category breakdown).
• CQRS, kitchen tickets vs the dining room. Orders (commands) become tickets pinned in order (the log); the kitchen produces different "views" from the same tickets: the plated food, the bill, the inventory deduction.
• DataFrame to matrix, a pivot table for a robot. You reshape tidy rows into a grid of numbers (users × movies) so a math-driven model can do linear algebra on it.

---

Cheat-sheet flashcards

Cover the answer and recall it.

• Declarative vs imperative query language? → Describe what you want vs code how to get it.
• Why are declarative languages good for performance? → The optimizer can change/parallelize execution without changing queries.
• What is the impedance mismatch? → The awkward gap between OO objects and relational tables.
• What is the N+1 query problem? → One query for N items, then one query per item (N+1 total) instead of a join.
• One-to-many relationships form what shape? → A tree.
• "One-to-few" implies? → Small counts → safe to embed in a document.
• Normalized vs denormalized? → Store a fact once (ID) vs duplicate it everywhere.
• Why use an ID instead of text? → IDs never need to change; human-meaningful text might.
• Normalized = faster at? / Denormalized = faster at? → Writes / reads.
• Denormalization is a form of what? → Derived data (you must maintain copies).
• What is "hydrating IDs"? → Resolving stored IDs to full records, a join in app code.
• Many-to-many in relational uses? → An associative / join table.
• Fact table vs dimension table? → One row per event (measures + FKs) vs the who/what/where/when context.
• Star vs snowflake schema? → Dimensions flat vs dimensions further normalized into subdimensions.
• What is OBT? → One Big Table, dimensions folded into a denormalized fact table.
• Schema-on-read vs schema-on-write? → Structure interpreted on read (implicit) vs enforced on write (explicit).
• Analogy for schema-on-read/write typing? → Dynamic/runtime vs static/compile-time typing.
• Why keep documents small? → The whole document is loaded on read and rewritten on update.
• What is shredding? → Splitting a document tree into multiple relational tables.
• Vertex vs edge? → Node/entity vs relationship/arc.
• Adjacency list vs matrix? → Good for traversal vs good for ML.
• Property graph vertex contains? → ID, label, in/out edges, properties.
• Edge limitation in graphs? → Connects only two vertices (use extra vertex or hypergraph for higher-degree).
• Cypher :WITHIN*0.. means? → Follow a WITHIN edge zero-or-more times.
• How does SQL express variable-length traversal? → Recursive CTE (WITH RECURSIVE).
• Triple structure? → (subject, predicate, object).
• What is RDF? → Resource Description Framework, the Semantic Web data model behind triples.
• SPARQL is for? → Querying RDF triple stores.
• Datalog is a subset of? → Prolog; rules derive virtual tables, can recurse.
• GraphQL's purpose and key limit? → Shape a JSON response for the UI; restricted (no recursion) because clients are untrusted.
• Event sourcing? → Use an immutable append-only event log as the source of truth.
• CQRS? → Separate read-optimized views derived from the write-optimized log.
• Command vs event? → A request to do something vs the recorded fact that it happened (past tense).
• Crypto-shredding? → Encrypt personal data with a deletable key to satisfy deletion requests.
• DataFrame's word for join? → Merge.
• One-hot encoding? → A 0/1 column per category to turn categorical data into numbers.

---

Common interview questions

1. When would you choose a document database over a relational one, and vice versa? (Document: self-contained trees loaded whole, schema flexibility, locality. Relational: joins, many-to-one/many-to-many.)
2. Explain normalization vs denormalization and their trade-offs. (One copy vs duplicates; write speed/consistency vs read speed; denormalization = derived data to maintain.)
3. What is the N+1 query problem and how do you fix it? (Per-item queries instead of a join; fetch related data together.)
4. Walk me through a star schema. What are fact and dimension tables? (Event rows with measures + FKs; context tables; star vs snowflake vs OBT.)
5. What's the difference between schema-on-read and schema-on-write? (Implicit/interpreted on read vs explicit/enforced on write; analogous to dynamic vs static typing; migration implications.)
6. When does a graph model beat relational, and why is graph traversal awkward in SQL? (Dense many-to-many, variable-hop traversal; SQL needs recursive CTEs, verbose.)
7. Compare property graphs and triple stores. (Mostly equivalent; vertices/edges/properties vs subject-predicate-object / RDF; Cypher vs SPARQL.)
8. What is GraphQL good and bad at? (UI-shaped JSON, client-driven; restricted because untrusted, no recursion/arbitrary search; needs backend mapping/auth/rate-limiting.)
9. Explain event sourcing and CQRS. What are the main benefits and pitfalls? (Immutable event log as source of truth + derived views; intent, reproducibility, auditability, throughput; vs determinism, GDPR deletion, reprocessing side effects.)
10. Why must event-processing be deterministic, and how do you handle external data like exchange rates? (Recompute must yield the same view; embed the value or query a fixed historical value.)
11. How do you handle the GDPR "right to erasure" with an immutable event log? (Store personal data outside events, or crypto-shredding.)
12. Why do data scientists use DataFrames and convert data to matrices? (Imperative wrangling, ops beyond SQL; matrices feed linear-algebra-based ML; sparse + one-hot encoding.)

---

Key terms glossary

---

Forward links (where these ideas return)

• Storage-engine internals behind these models → Chapter 4
• Schemas and schema evolution (JSON/XML/Avro, schema-on-read) → Chapter 5
• Secondary indexes → Chapter 4
• Atomic transactions for consistent denormalization → Chapter 8
• Stream processing, Kafka as event log, maintaining materialized views → Chapters 11 and 12
• Ordering events across a distributed system → Chapter 10
• Full-text and vector search → Chapter 4