Type
Text
Type
Dissertation
Advisor
David S. Warren | Liu, Yanhong A. | Michael Kifer | Patrick Cousot.
Date
2010-12-01
Keywords
Algorithms, Databases, Programming Languages, Query-processing | Computer Science
Department
Department of Computer Science
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/72699
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
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 understand their time and space complexities, particularly for answering queries of interest without inferring all facts.This dissertation focuses on Datalog---an important class of rules for applications in databases, program analysis, security, semantic web, and many other areas. We describe a systematic method for precisely analyzing the time and space complexities of best known strategies for answering Datalog queries. We also characterize precise relationships among these strategies. Furthermore, we develop new transformations and combine them with existing transformations to drastically optimize the rules and queries for generating efficient implementations. Finally, we show the effectiveness of our analyses and transformations for solving important problems in program analysis, language processing, and semantic web, and for answering graph queries, which have many applications.
Recommended Citation
Tekle, Tuncay, "Efficient Datalog Queries with Time and Space Complexity Guarantees" (2010). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 1902.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/1902