Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/18259
標題: 多鍵語赫序法則式的檔案庫系統對於部份吻合查詢的特性研究
作者: 蘇東興
SU, DONG-XING
關鍵字: ROTHNIE;多鍵語赫序法則式;LOZANO;LIN LEE;DU;檔案庫;部分吻合查詢;隨意性
出版社: 應用數學研究所
摘要: 
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 的冪次時,我們的猜測法能用來設計出最理想的多鍵語
赫序法則。
URI: http://hdl.handle.net/11455/18259
Appears in Collections:應用數學系所

Show full item record
 
TAIR Related Article

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.