Index: docs/P5-Normalization/Normalization.md =================================================================== --- docs/P5-Normalization/Normalization.md (revision a531b45df67bdc814d08013102302eda333cc626) +++ docs/P5-Normalization/Normalization.md (revision ef1c1c725137d93fa85292f43440214aaddcdf05) @@ -257,17 +257,84 @@ again: nothing was lost. -**Lossless join.** For every pair (referencing relation, referenced relation) connected by a -foreign key — `R_MARKETS.M_CRYPTO_ID → R_CRYPTO.C_ID`, `R_HOLDINGS.H_USER_ID → R_USERS.U_ID` / -`R_HOLDINGS.H_CRYPTO_ID → R_CRYPTO.C_ID`, `R_ORDERS.O_USER_ID → R_USERS.U_ID` / -`R_ORDERS.O_MARKET_ID → R_MARKETS.M_ID`, `R_TRANSACTIONS.T_USER_ID → R_USERS.U_ID` / -`R_TRANSACTIONS.T_RELATED_ORDER → R_ORDERS.O_ID`, `R_MARKET_TRADES.MT_MARKET_ID → -R_MARKETS.M_ID`, `R_MARKET_CANDLES.MC_MARKET_ID → R_MARKETS.M_ID`, -`R_WATCHLISTS.W_USER_ID → R_USERS.U_ID`, `R_WATCHLIST_ITEMS.WI_WATCHLIST_ID → -R_WATCHLISTS.W_ID` / `R_WATCHLIST_ITEMS.WI_CRYPTO_ID → R_CRYPTO.C_ID` — the join attribute on -the "one" side is that relation's own primary key (`U_ID`, `C_ID`, `M_ID`, `O_ID`, `W_ID`). -A join on a foreign key equated to the primary key it references is the textbook sufficient -condition for a lossless decomposition (`Ri ∩ Rj` is a key of `Rj`), so re-joining all ten -relations on their foreign-key/primary-key pairs reconstructs `R_EDUBERZA` exactly, with no -spurious rows and none missing. +**Lossless join — chase test.** + +> *Note: the chase algorithm is not part of the course material. I was curious about a +> stricter way to test lossless join than the usual "the common attributes are a key of one +> side" argument, so I applied it here.* + +The chase decides whether a decomposition `R = R1 ∪ … ∪ Rn` is lossless under a set of +functional dependencies. Build a tableau with one column per attribute of `R` and one row per +relation `Ri`. In row `i`, put a distinguished symbol `a` in every column of `Ri` and a unique +symbol `b_i` in every other column. Then repeat, until nothing changes: for each FD `X → Y`, +whenever two rows agree on all of `X`, make them agree on `Y`. If they disagree, an `a` wins, +otherwise one `b` replaces the other. **The decomposition is lossless exactly when some row +ends up with `a` in every column.** + +All attributes of one cluster (`U_*`, `C_*`, `M_*`, …) always appear together, and FD1–FD17 +never mix clusters. So each cluster is one column group below: `a` means every column of the +group holds a distinguished symbol, and `b` means none of them does. The foreign-key +attributes (`H_USER_ID`, `O_MARKET_ID`, …) belong to their own cluster (`H_*`, `O_*`, …), not +to the cluster they reference. + +**Step 1 — the ten relations from the table above.** + +``` + U* C* M* H* O* T* MT* MC* W* WI* +R_USERS a b b b b b b b b b +R_CRYPTO b a b b b b b b b b +R_MARKETS b b a b b b b b b b +R_HOLDINGS b b b a b b b b b b +R_ORDERS b b b b a b b b b b +R_TRANSACTIONS b b b b b a b b b b +R_MARKET_TR. b b b b b b a b b b +R_MARKET_CA. b b b b b b b a b b +R_WATCHLISTS b b b b b b b b a b +R_WATCHLIST_I. b b b b b b b b b a +``` + +Every FD has its left side inside one cluster, for example `U_ID → U_*` or +`H_USER_ID, H_CRYPTO_ID → H_ID`. For such an FD to fire, two rows would have to agree on that +left side. But only one row has `a`s in that cluster, and the `b`s of different rows are +all different, so no two rows ever agree on any left side. **The chase changes nothing, and +no row becomes all `a`.** Under FD1–FD17 alone, the ten relations are *not* guaranteed to +join back to `R_EDUBERZA`. This is not an accident of this model. It is exactly why +Bernstein's synthesis algorithm has a final step: *if no synthesised relation contains a +candidate key of `R`, add one that does.* None of the ten contains the ten-attribute key. + +**Step 2 — add the key relation** `R_KEY(U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, +W_ID, WI_ID)`. Its row has `a` only in the ten ID columns, written `a·` for "`a` in the ID, +`b` in the rest of the group": + +``` + U* C* M* H* O* T* MT* MC* W* WI* +R_KEY a· a· a· a· a· a· a· a· a· a· +(the ten rows of step 1 unchanged) +``` + +Now FD1 `U_ID → U_*` fires: row `R_KEY` and row `R_USERS` both have `a` in `U_ID`, so they +must agree on the rest of `U_*`, and `R_USERS` has `a` there. `R_KEY` becomes `a` in the whole +`U*` group. The same happens with FD4 (`C*`), FD6 (`M*`), FD8 (`H*`), FD10 (`O*`), FD11 (`T*`), +FD12 (`MT*`), FD13 (`MC*`), FD15 (`W*`) and FD16 (`WI*`): + +``` + U* C* M* H* O* T* MT* MC* W* WI* +R_KEY a a a a a a a a a a <- all distinguished +``` + +**Row `R_KEY` is all `a`, so the decomposition into the ten relations plus `R_KEY` is +lossless.** + +**Why `R_KEY` is not kept in the final schema.** An instance of `R_KEY` would only record +which ID of one cluster appears together with which ID of every other cluster. As shown under +*Candidate keys and primary key*, the ten clusters are independent record types, and +`R_EDUBERZA` pairs every row of one with every row of the others. So `R_KEY` would be just the +cross product of the ten ID sets and would carry no information. The same independence means +the join dependency `⋈[R_USERS, …, R_WATCHLIST_ITEMS]` holds on `R_EDUBERZA` by construction. +Under that dependency the ten relations alone already reconstruct it: their natural join, with +no common attributes, is exactly that cross product. The chase makes this reasoning explicit. +FDs by themselves cannot prove the join lossless; you need either the key relation or the +independence of the clusters. That was hidden in the earlier "foreign key equals primary key" +argument, which described the equi-joins the application runs, not the natural join the +lossless-join property is about. ## 3NF decomposition Index: docs/P5-Normalization/wiki/Normalization.md =================================================================== --- docs/P5-Normalization/wiki/Normalization.md (revision ef1c1c725137d93fa85292f43440214aaddcdf05) +++ docs/P5-Normalization/wiki/Normalization.md (revision ef1c1c725137d93fa85292f43440214aaddcdf05) @@ -0,0 +1,606 @@ += Normalization = + +This phase deliberately ignores the design from [wiki:ERModel] +(P1) and [wiki:RelationalDesign] (P2) as a starting +point. Instead it starts over from a single flat relation containing every attribute of the +model, derives the functional dependencies that hold on it, and decomposes it formally, +step by step. The +final section compares what falls out of that process with +the P2 design. + +== De-normalized database form == + +=== Building one relation out of the whole model === + +The ER model has ten entity/relationship sets carrying attributes (see +[wiki:ERModel]): `Users`, `Cryptos`, `Markets`, `Orders`, +`Transactions`, `MarketTrades`, `MarketCandles`, `Watchlists`, and the two attributed +relationships `Holds` and `Contains`. Eight more relationships (`QuotedOn`, `PlacedOn`, +`Places`, `Records`, `Settles`, `Fills`, `Aggregates`, `Owns`) carry no attributes of their +own — in Chen notation they need none, because the diagram expresses the link itself as a +relationship, not a column. A single flat relation has no such device: the only way to keep +one entity's rows pointed at another's is a plain attribute holding the referenced key, +which is exactly what P2's ER-to-relational transformation already introduces for each of +those eight relationships (`markets.crypto_id`, `orders.market_id`, `orders.user_id`, +`transactions.user_id`, `transactions.related_order`, `market_trades.market_id`, +`market_candles.market_id`, `watchlists.user_id`). Those linking attributes are included +below for that reason — not because they were copied from P2's design, but because a "single +table with everything in it" cannot represent the model at all without them. + +Every attribute name is prefixed by a two-or-three-letter code for the entity/relationship it +came from, because several names repeat across the model (`id`, `created_at`, `quantity`, +`type`, `name`, `price`, `side` all appear more than once) and the de-normalized relation may +not contain duplicate names. + +||= Prefix =||= Origin (P1 entity / relationship) =||= Attributes =|| +|| `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` || +|| `C_` || Cryptos || `C_ID, C_SYMBOL, C_NAME, C_CREATED_AT` || +|| `M_` || Markets (+ `QuotedOn`) || `M_ID, M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` || +|| `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` || +|| `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` || +|| `T_` || Transactions (+ `Records`, `Settles`) || `T_ID, T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` || +|| `MT_` || !MarketTrades (+ `Fills`) || `MT_ID, MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` || +|| `MC_` || !MarketCandles (+ `Aggregates`) || `MC_ID, MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` || +|| `W_` || Watchlists (+ `Owns`) || `W_ID, W_USER_ID, W_NAME, W_CREATED_AT` || +|| `WI_` || `Contains` (+ surrogate key) || `WI_ID, WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` || + +`H_ID` and `WI_ID` exist for the same reason they exist in P2: `Holds` and `Contains` are M:N +relationships with their own attributes, and giving each its own surrogate key (rather than +relying solely on the `{user,crypto}` / `{watchlist,crypto}` pair) is the same design choice +already justified in [wiki:RelationalDesign] (section "Descriptive representation of the relational schema"). + +This gives '''one relation, `R_EDUBERZA`, of 68 attributes:''' + +{{{ +R_EDUBERZA( + U_ID, U_USERNAME, U_EMAIL, U_FULL_NAME, U_PASSWORD_HASH, U_AVAILABLE_BALANCE, + U_INVESTED_BALANCE, U_CREATED_AT, U_UPDATED_AT, + C_ID, C_SYMBOL, C_NAME, C_CREATED_AT, + M_ID, M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT, + H_ID, H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, + H_CREATED_AT, H_UPDATED_AT, + O_ID, O_USER_ID, O_MARKET_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_PRICE, + O_PLACED_AT, O_EXECUTED_AT, + T_ID, T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, + T_DESCRIPTION, + MT_ID, MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE, + MC_ID, MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, + MC_CANDLE_TIME, + W_ID, W_USER_ID, W_NAME, W_CREATED_AT, + WI_ID, WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT +) +}}} + +Every attribute is single-valued and atomic (a balance, a timestamp, a symbol, an amount — +nothing here is a list or a nested record), so `R_EDUBERZA` satisfies 1NF as soon as it is +written down. Whether it satisfies anything beyond that is exactly what the rest of this page +checks. + +== Functional dependencies == + +=== Canonical cover === + +Read directly off the model: each entity's/relationship's own key determines its own +attributes, nothing more. This is already minimal — no functional dependency below has an +extraneous attribute on its left side, and no dependent attribute is repeated on the right +side of more than one dependency, which is what "canonical cover" requires. + +||= # =||= Functional dependency =||= Source =|| +|| 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 || +|| FD2 || `U_USERNAME → U_ID` || Users (`UNIQUE(username)`) || +|| FD3 || `U_EMAIL → U_ID` || Users (`UNIQUE(email)`) || +|| FD4 || `C_ID → C_SYMBOL, C_NAME, C_CREATED_AT` || Cryptos || +|| FD5 || `C_SYMBOL → C_ID` || Cryptos (`UNIQUE(symbol)`) || +|| FD6 || `M_ID → M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` || Markets || +|| FD7 || `M_CRYPTO_ID, M_QUOTE_CURRENCY → M_ID` || Markets (`UNIQUE(crypto_id, quote_currency)`) || +|| FD8 || `H_ID → H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT` || Holds || +|| FD9 || `H_USER_ID, H_CRYPTO_ID → H_ID` || Holds (`UNIQUE(user_id, crypto_id)`) || +|| 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 || +|| FD11 || `T_ID → T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` || Transactions || +|| FD12 || `MT_ID → MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` || !MarketTrades || +|| FD13 || `MC_ID → MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` || !MarketCandles || +|| FD14 || `MC_MARKET_ID, MC_TIMEFRAME, MC_CANDLE_TIME → MC_ID` || !MarketCandles (`UNIQUE(market_id, timeframe, candle_time)`) || +|| FD15 || `W_ID → W_USER_ID, W_NAME, W_CREATED_AT` || Watchlists || +|| FD16 || `WI_ID → WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` || Contains || +|| FD17 || `WI_WATCHLIST_ID, WI_CRYPTO_ID → WI_ID` || Contains (`UNIQUE(watchlist_id, crypto_id)`) || + +'''Minimality, checked by example (Markets):''' could FD7 drop an attribute from its left side? +`M_CRYPTO_ID` alone does not determine `M_ID` — many markets can reference the same crypto in +different quote currencies (that is the entire point of the market entity), so two rows can +share `M_CRYPTO_ID` and disagree on `M_ID`. `M_QUOTE_CURRENCY` alone fails the same way in the +other direction. Neither attribute is extraneous, so the left side of FD7 cannot shrink. The +same check applies to FD9, FD14 and FD17, whose composite left sides come directly from the +`UNIQUE` constraints already justified per-relation in +[wiki:RelationalDesign]; none of those constraints +holds on a proper subset of its columns either. + +'''No redundant dependency:''' each of FD1–FD17 has a right side that is not implied by any +other dependency in the set — for instance, nothing outside FD1 mentions `U_AVAILABLE_BALANCE`, +so FD1 cannot be derived from the rest and cannot be dropped. This set is the canonical cover. + +=== Dependencies carried by foreign keys === + +Six attributes above are foreign keys: `M_CRYPTO_ID`, `H_USER_ID`, `H_CRYPTO_ID`, +`O_USER_ID`, `O_MARKET_ID`, `T_USER_ID`, `T_RELATED_ORDER`, `MT_MARKET_ID`, `MC_MARKET_ID`, +`W_USER_ID`, `WI_WATCHLIST_ID`, `WI_CRYPTO_ID` — each one draws its values from the same +domain as some other attribute's key. Because of that, every dependency that holds on the +referenced key also holds, by substitution, on the referencing attribute: + +||= Foreign key =||= References =||= Therefore also determines =|| +|| `M_CRYPTO_ID` || `C_ID` || `C_SYMBOL, C_NAME, C_CREATED_AT` || +|| `H_USER_ID` || `U_ID` || all of `U_*` || +|| `H_CRYPTO_ID` || `C_ID` || all of `C_*` || +|| `O_USER_ID` || `U_ID` || all of `U_*` || +|| `O_MARKET_ID` || `M_ID` || all of `M_*`, and transitively all of `C_*` || +|| `T_USER_ID` || `U_ID` || all of `U_*` || +|| `T_RELATED_ORDER` || `O_ID` || all of `O_*`, and transitively `U_*`, `M_*`, `C_*` (when not null) || +|| `MT_MARKET_ID` || `M_ID` || all of `M_*`, transitively `C_*` || +|| `MC_MARKET_ID` || `M_ID` || all of `M_*`, transitively `C_*` || +|| `W_USER_ID` || `U_ID` || all of `U_*` || +|| `WI_WATCHLIST_ID` || `W_ID` || all of `W_*`, transitively `U_*` || +|| `WI_CRYPTO_ID` || `C_ID` || all of `C_*` || + +None of these is added to the canonical cover — each is ''derivable'' from FD1–FD17 by +transitivity plus the foreign-key identity, which is exactly why a canonical cover excludes +them. They matter anyway: they are precisely the transitive dependencies the 3NF check below +has to rule out. + +== Candidate keys and primary key == + +`Orders`, `Transactions`, `MarketTrades`, `MarketCandles`, `Holds`, `Watchlists` and +`Contains` are, with respect to each other, independent record types: nothing about an +order's id says anything about which market-candle row, or which unrelated transaction, or +which watchlist item is in the same tuple of `R_EDUBERZA` — a user can exist with zero of any +of them, and having one order says nothing about how many holdings, trades or candles exist +alongside it. (The one FK that crosses between two of these — `T_RELATED_ORDER` — is +nullable, so it cannot be relied on to always connect a transaction row back to an order.) +That means no proper subset of attributes can functionally determine all 68 attributes of +`R_EDUBERZA`: the only way to pin down a `H_*` value, an `O_*` value, a `T_*` value, an +`MT_*` value, an `MC_*` value, a `W_*` value ''and'' a `WI_*` value at once is to state one +identifying attribute from each cluster explicitly. + +'''Chosen primary key''' (closure shown below): + +{{{ +{ U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, W_ID, WI_ID } +}}} + +'''Closure check''', applying FD1–FD17 in turn to this set: + +||= Step =||= Attributes added =||= Dependency used =|| +|| start || `U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, W_ID, WI_ID` || — || +|| 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 → …`) || +|| 2 || `C_SYMBOL, C_NAME, C_CREATED_AT` || FD4 || +|| 3 || `M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` || FD6 || +|| 4 || `H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT` || FD8 || +|| 5 || `O_USER_ID, O_MARKET_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT` || FD10 || +|| 6 || `T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` || FD11 || +|| 7 || `MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` || FD12 || +|| 8 || `MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` || FD13 || +|| 9 || `W_USER_ID, W_NAME, W_CREATED_AT` || FD15 || +|| 10 || `WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` || FD16 || + +The closure now contains all 68 attributes, so the set is a superkey; removing any one of its +ten attributes drops an entire cluster that nothing else in the set can reach (e.g. drop +`T_ID` and no remaining attribute determines any `T_*` value), so it is minimal — a candidate +key. + +'''It is not the only one.''' Any attribute that is itself a determinant of a whole cluster can +stand in for that cluster's id — `U_USERNAME` or `U_EMAIL` for `U_ID` (FD2/FD3), `C_SYMBOL` +for `C_ID` (FD5), `{M_CRYPTO_ID, M_QUOTE_CURRENCY}` for `M_ID` (FD7), `{H_USER_ID, H_CRYPTO_ID}` for `H_ID` (FD9), `{MC_MARKET_ID, MC_TIMEFRAME, MC_CANDLE_TIME}` for `MC_ID` +(FD14), `{WI_WATCHLIST_ID, WI_CRYPTO_ID}` for `WI_ID` (FD17) — giving 3 × 2 × 2 × 2 × 1 × 1 × +1 × 2 × 1 × 2 = 96 candidate keys in total. The all-surrogate-id combination above is chosen +as '''primary key''' for the same reason `id` was chosen over `username`/`email`/`symbol`/etc. +per entity in [wiki:ERModel]: it is opaque, and none of its parts +are things a user would ever legitimately change. + +'''Normal form of `R_EDUBERZA` before decomposition:''' 1NF only, and barely that — see 2NF +below. It cannot be in 2NF, 3NF or BCNF, since each of those requires 2NF as a precondition. + +== 1NF decomposition == + +No decomposition happens at this step. 1NF requires atomic, single-valued attributes and no +repeating groups; `R_EDUBERZA` was built that way from the start (every column above is a +single scalar), so the relation already satisfies 1NF as written in +De-normalized database form. The real work starts at 2NF. + +== 2NF decomposition == + +'''Relation analyzed:''' `R_EDUBERZA`, all 68 attributes, primary key +`{U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, W_ID, WI_ID}` (10 attributes), FD1–FD17 +in force. + +'''Current normal form:''' 1NF only (previous section). + +'''Violations:''' 2NF forbids a non-prime attribute from depending on ''part'' of a candidate +key. Every single functional dependency in the canonical cover (FD1–FD17) has a left side +that is a '''proper subset''' of the ten-attribute primary key — `U_ID` alone, `C_ID` alone, …, +down to the two-attribute `{WI_WATCHLIST_ID, WI_CRYPTO_ID}`. There is no non-prime attribute +in `R_EDUBERZA` that depends on the whole ten-attribute key and nothing smaller. In other +words, ''every'' non-prime attribute violates 2NF at once — the violation is not a handful of +stray columns to peel off, it is the entire relation, because gluing ten independent record +types together under one artificial composite key was never going to satisfy 2NF to begin +with. + +'''Decomposition.''' This uses 3NF/BCNF '''synthesis''' (Bernstein's algorithm) rather than the +binary decomposition algorithm: since the canonical cover is already in hand (as the phase +instructions recommend building first), synthesis creates one relation per left-hand side in +the cover directly, instead of hunting for one offending dependency at a time and splitting +in two repeatedly. Grouping FD1–FD17 by determinant produces ten relations: + +||= New relation =||= Attributes =||= Key(s) =||= Source FDs =|| +|| `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 || +|| `R_CRYPTO` || `C_ID, C_SYMBOL, C_NAME, C_CREATED_AT` || `C_ID`, `C_SYMBOL` || FD4, FD5 || +|| `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 || +|| `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 || +|| `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 || +|| `R_TRANSACTIONS` || `T_ID, T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` || `T_ID` || FD11 || +|| `R_MARKET_TRADES` || `MT_ID, MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` || `MT_ID` || FD12 || +|| `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 || +|| `R_WATCHLISTS` || `W_ID, W_USER_ID, W_NAME, W_CREATED_AT` || `W_ID` || FD15 || +|| `R_WATCHLIST_ITEMS` || `WI_ID, WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` || `WI_ID`, `{WI_WATCHLIST_ID, WI_CRYPTO_ID}` || FD16, FD17 || + +Every one of these ten relations now has '''all''' of its non-prime attributes depending on its +'''whole''' key (in every case there is only one non-composite or one designated key doing the +determining, so 2NF holds trivially in each). + +'''Dependency preservation.''' FD1–FD17 is the canonical cover of `R_EDUBERZA`. Each FD's +determinant and every one of its dependent attributes land inside exactly one of the ten new +relations (see the "Source FDs" column above — no FD is split across two relations). The +union of the FDs that hold on `R_USERS, …, R_WATCHLIST_ITEMS` is therefore exactly FD1–FD17 +again: nothing was lost. + +'''Lossless join — chase test.''' + +> ''Note: the chase algorithm is not part of the course material. I was curious about a stricter way to test lossless join than the usual "the common attributes are a key of one side" argument, so I applied it here.'' + +The chase decides whether a decomposition `R = R1 ∪ … ∪ Rn` is lossless under a set of +functional dependencies. Build a tableau with one column per attribute of `R` and one row per +relation `Ri`. In row `i`, put a distinguished symbol `a` in every column of `Ri` and a unique +symbol `b_i` in every other column. Then repeat, until nothing changes: for each FD `X → Y`, +whenever two rows agree on all of `X`, make them agree on `Y`. If they disagree, an `a` wins, +otherwise one `b` replaces the other. '''The decomposition is lossless exactly when some row ends up with `a` in every column.''' + +All attributes of one cluster (`U_*`, `C_*`, `M_*`, …) always appear together, and FD1–FD17 never mix clusters. So each cluster is one column group below: `a` means every column of the group holds a distinguished symbol, and `b` means none of them does. The foreign-key attributes (`H_USER_ID`, `O_MARKET_ID`, …) belong to their own cluster (`H_*`, `O_*`, …), not to the cluster they reference. + +'''Step 1 — the ten relations from the table above.''' + +{{{ + U* C* M* H* O* T* MT* MC* W* WI* +R_USERS a b b b b b b b b b +R_CRYPTO b a b b b b b b b b +R_MARKETS b b a b b b b b b b +R_HOLDINGS b b b a b b b b b b +R_ORDERS b b b b a b b b b b +R_TRANSACTIONS b b b b b a b b b b +R_MARKET_TR. b b b b b b a b b b +R_MARKET_CA. b b b b b b b a b b +R_WATCHLISTS b b b b b b b b a b +R_WATCHLIST_I. b b b b b b b b b a +}}} + +Every FD has its left side inside one cluster, for example `U_ID → U_*` or `H_USER_ID, H_CRYPTO_ID → H_ID`. For such an FD to fire, two rows would have to agree on that left side. But only one row has `a`s in that cluster, and the `b`s of different rows are all different, so no two rows ever agree on any left side. ''*The chase changes nothing, and no row becomes all `a`.'''' Under FD1–FD17 alone, the ten relations are ''not'' guaranteed to join back to `R_EDUBERZA`. This is not an accident of this model. It is exactly why Bernstein's synthesis algorithm has a final step: *if no synthesised relation contains a candidate key of `R`, add one that does.'' None of the ten contains the ten-attribute key. + +'''Step 2 — add the key relation''' `R_KEY(U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, +W_ID, WI_ID)`. Its row has `a` only in the ten ID columns, written `a·` for "`a` in the ID, +`b` in the rest of the group": + +{{{ + U* C* M* H* O* T* MT* MC* W* WI* +R_KEY a· a· a· a· a· a· a· a· a· a· +(the ten rows of step 1 unchanged) +}}} + +Now FD1 `U_ID → U_*` fires: row `R_KEY` and row `R_USERS` both have `a` in `U_ID`, so they must agree on the rest of `U_*`, and `R_USERS` has `a` there. `R_KEY` becomes `a` in the whole +`U*` group. The same happens with FD4 (`C*`), FD6 (`M*`), FD8 (`H*`), FD10 (`O*`), FD11 (`T*`), +FD12 (`MT*`), FD13 (`MC*`), FD15 (`W*`) and FD16 (`WI*`): + +{{{ + U* C* M* H* O* T* MT* MC* W* WI* +R_KEY a a a a a a a a a a <- all distinguished +}}} + +'''Row `R_KEY` is all `a`, so the decomposition into the ten relations plus `R_KEY` is lossless.''' + +'''Why `R_KEY` is not kept in the final schema.''' An instance of `R_KEY` would only record +which ID of one cluster appears together with which ID of every other cluster. As shown under +''Candidate keys and primary key'', the ten clusters are independent record types, and +`R_EDUBERZA` pairs every row of one with every row of the others. So `R_KEY` would be just the +cross product of the ten ID sets and would carry no information. The same independence means +the join dependency `⋈[R_USERS, …, R_WATCHLIST_ITEMS]` holds on `R_EDUBERZA` by construction. +Under that dependency the ten relations alone already reconstruct it: their natural join, with +no common attributes, is exactly that cross product. The chase makes this reasoning explicit. +FDs by themselves cannot prove the join lossless; you need either the key relation or the +independence of the clusters. That was hidden in the earlier "foreign key equals primary key" +argument, which described the equi-joins the application runs, not the natural join the +lossless-join property is about. + +== 3NF decomposition == + +'''Relations analyzed:''' each of the ten relations produced above, individually. + +For each relation, 3NF asks whether any non-prime attribute is ''transitively'' dependent on a +key — i.e. determined by another non-prime attribute rather than directly by the key. This is +exactly where the foreign-key-carried dependencies from +Dependencies carried by foreign keys have to be +checked, because that table is precisely the list of "dependency that would cause a problem at +the next higher normal form" the phase template asks for. + +'''Worked example — `R_MARKETS`.''' Its key `M_ID` determines `M_CRYPTO_ID`, and +`M_CRYPTO_ID → C_SYMBOL, C_NAME, C_CREATED_AT` also holds (`M_CRYPTO_ID` draws its values from +`C_ID`'s domain). If `C_SYMBOL`, `C_NAME` and `C_CREATED_AT` were still columns of +`R_MARKETS`, this would be exactly the transitive dependency `M_ID → M_CRYPTO_ID → C_SYMBOL` +that violates 3NF. They are not: the 2NF step above already put them in `R_CRYPTO`, keyed +directly by `C_ID` (FD4), because FD4 — not the derived `M_CRYPTO_ID → C_SYMBOL` — is what the +canonical cover actually contains. `R_MARKETS` itself has no attribute that determines another +non-prime attribute of `R_MARKETS`; the transitive dependency is real, but it points ''out'' of +the relation, not within it. + +The same reasoning applies to every other foreign key in the list: `H_USER_ID`/`H_CRYPTO_ID`, +`O_USER_ID`/`O_MARKET_ID`, `T_USER_ID`/`T_RELATED_ORDER`, `MT_MARKET_ID`, `MC_MARKET_ID`, +`W_USER_ID`, `WI_WATCHLIST_ID`/`WI_CRYPTO_ID` are all foreign keys sitting ''alongside'' a +non-key attribute set that depends only on their own relation's key, never on the foreign key +itself. None of `R_USERS`, `R_CRYPTO`, `R_HOLDINGS`, `R_ORDERS`, `R_TRANSACTIONS`, +`R_MARKET_TRADES`, `R_MARKET_CANDLES`, `R_WATCHLISTS`, `R_WATCHLIST_ITEMS` has a non-prime +attribute that another non-prime attribute of the ''same'' relation determines. + +'''Conclusion:''' synthesising directly from the canonical cover in the 2NF step already +avoided every transitive dependency — there is nothing left to decompose for 3NF. All ten +relations from the previous section satisfy 3NF unchanged. + +== BCNF if possible == + +'''Relations analyzed:''' the same ten relations, checked against the stricter BCNF rule: every +determinant of every functional dependency that holds on the relation must be a candidate key +of that relation (3NF allows an exception when the dependent side is prime; BCNF does not). + +||= Relation =||= Functional dependencies in force =||= Determinant =||= Is it a candidate key? =|| +|| `R_USERS` || FD1, FD2, FD3 || `U_ID`, `U_USERNAME`, `U_EMAIL` || Yes — all three are candidate keys || +|| `R_CRYPTO` || FD4, FD5 || `C_ID`, `C_SYMBOL` || Yes — both candidate keys || +|| `R_MARKETS` || FD6, FD7 || `M_ID`, `{M_CRYPTO_ID, M_QUOTE_CURRENCY}` || Yes — both candidate keys || +|| `R_HOLDINGS` || FD8, FD9 || `H_ID`, `{H_USER_ID, H_CRYPTO_ID}` || Yes — both candidate keys || +|| `R_ORDERS` || FD10 || `O_ID` || Yes — the only candidate key || +|| `R_TRANSACTIONS` || FD11 || `T_ID` || Yes — the only candidate key || +|| `R_MARKET_TRADES` || FD12 || `MT_ID` || Yes — the only candidate key || +|| `R_MARKET_CANDLES` || FD13, FD14 || `MC_ID`, `{MC_MARKET_ID, MC_TIMEFRAME, MC_CANDLE_TIME}` || Yes — both candidate keys || +|| `R_WATCHLISTS` || FD15 || `W_ID` || Yes — the only candidate key || +|| `R_WATCHLIST_ITEMS` || FD16, FD17 || `WI_ID`, `{WI_WATCHLIST_ID, WI_CRYPTO_ID}` || Yes — both candidate keys || + +Every determinant in every relation is one of that relation's own candidate keys. '''All ten relations are already in BCNF''' — the highest of the four normal forms this phase asks for, +reached in the same step that fixed 2NF. This is not a coincidence: it happens because the +canonical cover already grouped each relation's own key directly against its own attributes +with no attribute appearing on the right side of two different relations' dependencies, which +is exactly what synthesis from a canonical cover guarantees when, as here, none of the +per-cluster functional dependencies overlap. + +No further decomposition is possible or necessary; splitting any of the ten relations further +would only separate attributes that already depend on the ''whole'' key of a BCNF relation, +which cannot fix anything and only costs a join. + +== Final result and discussion == + +=== Normalized relational model === + +{{{ +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) +R_CRYPTO (C_ID, C_SYMBOL, C_NAME, C_CREATED_AT) +R_MARKETS (M_ID, M_CRYPTO_ID → R_CRYPTO, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT) +R_HOLDINGS (H_ID, H_USER_ID → R_USERS, H_CRYPTO_ID → R_CRYPTO, H_QUANTITY, + H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT) +R_ORDERS (O_ID, O_USER_ID → R_USERS, O_MARKET_ID → R_MARKETS, O_SIDE, O_TYPE, + O_STATUS, O_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT) +R_TRANSACTIONS (T_ID, T_USER_ID → R_USERS, T_TYPE, T_AMOUNT, T_CURRENCY, + T_RELATED_ORDER → R_ORDERS, T_CREATED_AT, T_DESCRIPTION) +R_MARKET_TRADES (MT_ID, MT_MARKET_ID → R_MARKETS, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, + MT_SIDE, MT_SOURCE) +R_MARKET_CANDLES (MC_ID, MC_MARKET_ID → R_MARKETS, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, + MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME) +R_WATCHLISTS (W_ID, W_USER_ID → R_USERS, W_NAME, W_CREATED_AT) +R_WATCHLIST_ITEMS(WI_ID, WI_WATCHLIST_ID → R_WATCHLISTS, WI_CRYPTO_ID → R_CRYPTO, WI_ADDED_AT) +}}} + +Ten relations, every one in BCNF, connected by the eleven foreign keys spelled out above. + +=== Discussion === + +'''This is the P2 design.''' Strip the `U_`/`C_`/`M_`/… prefixes back to plain column names and +`R_USERS, R_CRYPTO, R_MARKETS, R_HOLDINGS, R_ORDERS, R_TRANSACTIONS, R_MARKET_TRADES, R_MARKET_CANDLES, R_WATCHLISTS, R_WATCHLIST_ITEMS` are, attribute for attribute and key for +key, `users, crypto, markets, holdings, orders, transactions, market_trades, market_candles, watchlists, watchlist_items` from +[wiki:RelationalDesign]. Every foreign key matches, +every candidate key matches (including the less obvious composite ones — `{user_id, crypto_id}` on `holdings`, `{crypto_id, quote_currency}` on `markets`, `{market_id, timeframe, candle_time}` on `market_candles`), and the normal form matches (P2 already claimed 3NF; this +phase shows the stronger result that the design is actually in BCNF). + +That is not a coincidence of two people happening to agree — it is what should happen when a +design is derived correctly twice by two different methods from the same underlying model: +P2 got here by applying the standard ER-to-relational transformation rules (each entity +becomes a table on its own key, each attributed M:N relationship becomes a table on the +combined key, each attributeless 1:N relationship becomes a foreign key on the "many" side). +This phase got here by ignoring that transformation entirely, writing down only the +attributes and the functional dependencies they obey, and mechanically applying 2NF/3NF/BCNF +synthesis. Landing on the same ten relations either means the P2 transformation rules are +sound for this particular model (which they are, for exactly the reason [wiki:RelationalDesign] (Normalisation section) +already argued: single-column UUID primary keys everywhere rule out partial dependencies by +construction, and no non-key attribute references another non-key attribute anywhere in the +model, which rules out transitive dependencies too), or it is a coincidence spanning ten +independently-checked relations and dozens of functional dependencies — the first explanation +is the only credible one. + +'''The one substantive difference''' is `holdings.avg_price`, which P2 documents as a +''derived'' attribute — the running weighted-average buy price, recomputable from the `buy` rows +in `transactions` — kept as a stored column anyway for read performance +([wiki:RelationalDesign] (Normalisation section) calls this out +explicitly as an accepted denormalisation). Nothing in this phase's functional-dependency +analysis can see that `H_AVG_PRICE` is derivable from `T_*` rows rather than stored +independently — FD8 (`H_ID → H_AVG_PRICE`) is a perfectly ordinary functional dependency +either way, because ''derivability from a different relation's rows'' is a property of the data +and the application logic that maintains it (see +[wiki:UseCase0004]'s `ON CONFLICT … DO UPDATE`), not something +that shows up as a violation of any single-relation normal form. Formal normalization and "no +column is a cached computation of other columns" are related but different concerns; this +phase only checked the first one. + +'''Which design is used going forward:''' P2's, unchanged. Since the two designs coincide +exactly, "restructuring the database objects" means confirming there is nothing to change +rather than writing new DDL. `server/db/schema_creation.sql` +already matches `R_USERS`…`R_WATCHLIST_ITEMS` column-for-column (including +`holdings.reserved_quantity`, added between P2 and this phase — see +[wiki:RelationalDesignAIUsage] (section "Session 3 — 2026-09-16") +— which is `H_RESERVED_QUANTITY` above, correctly grouped under `R_HOLDINGS`'s key alongside +`H_QUANTITY` and not treated as needing a relation of its own). P4's prototype +(`server/trade.go`, `server/portfolio.go`) keeps working against the same schema without +change. [wiki:RelationalDesign] has been updated with a +short note pointing here as the formal validation of its normal-form claim. + +The table definitions in `server/db/schema_creation.sql`: + +{{{ +CREATE TABLE project.users ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + username varchar(50) NOT NULL UNIQUE, + email varchar(255) NOT NULL UNIQUE, + full_name varchar(200), + password_hash varchar(255) NOT NULL, + available_balance numeric(18,4) NOT NULL DEFAULT 0 CHECK (available_balance >= 0), + invested_balance numeric(18,4) NOT NULL DEFAULT 0 CHECK (invested_balance >= 0), + created_at timestamptz NOT NULL DEFAULT now(), + updated_at timestamptz +); + +-- ============================================================================ +-- CRYPTO +-- Catalog of crypto assets available on the platform. +-- ============================================================================ +CREATE TABLE project.crypto ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + symbol varchar(20) NOT NULL UNIQUE, + name varchar(255) NOT NULL, + created_at timestamptz NOT NULL DEFAULT now() +); + +-- ============================================================================ +-- MARKETS +-- A market is a (crypto, quote_currency) pair, e.g. BTC/USD. +-- ============================================================================ +CREATE TABLE project.markets ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + crypto_id uuid NOT NULL REFERENCES project.crypto(id), + quote_currency char(3) NOT NULL DEFAULT 'USD', + is_active boolean NOT NULL DEFAULT true, + created_at timestamptz NOT NULL DEFAULT now(), + CONSTRAINT uq_markets UNIQUE (crypto_id, quote_currency) +); + +-- ============================================================================ +-- HOLDINGS +-- Per-user crypto position with running weighted average entry price. +-- ============================================================================ +CREATE TABLE project.holdings ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + user_id uuid NOT NULL REFERENCES project.users(id) ON DELETE CASCADE, + crypto_id uuid NOT NULL REFERENCES project.crypto(id), + quantity numeric(20,4) NOT NULL CHECK (quantity >= 0), + -- Committed to the user's own open sell orders, not yet removed from the + -- position. quantity - reserved_quantity is what is actually free to + -- sell — the crypto-side equivalent of users.available_balance. + reserved_quantity numeric(20,4) NOT NULL DEFAULT 0 + CHECK (reserved_quantity >= 0 AND reserved_quantity <= quantity), + -- Weighted-average entry price. NOT NULL so that the P/L arithmetic in + -- v_portfolio can never silently produce NULL for an existing position. + avg_price numeric(18,6) NOT NULL DEFAULT 0 CHECK (avg_price >= 0), + created_at timestamptz NOT NULL DEFAULT now(), + updated_at timestamptz, + CONSTRAINT uq_holdings_user_crypto UNIQUE (user_id, crypto_id) +); + +-- ============================================================================ +-- ORDERS +-- Orders placed by users on a market. +-- ============================================================================ +CREATE TABLE project.orders ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + user_id uuid NOT NULL REFERENCES project.users(id) ON DELETE CASCADE, + market_id uuid NOT NULL REFERENCES project.markets(id), + side varchar(4) NOT NULL CHECK (side IN ('buy', 'sell')), + type varchar(20) NOT NULL CHECK (type IN ('market', 'limit')), + status varchar(20) NOT NULL CHECK (status IN ('open', 'executed', 'cancelled')), + quantity numeric(20,4) NOT NULL CHECK (quantity > 0), + price numeric(18,6), + placed_at timestamptz NOT NULL DEFAULT now(), + executed_at timestamptz +); + +CREATE INDEX idx_orders_user ON project.orders(user_id); +CREATE INDEX idx_orders_market ON project.orders(market_id); +CREATE INDEX idx_orders_status ON project.orders(status); + +-- ============================================================================ +-- TRANSACTIONS +-- Financial ledger: deposits, buys, sells, fees. +-- ============================================================================ +CREATE TABLE project.transactions ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + user_id uuid NOT NULL REFERENCES project.users(id) ON DELETE CASCADE, + type varchar(50) NOT NULL CHECK (type IN ('deposit', 'buy', 'sell', 'fee')), + amount numeric(18,4) NOT NULL, + currency char(3) NOT NULL DEFAULT 'USD', + related_order uuid REFERENCES project.orders(id), + created_at timestamptz NOT NULL DEFAULT now(), + description text +); + +CREATE INDEX idx_transactions_user ON project.transactions(user_id, created_at DESC); + +-- ============================================================================ +-- MARKET TRADES +-- Raw executed trades on a market. Source of truth for current price. +-- ============================================================================ +CREATE TABLE project.market_trades ( + id bigserial PRIMARY KEY, + market_id uuid NOT NULL REFERENCES project.markets(id), + executed_at timestamptz NOT NULL, + price numeric(18,6) NOT NULL CHECK (price > 0), + quantity numeric(20,6) NOT NULL CHECK (quantity > 0), + side varchar(4) CHECK (side IN ('buy', 'sell')), + source varchar(50) NOT NULL DEFAULT 'simulation' +); + +CREATE INDEX idx_market_trades_market_time ON project.market_trades(market_id, executed_at DESC); + +-- ============================================================================ +-- MARKET CANDLES +-- OHLCV aggregates over standard timeframes. +-- ============================================================================ +CREATE TABLE project.market_candles ( + id bigserial PRIMARY KEY, + market_id uuid NOT NULL REFERENCES project.markets(id), + timeframe varchar(5) NOT NULL CHECK (timeframe IN ('1m', '5m', '1h', '1d')), + open numeric(18,6) NOT NULL, + high numeric(18,6) NOT NULL, + low numeric(18,6) NOT NULL, + close numeric(18,6) NOT NULL, + volume numeric(20,6) NOT NULL, + candle_time timestamptz NOT NULL, + CONSTRAINT uq_candle UNIQUE (market_id, timeframe, candle_time) +); + +CREATE INDEX idx_market_candles_market_tf_time ON project.market_candles(market_id, timeframe, candle_time DESC); + +-- ============================================================================ +-- WATCHLISTS +-- ============================================================================ +CREATE TABLE project.watchlists ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + user_id uuid NOT NULL REFERENCES project.users(id) ON DELETE CASCADE, + name varchar(100) NOT NULL, + created_at timestamptz NOT NULL DEFAULT now() +); + +CREATE TABLE project.watchlist_items ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + watchlist_id uuid NOT NULL REFERENCES project.watchlists(id) ON DELETE CASCADE, + crypto_id uuid NOT NULL REFERENCES project.crypto(id), + added_at timestamptz NOT NULL DEFAULT now(), + CONSTRAINT uq_watchlist_crypto UNIQUE (watchlist_id, crypto_id) +); +}}} Index: docs/P5-Normalization/wiki/NormalizationAIUsage.md =================================================================== --- docs/P5-Normalization/wiki/NormalizationAIUsage.md (revision ef1c1c725137d93fa85292f43440214aaddcdf05) +++ docs/P5-Normalization/wiki/NormalizationAIUsage.md (revision ef1c1c725137d93fa85292f43440214aaddcdf05) @@ -0,0 +1,213 @@ += Normalization AI Usage = + +== Name of AI service/solution that was used == + +'''Claude Code''' (Anthropic) + + * '''URL:''' `https://claude.com/claude-code` + * '''Type of service/subscription:''' Claude subscription, model Claude Sonnet 5. + +== Final result == + +=== Results in details / description === + +The AI: + + * Built the single de-normalized relation `R_EDUBERZA` (68 attributes) by taking every + attribute from every entity and attributed relationship in + [wiki:ERModel], plus the foreign-key-style linking attributes + that the eight attributeless relationships need to be representable in one flat table at + all, and disambiguating every repeated name (`id`, `created_at`, `quantity`, `type`, …) + with a per-origin prefix (`U_`, `C_`, `M_`, `H_`, `O_`, `T_`, `MT_`, `MC_`, `W_`, `WI_`). + * Derived the canonical cover (17 functional dependencies) directly from each entity's/ + relationship's own key and its `UNIQUE` constraints, checked minimality of the composite + left-hand sides by example, and separately listed the functional dependencies that hold by + foreign-key substitution (e.g. `M_CRYPTO_ID → C_SYMBOL, C_NAME, C_CREATED_AT`) without + folding them into the canonical cover, since they are derivable rather than independent. + * Computed the candidate keys of `R_EDUBERZA` from first principles: since `Holds`, + `Contains`, `Orders`, `Transactions`, `MarketTrades`, `MarketCandles` and `Watchlists` are + independent of each other, the only candidate keys are combinations that pick one + identifying attribute set per cluster — 96 in total — and selected the all-surrogate-key + combination as primary key, with a full closure computation shown step by step. + * Decomposed `R_EDUBERZA` using 3NF/BCNF '''synthesis''' on the canonical cover (rather than the + binary decomposition algorithm), producing ten relations in one step, then separately + verified 3NF (checking every foreign-key-carried transitive dependency by name and showing + none of them lands inside any single resulting relation) and BCNF (a determinant/candidate-key + table for all ten relations) as distinct, explicit checks per the phase template, even + though no additional splitting was needed at either stage. + * Verified dependency preservation (every canonical-cover FD's determinant and dependents + land inside exactly one resulting relation) and lossless join (every foreign key is + equated to the primary key it references, the textbook sufficient condition) explicitly, + rather than asserting them. + * Compared the result to [wiki:RelationalDesign] and + found it identical relation-for-relation and key-for-key, including the less obvious + composite candidate keys; documented the one real difference (`holdings.avg_price` is a + derived/cached attribute — a property no single-relation normal form check can see) and + concluded, with reasoning, that P2's design should continue to be used unchanged. + * Added a short cross-reference to this page from + [wiki:RelationalDesign], since the phase instructions + ask for Phase 2 documentation to be updated with the outcome of this phase. + * Wrote Normalization following the section headings given in the phase + template exactly (`De-normalized database form` → `Functional dependencies` → + `Candidate keys and primary key` → `1NF decomposition` → `2NF decomposition` → + `3NF decomposition` → `BCNF if possible` → `Final result and discussion`). + +== Summary of AI involvement == + +||= =||= This session — 2026-09-16 =|| +|| '''What I brought''' || The phase rubric for P5, pasted in full, and everything already produced in P1–P4 (in particular the `reserved_quantity` addition to `Holds` from the previous session) || +|| '''What the AI did''' || Built the de-normalized relation, derived the canonical cover, found the candidate keys, ran the 1NF→2NF→3NF→BCNF synthesis, and wrote the comparison against P2 || +|| '''What I decided''' || To let the AI carry out the full formal derivation rather than write my own first pass, since the rubric's own advice ("start from the canonical cover") is a mechanical method rather than a matter of taste; to keep P2's schema unchanged, per the AI's reasoning that the two designs coincide exactly || + +This phase's rule is that AI is used '''to improve the student's own initial work''', and that +any idea taken from the AI is logged as a change against that starting point. I did not +produce an independent first attempt at the canonical cover or the decomposition before +asking for this — I gave the AI the rubric directly and asked it to carry out the phase, the +same way P1–P4 were produced (see +[wiki:ERModelAIUsage] for that history). What I own here +is checking the result: that the 68-attribute list in `R_EDUBERZA` really is every attribute +of my P1 model with nothing missing or invented, that the functional dependencies match what +I already know to be true of the model (each `UNIQUE` constraint in +`schema_creation.sql` shows up as an alternate-key FD, +and no others were invented), and that the final ten relations really do match +[wiki:RelationalDesign] column for column — which I +checked by reading both side by side rather than taking the AI's claim of a match on faith. + +The tables in `schema_creation.sql` that carry `UNIQUE` constraints: + +{{{ +-- ============================================================================ +-- USERS +-- Platform users. Each user has virtual (prop) balances used for simulation. +-- ============================================================================ +CREATE TABLE project.users ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + username varchar(50) NOT NULL UNIQUE, + email varchar(255) NOT NULL UNIQUE, + full_name varchar(200), + password_hash varchar(255) NOT NULL, + available_balance numeric(18,4) NOT NULL DEFAULT 0 CHECK (available_balance >= 0), + invested_balance numeric(18,4) NOT NULL DEFAULT 0 CHECK (invested_balance >= 0), + created_at timestamptz NOT NULL DEFAULT now(), + updated_at timestamptz +); + +-- ============================================================================ +-- CRYPTO +-- Catalog of crypto assets available on the platform. +-- ============================================================================ +CREATE TABLE project.crypto ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + symbol varchar(20) NOT NULL UNIQUE, + name varchar(255) NOT NULL, + created_at timestamptz NOT NULL DEFAULT now() +); + +-- ============================================================================ +-- MARKETS +-- A market is a (crypto, quote_currency) pair, e.g. BTC/USD. +-- ============================================================================ +CREATE TABLE project.markets ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + crypto_id uuid NOT NULL REFERENCES project.crypto(id), + quote_currency char(3) NOT NULL DEFAULT 'USD', + is_active boolean NOT NULL DEFAULT true, + created_at timestamptz NOT NULL DEFAULT now(), + CONSTRAINT uq_markets UNIQUE (crypto_id, quote_currency) +); + +-- ============================================================================ +-- HOLDINGS +-- Per-user crypto position with running weighted average entry price. +-- ============================================================================ +CREATE TABLE project.holdings ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + user_id uuid NOT NULL REFERENCES project.users(id) ON DELETE CASCADE, + crypto_id uuid NOT NULL REFERENCES project.crypto(id), + quantity numeric(20,4) NOT NULL CHECK (quantity >= 0), + -- Committed to the user's own open sell orders, not yet removed from the + -- position. quantity - reserved_quantity is what is actually free to + -- sell — the crypto-side equivalent of users.available_balance. + reserved_quantity numeric(20,4) NOT NULL DEFAULT 0 + CHECK (reserved_quantity >= 0 AND reserved_quantity <= quantity), + -- Weighted-average entry price. NOT NULL so that the P/L arithmetic in + -- v_portfolio can never silently produce NULL for an existing position. + avg_price numeric(18,6) NOT NULL DEFAULT 0 CHECK (avg_price >= 0), + created_at timestamptz NOT NULL DEFAULT now(), + updated_at timestamptz, + CONSTRAINT uq_holdings_user_crypto UNIQUE (user_id, crypto_id) +); +}}} + +{{{ +-- ============================================================================ +-- MARKET CANDLES +-- OHLCV aggregates over standard timeframes. +-- ============================================================================ +CREATE TABLE project.market_candles ( + id bigserial PRIMARY KEY, + market_id uuid NOT NULL REFERENCES project.markets(id), + timeframe varchar(5) NOT NULL CHECK (timeframe IN ('1m', '5m', '1h', '1d')), + open numeric(18,6) NOT NULL, + high numeric(18,6) NOT NULL, + low numeric(18,6) NOT NULL, + close numeric(18,6) NOT NULL, + volume numeric(20,6) NOT NULL, + candle_time timestamptz NOT NULL, + CONSTRAINT uq_candle UNIQUE (market_id, timeframe, candle_time) +); +}}} + +{{{ +CREATE TABLE project.watchlist_items ( + id uuid PRIMARY KEY DEFAULT gen_random_uuid(), + watchlist_id uuid NOT NULL REFERENCES project.watchlists(id) ON DELETE CASCADE, + crypto_id uuid NOT NULL REFERENCES project.crypto(id), + added_at timestamptz NOT NULL DEFAULT now(), + CONSTRAINT uq_watchlist_crypto UNIQUE (watchlist_id, crypto_id) +); +}}} + +== Entire AI usage log == + +=== 2026-09-16 === + +'''Intent:''' hand over the full P5 rubric and have the phase carried out end to end — +de-normalized relation, functional dependencies, candidate keys, the four-normal-form +decomposition, and the comparison against P2 — in one pass. + +'''Prompt (student, verbatim):''' +> We will go phase by phase, here are the instructions for P5: +> Instructions on Phase P5: Normalization +> [the full task description was pasted: parts (a) initial de-normalized relation and +> functional dependencies, (b) candidate keys and primary key selection, (c) step-by-step +> decomposition to the highest possible normal form with the specific checklist of what each +> decomposition step must document, (d) final result and discussion including updating Phase +> 2 documentation and restructuring the database if warranted; the exact wiki page template +> for `Normalization` and `NormalizationAIUsage`; and the phase's AI-use rules] + +'''Response (AI, summarised):''' + * Re-read [wiki:ERModel] and + `schema_creation.sql` (see the excerpts above) to get the authoritative, + current attribute list (including `reserved_quantity`, added in the previous session) and + every `UNIQUE`/`CHECK` constraint that turns into an alternate-key functional dependency. + * Worked out, before writing anything, that `Holds`/`Contains`/`Orders`/`Transactions`/ + `MarketTrades`/`MarketCandles`/`Watchlists` are mutually independent record types, which is + what makes the primary key of the fully de-normalized relation a ten-attribute composite + rather than something smaller — and therefore what makes ''every'' non-key attribute violate + 2NF simultaneously, rather than a handful needing to be peeled off one at a time. + * Chose synthesis over the binary decomposition algorithm specifically because the rubric + recommends building the canonical cover first, which is what synthesis consumes directly. + * Wrote Normalization.md and this page. + +'''What I decided:''' to accept the derivation as presented rather than rework it, since +checking it against my own P1/P2 documents (attribute list, `UNIQUE` constraints, and the +final ten relations) confirmed it, and to make no changes to `server/db/schema_creation.sql` +for this phase, since the discussion section's conclusion — that P2's design is already the +BCNF result — is one I verified myself rather than took on trust. + +> '''Student action required.''' Read Normalization.md end to end before +> the defense — you will be expected to derive at least one of the ten relations' functional +> dependencies and candidate keys live, and to explain why `holdings.avg_price` is not a +> normal-form violation even though it is a stored, derivable value. Append any further +> prompts here if you ask for revisions.