MicroSpec VIC Data Manager (MicroSpec LTD, 1982) - It's hard to believe I've come across another (quite capable) database program for the Commodore VIC20 in the last couple days.  This one isn't quite as fancy as Mini Jini Record Keeper, but it's still impressive considering the limited hardware of a VIC20, although it does require at least 8K RAM.  The manual is included inside the archive.

** There's a C64 version of this program, but I only have the manual, so if you have a copy, please consider getting in touch if you want to share.

Mini Jini Record Keeper (1983 Jini Micro) for the Commodore VIC20 - This isn't exactly a relational database, but it could certainly be considered a full featured database for it's time, especially considering the hardware it was running on! 

You'll need to do a few steps to get it running in an emulator, because it was originally in cartridge format.  Inside the archive there is a readme.txt that explains what to do, along with the full manual in PDF format.  If you want to know more about where this came from, and how it was converted, check out this forum thread over at the VIC20 Denial forum.

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.