"Query determinacy and rewriting"
Victor Vianu
(UCSD)
Monday, April 21st, 2014, 2:00 pm
EBU3B, Room 4140
Abstract:
Suppose we are given a query P and a query Q. Consider the following question (referred to as determinacy): does P provide enough information to answer Q ? If so, how can we rewrite Q using P ? Such questions arise naturally in various contexts ranging from query optimization to privacy. If the query language is powerful enough (say, first-order logic) then determinacy is immediately undecidable. More interestingly, determinacy is also undecidable for much weaker languages, and decidability remains open for the simplest non-trivial query language, the conjunctive queries (CQ). The rewriting question is also intriguing: contrary to long-held conventional wisdom, rewriting a conjunctive query Q in terms of another conjunctive query P (when P determines Q) sometimes requires a more powerful language than the conjunctive queries themselves. I will present several results on determinacy and rewriting for query languages ranging from CQ to FO. If time allows, I will mention some other simple (to state) problems in database theory that remain tantalizingly open.
