This project concerns parallel evaluation of deductive database queries by processors interconnected by a communication network. Deductive database systems are key to the future design of complex applications like knowledge bases, expert systems, and scientific applications. Yet the potential of such systems is compromised by poor performance in environments where the data cannot fit in main memory. Parallelization is investigated as the means to improve performance, with attention on Datalog, a logic- based deductive language that naturally expresses queries that arise in advanced database applications. Based on three parameters of discriminating functions, discriminating variables and hash functions, a framework for the parallelization of Datalog programs is designed. Discriminating functions and variables which establish only required interconnections between parallel processors, thereby minimizing the overhead of unnecessary communication, are investigated. Hash functions are designed which capture the division of labor between processors and provide maximum performance by effectively balancing the workload. Although parallel systems promise enormous computing resources, their performance rests on the design of sophisticated parallelizing compilers that can make effective use of such resources. This research makes a pragmatic contribution to parallel system performance by providing an approach to the automatic parallel evaluation of an important subset of deductive database programs, Datalog.
