Order-invariant cluster logic includes local-order-invariant logic on finite structures
Order-Invariant CFO Contains Local-Order-Invariant FO
Logic in Computer Science
Summary
The paper studies different ways of writing logical statements that are unaffected by how elements are ordered in a structure, focusing on certain technical subsets of these logics. It shows that one such logic called order-invariant cluster first-order logic (CFO) is powerful enough to express everything that the local-order-invariant first-order logic can on any finite structure. This settles a previous question about their relative expressiveness. The authors also show that these logics behave the same on graphs with limited connections per node, and that checking statements in these logics can be done efficiently in such cases.
What this means in practice
- •For graph database engineers: Improve query evaluation efficiency on bounded-degree graph databases using the equivalence of order-invariant CFO and local-order-invariant FO.
- •For database system developers: Use the logical collapse results to optimize query engines handling logic formulas invariant under data ordering in bounded-degree structured data.
A theory result. No direct application yet.
Authors
Derek R. Aoki
Abstract
Order-invariant cluster first-order logic (CFO) and local-order-invariant first-order logic are two fragments of order-invariant first-order logic, both motivated by the study of invariant logics on classes of bounded degree. Our main result is that order-invariant CFO contains local-order-invariant FO on arbitrary classes of finite structures, settling the conjecture of Ghasemi and Grange that order-invariant CFO contains plain FO. By combining this with a collapse result of Ghasemi and Grange, we obtain the equivalence of FO, local-order-invariant FO, and order-invariant CFO on classes of finite colored graphs of bounded degree. The proof makes use of Gaifman normal form, which allows our translation from local-order-invariant FO to order-invariant CFO to be effective. Combined with the fixed-parameter tractability of model-checking for order-invariant CFO on bounded-degree colored graph classes, this shows that model-checking for local-order-invariant FO on bounded-degree colored graph classes is fixed-parameter tractable. To generalize our collapse and model-checking results beyond colored graphs, we use a method based on first-order interpretations which also yields a collapse of order-invariant FO to FO when restricted to graph classes of bounded shrub-depth. Finally, we give an application to the database-motivated frozen-witness logic of Abiteboul, Simon, and Vianu by showing that local-order-invariant FO contains deterministic frozen-witness FO, and thus that deterministic frozen-witness FO collapses to FO on classes of finite structures of bounded degree.