= Normalization =

== Initial de-normalized relation and functional dependencies ==

=== Global set of attributes ===
Single unified de-normalized relation that includes all attributes from the ER model. It is important that there are no duplicate attribute names.

'''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

'''}'''

=== Functional dependencies ===

'''FD1:''' {{{user_id}}} → {{{username}}}, {{{first_name}}}, {{{last_name}}}, {{{password}}}, {{{email}}}

'''FD2:''' {{{admin_id}}} → {{{user_id}}}

'''FD3:''' {{{owner_id}}} → {{{user_id}}}

'''FD4:''' {{{sitter_id}}} → {{{user_id}}}

'''FD5:''' {{{pettype_id}}} → {{{species}}}, {{{average_lifespan}}}, {{{needs_outdoor_walk}}}

'''FD6:''' {{{pet_id}}} → {{{pet_name}}}, {{{photo}}}, {{{age}}}, {{{special_needs}}}, {{{pet_description}}}, {{{owner_id}}}, {{{pettype_id}}}

'''FD7:''' {{{service_id}}} → {{{service_type}}}, {{{service_description}}}

'''FD8:''' {{{booking_id}}} → {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}}, {{{owner_id}}}, {{{sitter_id}}}

'''FD9:''' {{{review_id}}} → {{{rating}}}, {{{comment}}}, {{{booking_id}}}

'''FD10:''' {{{payment_id}}} → {{{amount}}}, {{{payment_type}}}, {{{booking_id}}}

'''FD11:''' ({{{admin_id}}}, {{{user_id}}}) → ∅ (represents AdminManagement M:N)

'''FD12:''' ({{{booking_id}}}, {{{pet_id}}}) → ∅ (represents BookingPets M:N)

'''FD13:''' ({{{sitter_id}}}, {{{service_id}}}) → ∅ (represents SitterServices M:N)

'''FD14:''' ({{{booking_id}}}, {{{service_id}}}) → ∅ (represents BookingServices M:N)

== Candidate keys and primary key selection ==

=== Determination of Candidate Keys ===
To find a candidate key, we must find a minimal set of attributes whose closure contains all attributes of the relation. We begin by classifying all attributes based on where they appear in the Functional Dependencies.

=== Attribute Classification (Left / Right Side) ===
|| '''Attribute''' || '''Left Side''' || '''Right Side''' || '''Classification''' ||
|| '''admin_id''' || ✓ (FD2, FD11) || ✗ || '''Left only''' ||
|| '''pet_id''' || ✓ (FD6, FD12) || ✗ || '''Left only''' ||
|| '''service_id''' || ✓ (FD7, FD13, FD14) || ✗ || '''Left only''' ||
|| '''review_id''' || ✓ (FD9) || ✗ || '''Left only''' ||
|| '''payment_id''' || ✓ (FD10) || ✗ || '''Left only''' ||
|| {{{user_id}}} || ✓ (FD1, FD11) || ✓ (FD2, FD3, FD4) || Both ||
|| {{{owner_id}}} || ✓ (FD3) || ✓ (FD6, FD8) || Both ||
|| {{{sitter_id}}} || ✓ (FD4, FD13) || ✓ (FD8) || Both ||
|| {{{pettype_id}}} || ✓ (FD5) || ✓ (FD6) || Both ||
|| {{{booking_id}}} || ✓ (FD8, FD12, FD14) || ✓ (FD9, FD10) || Both ||
|| {{{username}}}, {{{first_name}}}, {{{last_name}}}, {{{password}}}, {{{email}}} || ✗ || ✓ (FD1) || Right only ||
|| {{{species}}}, {{{average_lifespan}}}, {{{needs_outdoor_walk}}} || ✗ || ✓ (FD5) || Right only ||
|| {{{pet_name}}}, {{{photo}}}, {{{age}}}, {{{special_needs}}}, {{{pet_description}}} || ✗ || ✓ (FD6) || Right only ||
|| {{{service_type}}}, {{{service_description}}} || ✗ || ✓ (FD7) || Right only ||
|| {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}} || ✗ || ✓ (FD8) || Right only ||
|| {{{rating}}}, {{{comment}}} || ✗ || ✓ (FD9) || Right only ||
|| {{{amount}}}, {{{payment_type}}} || ✗ || ✓ (FD10) || Right only ||

=== Attributes That Appear ONLY on the Left Side ===
According to relational theory, attributes that appear ''only'' on the left side of functional dependencies can never be derived from any other attribute. Therefore, they '''must''' be part of every candidate key:
 * '''admin_id'''
 * '''pet_id'''
 * '''service_id'''
 * '''review_id'''
 * '''payment_id'''

=== Closure Computation ===
'''Step 1:''' We start with our mandatory attributes {{{ {admin_id, pet_id, service_id, review_id, payment_id} }}} and compute the mathematical closure:

{{{ {admin_id, pet_id, service_id, review_id, payment_id}⁺ }}}:
 * '''From FD2''' ({{{admin_id}}} → {{{user_id}}}): We obtain {{{user_id}}}
 * '''From FD1''' ({{{user_id}}} → {{{username}}}, {{{first_name}}}...): We obtain {{{username, first_name, last_name, password, email}}}
 * '''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}}}
 * '''From FD5''' ({{{pettype_id}}} → {{{species}}}...): We obtain {{{species, average_lifespan, needs_outdoor_walk}}}
 * '''From FD7''' ({{{service_id}}} → {{{service_type}}}...): We obtain {{{service_type, service_description}}}
 * '''From FD9''' ({{{review_id}}} → {{{rating}}}, {{{comment}}}, {{{booking_id}}}): We obtain {{{rating, comment, booking_id}}}
 * '''From FD8''' ({{{booking_id}}} → {{{booking_status}}}... {{{sitter_id}}}): We obtain {{{booking_status, date_from, date_to, address, sitter_id}}}
 * '''From FD10''' ({{{payment_id}}} → {{{amount}}}, {{{payment_type}}}, {{{booking_id}}}): We obtain {{{amount, payment_type}}} ({{{booking_id}}} is already in closure)
 * '''From FD3 & FD4:''' {{{owner_id}}} and {{{sitter_id}}} map to {{{user_id}}}, which is already in the closure.
 * '''From FD11-FD14:''' All composite pairings (e.g., {{{booking_id}}} and {{{pet_id}}}) are already present in the closure, satisfying the M:N relations.

