Linkwood Development

Trees in SQL: Nested Sets and Materialized Path

2005-03-03T04:56:00.000-08:00

Whilst searching the internet for methods of storing hierarchies in a database I came across possibly the best example I have ever seen.

Vadim Tropashko's article, entitled the same as the subject of this post, talks us through a hybrid hierarchy storing method for SQL databases. A cross between nested sets and materialized paths produces a method of uniquely numbering a node in a hierarchy by using binary fractions. When I read this the benefits seemed immediately apparent, all node manipulation based on atomic integer operations all factored by binary logarithm (base 2).

Further more I was unable to find any other examples of this sort of hierarchy in use anywhere else, even MSDN suggests using methods which appear to be inferior to this one. MSDN only appears to scribe about adjacency lists, a method which is undoubtably performs, but requires an awful lot of (nested) SQL to work with.

After reading Vadim's posts, I decided to create some conceptual maps based on what I had read to fully understand the idea.

Vadim's code and proof of concept was all, unfortunately for me, in Oracle syntax, so a quick bit of conversion over to Transact-SQL syntax and I had created a fully operational example.

In the top pane of my Visual Studio screenshot you can see the SQL to generate the view, the center pane holds the result set and the lower pane the source information (also depicted is a method of working optimistic concurrency, with CreateStamp, UpdateStamp, DeleteStamp).

Harnessing the power of hierarchies in SQL has been a side-fetish for me now for the past 2 or 3 monthes as the necessity to implement something like this in my work has been under increasing demand. My work on this is as yet unappreciated by my colleagues. I'm likely to keep it a secret until people have a use for it, sure enough they will do, such hierarchies have already been in heated discussions, with my managers unsure of how to cope with such a complex technical implementation. My view is its a relatively complex method but one which is preferable to a bodged job.

I'm sure fellow developers in the world have always thought to 'do something better if they were doing it for personal gain', well my work on this could well end up being just that.

I'm just pondering on the potential for the suitability of this type of hierarchy in semantic web style applications, which is somewhere I seriously need to do lots of reading up on.

Very very cool.

Open Product Taxonomies and The Semantic Web

2005-02-02T01:31:00.000-08:00

With my recent ramblings on product categories, less than a month or 2 ago, I have stumbled across the discovery which appears to be taking alot of people by storm, The Semantic Web.

A system of classification for anything? Sounds ideal! I think this is the field that I'm going to specialize in as I grow older.

After reading How Google beat Amazon and Ebay to the Semantic Web by Paul Ford, the thoughts of such semantic systems make me very excited! Working with such a diverse set of interconnected data/ontologies, that have the capacity to be linked and referenced by other ontologies to create a mass of data, with the potential for exponential growth is enough to make my toes curl!

Do such semantic ontologies already exist for describing the predicate links between subjects and objects such as products, manufacturers, suppliers and retailers? Well I'm still looking into that, but the idea of an 'Open Product Taxonomy' is very exciting and could push benefits for retail systems development, which is my current field.

Obviously developing anything like this for my present company is a bit of a pipe dream, but is definitely something I'd consider playing with in my spare time, which at the moment is severely restricted.

Optimistic Concurrency and Synchronisation

2004-12-20T06:02:00.000-08:00

An interesting, obvious and totally overlooked problem cropped up the other day in the office... the problem of synchronising deleted records with remote databases.

Our implementation is a bit freakish, with what could be called (but are designed nothing like) 'data warehouses' feeding off of a centrally located database.

If implemented correclty, this model can serve to be totally rewarding, our implementation, I fear, is far from rewarding.

Anyway, the problem exhibited is that when we delete records from the central database, these deleted records need to be forwarded to the data warehouses so that they can be deleted there as well where appropriate.

This complication was totally overlooked in our implementation, and a half-baked solution has been concocted over much collusion and semi-implemented.

I was theorising on a method of allowing concurrency at the same time as allowing synchronisation, and it seemed fairly obvious that a database-wide strategy is required for identifying new records, amended records and deleted records.

