2026-07-25T12:07:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11926 2024-03-06T10:49:02Z ddc:004 open_access

What Makes a Variant of Query Determinacy (Un)Decidable? (Invited Talk) Marcinkowski, Jerzy database theory query view determinacy This paper was written as the companion paper of the ICDT 2020 invited tutorial. Query determinacy is a broad topic, with literally hundreds of papers published since late 1980s. This paper is not going to be a "survey" but rather a personal perspective of a person somehow involved in the recent developments in the area. First I 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 available views and the query language of the query itself. But - surprisingly - there is also some choice regarding what the word "to compute" actually means in this context. Then I concentrate on certain variants of the decision problem of determinacy (for each choice of parameters there is one such problem) and explain how I understand the mechanisms rendering such variants of determinacy decidable or undecidable. This is on a rather informal level. No really new theorems are presented, but I show some improvements of existing theorems and also simplified proofs of some of the earlier results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jerzy Marcinkowski 2020 Is Part Of LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2020.2 urn:nbn:de:0030-drops-119265 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.2 eng https://creativecommons.org/licenses/by/3.0/legalcode