wiki:Normalization

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

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

Постапката започнува од една единствена денормализирана релација R која ги содржи сите атрибути од ЕР моделот, како целата база да е сместена во една табела.

Бидејќи во моделот повеќе ентитети имаат атрибут со исто име (id, name, type, created_at), атрибутите се преименувани така што во R нема две исти имиња:

Изворно име Добива име во R
id user_id, high_school_id, contact_id, major_id, semester_id, subject_id, enrolled_id, sem_subject_id, passed_id, document_id, token_id, payment_id
name user_name, major_name, subject_name
type hs_type, semester_type, document_type
created_at user_created_at, enrolled_created_at
number phone_number
index index_no
body document_body
cost document_cost
token token_value
quota quota (на корисник) и enrolled_quota (на запишан семестар)
professor professor_id (професор на конкретен запишан предмет) и teaching_prof_id (професор во распоредот по семестар)
dependency_id prerequisite_id (предметот кој е предуслов)

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

R = { user_id, user_name, embg, surname, index_no, bday, email, password, role, quota, enrollment_year, user_created_at, high_school_id, gpa, hs_type, contact_id, city, municipality, address, phone_number, microsoft_email, major_id, major_name, semester_id, year, semester_type, subject_id, subject_name, subject_code, awarded_credits, dependency_credit, enrolled_id, enrolled_quota, note, student_comment, enrolled_created_at, last_change, completed, sem_subject_id, professor_id, signature, passed_id, grade, date_passed, document_id, document_type, document_body, document_cost, token_id, token_value, expires_at, is_valid, payment_id, amount, mandatory_semester, prerequisite_id, teaching_prof_id }

Вкупно |R| = 57 атрибути.

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

Даден е каноничкиот покривач на множеството функционални зависности кои важат во R:

  • FD1: user_id → user_name, embg, surname, index_no, bday, email, password, role, quota, enrollment_year, user_created_at
  • FD2: email → user_id
  • FD3: user_id → high_school_id
  • FD4: high_school_id → user_id, gpa, hs_type
  • FD5: user_id → contact_id
  • FD6: contact_id → user_id, city, municipality, address, phone_number, microsoft_email
  • FD7: major_id → major_name
  • FD8: semester_id → year, semester_type
  • FD9: (year, semester_type) → semester_id
  • FD10: subject_id → subject_name, subject_code, awarded_credits, dependency_credit
  • FD11: subject_name → subject_id
  • FD12: subject_code → subject_id
  • FD13: enrolled_id → user_id, enrolled_quota, major_id, note, student_comment, enrolled_created_at, last_change, completed, semester_id
  • FD14: (user_id, semester_id) → enrolled_id
  • FD15: sem_subject_id → enrolled_id, subject_id, professor_id, signature
  • FD16: (enrolled_id, subject_id) → sem_subject_id
  • FD17: passed_id → sem_subject_id, grade, date_passed
  • FD18: sem_subject_id → passed_id, grade, date_passed
  • FD19: document_id → document_type, document_body, document_cost
  • FD20: token_id → user_id, token_value, expires_at, is_valid
  • FD21: payment_id → user_id, enrolled_id, amount
  • FD22: (major_id, subject_id) → mandatory_semester

Следните комбинации не определуваат ниту еден атрибут, односно претставуваат чисти врски (сите атрибути се дел од клучот):

  • FD23: (user_id, document_id) → ∅
  • FD24: (subject_id, prerequisite_id) → ∅
  • FD25: (teaching_prof_id, semester_id, subject_id) → ∅

Зависностите FD2, FD9, FD11, FD12, FD14, FD16 и FD17 произлегуваат од UNIQUE ограничувањата, а FD4 и FD6 од тоа што врските се 1:1.

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

Атрибути кои се појавуваат само лево (мора да бидат дел од секој кандидат клуч):

document_id, token_id, payment_id, prerequisite_id, teaching_prof_id

Атрибути кои се појавуваат само десно (не можат да бидат дел од кандидат клуч), 38 атрибути:

address, amount, awarded_credits, bday, city, completed, date_passed, dependency_credit, document_body, document_cost, document_type, embg, enrolled_created_at, enrolled_quota, enrollment_year, expires_at, gpa, grade, hs_type, index_no, is_valid, last_change, major_name, mandatory_semester, microsoft_email, municipality, note, password, phone_number, professor_id, quota, role, signature, student_comment, surname, token_value, user_created_at, user_name