All of the above can be done with time stamps, nice, simple, time stamps.

Below are the fields which will exist in every database table in my conceptual database model:

Key {
! = Can be null
}

CreateStamp Date
AmendStamp Date
DeleteStamp Date !

The create stamp is set the first time the record is inserted, nice, simple, clean and effective. At the same time, the Amend stamp is set to the same date as the create stamp, if the two match then the record has obviously never been modified.

The amend stamp is updated when the record is changed, thus the create and amend stamp are no longer equal, resulting in a record which can be identified as amended.

The delete stamp is different, it is set when the record is deleted, along with the amend stamp which is set at the same time to the same value. The delete stamp can be set back to null, effectively undeleting the record, as long as the amend stamp is updated to the time of undeletion.

This allows a much greater level of synchronisation, as when a data warehouse requires to synchronise with the remote database, it simply gets all the record with an amendment time greater than its last synchronisation time. If the delete stamp is not null, the record (as long as it has no dependancies) are deleted at the data warehouse, or stored as deleted, whichever.

A record with a deleted stamp set can safely be deleted whence all data warehouses have a synchronised stamp greater than the deleted stamp. This would be a batch purge function.

Concurrency by default use of a data adapter and a command builder in .NET, is enforced strictly by comparing all mapped fields in the where clause. This is costly CPU cycles enforcing this very strict evaluation. Specifying a where clause on the amend stamp only is, in my oppinion, vastly superior. As long as the amend stamp in the disconnected data matches the record in the database, the data can safely be updated; else the user can be prompted for a abandon, overwrite or comparison process.

There are two slight concerns in my theory however, the synchronisation of time between different domains/data warehouses. All date/times would have to be UTC, another method of conformity. The second concern would be concurrency between data warehouses and a central data source. If two data warehouses update data to their local databases away from the central database, batch processing would have be performed on all remote data warehouses at once whence they are ready to reconcile with the central database to identify concurrency conflicts. A second set of time stamps could be introduced for each record, including an indicator as to the origin or holder of the source data, and the central time stamps provided by the origin, which are only updated if the application updating the database is identified as the datas root source.

Interesting, no?

Conformity

2004-12-20T05:38:00.000-08:00

ISO standards are a key asset in allowing inter-operation between multiple organisational entities.

I mentioned in my last blog that I'm performing some conceptual modelling of a database structure which is globalised, ontological and simple.

I was casually glancing an eye over the operation of Froogle, the shopping search engine provided by google. It had a merchants information page, where instructions could be found on how to get your product data onto froogle.

I noticed that these feeds conformed to ISO standards, which is where I had a sudden realisation. This is definitely the key to designing future systems, allowing a system the capacity to talk to other systems... allowing froogle to canvas an online product catalogue would be extremely impressive- an attractive prospect to many potential clientel.

This should be BLATANTLY obvious to anyone working in this industry for a surmountable period of time, however I'm only young, and at 21, I find these quite major details overlooked by similar professionals with ALOT more experience than me.

The first step I took at implementing ISO standards was currencies, and remodelled my conceptual currency table to the following:

Key {
! = can be null
PK = Primary Key
FK = Foreign Key
}

Currencies {
cu_ID PK Fixed Unique
cu_ISO Industry Standard ISO-4217
cu_ISO_Unicode Industry Standard ISO-4217
cu_Global_ID ! FK Language Entity
cu_Rank
CreateStamp
AmendStamp
DeleteStamp !
}

