A graph representation of a semi-join program and its optimization

Abstract

A semi-join program is considered to be a strategy for processing a query in a distributed database system. To produce such a strategy for a general query, heuristics are required, as the problem of deriving an optimal solution is considered to be difficult. This thesis presents a semi-join program in graph-theoretic terms. In this framework, it seeks to improve the semi-join program by transforming it into one with non-increasing cost and non-decreasing benefit. The transformation algorithm runs in 0(n**3) time where n is the number of semi-joins in the program.