'''Closure = Universal_Relation ✓''' (all 33 attributes are successfully derived)

=== Minimality Check ===
To formally prove this key is minimal, we test proper subsets of '''K = {admin_id, pet_id, service_id, review_id, payment_id}''':

|| '''Subset''' || '''Closure Equals Universal_Relation?''' || '''Justification''' ||
|| '''K − {admin_id}''' || ✗ NO || Cannot derive {{{admin_id}}}. ||
|| '''K − {pet_id}''' || ✗ NO || Cannot derive pet attributes ({{{pet_name, photo, age, special_needs, pet_description}}}). ||
|| '''K − {service_id}''' || ✗ NO || Cannot derive service attributes ({{{service_type, service_description}}}). ||
|| '''K − {review_id}''' || ✗ NO || Cannot derive review attributes ({{{review_id, rating, comment}}}). ||
|| '''K − {payment_id}''' || ✗ NO || Cannot derive payment attributes ({{{payment_id, amount, payment_type}}}). ||

'''Conclusion:''' K = {admin_id, pet_id, service_id, review_id, payment_id} is minimal and is the strictly mathematically correct candidate key.

=== Choice of Primary Key ===
'''Chosen Primary Key:''' {{{ {admin_id, pet_id, service_id, review_id, payment_id} }}}

