| Version 2 (modified by , 4 hours ago) ( diff ) |
|---|
Phase P5: Normalization
a) Initial De-normalized Relation and Functional Dependencies
Global Attribute List (unified relation R)
Сите атрибути од целиот ER модел, обединети во една единствена релација R, без дупликати имиња:
R( user_id, user_email, user_name, user_picture, user_created_at, tenant_id, tenant_name, owner_email, tenant_created_at, role, membership_created_at, env_id, env_name, env_created_at, env_token_id, token, et_created_at, expires_at, save_process_history, es_created_at, es_updated_at, computer_id, computer_name, computer_user, computer_ip, computer_os, first_seen, last_seen, sysmon_available, process_id, pid, process_name, cpu_percent, memory_mb, proc_username, cmdline, proc_timestamp, history_id, cpu_usage, ram_usage, disk_usage, network_sent_mb, network_recv_mb, hist_timestamp, net_conn_id, local_address, remote_address, status, nc_process_name, nc_timestamp, alert_id, alert_type, severity, description, alert_timestamp, resolved, sysmon_event_id, event_id, event_type, message, sysmon_timestamp, details )
Canonical Cover — Global Set of Functional Dependencies
FD1: user_id -> user_email, user_name, user_picture, user_created_at
FD2: tenant_id -> tenant_name, owner_email, tenant_created_at
FD3: (user_id, tenant_id) -> role, membership_created_at
FD4: env_id -> tenant_id, env_name, env_created_at
FD5: env_token_id -> tenant_id, env_name, token, et_created_at, expires_at
FD6: (tenant_id, env_name) -> save_process_history, es_created_at, es_updated_at
FD7: computer_id -> tenant_id, env_name, computer_name, computer_user,
computer_ip, computer_os, first_seen, last_seen, sysmon_available
FD8: process_id -> computer_id, pid, process_name, cpu_percent, memory_mb,
proc_username, cmdline, proc_timestamp
FD9: history_id -> computer_id, cpu_usage, ram_usage, disk_usage,
network_sent_mb, network_recv_mb, hist_timestamp
FD10: net_conn_id -> computer_id, pid, local_address, remote_address,
status, nc_process_name, nc_timestamp
FD11: alert_id -> computer_id, alert_type, severity, description,
alert_timestamp, resolved
FD12: sysmon_event_id -> computer_id, event_id, event_type, message,
sysmon_timestamp, details
Ова е канонски cover (минимален сет): секоја FD има единствен атрибут / минимален сет на левата страна, нема вишок FD-и кои можат да се изведат од другите, и нема redundant атрибути на десните страни.
b) Candidate Keys and Primary Key Selection
Идентификување примитивни атрибути
Атрибут е примитивен ако никогаш не се појавува на десната страна (RHS) на ниту една FD. Таквите атрибути мора да бидат дел од секој кандидат клуч, бидејќи ниту една FD не може да ги "произведе" - единствениот начин да се дојде до нив е да се земат директно.
Проверка на секој атрибут од R против сите RHS на FD1-FD12:
Примитивни атрибути (никогаш на RHS): user_id, env_id, env_token_id, process_id, history_id, net_conn_id, alert_id, sysmon_event_id Забелешка: tenant_id и computer_id НЕ се примитивни - тие се појавуваат на RHS во FD4, FD5, FD7 (изведливи атрибути).
Пробен клуч и Attribute Closure (K+)
K = { user_id, env_id, env_token_id, process_id,
history_id, net_conn_id, alert_id, sysmon_event_id }
Пресметка на closure K+ чекор по чекор:
K+ (почетно) = K
Применуваме FD1 (user_id):
K+ = K+ U { user_email, user_name, user_picture, user_created_at }
Применуваме FD4 (env_id):
K+ = K+ U { tenant_id, env_name, env_created_at }
Применуваме FD5 (env_token_id):
K+ = K+ U { token, et_created_at, expires_at }
(tenant_id, env_name веќе се во K+)
Применуваме FD8 (process_id):
K+ = K+ U { computer_id, pid, process_name, cpu_percent, memory_mb,
proc_username, cmdline, proc_timestamp }
Применуваме FD9 (history_id):
K+ = K+ U { cpu_usage, ram_usage, disk_usage,
network_sent_mb, network_recv_mb, hist_timestamp }
Применуваме FD10 (net_conn_id):
K+ = K+ U { local_address, remote_address, status,
nc_process_name, nc_timestamp }
Применуваме FD11 (alert_id):
K+ = K+ U { alert_type, severity, description, alert_timestamp, resolved }
Применуваме FD12 (sysmon_event_id):
K+ = K+ U { event_id, event_type, message, sysmon_timestamp, details }
Сега computer_id е веќе во K+ -> применуваме FD7:
K+ = K+ U { computer_name, computer_user, computer_ip, computer_os,
first_seen, last_seen, sysmon_available }
Сега (tenant_id, env_name) се двете во K+ -> применуваме FD6:
K+ = K+ U { save_process_history, es_created_at, es_updated_at }
Сега (user_id, tenant_id) се двете во K+ -> применуваме FD3:
K+ = K+ U { role, membership_created_at }
------------------------------------------------------
K+ = сите атрибути на R => K е superkey
------------------------------------------------------
Минималност (доказ дека К е Candidate Key)
За да биде К candidate key, а не само superkey, мора да е минимален - тргнувањето на било кој атрибут од К мора да го "скрши" closure-от (да не стигне повеќе до сите атрибути).
Бидејќи сите 8 атрибути во К се примитивни (никогаш не се на RHS на ниту една FD), секој од нив е задолжителен - ниту еден друг атрибут во целата релација не може да го "изведе". Значи тргнувањето на кој било од нив прави closure-от веднаш да падне под целосниот сет атрибути.
=> K е минимален superkey => K е Candidate Key
Candidate Key = (user_id, env_id, env_token_id, process_id,
history_id, net_conn_id, alert_id, sysmon_event_id)
Единственост на кандидат клучот
Бидејќи сите 8 атрибути во К се примитивни (задолжителни во секој candidate key), а нивниот closure веќе покрива целосно R, не постои друга комбинација атрибути (со помалку или различни примитивни атрибути) која исто така би била минимален superkey. Следствено, ова е единствениот candidate key на релацијата R.
PRIMARY KEY (R) = (user_id, env_id, env_token_id, process_id,
history_id, net_conn_id, alert_id, sysmon_event_id)
Забелешка: tenant_id и computer_id намерно НЕ се дел од клучот, иако интуитивно "изгледаат" како да треба - тие се redundant атрибути (изводливи преку env_id/computer_id верижно преку FD4, FD7), и нивно вклучување во клучот би го нарушило условот за минималност.
Нормална форма на почетната релација
1NF: ДА - сите вредности се атомски, нема повторувачки групи/низи
2NF: НЕ - клучот е composite (8 атрибути), но постојат атрибути кои
зависат само од ДЕЛ од клучот:
* user_email, user_name, ... зависат само од user_id
* token, et_created_at, ... зависат само од env_token_id
* process_name, cpu_percent, ... зависат само од process_id
* ... (аналогно за сите останати FD-и)
Ова е класична парцијална зависност -> нарушување на 2NF.
Заклучок: почетната релација R е само во 1NF.
Декомпозицијата започнува со отстранување на парцијалните зависности.
c) Step-by-Step Decomposition
Чекор 1: 1NF -> 2NF (отстранување на парцијални зависности)
За секоја FD чија лева страна е подмножество (proper subset) на кандидат клучот, тој дел од клучот заедно со сите атрибути кои зависат од него се издвојува во нова релација.
Анализирана релација: R (почетна, 1NF) FD-и кои предизвикуваат проблем: FD1, FD2, FD3, FD4, FD5, FD6, FD7, FD8, FD9, FD10, FD11, FD12 (сите, бидејќи левите страни се proper subsets на 8-атрибутниот клуч) Прв старт на декомпозиција: FD1 (user_id -> ...), потоа редоследно и останатите
Резултат по декомпозицијата:
R1: Users(user_id, user_email, user_name, user_picture, user_created_at)
FD: user_id -> сите останати
Candidate key: {user_id} PK: user_id
R2: Tenants(tenant_id, tenant_name, owner_email, tenant_created_at)
FD: tenant_id -> сите останати
Candidate key: {tenant_id} PK: tenant_id
R3: Memberships(user_id, tenant_id, role, membership_created_at)
FD: (user_id, tenant_id) -> role, membership_created_at
Candidate key: {user_id, tenant_id} PK: (user_id, tenant_id)
R4: Environments(env_id, tenant_id, env_name, env_created_at)
FD: env_id -> tenant_id, env_name, env_created_at
Candidate key: {env_id} PK: env_id
R5: EnvTokens(env_token_id, tenant_id, env_name, token, et_created_at, expires_at)
FD: env_token_id -> сите останати
Candidate key: {env_token_id} PK: env_token_id
R6: EnvSettings(tenant_id, env_name, save_process_history, es_created_at, es_updated_at)
FD: (tenant_id, env_name) -> save_process_history, es_created_at, es_updated_at
Candidate key: {tenant_id, env_name} PK: (tenant_id, env_name)
R7: Computers(computer_id, tenant_id, env_name, computer_name, computer_user,
computer_ip, computer_os, first_seen, last_seen, sysmon_available)
FD: computer_id -> сите останати
Candidate key: {computer_id} PK: computer_id
R8: Processes(process_id, computer_id, pid, process_name, cpu_percent,
memory_mb, proc_username, cmdline, proc_timestamp)
FD: process_id -> сите останати
Candidate key: {process_id} PK: process_id
R9: ComputerHistory(history_id, computer_id, cpu_usage, ram_usage, disk_usage,
network_sent_mb, network_recv_mb, hist_timestamp)
FD: history_id -> сите останати
Candidate key: {history_id} PK: history_id
R10: NetworkConnections(net_conn_id, computer_id, pid, local_address,
remote_address, status, nc_process_name, nc_timestamp)
FD: net_conn_id -> сите останати
Candidate key: {net_conn_id} PK: net_conn_id
R11: SecurityAlerts(alert_id, computer_id, alert_type, severity,
description, alert_timestamp, resolved)
FD: alert_id -> siте останати
Candidate key: {alert_id} PK: alert_id
R12: SysmonEvents(sysmon_event_id, computer_id, event_id, event_type,
message, sysmon_timestamp, details)
FD: sysmon_event_id -> сите останати
Candidate key: {sysmon_event_id} PK: sysmon_event_id
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-и се зачувани.
Формален доказ за Lossless Join со помош на Chasing Алгоритам
За да докажеме дека декомпозицијата е без загуби (Lossless Join) над повеќе од две релации, конструираме матрица на бркање (Chase Matrix). Колоните ги претставуваат сите глобални атрибути, а редовите соодветствуваат на релациите R1 до R12.
Ако релацијата го содржи атрибутот, во соодветната ќелија се впишува симболот a_j (каде j е индексот на колоната), во спротивно се впишува b_i,j.
Применувајќи ги функционалните зависности последователно врз матрицата, ги изедначуваме b вредностите со соодветните a вредности:
- Примена на FD1 (user_id -> ...): Сите редови кои имаат a_user_id (тоа се R1 и R3) ги споделуваат и добиваат вредности за a_user_email, a_user_name, a_user_picture, a_user_created_at.
- Примена на FD4 (env_id -> ...): Бидејќи само R4 го има примитивното env_id, тоа го детерминира tenant_id и env_name во тој ред.
- Примена на FD8 (process_id -> ...): Го изедначува computer_id во сите редови каде постои соодветната релација.
- Примена на FD7 (computer_id -> ...): Кај сите редови што содржат computer_id (R7, R8, R9, R10, R11, R12), b вредностите за атрибутите на компјутерот (вклучувајќи ги tenant_id и env_name) се трансформираат во а симболи.
Клучен чекор за успешност на алгоритмот: Бидејќи по извршените трансформации редовите за системските ентитети (R4, R5, R6, R7) сега сите имаат заеднички a_tenant_id и a_env_name, со примена на FD6 (tenant_id, env_name -> save_process_history, ...), овие атрибути се пропагираат низ сите нив како а симболи.
На крајот од процесот на "бркање", бидејќи почетниот кандидат клуч е составен токму од овие независни примитивни клучеви чии релации се спојуваат преку нивните соодветни странски клучеви, во матрицата се генерира целосен ред составен само од а симболи.
Ова математички докажува дека декомпозицијата има Lossless Join карактеристика.
Чекор 2: 2NF -> 3NF (проверка на транзитивни зависности)
За секоја R1-R12, се проверува дали не-клучен атрибут зависe од друг не-клучен атрибут (наместо директно од клучот).
R1 (Users): само еден детерминант (user_id) во FD1 -> нема транзитивност
R2 (Tenants): само еден детерминант (tenant_id) во FD2 -> нема транзитивност
R3 (Memberships): role, membership_created_at немаат меѓусебна
зависност -> нема транзитивност
R4 (Environments): env_name, env_created_at зависат само од
env_id, не едно од друго -> нема транзитивност
R5 (EnvTokens): token, expires_at зависат само од
env_token_id -> нема транзитивност
R6 (EnvSettings): save_process_history не зависи од друг
не-клучен атрибут -> нема транзитивност
R7 (Computers): computer_name, computer_os, ... зависат само
од computer_id (env_name овде е FK, не
детерминира ништо друго) -> нема транзитивност
R8 (Processes): сите атрибути зависат директно од process_id -> нема транзитивност
R9 (ComputerHistory): сите атрибути зависат директно од history_id -> нема транзитивност
R10 (NetworkConnections): сите атрибути зависат директно од net_conn_id -> нема транзитивност
R11 (SecurityAlerts): сите атрибути зависат директно од alert_id -> нема транзитивност
R12 (SysmonEvents): сите атрибути зависат директно од
sysmon_event_id -> нема транзитивност
Заклучок: сите R1-R12 се веќе во 3NF по завршување на Чекор 1.
Чекор 3: 3NF -> BCNF
За BCNF, за секоја нетривијална FD X -> Y во релацијата, X мора да е superkey.
R1: единствена FD е user_id -> ... user_id е PK -> superkey BCNF OK R2: единствена FD е tenant_id -> ... tenant_id е PK -> superkey BCNF OK R3: единствена FD е (user_id,tenant_id)->... тоа е PK -> superkey BCNF OK R4: единствена FD е env_id -> ... env_id е PK -> superkey BCNF OK R5: единствена FD е env_token_id -> ... env_token_id е PK -> superkey BCNF OK R6: единствена FD е (tenant_id,env_name)->.. тоа е PK -> superkey BCNF OK R7: единствена FD е computer_id -> ... computer_id е PK -> superkey BCNF OK R8: единствена FD е process_id -> ... process_id е PK -> superkey BCNF OK R9: единствена FD е history_id -> ... history_id е PK -> superkey BCNF OK R10: единствена FD е net_conn_id -> ... net_conn_id е PK -> superkey BCNF OK R11: единствена FD е alert_id -> ... alert_id е PK -> superkey BCNF OK R12: единствена FD е sysmon_event_id -> ... sysmon_event_id е PK -> superkey BCNF OK Заклучок: сите R1-R12 се веќе во BCNF. Декомпозицијата завршува по еден единствен чекор (1NF -> 2NF), бидејќи истовремено ги отстранивме сите парцијални И транзитивни зависности.
d) Final Result and Discussion
Финален нормализиран дизајн
Users(user_id, user_email, user_name, user_picture, user_created_at)
Tenants(tenant_id, tenant_name, owner_email, tenant_created_at)
Memberships(user_id, tenant_id, role, membership_created_at)
Environments(env_id, tenant_id, env_name, env_created_at)
EnvTokens(env_token_id, tenant_id, env_name, token, et_created_at, expires_at)
EnvSettings(tenant_id, env_name, save_process_history, es_created_at, es_updated_at)
Computers(computer_id, tenant_id, env_name, computer_name, computer_user,
computer_ip, computer_os, first_seen, last_seen, sysmon_available)
Processes(process_id, computer_id, pid, process_name, cpu_percent, memory_mb,
proc_username, cmdline, proc_timestamp)
ComputerHistory(history_id, computer_id, cpu_usage, ram_usage, disk_usage,
network_sent_mb, network_recv_mb, hist_timestamp)
NetworkConnections(net_conn_id, computer_id, pid, local_address, remote_address,
status, nc_process_name, nc_timestamp)
SecurityAlerts(alert_id, computer_id, alert_type, severity, description,
alert_timestamp, resolved)
SysmonEvents(sysmon_event_id, computer_id, event_id, event_type, message,
sysmon_timestamp, details)
Сите 12 релации се во BCNF, со зачувани функционални зависности (FD preservation) и без губење на податоци при join (lossless join).
Дискусија: споредба со дизајнот од Фаза 2
Формалната normalization постапка (стартувајќи од единствена денормализирана универзална релација и attribute closure анализа) резултира со дизајн кој е речиси идентичен со реалната имплементирана шема од Фаза 2 на проектот. Ова е очекувано и добар знак - потврдува дека физичкиот дизајн од самиот почеток бил веќе близу оптимален (3NF/BCNF), без непотребна редундантност.
Постои една значајна структурна разлика помеѓу теоретскиот модел добиен со чиста нормализација и реалната имплементација од Фаза 2 на проектот. Во теоретски нормализираниот модел, постои само една релација за процеси: Processes (R8). Меѓутоа, во физичкиот SQL DDL од Фаза 2, овој ентитет е поделен на три посебни табели: computer_processes, computer_processes_current и computer_processes_history.
Оваа одлука не е денормализација во негативна смисла, туку е свесна архитектурна оптимизација за подобри перформанси. Во сигурносен мониторинг систем, табелата со тековни процеси (_current) се ажурира на секои неколку секунди и бара брз упис и читање, додека историската табела (_history) содржи милиони записи и служи за ретроспективна анализа. Нивното физичко раздвојување спречува заклучување на табелите (table locking) и го оптимизира просторот. Логичката структура на атрибутите во сите три табели е идентична и комплетно еквивалентна на нормализираната форма R8.
Заклучок: дизајнот од Фаза 2 останува дизајнот кој ќе се користи во следните фази на проектот, бидејќи е веќе во BCNF и оваа анализа само формално го потврдува тоа преку Chasing алгоритмот.
