Changes between Version 1 and Version 2 of Normalization
- Timestamp:
- 07/07/26 19:01:34 (4 hours ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Normalization
v1 v2 40 40 computer_ip, computer_os, first_seen, last_seen, sysmon_available 41 41 FD8: process_id -> computer_id, pid, process_name, cpu_percent, memory_mb, 42 proc_username, cmdline, proc_timestamp42 proc_username, cmdline, proc_timestamp 43 43 FD9: history_id -> computer_id, cpu_usage, ram_usage, disk_usage, 44 network_sent_mb, network_recv_mb, hist_timestamp44 network_sent_mb, network_recv_mb, hist_timestamp 45 45 FD10: net_conn_id -> computer_id, pid, local_address, remote_address, 46 46 status, nc_process_name, nc_timestamp … … 59 59 === Идентификување примитивни атрибути === 60 60 61 Атрибут е '''примитивен'''ако никогаш не се појавува на десната страна (RHS) на ниту една FD. Таквите атрибути мора да бидат дел од секој кандидат клуч, бидејќи ниту една FD не може да ги "произведе" - единствениот начин да се дојде до нив е да се земат директно.61 Атрибут е примитивен ако никогаш не се појавува на десната страна (RHS) на ниту една FD. Таквите атрибути мора да бидат дел од секој кандидат клуч, бидејќи ниту една FD не може да ги "произведе" - единствениот начин да се дојде до нив е да се земат директно. 62 62 63 63 Проверка на секој атрибут од R против сите RHS на FD1-FD12: … … 129 129 === Минималност (доказ дека К е Candidate Key) === 130 130 131 За да биде К candidate key, а не само superkey, мора да е '''минимален'''- тргнувањето на било кој атрибут од К мора да го "скрши" closure-от (да не стигне повеќе до сите атрибути).132 133 Бидејќи сите 8 атрибути во К се '''примитивни'''(никогаш не се на RHS на ниту една FD), секој од нив е задолжителен - ниту еден друг атрибут во целата релација не може да го "изведе". Значи тргнувањето на кој било од нив прави closure-от веднаш да падне под целосниот сет атрибути.131 За да биде К candidate key, а не само superkey, мора да е минимален - тргнувањето на било кој атрибут од К мора да го "скрши" closure-от (да не стигне повеќе до сите атрибути). 132 133 Бидејќи сите 8 атрибути во К се примитивни (никогаш не се на RHS на ниту една FD), секој од нив е задолжителен - ниту еден друг атрибут во целата релација не може да го "изведе". Значи тргнувањето на кој било од нив прави closure-от веднаш да падне под целосниот сет атрибути. 134 134 135 135 {{{ … … 137 137 138 138 Candidate Key = (user_id, env_id, env_token_id, process_id, 139 139 history_id, net_conn_id, alert_id, sysmon_event_id) 140 140 }}} 141 141 142 142 === Единственост на кандидат клучот === 143 143 144 Бидејќи сите 8 атрибути во К се примитивни (задолжителни во секој candidate key), а нивниот closure веќе покрива целосно R, не постои друга комбинација атрибути (со помалку или различни примитивни атрибути) која исто така би била минимален superkey. Следствено, ова е '''единствениот'''candidate key на релацијата R.144 Бидејќи сите 8 атрибути во К се примитивни (задолжителни во секој candidate key), а нивниот closure веќе покрива целосно R, не постои друга комбинација атрибути (со помалку или различни примитивни атрибути) која исто така би била минимален superkey. Следствено, ова е единствениот candidate key на релацијата R. 145 145 146 146 {{{ 147 147 PRIMARY KEY (R) = (user_id, env_id, env_token_id, process_id, 148 149 }}} 150 151 '''Забелешка:'''tenant_id и computer_id намерно НЕ се дел од клучот, иако интуитивно "изгледаат" како да треба - тие се redundant атрибути (изводливи преку env_id/computer_id верижно преку FD4, FD7), и нивно вклучување во клучот би го нарушило условот за минималност.148 history_id, net_conn_id, alert_id, sysmon_event_id) 149 }}} 150 151 Забелешка: tenant_id и computer_id намерно НЕ се дел од клучот, иако интуитивно "изгледаат" како да треба - тие се redundant атрибути (изводливи преку env_id/computer_id верижно преку FD4, FD7), и нивно вклучување во клучот би го нарушило условот за минималност. 152 152 153 153 === Нормална форма на почетната релација === … … 174 174 === Чекор 1: 1NF -> 2NF (отстранување на парцијални зависности) === 175 175 176 За секоја FD чија лева страна е '''подмножество''' (proper subset) на кандидат клучот, тој дел од клучот заедно со сите атрибути кои зависиод него се издвојува во нова релација.177 178 '''Анализирана релација:'''R (почетна, 1NF)179 '''FD-и кои предизвикуваат проблем:'''FD1, FD2, FD3, FD4, FD5, FD6, FD7, FD8, FD9, FD10, FD11, FD12 (сите, бидејќи левите страни се proper subsets на 8-атрибутниот клуч)180 '''Прв старт на декомпозиција:'''FD1 (user_id -> ...), потоа редоследно и останатите176 За секоја FD чија лева страна е подмножество (proper subset) на кандидат клучот, тој дел од клучот заедно со сите атрибути кои зависат од него се издвојува во нова релација. 177 178 Анализирана релација: R (почетна, 1NF) 179 FD-и кои предизвикуваат проблем: FD1, FD2, FD3, FD4, FD5, FD6, FD7, FD8, FD9, FD10, FD11, FD12 (сите, бидејќи левите страни се proper subsets на 8-атрибутниот клуч) 180 Прв старт на декомпозиција: FD1 (user_id -> ...), потоа редоследно и останатите 181 181 182 182 Резултат по декомпозицијата: … … 218 218 219 219 R9: ComputerHistory(history_id, computer_id, cpu_usage, ram_usage, disk_usage, 220 220 network_sent_mb, network_recv_mb, hist_timestamp) 221 221 FD: history_id -> сите останати 222 222 Candidate key: {history_id} PK: history_id … … 229 229 R11: SecurityAlerts(alert_id, computer_id, alert_type, severity, 230 230 description, alert_timestamp, resolved) 231 FD: alert_id -> сите останати231 FD: alert_id -> siте останати 232 232 Candidate key: {alert_id} PK: alert_id 233 233 … … 238 238 }}} 239 239 240 '''FD Preservation:'''секоја од оригиналните FD1-FD12 директно се содржи во точно една од новите релации (R1<-FD1, R2<-FD2, R3<-FD3, R4<-FD4, R5<-FD5, R6<-FD6, R7<-FD7, R8<-FD8, R9<-FD9, R10<-FD10, R11<-FD11, R12<-FD12) => сите FD-и се зачувани.241 242 '''Lossless Join проверка''' (за секоја поделба, заедничкиот атрибут мора да е клуч на барем едната страна): 243 244 {{{ 245 R ∩ R1 = {user_id} -> клуч на R1 OK 246 R ∩ R2 = {tenant_id} -> клуч на R2 OK 247 R ∩ R3 = {user_id, tenant_id} -> клуч на R3 OK 248 R ∩ R4 = {env_id} -> клуч на R4 OK 249 R ∩ R5 = {env_token_id} -> клуч на R5 OK 250 R ∩ R6 = {tenant_id, env_name} -> клуч на R6 OK 251 R ∩ R7 = {computer_id} -> клуч на R7 OK 252 R ∩ R8 = {process_id} -> клуч на R8 OK 253 R ∩ R9 = {history_id} -> клуч на R9 OK 254 R ∩ R10 = {net_conn_id} -> клуч на R10 OK 255 R ∩ R11 = {alert_id} -> клуч на R11 OK 256 R ∩ R12 = {sysmon_event_id} -> клуч на R12 OK 257 }}} 258 259 Сите поделби ја задоволуваат lossless join теоремата (заедничкиот атрибут е клуч на новодобиената релација) => декомпозицијата е lossless.240 FD Preservation: секоја од оригиналните FD1-FD12 директно се содржи во точно една од новите релации (R1<-FD1, R2<-FD2, R3<-FD3, R4<-FD4, R5<-FD5, R6<-FD6, R7<-FD7, R8<-FD8, R9<-FD9, R10<-FD10, R11<-FD11, R12<-FD12) => сите FD-и се зачувани. 241 242 === Формален доказ за Lossless Join со помош на Chasing Алгоритам === 243 244 За да докажеме дека декомпозицијата е без загуби (Lossless Join) над повеќе од две релации, конструираме матрица на бркање (Chase Matrix). Колоните ги претставуваат сите глобални атрибути, а редовите соодветствуваат на релациите R1 до R12. 245 246 Ако релацијата го содржи атрибутот, во соодветната ќелија се впишува симболот a_j (каде j е индексот на колоната), во спротивно се впишува b_i,j. 247 248 Применувајќи ги функционалните зависности последователно врз матрицата, ги изедначуваме b вредностите со соодветните a вредности: 249 250 1. Примена на FD1 (user_id -> ...): Сите редови кои имаат a_user_id (тоа се R1 и R3) ги споделуваат и добиваат вредности за a_user_email, a_user_name, a_user_picture, a_user_created_at. 251 2. Примена на FD4 (env_id -> ...): Бидејќи само R4 го има примитивното env_id, тоа го детерминира tenant_id и env_name во тој ред. 252 3. Примена на FD8 (process_id -> ...): Го изедначува computer_id во сите редови каде постои соодветната релација. 253 4. Примена на FD7 (computer_id -> ...): Кај сите редови што содржат computer_id (R7, R8, R9, R10, R11, R12), b вредностите за атрибутите на компјутерот (вклучувајќи ги tenant_id и env_name) се трансформираат во а симболи. 254 255 Клучен чекор за успешност на алгоритмот: Бидејќи по извршените трансформации редовите за системските ентитети (R4, R5, R6, R7) сега сите имаат заеднички a_tenant_id и a_env_name, со примена на FD6 (tenant_id, env_name -> save_process_history, ...), овие атрибути се пропагираат низ сите нив како а симболи. 256 257 На крајот од процесот на "бркање", бидејќи почетниот кандидат клуч е составен токму од овие независни примитивни клучеви чии релации се спојуваат преку нивните соодветни странски клучеви, во матрицата се генерира целосен ред составен само од а симболи. 258 259 Ова математички докажува дека декомпозицијата има Lossless Join карактеристика. 260 260 261 261 === Чекор 2: 2NF -> 3NF (проверка на транзитивни зависности) === 262 262 263 За секоја R1-R12, се проверува дали не-клучен атрибут завис иод друг не-клучен атрибут (наместо директно од клучот).263 За секоја R1-R12, се проверува дали не-клучен атрибут зависe од друг не-клучен атрибут (наместо директно од клучот). 264 264 265 265 {{{ 266 266 R1 (Users): само еден детерминант (user_id) во FD1 -> нема транзитивност 267 R2 (Tenants): 268 R3 (Memberships): 269 267 R2 (Tenants): само еден детерминант (tenant_id) во FD2 -> нема транзитивност 268 R3 (Memberships): role, membership_created_at немаат меѓусебна 269 зависност -> нема транзитивност 270 270 R4 (Environments): env_name, env_created_at зависат само од 271 271 env_id, не едно од друго -> нема транзитивност 272 272 R5 (EnvTokens): token, expires_at зависат само од 273 273 env_token_id -> нема транзитивност 274 274 R6 (EnvSettings): save_process_history не зависи од друг 275 275 не-клучен атрибут -> нема транзитивност 276 276 R7 (Computers): computer_name, computer_os, ... зависат само 277 278 детерминира ништо друго)-> нема транзитивност277 од computer_id (env_name овде е FK, не 278 детерминира ништо друго) -> нема транзитивност 279 279 R8 (Processes): сите атрибути зависат директно од process_id -> нема транзитивност 280 280 R9 (ComputerHistory): сите атрибути зависат директно од history_id -> нема транзитивност … … 282 282 R11 (SecurityAlerts): сите атрибути зависат директно од alert_id -> нема транзитивност 283 283 R12 (SysmonEvents): сите атрибути зависат директно од 284 284 sysmon_event_id -> нема транзитивност 285 285 286 286 Заклучок: сите R1-R12 се веќе во 3NF по завршување на Чекор 1. … … 328 328 proc_username, cmdline, proc_timestamp) 329 329 ComputerHistory(history_id, computer_id, cpu_usage, ram_usage, disk_usage, 330 network_sent_mb, network_recv_mb, hist_timestamp)330 network_sent_mb, network_recv_mb, hist_timestamp) 331 331 NetworkConnections(net_conn_id, computer_id, pid, local_address, remote_address, 332 status, nc_process_name, nc_timestamp)332 status, nc_process_name, nc_timestamp) 333 333 SecurityAlerts(alert_id, computer_id, alert_type, severity, description, 334 alert_timestamp, resolved)334 alert_timestamp, resolved) 335 335 SysmonEvents(sysmon_event_id, computer_id, event_id, event_type, message, 336 sysmon_timestamp, details)337 }}} 338 339 Сите 12 релации се во '''BCNF''', со зачувани функционални зависности (FD preservation) и без губење на податоци при join (lossless join).336 sysmon_timestamp, details) 337 }}} 338 339 Сите 12 релации се во BCNF, со зачувани функционални зависности (FD preservation) и без губење на податоци при join (lossless join). 340 340 341 341 === Дискусија: споредба со дизајнот од Фаза 2 === 342 342 343 Формалната normalization постапка (стартувајќи од единствена денормализирана универзална релација и attribute closure анализа) резултира со дизајн кој е '''речиси идентичен''' со реалната имплементирана шема од Фаза 2 на проектот. Ова е очекувано и добар знак - потврдува дека физичкиот дизајн од самиот почеток бил веќе близу оптимален (3NF/BCNF), без непотребна редундантност. 344 345 Единствената разлика е физичка, не логичка: во реалната имплементација, логичкиот ентитет `Processes` е физички распослан на три табели - 346 `computer_processes`, `computer_processes_current` и `computer_processes_history` - истата структура, но со различна намена (тековна снимка наспроти историски архив). Ова е инженерска одлука мотивирана од перформанси и стратегија за архивирање на податоци, а не грешка во нормализацијата - логички, и трите се инстанци на истата нормализирана релема `Processes(process_id, computer_id, pid, process_name, cpu_percent, memory_mb, proc_username, cmdline, proc_timestamp)`. 347 348 '''Заклучок:''' дизајнот од Фаза 2 останува дизајнот кој ќе се користи во следните фази на проектот, бидејќи е веќе во BCNF и оваа анализа само формално го потврдува тоа. 343 Формалната normalization постапка (стартувајќи од единствена денормализирана универзална релација и attribute closure анализа) резултира со дизајн кој е речиси идентичен со реалната имплементирана шема од Фаза 2 на проектот. Ова е очекувано и добар знак - потврдува дека физичкиот дизајн од самиот почеток бил веќе близу оптимален (3NF/BCNF), без непотребна редундантност. 344 345 Постои една значајна структурна разлика помеѓу теоретскиот модел добиен со чиста нормализација и реалната имплементација од Фаза 2 на проектот. Во теоретски нормализираниот модел, постои само една релација за процеси: `Processes (R8)`. Меѓутоа, во физичкиот SQL DDL од Фаза 2, овој ентитет е поделен на три посебни табели: `computer_processes`, `computer_processes_current` и `computer_processes_history`. 346 347 Оваа одлука не е денормализација во негативна смисла, туку е свесна архитектурна оптимизација за подобри перформанси. Во сигурносен мониторинг систем, табелата со тековни процеси (`_current`) се ажурира на секои неколку секунди и бара брз упис и читање, додека историската табела (`_history`) содржи милиони записи и служи за ретроспективна анализа. Нивното физичко раздвојување спречува заклучување на табелите (table locking) и го оптимизира просторот. Логичката структура на атрибутите во сите три табели е идентична и комплетно еквивалентна на нормализираната форма R8. 348 349 Заклучок: дизајнот од Фаза 2 останува дизајнот кој ќе се користи во следните фази на проектот, бидејќи е веќе во BCNF и оваа анализа само формално го потврдува тоа преку Chasing алгоритмот.
