Changes between Initial Version and Version 1 of Normalization

Timestamp:

09/16/26 14:17:27 (12 days ago)

Author:

233149

Comment:

--

Normalization

@@ +1 @@
+== Нормализација
+
+== Денормализирана форма на базата
+
+Постапката започнува од една единствена денормализирана релација '''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, Во тек )]] '''