Abstract
Computational and model-theoretic properties of logical languages constitute a central field of research in logic-based knowledge representation. Datalog is a very popular formalism, a de-facto standard for expressing and querying knowledge. Diverse results exist regarding the expressivity of Datalog and its extension by input negation (semipositive Datalog) and/or a linear order (order-invariant Datalog). When classifying the expressivity of logical formalisms by their model-theoretic properties, a very natural and prominent such property is preservation under homomorphisms. This paper solves the remaining open questions needed to arrive at a complete picture regarding the interrelationships between the class of homomorphism-closed queries and the query classes related to the four versions of Datalog. Most notably, we exhibit a query that is both homomorphism-closed and computable in polynomial time but cannot be expressed in order-invariant Datalog.
Introduction: The Datalog Expressivity Gap
In the field of Knowledge Representation (KR), Datalog serves as a foundational language for querying structured data. To enhance its power, researchers have explored various extensions, most notably semipositive Datalog ($\neg$), which allows negation on input facts, and order-invariant Datalog ($\leq$), which permits the use of a linear order on domain elements as long as the query result remains independent of the specific order chosen.
A major goal in descriptive complexity is to characterize computational classes like PTIME using logical languages. It is well-established that semipositive Datalog with a linear order captures exactly PTIME. Furthermore, plain Datalog is known to be limited to queries that are homomorphism-closed—meaning if a query is true for a database, it remains true for any database to which the original can be mapped via a homomorphism. The critical open question addressed by this research is whether order-invariant Datalog can capture all homomorphism-closed queries that are computable in polynomial time ($HC \cap PTIME$).
Methodology: Bridging Logic and Circuit Complexity
The authors prove that order-invariant Datalog cannot capture all $HC \cap PTIME$ queries through a sophisticated reduction to circuit complexity. They construct a specific Boolean query that is both PTIME-computable and homomorphism-closed, centered around the Perfect Matching problem in graphs.
The core of the proof demonstrates that if this query were expressible in order-invariant Datalog, one could derive a polynomial-size monotone Boolean circuit for the perfect matching problem. However, a landmark result by Alexander Razborov (1985) established that such circuits must be super-polynomial in size. To reconcile the non-monotonic nature of perfect matching with the requirement of homomorphism-closure, the authors introduce a "compression" technique. This involves defining "enlisted elements" and congruence relations to transform arbitrary structures into well-behaved ones where perfect matchings can be safely evaluated using auxiliary predicates like first, last, and next as shown in Figure 4.
Results: The Final Map of Datalog Variants
The primary contribution of this work is the completion of the "expressivity map" for Datalog variants. The authors successfully demonstrate that $HC \cap PTIME \not\subseteq Datalog(\leq)$. This finding reveals a fundamental gap: there are monotonic PTIME queries that even order-invariant Datalog cannot express.
As shown in Figure 1, the relationships between the five key query classes are now fully characterized:
- Datalog: Plain Datalog, inherently homomorphism-closed.
- Datalog($\neg$): Semipositive Datalog.
- Datalog($\leq$): Order-invariant Datalog.
- Datalog($\leq, \neg$): Order-invariant semipositive Datalog, which is equivalent to PTIME.
- HC: The class of all homomorphism-closed queries.
The result highlights that the gap between Datalog and PTIME is not merely a matter of having access to an order; it involves deeper constraints on how logic processes information compared to monotone circuits.
Conclusion and Future Directions
This paper settles a long-standing question by showing that order-invariance is a subtle and limited property. Despite being able to "see" an order, the invariance requirement significantly restricts the logic's computational reach. One intriguing takeaway is the "monotonicity paradox": to express certain highly monotonic queries, one must utilize negation—the very epitome of non-monotonicity. Future research may extend these findings to other Datalog variants, such as those used in Description Logics or systems involving existential rules.
Summary updated