EUVIMEDEUVIMED entdecken
Crossref

Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum

Nofar Carmeli, Nikolaos Tziavelis

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

DOI: 10.1145/3801899 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Nofar Carmeli und 1 weiteren Autor:innen. Die Arbeit nennt 29 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We investigate the fine-grained complexity of direct access to Conjunctive Query (CQ) answers according to their position, ordered by the minimum (or maximum) value between attributes. We further use the tools we develop to explore a wealth of related tasks. We consider the task of ranked enumeration under min/max orders, as well as tasks concerning a CQ with a predicate of the form x ≤ min X , where X is a set of variables and x is a single variable: counting, enumeration, direct access, and predicate elimination (i.e., transforming the pair of query and database to an equivalent pair without min-predicates). For each task, we establish a complete dichotomy for self-join-free CQs, precisely identifying the cases that are solvable in near-ideal time, i.e., (quasi)linear preprocessing time followed by constant or logarithmic time per output.

Zitieren

APA

Carmeli, N., & Tziavelis, N. (2026). Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum. Proceedings of the ACM on Management of Data, 4(2), 1-25. https://doi.org/10.1145/3801899

Vancouver

Carmeli N, Tziavelis N. Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum. Proceedings of the ACM on Management of Data. 2026;4(2):1-25. doi:10.1145/3801899

BibTeX
@article{Carmeli2026,
  author = {Carmeli, Nofar and Tziavelis, Nikolaos},
  title = {Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {2},
  pages = {1--25},
  doi = {10.1145/3801899}
}
Kostenlos starten →