Applying Edgar Codd’s 1NF normalization procedure

Question

In 1970, Edgar Codd published his landmark paper ‘A Relational Model of Data for Large Shared Data Banks’ where he defined relational databases as well as their normalization to first normal form (1NF) in section 1.4, page 381. It is a procedure for eliminating non-simple domains (domains whose elements are relations) from a set of relation schemata (i.e. a database schema) in order to allow simple two-dimensional array representations without pointers.

I have applied this 1NF normalization procedure to the following six database schemata modeling music recordings.

Italics denotes a key constraint.

R₁ > R₂ denotes a non-simple domain relationships such that the relation schema R₁ has an attribute R₂ whose domain constraint is described by the relation schema R₂ (i.e. it is a relation-valued domain). For instance in Codd’s example, we have the following non-simple domain relationships: employee > jobhistory > salaryhistory and employee > children.

Database schema 1

Unnormalized (non-simple domain relationships: artist > album > song):

• artist(artist_id, artist_name, album);
• album(album_id, album_title, album_date, song);
• song (song_id, song_title).

Normalized (1NF):

• artist(artist_id, artist_name);
• album(artist_id, album_id, album_title, album_date);
• song(artist_id, album_id, song_id, song_title).

Database schema 2

Unnormalized (non-simple domain relationships: artist > song > album):

• artist(artist_id, artist_name, song);
• song(song_id, song_title, album);
• album(album_id, album_title, album_date).

Normalized (1NF):

• artist(artist_id, artist_name);
• song(artist_id, song_id, song_title);
• album(artist_id, song_id, album_id, album_title, album_date).

Database schema 3

Unnormalized (non-simple domain relationships: album > artist > song):

• album(album_id, album_title, album_date, artist);
• artist(artist_id, artist_name, song);
• song(song_id, song_title).

Normalized (1NF):

• album(album_id, album_title, album_date);
• artist(album_id, artist_id, artist_name);
• song(album_id, artist_id, song_id, song_title).

Database schema 4

Unnormalized (non-simple domain relationships: album > song > artist):

• album(album_id, album_title, album_date, song);
• song(song_id, song_title, artist);
• artist(artist_id, artist_name).

Normalized (1NF):

• album(album_id, album_title, album_date);
• song(album_id, song_id, song_title);
• artist(album_id, song_id, artist_id, artist_name).

Database schema 5

Unnormalized (non-simple domain relationships: song > artist > album):

• song(song_id, song_title, artist);
• artist(artist_id, artist_name, album);
• album(album_id, album_title, album_date).

Normalized (1NF):

• song(song_id, song_title);
• artist(song_id, artist_id, artist_name);
• album(song_id, artist_id, album_id, album_title, album_date).

Database schema 6

Unnormalized (non-simple domain relationships: song > album > artist):

• song(song_id, song_title, album);
• album(album_id, album_title, album_date, artist);
• artist(artist_id, artist_name).

Normalized (1NF):

• song(song_id, song_title);
• album(song_id, album_id, album_title, album_date);
• artist(song_id, album_id, artist_id, artist_name).

Which of these six normalized database schemata makes more sense?

Answer 1

Both need some further normalization work if you want a fully normalized model.

However, it is either missing the notion of M:N relationship (first-class relationships), or it is insufficiently normalized, such that modeling an M:N relationship requires duplication, which makes it denormalized.

To get to further normalized database, we would model both entities and relationships using their own tables.

artist (artist_id, artist_name)
album (album_id, album_title, album_date)
song (song_id, song_title, song_duration)

songs_x_album (song_id, album_id)
artists_x_song (artist_id, song_id)

The first three are simple entity tables, and, the latter two are relationship tables, capturing the relationships without duplicating any other info from albums, artists, or songs.

artists_x_album can be derived from the above using a larger join.

Of course, due to the nature of relational queries, given a relationship table we can traverse an M:N relationship a_x_b bidirectionally from an a to its bs and also from a b to its as.

---

In some but not all cases relationship tables need their own id; not shown in the above (there are only foreign keys).

---

There is a lot more to consider, of course. Authoring a song and performing/publishing a song are potentially different, for example. Songs are sometimes released without an album.

Answer 2

You are missing a couple components in your model that represent the relationships between your artists, songs, and albums. These are sometimes referred to as associative tables.

1. Albums have numbered tracks, each of which is a song.
2. Artists can be credited with multiple songs.

So a normalized model might look like the following. Your basic tables:

artist (artist_id, artist_name)
song (song_id, song_name)
album (album_id, album_name)

And your associative tables:

album_track (album_id, song_id, track_number)
artist_credit (artist_id, song_id)

The associative tables embody the many-to-many relationships that others have pointed out.

Note that for some types of music, the above may not be enough. For example, for some kinds of electronic dance music, there is an artist credit for the album but not for the songs (e.g. a DJ who put together the album but did not write any of the songs). For that you might need three associative tables instead of two:

album_track (album_id, song_id, track_number)
song_artist_credit (artist_id, song_id)
album_artist_credit (artist_id, album_id)

