Re: how to build a database from scratch

On 2006-12-08, vc wrote:

> I think that it is pretty obvious that global lock acquisition
> ordering is hardly practically possible because the transaction
> read/write sets are not generally speaking known beforehand.

True. However, there are some applications where you can count on such things. One example would be a remote smartcard transaction, because you can guarantee referential integrity between any set of permanent identifiers stored on the card by just assigning the identifiers yourself and performing initial cryptographic authentication over the whole set; search by the user is generally limited to lookup on one of the keys or inputing checksum protected account numbers which are only used for blind summation. None of the typical user requests calls for anything but a singleton lookup and/or (logical) update on a set of keys.

Also, even if you can't rely on something like this, you can offer an option to declare the sets and then utilize them on top of a more general DBMS. If you want to incentivize your users, you can even guarantee higher acquisition priority to a transaction which has declared the sets or which has a form which enables the sets to be deduced statically.

> Also, are not you confusing global lock ordering with the wait-for
> graph deadlock avoidance technique?

Kinda. You should say techniques, plural, because any policy which guarantees that one or more of the Coffman conditions is a negative invariant, cyclicity of the wait-for graph being one of them, is enough to guarantee deadlock-freeness. Resource ordering is indeed a crude example of this more general class of algorithms.

-- 
Sampo Syreeni, aka decoy - mailto:decoy_at_iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2