Атрибути кои се појавуваат и лево и десно (кандидати за дополнување на клучот), 14 атрибути:

contact_id, email, enrolled_id, high_school_id, major_id, passed_id, sem_subject_id, semester_id, semester_type, subject_code, subject_id, subject_name, user_id, year

Покривач на јадрото

Нека K = { document_id, token_id, payment_id, prerequisite_id, teaching_prof_id }.

K+ содржи 45 од вкупно 57 атрибути. Не се добиваат:

awarded_credits, date_passed, dependency_credit, grade, mandatory_semester, passed_id, professor_id, sem_subject_id, signature, subject_code, subject_id, subject_name

Значи K сам по себе не е суперклуч. Причината е што ниту еден од атрибутите во K не води до предметот: до sem_subject_id се стигнува само преку (enrolled_id, subject_id) со FD16 или преку passed_id со FD17, а subject_id не се добива од ниту една зависност чија лева страна е во K+.

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

Со додавање на еден атрибут од двостраните на K се добиваат следните минимални суперклучеви, односно кандидат клучеви:

  • CK1 = K ∪ { subject_id }
  • CK2 = K ∪ { sem_subject_id }
  • CK3 = K ∪ { passed_id }
  • CK4 = K ∪ { subject_code }
  • CK5 = K ∪ { subject_name }

CK4 и CK5 постојат затоа што subject_code и subject_name се UNIQUE, па се алтернативни идентификатори на предметот. CK2 и CK3 постојат затоа што sem_subject_id и passed_id се во однос 1:1 и секој од нив води до subject_id.

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

За секое CKi се пресметува затворачот CKi+ и се проверува дали CKi+ = R, односно дали ги покрива сите 57 атрибути. Се користи стандардниот алгоритам: се тргнува од самото множество и се применува FD чија лева страна е веќе содржана, сè додека има промена.

Заедничкиот дел за сите пет клучеви е K+, кој беше пресметан погоре и содржи 45 атрибути. Затоа за секој CKi се прикажува само што се додава над K+, односно дали се добиваат сите 12 атрибути кои недостасуваат во K+.

CK1+ = (K ∪ { subject_id })+

  1. Почетно: K ∪ { subject_id }
  2. Сите чекори од пресметката на K+ важат и тука ⇒ вкупно 45 атрибути + subject_id = 46
  3. FD10: subject_id → subject_name, subject_code, awarded_credits, dependency_credit ⇒ вкупно 50
  4. FD16: (enrolled_id, subject_id) → sem_subject_id (enrolled_id е добиен преку FD21) ⇒ вкупно 51
  5. FD15: sem_subject_id → professor_id, signature ⇒ вкупно 53
  6. FD18: sem_subject_id → passed_id, grade, date_passed ⇒ вкупно 56
  7. FD22: (major_id, subject_id) → mandatory_semester (major_id е добиен преку FD13) ⇒ вкупно 57

CK1+ = R (57/57) ⇒ CK1 е суперклуч.

CK2+ = (K ∪ { sem_subject_id })+

  1. Почетно: K ∪ { sem_subject_id }, плус чекорите на K+ ⇒ вкупно 46
  2. FD15: sem_subject_id → enrolled_id, subject_id, professor_id, signature ⇒ вкупно 48 (enrolled_id веќе е во K+)
  3. FD10: subject_id → subject_name, subject_code, awarded_credits, dependency_credit ⇒ вкупно 52
  4. FD18: sem_subject_id → passed_id, grade, date_passed ⇒ вкупно 55
  5. FD22: (major_id, subject_id) → mandatory_semester ⇒ вкупно 56
  6. Останува уште sem_subject_id самиот, кој е во почетното множество ⇒ вкупно 57

CK2+ = R (57/57) ⇒ CK2 е суперклуч.

CK3+ = (K ∪ { passed_id })+

  1. Почетно: K ∪ { passed_id }, плус чекорите на K+ ⇒ вкупно 46
  2. FD17: passed_id → sem_subject_id, grade, date_passed ⇒ вкупно 49
  3. FD15: sem_subject_id → enrolled_id, subject_id, professor_id, signature ⇒ вкупно 52
  4. FD10: subject_id → subject_name, subject_code, awarded_credits, dependency_credit ⇒ вкупно 56
  5. FD22: (major_id, subject_id) → mandatory_semester ⇒ вкупно 57

