Friday, June 29, 2007

Databases and objects

I have long been a fan of Fabian Pascal's database ramblings (not his political and economical ones, the man has absolutely no clue on those). Yes, the relational theory is actually set algebra, and therefore a relational database is the most complete and powerful type of database, bar none. Object databases, hierarchical databases (registry), network databases (objects) - they all have problems which simply do not exist in an RDB.

However, I was re-reading an article about the object / relational mismatch problem - Interoperability happens and I got to this part:

Developers simply give up on relational storage entirely, and use a storage model that fits the way their languages of choice look at the world. Object-storage systems, such as the db4o project, solve the problem neatly by storing objects directly to disk, eliminating many (but not all) of the aforementioned issues; there is no "second schema", for example, because the only schema used is that of the object definitions themselves. While many DBAs will faint dead away at the thought, in an increasingly service-oriented world, which eschews the idea of direct data access but instead requires all access go through the service gateway thus encapsulating the storage mechanism away from prying eyes, it becomes entirely feasible to imagine developers storing data in a form that's much easier for them to use, rather than DBAs.

So... an application could simply forget about the whole database thing and completely take over the storage and management of objects. It can also handle the problem (mentioned in that article) of other parts of the same enterprise wanting to use the data by exposing it through services, so that nobody can have access to the underlying objects (and thus nobody needs to change their own application if this application is refactored). True, such an "object database" lacks a lot of the powerful advantages of a relational one, like ad-hoc querying - but maybe for this application, You Ain't Gonna Need It.

Interesting idea. I think I read somewhere that Robert Martin starts what are to everyone else obvious database applications by ignoring that part... because he might not need a database after all, and he definitely does not need it to start with. I never understood that until now :)

Wednesday, June 13, 2007

Sudoku and TDD

For the last few months, I've been trying on and off to write a program to solve a Sudoku game. The "easy" ones are easy, you just use a rudimentary algorithm:


  • each cell has a list of possible values associated with it

  • start by associating all values 1-9 to each cell

  • repeat until solved:


    • for each cell, remove any values already present in the same line, column, or box




By this process of repeated elimination you can solve a lot of the "easy" tables. However, this algorithm is too limited and it will go into an infinite loop if you have a situation where, for example, two cells in the same row can accept values 1 and 5, but at this point you have no way of knowing which is which.

Now, of course the solution to that problem is simply a recursive backtracking algorithm:


  • save the current state

  • pick one value and try to solve the rest of the table; if it worked, all is good; if not, go back to the saved state and try the next value



The devil, however, is in the details. I would go into some weird state where suddenly I had a row with two cells having the same value... which of course ruined everything else. And debugging something which is five recursion levels deep and goes through 81 cells each time... I wasn't willing to spend all that effort for a stupid problem, especially with the number of programs already available solving it.

That was the case until one night when I was really bored and wanted to program something for fun :) But I had also just read yet another article on Test-Driven Design and decided to try it. It took me a few hours that night, and a few more hours the next morning, but I managed to make it work. Hehe. That's a cool feeling, especially since, while I have tried TDD before, this was the first time I actually felt it helped.

That's code I'd take to an interview :)