Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries
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.
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}
}
EUVIMED