CK3+ = R (57/57) ⇒ CK3 е суперклуч.

CK4+ = (K ∪ { subject_code })+

  1. Почетно: K ∪ { subject_code }, плус чекорите на K+ ⇒ вкупно 46
  2. FD12: subject_code → subject_id ⇒ вкупно 47
  3. Од чекор 3 натаму пресметката е идентична со CK1 ⇒ вкупно 57

CK4+ = R (57/57) ⇒ CK4 е суперклуч.

CK5+ = (K ∪ { subject_name })+

  1. Почетно: K ∪ { subject_name }, плус чекорите на K+ ⇒ вкупно 46
  2. FD11: subject_name → subject_id ⇒ вкупно 47
  3. Од чекор 3 натаму пресметката е идентична со CK1 ⇒ вкупно 57

CK5+ = R (57/57) ⇒ CK5 е суперклуч.

Проверка на минималноста

Суперклучот е кандидат клуч само ако ниту едно негово вистинско подмножество не е суперклуч. За секој CKi = K ∪ { X } се проверуваат двата случаја:

  • Отстранување на X: останува K, а веќе е покажано дека K+ има 45 < 57 атрибути. Значи K не е суперклуч и X е неопходен.
  • Отстранување на било кој атрибут од K: петте атрибути document_id, token_id, payment_id, prerequisite_id и teaching_prof_id се појавуваат само на лева страна во сите FD1-FD25. Атрибут кој никогаш не стои десно не може да се изведе од ниту една зависност, па мора да припаѓа на секој суперклуч. Значи ниту еден од нив не смее да се отстрани.

Според тоа сите пет множества се минимални суперклучеви, односно кандидат клучеви.

Проверка дека нема други кандидат клучеви

Секој кандидат клуч мора да го содржи K (петте само-лево атрибути) и не смее да содржи ниту еден од 38-те само-десно атрибути. Останува да се провери само кои од 14-те двострани атрибути можат да го дополнат K.

Девет од нив веќе се содржани во K+: contact_id, email, enrolled_id, high_school_id, major_id, semester_id, semester_type, user_id, year. Ако атрибутот A е во K+, тогаш (K ∪ {A})+ = K+, што има 45 атрибути, па таквото множество не е суперклуч.

Преостануваат точно петте кои не се во K+ и водат до предметот: subject_id, sem_subject_id, passed_id, subject_code, subject_name - тоа се CK1-CK5. Секое множество со два или повеќе додадени атрибути го содржи некој од нив, па не е минимално.

Заклучок: релацијата R има точно 5 кандидат клучеви, сите со големина 6.

Избран примарен клуч:

PK = { document_id, token_id, payment_id, prerequisite_id, teaching_prof_id, subject_id }

Избран е CK1 бидејќи subject_id е природниот идентификатор на предметот, додека sem_subject_id и passed_id се идентификатори на врски кои постојат само ако студентот го запишал, односно положил предметот.

Проверка во која нормална форма е R

Релацијата R ја задоволува 1НФ: сите атрибути се атомични, нема повеќевредносни атрибути ниту повторувачки групи, и секоја редица е определена со PK.

R не ја задоволува 2НФ, бидејќи постојат парцијални зависности - атрибути кои зависат од дел од примарниот клуч, а не од целиот. На пример document_id → document_type, каде document_id е само еден дел од PK.

Критериум за спојување без загуба

Секоја декомпозиција подолу дели една релација Ri на точно две релации, A и B. За секоја од нив експлицитно се наведува:

  1. по кои атрибути се спојуваат, односно пресекот A ∩ B;
  2. на која од двете релации тој пресек е (супер)клуч.

Користен е критериумот на Хит (Heath): декомпозицијата на Ri на A и B е без загуба ако и само ако важи

(A ∩ B) → A или (A ∩ B) → B

односно ако заедничките атрибути се суперклуч на барем едната од двете релации. Тогаш A ⋈ B = Ri, при што спојувањето е природно спојување по целиот пресек A ∩ B, а не по произволен атрибут.

Кај 4НФ функционалната зависност не е доволна, па таму се користи проширениот критериум: декомпозицијата е без загуба ако важи повеќевредносната зависност (A ∩ B) ↠ A, односно (A ∩ B) ↠ B.

