wiki:Normalization

Version 16 (modified by 232012, 7 days ago) ( diff )

--

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

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

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
Note: See TracWiki for help on using the wiki.