多鍵語赫序法則式的檔案庫系統對於部份吻合查詢的特性研究

Abstract

Rothnie 與Lozano最早提出利用多鍵語赫序法則（Multiple Key Hashing簡稱MKH ） 來建造多鍵語檔案庫，不久Lin Lee 與Du更明確地指出利用多鍵語赫序法則所建造的 檔案庫，由於能將類似的記錄（record）分配在同一個區段（bucket）中，所以非常 適合部份吻合查詢。本文將導出利用多鍵語赫序法則所建造之檔案庫系統對於部分吻 合查詢的效益公式，並且提出隨意式檔案庫系統（haphazard file system ）的觀念 ，同時也導出該類檔案對於部分吻合查詢的平均效益公式。我們將證明多鍵語赫序法 則式的檔案庫系統，對於部分吻合查詢的平均回覆時間，將比隨意式檔案庫系統來得 快。 在某些條件限制下，我們發現設計一個多鍵語赫序法則式的最佳檔案庫系統的問題， 與尋找最小N 字元（minimal N-tuple ）的問題，有極密切的關連。更進一步地，我 們提出一個猜測（heuristic ）方法，用來設計一組非常有效的多鍵語赫序法則，計 算機模擬實驗的結果顯示出我們所提出來的猜測方法，經常可以找到非常理想的多鍵 語赫序法則。我們將說明Aho 與Ullman所提出的鍵欄長度分配（Attribute Length A ssignment ALA ）式的檔案庫系統與多鍵語赫序法則式的檔案庫系統之關連。當檔案 庫所用到的總區段數剛好是2 的冪次時，我們的猜測法能用來設計出最理想的多鍵語 赫序法則。