Во целата постапка секој чекор ја дели тековната релација Ri на новоиздвоената релација и остатокот Ri+1, па конечната шема се реконструира со редоследно спојување наназад:

R = R1 ⋈ Documents = R2 ⋈ Token ⋈ Documents = … = R13 ⋈ (сите издвоени релации)

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

Не е потребна декомпозиција. R е веќе во 1НФ: секој атрибут има атомична вредност од единствен домен, нема повторувачки групи и секоја редица е уникатно определена со примарниот клуч.

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

Анализирана релација: R, PK = { document_id, token_id, payment_id, prerequisite_id, teaching_prof_id, subject_id }

Парцијални зависности (лева страна е вистински подмножество на PK):

  • FD19: document_id → document_type, document_body, document_cost
  • FD20: token_id → token_value, expires_at, is_valid
  • FD21: payment_id → amount
  • FD10: subject_id → subject_name, subject_code, awarded_credits, dependency_credit

Секоја од нив се издвојува во посебна релација. Атрибутите кои се клучеви или се потребни за поврзување остануваат и во преостанатата релација.

Декомпозиција по FD19

Documents(document_id, document_type, document_body, document_cost)

R1 = R − { document_type, document_body, document_cost }

  • Клуч: document_id
  • Lossless join: R = Documents ⋈ R1, спојување по Documents ∩ R1 = { document_id }. Тој пресек е клуч на Documents (FD19: document_id → сите останати атрибути на Documents), па важи (A ∩ B) → A и декомпозицијата е без загуба.
  • Dependency preservation: FD19 е сочувана во Documents.

Декомпозиција по FD20

Token(token_id, user_id, token_value, expires_at, is_valid)

R2 = R1 − { token_value, expires_at, is_valid }

  • Клуч: token_id
  • Lossless join: R1 = Token ⋈ R2, спојување по Token ∩ R2 = { token_id, user_id } (и двата атрибути остануваат во R2). Тој пресек е суперклуч на Token, бидејќи веќе token_id сам по FD20 ги определува сите атрибути на Token. Значи (A ∩ B) → A, па спојувањето е без загуба.
  • Dependency preservation: FD20 е сочувана во Token.

Декомпозиција по FD21

Payment(payment_id, enrolled_id, amount)

R3 = R2 − { amount }

  • Клуч: payment_id
  • Lossless join: R2 = Payment ⋈ R3, спојување по Payment ∩ R3 = { payment_id, enrolled_id }. Тој пресек е суперклуч на Payment, бидејќи payment_id → enrolled_id, amount (FD21). Значи (A ∩ B) → A, па спојувањето е без загуба.
  • Dependency preservation: FD21 е сочувана во Payment.
  • Забелешка: атрибутот user_id намерно не е дел од Payment. Види ја дискусијата за БКНФ подолу.

Декомпозиција по FD10

Subjects(subject_id, subject_name, subject_code, awarded_credits, dependency_credit)

R4 = R3 − { subject_name, subject_code, awarded_credits, dependency_credit }

  • Клучеви: subject_id (примарен), subject_name, subject_code (алтернативни, поради FD11 и FD12)
  • Lossless join: R3 = Subjects ⋈ R4, спојување по Subjects ∩ R4 = { subject_id }. Тој пресек е клуч на Subjects (FD10), па важи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD10, FD11 и FD12 се сочувани во Subjects.

Резултат по 2НФ:

R4 = { user_id, user_name, embg, surname, index_no, bday, email, password, role, quota, enrollment_year, user_created_at, high_school_id, gpa, hs_type, contact_id, city, municipality, address, phone_number, microsoft_email, major_id, major_name, semester_id, year, semester_type, subject_id, enrolled_id, enrolled_quota, note, student_comment, enrolled_created_at, last_change, completed, sem_subject_id, professor_id, signature, passed_id, grade, date_passed, document_id, token_id, payment_id, mandatory_semester, prerequisite_id, teaching_prof_id }

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

R4 не ја задоволува 3НФ поради транзитивни зависности: token_id → user_id → user_name, payment_id → enrolled_id → major_id → major_name, и слично.

Декомпозиција по FD1

Users(user_id, user_name, embg, surname, index_no, bday, email, password, role, quota, enrollment_year, user_created_at)

