2026-07-21T19:24:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4976 2024-03-06T10:35:38Z ddc:004 open_access

Asymptotic Determinacy of Path Queries using Union-of-Paths Views Francis, Nadime Graph databases Views Determinacy Rewriting Path queries We consider the view determinacy problem over graph databases for queries defined as (possibly infinite) unions of path queries. These queries select pairs of nodes in a graph that are connected through a path whose length falls in a given set. A view specification is a set of such queries. We say that a view specification V determines a query Q if, for all databases D, the answers to V on D contain enough information to answer Q. Our main result states that, given a view V, there exists an explicit bound that depends on V such that we can decide the determinacy problem for all queries that ask for a path longer than this bound, and provide first-order rewritings for the queries that are determined. We call this notion asymptotic determinacy. As a corollary, we can also compute the set of almost all path queries that are determined by V. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nadime Francis 2015 Is Part Of LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2015.44 urn:nbn:de:0030-drops-49760 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.44 eng https://creativecommons.org/licenses/by/3.0/legalcode