Normalization

De-normalized Database Form

First, we combine every attribute in the entire model into one single relation - Universal Relation R.

R(
    user_id,
    email,
    username,
    password,
    date_created,
    shipping_address,
    telephone_number,
    admin_id,
    admin_type,
    discount_percentage,
    points_collected,
    artist_id,
    artist_name,
    artist_description,
    artist_photo,
    release_id,
    title,
    record_label,
    genre,
    release_date,
    cover_photo,
    album_id,
    duration,
    song_id,
    song_name,
    song_duration,
    product_id,
    format,
    price,
    product_description,
    stock,
    order_id,
    payment_method,
    purchase_date,
    points_earned,
    points_used,
    status,
    modification_id,
    date_modified,
    type_of_modification,
    discount,
    wishlist_id,
    quantity,
    price_at_purchase,
    added_at,
    release_ordinal,
    type,
    song_ordinal
)

Functional Dependencies

FD01: user_id → email, username, password, date_created, shipping_address, telephone_number
FD02: email → user_id
FD03: username → user_id
FD04: user_id → admin_type, discount_percentage
FD05: user_id → points_collected
FD06: artist_id → artist_name, artist_description, artist_photo
FD07: release_id → title, record_label, genre, release_date, cover_photo, duration
FD08: song_id → song_name, song_duration
FD09: product_id → release_id, format, price, product_description, stock
FD10: order_id → user_id, payment_method, purchase_date, points_earned, points_used, status
FD11: modification_id → admin_id, date_modified, type_of_modification, discount
FD12: wishlist_id → user_id
FD13: user_id → wishlist_id
FD14: (order_id, product_id) → price_at_purchase, quantity
FD15: (wishlist_id, product_id) → added_at
FD16: (release_id, artist_id) → release_ordinal, type
FD17: (song_id, artist_id) → song_ordinal

LHS only:
artist_id, song_id, product_id, order_id, modification_id, album_id

RHS only:
email, username, password, date_created, shipping_address, telephone_number, admin_type, discount_percentage, points_collected, artist_name, artist_description, artist_photo, title, record_label, genre, release_date, cover_photo, duration, song_name, song_duration, format, price, product_description, stock, payment_method, purchase_date, points_earned, points_used, status, date_modified, type_of_modification, discount, price_at_purchase, quantity, release_ordinal, type, added_at, song_ordinal

Both LHS and RHS:
user_id, wishlist_id, release_id

Candidate Keys and Primary Key

When identifying a candidate key, we first consider the attributes that appear only on the left-hand side (LHS) of the functional dependencies:

{artist_id, song_id, product_id, order_id,modification_id, album_id}

These attributes cannot be derived from any other attributes using the given functional dependencies, so they must be included in a candidate key.

Therefore, we initially define:

K = {order_id, product_id, artist_id, song_id, modification_id, album_id}

The closure K+ contains all attributes of the universal relation R. Therefore, K is a superkey. Each attribute in K is necessary because removing any one of them prevents at least one set of attributes of R from being derived. Therefore, K is minimal and the selected primary key for the initial de-normalized relation is:

(order_id, product_id, artist_id, song_id, modification_id, album_id)

Normal Form of R Before Decomposition

R ∈ 1NF: The universal relation R is in 1NF because all attributes contain atomic values and there are no repeating groups.

R ∉ 2NF: Since candidate key of R: K = {order_id, product_id, artist_id, song_id, modification_id, album_id} is a composite key, we must check for partial functional dependencies in order to determine whether R satisfies 2NF.

Examples of a 2NF violation:

• product_id → release_id, format, price, product_description, stock
• artist_id → artist_name, artist_description, artist_photo
• song_id → song_name, song_duration

In each case, a proper subset of the candidate key determines non-prime attributes. Therefore, R contains partial functional dependencies and is not in 2NF.

2NF Decomposition

1. PRODUCT(product_id, format, price, product_description, stock)

R1 = R - {release_id, format, price, product_description, stock}

