TY - JOUR

T1 - Evaluating Recursive Queries in Distributed Databases

AU - Nejdl, Wolfgang

AU - Ceri, Stefano

AU - Wiederhold, Gio

N1 - Funding Information: Manuscript received November 27, 1989; revised February 17, 1992. This work was partly performed at Stanford University as part of the KBMS Project, which is supported in part by DARPA under Contract N39-84-C-11, partly performed at by the Technical University of Vienna with support from the Austrian Industries in the context of the CD-Laboratory, and partly performed at Modena University within the “Progetto Finalizzato Informatica e Calcolo Parallelo,” which is supported by CNR. W. Nejdl is with Informatik V, Technical University of Aachen, D-5100 Aachen, Germany. S. Ceri is with the Dipartimento di Elettronica e Informazione, Politecnico di Milano, 20133 Milano, Italy. G. Wiederhold is with the Computer Science Department, Stanford University, Stanford, CA 94305. IEEE Log Number 9205835.

PY - 1993/2

Y1 - 1993/2

N2 - In this paper, we study the execution of logic queries in a distributed database environment. We assume that each local database system can execute logic queries, and we design methods for the efficient execution of queries requiring data from multiple sites. Conventional optimization strategies which are well known in the field of distributed databases, 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 we present several program transformation techniques which attempt to minimize distribution costs based on the idea of semijoins and generalized semijoins in conventional databases. Although local computation of semijoins is not possible for the general case, we indicate classes of programs for which these transformations succeed in producing set-oriented computation. We describe processes evaluating the recursive program in a distributed network and develop an efficient method for testing the termination of the computation. Finally, we compare our approach with sequential as well as dataflow-oriented evaluation. Datalog is assumed as logic programming language and paradigm.

AB - In this paper, we study the execution of logic queries in a distributed database environment. We assume that each local database system can execute logic queries, and we design methods for the efficient execution of queries requiring data from multiple sites. Conventional optimization strategies which are well known in the field of distributed databases, 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 we present several program transformation techniques which attempt to minimize distribution costs based on the idea of semijoins and generalized semijoins in conventional databases. Although local computation of semijoins is not possible for the general case, we indicate classes of programs for which these transformations succeed in producing set-oriented computation. We describe processes evaluating the recursive program in a distributed network and develop an efficient method for testing the termination of the computation. Finally, we compare our approach with sequential as well as dataflow-oriented evaluation. Datalog is assumed as logic programming language and paradigm.

KW - Deductive databases

KW - distributed databases

KW - distributed query processing

KW - query optimization

KW - recursive query processing

KW - semi-join

UR - http://www.scopus.com/inward/record.url?scp=0027544284&partnerID=8YFLogxK

U2 - 10.1109/69.204095

DO - 10.1109/69.204095

M3 - Article

AN - SCOPUS:0027544284

VL - 5

SP - 104

EP - 121

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

SN - 1041-4347

IS - 1

ER -