What makes a variant of query determinacy (un)decidable?

Talk by Jerzy Marcinkowski

Location: APB 3027
Start: 5. December 2019 at 1:00 pm
End: 5. December 2019 at 2:30 pm
Research group: Computational Logic
Research group: Knowledge-Based Systems
Event series: KBS Seminar
iCal

Suppose there is a database we have no direct access to, but there are views of this database available to us, defined by some queries Q_1 , Q_2 , . . . Q_k. And we are given another query Q. Will we be able to compute Q only using the available views?

The above question, call it "the question of determinacy", sounds almost philosophical. One can easily imagine a bearded man in himation chained to the wall of a cave watching the views projected on the wall and pondering whether, from what he is able to see, the reality can be faithfully reconstructed.

For us it is a database theory question though. And a really well motivated one, with motivations ranging from query evaluation plans optimization (where we prefer a positive answer) to privacy issues (where the preferred answer is negative).

Query determinacy is a broad topic, with literally hundreds of papers published since the late 1980s. This talk is not going to be a "survey" (which would be impossible, within a one hour time frame, and with this speaker), but rather a personal perspective of a person somehow involved in the recent developments in the area.

First I will explain how, in the last 30+ years, the question of determinacy was formalized. There are many parameters here: obviously one needs to choose the query language of the queries Q_i and the query language of Q. But -- surprisingly -- there is also some choice regarding what the word "to compute" actually means in this context.

Then I will concentrate on the variants of the decision problem of determinacy (for each choice of parameters there is one such problem -- Q_1 , Q_2 , . . . Q_k and Q constitute the instance, and the question is whether Q_1 , Q_2 , . . . Q_k determine Q) and I will talk about how I understand the mechanisms rendering different variants of determinacy decidable or undecidable. This will be on a slightly informal level. No new theorems will be presented, but I think I will be able to show simplified proofs of some of the earlier results.

This is a preview of the invited talk at ICDT 2020.