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

规则系统越来越多地用于程序分析、语义Web、安全框架、传感器网络、认知无线电和容中断网络等领域，每一个领域都有自己的效率和可扩展性需求。 这些领域的进步将带来新一代的强大而安全的应用程序，这些应用程序可以控制人类安全甚至生命所依赖的设备，提供关键信息，并通过将分布式的以Web为中心的资源集中在一起，分析它们并自动化复杂的信息绑定任务来帮助人们做出明智的决策。然而，现有的规则系统实现并不具有可伸缩性，并且已经被证明在性能上存在很大差异。 为了实现上述下一代健壮应用的愿景，必须了解规则系统的性能特征，并为它们开发可扩展的优化和分析技术。 尽管在提高规则系统的性能方面已经取得了进展，但这个问题仍然极具挑战性，而且在理论和实施方面都知之甚少。本项目将开发一个全面的框架，用于严格理解和优化规则系统。 该方法基于精确的成本计算和全局程序转换，并结合和扩展了数据库查询优化，编译器优化和递归查询处理技术。 它包括：（1）生成逻辑等价但效率更高的程序的技术;（2）为规则程序的运行时间和空间使用生成参数化代价公式的代价模型和分析;（3）预测代价公式参数的技术;（4）搜索逻辑等价规则程序的指数大空间以找到具有最佳预测时间、空间和折衷的规则程序的算法;以及（5）将该策略实现为广泛使用的开源XSB逻辑编程系统的优化器。 该方法和实现将使用程序分析和语义Web中的应用程序进行评估。

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.