SHF: Medium: Perfomance 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, and Disruption-tolerant Networking, each with its own demands for efficiency and scalability. Advances in these areas will lead to a new generation of robust and secure applications that control devices on which human safety and even lives depend, supply with critical information, and help people make informed decisions by pulling together distributed Web-centric resources, analyzing them, and automating complex information-bound tasks. However, existing implementations of rule systems are not sufficiently scalable and have been shown to vary widely in performance. To make the above vision of next generation robust applications a reality, one must understand the performance characteristics of rule systems and develop scalable optimization and analysis techniques for them. Although advances have been made in improving performance of rule systems, the problem remained extremely challenging and poorly understood both theoretically and implementation-wise. This project will develop a comprehensive framework for rigorous understanding and optimization of rule systems. The approach is based on precise cost calculations and global program transformations, and it combines and extends techniques from database query optimization, compiler optimization, and recursive query processing. It includes: (1) techniques for generating logically equivalent but more efficient programs; (2) cost models and analysis for generating parameterized cost formulas for the running time and space usage of rule programs; (3) techniques for estimating parameters of the cost formulas; (4) heuristics for searching the exponentially large space of logically equivalent rule programs to find the 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 implementation will be evaluated using applications in Program Analysis and Semantic Web.