R5 = R4 − { user_name, embg, surname, index_no, bday, email, password, role, quota, enrollment_year, user_created_at }

  • Клучеви: user_id (примарен), email (алтернативен, поради FD2)
  • Транзитивна зависност: token_id → user_id → останатите атрибути на корисникот
  • Lossless join: R4 = Users ⋈ R5, спојување по Users ∩ R5 = { user_id } (email се отстранува од R5, па не е дел од пресекот). Тој пресек е клуч на Users (FD1), па важи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD1 и FD2 се сочувани во Users.

Декомпозиција по FD4

HighSchool(high_school_id, user_id, gpa, hs_type)

R6 = R5 − { gpa, hs_type }

  • Клучеви: high_school_id (примарен), user_id (алтернативен, поради FD3 - врската е 1:1)
  • Lossless join: R5 = HighSchool ⋈ R6, спојување по HighSchool ∩ R6 = { high_school_id, user_id }. Тој пресек е суперклуч на HighSchool - секој од двата атрибути посебно е клуч (FD4, односно FD3 бидејќи врската е 1:1). Значи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD3 и FD4 се сочувани во HighSchool.

Декомпозиција по FD6

Contact(contact_id, user_id, city, municipality, address, phone_number, microsoft_email)

R7 = R6 − { city, municipality, address, phone_number, microsoft_email }

  • Клучеви: contact_id (примарен), user_id (алтернативен, поради FD5)
  • Lossless join: R6 = Contact ⋈ R7, спојување по Contact ∩ R7 = { contact_id, user_id }. Тој пресек е суперклуч на Contact - contact_id е клуч по FD6, а user_id по FD5, бидејќи врската е 1:1. Значи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD5 и FD6 се сочувани во Contact.

Декомпозиција по FD13

EnrolledSemesters(enrolled_id, user_id, enrolled_quota, major_id, note, student_comment, enrolled_created_at, last_change, completed, semester_id)

R8 = R7 − { enrolled_quota, note, student_comment, enrolled_created_at, last_change, completed }

  • Клучеви: enrolled_id (примарен), (user_id, semester_id) (алтернативен, поради FD14)
  • Транзитивна зависност: payment_id → enrolled_id → атрибутите на запишувањето
  • Lossless join: R7 = EnrolledSemesters ⋈ R8, спојување по EnrolledSemesters ∩ R8 = { enrolled_id, user_id, major_id, semester_id }. Тој пресек е суперклуч на EnrolledSemesters, бидејќи веќе enrolled_id сам по FD13 ги определува сите нејзини атрибути. Значи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD13 и FD14 се сочувани во EnrolledSemesters.

Декомпозиција по FD7

Major(major_id, major_name)

R9 = R8 − { major_name }

  • Клуч: major_id
  • Транзитивна зависност: enrolled_id → major_id → major_name
  • Lossless join: R8 = Major ⋈ R9, спојување по Major ∩ R9 = { major_id }. Тој пресек е клуч на Major (FD7), па важи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD7 е сочувана во Major.

Декомпозиција по FD8

ActiveSemesters(semester_id, year, semester_type)

R10 = R9 − { year, semester_type }

  • Клучеви: semester_id (примарен), (year, semester_type) (алтернативен, поради FD9)
  • Транзитивна зависност: enrolled_id → semester_id → year, semester_type
  • Lossless join: R9 = ActiveSemesters ⋈ R10, спојување по ActiveSemesters ∩ R10 = { semester_id } (year и semester_type се отстрануваат од R10). Тој пресек е клуч на ActiveSemesters (FD8), па важи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD8 и FD9 се сочувани во ActiveSemesters.

Декомпозиција по FD15

SemestersSubjects(sem_subject_id, enrolled_id, subject_id, professor_id, signature)

R11 = R10 − { professor_id, signature }

  • Клучеви: sem_subject_id (примарен), (enrolled_id, subject_id) (алтернативен, поради FD16)
  • Lossless join: R10 = SemestersSubjects ⋈ R11, спојување по SemestersSubjects ∩ R11 = { sem_subject_id, enrolled_id, subject_id }. Тој пресек е суперклуч на SemestersSubjects, бидејќи веќе sem_subject_id сам по FD15 ги определува professor_id и signature. Значи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD15 и FD16 се сочувани во SemestersSubjects.

Декомпозиција по FD17

PassedSubjects(passed_id, sem_subject_id, grade, date_passed)

