Data Models and Query Languages

Topics Covered

The Relational Model

Normalization and Why It Matters

Joins: The Relational Superpower

Many-to-One and Many-to-Many

The Document Model

Schema-on-Read vs Schema-on-Write

Document References vs Embedding

Many-to-Many: The Document Model's Weakness

Graph Data Models

Property Graphs

Triple Stores and RDF

When Graphs Beat Tables

Query Languages and Paradigms

Declarative: SQL

Imperative: The Alternative

Graph Query Languages: Cypher

MapReduce: Declarative Meets Functional

Datalog: The Foundation

Why has the relational model dominated for over 40 years? Because it made one bet that paid off enormously: separate the logical representation of data from the physical storage. You describe what data you want, and the database figures out how to retrieve it. Every competing model from the 1970s (hierarchical, network) forced developers to think about access paths and pointer chains. The relational model freed them from that burden.

The core abstraction is the relation (a table): an unordered collection of rows, where each row has the same set of columns. This sounds trivial until you realize what it enables. Because rows are unordered and self-describing, the database engine can choose any access strategy (sequential scan, index lookup, hash join) without the application knowing or caring. Change the indexes, add a column, restructure the physical layout — the queries stay the same.

Compare this with the hierarchical model (IBM's IMS, popular in the 1960s-70s), where data was organized as a tree. To access a customer's orders, you navigated down the tree from customer to order nodes. If the access pattern changed — say, you now needed to find all orders for a specific product across all customers — you had to restructure the tree or write a new navigation path. The relational model solved this by making all access paths equivalent: any query can reach any data through any combination of columns. No privileged direction, no hardcoded tree structure.

One user record laid out as normalized tables and again as a single document, with the reads and updates each shape implies.

Normalization and Why It Matters

Normalization is not about following rules for their own sake. It solves a concrete problem: update anomalies. If you store a user's city name as a string in 15 different rows across 3 tables, what happens when the city is renamed? You must find and update all 15 copies. Miss one and your data is inconsistent. Normalization eliminates this by storing each fact exactly once and using references (foreign keys) to point to it.

The practical levels most engineers need:

  • First Normal Form (1NF): Every column holds a single atomic value, not a list or nested structure. A column phone_numbers containing "555-1234, 555-5678" violates 1NF. Split it into a separate phone_numbers table with one row per number.
  • Second Normal Form (2NF): Every non-key column depends on the entire primary key, not just part of it. In an order_items table with a composite key (order_id, product_id), a column product_name depends only on product_id — move it to the products table.
  • Third Normal Form (3NF): No non-key column depends on another non-key column. If orders has customer_id, customer_name, and customer_city, the name and city depend on customer_id, not on the order. Move them to a customers table.

In practice, most production databases aim for 3NF and stop there. Higher normal forms (BCNF, 4NF, 5NF) exist but address edge cases that rarely arise in application development. The real-world decision is not "which normal form should I use?" but rather "how much denormalization is acceptable for my read patterns?" Every denormalization is a conscious decision to duplicate data for read performance, with the understanding that writes become more complex and inconsistency becomes possible.

sql
1-- Normalized: each fact stored once
2CREATE TABLE regions (
3  region_id   SERIAL PRIMARY KEY,
4  name        VARCHAR(100) NOT NULL
5);
6
7CREATE TABLE users (
8  user_id     SERIAL PRIMARY KEY,
9  name        VARCHAR(100) NOT NULL,
10  region_id   INT REFERENCES regions(region_id)
11);
12
13-- Denormalized: region name duplicated in every user row
14CREATE TABLE users_denormalized (
15  user_id     SERIAL PRIMARY KEY,
16  name        VARCHAR(100) NOT NULL,
17  region_name VARCHAR(100)  -- duplicated across thousands of rows
18);
Key Insight

Normalization is really about write correctness: storing each fact once means you can never have contradictory copies. Denormalization is about read performance: duplicating data means you can answer queries without joins. Every database schema is a position on this spectrum, and the right position depends on your read-to-write ratio.

Joins: The Relational Superpower

Joins are what make normalization practical. You split data across tables for integrity, then recombine it at query time. The database engine chooses the join algorithm (nested loop, hash join, merge join) based on table sizes and available indexes. You never specify the algorithm — you just declare the relationship.

A join across four normalized tables built up one clause at a time, with the rows surviving each step.
sql
1SELECT u.name, o.order_date, p.product_name, p.price
2FROM users u
3JOIN orders o ON u.user_id = o.user_id
4JOIN order_items oi ON o.order_id = oi.order_id
5JOIN products p ON oi.product_id = p.product_id
6WHERE u.user_id = 42;

This query touches four tables but reads as a simple English sentence: "Get the name, order dates, product names, and prices for user 42." The query optimizer decides whether to start from users and follow foreign keys outward, or start from order_items and filter inward. The developer does not need to know.

The performance cost of joins is real but often overstated. A join on indexed foreign keys is typically a B-tree lookup: O(log N) per row. For a query that starts from a single user and follows foreign keys outward, the total cost is proportional to the number of result rows, not the total table size. A database with 100 million orders can answer "user 42's orders" in milliseconds because the index on user_id prunes 99.99% of the table immediately. Joins become expensive when they lack indexes, when they produce large intermediate result sets, or when they cross table partitions in a distributed database.

Many-to-One and Many-to-Many

Relational databases handle both relationship types naturally:

Many-to-one: Multiple users live in the same region. Each user row stores a region_id foreign key pointing to a single row in the regions table. Storage-efficient: the region name appears once. More importantly, the regions table can hold additional data (population, timezone, country) that is automatically available to any query that joins on region_id, without duplicating that data in every user row.

Many-to-many: A student enrolls in multiple courses. A course has multiple students. A junction table enrollments(student_id, course_id) represents the relationship. Neither the students table nor the courses table needs to change when new enrollments are added. The junction table can also carry its own columns: enrolled_at, grade, status. This is something the document model struggles with — where do you put attributes that belong to the relationship itself, not to either entity?

This flexibility is why relational databases handle evolving requirements well. When you add a new relationship type (say, "students can also be teaching assistants"), you add a junction table. No existing tables change. No existing queries break.

The many-to-many relationship is also the reason relational databases use set-based operations rather than record-at-a-time processing. A junction table is just a set of pairs. Joining two tables through a junction table is set intersection. Finding all students not enrolled in any course is set difference. These operations compose naturally in SQL because the relational model is built on set theory. This mathematical foundation is not just academic elegance — it is why the query optimizer can reason about and transform queries: it can prove that two query plans are equivalent because the underlying set operations are equivalent.