'''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.

=== Current Normal Form Status ===
Before decomposition, the universal relation '''R''' is in '''1NF'''. It satisfies 1NF because all attributes contain atomic values and there are no repeating groups. However, it violates 2NF due to severe partial dependencies on the composite primary key.

== Step-by-step decomposition to highest possible normal form ==

=== 1. Decomposition to 2NF ===

'''Relation analyzed:''' The universal de-normalized relation '''R'''.

'''Issues with higher normal forms:''' R violates 2NF because non-prime attributes are partially dependent on components of the composite primary key. For example, {{{pet_name}}} depends ONLY on {{{pet_id}}}, not on the entire composite key '''K'''.

'''Action taken:''' We decompose R into smaller relations by grouping attributes based on their exact determinants (eliminating partial dependencies).

'''Relations obtained after 2NF decomposition:'''

'''Users''' ({{{user_id}}}, {{{username}}}, {{{first_name}}}, {{{last_name}}}, {{{password}}}, {{{email}}})

'''Admins''' ({{{admin_id}}}, {{{user_id}}})

'''PetOwners''' ({{{owner_id}}}, {{{user_id}}})

'''PetSitters''' ({{{sitter_id}}}, {{{user_id}}})

'''PetTypes''' ({{{pettype_id}}}, {{{species}}}, {{{average_lifespan}}}, {{{needs_outdoor_walk}}})

'''Pets''' ({{{pet_id}}}, {{{pet_name}}}, {{{photo}}}, {{{age}}}, {{{special_needs}}}, {{{pet_description}}}, {{{owner_id}}}, {{{pettype_id}}})

'''Services''' ({{{service_id}}}, {{{service_type}}}, {{{service_description}}})

'''Bookings''' ({{{booking_id}}}, {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}}, {{{owner_id}}}, {{{sitter_id}}})

'''Reviews''' ({{{review_id}}}, {{{rating}}}, {{{comment}}}, {{{booking_id}}})

'''Payments''' ({{{payment_id}}}, {{{amount}}}, {{{payment_type}}}, {{{booking_id}}})

'''AdminManagement''' ({{{admin_id}}}, {{{user_id}}})

'''BookingPets''' ({{{booking_id}}}, {{{pet_id}}})

'''SitterServices''' ({{{sitter_id}}}, {{{service_id}}})

'''BookingServices''' ({{{booking_id}}}, {{{service_id}}})

'''Validation of 2NF Decomposition:'''

'''1. Loss-less Join Property:''' 
By definition (Heath's Theorem), a decomposition of relation ''R'' into ''R1'' and ''R2'' is lossless if the common attributes (''R1'' ∩ ''R2'') form a superkey for either ''R1'' or ''R2''. 
Our 14 relations were not created in a single split, but through '''successive binary decompositions'''. 
 * For example, in the first step, ''R'' was decomposed into ''R_Users'' and ''R_Remainder'' based on FD1. The intersection of these two relations is {{{user_id}}}. Because {{{user_id}}} is the primary key of ''R_Users'', the functional dependency {{{user_id → username, first_name, last_name, password, email}}} is preserved, proving this specific binary split is lossless. 
 * In another step, the remainder was split into ''R_Pets'' and a new remainder based on FD6. The intersection is {{{pet_id}}}. Since {{{pet_id}}} is the primary key of ''R_Pets'', this split is also lossless.
 * By recursively applying this exact binary splitting logic along the boundaries of FD2 through FD14, every single decomposition step shared a primary key with the remainder relation. Therefore, the final 14-table schema is strictly lossless.

'''2. Dependency Preservation:'''
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). 
Because we explicitly created our relations based on the exact determinants of our FDs, every single functional dependency is fully localized within a single table. 
 * 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. 
 * Similarly, FD7 ({{{service_id → service_type, service_description}}}) is entirely contained within the '''Services''' table.
Since all 14 original FDs are preserved natively inside the 14 new relations, the decomposition is strictly dependency preserving.

=== Step 2: Decomposition to 3NF ===

'''Relations analyzed:''' All 14 relations obtained from the 2NF decomposition.

'''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.

