2026-09-26T20:39:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25636 2026-09-23T23:45:33Z ddc:004 open_access

View-Based Query Determinacy for Walk-Based Semantics Francis, Nadime graph databases regular path queries trail semantics shortest walk semantics view-based query determinacy The view-based query determinacy problem asks, given a view 𝒱 and a query Q whether the information contained in 𝒱 always suffices to answer the query Q. It is a notoriously hard problem that is known to be undecidable even in very restricted settings. Here, we study it in the context of graph databases and regular path queries and views evaluated under several "walk-based semantics", that is, semantics in which queries and views return the matched walks in full as opposed to the classical "endpoint semantics". Our main finding is that view-based query determinacy is decidable for regular path queries under both trail and shortest walk semantics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nadime Francis 2026 Is Part Of LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2026.22 urn:nbn:de:0030-drops-256362 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.22 eng https://creativecommons.org/licenses/by/4.0/legalcode