R12 = R11 − { grade, date_passed }

  • Клучеви: passed_id (примарен), sem_subject_id (алтернативен, поради FD18 - врската е 1:1)
  • Lossless join: R11 = PassedSubjects ⋈ R12, спојување по PassedSubjects ∩ R12 = { passed_id, sem_subject_id }. Тој пресек е суперклуч на PassedSubjects - passed_id е клуч по FD17, а sem_subject_id по FD18, бидејќи врската е 1:1. Значи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD17 и FD18 се сочувани во PassedSubjects.

Декомпозиција по FD22

MajorSubjects(major_id, subject_id, mandatory_semester)

R13 = R12 − { mandatory_semester }

  • Клуч: (major_id, subject_id)
  • Зависноста FD22 има сложена лева страна која не е клуч на R12, што ја нарушува 3НФ.
  • Lossless join: R12 = MajorSubjects ⋈ R13, спојување по MajorSubjects ∩ R13 = { major_id, subject_id }. Тој пресек е клуч на MajorSubjects (FD22), па важи (A ∩ B) → A и спојувањето е без загуба.
  • Dependency preservation: FD22 е сочувана во MajorSubjects.

Резултат по 3НФ:

R13 = { user_id, high_school_id, contact_id, major_id, semester_id, subject_id, enrolled_id, sem_subject_id, passed_id, document_id, token_id, payment_id, prerequisite_id, teaching_prof_id }

Во R13 остануваат само идентификатори. Сите зависности со неклучна десна страна се веќе издвоени.

БКНФ

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

  • Users - детерминанти user_id и email, обата се кандидат клучеви ⇒ БКНФ
  • HighSchool - детерминанти high_school_id и user_id, обата се кандидат клучеви ⇒ БКНФ
  • Contact - детерминанти contact_id и user_id, обата се кандидат клучеви ⇒ БКНФ
  • Major - детерминанта major_id ⇒ БКНФ
  • ActiveSemesters - детерминанти semester_id и (year, semester_type) ⇒ БКНФ
  • Subjects - детерминанти subject_id, subject_name, subject_code, сите кандидат клучеви ⇒ БКНФ
  • EnrolledSemesters - детерминанти enrolled_id и (user_id, semester_id) ⇒ БКНФ
  • SemestersSubjects - детерминанти sem_subject_id и (enrolled_id, subject_id) ⇒ БКНФ
  • PassedSubjects - детерминанти passed_id и sem_subject_id ⇒ БКНФ
  • Documents - детерминанта document_id ⇒ БКНФ
  • Token - детерминанта token_id ⇒ БКНФ
  • Payment - детерминанта payment_id ⇒ БКНФ
  • MajorSubjects - детерминанта (major_id, subject_id) ⇒ БКНФ

Пронајдено нарушување на БКНФ

Ако релацијата Payment се дефинира како во Фаза 2:

Payment(payment_id, user_id, enrolled_id, amount)

тогаш во неа важи и зависноста enrolled_id → user_id (изведена од FD13), а enrolled_id не е клуч на Payment. Ова е нарушување на БКНФ и значи дека атрибутот user_id во Payment е редундантен: студентот е веќе определен преку запишувањето кое се плаќа.

Практичната последица е можност за противречни податоци - ред во Payment може да тврди дека плаќањето е на еден студент, додека запишувањето на кое се однесува припаѓа на друг студент. Базата тоа не го спречува.

Декомпозиција по enrolled_id → user_id:

Payment(payment_id, enrolled_id, amount)

user_id се добива со спојување преку EnrolledSemesters.

  • Lossless join: оригиналната Payment(payment_id, user_id, enrolled_id, amount) се дели на Payment(payment_id, enrolled_id, amount) и EnrolledSemesters(enrolled_id, user_id, …). Спојувањето е по Payment ∩ EnrolledSemesters = { enrolled_id }. Тој пресек е клуч на EnrolledSemesters (FD13), па важи (A ∩ B) → B и спојувањето е без загуба. Атрибутот user_id се враќа со Payment ⋈ EnrolledSemesters по enrolled_id.
  • Dependency preservation: FD21 останува сочувана, бидејќи payment_id → enrolled_id, amount е во Payment, а payment_id → user_id се изведува транзитивно преку FD13.

По оваа измена сите релации се во БКНФ.

4НФ

Преостанатата релација R13 содржи само идентификатори и во неа постојат повеќевредносни зависности кои се меѓусебно независни. На пример, документите кои ги побарал еден корисник се независни од предусловите меѓу предметите и од распоредот на професорите.

