Нормализација

Денормализирана форма на базата

Тргнуваме од една унифицирана релација R која ги содржи сите атрибути од ЕР моделот. Бидејќи имињата на атрибутите мора да бидат единствени, атрибутите се именувани со префикс според ентитетот.

Работниците и администраторите учествуваат во повеќе релации со различни улоги (работник кој менува статус, кој пишува коментар и кој е доделен; администратор кој управува со категорија и кој доделува пријава). Една иста вредност не може да ги опише сите улоги во еден ред, па за секоја улога се воведува посебен атрибут (log_worker_id, comment_worker_id, assignment_worker_id, category_admin_id, assignment_admin_id). Сопствените атрибути на работникот и администраторот (worker_id, admin_id и нивните податоци) остануваат посебни. Граѓанинот и категоријата учествуваат само во една релација, па citizen_id и category_id се исти атрибути и во ентитетот и во пријавата. Сите фотографии, статуси, коментари и доделувања во еден ред се однесуваат на иста пријава, па report_id е еден атрибут.

R(admin_id, admin_full_name, admin_email, admin_password,
  worker_id, worker_full_name, worker_email, worker_password,
  citizen_id, citizen_full_name, citizen_email, citizen_phone, citizen_password,
  category_id, category_name, category_admin_id,
  report_id, report_description, location_text, latitude, longitude,
  report_status, report_priority, report_created_at,
  photo_id, image_url,
  log_id, log_status, log_changed_at, log_note, log_worker_id,
  comment_id, comment_content, comment_created_at, comment_worker_id,
  assignment_id, assignment_assigned_at, assignment_note,
  assignment_admin_id, assignment_worker_id)

Функционални зависности

Канонично покривање на множеството функционални зависности кои важат секогаш и секаде во R (десните страни се групирани заради прегледност, според правилото за унија):

ЗФ1:  admin_id    → admin_full_name, admin_email, admin_password
ЗФ2:  admin_email → admin_id
ЗФ3:  worker_id    → worker_full_name, worker_email, worker_password
ЗФ4:  worker_email → worker_id
ЗФ5:  citizen_id    → citizen_full_name, citizen_email, citizen_phone, citizen_password
ЗФ6:  citizen_email → citizen_id
ЗФ7:  category_id   → category_name, category_admin_id
ЗФ8:  category_name → category_id
ЗФ9:  report_id → report_description, location_text, latitude, longitude,
                  report_status, report_priority, report_created_at,
                  citizen_id, category_id
ЗФ10: photo_id → image_url, report_id
ЗФ11: log_id → log_status, log_changed_at, log_note, log_worker_id, report_id
ЗФ12: comment_id → comment_content, comment_created_at, comment_worker_id, report_id
ЗФ13: assignment_id → assignment_assigned_at, assignment_note,
                      assignment_admin_id, assignment_worker_id, report_id
ЗФ14: report_id, assignment_worker_id → assignment_id

Објаснувања:

• ЗФ2, ЗФ4, ЗФ6 и ЗФ8 важат бидејќи е-поштата и името на категоријата се единствени.
• ЗФ14 важи бидејќи ист работник не може двапати да биде доделен на иста пријава.
• Меѓу координатите и адресата нема функционална зависност, бидејќи адресата се внесува рачно и не е секогаш присутна.
• Атрибутите со улоги (log_worker_id, comment_worker_id, assignment_worker_id, category_admin_id, assignment_admin_id) се поврзани со worker_id и admin_id преку зависности на вклучување (надворешни клучеви), а не преку функционални зависности.

Покривањето е канонично: секоја лева страна е минимална, и ниту една зависност не може да се изведе од останатите.

Кандидат клучеви и примарен клуч

Атрибутите photo_id, log_id и comment_id не се појавуваат на десна страна во ниту една зависност, па мора да бидат во секој кандидат клуч. Исто така:

• admin_id и admin_email се определуваат само еден со друг (ЗФ1, ЗФ2), па секој клуч содржи еден од нив;
• worker_id и worker_email - исто (ЗФ3, ЗФ4);
• assignment_id се определува со report_id и assignment_worker_id (ЗФ14), а report_id веќе се добива од photo_id (ЗФ10), па секој клуч содржи assignment_id или assignment_worker_id.

Затворање на K = {photo_id, log_id, comment_id, assignment_id, admin_id, worker_id}:

