This paper addresses the problem of physical query processing for large object-oriented, temporal knowledge bases. The major tasks being investigated are how to generate the space of all possible execution plans for a given knowledge base query and how to traverse this space in order to choose an efficient execution plan. The results of this work include: (a) the formulation of a set of access level operations which depend on the underlying storage model and the development of a cost model for estimating their cost; (b) the exploration of various optimization heuristics for selecting efficient execution plans for temporal path queries which make use of the join index relations that are provided by the storage model; and (c) a performance study that shows the benefits of join index based query processing techniques for knowledge bases compared to the traditional tuple-oriented (characteristic of the AI-DB coupling systems) and bulk join query processing approaches in database systems. ...

In this paper, we address the problem of clustering graphs in object-oriented databases. Unlike previous studies which focused only on a workload consisting of a single operation, this study tackles the problem when the workload is a set of operations (method and queries) that occur with a certain probability. Thus, the goal is to minimize the expected cost of an operation in the workload, while maintaining a similarly low cost for each individual operation class.