Changes between Version 8 and Version 9 of Normalization


Ignore:
Timestamp:
08/28/26 00:09:01 (5 days ago)
Author:
181201
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • Normalization

    v8 v9  
    4545'''FD7:''' {{{service_id}}} → {{{service_type}}}, {{{service_description}}}
    4646
    47 '''FD8:''' {{{booking_id}}} → {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}}, {{{owner_id}}}, {{{sitter_id}}}
     47'''FD8:''' {{{booking_id}}} → {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}}, {{{owner_id}}}, {{{sitter_id}}}, {{{service_id}}}
    4848
    4949'''FD9:''' {{{review_id}}} → {{{rating}}}, {{{comment}}}, {{{booking_id}}}
    … …  
    5656
    5757'''FD13:''' ({{{sitter_id}}}, {{{service_id}}}) → ∅ (represents SitterServices M:N)
    58 
    59 '''FD14:''' ({{{booking_id}}}, {{{service_id}}}) → ∅ (represents BookingServices M:N)
    6058
    6159== Candidate keys and primary key selection ==
    … …  
    6866|| '''admin_id''' || ✓ (FD2, FD11) || ✗ || '''Left only''' ||
    6967|| '''pet_id''' || ✓ (FD6, FD12) || ✗ || '''Left only''' ||
    70 || '''service_id''' || ✓ (FD7, FD13, FD14) || ✗ || '''Left only''' ||
    7168|| '''review_id''' || ✓ (FD9) || ✗ || '''Left only''' ||
    7269|| '''payment_id''' || ✓ (FD10) || ✗ || '''Left only''' ||
    … …  
    7471|| {{{owner_id}}} || ✓ (FD3) || ✓ (FD6, FD8) || Both ||
    7572|| {{{sitter_id}}} || ✓ (FD4, FD13) || ✓ (FD8) || Both ||
     73|| {{{service_id}}} || ✓ (FD7, FD13) || ✓ (FD8) || Both ||
    7674|| {{{pettype_id}}} || ✓ (FD5) || ✓ (FD6) || Both ||
    77 || {{{booking_id}}} || ✓ (FD8, FD12, FD14) || ✓ (FD9, FD10) || Both ||
     75|| {{{booking_id}}} || ✓ (FD8, FD12) || ✓ (FD9, FD10) || Both ||
    7876|| {{{username}}}, {{{first_name}}}, {{{last_name}}}, {{{password}}}, {{{email}}} || ✗ || ✓ (FD1) || Right only ||
    7977|| {{{species}}}, {{{average_lifespan}}}, {{{needs_outdoor_walk}}} || ✗ || ✓ (FD5) || Right only ||
    … …  
    8886 * '''admin_id'''
    8987 * '''pet_id'''
    90  * '''service_id'''
    9188 * '''review_id'''
    9289 * '''payment_id'''
    9390
    9491=== Closure Computation ===
    95 '''Step 1:''' We start with our mandatory attributes {{{ {admin_id, pet_id, service_id, review_id, payment_id} }}} and compute the mathematical closure:
    96 
    97 {{{ {admin_id, pet_id, service_id, review_id, payment_id}⁺ }}}:
     92'''Step 1:''' We start with our mandatory attributes {{{ {admin_id, pet_id, review_id, payment_id} }}} and compute the mathematical closure:
     93
     94{{{ {admin_id, pet_id, review_id, payment_id}⁺ }}}:
    9895 * '''From FD2''' ({{{admin_id}}} → {{{user_id}}}): We obtain {{{user_id}}}
    9996 * '''From FD1''' ({{{user_id}}} → {{{username}}}, {{{first_name}}}...): We obtain {{{username, first_name, last_name, password, email}}}
    10097 * '''From FD6''' ({{{pet_id}}} → {{{pet_name}}}, {{{photo}}}... {{{owner_id}}}, {{{pettype_id}}}): We obtain {{{pet_name, photo, age, special_needs, pet_description, owner_id, pettype_id}}}
    10198 * '''From FD5''' ({{{pettype_id}}} → {{{species}}}...): We obtain {{{species, average_lifespan, needs_outdoor_walk}}}
    102  * '''From FD7''' ({{{service_id}}} → {{{service_type}}}...): We obtain {{{service_type, service_description}}}
    10399 * '''From FD9''' ({{{review_id}}} → {{{rating}}}, {{{comment}}}, {{{booking_id}}}): We obtain {{{rating, comment, booking_id}}}
    104  * '''From FD8''' ({{{booking_id}}} → {{{booking_status}}}... {{{sitter_id}}}): We obtain {{{booking_status, date_from, date_to, address, sitter_id}}}
     100 * '''From FD8''' ({{{booking_id}}} → {{{booking_status}}}... {{{sitter_id}}}, {{{service_id}}}): We obtain {{{booking_status, date_from, date_to, address, sitter_id, service_id}}}
     101 * '''From FD7''' ({{{service_id}}} → {{{service_type}}}, {{{service_description}}}): We obtain {{{service_type, service_description}}}
    105102 * '''From FD10''' ({{{payment_id}}} → {{{amount}}}, {{{payment_type}}}, {{{booking_id}}}): We obtain {{{amount, payment_type}}} ({{{booking_id}}} is already in closure)
    106103 * '''From FD3 & FD4:''' {{{owner_id}}} and {{{sitter_id}}} map to {{{user_id}}}, which is already in the closure.
    107  * '''From FD11-FD14:''' All composite pairings (e.g., {{{booking_id}}} and {{{pet_id}}}) are already present in the closure, satisfying the M:N relations.
     104 * '''From FD11-FD13:''' All composite pairings (e.g., {{{booking_id}}} and {{{pet_id}}}) are already present in the closure, satisfying the M:N relations.
    108105
    109106'''Closure = Universal_Relation ✓''' (all 33 attributes are successfully derived)
    110107
    111108=== Minimality Check ===
    112 To formally prove this key is minimal, we test proper subsets of '''K = {admin_id, pet_id, service_id, review_id, payment_id}''':
     109To formally prove this key is minimal, we test proper subsets of '''K = {admin_id, pet_id, review_id, payment_id}''':
    113110
    114111|| '''Subset''' || '''Closure Equals Universal_Relation?''' || '''Justification''' ||
    115112|| '''K − {admin_id}''' || ✗ NO || Cannot derive {{{admin_id}}}. ||
    116113|| '''K − {pet_id}''' || ✗ NO || Cannot derive pet attributes ({{{pet_name, photo, age, special_needs, pet_description}}}). ||
    117 || '''K − {service_id}''' || ✗ NO || Cannot derive service attributes ({{{service_type, service_description}}}). ||
    118114|| '''K − {review_id}''' || ✗ NO || Cannot derive review attributes ({{{review_id, rating, comment}}}). ||
    119115|| '''K − {payment_id}''' || ✗ NO || Cannot derive payment attributes ({{{payment_id, amount, payment_type}}}). ||
    120116
    121 '''Conclusion:''' K = {admin_id, pet_id, service_id, review_id, payment_id} is minimal and is the strictly mathematically correct candidate key.
     117'''Conclusion:''' K = {admin_id, pet_id, review_id, payment_id} is minimal and is the strictly mathematically correct candidate key.
    122118
    123119=== Choice of Primary Key ===
    124 '''Chosen Primary Key:''' {{{ {admin_id, pet_id, service_id, review_id, payment_id} }}}
    125 
    126 '''Justification:''' This composite key is the officially proven minimal Candidate Key. Attempting to include other logical identifiers (such as {{{owner_id}}}, {{{sitter_id}}}, or {{{booking_id}}}) would violate the rule of minimality, because the closure proof demonstrates those attributes are functionally dependent on the core transactional IDs.
     120'''Chosen Primary Key:''' {{{ {admin_id, pet_id, review_id, payment_id} }}}
     121
     122'''Justification:''' This composite key is the officially proven minimal Candidate Key. Attempting to include other logical identifiers (such as {{{owner_id}}}, {{{sitter_id}}}, {{{service_id}}} or {{{booking_id}}}) would violate the rule of minimality, because the closure proof demonstrates those attributes are functionally dependent on the core transactional IDs. In particular {{{service_id}}} is no longer part of the key, because each {{{Booking}}} requires exactly one {{{Service}}} and therefore {{{service_id}}} is derivable from {{{booking_id}}} through FD8.
    127123
    128124=== Current Normal Form Status ===
    … …  
    155151'''Services''' ({{{service_id}}}, {{{service_type}}}, {{{service_description}}})
    156152
    157 '''Bookings''' ({{{booking_id}}}, {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}}, {{{owner_id}}}, {{{sitter_id}}})
     153'''Bookings''' ({{{booking_id}}}, {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}}, {{{owner_id}}}, {{{sitter_id}}}, {{{service_id}}})
    158154
    159155'''Reviews''' ({{{review_id}}}, {{{rating}}}, {{{comment}}}, {{{booking_id}}})
    … …  
    167163'''SitterServices''' ({{{sitter_id}}}, {{{service_id}}})
    168164
    169 '''BookingServices''' ({{{booking_id}}}, {{{service_id}}})
    170 
    171165'''1. Loss-less Join Property Validation:'''
    172 By definition (Heath's Theorem), a decomposition of relation ''R'' into ''R1'' and ''R2'' is lossless if the intersection of their attributes (''R1'' ∩ ''R2'') forms a superkey for either ''R1'' or ''R2''. To achieve our final schema without data loss, the universal relation ''R'' was decomposed through '''13 successive binary splits'''. Below is the formal proof of each split, detailing the exact attributes partitioned.
     166By definition (Heath's Theorem), a decomposition of relation ''R'' into ''R1'' and ''R2'' is lossless if the intersection of their attributes (''R1'' ∩ ''R2'') forms a superkey for either ''R1'' or ''R2''. To achieve our final schema without data loss, the universal relation ''R'' was decomposed through '''12 successive binary splits'''. Below is the formal proof of each split, detailing the exact attributes partitioned.
    173167
    174168Let '''R_remainder''' be the remainder relation after each split
    … …  
    228222'''Split 8: Extracting Bookings (FD8)'''
    229223 * '''Decomposition:''' '''R_remainder7''' is split into '''Bookings''' and '''R_remainder8'''.
    230  * '''Attributes in Bookings:''' {{{ {booking_id, booking_status, date_from, date_to, address, owner_id, sitter_id} }}}
     224 * '''Attributes in Bookings:''' {{{ {booking_id, booking_status, date_from, date_to, address, owner_id, sitter_id, service_id} }}}
    231225 * '''Attributes in R_remainder8:''' {{{ {admin_id, sitter_id, pet_id, service_id, booking_id, review_id, rating, comment, payment_id, amount, payment_type} }}}
    232226 * '''Intersection:''' '''Bookings''' ∩ '''R_remainder8''' = {{{ {booking_id} }}}
    … …  
    247241 * '''Proof:''' {{{payment_id}}} is the Primary Key of the '''Payments''' table. The split is lossless.
    248242
    249 '''Splits 11-13: Extracting M:N Relations/Junctions (FD11-FD14)'''
     243'''Splits 11-12: Extracting M:N Relations/Junctions (FD11-FD13)'''
    250244The final remainder relation ('''R_remainder10''') contains only the composite keys representing the Many-to-Many relationships:
    251245 * '''AdminManagement:''' {{{ {admin_id, user_id} }}}
    252246 * '''BookingPets:''' {{{ {booking_id, pet_id} }}}
    253247 * '''SitterServices:''' {{{ {sitter_id, service_id} }}}
    254  * '''BookingServices:''' {{{ {booking_id, service_id} }}}
    255248
    256249Because these final tables consist only of their composite primary keys, any further binary separation will trivially satisfy Heath's Theorem.
    257250
    258 '''Conclusion:''' Because every single step of the decomposition shared an intersection that was a guaranteed Primary Key, the final 14-table schema is strictly lossless.
     251'''Conclusion:''' Because every single step of the decomposition shared an intersection that was a guaranteed Primary Key, the final 13-table schema is strictly lossless.
    259252
    260253'''2. Dependency Preservation:'''
    261 A decomposition is dependency preserving if the union of the functional dependencies in the new tables is equivalent to the original set of FDs (FD1 to FD14).
     254A decomposition is dependency preserving if the union of the functional dependencies in the new tables is equivalent to the original set of FDs (FD1 to FD13).
    262255Because we explicitly created our relations based on the exact determinants of our FDs, every single functional dependency is fully localized within a single table.
    263256 * For example, FD5 ({{{pettype_id → species, average_lifespan, needs_outdoor_walk}}}) can be completely verified within the new '''PetTypes''' table without needing to perform a JOIN operation with any other table.
    264257 * Similarly, FD7 ({{{service_id → service_type, service_description}}}) is entirely contained within the '''Services''' table.
    265 Since all 14 original FDs are preserved natively inside the 14 new relations, the decomposition is strictly dependency preserving.
     258 * FD8, which now also determines {{{service_id}}}, is entirely contained within the '''Bookings''' table, so the rule that a booking has exactly one service is verifiable without a JOIN.
     259Since all 13 original FDs are preserved natively inside the 13 new relations, the decomposition is strictly dependency preserving.
    266260
    267261=== Step 2: Decomposition to 3NF ===
    268262
    269 '''Relations analyzed:''' All 14 relations obtained from the 2NF decomposition.
     263'''Relations analyzed:''' All 13 relations obtained from the 2NF decomposition.
    270264
    271265'''Issues with higher normal forms:''' A relation violates 3NF if there is a transitive dependency (A → B → C) where a non-prime attribute determines another non-prime attribute.
    … …  
    273267'''Action taken:''' We inspect the 2NF relations to ensure that all non-key attributes depend ''only'' on the primary key, and not on any other non-key attributes. We specifically target tables containing Foreign Keys, as this is where transitive chains can be present.
    274268
    275 * '''In Bookings:''' While {{{booking_id}}} determines {{{owner_id}}}, we must check if {{{owner_id}}} (a non-prime attribute in this table) determines any other non-prime attributes ''within'' this table. It does not. The descriptive user details for the owner are safely isolated in the '''Users''' table.
     269* '''In Bookings:''' While {{{booking_id}}} determines {{{owner_id}}}, {{{sitter_id}}} and {{{service_id}}}, we must check if any of these non-prime attributes determines another non-prime attribute ''within'' this table. They do not. The descriptive user details for the owner are safely isolated in the '''Users''' table, and the descriptive service details are safely isolated in the '''Services''' table.
    276270* '''In Reviews:''' While {{{review_id}}} determines {{{booking_id}}}, we must check if {{{booking_id}}} (a non-prime attribute in this table) determines any other non-prime attributes ''within'' this table (such as the sitter's details). It does not. Those details are isolated in their respective tables.
    277271* '''In Base Entities (Users, PetTypes, Services):''' All non-prime attributes logically depend directly on the primary key (example {{{species}}} depends only on {{{pettype_id}}}), making transitive chains mathematically impossible.
    … …  
    280274'''Result:''' Because we did not store redundant, descriptive data alongside our foreign keys, there are no instances where a non-prime attribute determines another non-prime attribute within the same relation.
    281275
    282 '''Status:''' All 14 relations naturally satisfy '''3NF'''.
     276'''Status:''' All 13 relations naturally satisfy '''3NF'''.
    283277
    284278=== 3. Decomposition to BCNF ===
    285279
    286 '''Relations analyzed:''' All 14 relations currently in 3NF.
     280'''Relations analyzed:''' All 13 relations currently in 3NF.
    287281
    288282'''Issues with higher normal forms:''' A relation violates Boyce-Codd Normal Form (BCNF) if a non-trivial functional dependency X → Y exists where X is not a superkey.
    289283
    290 '''Action taken:''' We evaluate the left side (determinant) of every functional dependency within all 14 relations:
     284'''Action taken:''' We evaluate the left side (determinant) of every functional dependency within all 13 relations:
    291285
    292286In '''Users''', {{{user_id}}} is a superkey.
    … …  
    316310In '''SitterServices''', the composite key ({{{sitter_id}}}, {{{service_id}}}) is the only determinant, meaning it is trivially a superkey.
    317311
    318 In '''BookingServices''', the composite key ({{{booking_id}}}, {{{service_id}}}) is the only determinant, meaning it is trivially a superkey.
    319 
    320312'''Result:''' In every single relation, the determinant is a candidate/superkey.
    321313
    322 '''Status:''' All 14 relations naturally satisfy '''BCNF'''. The decomposition process is complete.
     314'''Status:''' All 13 relations naturally satisfy '''BCNF'''. The decomposition process is complete.
    323315
    324316== Final result and discussion ==
    325317
    326318=== Final normalized relational design ===
    327 The final database schema operates in strict BCNF with the following 14 relations:
     319The final database schema operates in strict BCNF with the following 13 relations:
    328320
    329321'''Users''' ({{{user_id}}}, {{{username}}}, {{{first_name}}}, {{{last_name}}}, {{{password}}}, {{{email}}})
    … …  
    341333'''Services''' ({{{service_id}}}, {{{service_type}}}, {{{service_description}}})
    342334
    343 '''Bookings''' ({{{booking_id}}}, {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}}, {{{owner_id}}}, {{{sitter_id}}})
     335'''Bookings''' ({{{booking_id}}}, {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}}, {{{owner_id}}}, {{{sitter_id}}}, {{{service_id}}})
    344336
    345337'''Reviews''' ({{{review_id}}}, {{{rating}}}, {{{comment}}}, {{{booking_id}}})
    … …  
    352344
    353345'''SitterServices''' ({{{sitter_id}}}, {{{service_id}}})
    354 
    355 '''BookingServices''' ({{{booking_id}}}, {{{service_id}}})
    356346
    357347=== Discussion - compare with Phase 2 ===
    358348With completing the normalization process up to BCNF, we have proven that the resulting schema is identical to the logical design created in Phase 2.
     349
     350== Version history ==
     351
     352[https://develop.finki.ukim.mk/projects/petsitter/wiki/Normalization_v01 v01]
     353* Initial version
     354
     355[https://develop.finki.ukim.mk/projects/petsitter/wiki/Normalization v02]
     356* Current version, based on version [https://develop.finki.ukim.mk/projects/petsitter/wiki/ERModel v03] of the ER model
     357* Added {{{service_id}}} to the right side of '''FD8''', because {{{booking_id}}} now determines the single service of the booking
     358* Removed '''FD14''' ({{{booking_id}}}, {{{service_id}}}) → ∅, which represented the BookingServices M:N relation; now the number of functional dependencies is reduced from 14 to 13
     359* {{{service_id}}} is no longer an attribute that appears only on the left side, so the candidate key is reduced from {{{ {admin_id, pet_id, service_id, review_id, payment_id} }}} to {{{ {admin_id, pet_id, review_id, payment_id} }}}
     360* Added {{{service_id}}} to the '''Bookings''' relation and removed the '''BookingServices''' relation; the schema is reduced from 14 to 13 relations and the decomposition from 13 to 12 binary splits
     361* The 3NF and BCNF analysis is extended to cover the new {{{service_id}}} attribute in '''Bookings''' and the schema again satisfies BCNF