Abstract
本論文主要探討部分吻合擷取及區間擷取的最佳檔案結構之設計問題。我們首先針對垂直區間查詢去發展許多檔案組織法則的數學模式並推導其數學效益公式。根據這些效益公式，我們提出一個叫做MMI 的逐步最佳演算法並且證明，在某些條件下，利用MMI 法可求得針對垂直區間查詢的最佳檔案組織法則。我們同時證明MMI 演算法也可用以設計在一般條件下，針對垂直區間查詢的近似最佳檔案組織法。其次我們探討在可平行擷取的多磁碟系統中設計最佳的檔案區段分配問題。我們證明任一卡迪生乘積檔案庫針對部分吻查詢的最佳區段分分配設計問題相當於此檔案本身的一個子檔案，稱為剩餘子檔案，的最佳區段分配設計問題。根據此證明結果，我們指出剩餘型態的卡迪生乘積檔案是最難設計最佳的區段分配法則的卡迪生乘積檔案。於是我們試著解決一種非常重要的剩餘型態檔案，稱為k-元卡迪生乘積檔案，的最佳區段分配設計問題。我們提出許多可以使一個k-元卡迪生乘積檔案具有最佳區段分配的充分條件。利用這些充分條件，我們進一步提出一個啟發式法則，稱為循環赫序演算法，用以設計一般的卡迪生乘積檔案庫的近似最佳區段分配設計。並經由實驗證明循環赫序分配法的確非常的有效。此外，根據多餘儲存可以提高檔案效益的查詢及系統可靠度的觀念，我們提出兩個多餘儲存演算法分別用以設計k-元及一般卡迪生乘積檔案庫對部分吻合查詢的最佳區段分配法則。因為根據我們所證明的區段分配問題之簡化結果，我們的方法只須重覆儲存剩餘子檔案便可達到最佳擷取效益，因此避免了一般當使用多餘檔案儲存法時最嚴重的時間-空間消長問題。關於針對垂直區間查詢的區段分配設計問題，我們則探討並提出許多使廣義磁碟模式分配法具有最佳效益的充分條件。最後，我們探討有時間性的關連式資料庫的時間合併運算處裡問題。根據平面線段相交搜尋的技術，排序赫序的觀念，以及群序赫序的觀念。我們提出三種不同的資料結構用以有效的解決合併運算處理中最重要的時間區間相交搜尋問題。