R1 = {user_id, email, username, password, date_created, shipping_address, telephone_number, admin_type, discount_percentage, points_collected,
      artist_id, artist_name, artist_description, artist_photo, release_id, title, record_label, genre, release_date, cover_photo, duration,
      album_id, song_id, song_name, song_duration, order_id, payment_method, purchase_date, points_earned, points_used, status, modification_id,
      admin_id, date_modified, type_of_modification, discount, wishlist_id, quantity, price_at_purchase, added_at, release_ordinal,
      type, song_ordinal, product_id}

• Lossless join: The original relation can be reconstructed through a join using product_id.

• Dependency preservation: The dependency product_id → release_id, format, price, product_description, stock is preserved in the new PRODUCT relation.

2. ARTIST(artist_id, artist_name, artist_description, artist_photo)

R2 = R1 - {artist_name, artist_description, artist_photo}

R2 = {user_id, email, username, password, date_created, shipping_address, telephone_number, admin_type, discount_percentage, points_collected,
      artist_id, release_id, title, record_label, genre, release_date, cover_photo, duration, album_id, song_id, song_name, song_duration,
      product_id, order_id, payment_method, purchase_date, points_earned, points_used, status, modification_id, admin_id, date_modified,
      type_of_modification, discount, wishlist_id, quantity, price_at_purchase, added_at, release_ordinal, type, song_ordinal}

• Lossless join: The original relation can be reconstructed through a join using artist_id.

• Dependency preservation: The dependency artist_id → artist_name, artist_description, artist_photo is preserved in the new ARTIST relation.

3. RELEASE(release_id, title, record_label, genre, release_date, cover_photo, duration)

R3 = R2 - {title, record_label, genre, release_date, cover_photo, duration}

R3 = {user_id, email, username, password, date_created, shipping_address, telephone_number, admin_type, discount_percentage, points_collected,
      artist_id, release_id, album_id, song_id, song_name, song_duration, product_id, order_id, payment_method, purchase_date,
      points_earned, points_used, status, modification_id, admin_id, date_modified, type_of_modification, discount, wishlist_id,
      quantity, price_at_purchase, added_at, release_ordinal, type, song_ordinal}

• Lossless join: The original relation can be reconstructed through a join using release_id.

• Dependency preservation: The dependency release_id → title, record_label, genre, release_date, cover_photo is preserved in the new RELEASE relation.

4. SONG(song_id, song_name, song_duration)

R4 = R3 - {song_name, song_duration}

R4 = {user_id, email, username, password, date_created, shipping_address, telephone_number, admin_type, discount_percentage, points_collected,
      artist_id, release_id, album_id, song_id, product_id, order_id, payment_method, purchase_date, points_earned, points_used, status,
      modification_id, admin_id, date_modified, type_of_modification, discount, wishlist_id, quantity, price_at_purchase, added_at,
      release_ordinal, type, song_ordinal}

• Lossless join: The original relation can be reconstructed through a join using song_id.

• Dependency preservation: The dependency song_id → song_name, song_duration is preserved in the new SONG relation.

5. MODIFICATION(modification_id, admin_id, date_modified, type_of_modification, discount)

R5 = R4 - {admin_id, date_modified, type_of_modification, discount}

R5 = {user_id, email, username, password, date_created, shipping_address, telephone_number, admin_type, discount_percentage, points_collected,
      artist_id, release_id, album_id, song_id, product_id, order_id, payment_method, purchase_date, points_earned, points_used, status,
      modification_id, wishlist_id, quantity, price_at_purchase, added_at, release_ordinal, type, song_ordinal}

• Lossless join: The original relation can be reconstructed through a join using modification_id.

• Dependency preservation: The dependency modification_id → admin_id, date_modified, type_of_modification, discount is preserved in the new MODIFICATION relation.

6. ORDER(order_id, user_id, payment_method, purchase_date, points_earned, points_used, status)

R6 = R5 - {payment_method, purchase_date, points_earned, points_used, status}

