home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / scheme / 2817 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  6.2 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!spool.mu.edu!olivea!mintaka.lcs.mit.edu!zurich.ai.mit.edu!jaffer
  2. From: jaffer@zurich.ai.mit.edu (Aubrey Jaffer)
  3. Newsgroups: comp.lang.scheme
  4. Subject: database in Scheme
  5. Message-ID: <JAFFER.92Dec22170313@camelot.ai.mit.edu>
  6. Date: 22 Dec 92 22:03:13 GMT
  7. Sender: news@mintaka.lcs.mit.edu
  8. Organization: M.I.T. Artificial Intelligence Lab.
  9. Lines: 163
  10.  
  11. I have written the system described in this message.  If other people
  12. are interested in using this system, I may be able to convince my
  13. employer (which is not MIT) to release it for public use.  If you are
  14. interested, please send me a description of what you might use it for.
  15.  
  16. ======================================================================
  17. WB is a disk based, sorted associative array package integrated into
  18. the Scheme implementation SCM.  These associative arrays consist of
  19. keys and values which are strings of length less than 256 bytes.
  20. Associative arrays can be used to form a MUMPS style database which
  21. can be used to implement standard record structures without auxiallary
  22. files (see example below).
  23.  
  24. Basic operations are creation, destruction, opening and closing of
  25. diskfiles and arrays, insertion, deletion, retrieval, successor, and
  26. predecessor (with respect to dictionary order of keys).  Functional
  27. application of find-next, deletion, and modification over a range of
  28. consecutive key values is supported.
  29.  
  30. Multiple associative arrays can be stored in one disk file.
  31. Simultaneous access to multiple disk files is supported.  A structure
  32. checker, garbage collector are included.  A repair program and
  33. ram-disk type file (for temporary structures) are in developement.
  34.  
  35. The current WB implementation has a file size limit of 2^32 * block
  36. size (currently 2048) = 2^43 bytes (8796 Gbytes).  We currently run WB
  37. with file sizes of several hundred Mbytes.  WB does its own memory and
  38. disk management and maintains an in core cache of recently used
  39. blocks.  The WB implementation adds about 45 Kbytes to the size of
  40. SCM.
  41.  
  42. WB is implemented using a B-tree variant.  B-trees give slower access
  43. than hashing but are dynamic and provide an efficient determination of
  44. successor and predecessor keys.  All operations are O(log(n)) in the
  45. size of the database.  B-trees are commonly used by database systems
  46. for implementing index structures.  B-trees are optimized for using
  47. the minimum number of disk operations for large data structures.
  48. Prefix and suffix compression are used for storage efficiency.
  49.  
  50.            MUMPS Style Database Phone Book Example
  51.  
  52. (open-seg 5 "mydata" 2)            ;opens a previously created file.
  53. (define pb (create-db 5 #\T "phone-book")) ;create an array called
  54.                     ;"phone-book" which will
  55.                     ;contain the phone book
  56.                     ;records.
  57. (define pi (create-db 5 #\T "phone-index"))    ;create an array called
  58.                     ;"phone-index" which we will
  59.                     ;use for indexing by phone
  60.                     ;number.
  61. (define lni (create-db 5 #\T "lastname-index"))
  62.                     ;create an array called
  63.                     ;"lastname-book" which we will
  64.                     ;use for indexing by last name
  65. (define record-number 0)
  66.  
  67. ;;;MAKE-NAME is a routine which concatenates its arguments together
  68. ;;;separated by null characters.  This assures that the arguments act
  69. ;;;as independent subscripts.
  70.  
  71. (put! pb (make-name record-number "LN") "Doe") ;last name
  72. (put! pb (make-name record-number "FN") "Joe") ;first name
  73. (put! pb (make-name record-number "PN") "5551212") ;phone number
  74. (put! pb (make-name record-number "AD1") "13 Hi St.") ;street address
  75. (put! pb (make-name record-number "CITY") "Podunk")
  76. (put! pb (make-name record-number "ST") "NY")
  77. (put! pb (make-name record-number "ZIP") "10000")
  78. (put! lni (make-name "Doe" record-number) "")
  79.                     ;This adds index entry so that
  80.                     ;(next lni (make-name "Doe")) 
  81.                     ;will find the record with
  82.                     ;complete information.
  83. (put! pi (make-name "5551212" record-number) "")
  84.                     ;similarly for looking up by
  85.                     ;phone number.
  86.  
  87. ;;; Note we put the record number into the key.  This is so that we
  88. ;;; can index records for more than one "Doe".
  89.  
  90. (define doe-rec
  91.   (get-subscript
  92.    (next lni (make-name "Doe"))        ;returns the a name which
  93.    2                    ;includes the record number of
  94.                     ;the record.
  95.  
  96. (get pb (make-name doe-rec "PN"))    ;returns Doe's Phone number.
  97.  
  98.             SCHEME DATABASE CALLS
  99.  
  100.    (open-seg seg filename mode)                Procedure
  101.  
  102. Seg should be a non-negative number.  Opens the database seg in
  103. filename and returns seg if successful, #f otherwise.  The database
  104. seg will be read-only if the mode argument is 0.  It will be
  105. read-write if the mode argument is 2.
  106.  
  107.    (close-seg seg)                    Procedure
  108.  
  109. Closes database seg seg and the file containing it.
  110.  
  111.    (make-seg seg filename block-size)            Procedure
  112.  
  113. Makes a new empty database seg of name filename.  #t is returned
  114. of creation was successful, #f if not.  Use open-seg to get the
  115. new seg.
  116.  
  117.    (open-bt seg blknum)                    Procedure
  118.  
  119. Returns a bt-handle open to seg number seg, block number blknum.  If
  120. no such block exists or is not a root block #f is returned.
  121.  
  122.    (create-bt seg dir)                    Procedure
  123.  
  124. Creates a new root block in seg seg of type dir and returns a
  125. bt-handle open to it.
  126.  
  127.    (get han key)                    Procedure
  128.  
  129. Returns a string of the value associated with key in the bt which han
  130. is open to.  Returns #f if key is not in the bt.  Key is a string.
  131.  
  132.    (next han key)                    Procedure
  133.  
  134. Returns the next key in bt han or #f if none.
  135.  
  136.    (prev han key)                    Procedure
  137.  
  138. Returns the previous key in bt han or #f if none.
  139.  
  140.    (rem! han key)                    Procedure
  141.  
  142. Removes key and it's associated value from bt han.
  143.  
  144.    (rem han key)                    Procedure
  145.  
  146. Removes key and it's associated value from bt han only if key is
  147. present.  Returns #t for success, #f for failure (not present).
  148.  
  149.    (rem* han key1 key2)                    Procedure
  150.  
  151. Removes keys (and their associated values) between (including) key1
  152. and (not including) key2 from bt han.
  153.  
  154.    (put! han key val)                    Procedure
  155.  
  156. Associates key with val in the bt han.
  157.  
  158.    (put han key val)                    Procedure
  159.  
  160. Associates key with val in the bt han only if key was previously
  161. empty.  Returns #t for success, #f for failure.
  162.  
  163.    (create-db seg typ name)                Procedure
  164.  
  165. Returns a B-tree whose name has been entered in the root directory.
  166. Type should be one of
  167.     (define DIR-TYP #\D)
  168.     (define IND-TYP #\T)
  169.  
  170.    (open-db seg name)                    Procedure
  171.  
  172. Returns the B-tree whose name has been entered in the root directory
  173. or #f if not found
  174.