Create a multicomun unique index on State and SongInState
Put in the table create query
UNIQUE KEY `UniqueStateSong` (`State` , `SongInState`)
or if it's already created
ALTER TABLE `mytable` ADD UNIQUE `UniqueStateSong` ( `State` , `SongInState` )