Parallel Evaluation Of Deductive Database Queries

该项目涉及通过通信网络互连的处理器对演绎数据库查询的并行评估。演绎数据库系统是未来设计复杂应用程序的关键，如知识库、专家系统和科学应用程序。然而，在数据无法放入主内存的环境中，由于性能不佳，此类系统的潜力受到了影响。将并行化作为提高性能的手段进行了研究，并将注意力放在Datalog上，这是一种基于逻辑的演绎语言，可以自然地表达高级数据库应用程序中出现的查询。基于判别函数、判别变量和散列函数三个参数，设计了一种Datalog程序并行化的框架。研究了仅在并行处理机之间建立所需互连从而最小化不必要通信的开销的判别函数和变量。散列函数被设计成捕捉处理器之间的分工，并通过有效地平衡工作负载来提供最大性能。虽然并行系统承诺了巨大的计算资源，但它们的性能取决于能够有效利用这些资源的复杂并行化编译器的设计。这项研究为演绎数据库程序的一个重要子集Datalog提供了一种自动并行计算的方法，从而对并行系统的性能做出了务实的贡献。

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.