• од photo_id (ЗФ10) → report_id, па од ЗФ9 → сите атрибути на пријавата, citizen_id и category_id, па од ЗФ5 и ЗФ7 → сите атрибути на граѓанинот и категоријата;
• од log_id, comment_id и assignment_id (ЗФ11-ЗФ13) → сите атрибути на статусите, коментарите и доделувањата;
• од admin_id и worker_id (ЗФ1, ЗФ3) → атрибутите на администраторот и работникот.

K+ ги содржи сите атрибути на R, а ниту еден вистински подмножество не ги содржи, па K е кандидат клуч.

Сите кандидат клучеви имаат облик {photo_id, log_id, comment_id, A, W, X}, каде A ∈ {admin_id, admin_email}, W ∈ {worker_id, worker_email}, X ∈ {assignment_id, assignment_worker_id}, што дава 8 кандидат клучеви.

Примарен клуч: {photo_id, log_id, comment_id, assignment_id, admin_id, worker_id}, бидејќи е составен само од вештачки нумерички идентификатори, кои се стабилни и кратки.

Нормална форма на R: Сите атрибути се атомични (повеќе фотографии, статуси или коментари на една пријава се претставуваат со повеќе редови), па R е во 1НФ. R не е во 2НФ, бидејќи постојат непримарни атрибути кои зависат од дел од клучот (на пример admin_id → admin_full_name).

Декомпозиција во 1НФ

R е веќе во 1НФ, па не е потребна декомпозиција.

Декомпозиција во 2НФ

Во секој чекор, парцијалната зависност X → Y (X е дел од примарниот клуч) се отстранува со декомпозиција на релацијата во R1 = X ∪ Y и R2 = R − Y. Декомпозицијата е без загуба бидејќи R1 ∩ R2 = X, а X е клуч во R1.

Чекор 2.1 - Администратори

• Релација: R, клуч K.
• Проблем: ЗФ1: admin_id → admin_full_name, admin_email, admin_password, каде admin_id е дел од клучот.
• Резултат: R1(admin_id, admin_full_name, admin_email, admin_password) и Ra = R − {admin_full_name, admin_email, admin_password}.
• Зависности и клучеви: во R1 важат ЗФ1 и ЗФ2, кандидат клучеви се admin_id и admin_email, примарен клуч admin_id. Во Ra важат сите останати зависности, а клучот е K.
• Зачувување на зависностите: ЗФ1 и ЗФ2 се во R1, останатите се во Ra - зачувани.
• Спојување без загуба: R1 ∩ Ra = {admin_id}, клуч во R1 - без загуба.

Чекор 2.2 - Работници

• Релација: Ra, клуч K.
• Проблем: ЗФ3: worker_id → worker_full_name, worker_email, worker_password.
• Резултат: R2(worker_id, worker_full_name, worker_email, worker_password) и Rb = Ra − {worker_full_name, worker_email, worker_password}.
• Зависности и клучеви: во R2 важат ЗФ3 и ЗФ4, кандидат клучеви worker_id и worker_email, примарен клуч worker_id. Rb го задржува клучот K.
• Зачувување на зависностите: зачувани.
• Спојување без загуба: R2 ∩ Rb = {worker_id}, клуч во R2 - без загуба.

Чекор 2.3 - Фотографии

• Релација: Rb, клуч K.
• Проблем: ЗФ10: photo_id → image_url, report_id. Атрибутот report_id се определува и со log_id, comment_id и assignment_id, па останува и во Rb, а се отстранува само image_url.
• Резултат: R3(photo_id, image_url, report_id) и Rc = Rb − {image_url}.
• Зависности и клучеви: во R3 важи ЗФ10, клуч photo_id. Rc го задржува клучот K.
• Зачувување на зависностите: ЗФ10 е во R3 - зачувана.
• Спојување без загуба: R3 ∩ Rc = {photo_id, report_id}, што содржи клуч на R3 - без загуба.

Чекор 2.4 - Историја на статуси

• Релација: Rc, клуч K.
• Проблем: ЗФ11: log_id → log_status, log_changed_at, log_note, log_worker_id, report_id.
• Резултат: R4(log_id, log_status, log_changed_at, log_note, log_worker_id, report_id) и Rd = Rc − {log_status, log_changed_at, log_note, log_worker_id}.
• Зависности и клучеви: во R4 важи ЗФ11, клуч log_id.
• Зачувување на зависностите: зачувани.
• Спојување без загуба: R4 ∩ Rd = {log_id, report_id}, содржи клуч на R4 - без загуба.

Чекор 2.5 - Коментари

