-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path04-normalization.html
More file actions
525 lines (488 loc) · 45 KB
/
Copy path04-normalization.html
File metadata and controls
525 lines (488 loc) · 45 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0">
<script>try{var t=localStorage.getItem("dbms-theme")||"dark";document.documentElement.setAttribute("data-theme",t)}catch(e){document.documentElement.setAttribute("data-theme","dark")}</script>
<title>Normalization — DBMS Illustrated</title>
<link rel="stylesheet" href="../css/style.css">
<style>:root{--topic-color:#F59E0B}</style>
</head>
<body>
<div class="reading-progress" id="reading-progress"></div>
<nav class="navbar">
<div class="navbar-inner">
<a class="navbar-brand" href="../index.html"><span class="brand-icon" style="color:var(--primary-soft)">◆</span>DBMS Illustrated</a>
<div class="navbar-links"><a href="../index.html#topics">All Topics</a></div>
<div class="navbar-actions"><button class="btn-icon" id="theme-toggle" title="Toggle theme">☼</button></div>
</div>
</nav>
<div class="container">
<div class="breadcrumb">
<a href="../index.html">Home</a><span class="breadcrumb-sep">›</span>
<a href="../index.html#topics">Course</a><span class="breadcrumb-sep">›</span>
<span>Normalization</span>
</div>
<div class="topic-header">
<div class="topic-badge">Topic 04</div>
<h1>Database <span class="accent">Normalization</span></h1>
<p class="subtitle">Imagine storing every order as a single row with the customer's name, city, and every product they ordered — all jammed together. What happens when the customer moves cities? You have to update every single row. Normalization is the process of designing your tables so that each piece of information lives in exactly one place, making updates safe and data consistent.</p>
<div class="company-badges">
<span class="badge">MySQL</span><span class="badge">PostgreSQL</span><span class="badge">Oracle</span>
<span class="badge">SQL Server</span>
</div>
</div>
<div class="at-a-glance reveal">
<h3>At a Glance</h3>
<ul>
<li><strong>1NF</strong> — every cell holds one value, not a list. No "apple, banana, cherry" in a single column. No columns like phone1, phone2, phone3.</li>
<li><strong>2NF</strong> — every non-key column depends on the entire primary key. If your primary key is two columns combined, a non-key column should not be determined by just one of them — that information belongs in its own table.</li>
<li><strong>3NF</strong> — non-key columns do not determine each other. If zip code determines city, city does not belong in the orders table — it belongs in a zip_codes table. Store each fact where it is directly known.</li>
<li><strong>BCNF</strong> — a stricter version of 3NF that handles a rare edge case when a table has multiple overlapping ways to uniquely identify rows. In practice, reaching 3NF covers almost all real designs.</li>
<li><strong>Denormalization</strong> is not wrong — it is a deliberate choice you make after measuring. Always start normalized, then add redundancy only where you can prove it solves a real performance problem.</li>
</ul>
</div>
<!-- ── Why Normalize ───────────────────────────────────────── -->
<div class="section-label">Motivation</div>
<h2 class="section-title">Update Anomalies — Why Redundancy Is Dangerous</h2>
<p class="section-desc">Redundancy in a relational schema is not just wasteful storage — it creates three types of update anomalies that silently corrupt data. Every normal form exists to eliminate one of these anomaly types.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Insert anomaly</h4>
<p>Imagine a table that stores order rows with the customer's name and city baked in. If you want to add a new customer to the system before they have placed any order, you cannot — there is nowhere to put them. The customer information is tied to an order row, so a customer without an order simply cannot exist. This is an insert anomaly: you are forced to create unrelated data just to record the thing you actually want.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Update anomaly</h4>
<p>If a customer's city is stored in every order row, and that customer moves to a new city, you have to update hundreds of rows at once. If you update 99 out of 100 rows and miss one, your database now has contradicting information — the same customer living in two different cities at the same time. This is an update anomaly, and it is a silent data corruption problem. You may not even notice it until much later.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>Delete anomaly</h4>
<p>If the only record of a customer's address is embedded in order rows, then deleting the customer's last order also deletes their address — even though you only meant to delete the order. Information about the real world disappears as a side effect of an unrelated deletion. This is a delete anomaly: two pieces of information that should be independent are so tangled together that you cannot remove one without accidentally removing the other.</p>
</div>
</div>
</div>
<!-- ── Functional Dependencies ────────────────────────────── -->
<div class="section-label">Foundation</div>
<h2 class="section-title">Functional Dependencies</h2>
<p class="section-desc">A functional dependency (FD) A→B says: for any two rows in the table with the same value of A, they must have the same value of B. A uniquely determines B. FDs are the mathematical foundation for all normal forms. Normalization is the process of decomposing a relation so that each FD is "enforced" in exactly one table.</p>
<div class="mini-cards">
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Full FD</h4>
<p>A functional dependency (FD) just means "knowing this column tells you that column." For example, knowing a student ID tells you their name. A full FD is one where you need all the pieces of a composite key — you need both the order ID and the product ID together to know the quantity ordered. Neither alone is enough.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Partial FD</h4>
<p>A partial FD is a problem: part of your composite primary key determines a non-key column by itself, without needing the other part. For example, if your primary key is (order_id, product_id) but customer_name is determined by order_id alone — not by the combination — then customer_name does not belong in this table. It depends on only half the key. This violates 2NF and causes the customer name to be repeated in every row for the same order.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Transitive FD</h4>
<p>A transitive FD is an indirect chain: A determines B, and B determines C, so A indirectly determines C through B. For example, an order has a zip code, and a zip code determines the city. So the order indirectly determines the city — but via the zip code, not directly. The city does not belong in the orders table; it belongs in a zip_codes table. Storing it in orders creates a 3NF violation.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Armstrong's Axioms</h4>
<p>Armstrong's Axioms are a set of logical rules for reasoning about which columns determine which other columns. You do not need to memorize the formal symbols, but the ideas are intuitive. Reflexivity: a column trivially determines itself. Augmentation: if A determines B, then A combined with C also determines B combined with C. Transitivity: if A determines B and B determines C, then A determines C. These rules are used to figure out the full set of things any given set of columns can determine — helpful when checking whether a design is fully normalized.</p>
</div>
</div>
<!-- ── Normal Forms ───────────────────────────────────────── -->
<div class="section-label">1NF</div>
<h2 class="section-title">First Normal Form — Atomic Values</h2>
<p class="section-desc">A table is in 1NF if every column contains only atomic (single, indivisible) values and every row is unique. Violations: storing a list in a cell ("Apple, Banana"), repeating column groups (product1, product2, product3), or nested tables.</p>
<div class="table-wrap">
<table class="compare-table">
<thead><tr><th>Violation (Not 1NF)</th><th>Fix (1NF)</th></tr></thead>
<tbody>
<tr><td>tags = "sql,nosql,postgres" (list in one cell)</td><td>One row per tag: (post_id, tag) pairs in a separate table</td></tr>
<tr><td>item1, item2, item3 columns (repeating groups)</td><td>One item per row in an order_items table</td></tr>
<tr><td>address = "123 Main St, Springfield, IL" (compound)</td><td>street, city, state, zip as separate columns</td></tr>
<tr><td>phone_numbers = ["555-1234", "555-5678"] (array)</td><td>Separate user_phones table with (user_id, phone)</td></tr>
</tbody>
</table>
</div>
<!-- ── 2NF ────────────────────────────────────────────────── -->
<div class="section-label">2NF</div>
<h2 class="section-title">Second Normal Form — No Partial Dependencies</h2>
<p class="section-desc">A table in 1NF is also in 2NF if every non-key attribute depends on the FULL primary key — not just part of it. This only matters when the primary key is composite.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Identify the violation</h4>
<p>Table: <code>order_products(order_id, product_id, quantity, product_name, unit_price)</code>. PK is (order_id, product_id). But product_name and unit_price depend only on product_id — not on the full PK. That is a partial dependency: part of the composite key determines non-key attributes.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Decompose</h4>
<p>Extract the partially dependent attributes into a new table with the partial key as PK. Keep only the attributes that depend on the full key in the original table.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>Result</h4>
<p><code>order_products(order_id, product_id, quantity)</code> — PK is full (order_id, product_id), and quantity genuinely needs both. <code>products(product_id, product_name, unit_price)</code> — product_id determines name and price independently. Now product_name changes in one place only.</p>
</div>
</div>
</div>
<!-- ── 3NF ────────────────────────────────────────────────── -->
<div class="section-label">3NF</div>
<h2 class="section-title">Third Normal Form — No Transitive Dependencies</h2>
<p class="section-desc">A table in 2NF is also in 3NF if no non-key attribute depends on another non-key attribute. Transitivity chain: PK → A → B means B is transitively dependent on the PK through A. Extract A and B into a separate table.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Identify the chain</h4>
<p>Table: <code>orders(order_id, customer_id, customer_name, customer_zip, city, state)</code>. order_id → customer_zip (direct). customer_zip → city (transitive via zip!). customer_zip → state (transitive). City and state depend on zip, not directly on order_id.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Decompose at the transitive link</h4>
<p>Create <code>zip_codes(zip, city, state)</code> where zip is the PK. Remove city and state from orders. Keep only zip in the orders table as a FK reference.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>Result</h4>
<p><code>orders(order_id, customer_id, customer_zip)</code>. <code>zip_codes(zip, city, state)</code>. When a city name changes (e.g., a city renaming), update exactly one row in zip_codes — not thousands of order rows. The update anomaly is eliminated.</p>
</div>
</div>
</div>
<!-- ── BCNF ───────────────────────────────────────────────── -->
<div class="section-label">BCNF</div>
<h2 class="section-title">Boyce-Codd Normal Form</h2>
<p class="section-desc">BCNF is stricter than 3NF: for every non-trivial FD X→Y, X must be a superkey. 3NF allows Y to be a prime attribute (part of a candidate key); BCNF does not. Most tables in 3NF are also in BCNF — violations are rare but occur when a table has multiple overlapping candidate keys.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Classic BCNF violation example</h4>
<p>Relation <code>R(student, course, teacher)</code> where: {student, course} is a candidate key; {student, teacher} is also a candidate key (each teacher teaches only one course, each student-teacher pair is unique). FD: teacher → course. But teacher is NOT a superkey — it only determines course, not the full tuple. This violates BCNF. In 3NF, this is allowed because course is a prime attribute.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>BCNF decomposition</h4>
<p>Split into <code>teacher_course(teacher, course)</code> (with teacher as PK — the determinant) and <code>student_teacher(student, teacher)</code>. Both are in BCNF. Tradeoff: the FD {student, course} → teacher is no longer enforceable in a single table — it must be re-derived via a join. BCNF may sacrifice dependency preservation, but never lossless-join decomposition.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>3NF vs BCNF tradeoff</h4>
<p>3NF always preserves all functional dependencies — useful when you need to enforce FDs via key constraints. BCNF eliminates all redundancy but may require application logic or triggers to enforce some FDs. In practice, target 3NF for OLTP schemas; BCNF only when specific anomalies are observed.</p>
</div>
</div>
</div>
<!-- ── SQL Example ───────────────────────────────────────── -->
<div class="code-block">
<div class="cb-header"><span class="cb-lang">SQL — Before and After 3NF Normalization</span></div>
<pre><span class="cmt">-- BEFORE: denormalized order table (multiple anomaly types)</span>
<span class="cmt">-- order_data(order_id, cust_id, cust_name, cust_zip, city, state, product, price, qty)</span>
<span class="cmt">-- FDs: order_id → cust_id, cust_name, cust_zip</span>
<span class="cmt">-- cust_zip → city, state (transitive via zip)</span>
<span class="cmt">-- product → price (partial dep on product alone)</span>
<span class="cmt">-- (order_id, product) → qty (full dep on composite key)</span>
<span class="cmt">-- AFTER: normalized to 3NF</span>
<span class="kw">CREATE TABLE</span> zip_codes (
zip <span class="fn">CHAR</span>(<span class="num">5</span>) <span class="kw">PRIMARY KEY</span>,
city <span class="fn">VARCHAR</span>(<span class="num">100</span>) <span class="kw">NOT NULL</span>,
state <span class="fn">CHAR</span>(<span class="num">2</span>) <span class="kw">NOT NULL</span>
);
<span class="kw">CREATE TABLE</span> customers (
customer_id <span class="fn">SERIAL</span> <span class="kw">PRIMARY KEY</span>,
name <span class="fn">VARCHAR</span>(<span class="num">100</span>) <span class="kw">NOT NULL</span>,
zip <span class="fn">CHAR</span>(<span class="num">5</span>) <span class="kw">REFERENCES</span> zip_codes(zip)
);
<span class="kw">CREATE TABLE</span> products (
product_id <span class="fn">SERIAL</span> <span class="kw">PRIMARY KEY</span>,
name <span class="fn">VARCHAR</span>(<span class="num">200</span>) <span class="kw">NOT NULL</span>,
unit_price <span class="fn">NUMERIC</span>(<span class="num">10</span>,<span class="num">2</span>) <span class="kw">NOT NULL</span>
);
<span class="kw">CREATE TABLE</span> orders (
order_id <span class="fn">SERIAL</span> <span class="kw">PRIMARY KEY</span>,
customer_id <span class="fn">INT</span> <span class="kw">NOT NULL REFERENCES</span> customers(customer_id),
created_at <span class="fn">TIMESTAMPTZ</span> <span class="kw">NOT NULL DEFAULT</span> now()
);
<span class="kw">CREATE TABLE</span> order_items (
order_id <span class="fn">INT</span> <span class="kw">REFERENCES</span> orders(order_id),
product_id <span class="fn">INT</span> <span class="kw">REFERENCES</span> products(product_id),
quantity <span class="fn">INT</span> <span class="kw">NOT NULL CHECK</span> (quantity > <span class="num">0</span>),
<span class="kw">PRIMARY KEY</span> (order_id, product_id)
);
<span class="cmt">-- Now city update: one row in zip_codes (was: thousands of order rows)</span>
<span class="kw">UPDATE</span> zip_codes <span class="kw">SET</span> city = <span class="str">'New Springfield'</span> <span class="kw">WHERE</span> zip = <span class="str">'62701'</span>;
<span class="cmt">-- Can add a customer before they place any order (no insert anomaly)</span>
<span class="kw">INSERT INTO</span> customers (name, zip) <span class="kw">VALUES</span> (<span class="str">'Alice'</span>, <span class="str">'62701'</span>);
<span class="cmt">-- Deleting an order doesn't lose customer data (no delete anomaly)</span>
<span class="kw">DELETE FROM</span> orders <span class="kw">WHERE</span> order_id = <span class="num">42</span>;</pre>
</div>
<!-- ── OLAP Schemas ───────────────────────────────────────── -->
<div class="section-label">OLAP vs OLTP</div>
<h2 class="section-title">Star Schema and Denormalization for Analytics</h2>
<p class="section-desc">Normalization is ideal for OLTP (Online Transaction Processing) — frequent, small updates where redundancy causes anomalies. OLAP (Online Analytical Processing) workloads — bulk reads, aggregations, complex filters — benefit from controlled denormalization to reduce join counts.</p>
<div class="table-wrap">
<table class="compare-table">
<thead>
<tr><th>Property</th><th>Normalized (3NF) — OLTP</th><th>Star Schema — OLAP</th><th>Snowflake Schema — OLAP</th></tr>
</thead>
<tbody>
<tr><td>Redundancy</td><td>None — each fact stored once</td><td>Dimension tables denormalized</td><td>Dimension tables normalized</td></tr>
<tr><td>Join count</td><td>Many (4–10 per report query)</td><td>Few (fact + dimension tables)</td><td>More than star (dimension hierarchies)</td></tr>
<tr><td>Update anomalies</td><td>None</td><td>Possible in dimensions</td><td>Reduced vs star</td></tr>
<tr><td>Query speed</td><td>Slower (more joins)</td><td>Fast (fewer joins)</td><td>Between star and normalized</td></tr>
<tr><td>Storage size</td><td>Smallest</td><td>Larger (dimension data repeated)</td><td>Between</td></tr>
<tr><td>Typical use</td><td>Transactional apps, RDBMS core</td><td>Snowflake, BigQuery, Redshift fact tables</td><td>Enterprise data warehouses</td></tr>
</tbody>
</table>
</div>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Star schema structure</h4>
<p>One central fact table (measurements: sales_amount, quantity_sold) with foreign keys to multiple dimension tables (date, product, customer, store). Dimension tables are intentionally denormalized — they store all attributes of the dimension, even if those attributes are themselves functionally related. Example: dim_product stores (product_id, name, category, subcategory, brand, manufacturer) even though subcategory → category is a transitive dependency. Fewer joins means BI tools respond faster.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Slowly Changing Dimensions (SCD)</h4>
<p>When dimension data changes (customer changes address, product changes category), you have a choice: Type 1 — overwrite (lose history), Type 2 — add a new row with valid_from/valid_to timestamps (full history), Type 3 — add a new column for previous value (limited history). SCD Type 2 is most common in enterprise DW — every historical sale records the product's category as it was at the time of sale.</p>
</div>
</div>
</div>
<!-- ── Interactive Demo ───────────────────────────────────── -->
<div class="section-label">Interactive Demo</div>
<h2 class="section-title">Normalization Animator</h2>
<p class="section-desc">Start with a denormalized table with 1NF violations (red cells). Step through normalization. Each step shows the table decomposition animated on the canvas.</p>
<div class="diagram-box">
<svg viewBox="0 0 700 230" role="img" aria-label="Normalization stages from 1NF to BCNF">
<!-- Raw / Unnormalized -->
<rect x="10" y="20" width="140" height="190" rx="8" class="svg-box-r"/>
<text x="80" y="44" text-anchor="middle" class="svg-label">Unnormalized</text>
<text x="80" y="62" text-anchor="middle" class="svg-soft">Repeating groups</text>
<text x="80" y="80" text-anchor="middle" class="svg-mono">course, student,</text>
<text x="80" y="95" text-anchor="middle" class="svg-mono">grade, teacher,</text>
<text x="80" y="110" text-anchor="middle" class="svg-mono">dept, room...</text>
<text x="80" y="132" text-anchor="middle" class="svg-soft" style="fill:#EF4444">multi-value cells</text>
<!-- 1NF -->
<rect x="178" y="20" width="130" height="190" rx="8" class="svg-box-a"/>
<text x="243" y="44" text-anchor="middle" class="svg-label">1NF</text>
<text x="243" y="62" text-anchor="middle" class="svg-soft">Atomic values</text>
<text x="243" y="80" text-anchor="middle" class="svg-mono">PK: (student_id,</text>
<text x="243" y="95" text-anchor="middle" class="svg-mono">course_id)</text>
<text x="243" y="120" text-anchor="middle" class="svg-soft" style="fill:#F59E0B">partial deps remain</text>
<!-- 2NF -->
<rect x="336" y="20" width="130" height="190" rx="8" class="svg-box-c"/>
<text x="401" y="44" text-anchor="middle" class="svg-label">2NF</text>
<text x="401" y="62" text-anchor="middle" class="svg-soft">Remove partial deps</text>
<text x="401" y="80" text-anchor="middle" class="svg-mono">students(id, name)</text>
<text x="401" y="95" text-anchor="middle" class="svg-mono">courses(id, teacher)</text>
<text x="401" y="110" text-anchor="middle" class="svg-mono">enrollments(s,c,gr)</text>
<text x="401" y="130" text-anchor="middle" class="svg-soft" style="fill:#0EA5E9">transitive deps remain</text>
<!-- 3NF / BCNF -->
<rect x="494" y="20" width="196" height="190" rx="8" class="svg-box-g"/>
<text x="592" y="44" text-anchor="middle" class="svg-label">3NF / BCNF</text>
<text x="592" y="62" text-anchor="middle" class="svg-soft">Remove transitive deps</text>
<text x="592" y="80" text-anchor="middle" class="svg-mono">teachers(id, dept)</text>
<text x="592" y="95" text-anchor="middle" class="svg-mono">depts(id, room)</text>
<text x="592" y="110" text-anchor="middle" class="svg-mono">courses(id, teacher_id)</text>
<text x="592" y="130" text-anchor="middle" class="svg-soft" style="fill:#10B981">no redundancy</text>
<!-- Arrows -->
<line x1="150" y1="115" x2="178" y2="115" class="svg-line svg-dash" style="stroke:#F59E0B"/>
<line x1="308" y1="115" x2="336" y2="115" class="svg-line svg-dash" style="stroke:#0EA5E9"/>
<line x1="466" y1="115" x2="494" y2="115" class="svg-line svg-dash" style="stroke:#10B981"/>
<!-- Packets -->
<circle class="pkt" cx="150" cy="115" r="5" fill="#F59E0B"/>
<circle class="pkt" cx="308" cy="115" r="5" fill="#0EA5E9"/>
<circle class="pkt" cx="466" cy="115" r="5" fill="#10B981"/>
</svg>
<p class="diagram-caption">Each normal form eliminates a specific class of data anomaly. 1NF removes multi-valued cells; 2NF removes partial dependency on a composite key; 3NF removes transitive dependencies; BCNF handles edge cases where non-trivial determinants are not superkeys.</p>
</div>
<div class="demo-section" id="demo-normalization">
<div class="demo-header">
<h3>Normalization Steps</h3>
<div class="demo-controls">
<button class="demo-btn" data-action="next-norm">Next Step →</button>
<button class="demo-btn" data-action="reset-norm">Reset</button>
</div>
</div>
<div class="demo-canvas-wrap"></div>
<div class="demo-stats">
<div class="demo-stat">Steps: D → 1NF → 2NF → 3NF</div>
<div class="demo-stat">Red values = 1NF violations</div>
</div>
</div>
<!-- ── Denormalization ────────────────────────────────────── -->
<div class="section-label">Denormalization</div>
<h2 class="section-title">When to Denormalize Deliberately</h2>
<p class="section-desc">Denormalization is the deliberate introduction of redundancy for a performance reason. It is not a failure of design — it is a conscious trade-off. The prerequisite is always a measured performance problem, not an assumption.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Cached aggregates</h4>
<p>Store a pre-computed count or sum on the parent row. Example: <code>users.order_count</code> updated by a trigger or application code on every order insert/delete. Queries that need order_count avoid a <code>COUNT(*)</code> aggregate across all orders. Maintained via triggers or background jobs; document the denormalization contract clearly.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Materialized views</h4>
<p>A materialized view stores the result of a query on disk. Queries hit the materialized view instead of the base tables — no join overhead. PostgreSQL's <code>REFRESH MATERIALIZED VIEW CONCURRENTLY</code> updates it without blocking readers. Use for expensive aggregations and reports that run frequently but whose data changes infrequently (dashboards, leaderboards, reporting tables).</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>Embedding for NoSQL</h4>
<p>In MongoDB/Cassandra, related data is embedded in a single document/row rather than normalized across collections. This trades update overhead for read speed — the entire object is retrieved in one I/O. Use embedding when the embedded data is always read with the parent, rarely updated independently, and bounded in size. Use references (normalization equivalent) when the embedded data has its own identity and lifecycle.</p>
</div>
</div>
</div>
<!-- ── Anti-patterns ──────────────────────────────────────── -->
<div class="section-label">Anti-patterns</div>
<div class="antipatterns">
<div class="antipattern">
<h4>Comma-separated values in a single column</h4>
<p><code>tags = "sql,database,postgres"</code> violates 1NF. You cannot index individual values, enforce FK constraints, or query a specific tag without string parsing. Use a separate tags table with (entity_id, tag) rows. If using PostgreSQL, an array column with a GIN index is the pragmatic middle ground.</p>
</div>
<div class="antipattern">
<h4>Denormalizing without profiling first</h4>
<p>The JOIN between two indexed tables is usually fast (milliseconds). The update anomaly from storing customer city in every order row is always costly (potentially thousands of rows per update, inconsistency risk). Prove the JOIN is actually the bottleneck with EXPLAIN ANALYZE before adding redundancy.</p>
</div>
<div class="antipattern">
<h4>Over-normalizing OLAP schemas</h4>
<p>Pushing an analytical schema to 3NF or beyond means dozens of JOINs per reporting query. BI tools and analysts struggle with complex join paths. Star schemas intentionally stop at controlled denormalization — dimension tables are not normalized. Know your workload before choosing the schema pattern.</p>
</div>
<div class="antipattern">
<h4>Encoding multiple facts in one column</h4>
<p><code>status = "paid_shipped"</code> encodes two facts (payment status and shipping status) in one column. When payment or shipping logic changes independently, you must parse and rewrite the encoding. Use two separate boolean or enum columns — one for payment_status, one for shipping_status.</p>
</div>
</div>
<!-- ── Quiz ──────────────────────────────────────────────── -->
<div class="section-label">Quiz</div>
<div class="quiz-section">
<div class="quiz-question">
<div class="quiz-q-num">Question 1 of 5</div>
<div class="quiz-q-text">First Normal Form (1NF) requires that all attribute values are:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="2NF eliminates partial dependencies. 1NF is specifically about atomicity of values."><span class="opt-letter">A</span>Free of partial key dependencies</div>
<div class="quiz-option" data-correct="false" data-explanation="Composite keys are perfectly fine in 1NF — the issue is multi-valued attributes in cells."><span class="opt-letter">B</span>Based on a single-column primary key</div>
<div class="quiz-option" data-correct="true" data-explanation="1NF requires each attribute value to be atomic — a single, indivisible value. No sets, lists, arrays, or repeating groups in a single cell. Each row must be uniquely identifiable."><span class="opt-letter">C</span>Atomic — each cell contains a single, indivisible value</div>
<div class="quiz-option" data-correct="false" data-explanation="This describes uniqueness, not atomicity. 1NF requires both, but atomicity is the defining criterion."><span class="opt-letter">D</span>Equal in count to the primary key attributes</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 2 of 5</div>
<div class="quiz-q-text">Which normal form eliminates transitive functional dependencies?</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="1NF addresses atomicity of values, not transitive dependencies."><span class="opt-letter">A</span>1NF</div>
<div class="quiz-option" data-correct="false" data-explanation="2NF eliminates partial dependencies — non-key columns depending on only part of a composite key."><span class="opt-letter">B</span>2NF</div>
<div class="quiz-option" data-correct="true" data-explanation="3NF eliminates transitive dependencies: non-key column A depends on non-key column B which depends on the key. The chain key → B → A is transitive; A should be in a separate table keyed by B."><span class="opt-letter">C</span>3NF</div>
<div class="quiz-option" data-correct="false" data-explanation="BCNF is stricter than 3NF — it eliminates all remaining anomalies where a determinant is not a superkey. But the term 'transitive dependencies' maps to 3NF."><span class="opt-letter">D</span>BCNF</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 3 of 5</div>
<div class="quiz-q-text">A functional dependency A → B means:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="That is B → A — the reverse dependency. The arrow direction matters."><span class="opt-letter">A</span>B determines A</div>
<div class="quiz-option" data-correct="true" data-explanation="A → B means: for any two rows with the same A value, they must also have the same B value. Knowing A uniquely determines B. Example: student_id → student_name."><span class="opt-letter">B</span>Each A value uniquely determines the corresponding B value</div>
<div class="quiz-option" data-correct="false" data-explanation="A and B having equal values in every row would be a trivial FD or an equality constraint — not the general definition."><span class="opt-letter">C</span>A and B always contain identical values in every row</div>
<div class="quiz-option" data-correct="false" data-explanation="B being a primary key is a separate constraint. B can be a non-key attribute in a functional dependency."><span class="opt-letter">D</span>B is always the primary key of its relation</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 4 of 5</div>
<div class="quiz-q-text">Table: (order_id, product_id, quantity, product_name). PK is (order_id, product_id). What normal form violation exists?</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="1NF violations are about non-atomic values in cells — this table has no multi-valued cells."><span class="opt-letter">A</span>1NF — non-atomic values</div>
<div class="quiz-option" data-correct="true" data-explanation="product_name depends only on product_id, not on the full composite key (order_id, product_id). This is a partial dependency — product_name should be in a separate products table with product_id as PK. Violates 2NF."><span class="opt-letter">B</span>2NF — partial dependency (product_name depends only on product_id)</div>
<div class="quiz-option" data-correct="false" data-explanation="3NF violations involve non-key → non-key transitive chains. Here the issue is simpler: a non-key column depending on only part of the composite key."><span class="opt-letter">C</span>3NF — transitive dependency</div>
<div class="quiz-option" data-correct="false" data-explanation="BCNF violations require that a determinant is not a superkey — the issue here is more basic (partial dependency in 2NF terms)."><span class="opt-letter">D</span>BCNF — determinant is not a superkey</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 5 of 5</div>
<div class="quiz-q-text">In a star schema (used in data warehousing), dimension tables are intentionally:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="Star schemas use dimensional tables which may be intentionally denormalized — not 4NF normalized."><span class="opt-letter">A</span>Normalized to 4NF</div>
<div class="quiz-option" data-correct="false" data-explanation="Having no keys at all would make the tables unusable. Dimension tables always have a surrogate key."><span class="opt-letter">B</span>Without primary keys</div>
<div class="quiz-option" data-correct="true" data-explanation="Star schema dimension tables are intentionally denormalized — they store all attributes including those with transitive dependencies — to reduce join count in analytical queries. Fewer joins mean faster BI queries. The update anomaly risk is accepted because dimension data changes infrequently."><span class="opt-letter">C</span>Denormalized to reduce join count in analytical queries</div>
<div class="quiz-option" data-correct="false" data-explanation="Dimension tables are NOT split by normal forms in a star schema — that is the snowflake schema approach, and even then it is a partial normalization."><span class="opt-letter">D</span>Split per normal form violation into hundreds of tables</div>
</div>
<div class="quiz-feedback"></div>
</div>
</div>
<!-- ── Interview Q&A ──────────────────────────────────────── -->
<div class="section-label">Interview Q&A</div>
<div class="qa-section">
<div class="qa-item">
<div class="qa-q">What are the three types of update anomalies in a denormalized table?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner"><strong>Insert anomaly:</strong> you cannot add a fact without adding an unrelated fact. In a table that stores order + customer data in the same row, you cannot add a new customer until they place an order — the customer's existence is coupled to the order existence. <strong>Update anomaly:</strong> the same fact stored in multiple rows must be updated in all of them. Change a customer's city and you must update every order row for that customer. Miss one and the database becomes inconsistent. <strong>Delete anomaly:</strong> deleting a row destroys unrelated information. Delete the last order for a customer and you lose the customer's address — a fact that has nothing to do with orders. Normalization solves all three by storing each fact in exactly one place.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">Explain the difference between 3NF and BCNF with an example.<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">3NF allows a non-key attribute to determine a prime attribute (part of a candidate key) — as long as the determinant is not a non-prime attribute. BCNF does not — every determinant must be a superkey, period. Example: R(student, course, teacher) where each teacher teaches one course. Candidate keys: {student, course} and {student, teacher}. FD: teacher → course. Teacher is not a superkey (teacher alone doesn't uniquely identify a row). This violates BCNF. But 3NF allows it because course is a prime attribute (part of the first CK). BCNF decomposition: split into (teacher, course) and (student, teacher). Tradeoff: the FD {student, course} → teacher is no longer enforceable via a single table constraint — you lose dependency preservation. 3NF always preserves dependencies; BCNF may not.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">When would you intentionally denormalize and how do you manage the risks?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Denormalize when: (1) EXPLAIN ANALYZE proves the JOIN is the actual bottleneck, not a hypothetical one. (2) Read-heavy OLAP workloads where update anomalies are rare and tolerable. (3) Caching computed aggregates — e.g., storing order_count on the users table updated by triggers or background jobs. Management strategies: use database triggers to keep denormalized columns in sync; use materialized views with scheduled refreshes; document the denormalization explicitly in the schema DDL (comments); write integration tests that verify the denormalized data matches the normalized source. Never denormalize based on intuition — the JOIN is almost always fast enough for OLTP. Denormalization is a last resort, not a starting point.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is Armstrong's Axioms and how are they used in practice?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Armstrong's Axioms are a sound and complete set of inference rules for deriving all FDs from a given set F: (1) <strong>Reflexivity:</strong> if B ⊆ A then A → B (trivial FD). (2) <strong>Augmentation:</strong> if A → B then AC → BC. (3) <strong>Transitivity:</strong> if A → B and B → C then A → C. Derived rules: Union (A→B and A→C ⇒ A→BC), Decomposition, Pseudo-transitivity. In practice, they are used to compute attribute closure F+ — given a set of attributes X, what is the set of all attributes that X functionally determines? The closure X+ is used to: determine if X is a candidate key (if X+ = all attributes); identify all candidate keys; verify whether a proposed decomposition is in 3NF or BCNF.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is a lossless-join decomposition and why does it matter?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">A decomposition of R into R1 and R2 is lossless-join if natural joining R1 and R2 always gives back exactly R — no spurious (extra phantom) tuples, no missing tuples. If a decomposition is lossy, you cannot reconstruct the original relation — information is permanently destroyed. The lossless-join condition: the intersection of R1 and R2 attributes must be a superkey of either R1 or R2. All standard normal form decompositions (1NF through BCNF) must be lossless-join — that is the fundamental requirement. A related but separate property is dependency preservation — all FDs from the original relation can be enforced in at least one decomposed relation without needing a join. 3NF decomposition is always lossless-join AND dependency-preserving. BCNF is always lossless-join but may sacrifice dependency preservation.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is a star schema and how does it differ from a normalized OLTP schema?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">A star schema has one central fact table (sales, events, orders) surrounded by dimension tables (date, product, customer, geography). Dimension tables are intentionally denormalized — all attributes of a dimension are stored in one wide table, even if they have transitive dependencies internally (e.g., subcategory → category → department stored in one dim_product table). This reduces join count: a query needs to join the fact table with only a few dimension tables, not dozens of normalized tables. An OLTP normalized schema has many small tables with clean FDs — optimized for INSERT/UPDATE/DELETE correctness and avoiding anomalies. OLAP schemas optimize for read query performance over update correctness. Key insight: the choice of schema is driven by the workload, not by a universal "best practice."</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is 4NF and when does it apply?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">4NF eliminates multi-valued dependencies (MVDs). An MVD A ↡ B means: for each value of A, the set of B values is independent of the set of C values (all other attributes). Example: R(employee, skill, language) where employee has a set of skills and a set of languages independently. If an employee has skills {Python, SQL} and languages {English, French}, we must store all 4 combinations — (emp, Python, English), (emp, Python, French), etc. This is a multi-valued dependency, not an FD. 4NF: decompose into (employee, skill) and (employee, language) — now each fact is independent. 4NF is rare in practice — most schema design doesn't encounter true MVDs — but it occasionally appears in many-to-many junction tables with multiple independent dimensions.</div></div>
</div>
</div>
<div class="section-label">Further Reading</div>
<div class="reading-links">
<a class="reading-link" href="https://www.bkent.net/Doc/simple5.htm" target="_blank">A Simple Guide to Five Normal Forms (Kent 1983)</a>
<a class="reading-link" href="https://www.youtube.com/watch?v=GFQaEYEc8_8" target="_blank">1NF 2NF 3NF BCNF Explained (YouTube)</a>
<a class="reading-link" href="https://en.wikipedia.org/wiki/Boyce%E2%80%93Codd_normal_form" target="_blank">Boyce-Codd Normal Form (Wikipedia)</a>
</div>
<div class="topic-nav">
<a href="03-sql.html" class="topic-nav-link"><div class="topic-nav-arrow">←</div><div><div class="topic-nav-label">Previous</div><div class="topic-nav-title">SQL Fundamentals</div></div></a>
<a href="05-transactions.html" class="topic-nav-link next"><div class="topic-nav-arrow">→</div><div><div class="topic-nav-label">Next</div><div class="topic-nav-title">Transactions & ACID</div></div></a>
</div>
</div>
<footer class="site-footer">
<p class="footer-sub"><a href="../index.html">Back to Course</a> — DBMS Illustrated</p>
</footer>
<script src="../js/main.js"></script>
<script src="../js/demos.js"></script>
</body>
</html>