R6 = {user_id, email, username, password, date_created, shipping_address, telephone_number, admin_type, discount_percentage, points_collected,
      artist_id, release_id, album_id, song_id, product_id, order_id, modification_id, wishlist_id, quantity, price_at_purchase, added_at,
      release_ordinal, type, song_ordinal}

• Lossless join: The original relation can be reconstructed through a join using order_id.

• Dependency preservation: The dependency order_id → user_id, payment_method, purchase_date, points_earned, points_used, status is preserved in the new ORDER relation.

7. USER(user_id, email, username, password, date_created, shipping_address, telephone_number)

R7 = R6 - {email, username, password, date_created, shipping_address, telephone_number}

R7 = {user_id, admin_type, discount_percentage, points_collected, artist_id, release_id, album_id, song_id, product_id, order_id,
      modification_id, wishlist_id, quantity, price_at_purchase, added_at, release_ordinal, type, song_ordinal}

• Lossless join: The original relation can be reconstructed through a join using user_id.

• Dependency preservation: The dependency user_id → email, username, password, date_created, shipping_address, telephone_number is preserved in the new USER relation.

8. ORDER_PRODUCTS(order_id, product_id, price_at_purchase, quantity)

R8 = R7 - {price_at_purchase, quantity}

R8 = {user_id, admin_type, discount_percentage, points_collected, artist_id, release_id, album_id, song_id, product_id, order_id,
      modification_id, wishlist_id, added_at, release_ordinal, type, song_ordinal}

• Lossless join: The original relation can be reconstructed through a join using order_id, product_id.

• Dependency preservation: The dependency (order_id, product_id) → price_at_purchase, quantity is preserved in the new ORDER_PRODUCTS relation.

9. WISHLIST_PRODUCTS(wishlist_id, product_id, added_at)

R9 = R8 - {added_at}

R9 = {user_id, admin_type, discount_percentage, points_collected, artist_id, release_id, album_id, song_id, product_id, order_id,
      modification_id, wishlist_id, release_ordinal, type, song_ordinal}

• Lossless join: The original relation can be reconstructed through a join using wishlist_id, product_id.

• Dependency preservation: The dependency (wishlist_id, product_id) → added_at is preserved in the new WISHLIST_PRODUCTS relation.

10. RELEASE_ARTISTS(release_id, artist_id, release_ordinal, type)

R10 = R9 - {release_ordinal, type}

R10 = {user_id, admin_type, discount_percentage, points_collected, artist_id, release_id, album_id, song_id, product_id, order_id,
       modification_id, wishlist_id, song_ordinal}

• Lossless join: The original relation can be reconstructed through a join using release_id, artist_id.

• Dependency preservation: The dependency (release_id, artist_id) → release_ordinal, type is preserved in the new RELEASE_ARTISTS relation.

11. SONG_ARTISTS(song_id, artist_id, song_ordinal)

R11 = R10 - {song_ordinal}

R11 = {user_id, admin_type, discount_percentage, points_collected, artist_id, release_id, album_id, song_id, product_id, order_id,
       modification_id, wishlist_id}

• Lossless join: The original relation can be reconstructed through a join using song_id, artist_id.

• Dependency preservation: The dependency (song_id, artist_id) → song_ordinal is preserved in the new SONG_ARTISTS relation.

12. ADMIN(user_id, admin_type, discount_percentage)

R12 = R11 - {admin_type, discount_percentage}

R12 = {user_id, points_collected, artist_id, release_id, album_id, song_id, product_id, order_id, modification_id, wishlist_id}

• Lossless join: The original relation can be reconstructed through a join using user_id.

• Dependency preservation: The dependency user_id → admin_type, discount_percentage is preserved in the new ADMIN relation.

13. CONSUMER(user_id, points_collected)

R13 = R12 - {points_collected}

R13 = {user_id, artist_id, release_id, album_id, song_id, product_id, order_id, modification_id, wishlist_id}

• Lossless join: The original relation can be reconstructed through a join using user_id.