Повеќевредносните зависности кои важат во R13 се:

  • MVD1: user_id ↠ document_id
  • MVD2: subject_id ↠ prerequisite_id
  • MVD3: (semester_id, subject_id) ↠ teaching_prof_id

Ниту една од трите лева страна не е суперклуч на R13, па R13 не е во 4НФ.

Декомпозиција по 4НФ:

Чекор 1 - издвојување по MVD1

UserDocuments(user_id, document_id) - од FD23

R13a = R13 − { document_id }

  • Lossless join: R13 = UserDocuments ⋈ R13a, спојување по UserDocuments ∩ R13a = { user_id }. Пресекот не е клуч на ниту една од двете, но важи MVD1: user_id ↠ document_id, односно множеството документи што ги побарал еден корисник не зависи од ниту еден друг атрибут во R13a. Според критериумот за 4НФ (A ∩ B) ↠ A, па спојувањето е без загуба.

Чекор 2 - издвојување по MVD2

DependencySubject(subject_id, prerequisite_id) - од FD24

R13b = R13a − { prerequisite_id }

  • Lossless join: R13a = DependencySubject ⋈ R13b, спојување по DependencySubject ∩ R13b = { subject_id }. Важи MVD2: subject_id ↠ prerequisite_id, бидејќи предусловите на еден предмет се исти без оглед на тоа кој студент го запишал. Значи (A ∩ B) ↠ A и спојувањето е без загуба.

Чекор 3 - издвојување по MVD3

ProfessourSubjects(teaching_prof_id, semester_id, subject_id) - од FD25

R13c = R13b − { teaching_prof_id }

  • Lossless join: R13b = ProfessourSubjects ⋈ R13c, спојување по ProfessourSubjects ∩ R13c = { semester_id, subject_id }. Важи MVD3: (semester_id, subject_id) ↠ teaching_prof_id, бидејќи распоредот кој професор предава кој предмет во кој семестар е независен од конкретното запишување. Значи (A ∩ B) ↠ A и спојувањето е без загуба.

Преостанатата релација

R13c = { user_id, high_school_id, contact_id, major_id, semester_id, subject_id, enrolled_id, sem_subject_id, passed_id, token_id, payment_id }

R13c не се задржува како посебна релација, бидејќи не носи нова информација. Секој нејзин атрибут е функционално определен од друг атрибут кој веќе постои во некоја од издвоените релации:

  • token_id → user_id (FD20), веќе во Token
  • payment_id → enrolled_id (FD21), веќе во Payment
  • enrolled_id → user_id, major_id, semester_id (FD13), веќе во EnrolledSemesters
  • sem_subject_id → enrolled_id, subject_id (FD15), веќе во SemestersSubjects
  • passed_id → sem_subject_id (FD17), веќе во PassedSubjects
  • user_id → high_school_id, contact_id (FD3, FD5), веќе во HighSchool и Contact

Значи R13c = π(Token ⋈ Payment ⋈ EnrolledSemesters ⋈ SemestersSubjects ⋈ PassedSubjects ⋈ HighSchool ⋈ Contact), при што секое спојување е по атрибут кој е клуч на едната страна. Затоа нејзиното отстранување е без загуба на информација.

  • Dependency preservation: трите нови релации не носат функционални зависности, туку само врски, па ниту една FD не се губи со оваа декомпозиција.

Финален резултат и дискусија

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

  1. Users(user_id, user_name, embg, surname, index_no, bday, email, password, role, quota, enrollment_year, user_created_at)
  2. HighSchool(high_school_id, user_id, gpa, hs_type)
  3. Contact(contact_id, user_id, city, municipality, address, phone_number, microsoft_email)
  4. Major(major_id, major_name)
  5. ActiveSemesters(semester_id, year, semester_type)
  6. Subjects(subject_id, subject_name, subject_code, awarded_credits, dependency_credit)
  7. EnrolledSemesters(enrolled_id, user_id, enrolled_quota, major_id, note, student_comment, enrolled_created_at, last_change, completed, semester_id)
  8. SemestersSubjects(sem_subject_id, enrolled_id, subject_id, professor_id, signature)
  9. PassedSubjects(passed_id, sem_subject_id, grade, date_passed)
  10. Documents(document_id, document_type, document_body, document_cost)
  11. UserDocuments(user_id, document_id)
  12. Token(token_id, user_id, token_value, expires_at, is_valid)
  13. Payment(payment_id, enrolled_id, amount)
  14. MajorSubjects(major_id, subject_id, mandatory_semester)
  15. DependencySubject(subject_id, prerequisite_id)
  16. ProfessourSubjects(teaching_prof_id, semester_id, subject_id)

