Performance issues in the binary relationship model

摘要

In this paper we propose to use the Binary Relationship Model not only in the logical, but also in the physical level. At the logical level we propose and analyze a query optimization algorithm. The major optimization issue is to find an optimized join sequence for chain queries. A branch-and-bound search algorithm with dynamic programming is used in the search for such a sequence. At the physical level we propose to store the binary relations using multiattribute hashing. We develop a join algorithm which takes advantage of the clustering that multiattribute hashing achieves, and derive analytical formulas to predict its performance.