I would just do it lazily
If the user wants to play the song, you can request iPod DB, in particular for this song and, possibly, for the entire song βAlbumβ if the user deletes the album. This will require two database queries before playing each song, but you can check if it is enough, etc.
You can also put the β sync β option in the application using iPod DB , but as a choice for the user, telling the user a βwarningβ that it might take some time, maybe even give him an estimate of the time for the size of his particular library.
I think that from a usability / battery point of view, this would be better than querying the entire database every time the application starts or even in the background.
Goles source share