| dc.identifier.uri | http://hdl.handle.net/1951/55647 | |
| dc.identifier.uri | http://hdl.handle.net/11401/72699 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dc.type | Dissertation | |
| dcterms.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. | |
| dcterms.available | 2012-05-15T18:07:08Z | |
| dcterms.available | 2015-04-24T14:53:16Z | |
| dcterms.contributor | Liu, Yanhong A. | en_US |
| dcterms.contributor | David S. Warren | en_US |
| dcterms.contributor | Michael Kifer | en_US |
| dcterms.contributor | Patrick Cousot. | en_US |
| dcterms.creator | Tekle, Tuncay | |
| dcterms.dateAccepted | 2012-05-15T18:07:08Z | |
| dcterms.dateAccepted | 2015-04-24T14:53:16Z | |
| dcterms.dateSubmitted | 2012-05-15T18:07:08Z | |
| dcterms.dateSubmitted | 2015-04-24T14:53:16Z | |
| dcterms.description | Department of Computer Science | en_US |
| dcterms.format | Monograph | |
| dcterms.format | Application/PDF | en_US |
| dcterms.identifier | Tekle_grad.sunysb_0771E_10394.pdf | en_US |
| dcterms.identifier | http://hdl.handle.net/1951/55647 | |
| dcterms.identifier | http://hdl.handle.net/11401/72699 | |
| dcterms.issued | 2010-12-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2012-05-15T18:07:08Z (GMT). No. of bitstreams: 1
Tekle_grad.sunysb_0771E_10394.pdf: 690673 bytes, checksum: 7e540154227c372fb72308f8d871a4e0 (MD5)
Previous issue date: 1 | en |
| dcterms.provenance | Made available in DSpace on 2015-04-24T14:53:16Z (GMT). No. of bitstreams: 3
Tekle_grad.sunysb_0771E_10394.pdf.jpg: 1894 bytes, checksum: a6009c46e6ec8251b348085684cba80d (MD5)
Tekle_grad.sunysb_0771E_10394.pdf.txt: 234928 bytes, checksum: cf9cd9ffe694cd039cfd66ea579ba5ac (MD5)
Tekle_grad.sunysb_0771E_10394.pdf: 690673 bytes, checksum: 7e540154227c372fb72308f8d871a4e0 (MD5)
Previous issue date: 1 | en |
| dcterms.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dcterms.subject | Algorithms, Databases, Programming Languages, Query-processing | |
| dcterms.subject | Computer Science | |
| dcterms.title | Efficient Datalog Queries with Time and Space Complexity Guarantees | |
| dcterms.type | Dissertation | |
