Changeset 1549dae for docs/P5-Normalization/Normalization.md
- Timestamp:
- 09/29/26 20:55:13 (14 hours ago)
- Branches:
- main
- Parents:
- 0cee8ec
- File:
-
- 1 edited
-
docs/P5-Normalization/Normalization.md (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
docs/P5-Normalization/Normalization.md
r0cee8ec r1549dae 1 1 # Normalization 2 2 3 This phase deliberately ignores the design from [ERModel](../P1-ConceptualModel/ERModel.md) 4 (P1) and [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md) (P2) as a starting 5 point. Instead it starts over from a single flat relation containing every attribute of the 6 model, derives the functional dependencies that hold on it, and decomposes it formally, 7 step by step. The 8 [final section](#final-result-and-discussion) compares what falls out of that process with 9 the P2 design. 3 This phase does not use the relations of 4 [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md) (P2) as a starting point. 5 It starts from the attributes of [ERModel](../P1-ConceptualModel/ERModel.md) **v05** (P1), 6 put into one de-normalized relation. It states the functional dependencies that the 7 model's rules impose on those attributes, **computes** the keys of that relation from the 8 dependencies, and then decomposes it step by step through 2NF, 3NF and BCNF. Every step is 9 checked for a lossless join and for dependency preservation. The 10 [final section](#final-result-and-discussion) compares the result with P2. 10 11 11 12 ## De-normalized database form 12 13 13 ### Building one relation out of the whole model 14 15 The 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 18 relationships `Holds` and `Contains`. Eight more relationships (`QuotedOn`, `PlacedOn`, 19 `Places`, `Records`, `Settles`, `Fills`, `Aggregates`, `Owns`) carry no attributes of their 20 own — in Chen notation they need none, because the diagram expresses the link itself as a 21 relationship, not a column. A single flat relation has no such device: the only way to keep 22 one entity's rows pointed at another's is a plain attribute holding the referenced key, 23 which is exactly what P2's ER-to-relational transformation already introduces for each of 24 those 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 27 below for that reason — not because they were copied from P2's design, but because a "single 28 table with everything in it" cannot represent the model at all without them. 29 30 Every attribute name is prefixed by a two-or-three-letter code for the entity/relationship it 31 came 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 33 not contain duplicate names. 34 35 | Prefix | Origin (P1 entity / relationship) | Attributes | 14 ### Which attributes go into the relation 15 16 The relation contains **the attributes of the ER model and nothing else**. In v05 all 17 attributes belong to the 11 entity sets. None of the 15 relationships has attributes of its 18 own. 19 20 A relationship adds **no column**. Foreign-key columns such as `crypto_id` or `watchlist_id` 21 belong to the relational model of P2, not to the ER model, so they do not appear here. What a 22 relationship contributes is a **functional dependency** between attributes that are already 23 in the relation. For example, `Contains` (Watchlists 1 : N WatchlistItems) says that every 24 watchlist item is on exactly one watchlist, which is the dependency `WI_ID → W_ID` in the 25 next section. It is not a column `WI_WATCHLIST_ID`. 26 27 Attribute names are prefixed with the entity set they come from, because several names repeat 28 across the model (`id`, `created_at`, `quantity`, `type`, `name`, `price`, `side`), and one 29 relation cannot contain the same name twice. 30 31 | Prefix | Entity set (P1) | Attributes | 36 32 |---|---|---| 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 49 relationships with their own attributes, and giving each its own surrogate key (rather than 50 relying solely on the `{user,crypto}` / `{watchlist,crypto}` pair) is the same design choice 51 already justified in [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md#descriptive-representation-of-the-relational-schema). 52 53 This gives **one relation, `R_EDUBERZA`, of 68 attributes:** 33 | `U_` | Users | `U_ID, U_USERNAME, U_EMAIL, U_FULL_NAME, U_PASSWORD_HASH, U_AVAILABLE_BALANCE, U_INVESTED_BALANCE, U_RESERVED_BALANCE, U_CREATED_AT, U_UPDATED_AT` | 34 | `C_` | Cryptos | `C_ID, C_SYMBOL, C_NAME, C_CREATED_AT` | 35 | `M_` | Markets | `M_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` | 36 | `H_` | Holdings | `H_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT` | 37 | `O_` | Orders | `O_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_FILLED_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT` | 38 | `T_` | Transactions | `T_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_CREATED_AT, T_DESCRIPTION` | 39 | `MT_` | MarketTrades | `MT_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` | 40 | `OE_` | OrderEvents | `OE_ID, OE_EVENT_TYPE, OE_QUANTITY, OE_PRICE, OE_STATUS_AFTER, OE_CREATED_AT` | 41 | `MC_` | MarketCandles | `MC_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` | 42 | `W_` | Watchlists | `W_ID, W_NAME, W_CREATED_AT` | 43 | `WI_` | WatchlistItems | `WI_ID, WI_ADDED_AT` | 44 45 That is 64 attributes. **One case needs two more.** `FillsBuy` and `FillsSell` are two 46 different relationships between the same two entity sets, Orders and MarketTrades. A trade 47 can fill one buy order *and* one sell order, which are two different orders. One relation 48 has only one `O_ID` column, and one column cannot hold two different orders in the same 49 tuple. So the order's identifier appears once per **role**, named after the relationship 50 that gives the role: 51 52 | Attribute | Meaning | 53 |---|---| 54 | `O_ID_FILLSBUY` | the `id` of Orders, in its role in `FillsBuy` (the buy order a trade filled) | 55 | `O_ID_FILLSSELL` | the `id` of Orders, in its role in `FillsSell` (the sell order a trade filled) | 56 57 These are not foreign keys copied from P2. They are the ER attribute `Orders.id` itself, once 58 for each of the two relationships. [ERModel](../P1-ConceptualModel/ERModel.md) names these two 59 roles of `Orders` explicitly: *the buy order* of a trade in `FillsBuy`, and *the sell order* in 60 `FillsSell`. This is the only place where the model has two 61 relationships between the same pair of entity sets. Every other relationship is expressed with 62 the attributes above, without renaming. 63 64 This gives **one relation, `R_EDUBERZA`, of 66 attributes:** 54 65 55 66 ``` 56 67 R_EDUBERZA( 57 68 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,69 U_INVESTED_BALANCE, U_RESERVED_BALANCE, U_CREATED_AT, U_UPDATED_AT, 59 70 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, 71 M_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT, 72 H_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT, 73 O_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_FILLED_QUANTITY, O_PRICE, 64 74 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_AT75 T_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_CREATED_AT, T_DESCRIPTION, 76 MT_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE, 77 O_ID_FILLSBUY, O_ID_FILLSSELL, 78 OE_ID, OE_EVENT_TYPE, OE_QUANTITY, OE_PRICE, OE_STATUS_AFTER, OE_CREATED_AT, 79 MC_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME, 80 W_ID, W_NAME, W_CREATED_AT, 81 WI_ID, WI_ADDED_AT 72 82 ) 73 83 ``` 74 84 85 To keep the tables below readable, **`X_*`** means the non-identifier attributes of prefix 86 `X_`. For example, `U_*` = `U_USERNAME … U_UPDATED_AT` (9 attributes), and `O_*` = 87 `O_SIDE … O_EXECUTED_AT` (8 attributes). `U_ID`, `O_ID`, … are always written out. 88 75 89 Every attribute is single-valued and atomic (a balance, a timestamp, a symbol, an amount — 76 90 nothing here is a list or a nested record), so `R_EDUBERZA` satisfies 1NF as soon as it is 77 written down. Whether it satisfies anything beyond that is exactly what the rest of this page 91 written down. 92 93 ## Functional dependencies 94 95 At this point `R_EDUBERZA` is just a set of attributes. It has **no keys yet**. `U_ID`, 96 `O_ID`, … are ordinary attributes of this relation, and which attribute sets are keys of 97 `R_EDUBERZA` is computed in the [next section](#candidate-keys-and-primary-key), from the 98 dependencies below. Each dependency is justified by a rule of the domain, as described in 99 the data requirements of [ERModel](../P1-ConceptualModel/ERModel.md). The rules are of four 100 kinds: 101 102 - **(I) Identification.** Every value of an identifier (`U_ID`, `C_ID`, …) is given to 103 exactly one real object: one user, one crypto, one order. That object has exactly one 104 username, one balance, one price, and so on. So the identifier's value fixes those values. 105 - **(R) 1:N relationship.** In a 1:N relationship, each object on the N side is linked to 106 exactly one object on the 1 side. So the N side's identifier fixes the 1 side's 107 identifier. Example: an order is placed by exactly one user (`Places`), so `O_ID → U_ID`. 108 The opposite direction does not hold: a user places many orders, so `U_ID ↛ O_ID`. 109 - **(U) Uniqueness rule.** A rule of the form "at most one X per Y and Z" gives 110 `Y, Z → X`. 111 - **(N) Unique natural attribute.** No two users share a username or an email, and no two 112 cryptos share a symbol. 113 114 **Only rules of the ER model are used.** The dependencies below come from the rules stated in 115 [ERModel](../P1-ConceptualModel/ERModel.md) v05 and nothing else. The analysis uses the 116 classical definitions (Armstrong's axioms), with no special treatment of `NULL`. Partial 117 relationships (`Settles`, `FillsBuy`, `FillsSell`) are discussed where they matter: 118 under [Canonical cover](#canonical-cover) and in the [discussion](#discussion). 119 120 | # | Functional dependency | Rule | Why it holds | 121 |---|---|---|---| 122 | FD1 | `U_ID → U_USERNAME, U_EMAIL, U_FULL_NAME, U_PASSWORD_HASH, U_AVAILABLE_BALANCE, U_INVESTED_BALANCE, U_RESERVED_BALANCE, U_CREATED_AT, U_UPDATED_AT` | I | one user, one value of each | 123 | FD2 | `U_USERNAME → U_ID` | N | usernames are unique | 124 | FD3 | `U_EMAIL → U_ID` | N | emails are unique | 125 | FD4 | `C_ID → C_SYMBOL, C_NAME, C_CREATED_AT` | I | one crypto, one value of each | 126 | FD5 | `C_SYMBOL → C_ID` | N | symbols are unique | 127 | FD6 | `M_ID → M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT, C_ID` | I, R | …and a market is `QuotedOn` exactly one crypto | 128 | FD7 | `C_ID, M_QUOTE_CURRENCY → M_ID` | U | a crypto is quoted at most once per currency | 129 | FD8 | `H_ID → H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT, U_ID, C_ID` | I, R | …and a holding belongs to one user (`Holds`) and is a position in one crypto (`PositionIn`) | 130 | FD9 | `U_ID, C_ID → H_ID` | U | at most one holding per user and crypto | 131 | FD10 | `O_ID → O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_FILLED_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT, U_ID, M_ID` | I, R | …and an order is placed by one user (`Places`) on one market (`PlacedOn`) | 132 | FD11 | `T_ID → T_TYPE, T_AMOUNT, T_CURRENCY, T_CREATED_AT, T_DESCRIPTION, U_ID, O_ID` | I, R | …and a ledger entry belongs to one user (`Records`) and to at most one order (`Settles`) | 133 | FD12 | `MT_ID → MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE, M_ID, O_ID_FILLSBUY, O_ID_FILLSSELL` | I, R | …and a trade happened on one market (`Fills`) and filled at most one buy order (`FillsBuy`) and at most one sell order (`FillsSell`) | 134 | FD13 | `OE_ID → OE_EVENT_TYPE, OE_QUANTITY, OE_PRICE, OE_STATUS_AFTER, OE_CREATED_AT, O_ID` | I, R | …and an event belongs to one order (`Logs`) | 135 | FD14 | `MC_ID → MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME, M_ID` | I, R | …and a candle summarises one market (`Aggregates`) | 136 | FD15 | `M_ID, MC_TIMEFRAME, MC_CANDLE_TIME → MC_ID` | U | one candle per market, timeframe and bucket | 137 | FD16 | `W_ID → W_NAME, W_CREATED_AT, U_ID` | I, R | …and a watchlist is owned by one user (`Owns`) | 138 | FD17 | `WI_ID → WI_ADDED_AT, W_ID, C_ID` | I, R | …and an item is on one watchlist (`Contains`) and names one crypto (`Lists`) | 139 | FD18 | `W_ID, C_ID → WI_ID` | U | an asset appears at most once per watchlist | 140 141 **Dependencies that do *not* hold** are as important, because they are why some attributes 142 must be combined in the key later: 143 144 - The reverse of every (R) dependency, e.g. `U_ID ↛ O_ID`, `M_ID ↛ MT_ID`, `W_ID ↛ WI_ID`. 145 These are 1:N, not 1:1. 146 - `M_ID, MT_EXECUTED_AT ↛ MT_ID`. Two trades on a market can share a timestamp. 147 - `U_ID, W_NAME ↛ W_ID`. The model does not require list names to be unique per user. 148 - `O_ID_FILLSBUY` and `O_ID_FILLSSELL` determine no other attribute of `R_EDUBERZA` **by any 149 rule of the ER model**. The order data (`O_SIDE`, `O_PRICE`, …) describes the order in the 150 `O_ID` column, not the order in a role column. (The database also has a rule that a trade 151 and the orders it fills are on the same market. That rule is a trigger in P7 relating 152 several entity sets, not a rule of the ER model, so it is not used here.) 153 154 ### Canonical cover 155 156 A canonical (minimal) cover is obtained in three steps. 157 158 **Step 1 — single attribute on the right.** Each FD above is read as one dependency per 159 right-side attribute, e.g. FD6 is `M_ID → M_QUOTE_CURRENCY`, `M_ID → M_IS_ACTIVE`, 160 `M_ID → M_CREATED_AT`, `M_ID → C_ID`. 161 162 **Step 2 — no extraneous attribute on the left.** Only FD7, FD9, FD15 and FD18 have more than one 163 attribute on the left. For each one, dropping any attribute makes the rule false: 164 165 | FD | Drop | Counter-example (the smaller left side does not determine the right side) | 166 |---|---|---| 167 | FD7 | `M_QUOTE_CURRENCY` | BTC is quoted in USD *and* in EUR: one `C_ID`, two markets | 168 | | `C_ID` | USD is the quote currency of many markets | 169 | FD9 | `C_ID` | one user holds several cryptos | 170 | | `U_ID` | one crypto is held by several users | 171 | FD15 | `M_ID` | every market has a `1h` candle starting at 10:00 | 172 | | `MC_TIMEFRAME` | a market has a `1m` and a `1h` candle both starting at 10:00 | 173 | | `MC_CANDLE_TIME` | a market has many `1h` candles | 174 | FD18 | `C_ID` | a watchlist has several items | 175 | | `W_ID` | a crypto is on several watchlists | 176 177 **Step 3 — no redundant dependency.** A dependency is redundant if it follows from the others. For 178 almost every dependency, its right-side attribute appears on the right of no other 179 dependency with a different left side (e.g. nothing but `U_ID` determines 180 `U_AVAILABLE_BALANCE`), so it cannot be derived. The candidates worth checking are the 181 identifiers that are reached from several places: 182 183 - **`T_ID → U_ID` is redundant.** It follows by transitivity from `T_ID → O_ID` (FD11) and 184 `O_ID → U_ID` (FD10): a ledger entry's user is the user of the order it settles. It is 185 therefore **removed** from FD11. The derivation is valid only for an entry that has an 186 order. Every tuple of `R_EDUBERZA` does have one (see the 187 [discussion](#discussion)), so in the de-normalized relation the removal is correct. The 188 consequence for deposits, which have no order, is taken up in the discussion. 189 - `H_ID → U_ID`, `H_ID → C_ID`, `WI_ID → W_ID`, `WI_ID → C_ID`, `M_ID → C_ID`, `MT_ID → M_ID`, 190 `MC_ID → M_ID`, `OE_ID → O_ID`, `W_ID → U_ID` and `O_ID → U_ID`, `O_ID → M_ID`: for 191 each, no other dependency with a different left side has that attribute on its right 192 side and a left side reachable from this one, so none can be derived. 193 - The four (U) and three (N) dependencies go "backwards" from a non-identifier to an 194 identifier. Nothing else produces an identifier from those attributes, so they are not 195 derivable either. 196 197 Grouping the single-attribute dependencies back by left side gives FD1–FD18 as listed, 198 except that FD11 loses `U_ID`: 199 200 | # | Functional dependency (canonical cover) | 201 |---|---| 202 | FD11 | `T_ID → T_TYPE, T_AMOUNT, T_CURRENCY, T_CREATED_AT, T_DESCRIPTION, O_ID` | 203 204 **FD1–FD18, with this FD11, is the canonical cover.** From here on, "FD11" means this reduced 205 form. 206 207 ## Candidate keys and primary key 208 209 A candidate key is a minimal set of attributes whose closure under FD1–FD18 is all 66 210 attributes. 211 212 **Attributes that must be in every key.** `T_ID`, `OE_ID` and `MT_ID` appear on the right side 213 of no dependency. Nothing determines them, so every key must contain them. 214 215 **Closure of `{T_ID, OE_ID, MT_ID}`:** 216 217 | Step | Added | Using | 218 |---|---|---| 219 | start | `T_ID, OE_ID, MT_ID` | — | 220 | 1 | `T_*`, `O_ID` | FD11 | 221 | 2 | `OE_*` | FD13 | 222 | 3 | `MT_*`, `M_ID`, `O_ID_FILLSBUY`, `O_ID_FILLSSELL` | FD12 | 223 | 4 | `O_*`, `U_ID` | FD10 | 224 | 5 | `U_*` | FD1 | 225 | 6 | `M_*`, `C_ID` | FD6 | 226 | 7 | `C_*` | FD4 | 227 | 8 | `H_ID` | FD9 (`U_ID` and `C_ID` are both present) | 228 | 9 | `H_*` | FD8 | 229 230 That is 53 attributes. Still missing are all 8 `MC_` attributes, the 3 `W_` attributes and 231 the 2 `WI_` attributes: 232 233 - **`MC_`:** only `MC_ID` determines them (FD14), and `MC_ID` is reached only by FD15, which 234 needs `M_ID` (already present), `MC_TIMEFRAME` and `MC_CANDLE_TIME`. So the key must add 235 either `MC_ID` or both `MC_TIMEFRAME` and `MC_CANDLE_TIME`. Neither of those two alone is 236 enough. 237 - **`W_` and `WI_`:** `WI_ID` gives `W_ID` (FD17), and `W_ID` gives `WI_ID` together with 238 `C_ID`, which is already present (FD18). So adding either `WI_ID` or `W_ID` gives all five. 239 240 **Candidate keys** (each one's closure is all 66 attributes, and removing any member breaks 241 that, by the argument above): 242 243 | Key | Attributes | 244 |---|---| 245 | **K1** | `T_ID, OE_ID, MT_ID, MC_ID, WI_ID` | 246 | K2 | `T_ID, OE_ID, MT_ID, MC_ID, W_ID` | 247 | K3 | `T_ID, OE_ID, MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME, WI_ID` | 248 | K4 | `T_ID, OE_ID, MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME, W_ID` | 249 250 **Primary key: K1.** It consists only of identifiers, and it is the key that remains at the 251 end of the decomposition below. 252 253 **Prime attributes** (in at least one candidate key): `T_ID, OE_ID, MT_ID, MC_ID, 254 MC_TIMEFRAME, MC_CANDLE_TIME, W_ID, WI_ID`. The other 58 attributes are **non-prime**. The 255 difference matters: 2NF and 3NF only restrict dependencies of non-prime attributes, and BCNF 256 restricts all of them. 257 258 In words, a tuple of `R_EDUBERZA` puts together one ledger entry, one order event, one 259 trade, one candle and one watchlist item. Everything else in the tuple (the user, the order, 260 the market, the crypto, the holding, the watchlist) follows from those five. 261 262 **Normal form of `R_EDUBERZA`:** 1NF only. It is not in 2NF, because, for example, `T_AMOUNT` 263 depends on `T_ID` alone, a proper part of K1. 264 265 ## 1NF decomposition 266 267 No decomposition is needed. Every attribute of `R_EDUBERZA` is atomic and single-valued, and 268 the relation has no repeating groups (see 269 [De-normalized database form](#de-normalized-database-form)). 270 271 ## 2NF decomposition 272 273 ### How every step is described and checked 274 275 Each step of 2NF, 3NF and BCNF below lists, in this order: the relation analyzed, its 276 dependencies, its candidate keys and primary key, and its normal form; the dependency that 277 violates the next normal form and is used for the split; the two resulting relations, each 278 with its dependencies, keys and normal form; and the dependency-preservation and lossless-join 78 279 checks. 79 280 80 ## Functional dependencies 81 82 ### Canonical cover 83 84 Read directly off the model: each entity's/relationship's own key determines its own 85 attributes, nothing more. This is already minimal — no functional dependency below has an 86 extraneous attribute on its left side, and no dependent attribute is repeated on the right 87 side of more than one dependency, which is what "canonical cover" requires. 88 89 | # | Functional dependency | Source | 281 Every step splits one relation `R` into two: the **extracted** relation `Ri` and the 282 **residual** relation `R'` (what is left of `R`). The same two checks are made each time: 283 284 - **Lossless join.** The split of `R` into `Ri` and `R'` is lossless if the common attributes 285 determine one of the two sides: `(Ri ∩ R') → Ri` or `(Ri ∩ R') → R'`. Every step below 286 extracts `Ri = X ∪ (what X determines)` for some determinant `X` that stays in `R'`. So 287 `X ⊆ Ri ∩ R'` and `X → Ri`, and the first condition holds. 288 - **Dependency preservation.** Every dependency of the canonical cover must end up with all 289 its attributes inside one relation. So an attribute is removed from the residual only when 290 no dependency still waiting in the residual needs it. Otherwise it is extracted **and** 291 kept. 292 293 **Relation analyzed first:** `R_EDUBERZA` (66 attributes), dependencies FD1–FD18, candidate 294 keys K1–K4, primary key K1. **Normal form:** 1NF. 295 296 **Dependencies that violate 2NF.** 2NF forbids a non-prime attribute from depending on a proper 297 part of a candidate key. There are six such partial dependencies: 298 299 | Part of a key | Non-prime attributes that depend on it | Through | 90 300 |---|---|---| 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 111 different quote currencies (that is the entire point of the market entity), so two rows can 112 share `M_CRYPTO_ID` and disagree on `M_ID`. `M_QUOTE_CURRENCY` alone fails the same way in the 113 other direction. Neither attribute is extraneous, so the left side of FD7 cannot shrink. The 114 same 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 117 holds 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 120 other dependency in the set — for instance, nothing outside FD1 mentions `U_AVAILABLE_BALANCE`, 121 so 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 125 Six 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 128 domain as some other attribute's key. Because of that, every dependency that holds on the 129 referenced 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 146 None of these is added to the canonical cover — each is *derivable* from FD1–FD17 by 147 transitivity plus the foreign-key identity, which is exactly why a canonical cover excludes 148 them. They matter anyway: they are precisely the transitive dependencies the 3NF check below 149 has 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 155 order's id says anything about which market-candle row, or which unrelated transaction, or 156 which watchlist item is in the same tuple of `R_EDUBERZA` — a user can exist with zero of any 157 of them, and having one order says nothing about how many holdings, trades or candles exist 158 alongside it. (The one FK that crosses between two of these — `T_RELATED_ORDER` — is 159 nullable, so it cannot be relied on to always connect a transaction row back to an order.) 160 That 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 163 identifying 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 187 The closure now contains all 68 attributes, so the set is a superkey; removing any one of its 188 ten 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 190 key. 191 192 **It is not the only one.** Any attribute that is itself a determinant of a whole cluster can 193 stand in for that cluster's id — `U_USERNAME` or `U_EMAIL` for `U_ID` (FD2/FD3), `C_SYMBOL` 194 for `C_ID` (FD5), `{M_CRYPTO_ID, M_QUOTE_CURRENCY}` for `M_ID` (FD7), `{H_USER_ID, 195 H_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 × 197 1 × 2 × 1 × 2 = 96 candidate keys in total. The all-surrogate-id combination above is chosen 198 as **primary key** for the same reason `id` was chosen over `username`/`email`/`symbol`/etc. 199 per entity in [ERModel](../P1-ConceptualModel/ERModel.md): it is opaque, and none of its parts 200 are things a user would ever legitimately change. 201 202 **Normal form of `R_EDUBERZA` before decomposition:** 1NF only, and barely that — see 2NF 203 below. It cannot be in 2NF, 3NF or BCNF, since each of those requires 2NF as a precondition. 204 205 ## 1NF decomposition 206 207 No decomposition happens at this step. 1NF requires atomic, single-valued attributes and no 208 repeating groups; `R_EDUBERZA` was built that way from the start (every column above is a 209 single 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 216 in 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 221 key. Every single functional dependency in the canonical cover (FD1–FD17) has a left side 222 that is a **proper subset** of the ten-attribute primary key — `U_ID` alone, `C_ID` alone, …, 223 down to the two-attribute `{WI_WATCHLIST_ID, WI_CRYPTO_ID}`. There is no non-prime attribute 224 in `R_EDUBERZA` that depends on the whole ten-attribute key and nothing smaller. In other 225 words, *every* non-prime attribute violates 2NF at once — the violation is not a handful of 226 stray columns to peel off, it is the entire relation, because gluing ten independent record 227 types together under one artificial composite key was never going to satisfy 2NF to begin 228 with. 229 230 **Decomposition.** This uses 3NF/BCNF **synthesis** (Bernstein's algorithm) rather than the 231 binary decomposition algorithm: since the canonical cover is already in hand (as the phase 232 instructions recommend building first), synthesis creates one relation per left-hand side in 233 the cover directly, instead of hunting for one offending dependency at a time and splitting 234 in two repeatedly. Grouping FD1–FD17 by determinant produces ten relations: 235 236 | New relation | Attributes | Key(s) | Source FDs | 301 | `T_ID` (K1–K4) | `T_*`, `O_ID`, and through them `O_*`, `U_ID`, `U_*`, `M_ID`, `M_*`, `C_ID`, `C_*`, `H_ID`, `H_*` | FD11, then FD10, FD1, FD6, FD4, FD9, FD8 | 302 | `OE_ID` (K1–K4) | `OE_*`, `O_ID` | FD13 | 303 | `MT_ID` (K1–K4) | `MT_*`, `M_ID`, `O_ID_FILLSBUY`, `O_ID_FILLSSELL` | FD12 | 304 | `MC_ID` (K1, K2) | `MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME`, `M_ID` | FD14 | 305 | `W_ID` (K2, K4) | `W_*`, `U_ID` | FD16 | 306 | `WI_ID` (K1, K3) | `WI_ADDED_AT`, `C_ID` | FD17 | 307 308 The table lists the part of a key that each group depends on most directly. It is not the 309 only one: under K3/K4, for example, `MC_OPEN … MC_VOLUME` also depend on 310 `{MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME}`, and under K1/K3 `W_*` depend on `WI_ID` through 311 `W_ID`. These lead to the same relations, so they need no extra steps. `MC_TIMEFRAME`, 312 `MC_CANDLE_TIME` and `W_ID` also depend on parts of keys, but they are prime, so 2NF does not 313 restrict them. They are handled under BCNF. 314 315 Each step below removes one row of this table, splitting the current relation into two. The 316 **order** is chosen so that no dependency is lost. `T_ID` goes first, because its group is the 317 largest and carries FD1–FD11 with it. Each later step handles a group whose determinant is 318 still in the residual relation. 319 320 ### Step 2NF-1 — partial dependency on `T_ID` 321 322 - **Relation analyzed:** `R_EDUBERZA` (66 attributes). 323 - **Dependencies:** FD1–FD18. **Candidate keys:** K1–K4. **Primary key:** K1. 324 **Normal form:** 1NF. 325 - **2NF violations:** all six rows of the table above. **Split first on `T_ID`**, the 326 largest group (see the order explained above). 327 - **Decomposition dependency:** `T_ID → T_*, O_ID` (FD11), together with everything it 328 determines transitively (FD10, FD1, FD6, FD4, FD9, FD8). `T_ID` is a proper part of K1, and 329 `T_AMOUNT`, for example, is non-prime, so this violates 2NF. 330 - **New relation `R_A`** = `{ T_ID, T_*, O_ID, O_*, U_ID, U_*, M_ID, M_*, C_ID, C_*, H_ID, H_* }` 331 (39 attributes). Dependencies: FD1–FD11. Candidate key and primary key: `T_ID`. Normal form: 2NF (it has a 332 one-attribute key), but not 3NF (see 3NF). 333 - **Residual relation `S1`** = `R_EDUBERZA − { T_*, O_*, U_*, M_*, C_*, H_ID, H_* }` = 334 `{ T_ID, O_ID, U_ID, M_ID, C_ID, OE_ID, OE_*, MT_ID, MT_*, O_ID_FILLSBUY, O_ID_FILLSSELL, 335 MC_ID, MC_*, W_ID, W_*, WI_ID, WI_ADDED_AT }` (32 attributes). `O_ID`, `U_ID`, `M_ID` and 336 `C_ID` stay, because FD13, FD16, FD12/FD14/FD15 and FD17/FD18 still need them. Dependencies: FD12–FD18, plus the projected dependencies between the identifiers kept here: 337 `T_ID → O_ID, U_ID, M_ID, C_ID`, `O_ID → U_ID, M_ID, C_ID`, `M_ID → C_ID`, 338 `OE_ID → U_ID, M_ID, C_ID`, `MT_ID → C_ID`, `MC_ID → C_ID`, `WI_ID → U_ID`. 339 Candidate keys: K1–K4 (all 340 their attributes are still here). Normal form: 1NF. 341 - **Dependency preservation:** FD1–FD11 lie entirely in `R_A`, and FD12–FD18 entirely in `S1`. ✓ 342 - **Lossless join:** `R_A ∩ S1 = { T_ID, O_ID, U_ID, M_ID, C_ID }` contains `T_ID`, and 343 `T_ID → R_A`, so `(R_A ∩ S1) → R_A`. ✓ 344 345 ### Step 2NF-2 — partial dependency on `OE_ID` 346 347 - **Relation analyzed:** `S1` (32 attributes). Dependencies: as listed for `S1` in the 348 previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. 349 - **Remaining 2NF violations:** the partial dependencies on `OE_ID`, `MT_ID`, `MC_ID`, `W_ID` 350 and `WI_ID` (table above), and the partial dependencies of the kept identifiers 351 `O_ID`, `U_ID`, `M_ID`, `C_ID` on `T_ID`. The kept identifiers cannot leave yet, because 352 other groups still need them. Each one leaves with the last group that needs it (`O_ID` in 353 2NF-2, `M_ID` in 2NF-4, `U_ID` in 2NF-5, `C_ID` in 2NF-6). **Split first on `OE_ID`**, 354 because after it no group needs `O_ID` any more. 355 - **Decomposition dependency:** `OE_ID → OE_*, O_ID` (FD13). `OE_ID` is a proper part of K1 356 and `OE_*` are non-prime. 357 - **New relation `R_B`** = `{ OE_ID, OE_*, O_ID }` (7 attributes). Dependencies: FD13. 358 Candidate key: `OE_ID`. Normal form: BCNF. 359 - **Residual relation `S2`** = `S1 − { OE_*, O_ID }` (26 attributes). No dependency still 360 needed in the residual uses `O_ID`. Dependencies: FD12, FD14–FD18, plus the projected `T_ID → U_ID, M_ID, C_ID`, 361 `OE_ID → U_ID, M_ID, C_ID`, `M_ID → C_ID`, `MT_ID → C_ID`, `MC_ID → C_ID`, `WI_ID → U_ID`. 362 Candidate keys: K1–K4. Normal form: 1NF. 363 - **Dependency preservation:** FD13 is in `R_B`, and the others are in `S2`. 364 `T_ID → O_ID` is already kept in `R_A`. ✓ 365 - **Lossless join:** `R_B ∩ S2 = { OE_ID }`, and `OE_ID → R_B` (FD13). ✓ 366 367 ### Step 2NF-3 — partial dependency on `MT_ID` 368 369 - **Relation analyzed:** `S2` (26 attributes). Dependencies: as listed for `S2` in the 370 previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. 371 - **Remaining 2NF violations:** the groups of `MT_ID`, `MC_ID`, `W_ID`, `WI_ID`, and the kept 372 identifiers `U_ID`, `M_ID`, `C_ID`. **Split first on `MT_ID`**, the next group. `M_ID` must 373 still stay for `MC_ID`. 374 - **Decomposition dependency:** `MT_ID → MT_*, M_ID, O_ID_FILLSBUY, O_ID_FILLSSELL` (FD12). 375 - **New relation `R_C`** = `{ MT_ID, MT_*, M_ID, O_ID_FILLSBUY, O_ID_FILLSSELL }` 376 (9 attributes). Dependencies: FD12. Candidate key: `MT_ID`. Normal form: BCNF. 377 - **Residual relation `S3`** = `S2 − { MT_*, O_ID_FILLSBUY, O_ID_FILLSSELL }` (19 attributes). 378 `M_ID` stays, because FD14/FD15 need it. Dependencies: FD14–FD18, plus the projected `T_ID → U_ID, M_ID, C_ID`, 379 `OE_ID → U_ID, M_ID, C_ID`, `MT_ID → M_ID, C_ID`, `M_ID → C_ID`, `MC_ID → C_ID`, 380 `WI_ID → U_ID`. 381 Candidate keys: K1–K4. Normal form: 1NF. 382 - **Dependency preservation:** FD12 is in `R_C`, and FD14–FD18 are in `S3`. ✓ 383 - **Lossless join:** `R_C ∩ S3 = { MT_ID, M_ID }` contains `MT_ID`, and `MT_ID → R_C` 384 (FD12). ✓ 385 386 ### Step 2NF-4 — partial dependency on `MC_ID` 387 388 - **Relation analyzed:** `S3` (19 attributes). Dependencies: as listed for `S3` in the 389 previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. 390 - **Remaining 2NF violations:** the groups of `MC_ID`, `W_ID`, `WI_ID`, and the kept 391 identifiers `U_ID`, `M_ID`, `C_ID`. **Split first on `MC_ID`**, the last group that needs 392 `M_ID`, so `M_ID` can leave with it. 393 - **Decomposition dependency:** `MC_ID → MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, M_ID` 394 (FD14). `MC_ID` is a proper part of K1. The prime `MC_TIMEFRAME` and `MC_CANDLE_TIME` also go 395 into the new relation, so that FD15, which needs them with `M_ID` and `MC_ID`, is preserved. 396 - **New relation `R_D`** = `{ MC_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, 397 MC_VOLUME, MC_CANDLE_TIME, M_ID }` (9 attributes). Dependencies: FD14, FD15. Candidate keys: 398 `MC_ID` and `{M_ID, MC_TIMEFRAME, MC_CANDLE_TIME}`. Normal form: BCNF. 399 - **Residual relation `S4`** = `S3 − { MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, M_ID }` 400 (13 attributes). `MC_TIMEFRAME` and `MC_CANDLE_TIME` are prime and stay. Dependencies: FD16–FD18, plus the projected `T_ID → U_ID, C_ID`, `OE_ID → U_ID, C_ID`, 401 `MT_ID → C_ID`, `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME, C_ID`, `WI_ID → U_ID`. 402 Candidate keys: K1–K4. Normal form: 1NF. 403 - **Dependency preservation:** FD14 and FD15 are in `R_D`, and FD16–FD18 are in `S4`. ✓ 404 - **Lossless join:** `R_D ∩ S4 = { MC_ID, MC_TIMEFRAME, MC_CANDLE_TIME }` contains `MC_ID`, 405 and `MC_ID → R_D` (FD14). ✓ 406 407 ### Step 2NF-5 — partial dependency on `W_ID` 408 409 - **Relation analyzed:** `S4` (13 attributes). Dependencies: as listed for `S4` in the 410 previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. 411 - **Remaining 2NF violations:** the groups of `W_ID` and `WI_ID`, and the kept identifiers 412 `U_ID`, `C_ID`. **Split first on `W_ID`**, the last group that needs `U_ID`. 413 - **Decomposition dependency:** `W_ID → W_NAME, W_CREATED_AT, U_ID` (FD16). `W_ID` is a proper 414 part of K2. 415 - **New relation `R_E`** = `{ W_ID, W_NAME, W_CREATED_AT, U_ID }` (4 attributes). Dependencies: 416 FD16. Candidate key: `W_ID`. Normal form: BCNF. 417 - **Residual relation `S5`** = `S4 − { W_NAME, W_CREATED_AT, U_ID }` (10 attributes). 418 Dependencies: FD17, FD18, plus the projected `T_ID → C_ID`, `OE_ID → C_ID`, `MT_ID → C_ID`, 419 `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME, C_ID`. 420 Candidate keys: K1–K4. Normal form: 1NF. 421 - **Dependency preservation:** FD16 is in `R_E`, and FD17 and FD18 are in `S5`. ✓ 422 - **Lossless join:** `R_E ∩ S5 = { W_ID }`, and `W_ID → R_E` (FD16). ✓ 423 424 ### Step 2NF-6 — partial dependency on `WI_ID` 425 426 - **Relation analyzed:** `S5` (10 attributes). Dependencies: as listed for `S5` in the 427 previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. 428 - **Remaining 2NF violations:** the group of `WI_ID`, and the kept identifier `C_ID`. 429 **Split on `WI_ID`**, the last group that needs `C_ID`. 430 - **Decomposition dependency:** `WI_ID → WI_ADDED_AT, W_ID, C_ID` (FD17). `WI_ID` is a proper 431 part of K1, and `WI_ADDED_AT` and `C_ID` are non-prime. 432 - **New relation `R_F`** = `{ WI_ID, WI_ADDED_AT, W_ID, C_ID }` (4 attributes). Dependencies: 433 FD17, FD18. Candidate keys: `WI_ID` and `{W_ID, C_ID}`. Normal form: BCNF. 434 - **Residual relation `S6`** = `S5 − { WI_ADDED_AT, C_ID }` = 435 `{ T_ID, OE_ID, MT_ID, MC_ID, MC_TIMEFRAME, MC_CANDLE_TIME, W_ID, WI_ID }` (8 attributes). 436 `W_ID` is prime and stays. Dependencies: no dependency of the cover lies entirely inside 437 `S6`. The projected ones are `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME` and `WI_ID → W_ID`, plus 438 derived ones such as `MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME → MC_ID` and `MT_ID, W_ID → WI_ID`. 439 Candidate keys: K1–K4. Normal form: 3NF, because every attribute is prime (and so 2NF). 440 - **Dependency preservation:** FD17 and FD18 are in `R_F`. ✓ 441 - **Lossless join:** `R_F ∩ S6 = { WI_ID, W_ID }` contains `WI_ID`, and `WI_ID → R_F` 442 (FD17). ✓ 443 444 **Result of 2NF:** `R_A`, `R_B`, `R_C`, `R_D`, `R_E`, `R_F`, `S6`. All seven are in 2NF (`R_A` 445 only 2NF, `S6` 3NF, the rest BCNF). All 18 dependencies are preserved: FD1–FD11 in `R_A`, 446 FD13 in `R_B`, FD12 in `R_C`, FD14–FD15 in `R_D`, FD16 in `R_E`, FD17–FD18 in `R_F`. 447 448 ## 3NF decomposition 449 450 Only `R_A` is not in 3NF. `R_B`–`R_F` are already in BCNF, and `S6` is in 3NF (all its 451 attributes are prime). 452 453 **Dependencies that violate 3NF in `R_A`.** 3NF forbids a non-prime attribute from depending on 454 a key only **transitively**, through a determinant that is not a superkey. The only key of 455 `R_A` is `T_ID`, but inside `R_A`: 456 457 - `U_ID → U_*` (FD1), `U_USERNAME → U_ID` (FD2), `U_EMAIL → U_ID` (FD3) 458 - `C_ID → C_*` (FD4), `C_SYMBOL → C_ID` (FD5) 459 - `U_ID, C_ID → H_ID` (FD9), `H_ID → H_*, U_ID, C_ID` (FD8) 460 - `M_ID → M_*, C_ID` (FD6), `C_ID, M_QUOTE_CURRENCY → M_ID` (FD7) 461 - `O_ID → O_*, U_ID, M_ID` (FD10) 462 463 None of these determinants is a superkey of `R_A`. For example, `T_ID → O_ID → O_PRICE` is a 464 transitive dependency of the non-prime `O_PRICE` on the key. 465 466 **Order of the steps.** An attribute can leave the residual only after every dependency that 467 needs it has been extracted. FD9 needs `U_ID` and `C_ID` together, and extracting `Markets` 468 takes `C_ID` out of the residual, so `Holdings` must come before `Markets`. Extracting 469 `Orders` takes `M_ID` and `U_ID` out, so `Orders` comes last. The dependencies are therefore 470 taken from the "leaves" of the chain `T_ID → O_ID → {U_ID, M_ID → C_ID}` inward. 471 472 ### Step 3NF-1 — transitive dependency through `U_ID` 473 474 - **Relation analyzed:** `R_A` (39 attributes), dependencies FD1–FD11, candidate key and 475 primary candidate key and primary key `T_ID`, normal form 2NF. 476 - **3NF violations:** all five groups listed above. **Split first on `U_ID`**. It is a leaf 477 of the chain: its dependents determine nothing outside its own group. 478 - **Decomposition dependency:** `U_ID → U_*` (FD1). `U_ID` is not a superkey of `R_A`. 479 - **New relation `R_USERS`** = `{ U_ID, U_* }` (10 attributes). Dependencies: FD1, FD2, FD3. 480 Candidate keys: `U_ID`, `U_USERNAME`, `U_EMAIL`. Primary key: `U_ID`. Normal form: BCNF. 481 - **Residual relation `R_A1`** = `R_A − U_*` (30 attributes). Dependencies: FD4–FD11, which 482 also imply `T_ID → H_ID` and `O_ID → H_ID` (through `U_ID, C_ID`). 483 Candidate key and primary key: `T_ID`. Normal form: 2NF. 484 - **Dependency preservation:** FD1–FD3 are in `R_USERS`, and FD4–FD11 are in `R_A1`. ✓ 485 - **Lossless join:** `R_USERS ∩ R_A1 = { U_ID }`, and `U_ID → R_USERS` (FD1). ✓ 486 487 ### Step 3NF-2 — transitive dependency through `C_ID` 488 489 - **Relation analyzed:** `R_A1` (30 attributes), dependencies FD4–FD11, candidate key and primary key `T_ID`, normal form 490 2NF. 491 - **3NF violations:** `C_ID → C_*`, `U_ID, C_ID → H_ID → H_*`, `M_ID → M_*, C_ID`, 492 `O_ID → O_*, U_ID, M_ID`. **Split first on `C_ID`**, the next leaf. 493 - **Decomposition dependency:** `C_ID → C_*` (FD4). 494 - **New relation `R_CRYPTO`** = `{ C_ID, C_* }` (4 attributes). Dependencies: FD4, FD5. 495 Candidate keys: `C_ID`, `C_SYMBOL`. Primary key: `C_ID`. Normal form: BCNF. 496 - **Residual relation `R_A2`** = `R_A1 − C_*` (27 attributes). Dependencies: FD6–FD11. Candidate 497 key and primary key: `T_ID`. Normal form: 2NF. 498 - **Dependency preservation:** FD4 and FD5 are in `R_CRYPTO`, and FD6–FD11 are in `R_A2`. ✓ 499 - **Lossless join:** `R_CRYPTO ∩ R_A2 = { C_ID }`, and `C_ID → R_CRYPTO` (FD4). ✓ 500 501 ### Step 3NF-3 — transitive dependency through `{U_ID, C_ID}` 502 503 - **Relation analyzed:** `R_A2` (27 attributes), dependencies FD6–FD11, candidate key and primary key `T_ID`, normal form 504 2NF. 505 - **3NF violations:** `U_ID, C_ID → H_ID → H_*`, `M_ID → M_*, C_ID`, `O_ID → O_*, U_ID, M_ID`. 506 **Split first on `{U_ID, C_ID}`**, because it must come before `Markets` takes `C_ID` away. 507 - **Decomposition dependency:** `U_ID, C_ID → H_ID` (FD9), together with `H_ID → H_*` 508 (FD8). 509 - **New relation `R_HOLDINGS`** = `{ H_ID, H_*, U_ID, C_ID }` (8 attributes). Dependencies: 510 FD8, FD9. Candidate keys: `H_ID`, `{U_ID, C_ID}`. Primary key: `H_ID`. Normal form: BCNF. 511 - **Residual relation `R_A3`** = `R_A2 − { H_ID, H_* }` (21 attributes). Dependencies: FD6, 512 FD7, FD10, FD11. Candidate key and primary key: `T_ID`. Normal form: 2NF. 513 - **Dependency preservation:** FD8 and FD9 are in `R_HOLDINGS`, and the others are in `R_A3`. ✓ 514 - **Lossless join:** `R_HOLDINGS ∩ R_A3 = { U_ID, C_ID }`, and `U_ID, C_ID → H_ID → H_*`, so 515 `{U_ID, C_ID} → R_HOLDINGS`. ✓ 516 517 ### Step 3NF-4 — transitive dependency through `M_ID` 518 519 - **Relation analyzed:** `R_A3` (21 attributes), dependencies FD6, FD7, FD10, FD11, key 520 `T_ID`, normal form 2NF. 521 - **3NF violations:** `M_ID → M_*, C_ID` and `O_ID → O_*, U_ID, M_ID`. **Split first on 522 `M_ID`**, because `Orders` still needs `M_ID`. 523 - **Decomposition dependency:** `M_ID → M_*, C_ID` (FD6). 524 - **New relation `R_MARKETS`** = `{ M_ID, M_*, C_ID }` (5 attributes). Dependencies: FD6, FD7. 525 Candidate keys: `M_ID`, `{C_ID, M_QUOTE_CURRENCY}`. Primary key: `M_ID`. Normal form: BCNF. 526 - **Residual relation `R_A4`** = `R_A3 − { M_*, C_ID }` (17 attributes). No dependency left 527 needs `C_ID`. Dependencies: FD10, FD11. Candidate key and primary key: `T_ID`. Normal form: 2NF. 528 - **Dependency preservation:** FD6 and FD7 are in `R_MARKETS`, and FD10 and FD11 are in 529 `R_A4`. ✓ 530 - **Lossless join:** `R_MARKETS ∩ R_A4 = { M_ID }`, and `M_ID → R_MARKETS` (FD6). ✓ 531 532 ### Step 3NF-5 — transitive dependency through `O_ID` 533 534 - **Relation analyzed:** `R_A4` = `{ T_ID, T_*, O_ID, O_*, U_ID, M_ID }` (17 attributes), 535 dependencies FD10, FD11, candidate key and primary key `T_ID`, normal form 2NF. 536 - **3NF violations:** only `O_ID → O_*, U_ID, M_ID`. **Split on `O_ID`**. 537 - **Decomposition dependency:** `O_ID → O_*, U_ID, M_ID` (FD10). 538 - **New relation `R_ORDERS`** = `{ O_ID, O_*, U_ID, M_ID }` (11 attributes). Dependencies: 539 FD10. Candidate key: `O_ID`. Normal form: BCNF. 540 - **Residual relation `R_TRANSACTIONS`** = `R_A4 − { O_*, U_ID, M_ID }` = `{ T_ID, T_*, O_ID }` 541 (7 attributes). Dependencies: FD11. Candidate key: `T_ID`. Normal form: BCNF. Keeping `U_ID` 542 here would have left the transitive dependency `T_ID → O_ID → U_ID` inside the relation. 543 `T_ID → U_ID` was removed from the cover as redundant, so nothing is lost. 544 - **Dependency preservation:** FD10 is in `R_ORDERS`, and FD11 is in `R_TRANSACTIONS`. ✓ 545 - **Lossless join:** `R_ORDERS ∩ R_TRANSACTIONS = { O_ID }`, and `O_ID → R_ORDERS` 546 (FD10). ✓ 547 548 **Result of 3NF:** `R_USERS`, `R_CRYPTO`, `R_HOLDINGS`, `R_MARKETS`, `R_ORDERS`, 549 `R_TRANSACTIONS` (from `R_A`), and `R_B`, `R_C`, `R_D`, `R_E`, `R_F`, `S6` unchanged. 12 550 relations, all in 3NF, and all except `S6` in BCNF. All 18 dependencies are preserved. 551 552 ## BCNF if possible 553 554 BCNF requires **every** determinant of a non-trivial dependency to be a superkey, even when 555 the dependent attribute is prime. 556 557 | Relation | Dependencies in force | Determinants | All superkeys? | 237 558 |---|---|---|---| 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 249 Every 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 251 determining, so 2NF holds trivially in each). 252 253 **Dependency preservation.** FD1–FD17 is the canonical cover of `R_EDUBERZA`. Each FD's 254 determinant and every one of its dependent attributes land inside exactly one of the ten new 255 relations (see the "Source FDs" column above — no FD is split across two relations). The 256 union of the FDs that hold on `R_USERS, …, R_WATCHLIST_ITEMS` is therefore exactly FD1–FD17 257 again: 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 265 The chase decides whether a decomposition `R = R1 ∪ … ∪ Rn` is lossless under a set of 266 functional dependencies. Build a tableau with one column per attribute of `R` and one row per 267 relation `Ri`. In row `i`, put a distinguished symbol `a` in every column of `Ri` and a unique 268 symbol `b_i` in every other column. Then repeat, until nothing changes: for each FD `X → Y`, 269 whenever two rows agree on all of `X`, make them agree on `Y`. If they disagree, an `a` wins, 270 otherwise one `b` replaces the other. **The decomposition is lossless exactly when some row 271 ends up with `a` in every column.** 272 273 All attributes of one cluster (`U_*`, `C_*`, `M_*`, …) always appear together, and FD1–FD17 274 never mix clusters. So each cluster is one column group below: `a` means every column of the 275 group holds a distinguished symbol, and `b` means none of them does. The foreign-key 276 attributes (`H_USER_ID`, `O_MARKET_ID`, …) belong to their own cluster (`H_*`, `O_*`, …), not 277 to 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* 283 R_USERS a b b b b b b b b b 284 R_CRYPTO b a b b b b b b b b 285 R_MARKETS b b a b b b b b b b 286 R_HOLDINGS b b b a b b b b b b 287 R_ORDERS b b b b a b b b b b 288 R_TRANSACTIONS b b b b b a b b b b 289 R_MARKET_TR. b b b b b b a b b b 290 R_MARKET_CA. b b b b b b b a b b 291 R_WATCHLISTS b b b b b b b b a b 292 R_WATCHLIST_I. b b b b b b b b b a 293 ``` 294 295 Every 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 297 left side. But only one row has `a`s in that cluster, and the `b`s of different rows are 298 all different, so no two rows ever agree on any left side. **The chase changes nothing, and 299 no row becomes all `a`.** Under FD1–FD17 alone, the ten relations are *not* guaranteed to 300 join back to `R_EDUBERZA`. This is not an accident of this model. It is exactly why 301 Bernstein's synthesis algorithm has a final step: *if no synthesised relation contains a 302 candidate 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, 305 W_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* 310 R_KEY a· a· a· a· a· a· a· a· a· a· 311 (the ten rows of step 1 unchanged) 312 ``` 313 314 Now FD1 `U_ID → U_*` fires: row `R_KEY` and row `R_USERS` both have `a` in `U_ID`, so they 315 must 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*`), 317 FD12 (`MT*`), FD13 (`MC*`), FD15 (`W*`) and FD16 (`WI*`): 318 319 ``` 320 U* C* M* H* O* T* MT* MC* W* WI* 321 R_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 325 lossless.** 326 327 **Why `R_KEY` is not kept in the final schema.** An instance of `R_KEY` would only record 328 which 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 331 cross product of the ten ID sets and would carry no information. The same independence means 332 the join dependency `⋈[R_USERS, …, R_WATCHLIST_ITEMS]` holds on `R_EDUBERZA` by construction. 333 Under that dependency the ten relations alone already reconstruct it: their natural join, with 334 no common attributes, is exactly that cross product. The chase makes this reasoning explicit. 335 FDs by themselves cannot prove the join lossless; you need either the key relation or the 336 independence of the clusters. That was hidden in the earlier "foreign key equals primary key" 337 argument, which described the equi-joins the application runs, not the natural join the 338 lossless-join property is about. 339 340 ## 3NF decomposition 341 342 **Relations analyzed:** each of the ten relations produced above, individually. 343 344 For each relation, 3NF asks whether any non-prime attribute is *transitively* dependent on a 345 key — i.e. determined by another non-prime attribute rather than directly by the key. This is 346 exactly where the foreign-key-carried dependencies from 347 [Dependencies carried by foreign keys](#dependencies-carried-by-foreign-keys) have to be 348 checked, because that table is precisely the list of "dependency that would cause a problem at 349 the 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` 355 that violates 3NF. They are not: the 2NF step above already put them in `R_CRYPTO`, keyed 356 directly by `C_ID` (FD4), because FD4 — not the derived `M_CRYPTO_ID → C_SYMBOL` — is what the 357 canonical cover actually contains. `R_MARKETS` itself has no attribute that determines another 358 non-prime attribute of `R_MARKETS`; the transitive dependency is real, but it points *out* of 359 the relation, not within it. 360 361 The 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 364 non-key attribute set that depends only on their own relation's key, never on the foreign key 365 itself. 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 367 attribute that another non-prime attribute of the *same* relation determines. 368 369 **Conclusion:** synthesising directly from the canonical cover in the 2NF step already 370 avoided every transitive dependency — there is nothing left to decompose for 3NF. All ten 371 relations 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 376 determinant of every functional dependency that holds on the relation must be a candidate key 377 of 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 392 Every determinant in every relation is one of that relation's own candidate keys. **All ten 393 relations are already in BCNF** — the highest of the four normal forms this phase asks for, 394 reached in the same step that fixed 2NF. This is not a coincidence: it happens because the 395 canonical cover already grouped each relation's own key directly against its own attributes 396 with no attribute appearing on the right side of two different relations' dependencies, which 397 is exactly what synthesis from a canonical cover guarantees when, as here, none of the 398 per-cluster functional dependencies overlap. 399 400 No further decomposition is possible or necessary; splitting any of the ten relations further 401 would only separate attributes that already depend on the *whole* key of a BCNF relation, 402 which cannot fix anything and only costs a join. 559 | `R_USERS` | FD1, FD2, FD3 | `U_ID`, `U_USERNAME`, `U_EMAIL` | yes | 560 | `R_CRYPTO` | FD4, FD5 | `C_ID`, `C_SYMBOL` | yes | 561 | `R_MARKETS` | FD6, FD7 | `M_ID`, `{C_ID, M_QUOTE_CURRENCY}` | yes | 562 | `R_HOLDINGS` | FD8, FD9 | `H_ID`, `{U_ID, C_ID}` | yes | 563 | `R_ORDERS` | FD10 | `O_ID` | yes | 564 | `R_TRANSACTIONS` | FD11 | `T_ID` | yes | 565 | `R_B` | FD13 | `OE_ID` | yes | 566 | `R_C` | FD12 | `MT_ID` | yes | 567 | `R_D` | FD14, FD15 | `MC_ID`, `{M_ID, MC_TIMEFRAME, MC_CANDLE_TIME}` | yes | 568 | `R_E` | FD16 | `W_ID` | yes | 569 | `R_F` | FD17, FD18 | `WI_ID`, `{W_ID, C_ID}` | yes | 570 | `S6` | `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME`; `WI_ID → W_ID`; derived ones such as `MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME → MC_ID` and `MT_ID, W_ID → WI_ID` | `MC_ID`, `WI_ID`, `{MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME}`, `{MT_ID, W_ID}`, … | **no** | 571 572 **Dependencies that violate BCNF — only in `S6`.** `MC_ID` determines `MC_TIMEFRAME` and 573 `MC_CANDLE_TIME`, and `WI_ID` determines `W_ID`, but neither `MC_ID` nor `WI_ID` is a superkey 574 of `S6`. 3NF allowed this because the dependent attributes are prime. BCNF does not. The derived 575 dependencies all involve `W_ID` or `MC_TIMEFRAME`/`MC_CANDLE_TIME`, so they disappear once the 576 two steps below remove those attributes. 577 578 ### Step BCNF-1 — `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME` 579 580 - **Relation analyzed:** `S6` (8 attributes), dependencies as in the table above, candidate 581 keys K1–K4, primary key K1, normal form 3NF. 582 - **BCNF violations:** `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME` and `WI_ID → W_ID`, and the 583 derived ones that depend on them. **Split first on `MC_ID`**. The order does not matter 584 here, because the two violations share no attribute. 585 - **Decomposition dependency:** `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME`. `MC_ID` is not a 586 superkey of `S6`. 587 - **New relation** `{ MC_ID, MC_TIMEFRAME, MC_CANDLE_TIME }`. Dependencies: 588 `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME`. Key: `MC_ID`. Normal form: BCNF. It is a 589 projection of `R_D`, which already contains these attributes with the same key, so it adds no 590 information and is merged into `R_D`. 591 - **Residual relation `S7`** = `{ T_ID, OE_ID, MT_ID, MC_ID, W_ID, WI_ID }` (6 attributes). 592 Dependencies: `WI_ID → W_ID`, and derived ones such as `MT_ID, W_ID → WI_ID`. Candidate 593 keys: `{T_ID, OE_ID, MT_ID, MC_ID, WI_ID}` (K1) and `{T_ID, OE_ID, MT_ID, MC_ID, W_ID}` (K2). 594 Normal form: 3NF. 595 - **Dependency preservation:** no dependency of the cover is affected. FD14 and FD15 are in 596 `R_D`. ✓ 597 - **Lossless join:** the intersection is `{ MC_ID }`, and `MC_ID → { MC_ID, MC_TIMEFRAME, 598 MC_CANDLE_TIME }`. ✓ 599 600 ### Step BCNF-2 — `WI_ID → W_ID` 601 602 - **Relation analyzed:** `S7` (6 attributes), dependencies `WI_ID → W_ID` and derived ones, 603 candidate keys K1, K2, primary key K1, normal form 3NF. 604 - **BCNF violations:** only `WI_ID → W_ID` (and the derived `MT_ID, W_ID → WI_ID`). **Split on 605 `WI_ID`**. 606 - **Decomposition dependency:** `WI_ID → W_ID`. `WI_ID` is not a superkey of `S7`. 607 - **New relation** `{ WI_ID, W_ID }`. Dependencies: `WI_ID → W_ID`. Key: `WI_ID`. Normal 608 form: BCNF. For the same reason as in BCNF-1, it is merged into `R_F`. 609 - **Residual relation `R_KEY`** = `{ T_ID, OE_ID, MT_ID, MC_ID, WI_ID }` (5 attributes). No 610 non-trivial dependency holds among these attributes. Candidate key: all five (= K1). 611 Normal form: BCNF. 612 - **Dependency preservation:** no dependency of the cover is affected. FD17 and FD18 are in 613 `R_F`. The derived dependencies of `S6`/`S7` follow from FD12, FD15, FD17 and FD18, which 614 are all preserved. ✓ 615 - **Lossless join:** the intersection is `{ WI_ID }`, and `WI_ID → { WI_ID, W_ID }`. ✓ 616 617 **Result: every relation is in BCNF.** The decomposition into these 12 relations is lossless 618 (each of the 13 binary steps passed the test) and preserves all 18 dependencies of the 619 canonical cover. 403 620 404 621 ## Final result and discussion 405 622 406 623 ### Normalized relational model 624 625 Each relation is followed by its keys (primary key first). An attribute that is the 626 identifier of another relation is marked `→` with that relation. 407 627 408 628 ``` 409 629 R_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) 630 U_AVAILABLE_BALANCE, U_INVESTED_BALANCE, U_RESERVED_BALANCE, 631 U_CREATED_AT, U_UPDATED_AT) 632 keys: U_ID; U_USERNAME; U_EMAIL 411 633 R_CRYPTO (C_ID, C_SYMBOL, C_NAME, C_CREATED_AT) 412 R_MARKETS (M_ID, M_CRYPTO_ID → R_CRYPTO, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT) 413 R_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) 415 R_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) 417 R_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) 419 R_MARKET_TRADES (MT_ID, MT_MARKET_ID → R_MARKETS, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, 420 MT_SIDE, MT_SOURCE) 421 R_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) 423 R_WATCHLISTS (W_ID, W_USER_ID → R_USERS, W_NAME, W_CREATED_AT) 424 R_WATCHLIST_ITEMS(WI_ID, WI_WATCHLIST_ID → R_WATCHLISTS, WI_CRYPTO_ID → R_CRYPTO, WI_ADDED_AT) 634 keys: C_ID; C_SYMBOL 635 R_MARKETS (M_ID, C_ID → R_CRYPTO, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT) 636 keys: M_ID; {C_ID, M_QUOTE_CURRENCY} 637 R_HOLDINGS (H_ID, U_ID → R_USERS, C_ID → R_CRYPTO, H_QUANTITY, 638 H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT) 639 keys: H_ID; {U_ID, C_ID} 640 R_ORDERS (O_ID, U_ID → R_USERS, M_ID → R_MARKETS, O_SIDE, O_TYPE, O_STATUS, 641 O_QUANTITY, O_FILLED_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT) 642 key: O_ID 643 R_TRANSACTIONS (T_ID, O_ID → R_ORDERS, T_TYPE, T_AMOUNT, T_CURRENCY, T_CREATED_AT, 644 T_DESCRIPTION) 645 key: T_ID 646 R_MARKET_TRADES (MT_ID, M_ID → R_MARKETS, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, 647 MT_SIDE, MT_SOURCE, O_ID_FILLSBUY → R_ORDERS (nullable), 648 O_ID_FILLSSELL → R_ORDERS (nullable)) [= R_C] 649 key: MT_ID 650 R_ORDER_EVENTS (OE_ID, O_ID → R_ORDERS, OE_EVENT_TYPE, OE_QUANTITY, OE_PRICE, 651 OE_STATUS_AFTER, OE_CREATED_AT) [= R_B] 652 key: OE_ID 653 R_MARKET_CANDLES (MC_ID, M_ID → R_MARKETS, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, 654 MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME) [= R_D] 655 keys: MC_ID; {M_ID, MC_TIMEFRAME, MC_CANDLE_TIME} 656 R_WATCHLISTS (W_ID, U_ID → R_USERS, W_NAME, W_CREATED_AT) [= R_E] 657 key: W_ID 658 R_WATCHLIST_ITEMS(WI_ID, W_ID → R_WATCHLISTS, C_ID → R_CRYPTO, WI_ADDED_AT) [= R_F] 659 keys: WI_ID; {W_ID, C_ID} 660 R_KEY (T_ID, OE_ID, MT_ID, MC_ID, WI_ID) [= R_KEY] 661 key: all five 425 662 ``` 426 663 427 Ten relations, every one in BCNF, connected by the eleven foreign keys spelled out above.428 429 664 ### Discussion 430 665 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, 433 R_MARKET_CANDLES, R_WATCHLISTS, R_WATCHLIST_ITEMS` are, attribute for attribute and key for 434 key, `users, crypto, markets, holdings, orders, transactions, market_trades, market_candles, 435 watchlists, watchlist_items` from 436 [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md). Every foreign key matches, 437 every candidate key matches (including the less obvious composite ones — `{user_id, 438 crypto_id}` on `holdings`, `{crypto_id, quote_currency}` on `markets`, `{market_id, timeframe, 439 candle_time}` on `market_candles`), and the normal form matches (P2 already claimed 3NF; this 440 phase shows the stronger result that the design is actually in BCNF). 441 442 That is not a coincidence of two people happening to agree — it is what should happen when a 443 design is derived correctly twice by two different methods from the same underlying model: 444 P2 got here by applying the standard ER-to-relational transformation rules (each entity 445 becomes a table on its own key, each attributed M:N relationship becomes a table on the 446 combined key, each attributeless 1:N relationship becomes a foreign key on the "many" side). 447 This phase got here by ignoring that transformation entirely, writing down only the 448 attributes and the functional dependencies they obey, and mechanically applying 2NF/3NF/BCNF 449 synthesis. Landing on the same ten relations either means the P2 transformation rules are 450 sound for this particular model (which they are, for exactly the reason [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md#normalisation) 451 already argued: single-column UUID primary keys everywhere rule out partial dependencies by 452 construction, and no non-key attribute references another non-key attribute anywhere in the 453 model, which rules out transitive dependencies too), or it is a coincidence spanning ten 454 independently-checked relations and dozens of functional dependencies — the first explanation 455 is 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 459 in `transactions` — kept as a stored column anyway for read performance 460 ([RelationalDesign](../P2-RelationalDesign/RelationalDesign.md#normalisation) calls this out 461 explicitly as an accepted denormalisation). Nothing in this phase's functional-dependency 462 analysis can see that `H_AVG_PRICE` is derivable from `T_*` rows rather than stored 463 independently — FD8 (`H_ID → H_AVG_PRICE`) is a perfectly ordinary functional dependency 464 either way, because *derivability from a different relation's rows* is a property of the data 465 and the application logic that maintains it (see 466 [UseCase0004](../P3-UseCaseModel/UseCase0004.md)'s `ON CONFLICT … DO UPDATE`), not something 467 that shows up as a violation of any single-relation normal form. Formal normalization and "no 468 column is a cached computation of other columns" are related but different concerns; this 469 phase only checked the first one. 470 471 **Which design is used going forward:** P2's, unchanged. Since the two designs coincide 472 exactly, "restructuring the database objects" means confirming there is nothing to change 473 rather than writing new DDL. [`server/db/schema_creation.sql`](../../server/db/schema_creation.sql) 474 already 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 480 change. [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md) has been updated with a 481 short note pointing here as the formal validation of its normal-form claim. 666 **The eleven data relations are the P2 design, with one difference** (`transactions.user_id`, 667 explained below). Each relation is one entity set of the ER model: 668 669 | P5 relation | P2 table | How the relationships appear | 670 |---|---|---| 671 | `R_USERS` | `users` | — | 672 | `R_CRYPTO` | `crypto` | — | 673 | `R_MARKETS` | `markets` | `C_ID` = `crypto_id` (`QuotedOn`) | 674 | `R_HOLDINGS` | `holdings` | `U_ID` = `user_id` (`Holds`), `C_ID` = `crypto_id` (`PositionIn`) | 675 | `R_ORDERS` | `orders` | `U_ID` = `user_id` (`Places`), `M_ID` = `market_id` (`PlacedOn`) | 676 | `R_TRANSACTIONS` | `transactions` | `O_ID` = `related_order` (`Settles`); P2 also stores `user_id` (`Records`), see below | 677 | `R_MARKET_TRADES` | `market_trades` | `M_ID` = `market_id` (`Fills`), `O_ID_FILLSBUY` = `buy_order_id`, `O_ID_FILLSSELL` = `sell_order_id` | 678 | `R_ORDER_EVENTS` | `order_events` | `O_ID` = `order_id` (`Logs`) | 679 | `R_MARKET_CANDLES` | `market_candles` | `M_ID` = `market_id` (`Aggregates`) | 680 | `R_WATCHLISTS` | `watchlists` | `U_ID` = `user_id` (`Owns`) | 681 | `R_WATCHLIST_ITEMS` | `watchlist_items` | `W_ID` = `watchlist_id` (`Contains`), `C_ID` = `crypto_id` (`Lists`) | 682 683 The two methods produce the foreign keys differently. In P2 they come from a transformation 684 rule: a 1:N relationship becomes a column on the N side. Here, each one appears because a 685 dependency of kind (R), for example `O_ID → U_ID`, keeps the other entity's identifier in the 686 same relation as the entity that depends on it. The candidate keys also match, including the 687 composite ones (`{C_ID, M_QUOTE_CURRENCY}`, `{U_ID, C_ID}`, `{M_ID, MC_TIMEFRAME, 688 MC_CANDLE_TIME}`, `{W_ID, C_ID}`). They are exactly the `UNIQUE` constraints in 689 [`schema_creation.sql`](../../server/db/schema_creation.sql). 690 691 **The one difference: `transactions.user_id`.** The decomposition drops `U_ID` from 692 `R_TRANSACTIONS`, because `T_ID → U_ID` follows from `T_ID → O_ID` and `O_ID → U_ID`. That is 693 correct for every ledger entry that settles an order. It does not work for a **deposit**. 694 `Settles` is partial, so a deposit has no order, and without `user_id` a deposit would have no 695 owner at all. The de-normalized relation cannot show this case. Every one of its tuples 696 contains an order (every key contains `OE_ID`, and every order event has an order), so a 697 ledger entry without an order cannot appear in it. P2 therefore keeps `user_id` (the 698 relationship `Records`) as a deliberate exception. As a result, the implemented 699 `transactions` table is in **2NF but not in 3NF** (`related_order → user_id` is a transitive 700 dependency), and this is by design. For entries with an order, 701 `transactions.user_id` repeats the order's user. The only code that sets `related_order` (the buy 702 and sell inserts in `advanced_db.sql`) writes the user and the id of the same order row. No 703 database constraint enforces this. 704 705 **Two order columns in `market_trades`.** `FillsBuy` and `FillsSell` needed two role 706 attributes already in the de-normalized relation, and both end up in `R_MARKET_TRADES`. 707 They correspond to `buy_order_id` and `sell_order_id`. 708 709 **`R_KEY` belongs to the formal result, but it is not implemented as a table.** It is the 710 relation that contains a key of `R_EDUBERZA`, and the lossless-join result above holds for all 711 12 relations *including* it. It records no fact of the domain. It only says which ledger 712 entry, order event, trade, candle and watchlist item were put into the same tuple, and that 713 combination exists only because we started from one single relation. Not implementing it is 714 an implementation decision. The eleven implemented tables are not claimed to reconstruct 715 `R_EDUBERZA` on their own. They keep every attribute and every dependency of the canonical 716 cover, and that is what the application needs. 717 718 **`holdings.avg_price`** is shown as a *derived* attribute in the ER model: it can be 719 recomputed from the buy history. It is still stored, and that is a deliberate 720 denormalisation (see [RelationalDesign](../P2-RelationalDesign/RelationalDesign.md#normalisation)). 721 Normalisation cannot detect this. `H_ID → H_AVG_PRICE` is an ordinary functional dependency, 722 because "derivable from rows of another entity" is a property of the application logic 723 that maintains the value (see [UseCase0004](../P3-UseCaseModel/UseCase0004.md), 724 `ON CONFLICT … DO UPDATE`), not a dependency between attributes of one tuple. 725 726 **Which design is used going forward:** P2's, unchanged. The eleven data relations coincide 727 with the eleven tables of [`schema_creation.sql`](../../server/db/schema_creation.sql) and 728 [`advanced_db.sql`](../../server/db/advanced_db.sql) column for column, except for the 729 deliberately kept `transactions.user_id` explained above. So there are no database objects 730 to restructure, and the prototype and the reports of P6/P7 keep working against the same 731 schema.
Note:
See TracChangeset
for help on using the changeset viewer.
