Changes between Version 3 and Version 4 of Normalization

Timestamp:

01/28/26 01:07:32 (12 days ago)

Author:

233144

Comment:

--

Normalization

@@ -1 +1 @@
 = Normalization
 
-Our database has the following identificators: user_id, component_id, build_id, review_id and suggestion_id.\\
-Some of the relations have composite primary keys, such as:\\
-(build_id, component_id) - build_component\\
-(build_id, user_id) - rating_build\\
-(build_id, user_id) - favorite_build\\
-The component subtypes like CPU, GPU, Motherboard etc. do not have separate identificators, because they use component_id as both primary and foreign key referencing the **components** table.
-
-== Functional Dependencies
-
-user_id → username, password, email\\
-user_id → / (admins is a subtype of user with no additional attributes)\\
-
-component_id → name, brand, price, type, img_url\\
-
-component_id → socket, cores, threads, base_clock, boost_clock, tdp                 (cpu)\\
-component_id → vram, tdp, base_clock, boost_clock, chipset, length                (gpu)\\
-component_id → memory_type, speed, capacity, modules                              (memory)\\
-component_id → storage_type, capacity, form_factor                                (storage)\\
-component_id → psu_type, wattage, form_factor                                     (power_supply)\\
-component_id → socket, chipset, form_factor, ram_type, num_ram_slots, max_ram_capacity, pci_express_slots                                (motherboard)\\
-component_id → cooler_max_height, gpu_max_length                                   (pc_case)\\
-component_id → cooler_type, height, max_tdp_supported                               (cooler)\\
-component_id → num_slots, interface                                                (memory_card)\\
-component_id → form_factor, type, interface, write_speed, read_speed               (optical_drive)\\
-component_id → sample_rate, bit_depth, chipset, interface, channel                 (sound_carad)\\
-component_id → length_cm, type                                                     (cable)\\
-component_id → wifi_version, interface, num_antennas                               (network_adapter)\\
-component_id → num_ports, speed, interface                                        (network_card)\\
-
-build_id → user_id, name, created_at, description, total_price, is_approved\\
-build_id, component_id → / (build_component)\\
-
-build_id, user_id → / (favorite_build)\\
-build_id, user_id → value (rating_build)\\
-
-review_id → build_id, user_id, content, created_at\\
-
-suggestion_id → user_id, admin_id, link, description, admin_comment, status, component_type\\
-
-== Universal Relation (R)
-
-R = {
-user_id, username, password, email,
-component_id, name, brand, price, type, img_url,
-cpu_socket, cpu_cores, cpu_threads, cpu_base_clock, cpu_boost_clock, cpu_tdp,
-gpu_vram, gpu_tdp, gpu_base_clock, gpu_boost_clock, gpu_chipset, gpu_length,
-memory_type, memory_speed, memory_capacity, memory_modules,
-storage_type, storage_capacity, storage_form_factor,
-psu_type, psu_wattage, psu_form_factor,
-motherboard_socket, motherboard_chipset, motherboard_form_factor,
-ram_type, num_ram_slots, max_ram_capacity, pci_express_slots,
-case_cooler_max_height, case_gpu_max_length,
-cooler_type, cooler_height, max_tdp_supported,
-build_id, build_name, created_at, description, total_price, is_approved,
-rating_value,
-review_id, review_content, review_created_at,
-suggestion_id, link, admin_comment, status, component_type
-}
-
-Left (determinants):\\
-user_id\\
-component_id\\
-build_id\\
-review_id\\
-suggestion_id\\
-
-Right (descriptive attributes), attributes with similar names are prefixed (cpu_, gpu_, build_, etc.):\\
-username, password, email,\\
-name, brand, price, type, img_url,\\
-cpu_*, gpu_*, memory_*, storage_*, psu_*, motherboard_*, case_*, cooler_*,\\
-build_name, created_at, description, total_price, is_approved,\\
-rating_value,\\
-review_content, review_created_at,\\
-link, admin_comment, status, component_type\\
-
-Left and right:\\
-user_id\\
-component_id\\
-build_id\\
-
-== Attribute Closures
-
-user_id+ = { user_id, username, password, email }
-
-component_id+ = { component_id, name, brand, price, type, img_url, 
-cpu_socket, cpu_cores, cpu_threads, cpu_base_clock, cpu_boost_clock, cpu_tdp,
-gpu_vram, gpu_tdp, gpu_base_clock, gpu_boost_clock, gpu_chipset, gpu_length,
-memory_type, memory_speed, memory_capacity, memory_modules,
-storage_type, storage_capacity, storage_form_factor,
-psu_type, psu_wattage, psu_form_factor,
-motherboard_socket, motherboard_chipset, motherboard_form_factor,
-ram_type, num_ram_slots, max_ram_capacity, pci_express_slots,
-case_cooler_max_height, case_gpu_max_length,
-cooler_type, cooler_height, max_tdp_supported,
-num_slots, interface, form_factor, type, write_speed, read_speed,
-sample_rate, bit_depth, chipset, interface, channel,
-length_cm, type,
-wifi_version, interface, num_antennas,
-num_ports, speed, interface }
-
-build_id+ = { build_id, user_id, name, created_at, description, total_price, is_approved }
-
-(build_id, component_id)+ = { build_id, component_id } (build_component)
-
-(build_id, user_id)+ = { build_id, user_id, rating_value }
-
-review_id+ = { review_id, build_id, user_id, content, created_at }
-
-suggestion_id+ = { suggestion_id, user_id, admin_id, link, description, admin_comment, status, component_type }
-
-
-The union of\\
-{ user_id, component_id, build_id, review_id, suggestion_id }+\\
-covers all attributes of R, so 1NF (First Normal Form) is satisfied. Now in this (lets call it) "super-table", if we consider **component_id** + other IDs as a composite key for the super-table, attributes like **cpu_socket** depend on **component_id** only, not on other IDs like **build_id** or **user_id**. This is a partial dependency, which means that 2NF is not satisfied.
-
-== 2NF Decomposition
-
-**First we will identify the partial dependencies:**\\
-
-user_id → username, email, password, is_admin\\
-
-component_id → name, brand, price, type, img_url, cpu_socket, cpu_cores, cpu_threads, cpu_base_clock, cpu_boost_clock, cpu_tdp,
-gpu_vram, gpu_tdp, gpu_base_clock, gpu_boost_clock, gpu_chipset, gpu_length,
-memory_type, memory_speed, memory_capacity, memory_modules,
-storage_type, storage_capacity, storage_form_factor,
-psu_type, psu_wattage, psu_form_factor,
-motherboard_socket, motherboard_chipset, motherboard_form_factor,
-ram_type, num_ram_slots, max_ram_capacity, pci_express_slots,
-case_cooler_max_height, case_gpu_max_length,
-cooler_type, cooler_height, max_tdp_supported
-
-build_id → user_id, name, created_at, description, total_price, is_approved
+== Initial de-normalized relation (R) and functional dependencies
+
+R(
+  user_id, username, password, email,
+  component_id, component_name, brand, price, component_type, img_url,
+  cpu_socket, cpu_cores, cpu_threads, cpu_base_clock, cpu_boost_clock, cpu_tdp,
+  gpu_vram, gpu_tdp, gpu_base_clock, gpu_boost_clock, gpu_chipset, gpu_length,
+  memory_type, memory_speed, memory_capacity, memory_modules,
+  storage_type, storage_capacity, storage_form_factor,
+  psu_type, psu_wattage, psu_form_factor,
+  motherboard_socket, motherboard_chipset, motherboard_form_factor,
+  ram_type, num_ram_slots, max_ram_capacity, pci_express_slots,
+  case_cooler_max_height, case_gpu_max_length,
+  case_storage_form_factor, case_storage_slots,
+  case_ps_form_factor,
+  case_mobo_form_factor,
+  cooler_type, cooler_height, cooler_max_tdp,
+  cooler_socket,
+  memory_card_slots, memory_card_interface,
+  optical_form_factor, optical_type, optical_interface,
+  optical_write_speed, optical_read_speed,
+  sound_sample_rate, sound_bit_depth, sound_chipset, sound_interface, sound_channel,
+  cable_length, cable_type,
+  net_adapter_wifi, net_adapter_interface, net_adapter_antennas,
+  net_card_ports, net_card_speed, net_card_interface,
+  build_id, build_name, build_created_at, build_description,
+  build_total_price, build_is_approved,
+  rating_value, review_content, review_created_at,
+  suggestion_id, suggestion_link, suggestion_description,
+  suggestion_status, suggestion_admin_comment, suggestion_component_type
+)
+
+Functional dependencies:
+
+user_id → username, password, email
+
+component_id → name, brand, price, component_type, img_url
+
+component_id → cpu_socket, cpu_cores, cpu_threads, cpu_base_clock, cpu_boost_clock, cpu_tdp
+
+component_id → gpu_vram, gpu_tdp, gpu_base_clock, gpu_boost_clock, gpu_chipset, gpu_length
+
+component_id → memory_type, memory_speed, memory_capacity, memory_modules
+
+component_id → storage_type, storage_capacity, storage_form_factor
+
+component_id → psu_type, psu_wattage, psu_form_factor
+
+component_id → motherboard_socket, motherboard_chipset, motherboard_form_factor, ram_type, num_ram_slots, max_ram_capacity, pci_express_slots
+
+component_id → case_cooler_max_height, case_gpu_max_length
+
+component_id → cooler_type, cooler_height, cooler_max_tdp
+
+component_id → memory_card_slots, memory_card_interface
+
+component_id → optical_form_factor, optical_type, optical_interface, optical_write_speed, optical_read_speed
+
+component_id → sound_sample_rate, sound_bit_depth, sound_chipset, sound_interface, sound_channel
+
+component_id → cable_length, cable_type
+
+component_id → net_adapter_wifi, net_adapter_interface, net_adapter_antennas
+
+component_id → net_card_ports, net_card_speed, net_card_interface
+ 
+(component_id, form_factor) → /, for case motherboard and power supply form factors
+
+(component_id, form_factor) → num_slots, for case storage form factors
+
+(component_id, socket) → /, for cooler cpu sockets
+
+build_id → user_id, build_name, build_created_at, build_description, build_total_price, build_is_approved
 
 (build_id, user_id) → rating_value
 
