How to store a database inside an Arduino?

Question

I'm working on project where I use an Arduino with a Bluetooth module and my cellphone Samsung Galaxy S II with Android OS. The idea of the project is to send some commands from my cellphone to the Arduino via Bluetooth. I want to include a database into the Arduino so that when I send login information from my cellphone, the Arduino will check the database and if the login information matches, it retrieves some data from the database and sends it to my cellphone.

How can I store a database inside the Arduino? Should I purchase an external EEPROM or RAM? And how can I deal with that database (adding, deleting and manipulating data)?

My Ardunio is of type UNO, BTW.

Answer 1

Just for simple login you don't need a database, you probably need just a simple table.

Consider first of all that usually EEPROMs allow from 1000 to 100000 write cycles. It means, if you write a single cell more than 100000 you have an high probability that your cell die, you cannot write it anymore.

The question is, how many logins are allowed? It is a all matter of choosing the right data structure and understand what is the amount of required memory.

Knowing the computational power of Arduino: If logins are just 2 .. 50, a simple list would be sufficient. Insertion at the end is O(1), deletion is O(n), lookup is O(n). A linked list however will allow you to reduce the number of writes for deletion to a constant small value.

If logins are more, 50 .. 1000, a sorted array with binary search is enough. Insertion is O(n), deletion is O(n), lookup is O(n log n). However the number of writes is O(n) both for deletion and insertion, and since writing is slow and can burn cells, it depends on the number of updates you want to do.

If logins are 1000 or more a binary tree is good. Insertion is O(n log n), deletion is O(n log n), lookup is O(n log n). The good thing is that for insertion and deletion you just need a small, constant number of writes.

Also an hashtable is good, but they usually use more memory. Insertion is averaged O(1), deletion is averaged O(1), lookup is averaged O(1). Insertion and deletion requires only a small constant number of write operations, less than a binary tree. As I said, this data structure uses more memory, speed comes at a cost.

You don't need a real relational database, but probably if you need too much users, you need an external EEPROM.

Of course, you have to save this data in a flash memory, internal or external, or you'll lose the database when you reset or power down the machine.

We can also say that you don't need to store the username and password, you can just store an hash of the password and username. If the hashed username and password exists, then you can allow login. In this way you can use fixed size memory and less memory. You can use MD5, it is the Android phone that have to send the MD5 hash, that is, 16 bytes, so the Arduino must only check if that MD5 hash exists in the list of users there, for example. And this is easy and fast.