You are not logged in |
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.
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.
