問題2-66

DBは、今日取り組んだような集合を扱うためのソフトウェアだと捉えると、どのような手続きでそれを表現できるか、ということを実験的に実装するのが問題2-66です。例題では、テーブルに収められているレコードのキーが、ただのリストとして管理されている場合について述べられていますが、これをツリー化すると、select文の実行速度を対数的に上げることができます。下記の手続きは、ツリー集合のelement-of-set?を少しだけ改変したものです。

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) #f)
        ((equal? given-key (key (car set-of-records)))
         (car set-of-records))
        ((< given-key (key (car set-of-records)))
         (lookup given-key (left-branch set-of-records)))
        ((> given-key (key (car set-of-records)))
         (lookup given-key (right-branch set-of-records)))))

かなり昔に読んだ『データベース実践講義』を再読してみたいなと思わせてくれた問題でした。