益於查詢的檔案結構之設計

Abstract

本論文文主要是探討多屬性檔案結構之設計。此主題又可依查詢的性質分為益於部份 吻合查詢及益於正交區間查詢兩大問題。 在益於部份吻合查詢的檔案結構設計方面，我們首先提出GREEDY METHOD 來設計一個 新的檔案結構……GREEDY FILE ，同時導出此檔案的效率公式，並以定理證明其績效 絕不次於OPTIMAL CARTESIAN PRODUCT FILE。接著，我們再提出另一種檔案結構，稱 作Ｘ檔案，它是由許多OPTIMAL CARTESIAN PRODUCT FILE子檔案所構成的檔案；GREE DY FILE 與CARTESIAN PRODUCT FILE皆為其特例。我們從最佳的Ｘ檔案的探討中發現 一個非常有趣的性質，即是一個績效越佳的Ｘ檔案結構，其BUCKET中所包含的RECORD 越“CLUSTER”且其每個子檔案的OPTIMAL CARTESIAN PRODUCT FILE 設計也越“SIMI LAR ”。 在益於正交區間查詢的檔案結構設計方面，本論文主要是討論CARTESIAN PRODUCT FI LE。我們先是導出其效率公式，使得在正交區間查詢上的效益評估由繁而簡；然後再 利用此簡單的效率公式提出一個啟發式的方法來找到益於正交區間查詢的最佳CARTES IAN PRODUCT FILE。