{"id":{"repo_id":"gatech","oai_identifier":"oai:repository.gatech.edu:1853/64222"},"canonical_url":"https://search.dev.ndltd.org/etd/gatech/oai:repository.gatech.edu:1853/64222","repository":{"repo_id":"gatech","name":"Georgia Tech","base_url":"https://repository.gatech.edu/server/oai/request"},"display":{"title":"Symbolic Reasoning for Query Verification and Optimization","abstract":"Structured Query Language (SQL) is the most widely used language for interacting with many database management systems (DBMS). Thus, the problems of optimizing and verifying SQL queries are two of the most studied problems in the DBMS community. Traditional techniques for optimizing and verifying SQL queries are based on syntax-driven approaches, which suffer many limitations in terms of effectiveness and efficiency. In this dissertation, I investigate two important problems in query verification and optimization to demonstrate the limitations of syntax-driven techniques: (1) proving query equivalence under set and bag semantics; (2) optimizing queries with learned predicates. I propose to use symbolic reasoning to address the limitations of syntax-driven approaches in these two problems. I first present two techniques for proving query equivalence under set and bag semantics based on symbolic representation. Both approaches are significantly more efficient and effective than the previous state-of-the-art syntax-driven techniques. I then present a novel algorithm that combines symbolic reasoning with machine learning to synthesize new predicates for optimizing queries. This algorithm enables the query optimizer to leverage more optimization rules that it cannot previously apply. This technique significantly speeds up the execution of queries with complex predicates. In conclusion, this thesis proved that using symbolic reasoning can significantly improve the efficiency and effectiveness of techniques for query equivalence verification and query optimization.","abstract_html":"Structured Query Language (SQL) is the most widely used language for interacting with many database management systems (DBMS). Thus, the problems of optimizing and verifying SQL queries are two of the most studied problems in the DBMS community. Traditional techniques for optimizing and verifying SQL queries are based on syntax-driven approaches, which suffer many limitations in terms of effectiveness and efficiency. In this dissertation, I investigate two important problems in query verification and optimization to demonstrate the limitations of syntax-driven techniques: (1) proving query equivalence under set and bag semantics; (2) optimizing queries with learned predicates. I propose to use symbolic reasoning to address the limitations of syntax-driven approaches in these two problems. I first present two techniques for proving query equivalence under set and bag semantics based on symbolic representation. Both approaches are significantly more efficient and effective than the previous state-of-the-art syntax-driven techniques. I then present a novel algorithm that combines symbolic reasoning with machine learning to synthesize new predicates for optimizing queries. This algorithm enables the query optimizer to leverage more optimization rules that it cannot previously apply. This technique significantly speeds up the execution of queries with complex predicates. In conclusion, this thesis proved that using symbolic reasoning can significantly improve the efficiency and effectiveness of techniques for query equivalence verification and query optimization.","abstract_has_math":false,"creators":["Zhou, Qi"],"institution":"Georgia Institute of Technology","degree_name":null,"degree_level":"Doctoral","degree_discipline":null,"degree_department":"Computer Science","school":null,"contributors":[],"advisors":["Harris, William","Arulraj, Joy"],"committee_chairs":[],"committee_members":["Orso, Alex","Regehr, John","Navathe, Shamkant B."],"year":2020,"date_issued":"2020-12-10","date_published":"2020-12-10","updated_at":"2026-07-27T19:48:57Z","subjects":["Symbolic Reasoning Query Verification"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1853/64222","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Harris, William","Arulraj, Joy"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Orso, Alex","Regehr, John","Navathe, Shamkant B."]},{"key":"dc:contributor.department","label":"Department","values":["Computer Science"]},{"key":"dc:creator","label":"Author","values":["Zhou, Qi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-01-11T17:14:48Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-01-11T17:14:48Z"]},{"key":"dc:date.issued","label":"Date","values":["2020-12-10"]},{"key":"dc:publisher","label":"Institution","values":["Georgia Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Symbolic Reasoning Query Verification"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1853/64222"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Structured Query Language (SQL) is the most widely used language for interacting with many database management systems (DBMS). Thus, the problems of optimizing and verifying SQL queries are two of the most studied problems in the DBMS community. Traditional techniques for optimizing and verifying SQL queries are based on syntax-driven approaches, which suffer many limitations in terms of effectiveness and efficiency. In this dissertation, I investigate two important problems in query verification and optimization to demonstrate the limitations of syntax-driven techniques: (1) proving query equivalence under set and bag semantics; (2) optimizing queries with learned predicates. I propose to use symbolic reasoning to address the limitations of syntax-driven approaches in these two problems. I first present two techniques for proving query equivalence under set and bag semantics based on symbolic representation. Both approaches are significantly more efficient and effective than the previous state-of-the-art syntax-driven techniques. I then present a novel algorithm that combines symbolic reasoning with machine learning to synthesize new predicates for optimizing queries. This algorithm enables the query optimizer to leverage more optimization rules that it cannot previously apply. This technique significantly speeds up the execution of queries with complex predicates. In conclusion, this thesis proved that using symbolic reasoning can significantly improve the efficiency and effectiveness of techniques for query equivalence verification and query optimization."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Symbolic Reasoning for Query Verification and Optimization"]}]}],"canonical_facts":{"dc:contributor.advisor":["Harris, William","Arulraj, Joy"],"dc:contributor.committeemember":["Orso, Alex","Regehr, John","Navathe, Shamkant B."],"dc:contributor.department":["Computer Science"],"dc:creator":["Zhou, Qi"],"dc:date.accessioned":["2021-01-11T17:14:48Z"],"dc:date.available":["2021-01-11T17:14:48Z"],"dc:date.issued":["2020-12-10"],"dc:description.abstract":["Structured Query Language (SQL) is the most widely used language for interacting with many database management systems (DBMS). Thus, the problems of optimizing and verifying SQL queries are two of the most studied problems in the DBMS community. Traditional techniques for optimizing and verifying SQL queries are based on syntax-driven approaches, which suffer many limitations in terms of effectiveness and efficiency. In this dissertation, I investigate two important problems in query verification and optimization to demonstrate the limitations of syntax-driven techniques: (1) proving query equivalence under set and bag semantics; (2) optimizing queries with learned predicates. I propose to use symbolic reasoning to address the limitations of syntax-driven approaches in these two problems. I first present two techniques for proving query equivalence under set and bag semantics based on symbolic representation. Both approaches are significantly more efficient and effective than the previous state-of-the-art syntax-driven techniques. I then present a novel algorithm that combines symbolic reasoning with machine learning to synthesize new predicates for optimizing queries. This algorithm enables the query optimizer to leverage more optimization rules that it cannot previously apply. This technique significantly speeds up the execution of queries with complex predicates. In conclusion, this thesis proved that using symbolic reasoning can significantly improve the efficiency and effectiveness of techniques for query equivalence verification and query optimization."],"dc:description.degree":["Ph.D."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1853/64222"],"dc:language.iso":["en_US"],"dc:publisher":["Georgia Institute of Technology"],"dc:subject":["Symbolic Reasoning Query Verification"],"dc:title":["Symbolic Reasoning for Query Verification and Optimization"],"dc:type":["Text"],"thesis:degree_level":["Doctoral"]},"updated_at":"2026-07-27T19:48:57Z"}