| 76 | | written down. Whether it satisfies anything beyond that is exactly what the rest of this page |
| | 89 | written down. |
| | 90 | |
| | 91 | == Functional dependencies == |
| | 92 | |
| | 93 | At this point `R_EDUBERZA` is just a set of attributes. It has '''no keys yet'''. `U_ID`, |
| | 94 | `O_ID`, … are ordinary attributes of this relation, and which attribute sets are keys of |
| | 95 | `R_EDUBERZA` is computed in the next section, from the |
| | 96 | dependencies below. Each dependency is justified by a rule of the domain, as described in |
| | 97 | the data requirements of [wiki:ERModel]. The rules are of four |
| | 98 | kinds: |
| | 99 | |
| | 100 | * '''(I) Identification.''' Every value of an identifier (`U_ID`, `C_ID`, …) is given to exactly one real object: one user, one crypto, one order. That object has exactly one username, one balance, one price, and so on. So the identifier's value fixes those values. |
| | 101 | * '''(R) 1:N relationship.''' In a 1:N relationship, each object on the N side is linked to exactly one object on the 1 side. So the N side's identifier fixes the 1 side's identifier. Example: an order is placed by exactly one user (`Places`), so `O_ID → U_ID`. The opposite direction does not hold: a user places many orders, so `U_ID ↛ O_ID`. |
| | 102 | * '''(U) Uniqueness rule.''' A rule of the form "at most one X per Y and Z" gives `Y, Z → X`. |
| | 103 | * '''(N) Unique natural attribute.''' No two users share a username or an email, and no two cryptos share a symbol. |
| | 104 | |
| | 105 | '''Only rules of the ER model are used.''' The dependencies below come from the rules stated in |
| | 106 | [wiki:ERModel] v05 and nothing else. The analysis uses the |
| | 107 | classical definitions (Armstrong's axioms), with no special treatment of `NULL`. Partial |
| | 108 | relationships (`Settles`, `FillsBuy`, `FillsSell`) are discussed where they matter: |
| | 109 | under Canonical cover and in the discussion. |
| | 110 | |
| | 111 | ||= # =||= Functional dependency =||= Rule =||= Why it holds =|| |
| | 112 | || 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 || |
| | 113 | || FD2 || `U_USERNAME → U_ID` || N || usernames are unique || |
| | 114 | || FD3 || `U_EMAIL → U_ID` || N || emails are unique || |
| | 115 | || FD4 || `C_ID → C_SYMBOL, C_NAME, C_CREATED_AT` || I || one crypto, one value of each || |
| | 116 | || FD5 || `C_SYMBOL → C_ID` || N || symbols are unique || |
| | 117 | || FD6 || `M_ID → M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT, C_ID` || I, R || …and a market is `QuotedOn` exactly one crypto || |
| | 118 | || FD7 || `C_ID, M_QUOTE_CURRENCY → M_ID` || U || a crypto is quoted at most once per currency || |
| | 119 | || 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`) || |
| | 120 | || FD9 || `U_ID, C_ID → H_ID` || U || at most one holding per user and crypto || |
| | 121 | || 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`) || |
| | 122 | || 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`) || |
| | 123 | || 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`) || |
| | 124 | || 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`) || |
| | 125 | || 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`) || |
| | 126 | || FD15 || `M_ID, MC_TIMEFRAME, MC_CANDLE_TIME → MC_ID` || U || one candle per market, timeframe and bucket || |
| | 127 | || FD16 || `W_ID → W_NAME, W_CREATED_AT, U_ID` || I, R || …and a watchlist is owned by one user (`Owns`) || |
| | 128 | || 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`) || |
| | 129 | || FD18 || `W_ID, C_ID → WI_ID` || U || an asset appears at most once per watchlist || |
| | 130 | |
| | 131 | '''Dependencies that do ''not'' hold''' are as important, because they are why some attributes |
| | 132 | must be combined in the key later: |
| | 133 | |
| | 134 | * The reverse of every (R) dependency, e.g. `U_ID ↛ O_ID`, `M_ID ↛ MT_ID`, `W_ID ↛ WI_ID`. These are 1:N, not 1:1. |
| | 135 | * `M_ID, MT_EXECUTED_AT ↛ MT_ID`. Two trades on a market can share a timestamp. |
| | 136 | * `U_ID, W_NAME ↛ W_ID`. The model does not require list names to be unique per user. |
| | 137 | * `O_ID_FILLSBUY` and `O_ID_FILLSSELL` determine no other attribute of `R_EDUBERZA` '''by any rule of the ER model'''. The order data (`O_SIDE`, `O_PRICE`, …) describes the order in the `O_ID` column, not the order in a role column. (The database also has a rule that a trade and the orders it fills are on the same market. That rule is a trigger in P7 relating several entity sets, not a rule of the ER model, so it is not used here.) |
| | 138 | |
| | 139 | === Canonical cover === |
| | 140 | |
| | 141 | A canonical (minimal) cover is obtained in three steps. |
| | 142 | |
| | 143 | '''Step 1 — single attribute on the right.''' Each FD above is read as one dependency per |
| | 144 | right-side attribute, e.g. FD6 is `M_ID → M_QUOTE_CURRENCY`, `M_ID → M_IS_ACTIVE`, |
| | 145 | `M_ID → M_CREATED_AT`, `M_ID → C_ID`. |
| | 146 | |
| | 147 | '''Step 2 — no extraneous attribute on the left.''' Only FD7, FD9, FD15 and FD18 have more than one |
| | 148 | attribute on the left. For each one, dropping any attribute makes the rule false: |
| | 149 | |
| | 150 | ||= FD =||= Drop =||= Counter-example (the smaller left side does not determine the right side) =|| |
| | 151 | || FD7 || `M_QUOTE_CURRENCY` || BTC is quoted in USD ''and'' in EUR: one `C_ID`, two markets || |
| | 152 | || || `C_ID` || USD is the quote currency of many markets || |
| | 153 | || FD9 || `C_ID` || one user holds several cryptos || |
| | 154 | || || `U_ID` || one crypto is held by several users || |
| | 155 | || FD15 || `M_ID` || every market has a `1h` candle starting at 10:00 || |
| | 156 | || || `MC_TIMEFRAME` || a market has a `1m` and a `1h` candle both starting at 10:00 || |
| | 157 | || || `MC_CANDLE_TIME` || a market has many `1h` candles || |
| | 158 | || FD18 || `C_ID` || a watchlist has several items || |
| | 159 | || || `W_ID` || a crypto is on several watchlists || |
| | 160 | |
| | 161 | '''Step 3 — no redundant dependency.''' A dependency is redundant if it follows from the others. For |
| | 162 | almost every dependency, its right-side attribute appears on the right of no other |
| | 163 | dependency with a different left side (e.g. nothing but `U_ID` determines |
| | 164 | `U_AVAILABLE_BALANCE`), so it cannot be derived. The candidates worth checking are the |
| | 165 | identifiers that are reached from several places: |
| | 166 | |
| | 167 | * '''`T_ID → U_ID` is redundant.''' It follows by transitivity from `T_ID → O_ID` (FD11) and `O_ID → U_ID` (FD10): a ledger entry's user is the user of the order it settles. It is therefore '''removed''' from FD11. The derivation is valid only for an entry that has an order. Every tuple of `R_EDUBERZA` does have one (see the discussion), so in the de-normalized relation the removal is correct. The consequence for deposits, which have no order, is taken up in the discussion. |
| | 168 | * `H_ID → U_ID`, `H_ID → C_ID`, `WI_ID → W_ID`, `WI_ID → C_ID`, `M_ID → C_ID`, `MT_ID → M_ID`, `MC_ID → M_ID`, `OE_ID → O_ID`, `W_ID → U_ID` and `O_ID → U_ID`, `O_ID → M_ID`: for each, no other dependency with a different left side has that attribute on its right side and a left side reachable from this one, so none can be derived. |
| | 169 | * The four (U) and three (N) dependencies go "backwards" from a non-identifier to an identifier. Nothing else produces an identifier from those attributes, so they are not derivable either. |
| | 170 | |
| | 171 | Grouping the single-attribute dependencies back by left side gives FD1–FD18 as listed, |
| | 172 | except that FD11 loses `U_ID`: |
| | 173 | |
| | 174 | ||= # =||= Functional dependency (canonical cover) =|| |
| | 175 | || FD11 || `T_ID → T_TYPE, T_AMOUNT, T_CURRENCY, T_CREATED_AT, T_DESCRIPTION, O_ID` || |
| | 176 | |
| | 177 | '''FD1–FD18, with this FD11, is the canonical cover.''' From here on, "FD11" means this reduced |
| | 178 | form. |
| | 179 | |
| | 180 | == Candidate keys and primary key == |
| | 181 | |
| | 182 | A candidate key is a minimal set of attributes whose closure under FD1–FD18 is all 66 |
| | 183 | attributes. |
| | 184 | |
| | 185 | '''Attributes that must be in every key.''' `T_ID`, `OE_ID` and `MT_ID` appear on the right side |
| | 186 | of no dependency. Nothing determines them, so every key must contain them. |
| | 187 | |
| | 188 | '''Closure of `{T_ID, OE_ID, MT_ID}`:''' |
| | 189 | |
| | 190 | ||= Step =||= Added =||= Using =|| |
| | 191 | || start || `T_ID, OE_ID, MT_ID` || — || |
| | 192 | || 1 || `T_*`, `O_ID` || FD11 || |
| | 193 | || 2 || `OE_*` || FD13 || |
| | 194 | || 3 || `MT_*`, `M_ID`, `O_ID_FILLSBUY`, `O_ID_FILLSSELL` || FD12 || |
| | 195 | || 4 || `O_*`, `U_ID` || FD10 || |
| | 196 | || 5 || `U_*` || FD1 || |
| | 197 | || 6 || `M_*`, `C_ID` || FD6 || |
| | 198 | || 7 || `C_*` || FD4 || |
| | 199 | || 8 || `H_ID` || FD9 (`U_ID` and `C_ID` are both present) || |
| | 200 | || 9 || `H_*` || FD8 || |
| | 201 | |
| | 202 | That is 53 attributes. Still missing are all 8 `MC_` attributes, the 3 `W_` attributes and |
| | 203 | the 2 `WI_` attributes: |
| | 204 | |
| | 205 | * '''`MC_`:''' only `MC_ID` determines them (FD14), and `MC_ID` is reached only by FD15, which needs `M_ID` (already present), `MC_TIMEFRAME` and `MC_CANDLE_TIME`. So the key must add either `MC_ID` or both `MC_TIMEFRAME` and `MC_CANDLE_TIME`. Neither of those two alone is enough. |
| | 206 | * '''`W_` and `WI_`:''' `WI_ID` gives `W_ID` (FD17), and `W_ID` gives `WI_ID` together with `C_ID`, which is already present (FD18). So adding either `WI_ID` or `W_ID` gives all five. |
| | 207 | |
| | 208 | '''Candidate keys''' (each one's closure is all 66 attributes, and removing any member breaks |
| | 209 | that, by the argument above): |
| | 210 | |
| | 211 | ||= Key =||= Attributes =|| |
| | 212 | || '''K1''' || `T_ID, OE_ID, MT_ID, MC_ID, WI_ID` || |
| | 213 | || K2 || `T_ID, OE_ID, MT_ID, MC_ID, W_ID` || |
| | 214 | || K3 || `T_ID, OE_ID, MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME, WI_ID` || |
| | 215 | || K4 || `T_ID, OE_ID, MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME, W_ID` || |
| | 216 | |
| | 217 | '''Primary key: K1.''' It consists only of identifiers, and it is the key that remains at the |
| | 218 | end of the decomposition below. |
| | 219 | |
| | 220 | '''Prime attributes''' (in at least one candidate key): `T_ID, OE_ID, MT_ID, MC_ID, |
| | 221 | MC_TIMEFRAME, MC_CANDLE_TIME, W_ID, WI_ID`. The other 58 attributes are '''non-prime'''. The |
| | 222 | difference matters: 2NF and 3NF only restrict dependencies of non-prime attributes, and BCNF |
| | 223 | restricts all of them. |
| | 224 | |
| | 225 | In words, a tuple of `R_EDUBERZA` puts together one ledger entry, one order event, one |
| | 226 | trade, one candle and one watchlist item. Everything else in the tuple (the user, the order, |
| | 227 | the market, the crypto, the holding, the watchlist) follows from those five. |
| | 228 | |
| | 229 | '''Normal form of `R_EDUBERZA`:''' 1NF only. It is not in 2NF, because, for example, `T_AMOUNT` |
| | 230 | depends on `T_ID` alone, a proper part of K1. |
| | 231 | |
| | 232 | == 1NF decomposition == |
| | 233 | |
| | 234 | No decomposition is needed. Every attribute of `R_EDUBERZA` is atomic and single-valued, and |
| | 235 | the relation has no repeating groups (see |
| | 236 | De-normalized database form). |
| | 237 | |
| | 238 | == 2NF decomposition == |
| | 239 | |
| | 240 | === How every step is described and checked === |
| | 241 | |
| | 242 | Each step of 2NF, 3NF and BCNF below lists, in this order: the relation analyzed, its |
| | 243 | dependencies, its candidate keys and primary key, and its normal form; the dependency that |
| | 244 | violates the next normal form and is used for the split; the two resulting relations, each |
| | 245 | with its dependencies, keys and normal form; and the dependency-preservation and lossless-join |
| 79 | | == Functional dependencies == |
| 80 | | |
| 81 | | === Canonical cover === |
| 82 | | |
| 83 | | Read directly off the model: each entity's/relationship's own key determines its own |
| 84 | | attributes, nothing more. This is already minimal — no functional dependency below has an |
| 85 | | extraneous attribute on its left side, and no dependent attribute is repeated on the right |
| 86 | | side of more than one dependency, which is what "canonical cover" requires. |
| 87 | | |
| 88 | | ||= # =||= Functional dependency =||= Source =|| |
| 89 | | || 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 || |
| 90 | | || FD2 || `U_USERNAME → U_ID` || Users (`UNIQUE(username)`) || |
| 91 | | || FD3 || `U_EMAIL → U_ID` || Users (`UNIQUE(email)`) || |
| 92 | | || FD4 || `C_ID → C_SYMBOL, C_NAME, C_CREATED_AT` || Cryptos || |
| 93 | | || FD5 || `C_SYMBOL → C_ID` || Cryptos (`UNIQUE(symbol)`) || |
| 94 | | || FD6 || `M_ID → M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` || Markets || |
| 95 | | || FD7 || `M_CRYPTO_ID, M_QUOTE_CURRENCY → M_ID` || Markets (`UNIQUE(crypto_id, quote_currency)`) || |
| 96 | | || FD8 || `H_ID → H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT` || Holds || |
| 97 | | || FD9 || `H_USER_ID, H_CRYPTO_ID → H_ID` || Holds (`UNIQUE(user_id, crypto_id)`) || |
| 98 | | || 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 || |
| 99 | | || FD11 || `T_ID → T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` || Transactions || |
| 100 | | || FD12 || `MT_ID → MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` || !MarketTrades || |
| 101 | | || FD13 || `MC_ID → MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` || !MarketCandles || |
| 102 | | || FD14 || `MC_MARKET_ID, MC_TIMEFRAME, MC_CANDLE_TIME → MC_ID` || !MarketCandles (`UNIQUE(market_id, timeframe, candle_time)`) || |
| 103 | | || FD15 || `W_ID → W_USER_ID, W_NAME, W_CREATED_AT` || Watchlists || |
| 104 | | || FD16 || `WI_ID → WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` || Contains || |
| 105 | | || FD17 || `WI_WATCHLIST_ID, WI_CRYPTO_ID → WI_ID` || Contains (`UNIQUE(watchlist_id, crypto_id)`) || |
| 106 | | |
| 107 | | '''Minimality, checked by example (Markets):''' could FD7 drop an attribute from its left side? |
| 108 | | `M_CRYPTO_ID` alone does not determine `M_ID` — many markets can reference the same crypto in |
| 109 | | different quote currencies (that is the entire point of the market entity), so two rows can |
| 110 | | share `M_CRYPTO_ID` and disagree on `M_ID`. `M_QUOTE_CURRENCY` alone fails the same way in the |
| 111 | | other direction. Neither attribute is extraneous, so the left side of FD7 cannot shrink. The |
| 112 | | same check applies to FD9, FD14 and FD17, whose composite left sides come directly from the |
| 113 | | `UNIQUE` constraints already justified per-relation in |
| 114 | | [wiki:RelationalDesign]; none of those constraints |
| 115 | | holds on a proper subset of its columns either. |
| 116 | | |
| 117 | | '''No redundant dependency:''' each of FD1–FD17 has a right side that is not implied by any |
| 118 | | other dependency in the set — for instance, nothing outside FD1 mentions `U_AVAILABLE_BALANCE`, |
| 119 | | so FD1 cannot be derived from the rest and cannot be dropped. This set is the canonical cover. |
| 120 | | |
| 121 | | === Dependencies carried by foreign keys === |
| 122 | | |
| 123 | | Six attributes above are foreign keys: `M_CRYPTO_ID`, `H_USER_ID`, `H_CRYPTO_ID`, |
| 124 | | `O_USER_ID`, `O_MARKET_ID`, `T_USER_ID`, `T_RELATED_ORDER`, `MT_MARKET_ID`, `MC_MARKET_ID`, |
| 125 | | `W_USER_ID`, `WI_WATCHLIST_ID`, `WI_CRYPTO_ID` — each one draws its values from the same |
| 126 | | domain as some other attribute's key. Because of that, every dependency that holds on the |
| 127 | | referenced key also holds, by substitution, on the referencing attribute: |
| 128 | | |
| 129 | | ||= Foreign key =||= References =||= Therefore also determines =|| |
| 130 | | || `M_CRYPTO_ID` || `C_ID` || `C_SYMBOL, C_NAME, C_CREATED_AT` || |
| 131 | | || `H_USER_ID` || `U_ID` || all of `U_*` || |
| 132 | | || `H_CRYPTO_ID` || `C_ID` || all of `C_*` || |
| 133 | | || `O_USER_ID` || `U_ID` || all of `U_*` || |
| 134 | | || `O_MARKET_ID` || `M_ID` || all of `M_*`, and transitively all of `C_*` || |
| 135 | | || `T_USER_ID` || `U_ID` || all of `U_*` || |
| 136 | | || `T_RELATED_ORDER` || `O_ID` || all of `O_*`, and transitively `U_*`, `M_*`, `C_*` (when not null) || |
| 137 | | || `MT_MARKET_ID` || `M_ID` || all of `M_*`, transitively `C_*` || |
| 138 | | || `MC_MARKET_ID` || `M_ID` || all of `M_*`, transitively `C_*` || |
| 139 | | || `W_USER_ID` || `U_ID` || all of `U_*` || |
| 140 | | || `WI_WATCHLIST_ID` || `W_ID` || all of `W_*`, transitively `U_*` || |
| 141 | | || `WI_CRYPTO_ID` || `C_ID` || all of `C_*` || |
| 142 | | |
| 143 | | None of these is added to the canonical cover — each is ''derivable'' from FD1–FD17 by |
| 144 | | transitivity plus the foreign-key identity, which is exactly why a canonical cover excludes |
| 145 | | them. They matter anyway: they are precisely the transitive dependencies the 3NF check below |
| 146 | | has to rule out. |
| 147 | | |
| 148 | | == Candidate keys and primary key == |
| 149 | | |
| 150 | | `Orders`, `Transactions`, `MarketTrades`, `MarketCandles`, `Holds`, `Watchlists` and |
| 151 | | `Contains` are, with respect to each other, independent record types: nothing about an |
| 152 | | order's id says anything about which market-candle row, or which unrelated transaction, or |
| 153 | | which watchlist item is in the same tuple of `R_EDUBERZA` — a user can exist with zero of any |
| 154 | | of them, and having one order says nothing about how many holdings, trades or candles exist |
| 155 | | alongside it. (The one FK that crosses between two of these — `T_RELATED_ORDER` — is |
| 156 | | nullable, so it cannot be relied on to always connect a transaction row back to an order.) |
| 157 | | That means no proper subset of attributes can functionally determine all 68 attributes of |
| 158 | | `R_EDUBERZA`: the only way to pin down a `H_*` value, an `O_*` value, a `T_*` value, an |
| 159 | | `MT_*` value, an `MC_*` value, a `W_*` value ''and'' a `WI_*` value at once is to state one |
| 160 | | identifying attribute from each cluster explicitly. |
| 161 | | |
| 162 | | '''Chosen primary key''' (closure shown below): |
| 163 | | |
| 164 | | {{{ |
| 165 | | { U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, W_ID, WI_ID } |
| 166 | | }}} |
| 167 | | |
| 168 | | '''Closure check''', applying FD1–FD17 in turn to this set: |
| 169 | | |
| 170 | | ||= Step =||= Attributes added =||= Dependency used =|| |
| 171 | | || start || `U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, W_ID, WI_ID` || — || |
| 172 | | || 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 → …`) || |
| 173 | | || 2 || `C_SYMBOL, C_NAME, C_CREATED_AT` || FD4 || |
| 174 | | || 3 || `M_CRYPTO_ID, M_QUOTE_CURRENCY, M_IS_ACTIVE, M_CREATED_AT` || FD6 || |
| 175 | | || 4 || `H_USER_ID, H_CRYPTO_ID, H_QUANTITY, H_RESERVED_QUANTITY, H_AVG_PRICE, H_CREATED_AT, H_UPDATED_AT` || FD8 || |
| 176 | | || 5 || `O_USER_ID, O_MARKET_ID, O_SIDE, O_TYPE, O_STATUS, O_QUANTITY, O_PRICE, O_PLACED_AT, O_EXECUTED_AT` || FD10 || |
| 177 | | || 6 || `T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` || FD11 || |
| 178 | | || 7 || `MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` || FD12 || |
| 179 | | || 8 || `MC_MARKET_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME` || FD13 || |
| 180 | | || 9 || `W_USER_ID, W_NAME, W_CREATED_AT` || FD15 || |
| 181 | | || 10 || `WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` || FD16 || |
| 182 | | |
| 183 | | The closure now contains all 68 attributes, so the set is a superkey; removing any one of its |
| 184 | | ten attributes drops an entire cluster that nothing else in the set can reach (e.g. drop |
| 185 | | `T_ID` and no remaining attribute determines any `T_*` value), so it is minimal — a candidate |
| 186 | | key. |
| 187 | | |
| 188 | | '''It is not the only one.''' Any attribute that is itself a determinant of a whole cluster can |
| 189 | | stand in for that cluster's id — `U_USERNAME` or `U_EMAIL` for `U_ID` (FD2/FD3), `C_SYMBOL` |
| 190 | | 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` |
| 191 | | (FD14), `{WI_WATCHLIST_ID, WI_CRYPTO_ID}` for `WI_ID` (FD17) — giving 3 × 2 × 2 × 2 × 1 × 1 × |
| 192 | | 1 × 2 × 1 × 2 = 96 candidate keys in total. The all-surrogate-id combination above is chosen |
| 193 | | as '''primary key''' for the same reason `id` was chosen over `username`/`email`/`symbol`/etc. |
| 194 | | per entity in [wiki:ERModel]: it is opaque, and none of its parts |
| 195 | | are things a user would ever legitimately change. |
| 196 | | |
| 197 | | '''Normal form of `R_EDUBERZA` before decomposition:''' 1NF only, and barely that — see 2NF |
| 198 | | below. It cannot be in 2NF, 3NF or BCNF, since each of those requires 2NF as a precondition. |
| 199 | | |
| 200 | | == 1NF decomposition == |
| 201 | | |
| 202 | | No decomposition happens at this step. 1NF requires atomic, single-valued attributes and no |
| 203 | | repeating groups; `R_EDUBERZA` was built that way from the start (every column above is a |
| 204 | | single scalar), so the relation already satisfies 1NF as written in |
| 205 | | De-normalized database form. The real work starts at 2NF. |
| 206 | | |
| 207 | | == 2NF decomposition == |
| 208 | | |
| 209 | | '''Relation analyzed:''' `R_EDUBERZA`, all 68 attributes, primary key |
| 210 | | `{U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, W_ID, WI_ID}` (10 attributes), FD1–FD17 |
| 211 | | in force. |
| 212 | | |
| 213 | | '''Current normal form:''' 1NF only (previous section). |
| 214 | | |
| 215 | | '''Violations:''' 2NF forbids a non-prime attribute from depending on ''part'' of a candidate |
| 216 | | key. Every single functional dependency in the canonical cover (FD1–FD17) has a left side |
| 217 | | that is a '''proper subset''' of the ten-attribute primary key — `U_ID` alone, `C_ID` alone, …, |
| 218 | | down to the two-attribute `{WI_WATCHLIST_ID, WI_CRYPTO_ID}`. There is no non-prime attribute |
| 219 | | in `R_EDUBERZA` that depends on the whole ten-attribute key and nothing smaller. In other |
| 220 | | words, ''every'' non-prime attribute violates 2NF at once — the violation is not a handful of |
| 221 | | stray columns to peel off, it is the entire relation, because gluing ten independent record |
| 222 | | types together under one artificial composite key was never going to satisfy 2NF to begin |
| 223 | | with. |
| 224 | | |
| 225 | | '''Decomposition.''' This uses 3NF/BCNF '''synthesis''' (Bernstein's algorithm) rather than the |
| 226 | | binary decomposition algorithm: since the canonical cover is already in hand (as the phase |
| 227 | | instructions recommend building first), synthesis creates one relation per left-hand side in |
| 228 | | the cover directly, instead of hunting for one offending dependency at a time and splitting |
| 229 | | in two repeatedly. Grouping FD1–FD17 by determinant produces ten relations: |
| 230 | | |
| 231 | | ||= New relation =||= Attributes =||= Key(s) =||= Source FDs =|| |
| 232 | | || `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 || |
| 233 | | || `R_CRYPTO` || `C_ID, C_SYMBOL, C_NAME, C_CREATED_AT` || `C_ID`, `C_SYMBOL` || FD4, FD5 || |
| 234 | | || `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 || |
| 235 | | || `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 || |
| 236 | | || `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 || |
| 237 | | || `R_TRANSACTIONS` || `T_ID, T_USER_ID, T_TYPE, T_AMOUNT, T_CURRENCY, T_RELATED_ORDER, T_CREATED_AT, T_DESCRIPTION` || `T_ID` || FD11 || |
| 238 | | || `R_MARKET_TRADES` || `MT_ID, MT_MARKET_ID, MT_EXECUTED_AT, MT_PRICE, MT_QUANTITY, MT_SIDE, MT_SOURCE` || `MT_ID` || FD12 || |
| 239 | | || `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 || |
| 240 | | || `R_WATCHLISTS` || `W_ID, W_USER_ID, W_NAME, W_CREATED_AT` || `W_ID` || FD15 || |
| 241 | | || `R_WATCHLIST_ITEMS` || `WI_ID, WI_WATCHLIST_ID, WI_CRYPTO_ID, WI_ADDED_AT` || `WI_ID`, `{WI_WATCHLIST_ID, WI_CRYPTO_ID}` || FD16, FD17 || |
| 242 | | |
| 243 | | Every one of these ten relations now has '''all''' of its non-prime attributes depending on its |
| 244 | | '''whole''' key (in every case there is only one non-composite or one designated key doing the |
| 245 | | determining, so 2NF holds trivially in each). |
| 246 | | |
| 247 | | '''Dependency preservation.''' FD1–FD17 is the canonical cover of `R_EDUBERZA`. Each FD's |
| 248 | | determinant and every one of its dependent attributes land inside exactly one of the ten new |
| 249 | | relations (see the "Source FDs" column above — no FD is split across two relations). The |
| 250 | | union of the FDs that hold on `R_USERS, …, R_WATCHLIST_ITEMS` is therefore exactly FD1–FD17 |
| 251 | | again: nothing was lost. |
| 252 | | |
| 253 | | '''Lossless join — chase test.''' |
| 254 | | |
| 255 | | > ''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.'' |
| 256 | | |
| 257 | | The chase decides whether a decomposition `R = R1 ∪ … ∪ Rn` is lossless under a set of |
| 258 | | functional dependencies. Build a tableau with one column per attribute of `R` and one row per |
| 259 | | relation `Ri`. In row `i`, put a distinguished symbol `a` in every column of `Ri` and a unique |
| 260 | | symbol `b_i` in every other column. Then repeat, until nothing changes: for each FD `X → Y`, |
| 261 | | whenever two rows agree on all of `X`, make them agree on `Y`. If they disagree, an `a` wins, |
| 262 | | otherwise one `b` replaces the other. '''The decomposition is lossless exactly when some row ends up with `a` in every column.''' |
| 263 | | |
| 264 | | 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. |
| 265 | | |
| 266 | | '''Step 1 — the ten relations from the table above.''' |
| 267 | | |
| 268 | | {{{ |
| 269 | | U* C* M* H* O* T* MT* MC* W* WI* |
| 270 | | R_USERS a b b b b b b b b b |
| 271 | | R_CRYPTO b a b b b b b b b b |
| 272 | | R_MARKETS b b a b b b b b b b |
| 273 | | R_HOLDINGS b b b a b b b b b b |
| 274 | | R_ORDERS b b b b a b b b b b |
| 275 | | R_TRANSACTIONS b b b b b a b b b b |
| 276 | | R_MARKET_TR. b b b b b b a b b b |
| 277 | | R_MARKET_CA. b b b b b b b a b b |
| 278 | | R_WATCHLISTS b b b b b b b b a b |
| 279 | | R_WATCHLIST_I. b b b b b b b b b a |
| 280 | | }}} |
| 281 | | |
| 282 | | 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. |
| 283 | | |
| 284 | | '''Step 2 — add the key relation''' `R_KEY(U_ID, C_ID, M_ID, H_ID, O_ID, T_ID, MT_ID, MC_ID, |
| 285 | | W_ID, WI_ID)`. Its row has `a` only in the ten ID columns, written `a·` for "`a` in the ID, |
| 286 | | `b` in the rest of the group": |
| 287 | | |
| 288 | | {{{ |
| 289 | | U* C* M* H* O* T* MT* MC* W* WI* |
| 290 | | R_KEY a· a· a· a· a· a· a· a· a· a· |
| 291 | | (the ten rows of step 1 unchanged) |
| 292 | | }}} |
| 293 | | |
| 294 | | 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 |
| 295 | | `U*` group. The same happens with FD4 (`C*`), FD6 (`M*`), FD8 (`H*`), FD10 (`O*`), FD11 (`T*`), |
| 296 | | FD12 (`MT*`), FD13 (`MC*`), FD15 (`W*`) and FD16 (`WI*`): |
| 297 | | |
| 298 | | {{{ |
| 299 | | U* C* M* H* O* T* MT* MC* W* WI* |
| 300 | | R_KEY a a a a a a a a a a <- all distinguished |
| 301 | | }}} |
| 302 | | |
| 303 | | '''Row `R_KEY` is all `a`, so the decomposition into the ten relations plus `R_KEY` is lossless.''' |
| 304 | | |
| 305 | | '''Why `R_KEY` is not kept in the final schema.''' An instance of `R_KEY` would only record |
| 306 | | which ID of one cluster appears together with which ID of every other cluster. As shown under |
| 307 | | ''Candidate keys and primary key'', the ten clusters are independent record types, and |
| 308 | | `R_EDUBERZA` pairs every row of one with every row of the others. So `R_KEY` would be just the |
| 309 | | cross product of the ten ID sets and would carry no information. The same independence means |
| 310 | | the join dependency `⋈[R_USERS, …, R_WATCHLIST_ITEMS]` holds on `R_EDUBERZA` by construction. |
| 311 | | Under that dependency the ten relations alone already reconstruct it: their natural join, with |
| 312 | | no common attributes, is exactly that cross product. The chase makes this reasoning explicit. |
| 313 | | FDs by themselves cannot prove the join lossless; you need either the key relation or the |
| 314 | | independence of the clusters. That was hidden in the earlier "foreign key equals primary key" |
| 315 | | argument, which described the equi-joins the application runs, not the natural join the |
| 316 | | lossless-join property is about. |
| | 248 | Every step splits one relation `R` into two: the '''extracted''' relation `Ri` and the |
| | 249 | '''residual''' relation `R'` (what is left of `R`). The same two checks are made each time: |
| | 250 | |
| | 251 | * '''Lossless join.''' The split of `R` into `Ri` and `R'` is lossless if the common attributes determine one of the two sides: `(Ri ∩ R') → Ri` or `(Ri ∩ R') → R'`. Every step below extracts `Ri = X ∪ (what X determines)` for some determinant `X` that stays in `R'`. So `X ⊆ Ri ∩ R'` and `X → Ri`, and the first condition holds. |
| | 252 | * '''Dependency preservation.''' Every dependency of the canonical cover must end up with all its attributes inside one relation. So an attribute is removed from the residual only when no dependency still waiting in the residual needs it. Otherwise it is extracted '''and''' kept. |
| | 253 | |
| | 254 | '''Relation analyzed first:''' `R_EDUBERZA` (66 attributes), dependencies FD1–FD18, candidate |
| | 255 | keys K1–K4, primary key K1. '''Normal form:''' 1NF. |
| | 256 | |
| | 257 | '''Dependencies that violate 2NF.''' 2NF forbids a non-prime attribute from depending on a proper |
| | 258 | part of a candidate key. There are six such partial dependencies: |
| | 259 | |
| | 260 | ||= Part of a key =||= Non-prime attributes that depend on it =||= Through =|| |
| | 261 | || `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 || |
| | 262 | || `OE_ID` (K1–K4) || `OE_*`, `O_ID` || FD13 || |
| | 263 | || `MT_ID` (K1–K4) || `MT_*`, `M_ID`, `O_ID_FILLSBUY`, `O_ID_FILLSSELL` || FD12 || |
| | 264 | || `MC_ID` (K1, K2) || `MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME`, `M_ID` || FD14 || |
| | 265 | || `W_ID` (K2, K4) || `W_*`, `U_ID` || FD16 || |
| | 266 | || `WI_ID` (K1, K3) || `WI_ADDED_AT`, `C_ID` || FD17 || |
| | 267 | |
| | 268 | The table lists the part of a key that each group depends on most directly. It is not the |
| | 269 | only one: under K3/K4, for example, `MC_OPEN … MC_VOLUME` also depend on |
| | 270 | `{MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME}`, and under K1/K3 `W_*` depend on `WI_ID` through |
| | 271 | `W_ID`. These lead to the same relations, so they need no extra steps. `MC_TIMEFRAME`, |
| | 272 | `MC_CANDLE_TIME` and `W_ID` also depend on parts of keys, but they are prime, so 2NF does not |
| | 273 | restrict them. They are handled under BCNF. |
| | 274 | |
| | 275 | Each step below removes one row of this table, splitting the current relation into two. The |
| | 276 | '''order''' is chosen so that no dependency is lost. `T_ID` goes first, because its group is the |
| | 277 | largest and carries FD1–FD11 with it. Each later step handles a group whose determinant is |
| | 278 | still in the residual relation. |
| | 279 | |
| | 280 | === Step 2NF-1 — partial dependency on `T_ID` === |
| | 281 | |
| | 282 | * '''Relation analyzed:''' `R_EDUBERZA` (66 attributes). |
| | 283 | * '''Dependencies:''' FD1–FD18. '''Candidate keys:''' K1–K4. '''Primary key:''' K1. '''Normal form:''' 1NF. |
| | 284 | * '''2NF violations:''' all six rows of the table above. '''Split first on `T_ID`''', the largest group (see the order explained above). |
| | 285 | * '''Decomposition dependency:''' `T_ID → T_*, O_ID` (FD11), together with everything it determines transitively (FD10, FD1, FD6, FD4, FD9, FD8). `T_ID` is a proper part of K1, and `T_AMOUNT`, for example, is non-prime, so this violates 2NF. |
| | 286 | * '''New relation `R_A`''' = `{ T_ID, T_*, O_ID, O_*, U_ID, U_*, M_ID, M_*, C_ID, C_*, H_ID, H_* }` (39 attributes). Dependencies: FD1–FD11. Candidate key and primary key: `T_ID`. Normal form: 2NF (it has a one-attribute key), but not 3NF (see 3NF). |
| | 287 | * '''Residual relation `S1`''' = `R_EDUBERZA − { T_*, O_*, U_*, M_*, C_*, H_ID, H_* }` = `{ T_ID, O_ID, U_ID, M_ID, C_ID, OE_ID, OE_*, MT_ID, MT_*, O_ID_FILLSBUY, O_ID_FILLSSELL, MC_ID, MC_*, W_ID, W_*, WI_ID, WI_ADDED_AT }` (32 attributes). `O_ID`, `U_ID`, `M_ID` and `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: `T_ID → O_ID, U_ID, M_ID, C_ID`, `O_ID → U_ID, M_ID, C_ID`, `M_ID → C_ID`, `OE_ID → U_ID, M_ID, C_ID`, `MT_ID → C_ID`, `MC_ID → C_ID`, `WI_ID → U_ID`. Candidate keys: K1–K4 (all their attributes are still here). Normal form: 1NF. |
| | 288 | * '''Dependency preservation:''' FD1–FD11 lie entirely in `R_A`, and FD12–FD18 entirely in `S1`. ✓ |
| | 289 | * '''Lossless join:''' `R_A ∩ S1 = { T_ID, O_ID, U_ID, M_ID, C_ID }` contains `T_ID`, and `T_ID → R_A`, so `(R_A ∩ S1) → R_A`. ✓ |
| | 290 | |
| | 291 | === Step 2NF-2 — partial dependency on `OE_ID` === |
| | 292 | |
| | 293 | * '''Relation analyzed:''' `S1` (32 attributes). Dependencies: as listed for `S1` in the previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. |
| | 294 | * '''Remaining 2NF violations:''' the partial dependencies on `OE_ID`, `MT_ID`, `MC_ID`, `W_ID` and `WI_ID` (table above), and the partial dependencies of the kept identifiers `O_ID`, `U_ID`, `M_ID`, `C_ID` on `T_ID`. The kept identifiers cannot leave yet, because other groups still need them. Each one leaves with the last group that needs it (`O_ID` in 2NF-2, `M_ID` in 2NF-4, `U_ID` in 2NF-5, `C_ID` in 2NF-6). '''Split first on `OE_ID`''', because after it no group needs `O_ID` any more. |
| | 295 | * '''Decomposition dependency:''' `OE_ID → OE_*, O_ID` (FD13). `OE_ID` is a proper part of K1 and `OE_*` are non-prime. |
| | 296 | * '''New relation `R_B`''' = `{ OE_ID, OE_*, O_ID }` (7 attributes). Dependencies: FD13. Candidate key: `OE_ID`. Normal form: BCNF. |
| | 297 | * '''Residual relation `S2`''' = `S1 − { OE_*, O_ID }` (26 attributes). No dependency still needed in the residual uses `O_ID`. Dependencies: FD12, FD14–FD18, plus the projected `T_ID → U_ID, M_ID, C_ID`, `OE_ID → U_ID, M_ID, C_ID`, `M_ID → C_ID`, `MT_ID → C_ID`, `MC_ID → C_ID`, `WI_ID → U_ID`. Candidate keys: K1–K4. Normal form: 1NF. |
| | 298 | * '''Dependency preservation:''' FD13 is in `R_B`, and the others are in `S2`. `T_ID → O_ID` is already kept in `R_A`. ✓ |
| | 299 | * '''Lossless join:''' `R_B ∩ S2 = { OE_ID }`, and `OE_ID → R_B` (FD13). ✓ |
| | 300 | |
| | 301 | === Step 2NF-3 — partial dependency on `MT_ID` === |
| | 302 | |
| | 303 | * '''Relation analyzed:''' `S2` (26 attributes). Dependencies: as listed for `S2` in the previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. |
| | 304 | * '''Remaining 2NF violations:''' the groups of `MT_ID`, `MC_ID`, `W_ID`, `WI_ID`, and the kept identifiers `U_ID`, `M_ID`, `C_ID`. '''Split first on `MT_ID`''', the next group. `M_ID` must still stay for `MC_ID`. |
| | 305 | * '''Decomposition dependency:''' `MT_ID → MT_*, M_ID, O_ID_FILLSBUY, O_ID_FILLSSELL` (FD12). |
| | 306 | * '''New relation `R_C`''' = `{ MT_ID, MT_*, M_ID, O_ID_FILLSBUY, O_ID_FILLSSELL }` (9 attributes). Dependencies: FD12. Candidate key: `MT_ID`. Normal form: BCNF. |
| | 307 | * '''Residual relation `S3`''' = `S2 − { MT_*, O_ID_FILLSBUY, O_ID_FILLSSELL }` (19 attributes). `M_ID` stays, because FD14/FD15 need it. Dependencies: FD14–FD18, plus the projected `T_ID → U_ID, M_ID, C_ID`, `OE_ID → U_ID, M_ID, C_ID`, `MT_ID → M_ID, C_ID`, `M_ID → C_ID`, `MC_ID → C_ID`, `WI_ID → U_ID`. Candidate keys: K1–K4. Normal form: 1NF. |
| | 308 | * '''Dependency preservation:''' FD12 is in `R_C`, and FD14–FD18 are in `S3`. ✓ |
| | 309 | * '''Lossless join:''' `R_C ∩ S3 = { MT_ID, M_ID }` contains `MT_ID`, and `MT_ID → R_C` (FD12). ✓ |
| | 310 | |
| | 311 | === Step 2NF-4 — partial dependency on `MC_ID` === |
| | 312 | |
| | 313 | * '''Relation analyzed:''' `S3` (19 attributes). Dependencies: as listed for `S3` in the previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. |
| | 314 | * '''Remaining 2NF violations:''' the groups of `MC_ID`, `W_ID`, `WI_ID`, and the kept identifiers `U_ID`, `M_ID`, `C_ID`. '''Split first on `MC_ID`''', the last group that needs `M_ID`, so `M_ID` can leave with it. |
| | 315 | * '''Decomposition dependency:''' `MC_ID → MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, M_ID` (FD14). `MC_ID` is a proper part of K1. The prime `MC_TIMEFRAME` and `MC_CANDLE_TIME` also go into the new relation, so that FD15, which needs them with `M_ID` and `MC_ID`, is preserved. |
| | 316 | * '''New relation `R_D`''' = `{ MC_ID, MC_TIMEFRAME, MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, MC_CANDLE_TIME, M_ID }` (9 attributes). Dependencies: FD14, FD15. Candidate keys: `MC_ID` and `{M_ID, MC_TIMEFRAME, MC_CANDLE_TIME}`. Normal form: BCNF. |
| | 317 | * '''Residual relation `S4`''' = `S3 − { MC_OPEN, MC_HIGH, MC_LOW, MC_CLOSE, MC_VOLUME, M_ID }` (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`, `MT_ID → C_ID`, `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME, C_ID`, `WI_ID → U_ID`. Candidate keys: K1–K4. Normal form: 1NF. |
| | 318 | * '''Dependency preservation:''' FD14 and FD15 are in `R_D`, and FD16–FD18 are in `S4`. ✓ |
| | 319 | * '''Lossless join:''' `R_D ∩ S4 = { MC_ID, MC_TIMEFRAME, MC_CANDLE_TIME }` contains `MC_ID`, and `MC_ID → R_D` (FD14). ✓ |
| | 320 | |
| | 321 | === Step 2NF-5 — partial dependency on `W_ID` === |
| | 322 | |
| | 323 | * '''Relation analyzed:''' `S4` (13 attributes). Dependencies: as listed for `S4` in the previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. |
| | 324 | * '''Remaining 2NF violations:''' the groups of `W_ID` and `WI_ID`, and the kept identifiers `U_ID`, `C_ID`. '''Split first on `W_ID`''', the last group that needs `U_ID`. |
| | 325 | * '''Decomposition dependency:''' `W_ID → W_NAME, W_CREATED_AT, U_ID` (FD16). `W_ID` is a proper part of K2. |
| | 326 | * '''New relation `R_E`''' = `{ W_ID, W_NAME, W_CREATED_AT, U_ID }` (4 attributes). Dependencies: FD16. Candidate key: `W_ID`. Normal form: BCNF. |
| | 327 | * '''Residual relation `S5`''' = `S4 − { W_NAME, W_CREATED_AT, U_ID }` (10 attributes). Dependencies: FD17, FD18, plus the projected `T_ID → C_ID`, `OE_ID → C_ID`, `MT_ID → C_ID`, `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME, C_ID`. Candidate keys: K1–K4. Normal form: 1NF. |
| | 328 | * '''Dependency preservation:''' FD16 is in `R_E`, and FD17 and FD18 are in `S5`. ✓ |
| | 329 | * '''Lossless join:''' `R_E ∩ S5 = { W_ID }`, and `W_ID → R_E` (FD16). ✓ |
| | 330 | |
| | 331 | === Step 2NF-6 — partial dependency on `WI_ID` === |
| | 332 | |
| | 333 | * '''Relation analyzed:''' `S5` (10 attributes). Dependencies: as listed for `S5` in the previous step. Candidate keys: K1–K4. Primary key: K1. Normal form: 1NF. |
| | 334 | * '''Remaining 2NF violations:''' the group of `WI_ID`, and the kept identifier `C_ID`. '''Split on `WI_ID`''', the last group that needs `C_ID`. |
| | 335 | * '''Decomposition dependency:''' `WI_ID → WI_ADDED_AT, W_ID, C_ID` (FD17). `WI_ID` is a proper part of K1, and `WI_ADDED_AT` and `C_ID` are non-prime. |
| | 336 | * '''New relation `R_F`''' = `{ WI_ID, WI_ADDED_AT, W_ID, C_ID }` (4 attributes). Dependencies: FD17, FD18. Candidate keys: `WI_ID` and `{W_ID, C_ID}`. Normal form: BCNF. |
| | 337 | * '''Residual relation `S6`''' = `S5 − { WI_ADDED_AT, C_ID }` = `{ T_ID, OE_ID, MT_ID, MC_ID, MC_TIMEFRAME, MC_CANDLE_TIME, W_ID, WI_ID }` (8 attributes). `W_ID` is prime and stays. Dependencies: no dependency of the cover lies entirely inside `S6`. The projected ones are `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME` and `WI_ID → W_ID`, plus derived ones such as `MT_ID, MC_TIMEFRAME, MC_CANDLE_TIME → MC_ID` and `MT_ID, W_ID → WI_ID`. Candidate keys: K1–K4. Normal form: 3NF, because every attribute is prime (and so 2NF). |
| | 338 | * '''Dependency preservation:''' FD17 and FD18 are in `R_F`. ✓ |
| | 339 | * '''Lossless join:''' `R_F ∩ S6 = { WI_ID, W_ID }` contains `WI_ID`, and `WI_ID → R_F` (FD17). ✓ |
| | 340 | |
| | 341 | '''Result of 2NF:''' `R_A`, `R_B`, `R_C`, `R_D`, `R_E`, `R_F`, `S6`. All seven are in 2NF (`R_A` |
| | 342 | only 2NF, `S6` 3NF, the rest BCNF). All 18 dependencies are preserved: FD1–FD11 in `R_A`, |
| | 343 | FD13 in `R_B`, FD12 in `R_C`, FD14–FD15 in `R_D`, FD16 in `R_E`, FD17–FD18 in `R_F`. |
| 320 | | '''Relations analyzed:''' each of the ten relations produced above, individually. |
| 321 | | |
| 322 | | For each relation, 3NF asks whether any non-prime attribute is ''transitively'' dependent on a |
| 323 | | key — i.e. determined by another non-prime attribute rather than directly by the key. This is |
| 324 | | exactly where the foreign-key-carried dependencies from |
| 325 | | Dependencies carried by foreign keys have to be |
| 326 | | checked, because that table is precisely the list of "dependency that would cause a problem at |
| 327 | | the next higher normal form" the phase template asks for. |
| 328 | | |
| 329 | | '''Worked example — `R_MARKETS`.''' Its key `M_ID` determines `M_CRYPTO_ID`, and |
| 330 | | `M_CRYPTO_ID → C_SYMBOL, C_NAME, C_CREATED_AT` also holds (`M_CRYPTO_ID` draws its values from |
| 331 | | `C_ID`'s domain). If `C_SYMBOL`, `C_NAME` and `C_CREATED_AT` were still columns of |
| 332 | | `R_MARKETS`, this would be exactly the transitive dependency `M_ID → M_CRYPTO_ID → C_SYMBOL` |
| 333 | | that violates 3NF. They are not: the 2NF step above already put them in `R_CRYPTO`, keyed |
| 334 | | directly by `C_ID` (FD4), because FD4 — not the derived `M_CRYPTO_ID → C_SYMBOL` — is what the |
| 335 | | canonical cover actually contains. `R_MARKETS` itself has no attribute that determines another |
| 336 | | non-prime attribute of `R_MARKETS`; the transitive dependency is real, but it points ''out'' of |
| 337 | | the relation, not within it. |
| 338 | | |
| 339 | | The same reasoning applies to every other foreign key in the list: `H_USER_ID`/`H_CRYPTO_ID`, |
| 340 | | `O_USER_ID`/`O_MARKET_ID`, `T_USER_ID`/`T_RELATED_ORDER`, `MT_MARKET_ID`, `MC_MARKET_ID`, |
| 341 | | `W_USER_ID`, `WI_WATCHLIST_ID`/`WI_CRYPTO_ID` are all foreign keys sitting ''alongside'' a |
| 342 | | non-key attribute set that depends only on their own relation's key, never on the foreign key |
| 343 | | itself. None of `R_USERS`, `R_CRYPTO`, `R_HOLDINGS`, `R_ORDERS`, `R_TRANSACTIONS`, |
| 344 | | `R_MARKET_TRADES`, `R_MARKET_CANDLES`, `R_WATCHLISTS`, `R_WATCHLIST_ITEMS` has a non-prime |
| 345 | | attribute that another non-prime attribute of the ''same'' relation determines. |
| 346 | | |
| 347 | | '''Conclusion:''' synthesising directly from the canonical cover in the 2NF step already |
| 348 | | avoided every transitive dependency — there is nothing left to decompose for 3NF. All ten |
| 349 | | relations from the previous section satisfy 3NF unchanged. |
| | 347 | Only `R_A` is not in 3NF. `R_B`–`R_F` are already in BCNF, and `S6` is in 3NF (all its |
| | 348 | attributes are prime). |
| | 349 | |
| | 350 | '''Dependencies that violate 3NF in `R_A`.''' 3NF forbids a non-prime attribute from depending on |
| | 351 | a key only '''transitively''', through a determinant that is not a superkey. The only key of |
| | 352 | `R_A` is `T_ID`, but inside `R_A`: |
| | 353 | |
| | 354 | * `U_ID → U_*` (FD1), `U_USERNAME → U_ID` (FD2), `U_EMAIL → U_ID` (FD3) |
| | 355 | * `C_ID → C_*` (FD4), `C_SYMBOL → C_ID` (FD5) |
| | 356 | * `U_ID, C_ID → H_ID` (FD9), `H_ID → H_*, U_ID, C_ID` (FD8) |
| | 357 | * `M_ID → M_*, C_ID` (FD6), `C_ID, M_QUOTE_CURRENCY → M_ID` (FD7) |
| | 358 | * `O_ID → O_*, U_ID, M_ID` (FD10) |
| | 359 | |
| | 360 | None of these determinants is a superkey of `R_A`. For example, `T_ID → O_ID → O_PRICE` is a |
| | 361 | transitive dependency of the non-prime `O_PRICE` on the key. |
| | 362 | |
| | 363 | '''Order of the steps.''' An attribute can leave the residual only after every dependency that |
| | 364 | needs it has been extracted. FD9 needs `U_ID` and `C_ID` together, and extracting `Markets` |
| | 365 | takes `C_ID` out of the residual, so `Holdings` must come before `Markets`. Extracting |
| | 366 | `Orders` takes `M_ID` and `U_ID` out, so `Orders` comes last. The dependencies are therefore |
| | 367 | taken from the "leaves" of the chain `T_ID → O_ID → {U_ID, M_ID → C_ID}` inward. |
| | 368 | |
| | 369 | === Step 3NF-1 — transitive dependency through `U_ID` === |
| | 370 | |
| | 371 | * '''Relation analyzed:''' `R_A` (39 attributes), dependencies FD1–FD11, candidate key and primary candidate key and primary key `T_ID`, normal form 2NF. |
| | 372 | * '''3NF violations:''' all five groups listed above. '''Split first on `U_ID`'''. It is a leaf of the chain: its dependents determine nothing outside its own group. |
| | 373 | * '''Decomposition dependency:''' `U_ID → U_*` (FD1). `U_ID` is not a superkey of `R_A`. |
| | 374 | * '''New relation `R_USERS`''' = `{ U_ID, U_* }` (10 attributes). Dependencies: FD1, FD2, FD3. Candidate keys: `U_ID`, `U_USERNAME`, `U_EMAIL`. Primary key: `U_ID`. Normal form: BCNF. |
| | 375 | * '''Residual relation `R_A1`''' = `R_A − U_*` (30 attributes). Dependencies: FD4–FD11, which also imply `T_ID → H_ID` and `O_ID → H_ID` (through `U_ID, C_ID`). Candidate key and primary key: `T_ID`. Normal form: 2NF. |
| | 376 | * '''Dependency preservation:''' FD1–FD3 are in `R_USERS`, and FD4–FD11 are in `R_A1`. ✓ |
| | 377 | * '''Lossless join:''' `R_USERS ∩ R_A1 = { U_ID }`, and `U_ID → R_USERS` (FD1). ✓ |
| | 378 | |
| | 379 | === Step 3NF-2 — transitive dependency through `C_ID` === |
| | 380 | |
| | 381 | * '''Relation analyzed:''' `R_A1` (30 attributes), dependencies FD4–FD11, candidate key and primary key `T_ID`, normal form 2NF. |
| | 382 | * '''3NF violations:''' `C_ID → C_*`, `U_ID, C_ID → H_ID → H_*`, `M_ID → M_*, C_ID`, `O_ID → O_*, U_ID, M_ID`. '''Split first on `C_ID`''', the next leaf. |
| | 383 | * '''Decomposition dependency:''' `C_ID → C_*` (FD4). |
| | 384 | * '''New relation `R_CRYPTO`''' = `{ C_ID, C_* }` (4 attributes). Dependencies: FD4, FD5. Candidate keys: `C_ID`, `C_SYMBOL`. Primary key: `C_ID`. Normal form: BCNF. |
| | 385 | * '''Residual relation `R_A2`''' = `R_A1 − C_*` (27 attributes). Dependencies: FD6–FD11. Candidate key and primary key: `T_ID`. Normal form: 2NF. |
| | 386 | * '''Dependency preservation:''' FD4 and FD5 are in `R_CRYPTO`, and FD6–FD11 are in `R_A2`. ✓ |
| | 387 | * '''Lossless join:''' `R_CRYPTO ∩ R_A2 = { C_ID }`, and `C_ID → R_CRYPTO` (FD4). ✓ |
| | 388 | |
| | 389 | === Step 3NF-3 — transitive dependency through `{U_ID, C_ID}` === |
| | 390 | |
| | 391 | * '''Relation analyzed:''' `R_A2` (27 attributes), dependencies FD6–FD11, candidate key and primary key `T_ID`, normal form 2NF. |
| | 392 | * '''3NF violations:''' `U_ID, C_ID → H_ID → H_*`, `M_ID → M_*, C_ID`, `O_ID → O_*, U_ID, M_ID`. '''Split first on `{U_ID, C_ID}`''', because it must come before `Markets` takes `C_ID` away. |
| | 393 | * '''Decomposition dependency:''' `U_ID, C_ID → H_ID` (FD9), together with `H_ID → H_*` (FD8). |
| | 394 | * '''New relation `R_HOLDINGS`''' = `{ H_ID, H_*, U_ID, C_ID }` (8 attributes). Dependencies: FD8, FD9. Candidate keys: `H_ID`, `{U_ID, C_ID}`. Primary key: `H_ID`. Normal form: BCNF. |
| | 395 | * '''Residual relation `R_A3`''' = `R_A2 − { H_ID, H_* }` (21 attributes). Dependencies: FD6, FD7, FD10, FD11. Candidate key and primary key: `T_ID`. Normal form: 2NF. |
| | 396 | * '''Dependency preservation:''' FD8 and FD9 are in `R_HOLDINGS`, and the others are in `R_A3`. ✓ |
| | 397 | * '''Lossless join:''' `R_HOLDINGS ∩ R_A3 = { U_ID, C_ID }`, and `U_ID, C_ID → H_ID → H_*`, so `{U_ID, C_ID} → R_HOLDINGS`. ✓ |
| | 398 | |
| | 399 | === Step 3NF-4 — transitive dependency through `M_ID` === |
| | 400 | |
| | 401 | * '''Relation analyzed:''' `R_A3` (21 attributes), dependencies FD6, FD7, FD10, FD11, key `T_ID`, normal form 2NF. |
| | 402 | * '''3NF violations:''' `M_ID → M_*, C_ID` and `O_ID → O_*, U_ID, M_ID`. '''Split first on `M_ID`''', because `Orders` still needs `M_ID`. |
| | 403 | * '''Decomposition dependency:''' `M_ID → M_*, C_ID` (FD6). |
| | 404 | * '''New relation `R_MARKETS`''' = `{ M_ID, M_*, C_ID }` (5 attributes). Dependencies: FD6, FD7. Candidate keys: `M_ID`, `{C_ID, M_QUOTE_CURRENCY}`. Primary key: `M_ID`. Normal form: BCNF. |
| | 405 | * '''Residual relation `R_A4`''' = `R_A3 − { M_*, C_ID }` (17 attributes). No dependency left needs `C_ID`. Dependencies: FD10, FD11. Candidate key and primary key: `T_ID`. Normal form: 2NF. |
| | 406 | * '''Dependency preservation:''' FD6 and FD7 are in `R_MARKETS`, and FD10 and FD11 are in `R_A4`. ✓ |
| | 407 | * '''Lossless join:''' `R_MARKETS ∩ R_A4 = { M_ID }`, and `M_ID → R_MARKETS` (FD6). ✓ |
| | 408 | |
| | 409 | === Step 3NF-5 — transitive dependency through `O_ID` === |
| | 410 | |
| | 411 | * '''Relation analyzed:''' `R_A4` = `{ T_ID, T_*, O_ID, O_*, U_ID, M_ID }` (17 attributes), dependencies FD10, FD11, candidate key and primary key `T_ID`, normal form 2NF. |
| | 412 | * '''3NF violations:''' only `O_ID → O_*, U_ID, M_ID`. '''Split on `O_ID`'''. |
| | 413 | * '''Decomposition dependency:''' `O_ID → O_*, U_ID, M_ID` (FD10). |
| | 414 | * '''New relation `R_ORDERS`''' = `{ O_ID, O_*, U_ID, M_ID }` (11 attributes). Dependencies: FD10. Candidate key: `O_ID`. Normal form: BCNF. |
| | 415 | * '''Residual relation `R_TRANSACTIONS`''' = `R_A4 − { O_*, U_ID, M_ID }` = `{ T_ID, T_*, O_ID }` (7 attributes). Dependencies: FD11. Candidate key: `T_ID`. Normal form: BCNF. Keeping `U_ID` here would have left the transitive dependency `T_ID → O_ID → U_ID` inside the relation. `T_ID → U_ID` was removed from the cover as redundant, so nothing is lost. |
| | 416 | * '''Dependency preservation:''' FD10 is in `R_ORDERS`, and FD11 is in `R_TRANSACTIONS`. ✓ |
| | 417 | * '''Lossless join:''' `R_ORDERS ∩ R_TRANSACTIONS = { O_ID }`, and `O_ID → R_ORDERS` (FD10). ✓ |
| | 418 | |
| | 419 | '''Result of 3NF:''' `R_USERS`, `R_CRYPTO`, `R_HOLDINGS`, `R_MARKETS`, `R_ORDERS`, |
| | 420 | `R_TRANSACTIONS` (from `R_A`), and `R_B`, `R_C`, `R_D`, `R_E`, `R_F`, `S6` unchanged. 12 |
| | 421 | relations, all in 3NF, and all except `S6` in BCNF. All 18 dependencies are preserved. |
| 353 | | '''Relations analyzed:''' the same ten relations, checked against the stricter BCNF rule: every |
| 354 | | determinant of every functional dependency that holds on the relation must be a candidate key |
| 355 | | of that relation (3NF allows an exception when the dependent side is prime; BCNF does not). |
| 356 | | |
| 357 | | ||= Relation =||= Functional dependencies in force =||= Determinant =||= Is it a candidate key? =|| |
| 358 | | || `R_USERS` || FD1, FD2, FD3 || `U_ID`, `U_USERNAME`, `U_EMAIL` || Yes — all three are candidate keys || |
| 359 | | || `R_CRYPTO` || FD4, FD5 || `C_ID`, `C_SYMBOL` || Yes — both candidate keys || |
| 360 | | || `R_MARKETS` || FD6, FD7 || `M_ID`, `{M_CRYPTO_ID, M_QUOTE_CURRENCY}` || Yes — both candidate keys || |
| 361 | | || `R_HOLDINGS` || FD8, FD9 || `H_ID`, `{H_USER_ID, H_CRYPTO_ID}` || Yes — both candidate keys || |
| 362 | | || `R_ORDERS` || FD10 || `O_ID` || Yes — the only candidate key || |
| 363 | | || `R_TRANSACTIONS` || FD11 || `T_ID` || Yes — the only candidate key || |
| 364 | | || `R_MARKET_TRADES` || FD12 || `MT_ID` || Yes — the only candidate key || |
| 365 | | || `R_MARKET_CANDLES` || FD13, FD14 || `MC_ID`, `{MC_MARKET_ID, MC_TIMEFRAME, MC_CANDLE_TIME}` || Yes — both candidate keys || |
| 366 | | || `R_WATCHLISTS` || FD15 || `W_ID` || Yes — the only candidate key || |
| 367 | | || `R_WATCHLIST_ITEMS` || FD16, FD17 || `WI_ID`, `{WI_WATCHLIST_ID, WI_CRYPTO_ID}` || Yes — both candidate keys || |
| 368 | | |
| 369 | | 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, |
| 370 | | reached in the same step that fixed 2NF. This is not a coincidence: it happens because the |
| 371 | | canonical cover already grouped each relation's own key directly against its own attributes |
| 372 | | with no attribute appearing on the right side of two different relations' dependencies, which |
| 373 | | is exactly what synthesis from a canonical cover guarantees when, as here, none of the |
| 374 | | per-cluster functional dependencies overlap. |
| 375 | | |
| 376 | | No further decomposition is possible or necessary; splitting any of the ten relations further |
| 377 | | would only separate attributes that already depend on the ''whole'' key of a BCNF relation, |
| 378 | | which cannot fix anything and only costs a join. |
| | 425 | BCNF requires '''every''' determinant of a non-trivial dependency to be a superkey, even when |
| | 426 | the dependent attribute is prime. |
| | 427 | |
| | 428 | ||= Relation =||= Dependencies in force =||= Determinants =||= All superkeys? =|| |
| | 429 | || `R_USERS` || FD1, FD2, FD3 || `U_ID`, `U_USERNAME`, `U_EMAIL` || yes || |
| | 430 | || `R_CRYPTO` || FD4, FD5 || `C_ID`, `C_SYMBOL` || yes || |
| | 431 | || `R_MARKETS` || FD6, FD7 || `M_ID`, `{C_ID, M_QUOTE_CURRENCY}` || yes || |
| | 432 | || `R_HOLDINGS` || FD8, FD9 || `H_ID`, `{U_ID, C_ID}` || yes || |
| | 433 | || `R_ORDERS` || FD10 || `O_ID` || yes || |
| | 434 | || `R_TRANSACTIONS` || FD11 || `T_ID` || yes || |
| | 435 | || `R_B` || FD13 || `OE_ID` || yes || |
| | 436 | || `R_C` || FD12 || `MT_ID` || yes || |
| | 437 | || `R_D` || FD14, FD15 || `MC_ID`, `{M_ID, MC_TIMEFRAME, MC_CANDLE_TIME}` || yes || |
| | 438 | || `R_E` || FD16 || `W_ID` || yes || |
| | 439 | || `R_F` || FD17, FD18 || `WI_ID`, `{W_ID, C_ID}` || yes || |
| | 440 | || `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''' || |
| | 441 | |
| | 442 | '''Dependencies that violate BCNF — only in `S6`.''' `MC_ID` determines `MC_TIMEFRAME` and |
| | 443 | `MC_CANDLE_TIME`, and `WI_ID` determines `W_ID`, but neither `MC_ID` nor `WI_ID` is a superkey |
| | 444 | of `S6`. 3NF allowed this because the dependent attributes are prime. BCNF does not. The derived |
| | 445 | dependencies all involve `W_ID` or `MC_TIMEFRAME`/`MC_CANDLE_TIME`, so they disappear once the |
| | 446 | two steps below remove those attributes. |
| | 447 | |
| | 448 | === Step BCNF-1 — `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME` === |
| | 449 | |
| | 450 | * '''Relation analyzed:''' `S6` (8 attributes), dependencies as in the table above, candidate keys K1–K4, primary key K1, normal form 3NF. |
| | 451 | * '''BCNF violations:''' `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME` and `WI_ID → W_ID`, and the derived ones that depend on them. '''Split first on `MC_ID`'''. The order does not matter here, because the two violations share no attribute. |
| | 452 | * '''Decomposition dependency:''' `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME`. `MC_ID` is not a superkey of `S6`. |
| | 453 | * '''New relation''' `{ MC_ID, MC_TIMEFRAME, MC_CANDLE_TIME }`. Dependencies: `MC_ID → MC_TIMEFRAME, MC_CANDLE_TIME`. Key: `MC_ID`. Normal form: BCNF. It is a projection of `R_D`, which already contains these attributes with the same key, so it adds no information and is merged into `R_D`. |
| | 454 | * '''Residual relation `S7`''' = `{ T_ID, OE_ID, MT_ID, MC_ID, W_ID, WI_ID }` (6 attributes). Dependencies: `WI_ID → W_ID`, and derived ones such as `MT_ID, W_ID → WI_ID`. Candidate keys: `{T_ID, OE_ID, MT_ID, MC_ID, WI_ID}` (K1) and `{T_ID, OE_ID, MT_ID, MC_ID, W_ID}` (K2). Normal form: 3NF. |
| | 455 | * '''Dependency preservation:''' no dependency of the cover is affected. FD14 and FD15 are in `R_D`. ✓ |
| | 456 | * '''Lossless join:''' the intersection is `{ MC_ID }`, and `MC_ID → { MC_ID, MC_TIMEFRAME, MC_CANDLE_TIME }`. ✓ |
| | 457 | |
| | 458 | === Step BCNF-2 — `WI_ID → W_ID` === |
| | 459 | |
| | 460 | * '''Relation analyzed:''' `S7` (6 attributes), dependencies `WI_ID → W_ID` and derived ones, candidate keys K1, K2, primary key K1, normal form 3NF. |
| | 461 | * '''BCNF violations:''' only `WI_ID → W_ID` (and the derived `MT_ID, W_ID → WI_ID`). '''Split on `WI_ID`'''. |
| | 462 | * '''Decomposition dependency:''' `WI_ID → W_ID`. `WI_ID` is not a superkey of `S7`. |
| | 463 | * '''New relation''' `{ WI_ID, W_ID }`. Dependencies: `WI_ID → W_ID`. Key: `WI_ID`. Normal form: BCNF. For the same reason as in BCNF-1, it is merged into `R_F`. |
| | 464 | * '''Residual relation `R_KEY`''' = `{ T_ID, OE_ID, MT_ID, MC_ID, WI_ID }` (5 attributes). No non-trivial dependency holds among these attributes. Candidate key: all five (= K1). Normal form: BCNF. |
| | 465 | * '''Dependency preservation:''' no dependency of the cover is affected. FD17 and FD18 are in `R_F`. The derived dependencies of `S6`/`S7` follow from FD12, FD15, FD17 and FD18, which are all preserved. ✓ |
| | 466 | * '''Lossless join:''' the intersection is `{ WI_ID }`, and `WI_ID → { WI_ID, W_ID }`. ✓ |
| | 467 | |
| | 468 | '''Result: every relation is in BCNF.''' The decomposition into these 12 relations is lossless |
| | 469 | (each of the 13 binary steps passed the test) and preserves all 18 dependencies of the |
| | 470 | canonical cover. |
| 407 | | '''This is the P2 design.''' Strip the `U_`/`C_`/`M_`/… prefixes back to plain column names and |
| 408 | | `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 |
| 409 | | key, `users, crypto, markets, holdings, orders, transactions, market_trades, market_candles, watchlists, watchlist_items` from |
| 410 | | [wiki:RelationalDesign]. Every foreign key matches, |
| 411 | | 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 |
| 412 | | phase shows the stronger result that the design is actually in BCNF). |
| 413 | | |
| 414 | | That is not a coincidence of two people happening to agree — it is what should happen when a |
| 415 | | design is derived correctly twice by two different methods from the same underlying model: |
| 416 | | P2 got here by applying the standard ER-to-relational transformation rules (each entity |
| 417 | | becomes a table on its own key, each attributed M:N relationship becomes a table on the |
| 418 | | combined key, each attributeless 1:N relationship becomes a foreign key on the "many" side). |
| 419 | | This phase got here by ignoring that transformation entirely, writing down only the |
| 420 | | attributes and the functional dependencies they obey, and mechanically applying 2NF/3NF/BCNF |
| 421 | | synthesis. Landing on the same ten relations either means the P2 transformation rules are |
| 422 | | sound for this particular model (which they are, for exactly the reason [wiki:RelationalDesign] (Normalisation section) |
| 423 | | already argued: single-column UUID primary keys everywhere rule out partial dependencies by |
| 424 | | construction, and no non-key attribute references another non-key attribute anywhere in the |
| 425 | | model, which rules out transitive dependencies too), or it is a coincidence spanning ten |
| 426 | | independently-checked relations and dozens of functional dependencies — the first explanation |
| 427 | | is the only credible one. |
| 428 | | |
| 429 | | '''The one substantive difference''' is `holdings.avg_price`, which P2 documents as a |
| 430 | | ''derived'' attribute — the running weighted-average buy price, recomputable from the `buy` rows |
| 431 | | in `transactions` — kept as a stored column anyway for read performance |
| 432 | | ([wiki:RelationalDesign] (Normalisation section) calls this out |
| 433 | | explicitly as an accepted denormalisation). Nothing in this phase's functional-dependency |
| 434 | | analysis can see that `H_AVG_PRICE` is derivable from `T_*` rows rather than stored |
| 435 | | independently — FD8 (`H_ID → H_AVG_PRICE`) is a perfectly ordinary functional dependency |
| 436 | | either way, because ''derivability from a different relation's rows'' is a property of the data |
| 437 | | and the application logic that maintains it (see |
| 438 | | [wiki:UseCase0004]'s `ON CONFLICT … DO UPDATE`), not something |
| 439 | | that shows up as a violation of any single-relation normal form. Formal normalization and "no |
| 440 | | column is a cached computation of other columns" are related but different concerns; this |
| 441 | | phase only checked the first one. |
| 442 | | |
| 443 | | '''Which design is used going forward:''' P2's, unchanged. Since the two designs coincide |
| 444 | | exactly, "restructuring the database objects" means confirming there is nothing to change |
| 445 | | rather than writing new DDL. `server/db/schema_creation.sql` |
| 446 | | already matches `R_USERS`…`R_WATCHLIST_ITEMS` column-for-column (including |
| 447 | | `holdings.reserved_quantity`, added between P2 and this phase — see |
| 448 | | [wiki:RelationalDesignAIUsage] (section "Session 3 — 2026-09-16") |
| 449 | | — which is `H_RESERVED_QUANTITY` above, correctly grouped under `R_HOLDINGS`'s key alongside |
| 450 | | `H_QUANTITY` and not treated as needing a relation of its own). P4's prototype |
| 451 | | (`server/trade.go`, `server/portfolio.go`) keeps working against the same schema without |
| 452 | | change. [wiki:RelationalDesign] has been updated with a |
| 453 | | short note pointing here as the formal validation of its normal-form claim. |
| 454 | | |
| 455 | | The table definitions in `server/db/schema_creation.sql`: |
| | 517 | '''The eleven data relations are the P2 design, with one difference''' (`transactions.user_id`, |
| | 518 | explained below). Each relation is one entity set of the ER model: |
| | 519 | |
| | 520 | ||= P5 relation =||= P2 table =||= How the relationships appear =|| |
| | 521 | || `R_USERS` || `users` || — || |
| | 522 | || `R_CRYPTO` || `crypto` || — || |
| | 523 | || `R_MARKETS` || `markets` || `C_ID` = `crypto_id` (`QuotedOn`) || |
| | 524 | || `R_HOLDINGS` || `holdings` || `U_ID` = `user_id` (`Holds`), `C_ID` = `crypto_id` (`PositionIn`) || |
| | 525 | || `R_ORDERS` || `orders` || `U_ID` = `user_id` (`Places`), `M_ID` = `market_id` (`PlacedOn`) || |
| | 526 | || `R_TRANSACTIONS` || `transactions` || `O_ID` = `related_order` (`Settles`); P2 also stores `user_id` (`Records`), see below || |
| | 527 | || `R_MARKET_TRADES` || `market_trades` || `M_ID` = `market_id` (`Fills`), `O_ID_FILLSBUY` = `buy_order_id`, `O_ID_FILLSSELL` = `sell_order_id` || |
| | 528 | || `R_ORDER_EVENTS` || `order_events` || `O_ID` = `order_id` (`Logs`) || |
| | 529 | || `R_MARKET_CANDLES` || `market_candles` || `M_ID` = `market_id` (`Aggregates`) || |
| | 530 | || `R_WATCHLISTS` || `watchlists` || `U_ID` = `user_id` (`Owns`) || |
| | 531 | || `R_WATCHLIST_ITEMS` || `watchlist_items` || `W_ID` = `watchlist_id` (`Contains`), `C_ID` = `crypto_id` (`Lists`) || |
| | 532 | |
| | 533 | The two methods produce the foreign keys differently. In P2 they come from a transformation |
| | 534 | rule: a 1:N relationship becomes a column on the N side. Here, each one appears because a |
| | 535 | dependency of kind (R), for example `O_ID → U_ID`, keeps the other entity's identifier in the |
| | 536 | same relation as the entity that depends on it. The candidate keys also match, including the |
| | 537 | composite ones (`{C_ID, M_QUOTE_CURRENCY}`, `{U_ID, C_ID}`, `{M_ID, MC_TIMEFRAME, |
| | 538 | MC_CANDLE_TIME}`, `{W_ID, C_ID}`). They are exactly the `UNIQUE` constraints in |
| | 539 | `schema_creation.sql`. |
| | 540 | |
| | 541 | '''The one difference: `transactions.user_id`.''' The decomposition drops `U_ID` from |
| | 542 | `R_TRANSACTIONS`, because `T_ID → U_ID` follows from `T_ID → O_ID` and `O_ID → U_ID`. That is |
| | 543 | correct for every ledger entry that settles an order. It does not work for a '''deposit'''. |
| | 544 | `Settles` is partial, so a deposit has no order, and without `user_id` a deposit would have no |
| | 545 | owner at all. The de-normalized relation cannot show this case. Every one of its tuples |
| | 546 | contains an order (every key contains `OE_ID`, and every order event has an order), so a |
| | 547 | ledger entry without an order cannot appear in it. P2 therefore keeps `user_id` (the |
| | 548 | relationship `Records`) as a deliberate exception. As a result, the implemented |
| | 549 | `transactions` table is in '''2NF but not in 3NF''' (`related_order → user_id` is a transitive |
| | 550 | dependency), and this is by design. For entries with an order, |
| | 551 | `transactions.user_id` repeats the order's user. The only code that sets `related_order` (the buy |
| | 552 | and sell inserts in `advanced_db.sql`) writes the user and the id of the same order row. No |
| | 553 | database constraint enforces this. |
| | 554 | |
| | 555 | '''Two order columns in `market_trades`.''' `FillsBuy` and `FillsSell` needed two role |
| | 556 | attributes already in the de-normalized relation, and both end up in `R_MARKET_TRADES`. |
| | 557 | They correspond to `buy_order_id` and `sell_order_id`. |
| | 558 | |
| | 559 | '''`R_KEY` belongs to the formal result, but it is not implemented as a table.''' It is the |
| | 560 | relation that contains a key of `R_EDUBERZA`, and the lossless-join result above holds for all |
| | 561 | 12 relations ''including'' it. It records no fact of the domain. It only says which ledger |
| | 562 | entry, order event, trade, candle and watchlist item were put into the same tuple, and that |
| | 563 | combination exists only because we started from one single relation. Not implementing it is |
| | 564 | an implementation decision. The eleven implemented tables are not claimed to reconstruct |
| | 565 | `R_EDUBERZA` on their own. They keep every attribute and every dependency of the canonical |
| | 566 | cover, and that is what the application needs. |
| | 567 | |
| | 568 | '''`holdings.avg_price`''' is shown as a ''derived'' attribute in the ER model: it can be |
| | 569 | recomputed from the buy history. It is still stored, and that is a deliberate |
| | 570 | denormalisation (see [wiki:RelationalDesign] (section "Normalisation")). |
| | 571 | Normalisation cannot detect this. `H_ID → H_AVG_PRICE` is an ordinary functional dependency, |
| | 572 | because "derivable from rows of another entity" is a property of the application logic |
| | 573 | that maintains the value (see [wiki:UseCase0004], |
| | 574 | `ON CONFLICT … DO UPDATE`), not a dependency between attributes of one tuple. |
| | 575 | |
| | 576 | '''Which design is used going forward:''' P2's, unchanged. The eleven data relations coincide |
| | 577 | with the eleven tables of `schema_creation.sql` and |
| | 578 | `advanced_db.sql` column for column, except for the |
| | 579 | deliberately kept `transactions.user_id` explained above. So there are no database objects |
| | 580 | to restructure, and the prototype and the reports of P6/P7 keep working against the same |
| | 581 | schema. |
| | 582 | |
| | 583 | The table definitions in `server/db/schema_creation.sql` and `server/db/advanced_db.sql`: |
