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

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

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

Бидејќи во моделот повеќе ентитети имаат атрибут со исто име (id, name, type, created_at), атрибутите се преименувани така што во 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.

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

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.

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: спојувањето по document_id ја реконструира R, бидејќи document_id е клуч на Documents.
• 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: спојување по token_id; token_id е клуч на Token.
• Dependency preservation: FD20 е сочувана во Token.

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

Payment(payment_id, enrolled_id, amount)

R3 = R2 − { amount }

• Клуч: payment_id
• Lossless join: спојување по payment_id.
• 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: спојување по subject_id.
• 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: спојување по user_id.
• 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: спојување по high_school_id.
• 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: спојување по contact_id.
• 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: спојување по enrolled_id.
• 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: спојување по major_id.
• 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: спојување по semester_id.
• 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: спојување по sem_subject_id.
• 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: спојување по passed_id.
• 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: спојување по (major_id, subject_id).
• 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: enrolled_id е надворешен клуч кон EnrolledSemesters, каде е клуч, па спојувањето е без загуба.
• Dependency preservation: FD21 останува сочувана, бидејќи payment_id → enrolled_id, amount е во Payment, а payment_id → user_id се изведува транзитивно преку FD13.

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

4НФ

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

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

• UserDocuments(user_id, document_id) - од FD23
• DependencySubject(subject_id, prerequisite_id) - од FD24
• ProfessourSubjects(teaching_prof_id, semester_id, subject_id) - од FD25

Останатите идентификатори од R13 (high_school_id, contact_id, major_id, enrolled_id, sem_subject_id, passed_id, token_id, payment_id) веќе се примарни клучеви во претходно издвоените релации, па не формираат нова релација.

• Lossless join: спојување по заедничките атрибути ја враќа R13.
• Dependency preservation: трите нови релации не носат функционални зависности, туку само врски.

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

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

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 релации се во БКНФ, декомпозицијата ги сочувува сите функционални зависности и е без загуба при спојување.

Дискусија

Постапката на нормализација, спроведена независно од дизајнот на Фаза 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.

Користење на вештачка интелигенција

NormalizationAIUsage

Историјат

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

Статус

Во тек