Evaluating recursive queries in distributed databases
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 5 (1) , 104-121
- https://doi.org/10.1109/69.204095
Abstract
The execution of logic queries in a distributed database environment is studied. Conventional optimization strategies, such as the early evaluation of selection conditions and the clustering of processing to manipulate and exchange large sets of tuples, are redefined in view of the additional difficulties due to logic queries, in particular to recursive rules. In order to allow efficient processing of these logic queries, several program transformation techniques that attempt to minimize distribution costs based on the idea of semijoins and generalized semijoins in conventional databases are presented. Although local computation of semijoins is not possible for the general case, classes of programs are indicated for which these transformations succeed in producing set-oriented computation. Processes evaluating the recursive program in a distributed network are described, and an efficient method for testing the termination of the computation is developed. The approach is compared with sequential as well as dataflow-oriented evaluation.Keywords
This publication has 21 references indexed in Scilit:
- Parallel computation of direct transitive closuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A framework for the parallel processing of Datalog queriesPublished by Association for Computing Machinery (ACM) ,1990
- An intelligent search method for query optimization by semijoinsIEEE Transactions on Knowledge and Data Engineering, 1989
- Why a single parallelization strategy is not enough in knowledge basesPublished by Association for Computing Machinery (ACM) ,1989
- On the power of magicPublished by Association for Computing Machinery (ACM) ,1987
- The parallel complexity of simple chain queriesPublished by Association for Computing Machinery (ACM) ,1987
- Parallel evaluation of recursive rule queriesPublished by Association for Computing Machinery (ACM) ,1985
- On the implementation of a simple class of logic queries for databasesPublished by Association for Computing Machinery (ACM) ,1985
- Magic sets and other strange ways to implement logic programs (extended abstract)Published by Association for Computing Machinery (ACM) ,1985
- On compiling queries in recursive first-order databasesJournal of the ACM, 1984