"The King's Arrival" was first noted down about the same time as the others, but the reference to the King dates it much earlier. The link I noticed was the "as good as you" line - which is shared by "John Cuckoo" and "The King's Arrival", but isn't in any of the DT songs.