'''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.

* '''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.
* '''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.
* '''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.
* '''In Junction Tables (BookingPets, AdminManagement):''' These relations consist purely of composite primary keys with zero non-prime attributes, automatically satisfying 3NF.

'''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.

'''Status:''' All 14 relations naturally satisfy '''3NF'''.
=== 3. Decomposition to BCNF ===

'''Relations analyzed:''' All 14 relations currently in 3NF.

'''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.

'''Action taken:''' We evaluate the left side (determinant) of every functional dependency within all 14 relations:

In '''Users''', {{{user_id}}} is a superkey.

In '''Admins''', {{{admin_id}}} is a superkey.

In '''PetOwners''', {{{owner_id}}} is a superkey.

In '''PetSitters''', {{{sitter_id}}} is a superkey.

In '''PetTypes''', {{{pettype_id}}} is a superkey.

In '''Pets''', {{{pet_id}}} is a superkey.

In '''Services''', {{{service_id}}} is a superkey.

In '''Bookings''', {{{booking_id}}} is a superkey.

In '''Reviews''', {{{review_id}}} is a superkey.

In '''Payments''', {{{payment_id}}} is a superkey.

In '''AdminManagement''', the composite key ({{{admin_id}}}, {{{user_id}}}) is the only determinant, meaning it is trivially a superkey.

In '''BookingPets''', the composite key ({{{booking_id}}}, {{{pet_id}}}) is the only determinant, meaning it is trivially a superkey.

In '''SitterServices''', the composite key ({{{sitter_id}}}, {{{service_id}}}) is the only determinant, meaning it is trivially a superkey.

In '''BookingServices''', the composite key ({{{booking_id}}}, {{{service_id}}}) is the only determinant, meaning it is trivially a superkey.

'''Result:''' In every single relation, the determinant is a candidate/superkey.

'''Status:''' All 14 relations naturally satisfy '''BCNF'''. The decomposition process is complete.

== Final result and discussion ==

=== Final normalized relational design ===
The final database schema operates in strict BCNF with the following 14 relations:

'''Users''' ({{{user_id}}}, {{{username}}}, {{{first_name}}}, {{{last_name}}}, {{{password}}}, {{{email}}})

'''Admins''' ({{{admin_id}}}, {{{user_id}}})

'''PetOwners''' ({{{owner_id}}}, {{{user_id}}})

'''PetSitters''' ({{{sitter_id}}}, {{{user_id}}})

'''PetTypes''' ({{{pettype_id}}}, {{{species}}}, {{{average_lifespan}}}, {{{needs_outdoor_walk}}})

'''Pets''' ({{{pet_id}}}, {{{pet_name}}}, {{{photo}}}, {{{age}}}, {{{special_needs}}}, {{{pet_description}}}, {{{owner_id}}}, {{{pettype_id}}})

'''Services''' ({{{service_id}}}, {{{service_type}}}, {{{service_description}}})

'''Bookings''' ({{{booking_id}}}, {{{booking_status}}}, {{{date_from}}}, {{{date_to}}}, {{{address}}}, {{{owner_id}}}, {{{sitter_id}}})

'''Reviews''' ({{{review_id}}}, {{{rating}}}, {{{comment}}}, {{{booking_id}}})

'''Payments''' ({{{payment_id}}}, {{{amount}}}, {{{payment_type}}}, {{{booking_id}}})

'''AdminManagement''' ({{{admin_id}}}, {{{user_id}}})

'''BookingPets''' ({{{booking_id}}}, {{{pet_id}}})

'''SitterServices''' ({{{sitter_id}}}, {{{service_id}}})

'''BookingServices''' ({{{booking_id}}}, {{{service_id}}})

=== Discussion - compare with Phase 2 ===
With completing the normalization process up to BCNF, we have proven that the resulting schema is identical to the logical design created in Phase 2.