The undoubtable benefit of this is automatic exchange rate computation. There is probably an XML web service somewhere (I think I may have already found one, but I can't recall bookmarking it) that reports all of the exchange rates to a base rate.

Consequentially, I looked at other standards I could conform to, and languages was an obvious optimization:

Languages {
la_ID PK Fixed Unique
la_ISO_1 Industry Standard ISO-639-1
la_ISO_2 Industry Standard ISO-639-2
la_Rank
la_Lang_ID ! FK
CreateStamp
AmendStamp
DeleteStamp !
}

If you're wondering what the 'Rank' fields might be about, its an aggregate field which is to be the result of a database wide aggregate process on the associated records usage, this will result in a 'most frequently selected' functionality in the user interface; It will be user adjustable.

My next blog, which I'm about to write, will be about optimistic concurrency and the usage of the (Create/Amend/Delete)Stamp fields, including their usage as a method of synchronisation.

Standard XML Reporting Schema

2004-11-19T02:49:00.000-08:00

After a brief Googling session, I can't appear to find any reporting schema standards where XML is concerned. The main complication appears to be that reports are totally diverse and are different for each business need.

The main reason I desire a standard reporting schema is the portability of presentation. After a reporting XML schema is defined, it can be easily reinterpretted by applying XSLT transformation. This would suitably accomodate my needs where a report has to be presented in a rich context, e.g. HTML, or in a standard fixed width text format for printing from a till receipt printer. Either way, the underlying data source is the same, its just the transformation schema applied to it which dictates its presentation.

This could be classed as an 'ideal' implementation, something I know we're not interested in by the company I work for.

But I forsee the benefits of the potential application independance, after all, additional layers of abstraction are always commendable.

Automated IRC Bot Hierarchical Object Model

2004-11-17T05:29:00.000-08:00

I was talking to a chap on channel #slack of Quakenet the other day, where he described the implementation of his IRC bot's internal address list (aka IAL). He said it was a 4 dimensional value array. However, since it was PHP implementation, the array could be indexed by string, hence some hashing must have been involved.

Updating the IAL would have its 4 dimensions walked thusly:

[Server]->[Channel]->[Alias]->[User Particulars (e.g. 'Modes')]

PHP supports this hashing natively, or so I've read, but I jest that it may not be the most ideal solution, especially when you want to perform statistics analysis, mostly because of the lack of association between different users, and the difficulty involved with implementing such associations in a multi dimensional array. Aggregate walking would have to be performed from the server dimension, matching all identical aliases in all the seperate channels, etc to identify a single user and the channels that they are in.

As such, I theorised the following object model.

One thing to note before we continue, when I refer to a 'clone' or 'clones', it actually means a particular user under a particular alias on a particular server. Multiple 'aliases' may appear under the same hostname (shared internet connections, for example), but they still have to be uniquely identifiable.

An ideal addition to this model would be logical associations between different 'clones', by having the bot hold an internal user list of whom it recognises (and their associated hostmasks in standard hostmask based syntax). The logical group of users (assembled by either manually or done by automated analysis), once concatenated together could be subject to a series of instant statistical evaluations designed to be performed on either a group of users or a group of channels.

Likewise for duration based statistics reporting periods, this data could easily be stored in XML, with seperate files representing hours, days (ideal, in my oppinion) or weeks. The structure would break away from the previous paradigms I've seen where all information is associated with the channel and instead associates it with the user. This may introduce a processing overhead for when the user simply wants to view a conversation on a particular channel- as it is the users structure which will be walked in order to recreate the channel log.

The reactive structure would be where all the model is controlled, reacting to messages received by the server. As its all hashed, the lookup would be almost instantenous. A join message would be parsed by first checking only the hostname of the user, evaluating what server the message was received from, then transverses the clone relationship based on the alias identified for that hostname for that server. It then associates the channel, its particulars (e.g. permissions) in a 'userchannel' class, which would have a composite relation to the channel (by transversing the Server->Channel relationship based on the server message from the root). The relationship is then fully complimented by automatically adding the user to that channels 'clones' collection.

Automation is the key to the hierarchies smooth operation. The above diagram doesn't depict the key locations where cyclic references would occur, but it will be most likely on the channels 'clones' collection, where the contained objects store a reference back to the channel in their 'userchannels' collection.

This is still, all only theory. As a personal project, it could be a little bit cumbersome with my current time constraints, especially when all of the client-server message logic would have to be written. But as is true with majority of frameworks, with the model in place it can be easily and intuitively expanded.