2026-07-21T14:14:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10317 2024-03-06T10:45:47Z ddc:004 open_access

The First Order Truth Behind Undecidability of Regular Path Queries Determinacy Głuch, Grzegorz Marcinkowski, Jerzy Ostropolski-Nalewaja, Piotr database theory query view determinacy recursive path queries In our paper [Głuch, Marcinkowski, Ostropolski-Nalewaja, LICS ACM, 2018] we have solved an old problem stated in [Calvanese, De Giacomo, Lenzerini, Vardi, SPDS ACM, 2000] showing that query determinacy is undecidable for Regular Path Queries. Here a strong generalisation of this result is shown, and - we think - a very unexpected one. We prove that no regularity is needed: determinacy remains undecidable even for finite unions of conjunctive path queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Grzegorz Głuch and Jerzy Marcinkowski and Piotr Ostropolski-Nalewaja 2019 Is Part Of LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2019.15 urn:nbn:de:0030-drops-103175 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.15 eng https://creativecommons.org/licenses/by/3.0/legalcode