• Релација: Rd, клуч K.
• Проблем: ЗФ12: comment_id → comment_content, comment_created_at, comment_worker_id, report_id.
• Резултат: R5(comment_id, comment_content, comment_created_at, comment_worker_id, report_id) и Re = Rd − {comment_content, comment_created_at, comment_worker_id}.
• Зависности и клучеви: во R5 важи ЗФ12, клуч comment_id.
• Зачувување на зависностите: зачувани.
• Спојување без загуба: R5 ∩ Re = {comment_id, report_id}, содржи клуч на R5 - без загуба.

Чекор 2.6 - Доделувања

• Релација: Re, клуч K.
• Проблем: ЗФ13: assignment_id → assignment_assigned_at, assignment_note, assignment_admin_id, assignment_worker_id, report_id.
• Резултат: R6(assignment_id, assignment_assigned_at, assignment_note, assignment_admin_id, assignment_worker_id, report_id) и Rf = Re − {assignment_assigned_at, assignment_note, assignment_admin_id, assignment_worker_id}.
• Зависности и клучеви: во R6 важат ЗФ13 и ЗФ14. Кандидат клучеви се assignment_id и {report_id, assignment_worker_id}, примарен клуч assignment_id. Во Rf клучот е K (assignment_worker_id повеќе не е во Rf, па assignment_id е единствената можност за тој дел од клучот).
• Зачувување на зависностите: ЗФ13 и ЗФ14 се во R6 - зачувани.
• Спојување без загуба: R6 ∩ Rf = {assignment_id, report_id}, содржи клуч на R6 - без загуба.

Чекор 2.7 - Пријави

• Релација: Rf(photo_id, log_id, comment_id, assignment_id, admin_id, worker_id, report_id, атрибутите на пријавата, граѓанинот и категоријата), клуч K.
• Проблем: photo_id → report_id и, преку ЗФ9, ЗФ5 и ЗФ7, photo_id → сите атрибути на пријавата, граѓанинот и категоријата. Тоа е парцијална зависност од клучот.
• Резултат: R7(photo_id, report_id, report_description, location_text, latitude, longitude, report_status, report_priority, report_created_at, citizen_id, citizen_full_name, citizen_email, citizen_phone, citizen_password, category_id, category_name, category_admin_id) и Rg(photo_id, log_id, comment_id, assignment_id, admin_id, worker_id).
• Зависности и клучеви: во R7 важат ЗФ5-ЗФ9 и photo_id → report_id, клуч photo_id. Rg нема нетривијални зависности, клучот се сите атрибути.
• Зачувување на зависностите: зависностите log_id → report_id, comment_id → report_id и assignment_id → report_id не се во Rg, но веќе се зачувани во R4, R5 и R6. Останатите се во R7 - зачувани.
• Спојување без загуба: R7 ∩ Rg = {photo_id}, клуч во R7 - без загуба.

Состојба по 2НФ

Сите релации се во 2НФ: R1-R5 и R7 имаат прост примарен клуч; во R6 непримарните атрибути зависат целосно од секој кандидат клуч; Rg нема непримарни атрибути.

Декомпозиција во 3НФ

Релациите R1-R6 и Rg се веќе во 3НФ: во нив секоја нетривијална зависност X → A има X кој е суперклуч (admin_email, worker_email, {report_id, assignment_worker_id} се кандидат клучеви). Единствено R7 содржи транзитивни зависности.

Чекор 3.1 - Издвојување на пријавата

• Релација: R7, клуч photo_id, релацијата е во 2НФ.
• Проблем: транзитивна зависност photo_id → report_id → report_description, ..., citizen_id, category_id (ЗФ9), каде report_id не е суперклуч во R7.
• Резултат: R8(report_id, report_description, location_text, latitude, longitude, report_status, report_priority, report_created_at, citizen_id, citizen_full_name, citizen_email, citizen_phone, citizen_password, category_id, category_name, category_admin_id) и R7a(photo_id, report_id).
• Зависности и клучеви: во R8 важат ЗФ5-ЗФ9, клуч report_id. Во R7a важи photo_id → report_id, клуч photo_id.
• Зачувување на зависностите: зачувани.
• Спојување без загуба: R8 ∩ R7a = {report_id}, клуч во R8 - без загуба.
• R7a е проекција на R3 со ист клуч (photo_id), па е вишок и се спојува со R3.

Чекор 3.2 - Издвојување на граѓанинот

• Релација: R8, клуч report_id.
• Проблем: транзитивна зависност report_id → citizen_id → citizen_full_name, citizen_email, citizen_phone, citizen_password (ЗФ5).
• Резултат: R9(citizen_id, citizen_full_name, citizen_email, citizen_phone, citizen_password) и R8a = R8 − {citizen_full_name, citizen_email, citizen_phone, citizen_password}.
• Зависности и клучеви: во R9 важат ЗФ5 и ЗФ6, кандидат клучеви citizen_id и citizen_email, примарен клуч citizen_id. Во R8a важат ЗФ7, ЗФ8 и ЗФ9, клуч report_id.
• Зачувување на зависностите: зачувани.
• Спојување без загуба: R9 ∩ R8a = {citizen_id}, клуч во R9 - без загуба.

