Making a relational database

This is a discussion on Making a relational database within the Tech Board forums, part of the Community Boards category; I am thinking of writing a tag engine for files using a relational database, but I can't find much information ...

  1. #1
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555

    Making a relational database

    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.

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    You could try using sqlite3 the dll is only around 250K. I dont know how well it performs speed-wise tho.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555
    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.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by OnionKnight View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. literature database: help with planning
    By officedog in forum C++ Programming
    Replies: 1
    Last Post: 01-23-2009, 11:34 AM
  2. Creating a database
    By Shamino in forum Game Programming
    Replies: 19
    Last Post: 06-10-2007, 01:09 PM
  3. Replies: 10
    Last Post: 05-18-2006, 11:23 PM
  4. Developing database management software
    By jdm in forum C++ Programming
    Replies: 4
    Last Post: 06-15-2004, 04:06 PM
  5. Making a Simple Database System
    By Speedy5 in forum C++ Programming
    Replies: 1
    Last Post: 03-14-2003, 09:17 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21