And in addition maybe you want to keep track of what role each artist had in a song, e.g. if they sung or wrote or played the bongos. For that you would add a role attribute to the artist credit table for songs and a domain table:

album_track (album_id, song_id, track_number)
song_artist_credit (artist_id, song_id, role_id)
album_artist_credit (artist_id, album_id)
credit_role (role_id, role_name)

These are just the basics. There is a lot more complexity in the music industry, and you would have to decide how much to build into your model. To give you an idea, I would recommend you review the work of someone who has already dealt with this, e.g. take a look at the Spotify object model.

Answer 3

There are two questions which are actually separate:

1. What are the data and relationships you want to represent in the database.

2. How to represent this as normalized tables.

Your question is not really about normalization, it is about deciding on a data model. You present 6 different data models, and then the normalization of each. The normalizations seem correct given the data models, but most of the data models does not make sense.

(I assume in your notation ">" indicates a one-to-many relationship, i.e. "artist > album > song" means one artist to many albums and one album to many songs.)

Variant 1: One artist can have multiple albums and one album have multiple songs. The seem like a reasonable model, although it would not be able to express if multiple artists collaborated on the same album or song.

Variant 2: A song can occur on multiple albums BUT an album can only have one song. This is not a very useful model!

Variant 3: An album can have multiple artists BUT an artist can only have one album.

Variant 4: A song can have multiple artists BUT an artist can only have one song!

Variant 5: A song can have multiple artists and an artist can have multiple albums BUT again there can only be one song per album.

Variant 6: A song can occur on multiple albums and an album can have multiple artists BUT an album can have only one song.

Of these 6 variants, only variant 1 would be reasonably useful, if a bit simplistic.

The problem with the rest of the variants is you really need many-to-many relationships if you want to express more information. If you want to represent an album having multiple artists, then you also need to represent that an artist can have multiple albums. So you need a many-to-many relationship between artists and albums.

You might be missing this in the analysis, because Codd's example does not have any many-to-many relationships, all the connections are one-to-many.

This might not be immediately obvious to a modern reader, since the connections in his diagram (fig 3a) does not have the cardinality (one-to-one, one-to-many, many-to-many etc.) explicitly stated as we probably would today. But the context of the example is a hierarchical database which only support one-to-many relationships. In any case, the ambiguity is resolved in the normalized form (fig 3b) where it is clear that there is a one-to-many relationship between employee' and children'.

It might seem weird that his data model does not consider that two employees could have a child together. Maybe it is a payroll database where the number of children might be important for benefits, but whether two employees shared the same child would be irrelevant. Or maybe he just didn't consider the possibility. In any case this is just an example.

For the music recordings database you also have to decide on a data model. Be aware that there is no "correct" data model for a given domain. A data model is always a simplified view of reality and depends on the requirements on your database and application.

Can an album have multiple artists? Can a song have multiple artists? Can an album have songs which are not by the same artist as the album artists? If a song occur on multiple albums is this the "same" song? These are "business" decisions which depends on the purpose of the database. A record shop might need to decide on a single artist per record in order to organize the records alphabetically per artist. A digital music library does not have such a constraint and might instead record artists per song rather than album. Should you include producers, song writers, session musicians etc? It all depends on the business requirements of the database.

Assuming a simple model where an album only have a single artist and all songs on the album by the same artist, the model presented as variant 1 would be sufficient.

A more fine-grained model where each song can have multiple artists might look like this:

Album -(one to many)-> Song <-(many to many)-> Artist

And this would be a normalized representation:

Artist: (artist_ID(PK), artist_name)

Album: (album_ID(PK), album_title, album_date)

Song: (song_id(PK), album_ID(FK), song_title)

Artist_Song: (song_ID(FK), artist_ID(FK)) 

(I prefer synthetic priary keys (artist_ID, album_ID etc.) because there could be multiple artist with the same name, multiple albums with the same title and so on.)

You should clarify what data model you want to represent before starting to normalize.

Answer 4

Understanding & Approach

You need to take the approach that this is an established paper, from 50 years ago, and try to understand it, as it is (as it was, fifty years ago).  

• Note that the terms are dated
• Note that in fifty years, the academics and theoreticians who allege to serve this space, and write textbooks on the subject, have not articulated this. They are stuck in their pre-1970 Record Filing Systems.

---

In 1970, Edgar Codd published his landmark paper ‘A Relational Model of Data for Large Shared Data Banks’ where he defined relational databases as well as their normalization to first normal form (1NF) in section 1.4

No.

• That is not "1NF”. Codd has not named it as such, and 1NF is already defined
  • 1NF: the domain is Atomic, not divisible, wrt the platform
• If anything, that Fig 3(b) Normalised Set is the definition of Relational Key Normal Form,
• with the pre-requisite Fig 3(a) Unnormalised Set being the Hierarchic Normal Form.  

Which unfortunately none of the academics and theoreticians have articulated, in fifty years of various textbooks and filth.

---

It is a procedure for eliminating non-simple domains (domains whose elements are relations) of a collection of relations in order to allow a simple two-dimensional array representation without pointers.

