More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets

Congratulations to LogicBlox team member Tuncay Tekle and academic collaborator Yanhong (Annie) Liu on the acceptance of their paper into SIGMOD 2011, the premier conference for database researchers! Their work dives deep into a topic very relevant for the evaluation of queries in LogicBlox database: what is the best strategy for a given query, top-down, or bottom-up. We look forward to experimenting and implementing the result of this work in LogicBlox!

Abstract Given a set of Datalog rules, facts, and a query, answers to the query can be inferred bottom-up starting with the facts or top-down starting with the query. The dominant strategies to improve the performance of answering queries are reusing answers to subqueries for top-down methods, and transforming rules based on demand from the query, such as the well-known magic sets transformation for bottom-up methods. However, the performance of these strategies vary drastically, and the most effective method remained unknown. This paper describes precise time and space complexity analysis for efficient implementation of Datalog queries using subsumptive tabling, a top-down evaluation method with more reuse of answers than the dominant tabling strategy, and shows that subsumptive tabling beats bottom-up evaluation of rules after magic sets transformation in both time and space complexities. It also describes subsumptive demand transformation, a novel method for transforming the rules so that bottom-up evaluation of the transformed rules mimics subsumptive tabling; we show that the time complexity of bottom-up evaluation after this transformation is equal to the time complexity of top-down evaluation with subsumptive tabling. The paper further describes subsumption optimization, an optimization to increase the use of subsumption in subsumptive methods, and shows its application in the derivation of a well-known demand-driven pointer analysis algorithm. We support our analyses and comparisons through experiments with applications in ontology queries and program analysis.


Leave a reply

© Copyright 2023. Infor. All rights reserved.

Log in with your credentials

Forgot your details?