• Dependency preservation: The dependency user_id → points_collected is preserved in the new CONSUMER relation.

14. WISHLIST(user_id, wishlist_id)

R14 = R13 - {wishlist_id}

R14 = {user_id, artist_id, release_id, album_id, song_id, product_id, order_id, modification_id}

• Lossless join: The original relation can be reconstructed through a join using user_id.

• Dependency preservation: The dependencies user_id → wishlist_id and wishlist_id → user_id are preserved in the new WISHLIST relation.

15. Removing Remaining Partial Dependencies

Two non-prime attributes remain:

1. order_id → user_id
2. product_id → release_id

Since order_id and product_id are proper subsets of the candidate key, these are still partial dependencies. However, these dependencies are already represented in ORDER and PRODUCT.

R15 = R14 - {user_id, release_id}

R15 = {artist_id, release_id, album_id, song_id, product_id,
       order_id, modification_id}

• Lossless join: The removed user_id can be recovered through the existing ORDER relation using order_id and the removed release_id can be recovered through the existing PRODUCT relation using product_id.

• Dependency preservation: The dependency order_id → user_id remains preserved in the existing ORDER relation and the dependency product_id → release_id remains preserved in the existing PRODUCT relation.

3NF Decomposition

Listed bellow are the relations obtained after the 2NF decomposition as they are examined for transitive dependencies to determine whether or not a 3NF Decomposition is needed.

PRODUCT

Attributes : product_id, release_id, format, price, product_description, stock
FDs        : FD09 (product_id → release_id, format, price, product_description, stock)
CKs / PK   : {product_id}

release_id is a non-key attribute and a foreign key to RELEASE, but it does not determine any other attribute within PRODUCT. All non-key attributes depend directly on product_id. No decomposition needed.

ARTIST

Attributes : artist_id, artist_name, artist_description, artist_photo
FDs        : FD06 (artist_id → artist_name, artist_description, artist_photo)
CKs / PK   : {artist_id}

All non-key attributes depend directly on artist_id. There are no dependencies between non-key attributes. No decomposition needed.

RELEASE

Attributes : release_id, title, record_label, genre, release_date, cover_photo, duration
FDs        : FD07 (release_id → title, record_label, genre, release_date, cover_photo, duration)
CKs / PK   : {release_id}

All non-key attributes depend directly on release_id. There is no non-key attribute that determines another non-key attribute. No decomposition needed.

SONG

Attributes : song_id, song_name, song_duration
FDs        : FD08 (song_id → song_name, song_duration)
CKs / PK   : {song_id}

Only two non-key attributes exist, and both depend directly on song_id. No transitive dependency exists. No decomposition needed.

MODIFICATION

Attributes : modification_id, admin_id, date_modified, type_of_modification, discount
FDs        : FD11 (modification_id → admin_id, date_modified, type_of_modification, discount)
CKs / PK   : {modification_id}

admin_id is a non-key attribute and a foreign key to ADMIN. Although admin_id determines attributes in ADMIN, it does not determine any other attribute inside MODIFICATION. Therefore, no transitive dependency exists within this relation. No decomposition needed.

ORDER

Attributes : order_id, user_id, payment_method, purchase_date, points_earned, points_used, status
FDs        : FD10 (order_id → user_id, payment_method, purchase_date, points_earned, points_used, status)
CKs / PK   : {order_id}

user_id is a non-key foreign key to USER, but it does not determine any other attribute within ORDER. All non-key attributes depend directly on order_id. No decomposition needed.

USER

Attributes : user_id, email, username, password, date_created, shipping_address, telephone_number
FDs        : FD01 (user_id → email, username, password, date_created, shipping_address, telephone_number)
             FD02 (email → user_id)
             FD03 (username → user_id)
CKs        : {user_id}, {email}, {username}
PK         : user_id

email and username both determine user_id, but each is itself a complete candidate key. Therefore, neither creates a transitive dependency. Every determinant in the listed functional dependencies is a candidate key. No decomposition needed.