-review_id → review_build_id (FK build_id), review_user_id (FK user_id), review_content
-
-suggestion_id → suggestion_user_id, suggestion_admin_id, suggestion_link, suggestion_admin_comment, suggestion_description, suggestion_status, suggestion_component_type
-
-(build_id, component_id) → /
-
-(build_id, user_id) → /
-
-**Then we will extract the proper relations:**\\
-
-users { user_id, username, email, password } - BCNF\\
-admins { user_id } → FK to users - BCNF\\
-
-components { component_id, name, brand, price, type, img_url } - BCNF
-
-cpu { component_id, socket, cores, threads, base_clock, boost_clock, tdp } → FK to components - BCNF\\
-gpu { component_id, vram, tdp, base_clock, boost_clock, chipset, length } → FK to components - BCNF\\
-memory { component_id, type, speed, capacity, modules } → FK to components - BCNF\\
-storage { component_id, type, capacity, form_factor } → FK to components - BCNF\\
-power_supply { component_id, type, wattage, form_factor } → FK to components - BCNF\\
-motherboard{ component_id, socket, chipset, form_factor, ram_type, num_ram_slots, max_ram_capacity, pci_express_slots } → FK to components - BCNF\\
-pc_case { component_id, cooler_max_height, gpu_max_length } → FK to components - BCNF\\
-case_storage_form_factors { case_id, form_factor, num_slots } → FK to pc_case - BCNF\\
-case_ps_form_factors { case_id, form_factor } → FK to pc_case - BCNF\\
-case_mobo_form_factors { case_id, form_factor } → FK to pc_case - BCNF\\
-cooler { component_id, type, height, max_tdp_supported } → FK to components - BCNF\\
-cooler_cpu_sockets { cooler_id, socket } → FK to cooler - BCNF\\
-memory_card { component_id, num_slots, interface } → FK to components - BCNF\\
-optical_drive { component_id, form_factor, type, interface, write_speed, read_speed } → FK to components - BCNF\\
-sound_card { component_id, sample_rate, bit_depth, chipset, interface, channel } → FK to components - BCNF\\
-cables { component_id, length_cm, type } → FK to components - BCNF\\
-network_adapter { component_id, wifi_version, interface, num_antennas } → FK to components - BCNF\\
-network_card { component_id, num_ports, speed, interface } → FK to components - BCNF\\
-
-build { build_id, build_user_id, build_name, created_at, description, total_price, is_approved } → FK to users - BCNF\\
-build_component { build_id, component_id } → FK to build and components - BCNF\\
-
-favorite_build { build_id, user_id } → FK to build and users - BCNF\\
-rating_build { build_id, user_id, value } → FK to build and users - BCNF\\
-review { review_id, build_id, user_id, content, created_at } → FK to build and users - BCNF\\
-
-suggestions { id, user_id, admin_id, link, admin_comment, description, status, component_type } → FK to users/admins - BCNF\\
-
-== Check 3NF and BCNF
-
-We can see that all foreign keys point to primary keys, so no transitive dependencies can be detected here. All component subtypes are in separate tables which removes the partial dependencies from before. We also separated the user roles, and in the relations all non-key attributes fully depend on their primary key. 
-
-3NF/BCNF is satisfied.
+review_id → build_id, user_id, review_content, review_created_at
+
+suggestion_id → user_id, admin_id, link, description, status, admin_comment, component_type
+
+The de-normalized relation violates 1NF because it contains multi-valued attributes.
+
+== Candidate keys of the de-normalized relation
+
+Because the universal relation combines users, builds, components, reviews, and suggestions, a minimal key must uniquely identify all of them.
+
+The artifical candidate key is {user_id, build_id, component_id, review_id, suggestion_id}
+
+Universal relation primary key = {user_id, build_id, component_id, review_id, suggestion_id}
+
+== 1NF Decomposition
+
+Here we have to separate the multi-valued attributes into individual relations. This will ensure that all values are atomic.
+
+case_storage_form_factors(case_id, form_factor, num_slots)
+
+case_ps_form_factors(case_id, form_factor)
+
+case_mobo_form_factors(case_id, form_factor)
+
+cooler_cpu_sockets(cooler_id, socket)
+
+build_component(build_id, component_id)
+
+
+We separate obvious entities in individual relations:
+
+users(user_id, username, password, email)
+
+admins(user_id)
+
+components(component_id, name, brand, price, component_type, img_url)
+
+cpu(component_id, cpu_socket, cpu_cores, cpu_threads, cpu_base_clock, cpu_boost_clock, cpu_tdp)
+
+gpu(component_id, gpu_vram, gpu_tdp, gpu_base_clock, gpu_boost_clock, gpu_chipset, gpu_length)
+
+memory(component_id, memory_type, memory_speed, memory_capacity, memory_modules)
+
+storage(component_id, storage_type, storage_capacity, storage_form_factor)
+
+power_supply(component_id, psu_type, psu_wattage, psu_form_factor)
+
+motherboard(component_id, motherboard_socket, motherboard_chipset, motherboard_form_factor, ram_type, num_ram_slots, max_ram_capacity, pci_express_slots)
+
+pc_case(component_id, case_cooler_max_height, case_gpu_max_length)
+
+cooler(component_id, cooler_type, cooler_height, cooler_max_tdp)
+
+memory_card(component_id, memory_card_slots, memory_card_interface)
+
+optical_drive(component_id, optical_form_factor, optical_type, optical_interface, optical_write_speed, optical_read_speed)
+
+sound_card(component_id, sound_sample_rate, sound_bit_depth, sound_chipset, sound_interface, sound_channel)
+
+cables(component_id, cable_length, cable_type)
+
+network_adapter(component_id, net_adapter_wifi, net_adapter_interface, net_adapter_antennas)
+
+network_card(component_id, net_card_ports, net_card_speed, net_card_interface)
+
+build(build_id, user_id, build_name, build_created_at, build_description, build_total_price, build_is_approved)
+
+review(review_id, build_id, user_id, review_content, review_created_at)
+
+rating_build(build_id, user_id, rating_value)
+
+suggestions(suggestion_id, user_id, admin_id, link, description, status, admin_comment, component_type)
+
+all of which satisfy 1NF.
+
+
+Candidate keys & primary keys:
+
+users → user_id
+
+admins → user_id
+
+components → component_id
+
+component subclasses (like cpu, gpu etc.) → component_id
+
+build → build_id
+
+review → review_id
+
+rating_build → (build_id, user_id)
+
+favorite_build → (build_id, user_id)
+
+suggestions → suggestion_id
+
+== Second Normal Form (2NF)
+
+2NF focuses on partial dependencies, which can only occur when a relation has a composite primary key and a non-key attribute depends on only part of that key. Relations with a single-attribute primary key were considered to be automatically in 2NF. Most of the relations obtained after 1NF like users, components, build, review and suggestions, have single-attribute primary keys so partial dependencies cannot exist in these relations. The remaining relations that have composite primary keys build_component, favorite_build, rating_build were analyzed separately.
+
+build_component(build_id, component_id) - doesn't have non-key attributes so it is already 2NF
+
+favorite_build(build_id, user_id) - doesn't have non-key attributes so it is already 2NF
+
+rating_build(build_id, user_id, rating_value) - rating_value depends on full key so it is 2NF
+
+In the case of associative tables like build_component and favorite_build no non-key attributes are present so partial dependencies are not possible. For rating_build the non-key attribute depend on the full composite key (a rating is uniquely determined by both the user and the build). Since no non-key attribute was found to be partially dependent all relations satisfy 2NF.
+
+== Third normal Form (3NF)
+
+users(user_id, username, password, email) - all attributes depend directly on user_id so 3NF is satisfied
+
+components(component_id, name, brand, price, component_type, img_url) - all attributes depend directly on component_id so this is 3NF
+
+build(build_id, user_id, build_name, build_created_at, build_description, build_total_price, build_is_approved) - all attributes depend on build_id which means that 3NF is satisfied
+
+component subclasses (like cpu, gpu, memory etc.) - all attributes depend directly on component_id so 3NF is satisfied
+
+review(review_id, build_id, user_id, review_content, review_created_at) - attributes depend on review_id, 3NF is satisfied
+
+rating_build(build_id, user_id, rating_value) → rating_value depends on (build_id, user_id), 3NF is satisfied
+
+favorite_build(build_id, user_id) - no non-key attributes so this automatically satisfies 3NF
+
+suggestions(suggestion_id, user_id, admin_id, link, description, status, admin_comment, component_type) - attributes depend on suggestion_id, 3NF is satisfied
+
+case_storage_form_factors(case_id, form_factor, num_slots) - no transitive dependencies, 3NF is satisfied
+
+case_ps_form_factors(case_id, form_factor) - no transitive dependencies, 3NF is satisfied
+
+case_mobo_form_factors(case_id, form_factor) - no transitive dependencies, 3NF is satisfied
+
+cooler_cpu_sockets(cooler_id, socket) - no transitive dependencies, 3NF is satisfied
+
+build_component(build_id, component_id) - no transitive dependencies because there are no non-key attributes, therefore 3NF is satisfied.
+
+== BCNF decomposition
+
+BCNF checks if every determinant is a super-key so we need to analyze all 3NF relations.
+
+users(user_id, username, password, email):
+
+ FD: user_id → username, password, email
+
+ Determinant user_id is the primary key (superkey), BCNF
+
+
+admins(user_id):
+
+ Determinant user_id is the primary key (superkey), BCNF
+
+
+components(component_id, name, brand, price, component_type, img_url):
+
+ FD: component_id → name, brand, price, component_type, img_url
+
+ Determinant component_id is the primary key (superkey), BCNF
+
+
+Component specialization tables (cpu, gpu, memory, etc.):
+
+ Each table: primary key = component_id
+
+ All attributes depend only on component_id
+
+ Determinant is primary key(superkey), BCNF
+
+
+build(build_id, user_id, build_name, build_created_at, build_description, build_total_price, build_is_approved):
+
+ FD: build_id → user_id, build_name, build_created_at, build_description, build_total_price, build_is_approved
+
+ Determinant build_id is primary key(superkey), BCNF
+
+
+build_component(build_id, component_id):
+
+ FD: composite key (build_id, component_id) → /
+
+ No non-key attributes so its by default BCNF 
+
+
+favorite_build(build_id, user_id):
+
+ FD: Composite key (build_id, user_id) → /
+
+ No non-key attributes so its by default BCNF 
+
+
+rating_build(build_id, user_id, rating_value):
+
+ FD: (build_id, user_id) → rating_value
+
+ Determinant is full primary key (superkey), BCNF
+
+
+review(review_id, build_id, user_id, review_content, review_created_at):
+
+ FD: review_id → build_id, user_id, review_content, review_created_at
+
+ Determinant = primary key (superkey), BCNF
+
+
+suggestions(suggestion_id, user_id, admin_id, link, description, status, admin_comment, component_type):
+
+ FD: suggestion_id → user_id, admin_id, link, description, status, admin_comment, component_type
+
+ Determinant is primary key (superkey)
+
+
+case_storage_form_factors(case_id, form_factor, num_slots):
+
+ FD: (case_id, form_factor) → num_slots
+
+ Full composite key is determinant (superkey), BCNF
+
+
+case_ps_form_factors(case_id, form_factor):
+
+ FD: (case_id, form_factor) → /
+
+ Full composite key is determinant (superkey), BCNF
+
+
+case_mobo_form_factors(case_id, form_factor):
+ 
+ FD: (case_id, form_factor) → /
+
+ Full composite key is determinant (superkey), BCNF
+
+ 
+cooler_cpu_sockets(cooler_id, socket):
+
+ FD: (cooler_id, socket) → /
+
+ Full composite key is determinant (superkey), BCNF
+
+
+We can now see that all determinants are superkeys, so BCNF is satisfied.
+
+