Collisions and reduction filters in distributed query processing

The optimization of general queries in a distributed database management system is an important research issue. The problem is to select the best sequence of database operations that will process the query efficiently and minimize costs. Approaches include algorithms which are join-based, semijoin-based, or a combination of both. The algorithm presented which is based on reduction filters, can process general queries consisting of an arbitrary number of relations and join attributes. Each query is represented by a graph and an adjacency list. Each relation is usually only processed once, to minimize data transfers. However, if a filter changes during use then certain relations must be processed again; a queue is used to record this information. The algorithm consists of two phases: during phase one the adjacency list is used to determine the order in which the filters are constructed and used