cgFOC admits computable VC-dimension bounds on nowhere dense structures and efficient algorithms for query answering and PAC learning on locally bounded expansion classes, but a minor extension is intractable on trees.
First-Order Query Evaluation with Cardinality Conditions
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We study an extension of first-order logic that allows to express cardinality conditions in a similar way as SQL's COUNT operator. The corresponding logic FOC(P) was introduced by Kuske and Schweikardt (LICS'17), who showed that query evaluation for this logic is fixed-parameter tractable on classes of structures (or databases) of bounded degree. In the present paper, we first show that the fixed-parameter tractability of FOC(P) cannot even be generalised to very simple classes of structures of unbounded degree such as unranked trees or strings with a linear order relation. Then we identify a fragment FOC1(P) of FOC(P) which is still sufficiently strong to express standard applications of SQL's COUNT operator. Our main result shows that query evaluation for FOC1(P) is fixed-parameter tractable with almost linear running time on nowhere dense classes of structures. As a corollary, we also obtain a fixed-parameter tractable algorithm for counting the number of tuples satisfying a query over nowhere dense classes of structures.
fields
cs.LO 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Complexity of Clique-Guarded First-Order Logic with Counting
cgFOC admits computable VC-dimension bounds on nowhere dense structures and efficient algorithms for query answering and PAC learning on locally bounded expansion classes, but a minor extension is intractable on trees.