In distributed database systems, the cost to process a query is mainly determined by the amount of communication. Semi-join is a very useful tool to reduce the cost of joins in such systems. There are, however, queries called cyclic ones which cannot be processed by semi-joins only. In this paper the concept of generalized semi-joins is introduced to solve such a problem. To handle an arbitrary cyclic query, first a spanning tree is selected in the corresponding query graph and then generalized semi-joins are applied in the order determined by the tree. Processing of cyclic queries, however, requires more communication cost than processing of tree queries, since in the former case we need to transmit attribute values which are not required in the latter case. A procedure to reduce the communication cost of such additional data is developed, which will make the generalized semi-join based procedures practical.
展开▼
