Invited ICDT Talk

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, calling 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 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 as to 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.

Jerzy Marcinkowski received his PhD degree, in 1993 , from the Mathematical Department of the University of Wrocław and spent his entire academic career (with the exception of a three semesters long post-doc at the Laboratoire d'I Informatique Fondamentale de Lille in France) working for the University of Wrocław, where he is currently serves as the head of the Department of Computer Science.

His modus operandi is to try to attack well-abstracted, long standing open problems in logic in computer science, including database theory. Database theory people may know him for his work on DATALOG single rule program boundedness (1996), database repairs and consistent query answering, including prioritized repair (with Jan Chomicki and Sławek Staworko; 2000s) and, more recently, for his work on the Chase algorithm, where he proved (with his student Tomasz Gogacz) that all-instances chase termination is undecidable (2014). His main topic of interest in the last five years has been query determinacy.