Seminars

Our seminar series is free and available for anyone to attend. Unless otherwise stated, seminars take place on Wednesday afternoons at 2pm in the Kilburn Building during teaching season.

If you wish to propose a seminar speaker please contact Antoniu Pop.

 

The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable

  • Speaker:   Professor  Jerzy Marcinkowski  (University of Wroclaw)
  • Host:   IPH
  • 3rd February 2016 at 14:00 in Kilburn L.T. 1.4
Abstract
A good research question is one that you can explain to your neighbour, who is a retired city bus driver. And the question we are going to talk about -- call it "conjunctive query determinacy problem" -- is good, in this sense.

Our scenario is as follows. There is a database D, which we do not see. This can be for efficiency reasons or security reasons. We however see a view V over D: V is what D answers when some set of queries is asked to D. And we have another query Q to D. Can we evaluate Q only seeing V, but not D? Of course sometimes we can and sometimes we cannot. But is there an algorithm deciding whether we can? Despite many attempts to answer it, this had been an open question for over 30 years. In 2015 we (me, together with my student Tomasz Gogacz) gave a negative answer to this question.

The talk will not be very technical and no special background is needed to follow it. During first 30 minutes we will concentrate on the history of the problem and show some simple examples. Last 15 minutes will be devoted to one particular idea of our proof (which itself is rather complicated) -- we will explain what a Red Spider is and what it is good for.
▲ Up to the top