home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / database / theory / 473 < prev    next >
Encoding:
Internet Message Format  |  1992-09-11  |  2.6 KB
  1. Path: sparky!uunet!sun-barr!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!rpi!bu.edu!dartvax!kip-sn-49.dartmouth.edu!user
  2. From: carl.pedersen@dartmouth.edu (L. Carl Pedersen)
  3. Newsgroups: comp.databases.theory
  4. Subject: Re: ordered collections
  5. Message-ID: <carl.pedersen-110992103841@kip-sn-49.dartmouth.edu>
  6. Date: 11 Sep 92 14:51:22 GMT
  7. References: <cdk.715362552@neptune> <DAVIDM.92Sep2112813@consilium.com> <cdk.716057364@neptune>
  8. Sender: news@dartvax.dartmouth.edu (The News Manager)
  9. Followup-To: comp.databases.theory
  10. Organization: Dartmouth College
  11. Lines: 42
  12.  
  13. On 1 Sep 92 15:49:12 GMT, cdk@neptune.dsc.com (Colin Kelley) said:
  14. > 
  15. > Is there a standard way to implement ordered collections in a relational
  16. > database that would allow for random insertion?  You could always have a
  17. > sequence number field to remember the ordering, but if you want random
  18. > insertion, you may run out of bits in this sequence number and not be able
  19. > to insert a new entry between two others.
  20.  
  21. I'm embarrased to say that Masterson's solution fooled me.  I thought the
  22. only
  23. problem with it was that you couldn't do a bunch of inserts at the same
  24. time -
  25. something I often need to do.
  26.  
  27. My solution to this is just as you imply:  A floating point sequence
  28. number.  New records get assigned a sequence # between the adjacent two.  I
  29. tell my DBMS to require this key to be unique, so it blows up if I run out
  30. of bits.  In one version of this, I occasionally renumbered - which isn't
  31. *too* hard using ORACLE.
  32.  
  33. I suppose this is the "standard" technique, but it's ugly and not fully
  34. general.  
  35.  
  36. Aside from the fact that current systems don't seem to have a solution for
  37. this, I'm not sure there *is* a good solution that is really general and
  38. performs well.
  39.  
  40. You need to be able to insert between this row and that row.  How do you
  41. specify which row?  Primary key?  What if there is no natural primary key? 
  42. OK, so you put it between the 4th and the 5th one already there, but now
  43. you have changed the ordinal positions of all subsequent records.  Is that
  44. OK?  Maybe.  It's hard to see, though, how this could be efficient for
  45. large collections.
  46.  
  47. It's easy enough to come up with a scheme for inserting efficiently, and
  48. finding the next record.  You could just have a link to the next record,
  49. based on unique record id - physical address if nothing else.  The problem,
  50. I think, is *specifying* which record you mean.  If the only way to say is
  51. something like, "Put this after the millionth record", we have a problem.
  52.  
  53. Maybe this just doesn't come up for collections that large.  So far, all of
  54. my applications involve only a few hundred records.
  55.