ORDER_PRODUCTS

Attributes : order_id, product_id, price_at_purchase, quantity
FDs        : FD14 ((order_id, product_id) → price_at_purchase, quantity)
CKs / PK   : {order_id, product_id}

The determinant (order_id, product_id) is the complete composite candidate key. Neither order_id nor product_id determines either non-key attribute independently within this relation. No transitive dependency exists. No decomposition needed.

WISHLIST_PRODUCTS

Attributes : wishlist_id, product_id, added_at
FDs        : FD15 ((wishlist_id, product_id) → added_at)
CKs / PK   : {wishlist_id, product_id}

The only non-key attribute, added_at, depends directly on the complete composite candidate key. There are no other non-key attributes that could create a transitive dependency. No decomposition needed.

RELEASE_ARTISTS

Attributes : release_id, artist_id, release_ordinal, release_artist_type
FDs        : FD16 ((release_id, artist_id) → release_ordinal, release_artist_type)
CKs / PK   : {release_id, artist_id}

Both non-key attributes depend directly on the complete composite candidate key (release_id, artist_id). Neither non-key attribute determines the other. No decomposition needed.

SONG_ARTISTS

Attributes : song_id, artist_id, song_ordinal
FDs        : FD17 ((song_id, artist_id) → song_ordinal)
CKs / PK   : {song_id, artist_id}

song_ordinal depends directly on the complete composite candidate key. There are no other non-key attributes and therefore no transitive dependency. No decomposition needed.

ADMIN

Attributes : user_id, admin_type, discount_percentage
FDs        : FD04 (user_id → admin_type, discount_percentage)
CKs / PK   : {user_id}

Both non-key attributes depend directly on user_id. Neither admin_type nor discount_percentage determines another attribute within the relation. No decomposition needed.

CONSUMER

Attributes : user_id, points_collected
FDs        : FD05 (user_id → points_collected)
CKs / PK   : {user_id}

There is only one non-key attribute, and it depends directly on the candidate key. No transitive dependency is possible. No decomposition needed.

WISHLIST

Attributes : user_id, wishlist_id
FDs        : FD12 (wishlist_id → user_id)
             FD13 (user_id → wishlist_id)
CKs        : {user_id}, {wishlist_id}
PK         : wishlist_id

user_id and wishlist_id determine each other, meaning each attribute is independently a candidate key. Both determinants are therefore superkeys, and no transitive dependency exists. No decomposition needed.

BCNF Decomposition

Listed below are the relations obtained after the 3NF analysis, examined to determine whether every non-trivial functional dependency has a superkey as its determinant and whether further decomposition is required to achieve BCNF.

The primary keys are bolded.

1. PRODUCT(product_id, release_id, format, price, product_description, stock) → satisfies BCNF
2. ARTIST(artist_id, artist_name, artist_description, artist_photo) → satisfies BCNF
3. RELEASE(release_id, title, record_label, genre, release_date, cover_photo, duration) → satisfies BCNF
4. SONG(song_id, song_name, song_duration) → satisfies BCNF
5. MODIFICATION(modification_id, admin_id, date_modified, type_of_modification, discount) → satisfies BCNF
6. ORDER(order_id, user_id, payment_method, purchase_date, points_earned, points_used, status) → satisfies BCNF
7. USER(user_id, email, username, password, date_created, shipping_address, telephone_number) → satisfies BCNF
8. ORDER_PRODUCTS(order_id, product_id, price_at_purchase, quantity) → satisfies BCNF
9. WISHLIST_PRODUCTS(wishlist_id, product_id, added_at) → satisfies BCNF
10. RELEASE_ARTISTS(release_id, artist_id, release_ordinal, release_artist_type) → satisfies BCNF
11. SONG_ARTISTS(song_id, artist_id, song_ordinal) → satisfies BCNF
12. ADMIN(user_id, admin_type, discount_percentage) → satisfies BCNF
13. CONSUMER(user_id, points_collected) → satisfies BCNF
14. WISHLIST(wishlist_id, user_id) → satisfies BCNF
15. R15 = {artist_id, album_id, song_id, product_id, order_id, modification_id} → satisfies BCNF

