source: docs/P5-Normalization/Normalization.md@ 0cee8ec

main
Last change on this file since 0cee8ec was ef1c1c7, checked in by Stefan <trsunovstefan@…>, 5 days ago

Wiki docs, phase 6 and phase 7 added

  • Property mode set to 100644
File size: 30.8 KB
Line 
1# Normalization
2
3This phase deliberately ignores the design from [ERModel](../P1-ConceptualModel/ERModel.md)
4(P1) and [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md) (P2) as a starting
5point. Instead it starts over from a single flat relation containing every attribute of the
6model, derives the functional dependencies that hold on it, and decomposes it formally,
7step by step. The
8[final section](#final-result-and-discussion) compares what falls out of that process with
9the P2 design.
10
11## De-normalized database form
12
13### Building one relation out of the whole model
14
15The ER model has ten entity/relationship sets carrying attributes (see
16[ERModel](../P1-ConceptualModel/ERModel.md)): `Users`, `Cryptos`, `Markets`, `Orders`,
17`Transactions`, `MarketTrades`, `MarketCandles`, `Watchlists`, and the two attributed
18relationships `Holds` and `Contains`. Eight more relationships (`QuotedOn`, `PlacedOn`,
19`Places`, `Records`, `Settles`, `Fills`, `Aggregates`, `Owns`) carry no attributes of their
20own — in Chen notation they need none, because the diagram expresses the link itself as a
21relationship, not a column. A single flat relation has no such device: the only way to keep
22one entity's rows pointed at another's is a plain attribute holding the referenced key,
23which is exactly what P2's ER-to-relational transformation already introduces for each of
24those eight relationships (`markets.crypto_id`, `orders.market_id`, `orders.user_id`,
25`transactions.user_id`, `transactions.related_order`, `market_trades.market_id`,
26`market_candles.market_id`, `watchlists.user_id`). Those linking attributes are included
27below for that reason — not because they were copied from P2's design, but because a "single
28table with everything in it" cannot represent the model at all without them.
29
30Every attribute name is prefixed by a two-or-three-letter code for the entity/relationship it
31came from, because several names repeat across the model (`id`, `created_at`, `quantity`,
32`type`, `name`, `price`, `side` all appear more than once) and the de-normalized relation may
33not contain duplicate names.
34
35| Prefix | Origin (P1 entity / relationship) | Attributes |
36|---|---|---|
37| `U_` | Users | `U_ID, U_USERNAME, U_EMAIL, U_FULL_NAME, U_PASSWORD_HASH, U_AVAILABLE_BALANCE, U_INVESTED_BALANCE, U_CREATED_AT, U_UPDATED_AT` |
38| `C_` | Cryptos | `C_ID, C_SYMBOL, C_NAME, C_CREATED_AT` |
39| `M_` | Markets (+ `QuotedOn`) | `M_ID, M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` |
40| `H_` | `Holds` (+ surrogate key) | `H_ID, H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT` |
41| `O_` | Orders (+ `PlacedOn`, `Places`) | `O_ID, O_USER_ID, O_MARKET_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT` |
42| `T_` | Transactions (+ `Records`, `Settles`) | `T_ID, T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` |
43| `MT_` | MarketTrades (+ `Fills`) | `MT_ID, MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` |
44| `MC_` | MarketCandles (+ `Aggregates`) | `MC_ID, MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` |
45| `W_` | Watchlists (+ `Owns`) | `W_ID, W_USER_ID, W_NAME, W_CREATED_AT` |
46| `WI_` | `Contains` (+ surrogate key) | `WI_ID, WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` |
47
48`H_ID` and `WI_ID` exist for the same reason they exist in P2: `Holds` and `Contains` are M:N
49relationships with their own attributes, and giving each its own surrogate key (rather than
50relying solely on the `{user,crypto}` / `{watchlist,crypto}` pair) is the same design choice
51already justified in [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md#descriptive-representation-of-the-relational-schema).
52
53This gives **one relation, `R_EDUBERZA`, of 68 attributes:**
54
55```
56R_EDUBERZA(
57 U_ID, U_USERNAME, U_EMAIL, U_FULL_NAME, U_PASSWORD_HASH, U_AVAILABLE_BALANCE,
58 U_INVESTED_BALANCE, U_CREATED_AT, U_UPDATED_AT,
59 C_ID, C_SYMBOL, C_NAME, C_CREATED_AT,
60 M_ID, M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT,
61 H_ID, H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE,
62 H_CREATED_AT, H_UPDATED_AT,
63 O_ID, O_USER_ID, O_MARKET_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_PRICE,
64 O_PLACED_AT, O_EXECUTED_AT,
65 T_ID, T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT,
66 T_DESCRIPTION,
67 MT_ID, MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE,
68 MC_ID, MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME,
69 MC_CANDLE_TIME,
70 W_ID, W_USER_ID, W_NAME, W_CREATED_AT,
71 WI_ID, WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT
72)
73```
74
75Every attribute is single-valued and atomic (a balance, a timestamp, a symbol, an amount —
76nothing here is a list or a nested record), so `R_EDUBERZA` satisfies 1NF as soon as it is
77written down. Whether it satisfies anything beyond that is exactly what the rest of this page
78checks.
79
80## Functional dependencies
81
82### Canonical cover
83
84Read directly off the model: each entity's/relationship's own key determines its own
85attributes, nothing more. This is already minimal — no functional dependency below has an
86extraneous attribute on its left side, and no dependent attribute is repeated on the right
87side of more than one dependency, which is what "canonical cover" requires.
88
89| # | Functional dependency | Source |
90|---|---|---|
91| FD1 | `U_ID → U_USERNAME, U_EMAIL, U_FULL_NAME, U_PASSWORD_HASH, U_AVAILABLE_BALANCE, U_INVESTED_BALANCE, U_CREATED_AT, U_UPDATED_AT` | Users |
92| FD2 | `U_USERNAME → U_ID` | Users (`UNIQUE(username)`) |
93| FD3 | `U_EMAIL → U_ID` | Users (`UNIQUE(email)`) |
94| FD4 | `C_ID → C_SYMBOL, C_NAME, C_CREATED_AT` | Cryptos |
95| FD5 | `C_SYMBOL → C_ID` | Cryptos (`UNIQUE(symbol)`) |
96| FD6 | `M_ID → M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` | Markets |
97| FD7 | `M_CRYPTO_ID, M_QUOTE_CURRENCY → M_ID` | Markets (`UNIQUE(crypto_id, quote_currency)`) |
98| FD8 | `H_ID → H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT` | Holds |
99| FD9 | `H_USER_ID, H_CRYPTO_ID → H_ID` | Holds (`UNIQUE(user_id, crypto_id)`) |
100| FD10 | `O_ID → O_USER_ID, O_MARKET_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT` | Orders |
101| FD11 | `T_ID → T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` | Transactions |
102| FD12 | `MT_ID → MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` | MarketTrades |
103| FD13 | `MC_ID → MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` | MarketCandles |
104| FD14 | `MC_MARKET_ID, MC_TIMEFRAME, MC_CANDLE_TIME → MC_ID` | MarketCandles (`UNIQUE(market_id, timeframe, candle_time)`) |
105| FD15 | `W_ID → W_USER_ID, W_NAME, W_CREATED_AT` | Watchlists |
106| FD16 | `WI_ID → WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` | Contains |
107| FD17 | `WI_WATCHLIST_ID, WI_CRYPTO_ID → WI_ID` | Contains (`UNIQUE(watchlist_id, crypto_id)`) |
108
109**Minimality, checked by example (Markets):** could FD7 drop an attribute from its left side?
110`M_CRYPTO_ID` alone does not determine `M_ID` — many markets can reference the same crypto in
111different quote currencies (that is the entire point of the market entity), so two rows can
112share `M_CRYPTO_ID` and disagree on `M_ID`. `M_QUOTE_CURRENCY` alone fails the same way in the
113other direction. Neither attribute is extraneous, so the left side of FD7 cannot shrink. The
114same check applies to FD9, FD14 and FD17, whose composite left sides come directly from the
115`UNIQUE` constraints already justified per-relation in
116[RelationalDesign](../P2-RelationalDesign/RelationalDesign.md); none of those constraints
117holds on a proper subset of its columns either.
118
119**No redundant dependency:** each of FD1–FD17 has a right side that is not implied by any
120other dependency in the set — for instance, nothing outside FD1 mentions `U_AVAILABLE_BALANCE`,
121so FD1 cannot be derived from the rest and cannot be dropped. This set is the canonical cover.
122
123### Dependencies carried by foreign keys
124
125Six attributes above are foreign keys: `M_CRYPTO_ID`, `H_USER_ID`, `H_CRYPTO_ID`,
126`O_USER_ID`, `O_MARKET_ID`, `T_USER_ID`, `T_RELATED_ORDER`, `MT_MARKET_ID`, `MC_MARKET_ID`,
127`W_USER_ID`, `WI_WATCHLIST_ID`, `WI_CRYPTO_ID` — each one draws its values from the same
128domain as some other attribute's key. Because of that, every dependency that holds on the
129referenced key also holds, by substitution, on the referencing attribute:
130
131| Foreign key | References | Therefore also determines |
132|---|---|---|
133| `M_CRYPTO_ID` | `C_ID` | `C_SYMBOL, C_NAME, C_CREATED_AT` |
134| `H_USER_ID` | `U_ID` | all of `U_*` |
135| `H_CRYPTO_ID` | `C_ID` | all of `C_*` |
136| `O_USER_ID` | `U_ID` | all of `U_*` |
137| `O_MARKET_ID` | `M_ID` | all of `M_*`, and transitively all of `C_*` |
138| `T_USER_ID` | `U_ID` | all of `U_*` |
139| `T_RELATED_ORDER` | `O_ID` | all of `O_*`, and transitively `U_*`, `M_*`, `C_*` (when not null) |
140| `MT_MARKET_ID` | `M_ID` | all of `M_*`, transitively `C_*` |
141| `MC_MARKET_ID` | `M_ID` | all of `M_*`, transitively `C_*` |
142| `W_USER_ID` | `U_ID` | all of `U_*` |
143| `WI_WATCHLIST_ID` | `W_ID` | all of `W_*`, transitively `U_*` |
144| `WI_CRYPTO_ID` | `C_ID` | all of `C_*` |
145
146None of these is added to the canonical cover — each is *derivable* from FD1–FD17 by
147transitivity plus the foreign-key identity, which is exactly why a canonical cover excludes
148them. They matter anyway: they are precisely the transitive dependencies the 3NF check below
149has to rule out.
150
151## Candidate keys and primary key
152
153`Orders`, `Transactions`, `MarketTrades`, `MarketCandles`, `Holds`, `Watchlists` and
154`Contains` are, with respect to each other, independent record types: nothing about an
155order's id says anything about which market-candle row, or which unrelated transaction, or
156which watchlist item is in the same tuple of `R_EDUBERZA` — a user can exist with zero of any
157of them, and having one order says nothing about how many holdings, trades or candles exist
158alongside it. (The one FK that crosses between two of these — `T_RELATED_ORDER` — is
159nullable, so it cannot be relied on to always connect a transaction row back to an order.)
160That means no proper subset of attributes can functionally determine all 68 attributes of
161`R_EDUBERZA`: the only way to pin down a `H_*` value, an `O_*` value, a `T_*` value, an
162`MT_*` value, an `MC_*` value, a `W_*` value *and* a `WI_*` value at once is to state one
163identifying attribute from each cluster explicitly.
164
165**Chosen primary key** (closure shown below):
166
167```
168{ U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, W_ID, WI_ID }
169```
170
171**Closure check**, applying FD1–FD17 in turn to this set:
172
173| Step | Attributes added | Dependency used |
174|---|---|---|
175| start | `U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, W_ID, WI_ID` | — |
176| 1 | `U_USERNAME, U_EMAIL, U_FULL_NAME, U_PASSWORD_HASH, U_AVAILABLE_BALANCE, U_INVESTED_BALANCE, U_CREATED_AT, U_UPDATED_AT` | FD1 (`U_ID → …`) |
177| 2 | `C_SYMBOL, C_NAME, C_CREATED_AT` | FD4 |
178| 3 | `M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` | FD6 |
179| 4 | `H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT` | FD8 |
180| 5 | `O_USER_ID, O_MARKET_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT` | FD10 |
181| 6 | `T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` | FD11 |
182| 7 | `MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` | FD12 |
183| 8 | `MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` | FD13 |
184| 9 | `W_USER_ID, W_NAME, W_CREATED_AT` | FD15 |
185| 10 | `WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` | FD16 |
186
187The closure now contains all 68 attributes, so the set is a superkey; removing any one of its
188ten attributes drops an entire cluster that nothing else in the set can reach (e.g. drop
189`T_ID` and no remaining attribute determines any `T_*` value), so it is minimal — a candidate
190key.
191
192**It is not the only one.** Any attribute that is itself a determinant of a whole cluster can
193stand in for that cluster's id — `U_USERNAME` or `U_EMAIL` for `U_ID` (FD2/FD3), `C_SYMBOL`
194for `C_ID` (FD5), `{M_CRYPTO_ID, M_QUOTE_CURRENCY}` for `M_ID` (FD7), `{H_USER_ID,
195H_CRYPTO_ID}` for `H_ID` (FD9), `{MC_MARKET_ID, MC_TIMEFRAME, MC_CANDLE_TIME}` for `MC_ID`
196(FD14), `{WI_WATCHLIST_ID, WI_CRYPTO_ID}` for `WI_ID` (FD17) — giving 3 × 2 × 2 × 2 × 1 × 1 ×
1971 × 2 × 1 × 2 = 96 candidate keys in total. The all-surrogate-id combination above is chosen
198as **primary key** for the same reason `id` was chosen over `username`/`email`/`symbol`/etc.
199per entity in [ERModel](../P1-ConceptualModel/ERModel.md): it is opaque, and none of its parts
200are things a user would ever legitimately change.
201
202**Normal form of `R_EDUBERZA` before decomposition:** 1NF only, and barely that — see 2NF
203below. It cannot be in 2NF, 3NF or BCNF, since each of those requires 2NF as a precondition.
204
205## 1NF decomposition
206
207No decomposition happens at this step. 1NF requires atomic, single-valued attributes and no
208repeating groups; `R_EDUBERZA` was built that way from the start (every column above is a
209single scalar), so the relation already satisfies 1NF as written in
210[De-normalized database form](#de-normalized-database-form). The real work starts at 2NF.
211
212## 2NF decomposition
213
214**Relation analyzed:** `R_EDUBERZA`, all 68 attributes, primary key
215`{U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, W_ID, WI_ID}` (10 attributes), FD1–FD17
216in force.
217
218**Current normal form:** 1NF only (previous section).
219
220**Violations:** 2NF forbids a non-prime attribute from depending on *part* of a candidate
221key. Every single functional dependency in the canonical cover (FD1–FD17) has a left side
222that is a **proper subset** of the ten-attribute primary key — `U_ID` alone, `C_ID` alone, …,
223down to the two-attribute `{WI_WATCHLIST_ID, WI_CRYPTO_ID}`. There is no non-prime attribute
224in `R_EDUBERZA` that depends on the whole ten-attribute key and nothing smaller. In other
225words, *every* non-prime attribute violates 2NF at once — the violation is not a handful of
226stray columns to peel off, it is the entire relation, because gluing ten independent record
227types together under one artificial composite key was never going to satisfy 2NF to begin
228with.
229
230**Decomposition.** This uses 3NF/BCNF **synthesis** (Bernstein's algorithm) rather than the
231binary decomposition algorithm: since the canonical cover is already in hand (as the phase
232instructions recommend building first), synthesis creates one relation per left-hand side in
233the cover directly, instead of hunting for one offending dependency at a time and splitting
234in two repeatedly. Grouping FD1–FD17 by determinant produces ten relations:
235
236| New relation | Attributes | Key(s) | Source FDs |
237|---|---|---|---|
238| `R_USERS` | `U_ID, U_USERNAME, U_EMAIL, U_FULL_NAME, U_PASSWORD_HASH, U_AVAILABLE_BALANCE, U_INVESTED_BALANCE, U_CREATED_AT, U_UPDATED_AT` | `U_ID`, `U_USERNAME`, `U_EMAIL` | FD1, FD2, FD3 |
239| `R_CRYPTO` | `C_ID, C_SYMBOL, C_NAME, C_CREATED_AT` | `C_ID`, `C_SYMBOL` | FD4, FD5 |
240| `R_MARKETS` | `M_ID, M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` | `M_ID`, `{M_CRYPTO_ID, M_QUOTE_CURRENCY}` | FD6, FD7 |
241| `R_HOLDINGS` | `H_ID, H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT` | `H_ID`, `{H_USER_ID, H_CRYPTO_ID}` | FD8, FD9 |
242| `R_ORDERS` | `O_ID, O_USER_ID, O_MARKET_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT` | `O_ID` | FD10 |
243| `R_TRANSACTIONS` | `T_ID, T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` | `T_ID` | FD11 |
244| `R_MARKET_TRADES` | `MT_ID, MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` | `MT_ID` | FD12 |
245| `R_MARKET_CANDLES` | `MC_ID, MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` | `MC_ID`, `{MC_MARKET_ID, MC_TIMEFRAME, MC_CANDLE_TIME}` | FD13, FD14 |
246| `R_WATCHLISTS` | `W_ID, W_USER_ID, W_NAME, W_CREATED_AT` | `W_ID` | FD15 |
247| `R_WATCHLIST_ITEMS` | `WI_ID, WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` | `WI_ID`, `{WI_WATCHLIST_ID, WI_CRYPTO_ID}` | FD16, FD17 |
248
249Every one of these ten relations now has **all** of its non-prime attributes depending on its
250**whole** key (in every case there is only one non-composite or one designated key doing the
251determining, so 2NF holds trivially in each).
252
253**Dependency preservation.** FD1–FD17 is the canonical cover of `R_EDUBERZA`. Each FD's
254determinant and every one of its dependent attributes land inside exactly one of the ten new
255relations (see the "Source FDs" column above — no FD is split across two relations). The
256union of the FDs that hold on `R_USERS, …, R_WATCHLIST_ITEMS` is therefore exactly FD1–FD17
257again: nothing was lost.
258
259**Lossless join — chase test.**
260
261> *Note: the chase algorithm is not part of the course material. I was curious about a
262> stricter way to test lossless join than the usual "the common attributes are a key of one
263> side" argument, so I applied it here.*
264
265The chase decides whether a decomposition `R = R1 ∪ … ∪ Rn` is lossless under a set of
266functional dependencies. Build a tableau with one column per attribute of `R` and one row per
267relation `Ri`. In row `i`, put a distinguished symbol `a` in every column of `Ri` and a unique
268symbol `b_i` in every other column. Then repeat, until nothing changes: for each FD `X → Y`,
269whenever two rows agree on all of `X`, make them agree on `Y`. If they disagree, an `a` wins,
270otherwise one `b` replaces the other. **The decomposition is lossless exactly when some row
271ends up with `a` in every column.**
272
273All attributes of one cluster (`U_*`, `C_*`, `M_*`, …) always appear together, and FD1–FD17
274never mix clusters. So each cluster is one column group below: `a` means every column of the
275group holds a distinguished symbol, and `b` means none of them does. The foreign-key
276attributes (`H_USER_ID`, `O_MARKET_ID`, …) belong to their own cluster (`H_*`, `O_*`, …), not
277to the cluster they reference.
278
279**Step 1 — the ten relations from the table above.**
280
281```
282 U* C* M* H* O* T* MT* MC* W* WI*
283R_USERS a b b b b b b b b b
284R_CRYPTO b a b b b b b b b b
285R_MARKETS b b a b b b b b b b
286R_HOLDINGS b b b a b b b b b b
287R_ORDERS b b b b a b b b b b
288R_TRANSACTIONS b b b b b a b b b b
289R_MARKET_TR. b b b b b b a b b b
290R_MARKET_CA. b b b b b b b a b b
291R_WATCHLISTS b b b b b b b b a b
292R_WATCHLIST_I. b b b b b b b b b a
293```
294
295Every FD has its left side inside one cluster, for example `U_ID → U_*` or
296`H_USER_ID, H_CRYPTO_ID → H_ID`. For such an FD to fire, two rows would have to agree on that
297left side. But only one row has `a`s in that cluster, and the `b`s of different rows are
298all different, so no two rows ever agree on any left side. **The chase changes nothing, and
299no row becomes all `a`.** Under FD1–FD17 alone, the ten relations are *not* guaranteed to
300join back to `R_EDUBERZA`. This is not an accident of this model. It is exactly why
301Bernstein's synthesis algorithm has a final step: *if no synthesised relation contains a
302candidate key of `R`, add one that does.* None of the ten contains the ten-attribute key.
303
304**Step 2 — add the key relation** `R_KEY(U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID,
305W_ID, WI_ID)`. Its row has `a` only in the ten ID columns, written `a·` for "`a` in the ID,
306`b` in the rest of the group":
307
308```
309 U* C* M* H* O* T* MT* MC* W* WI*
310R_KEY a· a· a· a· a· a· a· a· a· a·
311(the ten rows of step 1 unchanged)
312```
313
314Now FD1 `U_ID → U_*` fires: row `R_KEY` and row `R_USERS` both have `a` in `U_ID`, so they
315must agree on the rest of `U_*`, and `R_USERS` has `a` there. `R_KEY` becomes `a` in the whole
316`U*` group. The same happens with FD4 (`C*`), FD6 (`M*`), FD8 (`H*`), FD10 (`O*`), FD11 (`T*`),
317FD12 (`MT*`), FD13 (`MC*`), FD15 (`W*`) and FD16 (`WI*`):
318
319```
320 U* C* M* H* O* T* MT* MC* W* WI*
321R_KEY a a a a a a a a a a <- all distinguished
322```
323
324**Row `R_KEY` is all `a`, so the decomposition into the ten relations plus `R_KEY` is
325lossless.**
326
327**Why `R_KEY` is not kept in the final schema.** An instance of `R_KEY` would only record
328which ID of one cluster appears together with which ID of every other cluster. As shown under
329*Candidate keys and primary key*, the ten clusters are independent record types, and
330`R_EDUBERZA` pairs every row of one with every row of the others. So `R_KEY` would be just the
331cross product of the ten ID sets and would carry no information. The same independence means
332the join dependency `⋈[R_USERS, …, R_WATCHLIST_ITEMS]` holds on `R_EDUBERZA` by construction.
333Under that dependency the ten relations alone already reconstruct it: their natural join, with
334no common attributes, is exactly that cross product. The chase makes this reasoning explicit.
335FDs by themselves cannot prove the join lossless; you need either the key relation or the
336independence of the clusters. That was hidden in the earlier "foreign key equals primary key"
337argument, which described the equi-joins the application runs, not the natural join the
338lossless-join property is about.
339
340## 3NF decomposition
341
342**Relations analyzed:** each of the ten relations produced above, individually.
343
344For each relation, 3NF asks whether any non-prime attribute is *transitively* dependent on a
345key — i.e. determined by another non-prime attribute rather than directly by the key. This is
346exactly where the foreign-key-carried dependencies from
347[Dependencies carried by foreign keys](#dependencies-carried-by-foreign-keys) have to be
348checked, because that table is precisely the list of "dependency that would cause a problem at
349the next higher normal form" the phase template asks for.
350
351**Worked example — `R_MARKETS`.** Its key `M_ID` determines `M_CRYPTO_ID`, and
352`M_CRYPTO_ID → C_SYMBOL, C_NAME, C_CREATED_AT` also holds (`M_CRYPTO_ID` draws its values from
353`C_ID`'s domain). If `C_SYMBOL`, `C_NAME` and `C_CREATED_AT` were still columns of
354`R_MARKETS`, this would be exactly the transitive dependency `M_ID → M_CRYPTO_ID → C_SYMBOL`
355that violates 3NF. They are not: the 2NF step above already put them in `R_CRYPTO`, keyed
356directly by `C_ID` (FD4), because FD4 — not the derived `M_CRYPTO_ID → C_SYMBOL` — is what the
357canonical cover actually contains. `R_MARKETS` itself has no attribute that determines another
358non-prime attribute of `R_MARKETS`; the transitive dependency is real, but it points *out* of
359the relation, not within it.
360
361The same reasoning applies to every other foreign key in the list: `H_USER_ID`/`H_CRYPTO_ID`,
362`O_USER_ID`/`O_MARKET_ID`, `T_USER_ID`/`T_RELATED_ORDER`, `MT_MARKET_ID`, `MC_MARKET_ID`,
363`W_USER_ID`, `WI_WATCHLIST_ID`/`WI_CRYPTO_ID` are all foreign keys sitting *alongside* a
364non-key attribute set that depends only on their own relation's key, never on the foreign key
365itself. None of `R_USERS`, `R_CRYPTO`, `R_HOLDINGS`, `R_ORDERS`, `R_TRANSACTIONS`,
366`R_MARKET_TRADES`, `R_MARKET_CANDLES`, `R_WATCHLISTS`, `R_WATCHLIST_ITEMS` has a non-prime
367attribute that another non-prime attribute of the *same* relation determines.
368
369**Conclusion:** synthesising directly from the canonical cover in the 2NF step already
370avoided every transitive dependency — there is nothing left to decompose for 3NF. All ten
371relations from the previous section satisfy 3NF unchanged.
372
373## BCNF if possible
374
375**Relations analyzed:** the same ten relations, checked against the stricter BCNF rule: every
376determinant of every functional dependency that holds on the relation must be a candidate key
377of that relation (3NF allows an exception when the dependent side is prime; BCNF does not).
378
379| Relation | Functional dependencies in force | Determinant | Is it a candidate key? |
380|---|---|---|---|
381| `R_USERS` | FD1, FD2, FD3 | `U_ID`, `U_USERNAME`, `U_EMAIL` | Yes — all three are candidate keys |
382| `R_CRYPTO` | FD4, FD5 | `C_ID`, `C_SYMBOL` | Yes — both candidate keys |
383| `R_MARKETS` | FD6, FD7 | `M_ID`, `{M_CRYPTO_ID, M_QUOTE_CURRENCY}` | Yes — both candidate keys |
384| `R_HOLDINGS` | FD8, FD9 | `H_ID`, `{H_USER_ID, H_CRYPTO_ID}` | Yes — both candidate keys |
385| `R_ORDERS` | FD10 | `O_ID` | Yes — the only candidate key |
386| `R_TRANSACTIONS` | FD11 | `T_ID` | Yes — the only candidate key |
387| `R_MARKET_TRADES` | FD12 | `MT_ID` | Yes — the only candidate key |
388| `R_MARKET_CANDLES` | FD13, FD14 | `MC_ID`, `{MC_MARKET_ID, MC_TIMEFRAME, MC_CANDLE_TIME}` | Yes — both candidate keys |
389| `R_WATCHLISTS` | FD15 | `W_ID` | Yes — the only candidate key |
390| `R_WATCHLIST_ITEMS` | FD16, FD17 | `WI_ID`, `{WI_WATCHLIST_ID, WI_CRYPTO_ID}` | Yes — both candidate keys |
391
392Every determinant in every relation is one of that relation's own candidate keys. **All ten
393relations are already in BCNF** — the highest of the four normal forms this phase asks for,
394reached in the same step that fixed 2NF. This is not a coincidence: it happens because the
395canonical cover already grouped each relation's own key directly against its own attributes
396with no attribute appearing on the right side of two different relations' dependencies, which
397is exactly what synthesis from a canonical cover guarantees when, as here, none of the
398per-cluster functional dependencies overlap.
399
400No further decomposition is possible or necessary; splitting any of the ten relations further
401would only separate attributes that already depend on the *whole* key of a BCNF relation,
402which cannot fix anything and only costs a join.
403
404## Final result and discussion
405
406### Normalized relational model
407
408```
409R_USERS (U_ID, U_USERNAME, U_EMAIL, U_FULL_NAME, U_PASSWORD_HASH,
410 U_AVAILABLE_BALANCE, U_INVESTED_BALANCE, U_CREATED_AT, U_UPDATED_AT)
411R_CRYPTO (C_ID, C_SYMBOL, C_NAME, C_CREATED_AT)
412R_MARKETS (M_ID, M_CRYPTO_ID → R_CRYPTO, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT)
413R_HOLDINGS (H_ID, H_USER_ID → R_USERS, H_CRYPTO_ID → R_CRYPTO, H_QUANTITY,
414 H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT)
415R_ORDERS (O_ID, O_USER_ID → R_USERS, O_MARKET_ID → R_MARKETS, O_SIDE, O_TYPE,
416 O_STATUS, O_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT)
417R_TRANSACTIONS (T_ID, T_USER_ID → R_USERS, T_TYPE, T_AMOUNT, T_CURRENCY,
418 T_RELATED_ORDER → R_ORDERS, T_CREATED_AT, T_DESCRIPTION)
419R_MARKET_TRADES (MT_ID, MT_MARKET_ID → R_MARKETS, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY,
420 MT_SIDE, MT_SOURCE)
421R_MARKET_CANDLES (MC_ID, MC_MARKET_ID → R_MARKETS, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW,
422 MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME)
423R_WATCHLISTS (W_ID, W_USER_ID → R_USERS, W_NAME, W_CREATED_AT)
424R_WATCHLIST_ITEMS(WI_ID, WI_WATCHLIST_ID → R_WATCHLISTS, WI_CRYPTO_ID → R_CRYPTO, WI_ADDED_AT)
425```
426
427Ten relations, every one in BCNF, connected by the eleven foreign keys spelled out above.
428
429### Discussion
430
431**This is the P2 design.** Strip the `U_`/`C_`/`M_`/… prefixes back to plain column names and
432`R_USERS, R_CRYPTO, R_MARKETS, R_HOLDINGS, R_ORDERS, R_TRANSACTIONS, R_MARKET_TRADES,
433R_MARKET_CANDLES, R_WATCHLISTS, R_WATCHLIST_ITEMS` are, attribute for attribute and key for
434key, `users, crypto, markets, holdings, orders, transactions, market_trades, market_candles,
435watchlists, watchlist_items` from
436[RelationalDesign](../P2-RelationalDesign/RelationalDesign.md). Every foreign key matches,
437every candidate key matches (including the less obvious composite ones — `{user_id,
438crypto_id}` on `holdings`, `{crypto_id, quote_currency}` on `markets`, `{market_id, timeframe,
439candle_time}` on `market_candles`), and the normal form matches (P2 already claimed 3NF; this
440phase shows the stronger result that the design is actually in BCNF).
441
442That is not a coincidence of two people happening to agree — it is what should happen when a
443design is derived correctly twice by two different methods from the same underlying model:
444P2 got here by applying the standard ER-to-relational transformation rules (each entity
445becomes a table on its own key, each attributed M:N relationship becomes a table on the
446combined key, each attributeless 1:N relationship becomes a foreign key on the "many" side).
447This phase got here by ignoring that transformation entirely, writing down only the
448attributes and the functional dependencies they obey, and mechanically applying 2NF/3NF/BCNF
449synthesis. Landing on the same ten relations either means the P2 transformation rules are
450sound for this particular model (which they are, for exactly the reason [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md#normalisation)
451already argued: single-column UUID primary keys everywhere rule out partial dependencies by
452construction, and no non-key attribute references another non-key attribute anywhere in the
453model, which rules out transitive dependencies too), or it is a coincidence spanning ten
454independently-checked relations and dozens of functional dependencies — the first explanation
455is the only credible one.
456
457**The one substantive difference** is `holdings.avg_price`, which P2 documents as a
458*derived* attribute — the running weighted-average buy price, recomputable from the `buy` rows
459in `transactions` — kept as a stored column anyway for read performance
460([RelationalDesign](../P2-RelationalDesign/RelationalDesign.md#normalisation) calls this out
461explicitly as an accepted denormalisation). Nothing in this phase's functional-dependency
462analysis can see that `H_AVG_PRICE` is derivable from `T_*` rows rather than stored
463independently — FD8 (`H_ID → H_AVG_PRICE`) is a perfectly ordinary functional dependency
464either way, because *derivability from a different relation's rows* is a property of the data
465and the application logic that maintains it (see
466[UseCase0004](../P3-UseCaseModel/UseCase0004.md)'s `ON CONFLICT … DO UPDATE`), not something
467that shows up as a violation of any single-relation normal form. Formal normalization and "no
468column is a cached computation of other columns" are related but different concerns; this
469phase only checked the first one.
470
471**Which design is used going forward:** P2's, unchanged. Since the two designs coincide
472exactly, "restructuring the database objects" means confirming there is nothing to change
473rather than writing new DDL. [`server/db/schema_creation.sql`](../../server/db/schema_creation.sql)
474already matches `R_USERS`…`R_WATCHLIST_ITEMS` column-for-column (including
475`holdings.reserved_quantity`, added between P2 and this phase — see
476[RelationalDesignAIUsage](../P2-RelationalDesign/RelationalDesignAIUsage.md#session-3--2026-09-16)
477— which is `H_RESERVED_QUANTITY` above, correctly grouped under `R_HOLDINGS`'s key alongside
478`H_QUANTITY` and not treated as needing a relation of its own). P4's prototype
479(`server/trade.go`, `server/portfolio.go`) keeps working against the same schema without
480change. [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md) has been updated with a
481short note pointing here as the formal validation of its normal-form claim.
Note: See TracBrowser for help on using the repository browser.