EUVIMEDEUVIMED entdecken
Crossref

Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries

Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara, Dan Olteanu, Dan Suciu

Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-24

DOI: 10.1145/3801891 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Mahmoud Abo Khamis und 4 weiteren Autor:innen. Die Arbeit nennt 37 Literaturangaben. Gefördert von: NSF, Microsoft.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present an output-sensitive algorithm for evaluating an acyclic Conjunctive Regular Path Query (CRPQ). Its complexity is written in terms of the input size, the output size, and a well-known parameter of the query that is called the ''free-connex fractional hypertree width''. Our algorithm improves upon the complexity of the recently introduced output-sensitive algorithm for acyclic CRPQs. More notably, the complexity of our algorithm for a given acyclic CRPQ Q matches the best known output-sensitive complexity for the ''corresponding'' conjunctive query (CQ), that is the CQ that has the same structure as the CRPQ Q except that each RPQ is replaced with a binary atom (or a join of two binary atoms). This implies that it is not possible to improve upon our complexity for acyclic CRPQs without improving the state-of-the-art on output-sensitive evaluation for acyclic CQs. Our result is surprising because RPQs, and by extension CRPQs, are equivalent to recursive Datalog programs, which are generally poorly understood from a complexity standpoint. Yet, our result implies that the recursion aspect of acyclic CRPQs does not add any extra complexity on top of the corresponding (non-recursive) CQs, at least as far as output-sensitive analysis is concerned.

Förderung

  • NSF
  • Microsoft

Zitieren

APA

Khamis, M. A., Hurjui, A., Kara, A., Olteanu, D., & Suciu, D. (2026). Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries. Proceedings of the ACM on Management of Data, 4(2), 1-24. https://doi.org/10.1145/3801891

Vancouver

Khamis MA, Hurjui A, Kara A, Olteanu D, Suciu D. Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries. Proceedings of the ACM on Management of Data. 2026;4(2):1-24. doi:10.1145/3801891

BibTeX
@article{Khamis2026,
  author = {Khamis, Mahmoud Abo and Hurjui, Alexandru-Mihai and Kara, Ahmet and Olteanu, Dan and Suciu, Dan},
  title = {Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {2},
  pages = {1--24},
  doi = {10.1145/3801891}
}
Kostenlos starten →