Parallel Evaluation Of Deductive Database Queries

本课题是关于演绎数据库的并行计算 由通过通信网络互连的处理器进行的查询。 演绎数据库系统是未来设计的关键 复杂的应用程序，如知识库，专家系统， 科学应用。然而，这种系统的潜力是 由于在数据 无法放入主内存。作为一种新的方法， 意味着提高性能，注意数据库，一个逻辑- 基于演绎的语言，自然地表达查询， 出现在高级数据库应用程序中。基于三 判别函数参数，判别变量 和散列函数，一个并行化的框架， 设计了数据库程序。鉴别功能和 仅建立所需相互关系的变量， 并行处理器，从而最大限度地减少开销 不必要的沟通。散列函数 设计了一种捕捉处理器之间劳动分工的 并通过有效地平衡 工作量虽然并行系统承诺巨大的计算能力 资源，其性能取决于复杂的设计 并行化编译器，可以有效地利用这种 资源这项研究为以下方面做出了务实的贡献： 并行系统的性能，提供了一种方法， 演绎推理重要子集的自动并行求值 数据库程序

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.