Victor Vianu (Theory Seminar S14)

vianu.jpg"Query determinacy and rewriting"
Victor Vianu
Monday, April 21st, 2014, 2:00 pm
EBU3B, Room 4140
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.