物件導向資料庫查詢最佳化之研究

Abstract

本論文針對物件導向資料庫(OODB)的查詢最佳化(Query Optimization)作 探討,我們提出一個新方法,並且在我們實驗室設計的物件導向資料庫管理 系統(EODB)雛形(Prototype)上驗證.我們提出一個新觀念,對於有參考( Reference)關係的兩個類別(Class) ,我們可以有兩種運算方式,連結它們 之間的關係,而且端看所給的條件來決定使用何種運算.這個觀念可以使執 行查詢的成本變小.對於物件導向資料庫的查詢最佳化,我們的新方法是將 整個物件導向資料庫的綱要(Schema)視為一張大圖,從此大圖中擷取與查 詢相關的資訊而成為一張小圖,我們再從這張小圖上,運用前面所提到的新 觀念,去決定連結順序(Association Order),以達成查詢最佳化.這個方法 能為物件導向庫提供所有應有的運算,能解決因參考階層 (Reference Hierarchy)的特性對查詢最佳化處理器造成的影響,同時也能解決因繼承 階層(Inheritance Hierarchy)對查詢最佳化處理器的影響,這是以前的研 究方法所缺乏的.對於我們所提出的查詢最佳化處理器(Query Optimizer) 之製作方法及相關的物件導向資料庫模型在本論文亦作了詳細介紹. A new method for query optimization in object-oriented database systems is proposed in this thesis. We propose a policy for query optimizer to link two classe that have reference hierarchy. We can link these two classes either by association or inverse-association, dependent on the query predicate. By this policy, the cost of query paln can be reduced. By viewing the whole database schema as a graph, our method can extract the query-related information to form a subgraph. In this subgraph, the association order for optimizing the query is decided by utilizing the new policy to link two classes. The proposed method can be applied to any object-oriented database systems. All the operations that object-oriented database systems need are provided, including restriction, projection, join, union, difference, and intersection. It can also optimize a query that contains reference hierarchy and inheritance hierarchy. These features can not be achieved by previously proposed method. Finally, the implementation of our method is presented to show it is feasible.