Final Normalized Design

After completing the normalization process from 1NF through 2NF and 3NF to BCNF, the following relations represent the final normalized relational design. All resulting relations satisfy BCNF, and no further decomposition is required.

USERS(
    user_id              PK,
    email                UNIQUE,
    username             UNIQUE,
    password,
    date_created,
    shipping_address,
    telephone_number
)

ADMINS(
    user_id              PK, FK → USERS,
    admin_type,
    discount_percentage
)

CONSUMERS(
    user_id              PK, FK → USERS,
    points_collected
)

ARTISTS(
    artist_id            PK,
    artist_name,
    artist_description,
    artist_photo
)

RELEASES(
    release_id           PK,
    title,
    record_label,
    genre,
    release_date,
    cover_photo
)

ALBUMS(
    release_id           PK, FK → RELEASES
)

SINGLE_RELEASES(
    release_id           PK, FK → RELEASES,
    duration
)

SONGS(
    song_id              PK,
    song_name,
    song_duration
)

PRODUCTS(
    product_id           PK,
    release_id           FK → RELEASES,
    format,
    price,
    product_description,
    stock
)

ORDERS(
    order_id             PK,
    user_id              FK → USERS,
    payment_method,
    purchase_date,
    points_earned,
    points_used,
    status
)

MODIFICATIONS(
    modification_id      PK,
    admin_id             FK → ADMINS(user_id),
    date_modified,
    type_of_modification,
    discount
)

WISHLISTS(
    wishlist_id          PK,
    user_id              FK → USERS, UNIQUE
)

ORDER_PRODUCTS(
    order_id             PK, FK → ORDERS,
    product_id           PK, FK → PRODUCTS,
    price_at_purchase,
    quantity
)

WISHLIST_PRODUCTS(
    wishlist_id          PK, FK → WISHLISTS,
    product_id           PK, FK → PRODUCTS,
    added_at
)

ALBUM_SONGS(
    album_id             PK, FK → ALBUMS(release_id),
    song_id              PK, FK → SONGS
)

RELEASE_ARTISTS(
    release_id           PK, FK → RELEASES,
    artist_id            PK, FK → ARTISTS,
    release_ordinal,
    release_artist_type
)

SONG_ARTISTS(
    song_id              PK, FK → SONGS,
    artist_id            PK, FK → ARTISTS,
    song_ordinal
)

MODIFICATION_PRODUCTS(
    modification_id      PK, FK → MODIFICATIONS,
    product_id           PK, FK → PRODUCTS
)

Conclusion

The final normalized design is very similar to the relational design created in Phase 2. Most of the relations obtained during normalization, such as USERS, ARTISTS, SONGS, PRODUCTS, ORDERS, MODIFICATIONS, and WISHLISTS, already exist in the Phase 2 design. The same is true for the subtype relations ADMINS and CONSUMERS and the main many-to-many relations.

Some relations, such as ALBUM_SONGS and MODIFICATION_PRODUCTS, were not directly produced by the functional dependencies because they only contain their key attributes. However, they are kept because they represent important many-to-many relationships in the database.

There is also a difference in the handling of releases. During normalization, duration was considered dependent on release_id, while the Phase 2 design stores it only in SINGLE_RELEASES. The Phase 2 structure with RELEASES, ALBUMS, and SINGLE_RELEASES is kept because it better represents the meaning of the data. Additionally, there is no point in storing the overall length of the album release if it can be calculated by adding up the length of each of its songs.

The residual relation R15 is also not included as a physical table. It was useful for the theoretical normalization process, but its six attributes do not represent one meaningful relationship in the actual database.

Overall, the normalization process confirms that the Phase 2 design is already well normalized. Therefore, the Phase 2 relational design will be kept for the following phases, and no major restructuring of the database is required.