TY - GEN
T1 - Generating specialized rules and programs for demand-driven analysis
AU - Tekle, K. Tuncay
AU - Hristova, Katia
AU - Liu, Yanhong A.
PY - 2008
Y1 - 2008
N2 - Many complex analysis problems can be most clearly and easily specified as logic rules and queries, where rules specify how given facts can be combined to infer new facts, and queries select facts of interest to the analysis problem at hand. However, it has been extremely challenging to obtain efficient implementations from logic rules and to understand their time and space complexities, especially for on-demand analysis driven by queries. This paper describes a powerful method for generating specialized rules and programs for demand-driven analysis from Datalog rules and queries, and further for providing time and space complexity guarantees. The method combines recursion conversion with specialization of rules and then uses a method for program generation and complexity calculation from rules. We compare carefully with the best prior methods by examining many variants of rules and queries for the same graph reachability problems, and show the application of our method in implementing graph query languages in general.
AB - Many complex analysis problems can be most clearly and easily specified as logic rules and queries, where rules specify how given facts can be combined to infer new facts, and queries select facts of interest to the analysis problem at hand. However, it has been extremely challenging to obtain efficient implementations from logic rules and to understand their time and space complexities, especially for on-demand analysis driven by queries. This paper describes a powerful method for generating specialized rules and programs for demand-driven analysis from Datalog rules and queries, and further for providing time and space complexity guarantees. The method combines recursion conversion with specialization of rules and then uses a method for program generation and complexity calculation from rules. We compare carefully with the best prior methods by examining many variants of rules and queries for the same graph reachability problems, and show the application of our method in implementing graph query languages in general.
UR - https://www.scopus.com/pages/publications/51049124326
U2 - 10.1007/978-3-540-79980-1_26
DO - 10.1007/978-3-540-79980-1_26
M3 - Conference contribution
SN - 3540799796
SN - 9783540799795
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 346
EP - 361
BT - Algebraic Methodology and Software Technology - 12th International Conference, AMAST 2008, Proceedings
T2 - 12th International Conference on Algebraic Methodology and Software Technology, AMAST 2008
Y2 - 28 July 2008 through 31 July 2008
ER -