Music services (and really any sort of entertainment databases with genres) are becoming prime candidates for graph databases. Decibel is the latest company to realize that the RDBMS they started with is not going to be the most efficient model for data as they scale out their application.
"Relational databases are good for some things, but when you try to twist it around to be a graph database, they get very upset with you"
-- Evan Stein, Decibel founder
Stein also says that they need their database to go 20 to 30 times faster for their partner Jugglit, an all-around entertainment discovery service.