The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable
| Dates: | 3 February 2016 |
|---|
| Times: | 14:00 - 15:00 |
|---|
| What is it: | Seminar |
|---|
| Organiser: | Department of Computer Science |
|---|
| Who is it for: | University staff, Adults, Current University students |
|---|
| Speaker: | Professor Jerzy Marcinkowski |
|---|
|
The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable
3rd February 2016 at 14:00 in Kilburn L.T. 1.4
Speaker: Professor Jerzy Marcinkowski (University of Wroclaw)
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.
Speaker
Professor Jerzy Marcinkowski
Organisation: University of Wroclaw
Travel and Contact Information
Find event
Kilburn Lecture Theatre 1.4
Kilburn Building
Manchester
