EUVIMEDEUVIMED entdecken
Crossref

Resilience for Regular Path Queries: Towards a Complexity Classification

Antoine Amarilli, Wolfgang Gatterbauer, Neha Makhija, Mikaël Monet, Martín Muñoz

ACM Transactions on Database Systems · 13.11.2026

DOI: 10.1145/3862467 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 13.11.2026. Verfasst von Antoine Amarilli und 4 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

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 a dichotomy on all languages with a so-called neutral letter . We last show tractability for some classes of non-local languages, namely the so-called bipartite chain languages and one-dangling languages , and highlight some remaining obstacles towards a full dichotomy.

Zitieren

APA

Amarilli, A., Gatterbauer, W., Makhija, N., Monet, M., & Muñoz, M. (2026). Resilience for Regular Path Queries: Towards a Complexity Classification. ACM Transactions on Database Systems. https://doi.org/10.1145/3862467

Vancouver

Amarilli A, Gatterbauer W, Makhija N, Monet M, Muñoz M. Resilience for Regular Path Queries: Towards a Complexity Classification. ACM Transactions on Database Systems. 2026. doi:10.1145/3862467

BibTeX
@article{Amarilli2026,
  author = {Amarilli, Antoine and Gatterbauer, Wolfgang and Makhija, Neha and Monet, Mikaël and Muñoz, Martín},
  title = {Resilience for Regular Path Queries: Towards a Complexity Classification},
  journal = {ACM Transactions on Database Systems},
  year = {2026},
  doi = {10.1145/3862467}
}
Kostenlos starten →