Сите 16 релации се во БКНФ, декомпозицијата ги сочувува сите функционални зависности и е без загуба при спојување.

Преглед на спојувањата

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

Релација A Релација B Спојување по (A ∩ B) Клуч на Основа
Documents R1 document_id Documents FD19
Token R2 token_id, user_id Token FD20
Payment R3 payment_id, enrolled_id Payment FD21
Subjects R4 subject_id Subjects FD10
Users R5 user_id Users FD1
HighSchool R6 high_school_id, user_id HighSchool FD3, FD4
Contact R7 contact_id, user_id Contact FD5, FD6
EnrolledSemesters R8 enrolled_id, user_id, major_id, semester_id EnrolledSemesters FD13
Major R9 major_id Major FD7
ActiveSemesters R10 semester_id ActiveSemesters FD8
SemestersSubjects R11 sem_subject_id, enrolled_id, subject_id SemestersSubjects FD15
PassedSubjects R12 passed_id, sem_subject_id PassedSubjects FD17, FD18
MajorSubjects R13 major_id, subject_id MajorSubjects FD22
UserDocuments R13a user_id (MVD) MVD1
DependencySubject R13b subject_id (MVD) MVD2
ProfessourSubjects R13c semester_id, subject_id (MVD) MVD3

Кај првите тринаесет редови важи функционалната зависност (A ∩ B) → A, а кај последните три повеќевредносната (A ∩ B) ↠ A, што е условот за 4НФ.

Дискусија

Постапката на нормализација, спроведена независно од дизајнот на Фаза 2, даде практично ист резултат - истите 16 релации, со исти клучеви. Тоа значи дека ЕР моделот од Фаза 1 и релацискиот дизајн од Фаза 2 биле соодветно направени.

Постои една разлика, и таа е вистинска грешка во дизајнот од Фаза 2:

  • Фаза 2: Payment(id, user_id, enrollment_id, amount)
  • По нормализација: Payment(id, enrollment_id, amount)

Атрибутот user_id е редундантен, бидејќи enrollment_id → user_id. Покрај редундантноста, ваквиот дизајн дозволува аномалија при ажурирање: плаќање може да биде запишано на еден студент, а да се однесува на запишување на друг студент, што базата не го спречува со ниту едно ограничување.

За наредните фази се користи нормализираниот модел, односно табелата payment повеќе не содржи user_id. Скриптите schema_creation.sql и data_load.sql, како и документацијата на Фаза 2, се ажурирани соодветно.

Забелешка за постапката

Кандидат клучевите и проверката за БКНФ не се одредени само со разгледување, туку се пресметани програмски врз множеството функционални зависности (пресметка на покривач на атрибути и проверка дали секоја детерминанта е суперклуч во секоја релација). Токму таа проверка го откри нарушувањето кај Payment.

Со истата пресметка е потврдено дека затворачот на секој од петте кандидат клучеви ги покрива сите 57 атрибути на R, дека ниту едно нивно вистинско подмножество не е суперклуч, и дека не постои шести кандидат клуч.

Историјат

Верзија 1 - Прва верзија на нормализацијата: денормализирана релација, функционални зависности, кандидат клучеви и декомпозиција до БКНФ и 4НФ. Откриено и отстрането нарушување на БКНФ во релацијата Payment.

Верзија 2 - По забелешки: додадена е целосна пресметка на затворачот за сите пет кандидат клучеви со проверка дека покриваат 57/57 атрибути, проверка на минималноста и доказ дека нема други кандидат клучеви. Кај секоја декомпозиција е прецизно наведено кои две релации се спојуваат, по кои заеднички атрибути и на која од нив тие се клуч, со посебен критериум за чекорите во 4НФ. Стрелката → е задржана исклучиво за функционални зависности; преименувањата, пресметките и заклучоците сега користат табела, односно ⇒.

Статус

Во тек

Last modified 3 days ago Last modified on 09/24/26 20:05:14
Note: See TracWiki for help on using the wiki.