Parallel Bottom-Up Evaluation of Logic Programs: DeALS on Shared-Memory Multicore Machines

Mohan Yang ; Alexander Shkapsky ; Carlo Zaniolo

UCLA Henry Samueli School of Engineering and Applied Science

RP-ID  :  150003

学科分类：计算机科学（综合）

美国|英语

来源: UCLA Computer Science Technical Reports Database

【 摘 要 】

Delivering superior expressive power over RDBMS, while maintaining competitive performance, has represented the main goal and technical challenge for deductive database research since its inception forty years ago. Significant progress toward this ambitious goal is being achieved by the DeALS system through the parallel bottom-up evaluation of logic programs, including recursive programs with monotonic aggregates, on a shared-memory multicore machine.In DeALS, a program is represented as an AND/OR tree, where the parallel evaluation instantiates multiple copies of the same AND/OR tree that access the tables in the database concurrently. Synchronization methods such as locks are used to ensure the correctness of the evaluation. We describe a technique which finds an efficient hash partitioning strategy of the tables that minimizes the use of locks during the evaluation. Experimental results demonstrate the effectiveness of the proposed technique -- DeALS achieves competitive performance on non-recursive programs compared with commercial RDBMSs and superior performance on recursive programs compared with other existing systems.