Parallel Processing of Linear Recursive Datalog Queries using Transitive Closure Algorithms

Author:	Thomas Zurek
Date:	June 1992
Type:	Final Year Thesis, Department of Computer Science, Edinburgh Univeristy

Abstract

Datalog is a subset of Prolog and is used as a query language for deductive databases. The advantage of Datalog over query languages based on relational algebra is that it allows recursion. Normally relational query languages like SQL lack such mechanisms. The disadvantage is that recursive Datalog queries are expensive to process by the usual methods like bottom-up or top-down.

This report investigates two approaches to improving the performance of Datalog query processing: replacing linear recursion by using (parallel) transitive closure algorithms and using the data parallelism that is inherent in a large number of database applications. Finally the results obtained in the first chapters of this report were used as the basis of an implementation of the query processing algorithm of Jagadish et al. on a Connection Machine CM-200 and performance results of this implementation are given.

Thomas Zurek, <tz@dcs.ed.ac.uk>