Self join elimination and new notions of query containment

VCLA and WPI will host a talk by Evgenij Thorstensen on Thursday, October 20, 2016.

ABSTRACT

Query containment for conjunctive queries works best on the boolean fragment. For CQs with answer variables, however, it is somewhat brittle. In particular, it is difficult to compare queries where there is no known correspondance between answer variables. Furthermore, the fact that query containment preserves exact answers sometimes prevents interesting optimizations. In this talk, I will present a new notion of query containment based on the database a query extracts from an input database, rather than the answer tuples. I will show that this notion is very well suited for eliminating redundant self-joins in queries, and present a characterization of it using homomorphisms. As this is a work in progress, I will also present some interesting properties and theorems we are trying to prove.