Changes between Version 6 and Version 7 of Normalization


Ignore:
Timestamp:
05/28/26 17:16:25 (2 weeks ago)
Author:
181201
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • Normalization

    v6 v7  
    172172
    173173'''1. Loss-less Join Property Validation:'''
    174 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.
    175 
    176 (Let '''R_remainder''' denote the remainder relation after each split)
     174By 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.
     175
     176''(Let R_remainder denote the remainder relation after each split)''
     177
     178'''Initial State:'''
     179''R'' = {user_id, username, first_name, last_name, password, email, admin_id, owner_id, sitter_id, pettype_id, species, average_lifespan, needs_outdoor_walk, pet_id, pet_name, photo, age, special_needs, pet_description, service_id, service_type, service_description, booking_id, booking_status, date_from, date_to, address, review_id, rating, comment, payment_id, amount, payment_type}
    177180
    178181'''Split 1: Extracting Users (FD1)'''
    179182 * '''Decomposition:''' ''R'' is split into '''Users''' and '''R_remainder1'''.
     183 * '''Attributes in Users:''' {user_id, username, first_name, last_name, password, email}
     184 * '''Attributes in R_remainder1:''' {{{ {user_id, admin_id, owner_id, sitter_id, pettype_id, species, average_lifespan, needs_outdoor_walk, pet_id, pet_name, photo, age, special_needs, pet_description, service_id, service_type, service_description, booking_id, booking_status, date_from, date_to, address, review_id, rating, comment, payment_id, amount, payment_type} }}}
    180185 * '''Intersection:''' '''Users''' ∩ '''R_remainder1''' = {{{ {user_id} }}}
    181186 * '''Proof:''' {{{user_id}}} is the Primary Key of the '''Users''' table. The split is lossless.
    … …  
    183188'''Split 2: Extracting Admins (FD2)'''
    184189 * '''Decomposition:''' '''R_remainder1''' is split into '''Admins''' and '''R_remainder2'''.
     190 * '''Attributes in Admins:''' {admin_id, user_id}
     191 * '''Attributes in R_remainder2:''' {{{ {admin_id, owner_id, sitter_id, pettype_id, species, average_lifespan, needs_outdoor_walk, pet_id, pet_name, photo, age, special_needs, pet_description, service_id, service_type, service_description, booking_id, booking_status, date_from, date_to, address, review_id, rating, comment, payment_id, amount, payment_type} }}}
    185192 * '''Intersection:''' '''Admins''' ∩ '''R_remainder2''' = {{{ {admin_id} }}}
    186193 * '''Proof:''' {{{admin_id}}} is the Primary Key of the '''Admins''' table. The split is lossless.
    … …  
    188195'''Split 3: Extracting Pet Owners (FD3)'''
    189196 * '''Decomposition:''' '''R_remainder2''' is split into '''PetOwners''' and '''R_remainder3'''.
     197 * '''Attributes in PetOwners:''' {owner_id, user_id}
     198 * '''Attributes in R_remainder3:''' {{{ {admin_id, owner_id, sitter_id, pettype_id, species, average_lifespan, needs_outdoor_walk, pet_id, pet_name, photo, age, special_needs, pet_description, service_id, service_type, service_description, booking_id, booking_status, date_from, date_to, address, review_id, rating, comment, payment_id, amount, payment_type} }}}
    190199 * '''Intersection:''' '''PetOwners''' ∩ '''R_remainder3''' = {{{ {owner_id} }}}
    191200 * '''Proof:''' {{{owner_id}}} is the Primary Key of the '''PetOwners''' table. The split is lossless.
    … …  
    193202'''Split 4: Extracting Pet Sitters (FD4)'''
    194203 * '''Decomposition:''' '''R_remainder3''' is split into '''PetSitters''' and '''R_remainder4'''.
     204 * '''Attributes in PetSitters:''' {sitter_id, user_id}
     205 * '''Attributes in R_remainder4:''' {{{ {admin_id, owner_id, sitter_id, pettype_id, species, average_lifespan, needs_outdoor_walk, pet_id, pet_name, photo, age, special_needs, pet_description, service_id, service_type, service_description, booking_id, booking_status, date_from, date_to, address, review_id, rating, comment, payment_id, amount, payment_type} }}}
    195206 * '''Intersection:''' '''PetSitters''' ∩ '''R_remainder4''' = {{{ {sitter_id} }}}
    196207 * '''Proof:''' {{{sitter_id}}} is the Primary Key of the '''PetSitters''' table. The split is lossless.
    … …  
    198209'''Split 5: Extracting Pet Types (FD5)'''
    199210 * '''Decomposition:''' '''R_remainder4''' is split into '''PetTypes''' and '''R_remainder5'''.
     211 * '''Attributes in PetTypes:''' {pettype_id, species, average_lifespan, needs_outdoor_walk}
     212 * '''Attributes in R_remainder5:''' {{{ {admin_id, owner_id, sitter_id, pettype_id, pet_id, pet_name, photo, age, special_needs, pet_description, service_id, service_type, service_description, booking_id, booking_status, date_from, date_to, address, review_id, rating, comment, payment_id, amount, payment_type} }}}
    200213 * '''Intersection:''' '''PetTypes''' ∩ '''R_remainder5''' = {{{ {pettype_id} }}}
    201214 * '''Proof:''' {{{pettype_id}}} is the Primary Key of the '''PetTypes''' table. The split is lossless.
    … …  
    203216'''Split 6: Extracting Pets (FD6)'''
    204217 * '''Decomposition:''' '''R_remainder5''' is split into '''Pets''' and '''R_remainder6'''.
     218 * '''Attributes in Pets:''' {pet_id, pet_name, photo, age, special_needs, pet_description, owner_id, pettype_id}
     219 * '''Attributes in R_remainder6:''' {{{ {admin_id, owner_id, sitter_id, pet_id, service_id, service_type, service_description, booking_id, booking_status, date_from, date_to, address, review_id, rating, comment, payment_id, amount, payment_type} }}}
    205220 * '''Intersection:''' '''Pets''' ∩ '''R_remainder6''' = {{{ {pet_id} }}}
    206221 * '''Proof:''' {{{pet_id}}} is the Primary Key of the '''Pets''' table. The split is lossless.
    … …  
    208223'''Split 7: Extracting Services (FD7)'''
    209224 * '''Decomposition:''' '''R_remainder6''' is split into '''Services''' and '''R_remainder7'''.
     225 * '''Attributes in Services:''' {service_id, service_type, service_description}
     226 * '''Attributes in R_remainder7:''' {{{ {admin_id, owner_id, sitter_id, pet_id, service_id, booking_id, booking_status, date_from, date_to, address, review_id, rating, comment, payment_id, amount, payment_type} }}}
    210227 * '''Intersection:''' '''Services''' ∩ '''R_remainder7''' = {{{ {service_id} }}}
    211228 * '''Proof:''' {{{service_id}}} is the Primary Key of the '''Services''' table. The split is lossless.
    … …  
    213230'''Split 8: Extracting Bookings (FD8)'''
    214231 * '''Decomposition:''' '''R_remainder7''' is split into '''Bookings''' and '''R_remainder8'''.
     232 * '''Attributes in Bookings:''' {booking_id, booking_status, date_from, date_to, address, owner_id, sitter_id}
     233 * '''Attributes in R_remainder8:''' {{{ {admin_id, sitter_id, pet_id, service_id, booking_id, review_id, rating, comment, payment_id, amount, payment_type} }}}
    215234 * '''Intersection:''' '''Bookings''' ∩ '''R_remainder8''' = {{{ {booking_id} }}}
    216235 * '''Proof:''' {{{booking_id}}} is the Primary Key of the '''Bookings''' table. The split is lossless.
    … …  
    218237'''Split 9: Extracting Reviews (FD9)'''
    219238 * '''Decomposition:''' '''R_remainder8''' is split into '''Reviews''' and '''R_remainder9'''.
     239 * '''Attributes in Reviews:''' {review_id, rating, comment, booking_id}
     240 * '''Attributes in R_remainder9:''' {{{ {admin_id, sitter_id, pet_id, service_id, booking_id, payment_id, amount, payment_type} }}}
    220241 * '''Intersection:''' '''Reviews''' ∩ '''R_remainder9''' = {{{ {review_id} }}}
    221242 * '''Proof:''' {{{review_id}}} is the Primary Key of the '''Reviews''' table. The split is lossless.
    … …  
    223244'''Split 10: Extracting Payments (FD10)'''
    224245 * '''Decomposition:''' '''R_remainder9''' is split into '''Payments''' and '''R_remainder10'''.
     246 * '''Attributes in Payments:''' {payment_id, amount, payment_type, booking_id}
     247 * '''Attributes in R_remainder10:''' {{{ {admin_id, sitter_id, pet_id, service_id, booking_id} }}}
    225248 * '''Intersection:''' '''Payments''' ∩ '''R_remainder10''' = {{{ {payment_id} }}}
    226249 * '''Proof:''' {{{payment_id}}} is the Primary Key of the '''Payments''' table. The split is lossless.
    227250
    228251'''Splits 11-13: Extracting M:N Relations/Junctions (FD11-FD14)'''
    229 
    230 The final remainder relation ('''R_remainder10''') contains only the composite keys representing the Many-to-Many relationships ('''AdminManagement''', '''BookingPets''', '''SitterServices''', '''BookingServices'''). Because these tables consist ''entirely'' of their composite primary keys, any further separation will trivially satisfy Heath's Theorem.
     252The final remainder relation ('''R_remainder10''') contains only the composite keys representing the Many-to-Many relationships:
     253 * '''AdminManagement:''' {admin_id, user_id}
     254 * '''BookingPets:''' {booking_id, pet_id}
     255 * '''SitterServices:''' {sitter_id, service_id}
     256 * '''BookingServices:''' {booking_id, service_id}
     257
     258Because these final tables consist ''entirely'' of their composite primary keys, any further binary separation along these boundaries trivially satisfies Heath's Theorem.
    231259
    232260'''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.