Чекор 3.3 - Издвојување на категоријата

• Релација: R8a, клуч report_id.
• Проблем: транзитивна зависност report_id → category_id → category_name, category_admin_id (ЗФ7).
• Резултат: R10(category_id, category_name, category_admin_id) и R11(report_id, report_description, location_text, latitude, longitude, report_status, report_priority, report_created_at, citizen_id, category_id).
• Зависности и клучеви: во R10 важат ЗФ7 и ЗФ8, кандидат клучеви category_id и category_name, примарен клуч category_id. Во R11 важи ЗФ9, клуч report_id.
• Зачувување на зависностите: зачувани.
• Спојување без загуба: R10 ∩ R11 = {category_id}, клуч во R10 - без загуба.

BCNF

Сите добиени релации се во BCNF, бидејќи во секоја од нив левата страна на секоја нетривијална функционална зависност е суперклуч:

• R1: admin_id и admin_email се кандидат клучеви.
• R2: worker_id и worker_email се кандидат клучеви.
• R9: citizen_id и citizen_email се кандидат клучеви.
• R10: category_id и category_name се кандидат клучеви.
• R3, R4, R5, R11: единствената лева страна е примарниот клуч.
• R6: assignment_id и {report_id, assignment_worker_id} се кандидат клучеви.
• Rg: нема нетривијални функционални зависности.

Сите функционални зависности од почетното канонично покривање се зачувани (секоја е во барем една релација), а секој чекор е без загуба при спојување.

Конечен резултат и дискусија

Нормализиран релационен модел

Релациите се преименувани според значењето, а атрибутите со улоги се преименувани во имиња на надворешни клучеви:

admins      (admin_id, full_name, email, password)                          ← R1
workers     (worker_id, full_name, email, password)                         ← R2
citizens    (citizen_id, full_name, email, phone, password)                 ← R9
categories  (category_id, name, admin_id*)                                  ← R10
reports     (report_id, description, location_text, latitude, longitude,
             status, priority, created_at, citizen_id*, category_id*)       ← R11
photos      (photo_id, image_url, report_id*)                               ← R3 (+R7a)
status_logs (log_id, status, changed_at, note, report_id*, worker_id*)      ← R4
comments    (comment_id, content, created_at, report_id*, worker_id*)       ← R5
assignments (assignment_id, assigned_at, note,
             admin_id*, report_id*, worker_id*)                             ← R6

Примарните клучеви се првиот атрибут во секоја релација, а со * се означени надворешните клучеви. Алтернативни клучеви: email во admins, workers и citizens; name во categories; {report_id, worker_id} во assignments.

Дискусија

Нормализацијата резултира со истите девет релации како и релациониот дизајн од фазата P2, со истите примарни клучеви, надворешни клучеви и единствени ограничувања. Со ова се потврдува дека дизајнот од P2 е во BCNF и дека не содржи редундантност предизвикана од функционални зависности. Затоа објектите во базата и документацијата од фазата P2 не се менуваат, и дизајнот од P2 се користи во следните фази.

Преостанатата релација Rg(photo_id, log_id, comment_id, assignment_id, admin_id, worker_id) се состои само од клучот на почетната релација. Таа е потребна формално за спојувањето без загуба да ја врати целата униврзална релација, но не претставува ниту еден реален факт: секој нејзин ред е само комбинација на фотографија, статус, коментар и доделување на иста пријава, и произволен администратор и работник. Таа комбинација се добива со спојување на другите релации (повеќевредносни зависности, 4НФ), па Rg не се имплементира како табела.

Атрибутот status во reports не е функционално зависен од другите атрибути на пријавата, но неговата вредност секогаш е еднаква на последниот статус во status_logs за таа пријава. Оваа редундантност не произлегува од функционална зависност, па нормализацијата не ја отстранува. Таа е намерно задржана, бидејќи овозможува брзо филтрирање на пријавите по статус без пребарување на целата историја.

Атрибутите со улоги (log_worker_id, comment_worker_id, assignment_worker_id, category_admin_id, assignment_admin_id) во конечниот модел стануваат надворешни клучеви worker_id и admin_id кон табелите workers и admins, што одговара на зависностите на вклучување од почетниот модел.