Your choice should depend on the type and amount of data this database will handle. Can you give us some info on that?
In my college days, I create a random access database using files in Pascal and also in C. There was no SQL involved: everything was done using file operations (open, close, rewrite, reset, read, etc). It was pretty neat. I guess the same techniques can be used with Arduino in a SDcard.
However, if your database is small and has only very simple types, then EEPROM might be a good choice, since there is no need for extra hardware.