Exponential size gap found between two logic query languages
An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations
Logic in Computer ScienceComputational Complexity
Summary
Some ways of describing database queries use different logical languages. The authors show that when you switch from one language called three-variable logic to another called the calculus of relations, the descriptions can get exponentially larger. This means that certain logical expressions become much more complex and longer when translated between these languages. Their proof works even on small or finite data and applies to related query systems too.
What this means in practice
- •For database system designers: Avoid attempts to translate three-variable logic queries into calculus of relations when aiming for compact representations by understanding the exponential size penalty.
- •For query language developers: Use this size gap knowledge to assess complexity trade-offs when extending or combining logical query languages for graph and matrix queries.
A theory result. No direct application yet.
Authors
Yuya Uezato
Abstract
Three-variable first-order logic (FO3) and the calculus of relations (CoR) define the same binary queries, an equivalence going back to Tarski in the 1940s. While the classical translation $\text{FO3} \Rightarrow \text{CoR}$ is exponential, we prove that this blow-up is unavoidable, resolving a long-standing open question. We construct positive formulas $\varphi$ with a single quantifier whose equivalent terms require size $2^{Ω(|\varphi|)}$, even over finite structures and circuit representations with subterm sharing. Our proof uses a preservation argument over a single finite structure. This approach applies beyond our primary question, establishing the lower bound even for size-specific circuits and bounded-error randomized circuits, and yielding an analogous exponential gap for the matrix query language MATLANG.