No.

1. Codd uses the term domain no less than 83 times.  Without contradicting the core meaning, it does mean distinctly different things in different contexts.  Here non-simple domain means a repeating group or subordinate rows, which is deployed in a child relation.

2. The goal or purpose is not to "allow a simple two-dimensional array representation without pointers", that is simple enough to obtain via a SELECT, from any set of relations. That is just a capability of the Relational Model, not a goal.

3. The goal at that point, is to demonstrate logical Relational Keys, and how to achieve them.

4. The overall goal of the Relational Model is to treat data logically, 100% logically, in all aspects of logic.*

   • Unfortunately those who write textbooks are blissfully stuck in the little that they can understand, which is the physical, so they add a physical frame with RecordIDs.

---

I have applied this normalization procedure to the following variants of collection of relations modeling music recordings.

No, you have not applied that Normalisation procedure.  

• Codd requires that Keys are made up from the data, yours are not.
• You have RecordIDs, which are physical pointers, which are expressly prohibited.  Use of such additional fields will severely cripple the modelling exercise; complicate the coding; and degrade performance.
• Codd requires the pre-requisite Hierarchic NF, which means arranging the collection into trees (Directed Acyclic Graphs or DAGs), which you have not.  Instead of six possibles, give us one tree that is correct.
• Then perform Relational Key NF on that.

Yes, you have six variants.  No, you do not have one collection, you have six collections.

Variants

That is a completely separate question, regarding data modelling, using a given collection of data (not six), which are in bad shape.  You have not even specified which attributes you intend as Keys.  It has nothing at all to do with understanding Codd's paper, or understanding how to obtain Relational Key NF.  It is simply,

which of these six variants is best ?

No criteria for choosing better or best is given, so it is a free-for-all with the responders trying to help, and no Answer is correct.

The attributes are not good, so you are better off collecting more relevant data, and asking a single data modelling question.

Another way of stating that is, your six variants are merely an attempt to understand:

• the hierarchy that Codd has given in Fig 3(a),
• and his Normalisation Fig 3(b)
• using a collection of your own, and six possible combinations of such.
  Again, you are best advised to understand what Codd has given in his example, using his collection, first.

Codd’s Relational Model

You need to understand a bit more re your snapshot fragment of the RM. Since you are asking questions about it, first I provide the file structure of the best-known HDBMS of the era, IBM's IMS.

• Note the single access key, the rest are physical pointers (red)
• The internal Keys prevent duplication of records (they were not rows) within the region.

Now an explanation of Codd’s Fig 3(a). Straight out of the Hierarchic Model, but perceived logically.

• Note the tree, it is horizontal

And now, an explanation of Codd’s Fig 3(b).  

• Note the same tree, it is vertical.

Relational Data Model

If I cut to the chase, if I use data from the real world (ie. your six variants, normalised, plus relevant Identifying data), this is what the finished product would look like.  This is an example, as per your six variants, it is not a fully researched industry data model.

• there are three hierarchies: SongWriter; Producer; Artist
• notice the Relational Keys, which define the hierarchies

Note

• The Standard for Relational Data Modelling since 1983 is IDEF1X. For those unfamiliar with the Standard, refer to the short IDEF1X Introduction.

Answer 5

Let us take a few instances of my first normal form (1NF) relation schemas variant 1:

artist (artist_id, artist_name)
KEY(artist_id)
1 Queen
2 Pink Floyd

album (artist_id, album_id, album_title, album_date)
KEY(artist_id, album_id)
1 1 A Night at the Opera 1975
1 2 News of the World 1977
2 1 The Dark Side of the Moon 1973

song (artist_id, album_id, song_id, song_title)
KEY(artist_id, album_id, song_id)
1 1 1 Love of My Life
1 1 2 Bohemian Rhapsody
1 2 1 We Are the Champions
2 1 1 Time
2 1 2 Money

Everybody in this post claims that the previous relation schemas prevent many-to-many relations and are not normalized beyond 1NF and therefore promote data duplication, while their ‘associative’ relations schemas do not have these issues:

artist (artist_id, artist_name)
KEY(artist_id)
1 Queen
2 Pink Floyd

album (album_id, album_title, album_date)
KEY(album_id)
1 A Night at the Opera 1975
2 News of the World 1977
3 The Dark Side of the Moon 1973

song (song_id, song_title)
KEY(song_id)
1 Love of My Life
2 Bohemian Rhapsody
3 We Are the Champions
4 Time
5 Money

artist-album (artist_id, album_id)
KEY(artist_id, album_id)
1 1
1 2
2 3

album-song (album_id, song_id)
KEY(album_id, song_id)
1 1
1 2
2 3
3 4
3 5

But as I understand it, both my relation schemas and their relation schemas allow many-to-many relations and are normalized in domain–key normal form (DKNF) since their domain dependencies and key dependencies logically imply their constraints, as the only constraints are key dependencies, and therefore prevent data duplication. However their relation schemas have two extra schemas and therefore more data, for no apparent benefit.