VIC Mail for the Commodore VIC20 is a database for storing addresses.  The thing I find interesting, but certainly not uncommon for this era of software / hardware, is that the program stores the records on a tape drive one at a time as you enter them.