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.