Re: Surrogate Keys: an Implementation Issue

From: paul c <toledobythesea_at_oohay.ac>
Date: Sat, 22 Jul 2006 05:25:34 GMT
Message-ID: <iFiwg.215381$iF6.124032@pd7tw2no>

Paul Mansour wrote:
> paul c wrote:

>>...

> In the below discussion, I'll use "table" and "row" for this
> intermediate level, and resort to "relation" and "tuple" when refering
> to the logical model. Considers the following "table":
>
>
> ID AT SNO SNAME STATUS TS
> -- --- --- ----- ------ --
> 1 0 S1 Smith 20 1
> 2 0 S2 Jones 10 1
> 3 0 S3 Blake 30 1
>
>
> And the relation that the DBMS can produce from it:
>
> SNO(pk) SNAME STATUS
> --- ----- ------
> S1 Smith 20
> S2 Jones 10
> S3 Blake 30
>
>
> Now consider making an assignment to the relation that changes the
> status of supplier
> S2 to 40. One way to implement this in the intermediate level is to
> append a new "row" to the "table":
>
> ID AT SNO SNAME STATUS TS
> -- --- --- ----- ------ --
> 1 0 S1 Smith 20 1
> 2 0 S2 Jones 10 1
> 3 0 S3 Blake 30 1
> 2 1 S2 Jones 40 2
>
>
> Now, the DBMS just needs a way to convert the "table" to a relation.
> This is easily done by analyzing the SNO "column" and the AT (append
> "type", to distinguish inserts, updates, and deletes) "column" to
> produce:
>
> SNO(pk) SNAME STATUS
> --- ----- ------
> S1 Smith 20
> S2 Jones 40
> S3 Blake 30
>
> Note that in some sense, the "log IS the database"
>
> Now the DMBS should also, I think, be a able to produce this relation:
>
> SNO SNAME STATUS TS
> --- ----- ------ --
> S2 Jones 10 1
> S2 Jones 40 2
>
> with the system supplied time stamp TS as a primary key. I don't think
> this any way violates any relation principles, though finding a way to
> specify this relation in the relational algebra I'm not sure about.
>
>
> Now, if I allow the user to change the supplier key from S2 to S20, we
> get the following
> "table":
>
> ID AT SNO SNAME STATUS TS
> -- --- --- ----- ------ --
> 1 0 S1 Smith 20 1
> 2 0 S2 Jones 10 1
> 3 0 S3 Blake 30 1
> 2 1 S2 Jones 40 2
> 2 1 S20 Jones 40 3
>
> Now the DMBS must use the ID column rather than the SNO column - ID
> being an immutable identifier, in order to produce the current state of
> the associated relation:
>
>
> SNO(pk) SNAME STATUS
> --- ----- ------
> S1 Smith 20
> S20 Jones 40
> S3 Blake 30
>
>
> or the "update history" of supplier S20:
>
> SNO SNAME STATUS TS(pk)
> --- ----- ------ --
> S2 Jones 10 1
> S2 Jones 40 2
> S20 Jones 40 3
>
> Thus if we allow changes to a primary key, we must have some other
> immutable id, and I don't see how the timestamp helps here, though
> maybe in more conventional implementations it would.
>

paul m,

Thanks for the concrete example, I know it's a PITA typing all those spaces to make the columns line up but it sure has eased my neck-ache. Not sure I'd agree with the choice of terms, but anyhow, the example seems enough to follow a good part of what you're driving at.

I had been thinking that what you call an 'intermediate' level (intermediary scheme?) could correspond to what TTM calls a base relvar where one could project out ID and AT to get a TTM-style virtual relvar or 'view', but I see now that's not exactly what it means and candidates and surrogates aren't involved - eg., if SNO S1 is deleted, say by mistake, and then re-inserted the dbms would need to supply a new ID value (assuming there is no TS attribute) with the other attributes' values presumably still depending on the 'original' SNO value of S1.

For me, this all brings up vague questions which I don't have any definite comments about so I'll have to ponder them, to see how they might fit with normalization, the relational operators and maybe even temporal databases (when you suggest that the "log is the database", I can't help but think temporal), just exactly how the logical-physical distinction might be quantified as opposed to qualified and what-have-you. For example, if TRM is some kind of 'intermediate model', should all implementations specify just what their particular 'models' are? I'm not even sure that the example isn't verging into second-order predicates. Maybe this is just talking about the RT equivalent of anthropology's 'missing link'. So even if they're vague questions, I have a feeling they are big ones but they are in risky territory, not only because I'm weak at RT theory but because they touch on subjects that serious philosophers have been agreeing to disagree about for a century or more. Maybe Edgar Codd had thought long and hard about this and was far-sighted in not going into great detail about just what a table is, eg., just using the 'atomic' label to describe his role and domain values!

(Still trying, after many, many misfires, to send this quick reply for now. May not be able to reply further very soon as the cable internet connection here has gone flaky and we're waiting for a new line, but I think even though it's partly about 'implementation' this is a very interesting example, at least for somebody like me whose main experience is physical and who comes here because his theoretical knowledge is weak. I think this has the makings of a good thread, perhaps you should re-title it without the surrogate mention.)

p

ps: I think this example might also be veering away from the kind of 'foreign key' your original post mentioned. No criticism about that, and this is likely going in a different direction than you intended but it reminded me of an indirection technique I wanted to implement many years ago. The question goes something like this: 'what is the cheapest way to assign one thousand employees to a different department?'. Without violating the information principle, is it possible to re-assign them by updating only one tuple? The only approach to a solution I remember wondering about involved views where some attributes were read-only but their values were mutable, rather than immutable. Received on Sat Jul 22 2006 - 00:25:34 CDT