Complexity limits for evaluating logical queries with few variables
A Fine-Grained Dichotomy for Bounded-Variable Query Evaluation: The Calculus of Relations, a Boolean Modal Logic, and One-Variable Counting Logic
DatabasesComputational ComplexityLogic in Computer Science
Summary
This paper looks at how hard it is to evaluate certain logical questions that use a limited number of variables on data with many relationships. The authors show there's a sharp divide: some types of queries can be answered quickly, but others can't, assuming a widely believed complexity hypothesis. They identify exactly which query types are easier to solve and link them to three known logical systems. This helps us understand when checking complex data properties is computationally feasible.
What this means in practice
- •For database engineers: Optimize query engines by identifying query patterns that can be evaluated more efficiently due to bounded-variable restrictions.
- •For software verification teams: Focus model checking on logical fragments proven tractable to speed up correctness checks on sparse data models.
A theory result. No direct application yet.
Authors
Yoshiki Nakamura, Yuya Uezato
Abstract
We study the fine-grained complexity of evaluating Boolean bounded-variable first-order queries over sparse relational structures. For every fixed $k \ge 2$, every relational signature, and every fragment between $k$-variable primitive positive ($\mathrm{PP}^{k}$) and first-order ($\mathrm{FO}^{k}$) logic, we prove, assuming the Sparse MAX-$3$-SAT hypothesis, a dichotomy theorem for evaluation in $O(m^{k-\varepsilon})$ time, where $m$ is the number of tuples in the input structure. The only tractable cases fall into three families: (1) three-variable fragments, (2) two-variable fragments, and (3) fragments over unary signatures. On the hard side, for every fixed $k \ge 4$ and every $\varepsilon > 0$, there is a fixed sentence $\varphi_\varepsilon$ in $\mathrm{PP}^{k}$ over a single binary relation symbol, depending on $\varepsilon$ but not on the input structure, whose evaluation cannot be performed in $O(m^{k-\varepsilon})$ time. For the tractable cases, we show that the evaluation problem can be solved in $2^{O(|\varphi|)} \cdot m^{k-\varepsilon}$ time for some $\varepsilon > 0$. Moreover, every tractable fragment reduces, with a $2^{O(|\varphi|)}$ blowup in formula size under DAG representations, to one of the following query languages: (1) Tarski's calculus of relations, (2) a new Boolean modal logic for sparse model checking, and (3) one-variable counting logic.