Northwestern University

Mon 12:00 PM

CS Job Talk: Shumo Chu, Doctorate Student at the University of Washington, "Automated Reasoning of Database Queries"

Shumo Chu

When: Monday, February 11, 2019
12:00 PM - 1:00 PM  

Where: Mudd Hall ( formerly Seeley G. Mudd Library), 3rd Floor Seminar Room, 2233 Tech Drive, Evanston, IL 60208 map it

Audience: Faculty/Staff - Student - Public - Post Docs/Docs - Graduate Students

Contact: Brianna Mello   847.467.6558

Group: Electrical Engineering & Computer Science

Category: Lectures & Meetings


The CS Department welcomes Shumo Chu, Doctorate Student at the University of Washington.

Chu will present a talk entitled "Automated Reasoning of Database Queries" on Monday, February 11 at 12:00 PM in MUDD Hall 3rd Floor Seminar Room.

Abstract: From booking air tickets to analyzing astronomy datasets, database queries are pervasive in people’s work and life. However, reasoning database queries automatically is not easy. It is shown to be undecidable in general. And there are extensive studies from database community that are focus on the theoretical limitations.

I developed Cosette, the first tool for checking the semantic equivalence of SQL queries. The core of Cosette is a formal semantics of SQL based on semirings. This semantics covers major SQL features, including sophisticated ones such as grouping, aggregate, correlated subqueries, and integrity constraints. Also, this semantics is denotational and only adds a few equational axioms, as the interpretation of SQL, to semirings. Then, to check the equivalences, Cosette uses this semantics to encode a pair of input SQL queries in both an interactive theorem prover and a constraint solver. In the end, Cosette will either certify their equivalences using a sound decision procedure implemented in a theorem prover that covers the known decidable fragment of SQL, or show their inequivalence by providing a counter-example. Empirical studies show that Cosette can decide the equivalence or provide counter example for a wide range of practical SQL queries collected from database literature, real-world optimizer rules and bugs, and data management class homework assignment from UW. 

Bio: Shumo Chu is a doctorate student at the University of Washington. His research interests are in data management and programming languages. Shumo’s dissertation focus on developing theories, algorithms, and systems for automated reasoning of database queries. This requires leveraging both interactive theorem prover and constraint solver techniques. In the past, he had worked on large scale graph processing and query processing for distributed database systems. He also did internships with DMX group at Microsoft Research and Google’s Spanner team.

NOTE: Brown Bag style event with coffee served.

Hosted by CS Prof. Robby Findler

Add Event to Calendar

Add Event To My Group:

Please sign-in