適於平行擷取的檔案庫安排法之研究

Abstract

在本篇論文，們將探討如何一個事先設計好的多鍵語檔案庫系統(multi-key file system) 案排到兩套磁碟系統(twodisk system) 中，以方便部份 合查詢(partial match query) 的平行擷取(parallel retrieval) ，進而縮短查詢的平均回覆時間 (average response time)。 首先我們耐回顧Du 與Sobolewski 在1982 年所提出的磁碟模式安排法(Disk Modulo Allocation Method)。接著，再介紹我們所發展的最小伸展樹安排法(Short Spannin g Path Allocation Method)，或簡稱MST 案排法，及較短伸展路徑安排法(Short Sp anning Path Allocation Method)，或簡稱SSP 案排法，然後我們做了四個客觀的實 驗，針對卡迴生乘法當案庫(Cartesian Product Files) 及一般檔案結構(geneal f iles) ，利用我們的最小伸展樹安排法和較短伸展路徑案排法，與磁碟模式安排法及 案排法及隨意案排法之效益分別做一番比較，結果顯示：在30 姐卡迪生乘法檔案庫 中，MST 案排法有12 組未達到最佳(optimal) 的案排效益，而SSP 案排法總共有24 組檔案均達到最佳的案排效益。而對於一般的檔案結構，我們的實驗證明了MST 安排 法和SSP 案排法都優於隨意案排法。在此，我們必須特別強調：研碟模式安排法只能 適用於卡迪生乘法檔案庫的安排，而我們的方法卻可用來安排任意的檔案結構。 參考文獻 1.Chang,C.C.,Lee,R.C.T.,and Du,H,C.,(1980):Some Properties of Cartesian P roduct Files, Proc. ACM-SIGMOD 1980 Conference, Santa Monica, Calif., May 1980,pp.157-168. 2.Du,H.C., and Sobolewski, J.S.,(1982):Disk Allocation for Cartesian Produ ct Files on Multiple Disk Systems, ACM Trans. Database Systems, Vol. 7, Ma rch 1982, pp.82-101. 3.Fisher,R.A.,(1936):The Use of Multiple Measurements in Taxonomic Problem ,Annals of Eugenics, Vol. 7, 1936, pp.179-188.