Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.44
URN: urn:nbn:de:0030-drops-49760
URL: https://drops.dagstuhl.de/opus/volltexte/2015/4976/
Francis, Nadime
Asymptotic Determinacy of Path Queries using Union-of-Paths Views
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{francis:LIPIcs:2015:4976,
author = {Nadime Francis},
title = {{Asymptotic Determinacy of Path Queries using Union-of-Paths Views}},
booktitle = {18th International Conference on Database Theory (ICDT 2015)},
pages = {44--59},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-79-8},
ISSN = {1868-8969},
year = {2015},
volume = {31},
editor = {Marcelo Arenas and Mart{\'i}n Ugarte},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4976},
URN = {urn:nbn:de:0030-drops-49760},
doi = {10.4230/LIPIcs.ICDT.2015.44},
annote = {Keywords: Graph databases, Views, Determinacy, Rewriting, Path queries}
}
| Keywords: | Graph databases, Views, Determinacy, Rewriting, Path queries | |
| Seminar: | 18th International Conference on Database Theory (ICDT 2015) | |
| Issue date: | 2015 | |
| Date of publication: | 19.03.2015 |
