The Hunt for a Red Spider: Conjunctive Query Determinacy Problem is Undecidable

Prelegent(ci)

Jerzy Marcinkowski

Afiliacja

Uniwersytet Wrocławski

Termin

7 października 2015 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Imagine there is a set {Q_1,...Q_n} of database queries (conjunctive
queries), and, for any database  instance D, we have access to the
views Q_1(D),...Q_n(D) defined by these queries.

Then they give us another query, Q, and we would like to know whether, regardless of D, once knowing Q_1(D),...Q_n(D) we will also be able to compute Q(D).

This problem (known as Conjunctive Query Determinacy Problem) is
related to practical issues concerning efficiency and security and has
been studied since mid-1980s. Algorithms have been found for some
special cases, and some generalisations have been proved to be
undecidable.

We (together with my student Tomasz Gogacz) give a negative solution to this old problem, showing that Conjunctive Query Determinacy Problem is undecidable. Part of our work is presented in our LICS 2015 paper and part is still unpublished.

---