Journal article · 2026 · Open access

Extremal Fitting Problems for Conjunctive Queries

Balder ten Cate, Víctor Dalmau, Maurice Funk, Carsten Lutz

Journal of the ACM · Published 13 October 2026 · DOI 10.1145/3858670

Open PDFView at the publisherCite this paper

In brief

“Extremal Fitting Problems for Conjunctive Queries” is a 2026 journal article by Balder ten Cate and 3 co-authors, published in Journal of the ACM. OpenAlex counts 0 citations as of 17 November 2026. It is open access under a CC BY licence: the full text is free to read at Journal of the ACM.

Citations
0
References
54
Authors
4

Abstract

The fitting problem for conjunctive queries (CQs) is the problem to construct a CQ that fits a given set of labeled data examples. When a fitting CQ exists, it is in general not unique. This leads us to propose natural refinements of the notion of a fitting CQ, such as most-general fitting CQ , most-specific fitting CQ , and unique fitting CQ . We give structural characterizations of these notions in terms of (suitable refinements of) homomorphism dualities, frontiers, and direct products, which enable the construction of the refined fitting CQs when they exist. We also pinpoint the complexity of the associated existence and verification problems, and determine the size of fitting CQs. We study the same problems for unions of CQs (UCQs).

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

ten Cate, B., Dalmau, V., Funk, M., & Lutz, C. (2026). Extremal Fitting Problems for Conjunctive Queries. Journal of the ACM. https://doi.org/10.1145/3858670

MLA 9

ten Cate, Balder, et al. “Extremal Fitting Problems for Conjunctive Queries.” Journal of the ACM, 2026. https://doi.org/10.1145/3858670.

Chicago

ten Cate, Balder, Víctor Dalmau, Maurice Funk, and Carsten Lutz. 2026. “Extremal Fitting Problems for Conjunctive Queries.” Journal of the ACM. https://doi.org/10.1145/3858670.

Harvard

ten Cate, B. et al. (2026) ‘Extremal Fitting Problems for Conjunctive Queries’, Journal of the ACM. doi:10.1145/3858670.

IEEE

B. ten Cate, V. Dalmau, M. Funk, and C. Lutz, “Extremal Fitting Problems for Conjunctive Queries,” Journal of the ACM, 2026, doi: 10.1145/3858670.

BibTeX

@article{tencate2026extremal,
  title     = {{Extremal Fitting Problems for Conjunctive Queries}},
  author    = {ten Cate, Balder and Dalmau, Víctor and Funk, Maurice and Lutz, Carsten},
  journal   = {Journal of the ACM},
  year      = {2026},
  doi       = {10.1145/3858670},
  url       = {https://doi.org/10.1145/3858670}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Topic and keywords

Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries

  • conjunctive queries
  • frontier
  • direct products
  • unions of conjunctive queries
  • computational complexity

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

ten Cate, B., Dalmau, V., Funk, M., & Lutz, C. (2026). Extremal Fitting Problems for Conjunctive Queries. Journal of the ACM. https://doi.org/10.1145/3858670

How many times has this paper been cited?

0 times, according to OpenAlex on 17 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at Journal of the ACM: sign in and open the PDF from this page.

Who wrote this paper?

Balder ten Cate, Víctor Dalmau, Maurice Funk, Carsten Lutz.

What is the DOI of this paper?

10.1145/3858670, permanently at https://doi.org/10.1145/3858670. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 17 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.