Resilience for Regular Path Queries: Towards a Complexity Classification
Proceedings of the ACM on Management of Data · 09.06.2025 · 3 (2) · 1-18
DOI: 10.1145/3725245 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 09.06.2025. Verfasst von Antoine Amarilli und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 30 Literaturangaben. Gefördert von: Agence Nationale de la Recherche, Deutsche Forschungsgemeinschaft, NSF.
Abstract (Originalsprache)
The resilience problem for a query and an input set or bag database is to compute the minimum number of facts to remove from the database to make the query false. In this paper, we study how to compute the resilience of Regular Path Queries (RPQs) over graph databases. Our goal is to characterize the regular languages L for which it is tractable to compute the resilience of the existentially-quantified RPQ built from L . We show that computing the resilience in this sense is tractable (even in combined complexity) for all RPQs defined from so-called local languages . By contrast, we show hardness in data complexity for RPQs defined from the following language classes (after reducing the languages to eliminate redundant words): all finite languages featuring a word containing a repeated letter, and all languages featuring a specific kind of counterexample to being local (which we call four-legged languages). The latter include in particular all languages that are not star-free . Our results also imply hardness for all non-local languages with a so-called neutral letter . We last highlight some remaining obstacles towards a full dichotomy.
Förderung
- Agence Nationale de la Recherche
- Deutsche Forschungsgemeinschaft
- NSF
Zitieren
APA
Amarilli, A., Gatterbauer, W., Makhija, N., & Monet, M. (2025). Resilience for Regular Path Queries: Towards a Complexity Classification. Proceedings of the ACM on Management of Data, 3(2), 1-18. https://doi.org/10.1145/3725245
Vancouver
Amarilli A, Gatterbauer W, Makhija N, Monet M. Resilience for Regular Path Queries: Towards a Complexity Classification. Proceedings of the ACM on Management of Data. 2025;3(2):1-18. doi:10.1145/3725245
BibTeX
@article{Amarilli2025,
author = {Amarilli, Antoine and Gatterbauer, Wolfgang and Makhija, Neha and Monet, Mikaël},
title = {Resilience for Regular Path Queries: Towards a Complexity Classification},
journal = {Proceedings of the ACM on Management of Data},
year = {2025},
volume = {3},
number = {2},
pages = {1--18},
doi = {10.1145/3725245}
}
EUVIMED