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

Speaker(s)

Jerzy Marcinkowski

Affiliation

Uniwersytet Wrocławski

Date

Oct. 7, 2015, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---