Danny,
Might I add that artist-song is also n:n (one song, may artists): there's one who did it first, others can 'cover' the same song later (if 'cover' is the correct American term). Or even make a purely instrumental version, although you might argue if it is still the same song then (like in a library, is Harry Potter as a book and on DVD the same 'title' or a different one?).
Then we have the 'Best of the sixties' or 'Concert for Bangladesh'-type problems. Multiple artists on a CD.
And the translation problem, like in 'Do I have an English version of Edith Piaf's "La Mama"?'
And the duo's. You would want to be able to relate Paul Simon solo to the Simon of 'Simon and Garfunkel', so that Scarborough Fair turns up if you search for songs of Paul Simon.
And the CD-boxes. Multiple CD's in a box, so the number you're interested in is on CD #3.
And you might well be interested not only in the artist, but also in who (sometimes plural) wrote the text and composed the music (if known).
And, of course, the classical music problem. There must be lot of composers having written a Symphony #1, or an Etude in C or an Ave Maria. So title of a 'song' is not unique.
You might even have different recordings (with different conductors) by the New York Philharmonic of the same symphony. Do you consider that the same 'song' (or 'title', or however you want to call it in your data model)?.
All of this is far from trivial, I'm afraid.
Kees