Changes between Initial Version and Version 1 of Normalization

Timestamp:

07/03/26 12:48:19 (9 days ago)

Author:

223091

Comment:

--

Normalization

@@ +1 @@
+= Normalization =
+
+This page documents Phase P5 of the Room Reservation System project. The goal of this phase is to check the database model using formal normalization methods and to improve the model if typical problems of un-normalized designs are found.
+
+The normalization process starts from one theoretical de-normalized relation that contains all attributes from the model. From that relation, functional dependencies, candidate keys, and normal forms are analyzed. The relation is then decomposed step by step to the highest possible normal form while preserving functional dependencies and loss-less join properties.
+
+== De-normalized database form ==
+
+=== Initial de-normalized relation ===
+
+The process starts from a single unified de-normalized relation. This relation is not implemented in the database. It is used only as a formal starting point for the normalization process.
+
+The relation contains data about reservations, rooms, buildings, users, equipment, requested equipment, equipment assigned to rooms, and approvals. Attribute names are made globally unique in order to avoid duplicate attribute names.
+
+{{{
+R0(
+reservation_id,
+reservation_date,
+start_time,
+end_time,
+status,
+
+```
+room_id,
+room_code,
+room_capacity,
+room_type,
+
+building_id,
+building_name,
+building_address,
+
+requester_user_id,
+requester_username,
+requester_email,
+requester_full_name,
+requester_role,
+
+requested_equipment_id,
+requested_equipment_name,
+requested_equipment_stock_quantity,
+requested_quantity,
+
+room_equipment_id,
+room_equipment_name,
+room_equipment_stock_quantity,
+room_equipment_quantity,
+
+approval_id,
+approver_user_id,
+approver_username,
+approver_email,
+approver_full_name,
+approver_role,
+
+decision,
+decision_time,
+note
+```
+
+)
+}}}
+
+In this theoretical relation, the attributes ''requested_equipment_id'' and ''room_equipment_id'' both refer to equipment items, but they are named differently in the de-normalized form because the same entity type appears in two different roles. During normalization, these two groups are merged into one final ''equipment'' relation.
+
+=== Functional dependencies ===
+
+The following functional dependencies are valid in the de-normalized relation. For readability, they are written in grouped form. Each grouped dependency can be split into dependencies with one attribute on the right-hand side.
+
+{{{
+reservation_id -> reservation_date, start_time, end_time, status, room_id, requester_user_id
+
+room_id -> room_code, room_capacity, room_type, building_id
+room_code -> room_id
+
+building_id -> building_name, building_address
+building_name, building_address -> building_id
+
+requester_user_id -> requester_username, requester_email, requester_full_name, requester_role
+requester_username -> requester_user_id, requester_email, requester_full_name, requester_role
+requester_email -> requester_user_id, requester_username, requester_full_name, requester_role
+
+approver_user_id -> approver_username, approver_email, approver_full_name, approver_role
+approver_username -> approver_user_id, approver_email, approver_full_name, approver_role
+approver_email -> approver_user_id, approver_username, approver_full_name, approver_role
+
+requested_equipment_id -> requested_equipment_name, requested_equipment_stock_quantity
+requested_equipment_name -> requested_equipment_id, requested_equipment_stock_quantity
+
+room_equipment_id -> room_equipment_name, room_equipment_stock_quantity
+room_equipment_name -> room_equipment_id, room_equipment_stock_quantity
+
+reservation_id, requested_equipment_id -> requested_quantity
+room_id, room_equipment_id -> room_equipment_quantity
+
+approval_id -> reservation_id, approver_user_id, decision, decision_time, note
+reservation_id -> approval_id, approver_user_id, decision, decision_time, note
+}}}
+
+The dependency ''reservation_id -> approval_id, approver_user_id, decision, decision_time, note'' is valid for reservations that already have an approval decision. A reservation may still be pending, so the approval-related values may be missing until an approval is created. The business rule is that one reservation can have at most one approval record.
+
+=== Candidate keys and primary key ===
+
+The de-normalized relation contains information about one reservation, the equipment requested in that reservation, and the equipment assigned to the selected room. Therefore, a complete row in the de-normalized relation is identified by a combination of the reservation and the two equipment-role identifiers.
+
+Candidate keys for the de-normalized relation include:
+
+{{{
+K1 = (reservation_id, requested_equipment_id, room_equipment_id)
+K2 = (reservation_id, requested_equipment_name, room_equipment_id)
+K3 = (reservation_id, requested_equipment_id, room_equipment_name)
+K4 = (reservation_id, requested_equipment_name, room_equipment_name)
+}}}
+
+The selected primary key for the de-normalized relation is:
+
+{{{
+(reservation_id, requested_equipment_id, room_equipment_id)
+}}}
+
+This key is selected because it uses stable numeric identifiers instead of descriptive names.
+
+=== Normal form of the de-normalized relation ===
+
+The de-normalized relation is in 1NF because all attributes contain atomic values. There are no repeating groups inside one attribute, and equipment occurrences are represented as separate rows.
+
+However, the relation is not in 2NF because there are partial dependencies on parts of the composite key. Examples:
+
+{{{
+reservation_id -> reservation_date, start_time, end_time, status, room_id, requester_user_id
+
+requested_equipment_id -> requested_equipment_name, requested_equipment_stock_quantity
+
+room_equipment_id -> room_equipment_name, room_equipment_stock_quantity
+}}}
+
+These dependencies show that some non-key attributes depend only on part of the composite key, not on the whole key. Because of this, the relation is not in 2NF. Consequently, it is also not in 3NF or BCNF.
+
+== 1NF decomposition ==
+
+The first normal form requires that all attribute values are atomic and that repeating groups are removed.
+
+The relation R0 is already represented with atomic values. Multiple requested equipment items and multiple equipment items assigned to a room are represented as separate rows instead of being stored as lists in one attribute.
+
+Therefore, no additional decomposition is required for 1NF.
+
+The relation after this step is still:
+
+{{{
+R0(
+reservation_id,
+reservation_date,
+start_time,
+end_time,
+status,
+room_id,
+room_code,
+room_capacity,
+room_type,
+building_id,
+building_name,
+building_address,
+requester_user_id,
+requester_username,
+requester_email,
+requester_full_name,
+requester_role,
+requested_equipment_id,
+requested_equipment_name,
+requested_equipment_stock_quantity,
+requested_quantity,
+room_equipment_id,
+room_equipment_name,
+room_equipment_stock_quantity,
+room_equipment_quantity,
+approval_id,
+approver_user_id,
+approver_username,
+approver_email,
+approver_full_name,
+approver_role,
+decision,
+decision_time,
+note
+)
+}}}
+
+The relation is in 1NF, but it is not in 2NF because of partial dependencies.
+
+== 2NF decomposition ==
+
+A relation is in 2NF if it is in 1NF and every non-prime attribute is fully functionally dependent on the whole candidate key.
+
+The relation R0 violates 2NF because many attributes depend only on part of the composite key. For example, reservation data depends only on ''reservation_id'', requested equipment data depends only on ''requested_equipment_id'', and room equipment data depends only on ''room_equipment_id''.
+
+The first decomposition removes these partial dependencies.
+
+=== Decomposition step ===
+
+The following relations are obtained:
+
+{{{
+R1_reservations(
+reservation_id,
+reservation_date,
+start_time,
+end_time,
+status,
+room_id,
+requester_user_id
+)
+}}}
+
+Key:
+
+{{{
+reservation_id
+}}}
+
+Functional dependencies preserved:
+
+{{{
+reservation_id -> reservation_date, start_time, end_time, status, room_id, requester_user_id
+}}}
+
+{{{
+R1_rooms(
+room_id,
+room_code,
+room_capacity,
+room_type,
+building_id,
+building_name,
+building_address
+)
+}}}
+
+Keys:
+
+{{{
+room_id
+room_code
+}}}
+
+Functional dependencies preserved:
+
+{{{
+room_id -> room_code, room_capacity, room_type, building_id, building_name, building_address
+room_code -> room_id
+}}}
+
+{{{
+R1_requester_users(
+requester_user_id,
+requester_username,
+requester_email,
+requester_full_name,
+requester_role
+)
+}}}
+
+Keys:
+
+{{{
+requester_user_id
+requester_username
+requester_email
+}}}
+
+Functional dependencies preserved:
+
+{{{
+requester_user_id -> requester_username, requester_email, requester_full_name, requester_role
+requester_username -> requester_user_id, requester_email, requester_full_name, requester_role
+requester_email -> requester_user_id, requester_username, requester_full_name, requester_role
+}}}
+
+{{{
+R1_approver_users(
+approver_user_id,
+approver_username,
+approver_email,
+approver_full_name,
+approver_role
+)
+}}}
+
+Keys:
+
+{{{
+approver_user_id
+approver_username
+approver_email
+}}}
+
+Functional dependencies preserved:
+
+{{{
+approver_user_id -> approver_username, approver_email, approver_full_name, approver_role
+approver_username -> approver_user_id, approver_email, approver_full_name, approver_role
+approver_email -> approver_user_id, approver_username, approver_full_name, approver_role
+}}}
+
+{{{
+R1_requested_equipment(
+requested_equipment_id,
+requested_equipment_name,
+requested_equipment_stock_quantity
+)
+}}}
+
+Keys:
+
+{{{
+requested_equipment_id
+requested_equipment_name
+}}}
+
+Functional dependencies preserved:
+
+{{{
+requested_equipment_id -> requested_equipment_name, requested_equipment_stock_quantity
+requested_equipment_name -> requested_equipment_id, requested_equipment_stock_quantity
+}}}
+
+{{{
+R1_room_equipment_item(
+room_equipment_id,
+room_equipment_name,
+room_equipment_stock_quantity
+)
+}}}
+
+Keys:
+
+{{{
+room_equipment_id
+room_equipment_name
+}}}
+
+Functional dependencies preserved:
+
+{{{
+room_equipment_id -> room_equipment_name, room_equipment_stock_quantity
+room_equipment_name -> room_equipment_id, room_equipment_stock_quantity
+}}}
+
+{{{
+R1_reservation_equipment(
+reservation_id,
+requested_equipment_id,
+requested_quantity
+)
+}}}
+
+Key:
+
+{{{
+(reservation_id, requested_equipment_id)
+}}}
+
+Functional dependency preserved:
+
+{{{
+reservation_id, requested_equipment_id -> requested_quantity
+}}}
+
+{{{
+R1_room_equipment(
+room_id,
+room_equipment_id,
+room_equipment_quantity
+)
+}}}
+
+Key:
+
+{{{
+(room_id, room_equipment_id)
+}}}
+
+Functional dependency preserved:
+
+{{{
+room_id, room_equipment_id -> room_equipment_quantity
+}}}
+
+{{{
+R1_approvals(
+approval_id,
+reservation_id,
+approver_user_id,
+decision,
+decision_time,
+note
+)
+}}}
+
+Keys:
+
+{{{
+approval_id
+reservation_id
+}}}
+
+Functional dependencies preserved:
+
+{{{
+approval_id -> reservation_id, approver_user_id, decision, decision_time, note
+reservation_id -> approval_id, approver_user_id, decision, decision_time, note
+}}}
+
+=== Loss-less join and dependency preservation ===
+
+The decomposition to 2NF is loss-less because every decomposition step uses a determinant that is a key in one of the resulting relations. For example, reservation details are separated using ''reservation_id'', room details are separated using ''room_id'', and equipment details are separated using equipment identifiers.
+
+The functional dependencies are preserved because every dependency from the original relation is represented in one of the decomposed relations.
+
+After this step, the relations are in 2NF. However, some relations are still not in 3NF because transitive dependencies still exist.
+
+== 3NF decomposition ==
+
+A relation is in 3NF if it is in 2NF and no non-prime attribute depends transitively on a candidate key.
+
+The relation ''R1_rooms'' still contains a transitive dependency:
+
+{{{
+room_id -> building_id
+building_id -> building_name, building_address
+}}}
+
+Therefore:
+
+{{{
+room_id -> building_name, building_address
+}}}
+
+This means that building data depends on ''room_id'' only through ''building_id''. To remove this transitive dependency, building data is decomposed into a separate relation.
+
+=== Decomposition of room and building data ===
+
+The relation:
+
+{{{
+R1_rooms(
+room_id,
+room_code,
+room_capacity,
+room_type,
+building_id,
+building_name,
+building_address
+)
+}}}
+
+is decomposed into:
+
+{{{
+buildings(
+building_id,
+name,
+address
+)
+}}}
+
+Keys:
+
+{{{
+building_id
+(name, address)
+}}}
+
+Functional dependencies:
+
+{{{
+building_id -> name, address
+name, address -> building_id
+}}}
+
+{{{
+rooms(
+room_id,
+building_id,
+room_code,
+capacity,
+type
+)
+}}}
+
+Keys:
+
+{{{
+room_id
+room_code
+}}}
+
+Functional dependencies:
+
+{{{
+room_id -> building_id, room_code, capacity, type
+room_code -> room_id
+}}}
+
+This removes the transitive dependency between rooms and building attributes.
+
+=== Merging user roles ===
+
+The 2NF decomposition produced separate requester and approver user relations because the same entity type appeared in different roles in the de-normalized relation.
+
+However, both groups represent the same real entity set: users of the system. Therefore, they are merged into one relation:
+
+{{{
+users(
+user_id,
+username,
+email,
+full_name,
+role
+)
+}}}
+
+Keys:
+
+{{{
+user_id
+username
+email
+}}}
+
+Functional dependencies:
+
+{{{
+user_id -> username, email, full_name, role
+username -> user_id, email, full_name, role
+email -> user_id, username, full_name, role
+}}}
+
+In the final schema, ''reservations.user_id'' references the requester, while ''approvals.approver_id'' references the user who made the approval decision.
+
+=== Merging equipment roles ===
+
+The 2NF decomposition produced separate requested-equipment and room-equipment item relations because equipment appeared in two different roles in the de-normalized relation.
+
+However, both groups represent the same entity set: equipment types. Therefore, they are merged into one relation:
+
+{{{
+equipment(
+equipment_id,
+name,
+stock_quantity
+)
+}}}
+
+Keys:
+
+{{{
+equipment_id
+name
+}}}
+
+Functional dependencies:
+
+{{{
+equipment_id -> name, stock_quantity
+name -> equipment_id, stock_quantity
+}}}
+
+The relation ''room_equipment'' represents equipment assigned to rooms, while ''reservation_equipment'' represents equipment requested as part of reservations.
+
+=== Final relations after 3NF decomposition ===
+
+After removing partial and transitive dependencies, the resulting relations are:
+
+{{{
+buildings(
+building_id,
+name,
+address
+)
+}}}
+
+{{{
+rooms(
+room_id,
+building_id,
+room_code,
+capacity,
+type
+)
+}}}
+
+{{{
+equipment(
+equipment_id,
+name,
+stock_quantity
+)
+}}}
+
+{{{
+room_equipment(
+room_id,
+equipment_id,
+quantity
+)
+}}}
+
+{{{
+users(
+user_id,
+username,
+email,
+full_name,
+role
+)
+}}}
+
+{{{
+reservations(
+reservation_id,
+room_id,
+user_id,
+reservation_date,
+start_time,
+end_time,
+status
+)
+}}}
+
+{{{
+reservation_equipment(
+reservation_id,
+equipment_id,
+requested_quantity
+)
+}}}
+
+{{{
+approvals(
+approval_id,
+reservation_id,
+approver_id,
+decision,
+decision_time,
+note
+)
+}}}
+
+=== Loss-less join and dependency preservation ===
+
+The 3NF decomposition is loss-less because each decomposition separates attributes based on a functional dependency where the determinant becomes a key in one of the resulting relations.
+
+Examples:
+
+{{{
+building_id -> name, address
+}}}
+
+is preserved in:
+
+{{{
+buildings(building_id, name, address)
+}}}
+
+and the relation can be joined back with:
+
+{{{
+rooms(room_id, building_id, room_code, capacity, type)
+}}}
+
+using the foreign key ''building_id''.
+
+Similarly, user data and equipment data are separated into their own relations and referenced by identifiers from reservations, approvals, room equipment, and reservation equipment.
+
+The decomposition preserves the functional dependencies because each important dependency is represented inside one of the final relations.
+
+== BCNF if possible ==
+
+A relation is in BCNF if for every non-trivial functional dependency X -> Y, X is a superkey.
+
+The final relations are checked for BCNF as follows.
+
+=== buildings ===
+
+Relation:
+
+{{{
+buildings(building_id, name, address)
+}}}
+
+Functional dependencies:
+
+{{{
+building_id -> name, address
+name, address -> building_id
+}}}
+
+Candidate keys:
+
+{{{
+building_id
+(name, address)
+}}}
+
+All determinants are candidate keys, so the relation is in BCNF.
+
+=== rooms ===
+
+Relation:
+
+{{{
+rooms(room_id, building_id, room_code, capacity, type)
+}}}
+
+Functional dependencies:
+
+{{{
+room_id -> building_id, room_code, capacity, type
+room_code -> room_id
+}}}
+
+Candidate keys:
+
+{{{
+room_id
+room_code
+}}}
+
+All determinants are candidate keys, so the relation is in BCNF.
+
+=== equipment ===
+
+Relation:
+
+{{{
+equipment(equipment_id, name, stock_quantity)
+}}}
+
+Functional dependencies:
+
+{{{
+equipment_id -> name, stock_quantity
+name -> equipment_id, stock_quantity
+}}}
+
+Candidate keys:
+
+{{{
+equipment_id
+name
+}}}
+
+All determinants are candidate keys, so the relation is in BCNF.
+
+=== room_equipment ===
+
+Relation:
+
+{{{
+room_equipment(room_id, equipment_id, quantity)
+}}}
+
+Functional dependency:
+
+{{{
+room_id, equipment_id -> quantity
+}}}
+
+Candidate key:
+
+{{{
+(room_id, equipment_id)
+}}}
+
+The determinant is the candidate key, so the relation is in BCNF.
+
+=== users ===
+
+Relation:
+
+{{{
+users(user_id, username, email, full_name, role)
+}}}
+
+Functional dependencies:
+
+{{{
+user_id -> username, email, full_name, role
+username -> user_id, email, full_name, role
+email -> user_id, username, full_name, role
+}}}
+
+Candidate keys:
+
+{{{
+user_id
+username
+email
+}}}
+
+All determinants are candidate keys, so the relation is in BCNF.
+
+=== reservations ===
+
+Relation:
+
+{{{
+reservations(reservation_id, room_id, user_id, reservation_date, start_time, end_time, status)
+}}}
+
+Functional dependencies:
+
+{{{
+reservation_id -> room_id, user_id, reservation_date, start_time, end_time, status
+room_id, reservation_date, start_time, end_time -> reservation_id
+}}}
+
+Candidate keys:
+
+{{{
+reservation_id
+(room_id, reservation_date, start_time, end_time) for room-based reservations
+}}}
+
+The determinant ''reservation_id'' is the primary key. The determinant ''(room_id, reservation_date, start_time, end_time)'' is an alternative key for room-based reservations. Therefore, the relation is in BCNF.
+
+The attribute ''room_id'' is optional because equipment-only reservations are allowed.
+
+=== reservation_equipment ===
+
+Relation:
+
+{{{
+reservation_equipment(reservation_id, equipment_id, requested_quantity)
+}}}
+
+Functional dependency:
+
+{{{
+reservation_id, equipment_id -> requested_quantity
+}}}
+
+Candidate key:
+
+{{{
+(reservation_id, equipment_id)
+}}}
+
+The determinant is the candidate key, so the relation is in BCNF.
+
+=== approvals ===
+
+Relation:
+
+{{{
+approvals(approval_id, reservation_id, approver_id, decision, decision_time, note)
+}}}
+
+Functional dependencies:
+
+{{{
+approval_id -> reservation_id, approver_id, decision, decision_time, note
+reservation_id -> approval_id, approver_id, decision, decision_time, note
+}}}
+
+Candidate keys:
+
+{{{
+approval_id
+reservation_id
+}}}
+
+All determinants are candidate keys, so the relation is in BCNF.
+
+=== BCNF conclusion ===
+
+All final relations are in BCNF. The decomposition also preserves the important functional dependencies and has loss-less join properties. Therefore, no further decomposition is required.
+
+== Final result and discussion ==
+
+=== Normalized relational model ===
+
+The final normalized relational model is:
+
+{{{
+buildings(
+building_id PK,
+name,
+address
+)
+}}}
+
+{{{
+rooms(
+room_id PK,
+building_id FK,
+room_code AK,
+capacity,
+type
+)
+}}}
+
+{{{
+equipment(
+equipment_id PK,
+name AK,
+stock_quantity
+)
+}}}
+
+{{{
+room_equipment(
+room_id PK, FK,
+equipment_id PK, FK,
+quantity
+)
+}}}
+
+{{{
+users(
+user_id PK,
+username AK,
+email AK,
+full_name,
+role
+)
+}}}
+
+{{{
+reservations(
+reservation_id PK,
+room_id FK,
+user_id FK,
+reservation_date,
+start_time,
+end_time,
+status
+)
+}}}
+
+{{{
+reservation_equipment(
+reservation_id PK, FK,
+equipment_id PK, FK,
+requested_quantity
+)
+}}}
+
+{{{
+approvals(
+approval_id PK,
+reservation_id FK, AK,
+approver_id FK,
+decision,
+decision_time,
+note
+)
+}}}
+
+=== Discussion ===
+
+The normalization process started from a single de-normalized relation containing all attributes from the model. That relation was in 1NF, but it was not in 2NF because many attributes depended only on parts of the composite key. The decomposition removed partial dependencies, then removed transitive dependencies, and finally checked the resulting relations for BCNF.
+
+The final normalized design contains separate relations for buildings, rooms, equipment, users, reservations, room equipment, reservation equipment, and approvals.
+
+The M:N relationship between rooms and equipment is represented by:
+
+{{{
+room_equipment(room_id, equipment_id, quantity)
+}}}
+
+The M:N relationship between reservations and requested equipment is represented by:
+
+{{{
+reservation_equipment(reservation_id, equipment_id, requested_quantity)
+}}}
+
+This prevents repeated data and allows equipment to be managed independently from both rooms and reservations.
+
+=== Comparison with Phase P2 ===
+
+The final normalized model obtained in this phase is consistent with the relational design from Phase P2. The same main relations are used:
+
+* buildings
+* rooms
+* equipment
+* room_equipment
+* users
+* reservations
+* reservation_equipment
+* approvals
+
+This means that the Phase P2 relational schema was already designed in a normalized way. No structural change to the existing PostgreSQL database schema is required after the normalization check.
+
+The existing Phase P2 design will continue to be used in the following project phases.
+
+== Conclusion ==
+
+The formal normalization process shows that the final relational model is in BCNF. The decomposition preserves the functional dependencies, has loss-less join properties, and matches the already implemented relational schema from Phase P2.
+
+Therefore, the current database design is appropriate for the next phases of the project.