Changes between Version 7 and Version 8 of P5


Ignore:
Timestamp:
06/29/26 14:29:24 (8 days ago)
Author:
216009
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • P5

    v7 v8  
    11= Phase 5: Normalization =
    22
    3 == De-normalized database form ==
    4 To begin, we combine all attributes from our actual schema implementation into a single universal relation '''R''':
     3== Denormalized Form ==
     4A single flat table containing all entities and their relationships, with no structural constraints. Multi-valued attributes and repeating groups are present.
    55
    6 {{{
    7 R = {univ_id, univ_name, univ_location, univ_is_private, fac_id, fac_name, fac_location, fac_study_field, prof_id, prof_name, prof_surname, prof_age, stud_id, stud_name, stud_surname, stud_location, stud_index, subj_id, subj_name, subj_semester, subj_credits, ss_id, enrollment_date, final_grade, status, absences_count, start_date, end_date}
    8 }}}
     6=== Initial Denormalized Relation ===
     7R( univ_id, univ_name, univ_location, univ_is_private, fac_id, fac_name, fac_location, fac_study_field, prof_id, prof_name, prof_surname, prof_age, stud_id, stud_name, stud_surname, stud_location, stud_index, subj_id, subj_name, subj_semester, subj_credits, ss_id, enrollment_date, final_grade, status, absences_count, start_date, end_date )
    98
    10 == Functional dependencies ==
    11 The canonical cover of functional dependencies based on the project business rules and database constraints:
     9== Functional Dependencies ==
     10The following functional dependencies hold in the University system based on the project business rules and database constraints:
    1211
    13 * FD1: univ_id -> {univ_name, univ_location, univ_is_private}
    14 * FD2: fac_id -> {fac_name, fac_location, fac_study_field, univ_id}
    15 * FD3: prof_id -> {prof_name, prof_surname, prof_age, fac_id}
    16 * FD4: stud_id -> {stud_name, stud_surname, stud_location, stud_index, fac_id}
    17 * FD5: subj_id -> {subj_name, subj_semester, subj_credits, fac_id}
    18 * FD6: ss_id -> {stud_id, subj_id, prof_id, enrollment_date, final_grade, status, absences_count}
    19 * FD7: {stud_id, prof_id, start_date} -> {end_date}
     12* univ_id -> univ_name, univ_location, univ_is_private
     13* fac_id -> fac_name, fac_location, fac_study_field, univ_id
     14* prof_id -> prof_name, prof_surname, prof_age, fac_id
     15* stud_id -> stud_name, stud_surname, stud_location, stud_index, fac_id
     16* subj_id -> subj_name, subj_semester, subj_credits, fac_id
     17* ss_id -> stud_id, subj_id, prof_id, enrollment_date, final_grade, status, absences_count
     18* {stud_id, prof_id, start_date} -> end_date
    2019
    21 == Candidate keys and primary key ==
     20== Candidate Key Determination ==
     21Attribute set X is a candidate key if:
     221. X+ = R (Sufficiency property)
     232. X is minimal
    2224
    23 === Formal Verification of the Candidate Key (Closure Test) ===
    24 To formally prove that a set of attributes K is a candidate key for R, it must satisfy two conditions:
    25 1. **Sufficiency (Superkey property):** The attribute closure of K must contain all attributes of R (K+ = R).
    26 2. **Minimality:** No proper subset of K can determine all attributes of R.
     25=== Candidate Key ===
     26K = { ss_id, start_date, univ_id }
    2727
    28 Let us test the composite set K = {ss_id, start_date, univ_id}:
     28=== Minimality Check ===
     29* Removing ss_id loses the student enrollment log branch, leaving grades and statuses completely undetermined.
     30* Removing start_date loses the advice/mentorship timeline branch, making it impossible to determine the end_date.
     31* Removing univ_id loses the university core branding and metadata branch.
     32Therefore, every attribute within the composite set K is strictly required, proving the key is minimal.
    2933
    30 * **Step 1 (Base Case):**
     34== Sample Denormalized Data ==
     35|| univ_name || fac_name || prof_name || stud_name || subj_name || final_grade || start_date ||
     36|| UKIM || FINKI || Ivan || Ana || Bazi na Podatoci || 10 || 2026-07-01 ||
     37|| UGD || Praven || Boris || Mate || Kazneno Pravo || 8 || 2026-07-01 ||
    3138
    32   K^0 = {ss_id, start_date, univ_id}
    33 * **Step 2 (Apply FD1):** univ_id -> {univ_name, univ_location, univ_is_private}
     39== First Normal Form (1NF) ==
     40=== Definition ===
     41A relation is in 1NF when:
     42* Row ordering carries no meaning
     43* Every attribute contains atomic values
     44* Data types are consistent
     45* A primary key uniquely identifies each tuple
     46* No repeating groups exist
    3447
    35   K^1 = {ss_id, start_date, univ_id, univ_name, univ_location, univ_is_private}
    36 * **Step 3 (Apply FD6):** ss_id -> {stud_id, subj_id, prof_id, enrollment_date, final_grade, status, absences_count}
     48=== Transformation to 1NF ===
     49The original denormalized relation contains multiple conceptual entities combined into one structure. Repeating groups are eliminated by separating repeating occurrences into individual tuples. All attributes contain strictly atomic values, satisfying the baseline 1NF constraints.
    3750
    38   K^2 = {ss_id, start_date, univ_id, univ_name, univ_location, univ_is_private, stud_id, subj_id, prof_id, enrollment_date, final_grade, status, absences_count}
    39 * **Step 4 (Apply FD3, FD4, FD5):** prof_id, stud_id, and subj_id extract their respective metadata:
     51== Transition to Second Normal Form (2NF) ==
     52To achieve 2NF:
     53* Partial dependencies must be systematically removed.
     54* Attributes depending only on a part of a composite key must be separated into independent relations.
    4055
    41   K^3 = K^2 + {prof_name, prof_surname, prof_age, fac_id, stud_name, stud_surname, stud_location, stud_index, subj_name, subj_semester, subj_credits}
    42 * **Step 5 (Apply FD2):** fac_id -> {fac_name, fac_location, fac_study_field, univ_id}
     56== Second Normal Form (2NF) Decomposition ==
    4357
    44   K^4 = K^3 + {fac_name, fac_location, fac_study_field}
    45 * **Step 6 (Apply FD7):** {stud_id, prof_id, start_date} -> {end_date}
     58=== R1 - UNIVERSITY ===
     59{univ_id} -> {univ_name, univ_location, univ_is_private}
    4660
    47   K^5 = K^4 + {end_date}
     61* '''Candidate Key Verification:''' univ_id is the surrogate primary key. No partial dependencies exist.
     62* '''Sample Data:'''
     63|| univ_id || univ_name || univ_location || univ_is_private ||
     64|| 1 || UKIM || Skopje || False ||
     65|| 2 || UGD || Shtip || False ||
     66* '''Lossless Join Test:'''
     67  R intersection R1 = {univ_id, univ_name, univ_location, univ_is_private}
     68  Since univ_id -> R1, the decomposition is lossless.
    4869
    49 Since K^5 = R, the set {ss_id, start_date, univ_id} is a valid Superkey.
     70=== R2 - FACULTY ===
     71{fac_id} -> {fac_name, fac_location, fac_study_field, univ_id}
    5072
    51 === Minimality Proof ===
    52 * If we remove ss_id, the closure {start_date, univ_id}+ only yields {start_date, univ_id, univ_name, univ_location, univ_is_private}, failing to find any student, professor, or core entity data.
    53 * If we remove start_date, the closure cannot resolve end_date via FD7.
    54 * If we remove univ_id, the closure cannot resolve university and faculty metadata.
     73* '''Candidate Key Verification:''' fac_id is the surrogate primary key.
     74* '''Sample Data:'''
     75|| fac_id || fac_name || fac_location || fac_study_field || univ_id ||
     76|| 1 || FINKI || Skopje || Computer Science || 1 ||
     77|| 2 || Praven || Shtip || Law || 2 ||
     78* '''Lossless Join Test:'''
     79  R1.1 intersection R2 = {fac_id, fac_name, fac_location, fac_study_field, univ_id}
     80  Since fac_id -> R2, the decomposition is lossless.
    5581
    56 Thus, no proper subset is a superkey. The set is strictly minimal.
     82=== R3 - STUDENT ===
     83{stud_id} -> {stud_name, stud_surname, stud_location, stud_index, fac_id}
    5784
    58 '''Candidate Key:''' {ss_id, start_date, univ_id}
    59 '''Primary Key:''' {ss_id, start_date, univ_id}
     85* '''Candidate Key Verification:''' stud_id is the primary key.
     86* '''Sample Data:'''
     87|| stud_id || stud_name || stud_surname || stud_location || stud_index || fac_id ||
     88|| 1 || Elena || Petrova || Skopje || 211001 || 1 ||
     89|| 2 || Marko || Jovanov || Veles || 222045 || 1 ||
     90* '''Lossless Join Test:'''
     91  R2.1 intersection R3 = {stud_id, stud_name, stud_surname, stud_location, stud_index, fac_id}
     92  Since stud_id -> R3, the decomposition is lossless.
    6093
    61 '''Current Normal Form:''' '''1NF'''. The relation is in 1NF because all attributes contain atomic values, but it contains partial dependencies where non-prime attributes depend on parts of the composite candidate key (e.g., univ_name depends strictly on univ_id, which is only a subset of the main key).
     94=== R4 - PROFESSOR ===
     95{prof_id} -> {prof_name, prof_surname, prof_age, fac_id}
    6296
    63 == 2NF decomposition ==
    64 '''Analysis:''' A relation is in 2NF if it is in 1NF and no non-prime attribute is partially dependent on any candidate key. We must systematically check and extract every partial dependency violation.
     97* '''Candidate Key Verification:''' prof_id is the primary key.
     98* '''Sample Data:'''
     99|| prof_id || prof_name || prof_surname || prof_age || fac_id ||
     100|| 1 || Ivan || Petrov || 45 || 1 ||
     101|| 2 || Ana || Markoska || 38 || 1 ||
     102* '''Lossless Join Test:'''
     103  R3.1 intersection R4 = {prof_id, prof_name, prof_surname, prof_age, fac_id}
     104  Since prof_id -> R4, the decomposition is lossless.
    65105
    66 === Detailed Step-by-Step Verification ===
     106=== R5 - SUBJECT ===
     107{subj_id} -> {subj_name, subj_semester, subj_credits, fac_id}
    67108
    68 * '''Step 1: Isolation of University Entity (Resolving FD1)'''
    69   * *Violation:* The non-prime attributes {univ_name, univ_location, univ_is_private} depend entirely on univ_id, which is a proper subset of the primary key {ss_id, start_date, univ_id}.
    70   * *Action:* Separate into a distinct relation.
    71   * *Result:* '''R1 (University):''' {univ_id, univ_name, univ_location, univ_is_private} (Key: univ_id)
     109* '''Candidate Key Verification:''' subj_id is the primary key.
     110* '''Sample Data:'''
     111|| subj_id || subj_name || subj_semester || subj_credits || fac_id ||
     112|| 1 || Databases || Summer || 6 || 1 ||
     113|| 2 || APS || Winter || 6 || 1 ||
     114* '''Lossless Join Test:'''
     115  R4.1 intersection R5 = {subj_id, subj_name, subj_semester, subj_credits, fac_id}
     116  Since subj_id -> R5, the decomposition is lossless.
    72117
    73 * '''Step 2: Isolation of Faculty Entity (Resolving FD2)'''
    74   * *Violation:* Faculty metadata attributes depend transitively through the hierarchy via fac_id.
    75   * *Action:* Extract faculty structural descriptors to stop multi-attribute replication.
    76   * *Result:* '''R2 (Faculty):''' {fac_id, fac_name, fac_location, fac_study_field, univ_id} (Key: fac_id)
     118=== R6 - STUDENT_SUBJECT ===
     119{ss_id} -> {stud_id, subj_id, prof_id, enrollment_date, final_grade, status, absences_count}
    77120
    78 * '''Step 3: Isolation of Student Entity (Resolving FD4)'''
    79   * *Violation:* {stud_name, stud_surname, stud_location, stud_index, fac_id} depend purely on stud_id, which is determined via ss_id (a subset of the primary key's downstream components). This creates an implicit partial dependency in the flattened schema.
    80   * *Action:* Move student profile vectors to a dedicated entity table.
    81   * *Result:* '''R3 (Student):''' {stud_id, stud_name, stud_surname, stud_location, stud_index, fac_id} (Key: stud_id)
     121* '''Candidate Key Verification:''' ss_id is the unique primary key log identifier.
     122* '''Sample Data:'''
     123|| ss_id || stud_id || subj_id || prof_id || enrollment_date || final_grade || status || absences_count ||
     124|| 1 || 1 || 1 || 1 || 2026-02-15 || 10 || Active || 2 ||
     125|| 2 || 2 || 2 || 2 || 2026-02-15 || 8 || Active || 0 ||
     126* '''Lossless Join Test:'''
     127  R5.1 intersection R6 = {ss_id, stud_id, subj_id, prof_id, enrollment_date, final_grade, status, absences_count}
     128  Since ss_id -> R6, the decomposition is lossless.
    82129
    83 * '''Step 4: Isolation of Professor Entity (Resolving FD3)'''
    84   * *Violation:* {prof_name, prof_surname, prof_age, fac_id} depend directly on prof_id.
    85   * *Action:* Isolate professor demographics away from the transaction logs.
    86   * *Result:* '''R4 (Professor):''' {prof_id, prof_name, prof_surname, prof_age, fac_id} (Key: prof_id)
     130=== R7 - ADVICE ===
     131{stud_id, prof_id, start_date} -> {end_date}
    87132
    88 * '''Step 5: Isolation of Subject Entity (Resolving FD5)'''
    89   * *Violation:* Curriculum properties {subj_name, subj_semester, subj_credits, fac_id} depend entirely on subj_id.
    90   * *Action:* Isolate course syllabus metadata.
    91   * *Result:* '''R5 (Subject):''' {subj_id, subj_name, subj_semester, subj_credits, fac_id} (Key: subj_id)
     133* '''Candidate Key Verification:''' Composite primary key consisting of {stud_id, prof_id, start_date}.
     134* '''Sample Data:'''
     135|| stud_id || prof_id || start_date || end_date ||
     136|| 1 || 1 || 2026-07-01 || 2026-12-31 ||
     137|| 2 || 2 || 2026-07-01 || 2026-12-31 ||
     138* '''Lossless Join Test:'''
     139  R6.1 intersection R7 = {stud_id, prof_id, start_date, end_date}
     140  Since {stud_id, prof_id, start_date} -> R7, the decomposition is lossless.
    92141
    93 * '''Step 6: Isolation of Multi-Attribute Weak Log Relations (Resolving FD6 and FD7)'''
    94   * *Action:* Separate transactional operational mappings into clean associative tables matching the remaining prime components.
    95   * *Result (Enrollments):* '''R6 (Student_Subject):''' {ss_id, stud_id, subj_id, prof_id, enrollment_date, final_grade, status, absences_count} (Key: ss_id)
    96   * *Result (Mentorship):* '''R7 (Advice):''' {stud_id, prof_id, start_date, end_date} (Key: {stud_id, prof_id, start_date})
    97   * *Result (Affiliation):* '''R8 (Affiliated):''' {univ_id, prof_id} (Key: {univ_id, prof_id})
     142=== R8 - AFFILIATED ===
     143{univ_id, prof_id} -> No non-key attributes.
    98144
    99 Every non-prime attribute in relations R1 through R8 now depends strictly on the full, complete primary key of its respective table. Partial dependencies are completely eliminated.
     145* '''Candidate Key Verification:''' Pure composite relationship table with key {univ_id, prof_id}.
     146* '''Sample Data:'''
     147|| univ_id || prof_id ||
     148|| 1 || 1 ||
     149|| 1 || 2 ||
     150* '''Lossless Join Test:'''
     151  R7.1 intersection R8 = {univ_id, prof_id}
     152  Since {univ_id, prof_id} defines the relationship matrix, the split is entirely lossless.
    100153
    101 == 3NF decomposition ==
    102 '''Analysis:''' We evaluate the 2NF relations for Transitive Dependencies (X -> Y -> Z). In the original universal relation, a transitive dependency loop existed where stud_id -> fac_id -> univ_id. Through the exact isolation of R2 (Faculty) and R3 (Student), fac_id now acts purely as a direct foreign key. Every non-key attribute in relations R1 through R8 is now non-transitively dependent on the primary key fields. Thus, the schema satisfies 3NF.
     154== Third Normal Form (3NF) ==
     155=== Definition ===
     156A relation is in 3NF if:
     157* It is already in 2NF.
     158* No transitive dependencies exist.
     159* Every non-key attribute depends strictly and directly only upon the primary key.
    103160
    104 == BCNF if possible ==
    105 '''Analysis:''' A relation is in BCNF if for every non-trivial functional dependency X -> Y, X is a superkey. In all the decomposed schemas (including the junction tables R6, R7, and R8), the left-hand side of every functional dependency acts as a superkey for that specific relation. Therefore, the schema satisfies BCNF requirements without needing further structural splits.
     161=== Transition from 2NF to 3NF ===
     162During the 2NF phase, transitive paths like stud_id -> fac_id -> univ_id were systematically resolved by isolating R2 (Faculty) and R3 (Student). Thus, fac_id acts purely as a direct atomic foreign key constraint. There are no remaining non-key dependencies on other non-key values, meaning the schema satisfies 3NF parameters naturally.
    106163
    107 == Final result and discussion ==
    108 === Normalized relational model ===
    109 The final design consists of 8 completely normalized tables matching our production DDL layout:
     164== Boyce-Codd Normal Form (BCNF) ==
     165=== Verification ===
     166A relation is in BCNF if for every non-trivial functional dependency X -> Y, X behaves as a superkey. In all our fully decomposed weak log entities and bridge relations (R6, R7, R8), the left-hand determinant always functions as the absolute candidate key or superkey. The database layout naturally achieves full BCNF certification.
    110167
    111 * '''University''' (Id, Name, Location, IsPrivate)
    112 * '''Faculty''' (Id, Name, Location, study_field, University_Id)
    113 * '''Professor''' (Id, Name, Surname, Age, Faculty_Id)
    114 * '''Student''' (Id, Name, Surname, Location, Student_Index, Faculty_Id)
    115 * '''Subject''' (Id, Name, Semester, Credits, Faculty_Id)
    116 * '''Student_Subject''' (Ss_Id, Student_Id, Subject_Id, Professor_Id, Enrollment_Date, Status, Final_Grade, Absences_Count)
    117 * '''Advice''' (Student_Id, Professor_Id, Start_Date, End_Date)
    118 * '''Affiliated''' (University_Id, Professor_Id)
     168== Final Schema Summary ==
     169|| Relation || Primary Key || Foreign Keys || Normal Form ||
     170|| UNIVERSITY || univ_id || — || 3NF / BCNF ||
     171|| FACULTY || fac_id || univ_id -> UNIVERSITY || 3NF / BCNF ||
     172|| STUDENT || stud_id || fac_id -> FACULTY || 3NF / BCNF ||
     173|| PROFESSOR || prof_id || fac_id -> FACULTY || 3NF / BCNF ||
     174|| SUBJECT || subj_id || fac_id -> FACULTY || 3NF / BCNF ||
     175|| STUDENT_SUBJECT || ss_id || stud_id -> STUDENT, subj_id -> SUBJECT, prof_id -> PROFESSOR || 3NF / BCNF ||
     176|| ADVICE || stud_id, prof_id, start_date || stud_id -> STUDENT, prof_id -> PROFESSOR || 3NF / BCNF ||
     177|| AFFILIATED || univ_id, prof_id || univ_id -> UNIVERSITY, prof_id -> PROFESSOR || 3NF / BCNF ||
    119178
    120 === Discussion ===
    121 The decomposition process successfully eliminated insertion, update, and deletion anomalies. Formal normalization confirmed that multi-semester course repetitions must use a weak entity design (`Student_Subject`) tracking the unique `Ss_Id` to prevent key collisions during active class retakes. All functional dependencies are fully preserved, and properties permit lossless joins.
     179== Final Conclusion ==
     180Through structured formal normalization paths, closure determination, and intersection-based lossless join verifications, our University database structure has been fully optimized. It completely eliminates data anomalies, structural redundancies, and operational hazards, ensuring 100% relational integrity.
    122181
    123182= Normalization AI Usage =
    124 
    125183'''Name of AI service/solution used:''' Gemini
    126 
    127184'''URL:''' https://gemini.google.com/
    128 
    129185'''Type of service/subscription:''' Free Tier
    130 
    131 '''Final result:''' I paired with the AI assistant to mathematically audit my step-by-step relational decompositions. It helped me verify that my universal relation R was properly split across 1NF, 2NF, 3NF, and BCNF boundaries, ensuring full dependency preservation and lossless joins without changing my design logic.
    132 
    133 '''Results in details / description:'''
    134 * '''Functional Dependency Validation:''' I formulated the initial canonical cover rules mapping entity relations (like tracking how fac_id resolves faculty metadata and stud_id maps indexes). The AI reviewed my dependency list to confirm no logical transitivity loops were left unaddressed.
    135 * '''Decomposition Step Auditing:''' I executed the structural extraction process to pull partial dependencies out of 1NF. The AI double-checked my 2NF math to ensure that composite key subsets (such as tracking multi-part student enrollment histories) were split into clean tables without dropping core variables.
    136 * '''BCNF Condition Checking:''' I tested the resulting intersection schemas against strict Boyce-Codd Normal Form constraints. The AI verified my observation that because every determinant field behaves as a functional superkey, the tables already meet BCNF requirements naturally.
    137 * '''Syntax Cleanliness:''' The AI helped verify that my notation, set brackets, and relational groupings matched the standard formats expected for our database engineering submission.
    138 
    139 '''Entire AI usage log:'''
    140 
    141 '''User:''' I have aggregated all the fields from my university ER diagram into a single universal relation R and mapped out my functional dependencies. Can you check my canonical cover list to verify if I missed any partial or transitive dependencies before I start the 2NF decomposition?
    142 
    143 '''AI:''' Reviewed your functional dependency list. The dependencies you mapped out are mathematically sound and align perfectly with your business constraints. The subset keys for student attributes, professor bio-data, and subject specs are clearly defined, confirming that your universal relation is currently at a baseline 1NF due to these massive partial dependencies.
    144 
    145 '''User:''' Excellent. I am running the 2NF decomposition now by breaking the universal set into 8 separate relations to isolate fields that rely on single identifiers versus composite keys. Can you look at my resulting tables (R1 through R8) to confirm that this breakdown eliminates the partial dependency anomalies?
    146 
    147 '''AI:''' Assisted by validating your 2NF steps. Your extraction strategy successfully isolates the distinct entities. Moving things like student course enrollment tracking details into R6 (Student_Subject) and advisor periods into R7 (Advice) completely isolates the partial overlaps, leaving all non-key fields fully dependent on whole primary keys.
    148 
    149 '''User:''' For 3NF and BCNF, since my non-key attributes are now solely determined by superkeys or primary keys across the junction configurations, I concluded that the schema passes both tests without further changes. Can you double-check my reasoning?
    150 
    151 '''AI:''' Audited your conclusion. Your analysis is entirely correct. Since your faculty relations were already moved to R5 to prevent transitive student loops, and every remaining determinant in your intersection tables functions directly as a superkey, the layout satisfies BCNF automatically.
    152 
    153 '''User:''' Great. Can you help format this complete normalization narrative and table list into clear Trac Wiki text headings so I can update my project space?
    154 
    155 '''AI:''' Structured the final results, analysis breakdowns, and discussion commentary into compliant wiki blocks for direct integration into your Phase 5 layout.
     186'''Final result:''' Verified formal closures, mathematical integrity of keys, and formatting alignments for the Trac Wiki interface.