2

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.

First normal form.

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

Italics denotes a key constraint.

R1 > R2 denotes a non-simple domain relationships such that the relation schema R1 has an attribute R2 whose domain constraint is described by the relation schema R2 (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?

1
9

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.

16
  • 1
    @Maggyero, it is a 1NF normalisation (and due to the structure of the unnormalized data, it is trivially also 2NF and 3NF) Jun 17 '20 at 6:36
  • 2
    @Maggyero, 2NF: All non-key fields depend on the entire key (trivial, as there are no tables with multi-field composite keys and non-key fields); 3NF: All field values depend only on the key, there is no correlation between non-key field values that must be maintained (also trivial in this case). Jun 17 '20 at 11:04
  • 2
    @Maggyero, it appears to be a one-to-many relation (each child belongs to one employee; employees that are a couple and have children together are not considered in the model and in the era when this article was written that could have been a valid solution). Jun 2 at 6:31
  • 3
    @Maggyero, The model depicted in Codd's example will treat different records in the children schema as different children as there is no indication anywhere that the childname attribute needs to be globally unique. And if it is not globally unique, then you just cannot tell if two records with the childname attribute value "Bart" refer to the same child or not and the only safe assumption that you can make is that they are different children. Jun 2 at 13:40
  • 2
    @Maggyero, not all models need the information but you also cannot make assumptions about information that is not part of the model. Jun 2 at 18:31
6

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.

8
  • Thanks for the Spotify link and the insightful remark on my album lacking an artist and my song lacking a track number. Regarding the extra associative relations album_track and artist_credit, I am not sure they are necessary since my normalized relations already have their domains.
    – Maggyero
    Jun 17 '20 at 0:17
  • Is the credit_role relation necessary? I would have removed it and replace the attributes (artist_id, song_id, role_id) of the relation song_artist_credit with (artist_id, song_id, role_name).
    – Maggyero
    Dec 13 '20 at 21:28
  • 1
    Consider a query where you are obtaining the list of songs where Madonna was the songwriter. How would you do that with role_name? You'd have to make sure that the names are used consistently and spelled the same way. Also, you wouldn't be able to fit as many keys into a data page (since a name is longer than an ID) which would increase total I/O. If you're okay with both of those, then it's not necessary.
    – John Wu
    Dec 13 '20 at 22:34
  • Ah okay, in other words your credit_role relation is a kind of enumeration type?
    – Maggyero
    Dec 14 '20 at 10:43
  • 1
    Exactly. It is a list of valid values. In SQL, we refer to this as a "Domain table."
    – John Wu
    Dec 14 '20 at 15:56
2

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.

30
  • Why are you avoiding composite keys (by excluding the foreign keys of the parent relations from the keys)?
    – Maggyero
    Jun 1 at 22:43
  • In Codd’s example above, is the relation between employees and their children one-to-many or many-to-many?
    – Maggyero
    Jun 1 at 23:08
  • @Maggyero: In Codds example there is a one-to-many relationship from employee to children.
    – JacquesB
    Jun 2 at 7:11
  • What makes you say that couples are not considered? Why would two records with the same childname attribute but different man# attributes in the children relation schema always denote two different children?
    – Maggyero
    Jun 2 at 9:31
  • @Maggyero: You have that backwards - if a couple have a child, the child have to be registered twice (one for each man#) so two different records does not always represent two different children.
    – JacquesB
    Jun 2 at 9:37
1

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.

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

  2. 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. Hierarchical DBMS • File Structure

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

  • Note the tree, it is horizontal Relational Model Fig 3(a) • Unnormalised Set

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

  • Note the same tree, it is vertical. Relational Model Fig 3(b) • Nnormalised Set

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. Relational Data Model for Maggyero

  • 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.
10
  • 1
    I admit that my question was a mess. Thanks for the clarifications and the great model. Shouldn’t an album also have zero or more artists, and one or more labels?
    – Maggyero
    Jun 5 at 2:13
  • You should also have a producer per album track as it can be different for each track (e.g. The Lion King: Original Motion Picture Soundtrack). Also the credited track artist or album artist is not always the performer, it can be the songwriter, so we may rename your relation Artist to Performer (e.g. The Lion King: Original Motion Picture Soundtrack).
    – Maggyero
    Jun 5 at 12:53
  • @Maggyero Whoa. That data model is just an example, from what I gleaned from your six variants. It is not fully researched, to cater for the entire industry. Eg. a song may be written by more than one SongWriter. But sure, post the full requirement, and I will respond with a data model that fulfils it. Jun 6 at 0:14
  • ‘Note the single key, the rest are physical pointers (red).’ So what prevents them for pointing to the same ‘Children Region’, i.e. two employees sharing the same children?
    – Maggyero
    Jun 6 at 16:24
  • 1
    @Maggyero 1) Your question now leads into the physical structure of the IMS (HDBMS) file, and its limits. Prevention was done by the HDBMS. 2) If two employees have the one child, the child record (not row) has to be duplicated. One of the explicit goals that IBM gave Codd was to overcome that limitation. Which he did, brilliantly (the RM does not duplicate such a child). Bill of Materials. Jun 6 at 21:55
0

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.

21
  • In the first example, you repeat the artist per song even though the artist is given by the album. This means you can have inconsistent data, e.g. 2 1 2 Bohemian Rhapsody would indicate that the song is by Pink Floyd despite the album is by Queen. This is the kind of "anomaly" normalization is supposed to prevent.
    – JacquesB
    Jun 1 at 18:05
  • @JacquesB No in the first example the artist is actually not given by the album because two artists can have an album with the same attributes, in the same way that in Codd’s example an employee is not given by a child because two employees can have a child with the same attributes. In other words, the keys of an album and a song are local keys, that is unique in the namespace of an artist; they are not global keys.
    – Maggyero
    Jun 1 at 21:25
  • DKNF is not relevant to 1NF or normalization to higher NFs from 1NF to 5NF & 6NF (lossless decomposition to components that natural join to an original). "data duplication" doesn't mean anything in particular; normalization to higher NFs improves designs in a way that can reasonably described as reducing duplication. Your use of these terms is neither clear nor sound. (And 1NF-normalizing a nested relation variable is not a way to get good designs. Nor is following a 50-yr-old seminal paper.) Again, suggest you follow a (good) textbook.
    – philipxy
    Jun 2 at 1:52
  • You have misinterpreted what Codd (poorly) said. Codd's "unnormalized" list of name-attributes pairs is NOT a set of relation variables. Each of your "unnormalized" name-attributes lists if taken as a set of relation variables--which you & others have--do NOT 1NF-normalize to the "1NF" designs you give. Rather, Codd's & your "1NF" designs are the 1NF of certain designs with attribute values RELATED IN A CERTAIN WAY to the "unnormalized" list of name-attributes pairs. Please edit your question per my comments. "I have applied this normalization procedure"--No; you have the wrong starting point.
    – philipxy
    Jun 2 at 2:27
  • @Maggyero: OK so album ID is only unique per artist, not across all albums. This means you can't have more than one artist on the same album (in the first example), since a different (artist_Id, album_Id) combination would represent a different album. But you can have multiple artist per album in the second example. This is not a question of normalization though, it is a question if you want your data model to allow multiple artists per album.
    – JacquesB
    Jun 2 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.