SHF: Medium:Performance Analysis and Optimization for Logic Rule Engines

点击翻译按钮获取中文摘要

Rule systems are increasingly used in areas ranging from Program Analysis,Semantic Web, Security Frameworks, Sensor Networks, Cognitive Radio, andDisruption-tolerant Networking, each with its own demands for efficiencyand scalability. Advances in these areas will lead to a new generation ofrobust and secure applications that control devices on which human safetyand even lives depend, supply with critical information, and help peoplemake informed decisions by pulling together distributed Web-centricresources, analyzing them, and automating complex information-bound tasks.However, existing implementations of rule systems are not sufficientlyscalable and have been shown to vary widely in performance. To make theabove vision of next generation robust applications a reality, one mustunderstand the performance characteristics of rule systems and developscalable optimization and analysis techniques for them. Although advanceshave been made in improving performance of rule systems, the problemremained extremely challenging and poorly understood both theoretically andimplementation-wise.This project will develop a comprehensive framework for rigorousunderstanding and optimization of rule systems. The approach is based onprecise cost calculations and global program transformations, and itcombines and extends techniques from database query optimization, compileroptimization, and recursive query processing. It includes: (1) techniquesfor generating logically equivalent but more efficient programs; (2) costmodels and analysis for generating parameterized cost formulas for therunning time and space usage of rule programs; (3) techniques forestimating parameters of the cost formulas; (4) heuristics for searchingthe exponentially large space of logically equivalent rule programs to findthe ones with the best predicted time, space, and tradeoffs; and (5)implementation of the strategy as an optimizer for the widely used,open-source XSB Logic Programming System. The method and implementationwill be evaluated using applications in Program Analysis and Semantic Web.