If someone wants to write a program to recognise songs by melody (mobile apps like that exist), one would need some huge data sample for this. I'm wondering whether something like this exists (at least for, say, classical music), in what format is the data available and what license restrictions apply if I wanted to add melody data from currently popular music?
It seems like http://echoprint.me/ is the service you want:
Echoprint is a music fingerprint or music identification service. It listens to music signals and tells you what song is playing. It’s backed by a huge database of music that grows with the community and further partnerships. On launch we’ve partnered with Musicbrainz.
Does it work “over the air”, identifying songs over a microphone?
Yes - Echoprint has been designed from the ground up for OTA, and our informal tests have demonstrated many successful and promising results for this scenario. The system still needs a little more tuning, however, and is under continued development to further improve accuracy and performance.
Data license (at http://echoprint.me/data):
Echoprint data (for ingestion into your own server) is available under the “Echoprint Database License.” The intent of the license is simple: Use our data for whatever you want (commercial or non, research, personal use); If you download our data and then add to it, you are required to contribute data back to us. ; There is a good reason for this. We want Echoprint to be able to resolve every song in the universe. If you add to the database of resolvable tracks, the Echoprint community needs to know about it.