Making a relational database

[OnionKnight]

I am thinking of writing a tag engine for files using a relational database, but I can't find much information regarding the implementation of an efficient database. Supposedly there are books out there on this topic, but I haven't found anything.
I try to stay away from using RDBMSes like MySQL and PostgreSQL because I am looking for mostly simple CRUD-functionality and I don't want to require users installing other software just to run mine which I'm planning to write in C. Connecting and querying would also add a bit overhead, though I'm not sure how drastically it compares to that of reading and writing to files if you're connecting to your own computer.

The only thing I can think of is O(n) algorithms for handling simple SQL queries. If there's a selection it would most likely need to be sorted too adding giving it an additional O(n*log n) using quicksort on the resulting relation.

[mike_g]

You could try using sqlite3 the dll is only around 250K. I dont know how well it performs speed-wise tho.

[matsp]

For a searchable database, you need some sort of "key/index" table. This is usually arranged as a Balanced binary [1] tree - this you should be able to find with google, or in a decent algorithms book.

Using indexing (binary tree search= on different databases, you can improve the search by a fair amount, because it is O(log2(n)). Of course, insertion is slightly worse when the tree needs to be re-balanced, but that shouldn't be very frequently.

Once you have your (reduced) list of items, then you may need to sort the selected items if there is an "order by" statement in the SQL query.

I think there are some "miniSQL" implementations, which may be good to study or use. SQLite is one of those: http://sqlite.org/


[1] Most actual implementations contain some level of "tolerance" to unbalance, so that the tree doesn't need to be unnecessarily rebalanced, for exampel during a sequence of insertions or deletions, you don't want to rebalance the tree until it gets "quite unbalanced". The criteria for "quite unbalanced" is can of course be quite difficult to figure out, but allowing a certain level of unblance is definitely sane.

Of course, using a completely unbalanced binary tree can lead fo the tree becoming a linked list instead of a tree [if elements are inserted in order].

--
Mats

[OnionKnight]

I forgot to mention that I could consider using an RDBMS if it can be compiled into the program so I might just go with SQLite. The theory behind relational databases seems a bit too broad to get into right now.

[matsp]

I forgot to mention that I could consider using an RDBMS if it can be compiled into the program so I might just go with SQLite. The theory behind relational databases seems a bit too broad to get into right now.

Yes, the inner workings of Databases (whether they are relational or not) is a complicated matter, and not something you can easily grasp in a few days or weeks.

--
Mats