Simplest way to create a tiny database app in linux

I'm looking to create a very small cataloguing app for personal use (although I'd open source it if I thought anyone else would use it). I don't want a web app as it seems like overkill to have an application server just for this - plus I like the idea of it being standalone and sticking it on a USB stick.

My Criterea:

Interface must be simple to program. It can be curses-style if that makes it easer to code. My experience with ncurses would suggest otherwise, but I'd actually quite like a commanline UI.
Language doesn't really matter. My rough order of preference (highest first):
- Python
- C
- C++
- Java
- I'll consider anything linux-friendly
I'm thinking sqlite for storage, but other (embeddable) suggestions welcome.

Has anyone done this sort of thing in the past? Any suggestions? Pitfalls to avoid?

EDIT:

Ok, it looks like python+sqlite is the early winner. That just leaves the question of which ui library. I know you get tkinter for free in python - but it's just so ugly (I'd rather have a curses interface). I've done some GTK in C, but it looks fairly un-natural in python. I had a very brief dabble with wxwidgets but the documentation's pretty atrocious IIRC (They renamed the module at some point I think, and it's all a bit confused).

So that leaves me with pyqt4, or some sort of console library. Or maybe GTK. Thoughts? Or have I been too hasty in writing off one of the above?

Solution

I vote for pyqt or wx for the GUI. (And second the Python+sqlite votes to answer the original question.)