Databases and Systems

Source: Concepts adapted from Ace the Data Science Interview — Chapter 8 (“SQL & DB Design”) by Kevin Huo & Nick Singh. Rewritten in original wording for this course.

You do not need to know every storage-engine knob. Interviewers usually want a high-level picture: how tables relate, what to index, when to normalize vs denormalize, and the big distributed-system trade-offs (CAP, ACID/BASE, scale-up vs scale-out). That shows up more often at smaller companies where data scientists also touch pipelines and warehouse design.

This lesson pairs short concept quizzes with a few SQL drills on the same Reddit-style seed from the SQL lesson (users, posts — open Data before each query).

Schema design in interviews

A classic prompt: “Design tables for Reddit.” Sketch the entities (users, posts, subreddits, …), then the relationships. Posts carry a user_id pointing at the author — that column is the join key used everywhere.

You may also be asked what to index. Index join / filter keys that appear in hot paths — for Reddit analytics, posts.user_id is an obvious candidate because almost every user-level report joins on it.

	Primary key	Foreign key
Made of columns	Yes	Yes
Duplicate values	No	Yes
NULLs	No (usually)	Allowed (unless constrained)
Uniquely IDs a row	Yes	Maybe (depends on design)
Count per table	One PK	Zero or more FKs
Index	Auto-indexed	Not auto-indexed

Quiz

Schema & indexing

1 / 4

In a Reddit-style posts table, user_id is best described as…

Pick an answer to see if you are right.

Practice: keys in SQL

Keys and normalization

• Primary key — unique row identity (e.g. posts.post_id).
• Foreign key — relationship pointer (e.g. posts.user_id → users.user_id).

Storing author country once in users and referencing it from posts is normalization: less duplication, clearer constraints, better integrity. The cost is joins.

Denormalization copies fields into a wide table (or materializes aggregates) to avoid joins on hot read paths. Storage is cheap; repeated compute and consistency bugs are expensive — so warehouses and high-QPS feeds often denormalize deliberately.

Interview angles:

• Why does entity A hold an FK to B?
• Is the mapping 1:1, 1:N, or N:M? (N:M usually needs a junction table.)
• When would you denormalize anyway?

Users → posts is one-to-many: one user, many posts.

Quiz

Normalization & relationships

1 / 5

Normalization mainly aims to…

Pick an answer to see if you are right.

Practice: normalized vs “wide” reads

CAP theorem

For distributed stores, CAP says you can fully guarantee only two of:

• Consistency — every client reads the same up-to-date data
• Availability — every request gets a non-error response (may be stale)
• Partition tolerance — the system keeps working when nodes cannot talk

In practice partitions happen, so real systems choose CP or AP under stress. Business cost drives the choice:

• Social feed / like counts → often favor availability (stale like counts are fine)
• Payments / balances → favor consistency (double-spend is not fine; retries OK)

Classic textbook labels (simplified): many SQL systems are discussed as CA-leaning in non-partitioned deployments; MongoDB/Redis often appear in CP teaching diagrams — treat labels as interview shorthand, not gospel for every cluster config.

Quiz

CAP theorem

1 / 4

CAP says a distributed system can simultaneously guarantee…

Pick an answer to see if you are right.

ACID transactions

ACID describes transactional correctness (especially OLTP):

Letter	Meaning
Atomicity	All-or-nothing; abort → rollback
Consistency	Constraints hold before/after (including FK integrity)
Isolation	Concurrent transactions do not corrupt each other’s view
Durability	Committed data survives crashes

Think checkout, transfers, inventory updates — many concurrent writers that must not leave half-applied state.

Quiz

ACID

1 / 5

Order the ACID letters as they appear in the acronym (top = first letter).

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1Durability — committed data survives crashes
2. ⋮⋮2Isolation — concurrent transactions do not step on each other
3. ⋮⋮3Atomicity — all-or-nothing commit / rollback
4. ⋮⋮4Consistency — constraints hold before and after

Drag items into the correct order (or use ↑↓), then check.

Scaling databases

Older pattern: full-copy clusters behind a load balancer — every node holds all data (CAP issues under load remain).

Cloud-era levers:

• Vertical scaling (scale up) — bigger CPU/RAM on existing machines. Simple ops; eventually hits hardware/cost walls.
• Horizontal scaling (scale out) — more commodity nodes. Cheaper elasticity and better fault tolerance; you inherit distributed consistency/ops complexity.

Sharding is a common horizontal approach: same schema on each shard, rows partitioned by a key (hash, range, or lookup). Each row maps to exactly one shard for both reads and writes.

Quiz

Scaling & sharding

1 / 4

Vertical scaling means…

Pick an answer to see if you are right.

Relational vs NoSQL

Relational (SQL) — fixed tables/schemas (MySQL, Postgres). Strong fit for structured analytics + ACID OLTP.

NoSQL (“non-relational”) families:

Style	Idea	Example
Document	Flexible nested documents; easy new fields	MongoDB
Key-value	Simple lookup by key	Redis (often)
Column-family	Wide columns / sparse attributes	Cassandra-style
Graph	Nodes + first-class relationships	Neo4j

Graph DBs shine when edges matter as much as nodes (social graphs, recommendations).

BASE (NoSQL-oriented)

Analog of ACID with a different bias:

• Basically Available — responses exist; may be inaccurate
• Soft State — state can change without new client writes (reconciliation)
• Eventual Consistency — replicas converge later, not on a hard deadline

BASE prioritizes availability and scale; ACID prioritizes correctness of each transaction.

Quiz

SQL vs NoSQL & BASE

1 / 5

A document store like MongoDB is attractive when…

Pick an answer to see if you are right.

MapReduce, Hadoop, and Spark

MapReduce processes huge datasets in parallel. Four steps:

1. Split — chunk input across workers
2. Map — emit <key, value> pairs (e.g. each word → <word, 1>)
3. Shuffle — move equal keys onto the same worker (locality!)
4. Reduce — aggregate per key (e.g. sum counts → <word, 5>)

Shuffle is the efficiency secret: related pairs land together so reducers avoid chatty cross-node fetches.

Hadoop ecosystem pieces you’ll hear named:

1. HDFS — distributed storage / replication
2. MapReduce — the processing model
3. YARN — scheduling / resource management

Spark — also batch (and more) processing, but favors in-memory computation for speed (higher RAM cost). Built-in scheduling/monitoring, unlike classic MapReduce depending on YARN.

Orchestrators like Airflow / Luigi show up if your resume lists pipelines — expect conceptual “what / why,” not deep operator trivia, unless you claim expertise.

Quiz

MapReduce & big data stack

1 / 9

Put the MapReduce stages in the order they run (top = first).

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1Reduce — aggregate values for each key
2. ⋮⋮2Shuffle — colocate identical keys on one worker
3. ⋮⋮3Split — chunk input across workers
4. ⋮⋮4Map — emit <key, value> pairs

Drag items into the correct order (or use ↑↓), then check.

Interview checklist

1. Draw entities + PK/FK; name the cardinality (1:1 / 1:N / N:M).
2. Call out indexes on join/filter keys.
3. Say when you’d denormalize for read latency.
4. For distributed design: pick C vs A with a business reason; mention ACID vs BASE if NoSQL comes up.
5. Scale story: vertical vs horizontal; sharding key intuition.
6. Big data: Map → Shuffle → Reduce locality; Hadoop vs Spark one-liners.

Next: SQL Easy · Later: Coding interviews.