主 题: From Rules to Efficient Programs with Time and Space Guarantees.
报告人: Yanhong Annie Liu ((State Univ of New York at St))
时 间: 0000-00-00
地 点: 理科一号楼1560
While there are many special ways to specify analysis of complex data,relational rules simplify and generalize them. Such rules are used explicitly or implicitly in business processes, biological analysis,analysis of computer programs,and many other applications.Programming each kind of analysis by hand is a daunting recurringtask, but doing the analysis using a general evaluator program on any
particular set of rules incurs a significant overhead and does notprovide good performance guarantees. We have developed a method forautomatically generating efficient specialized programs for analysisproblems specified using Datalog, a general logic database query language based on relational rules. The method provides precise guarantees for both the running time and space consumption for the
generated analysis programs.
This result is based on a general transformational method that makes computation proceed in an iterative and incremental fashion, analogous to integration by differentiation in calculus. The method also exploits sophisticated structures for storing and accessing complex
data. Both time and space complexities of the generated programs are optimal in a precisely defined sense. We apply the method to a number of analysis problems, some with improved time complexities and all with greatly improved algorithm understanding and greatly simplified
complexity analysis.
