Andy @ Work

Thursday, December 01, 2005

Topological Sort

Yesterday my domain layer was having problems determining the order to commit objects to the database. The problem was foreign key referential integrity. It seems that SQL Server doesn't support a mechanism to delay the checking of foreign key constraints until the transaction is committed. If it did you could perform your inserts in any order, commit the transaction, and THEN let SQL check the foreign keys.

For example say we have four classes:



class Customer {...}
class ShippingAddress {...}
class Order {...}
class OrderItem {...}



and lets say that the underlying Order table has a foreign key to both the Customer and ShippingAddress tables, and that the OrderItem table has a foreign key to the Order table. If I create all these objects in one transaction (for the sake of my point), I have to make sure that I insert the Customer object before Shipping Address, both of which have to be inserted before the Order object which has to happen before the OrderItem object(s).

So I did a bit of reading in Martin Fowlers Patterns Of Enterprise Application Architecture and it seemed that Unit of Work combined with some Attributes/MetaData and a Topological Sort would be required.

Essentially I created an Attribute called ForeignKeyAttribute that accepts a single Type in its constructor. This was my way of signalling that one class had foreign key dependencies on one or more other classes.



class Customer {...} // No foreign keys

[ForeignKey(typeof(Customer))]
class ShippingAddress {...}

[ForeignKey(typeof(Customer))]
[ForeignKey(typeof(ShippingAddress))]
class Order {...}

[ForeignKey(typeof(Order))]
class OrderItem {...}



I then created a collection whose Enumerator would treat the collection as a Directed Acyclic Graph (DAG) and perform a Topological Sort (ie the order that the Enumerator returned items).

So when Commit() is called on my Unit of Work object, each object Type that is in my 'to be inserted' collection is added to my DirectedAcyclicGraph object, and I then enumerate through the graph, to work out in which order objects in my 'insert collection' should have their Commit() method called.

Later on I'll post some better code samples to demonstrate my point better.

0 Comments:

Post a Comment

<< Home