home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / database / theory / 438 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  3.0 KB
  1. Path: sparky!uunet!elroy.jpl.nasa.gov!ames!agate!triplerock.CS.Berkeley.EDU!mao
  2. From: mao@triplerock.CS.Berkeley.EDU (Mike Olson)
  3. Newsgroups: comp.databases.theory
  4. Subject: Re: ordered collections
  5. Date: 2 Sep 1992 00:48:40 GMT
  6. Organization: University of California at Berkeley
  7. Lines: 63
  8. Message-ID: <181318INNqt3@agate.berkeley.edu>
  9. References: <cdk.715362552@neptune> <Btwxq5.MBC@world.std.com>
  10. NNTP-Posting-Host: triplerock.cs.berkeley.edu
  11.  
  12. In <Btwxq5.MBC@world.std.com>, edwards@world.std.com (Jonathan Edwards)
  13. writes
  14.  
  15. > In article <cdk.715362552@neptune> cdk@neptune.dsc.com (Colin Kelley) writes:
  16. > 
  17. > >Recently someone posted a question about implementing FIFO queues in a
  18. > >relational database.  I'm interested in something even more basic:  ordered
  19. > >collections.
  20. > 
  21. > HAH! I'm glad you asked that - this is my personal favorite reason why
  22. > the relational model is a toy (i.e., unhelpful for my real-world needs).
  23. > 
  24. > A general solution that doesn't require large-scale reorganization ever is to
  25. > assign some unique key to every row and use that as an 'address' to build a 
  26. > doubly-linked list via forward and backward 'link' fields. But then you lose
  27. > the ability to have the ordering 'visible' to relational operators.
  28.  
  29. well, if that's all that's holding you back...
  30.  
  31. i think you're confusing a paucity of types and extensibility with a
  32. fundamental flaw in the relational model.  i can produce ordered sets
  33. in postgres in a straightforward way.
  34.  
  35. here's the strategy:  use arbitrary-precision (eg, bcd) decimal numbers,
  36. or arbitrary-length text strings, as the ordering key for the set.  make
  37. this an attribute of every record.  define the following functions inside
  38. the data manager:
  39.  
  40.     after : record-id -> key
  41.     between : record-id, record-id -> key
  42.     before : record-id -> key
  43.  
  44. when you insert a record, you say
  45.  
  46.     append my_relation (name = "mike", age = 30,
  47.                 setloc = between(337, 445))
  48.  
  49. where 337 and 445 are unique record identifiers that identify records in
  50. my_relation; the database system generates these for me when i insert a
  51. new record.
  52.  
  53. my functions after, before, and between identify the two records adjacent
  54. to the new record, and generate a new unique key by examining the setloc
  55. attributes of those records.  i can write the functions to use two-phase
  56. locking to exclude concurrent updates to the same location in the list,
  57. so the solution will be correct.  a btree or hash index can make it fast
  58. to locate existing records and generate new keys.
  59.  
  60. using this strategy, you can still see the ordering using algebraic
  61. operators, you can exploit it (or not) when you retrieve values, and
  62. you can guarantee ordered set semantics.
  63.  
  64. note that i haven't violated the relational model here; the only reason
  65. that i can do this and you can't is that my database system lets me
  66. define new types and operators whenever i want.
  67.  
  68. there's no question that relational databases are ill-suited for some
  69. applications, but this isn't necessarily one of them.
  70.  
  71.                     mike olson
  72.                     project sequoia 2000
  73.                     uc berkeley
  74.                     mao@cs.berkeley.edu
  75.