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

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

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

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

 [wiki:NormalizationAIUsage NormalizationAIUsage]

== Историјат

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

== Статус

 ''' [[span(style=color: #FF8000, Во тек )]] '''