Expressivity of Datalog Variants – Completing the Picture

Sebastian Rudolph, Michaël Thomazo

TL;DR

This paper tackles the expressivity of Datalog, a popular knowledge representation language, and its variants. The authors provide a complete picture of the relationships between different Datalog versions and homomorphism-closed queries, introducing a novel query that is both computationally efficient and preserves structure but cannot be expressed by a standard order-invariant Datalog.

What Problem Does This Paper Address?

Knowledge representation (KR) languages are crucial for formalizing and querying information. Datalog is a widely used formalism, forming the basis for many KR languages and query systems. Researchers are interested in understanding the expressive power of Datalog and its extensions, particularly how they relate to computational complexity and structural properties like homomorphism preservation.

The paper focuses on two key extensions to Datalog:

  1. Input Negation (Semipositive Datalog): Allowing negation of database predicates.
  2. Linear Order (Order-Invariant Datalog): Enabling the use of a predefined order on domain elements.

These extensions lead to four distinct Datalog variants. A central question is how these variants compare in terms of what queries they can express, especially when considering queries that are "homomorphism-closed." A query is homomorphism-closed if any structure that "looks like" a query result also counts as a query result. While some relationships are known (e.g., semipositive Datalog with a linear order can express all polynomial-time computable queries), a complete picture, particularly concerning homomorphism-closed queries and their expressibility without negation and linear order, was missing. This paper aims to fill those gaps.

Methods

The paper employs a combination of theoretical analysis and construction of novel queries. Key methods include:

  • Formal Definitions: Rigorous definitions of Datalog variants, homomorphism-closed queries, and related concepts like perfect matchings.
  • Query Construction: The core technical contribution is the construction of a specific query that is:
  • PTIME-computable: Can be evaluated in polynomial time.
  • Homomorphism-closed: Preserves structural properties under homomorphisms.
  • Not expressible in order-invariant Datalog: Demonstrates a limitation of this Datalog variant. This construction involves defining a database schema with predicates for encoding graphs and linear orders, then defining a query that leverages these to check for perfect matchings in a homomorphism-preserving way.

  • Circuit Construction: To prove the non-expressibility of the constructed query in order-invariant Datalog, the authors transform the query into a polynomial-size monotone Boolean circuit. This is a standard technique in descriptive complexity.

  • Proof Techniques: The paper relies heavily on logical proofs, including induction, to establish properties of queries and programs, and to demonstrate equivalences and non-equivalences between query classes.
  • Relating to Existing Results: The work builds upon and extends known results, such as Feder and Vardi's work on semipositive Datalog and Razborov's result on the circuit complexity of perfect matchings.

Datasets

Not discussed in the paper. The paper focuses on theoretical query expressivity rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Completing the Expressivity Map: The paper provides a definitive Venn diagram showing the precise relationships between five query classes: Datalog, Datalog(¬), Datalog(≤), Datalog(≤, ¬), and Homomorphism-Closed (HC) queries. This clarifies long-standing questions.
  • The Surprising Power of Negation: A key finding is that even for homomorphism-closed queries (which are inherently monotonic), input negation is not dispensable for expressibility in Datalog without a linear order. This is counter-intuitive, as negation is typically associated with non-monotonicity.
  • A Novel PTIME Homomorphism-Closed Query: The paper introduces a query that is PTIME-computable and homomorphism-closed but cannot be expressed by order-invariant Datalog. This query is crucial for establishing the boundaries of expressivity.
  • Bridging Graph Theory and Logic: The paper elegantly connects graph theory problems (perfect matchings) with logical query languages, using the complexity of checking for perfect matchings (via Boolean circuits) to prove limitations of Datalog variants.

Key Results

  • A Complete Picture of Datalog Variants: The paper establishes a precise hierarchy of expressivity for four Datalog variants and the class of homomorphism-closed queries, visualized in a Venn diagram.
  • Non-Expressibility Result: The paper proves that a specific PTIME-computable, homomorphism-closed query cannot be expressed in order-invariant Datalog. This is demonstrated by showing that such an expressibility would imply the existence of a polynomial-size monotone Boolean circuit for the perfect matching problem, which is known to be impossible.
  • Confirmation of Existing Results: The paper re-affirms and contextualizes known results, such as the expressiveness of semipositive Datalog with a linear order and the relationship between Datalog and homomorphism-closed queries.

Limitations and Future Work

  • Limitations: The paper's primary limitation, as acknowledged by the authors, is the counter-intuitive finding that input negation is necessary for expressing certain homomorphism-closed (monotonic) queries in Datalog without a linear order. This suggests a deeper complexity in the interaction between monotonicity and negation than initially assumed.
  • Future Work: The authors express a desire to further characterize other variants of Datalog by their model-theoretic and computational properties. This suggests ongoing research into the rich landscape of logical query languages and their expressive capabilities.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{rudolph2016expressivity,
  author = {Sebastian Rudolph and Michaël Thomazo},
  title = {{Expressivity of Datalog Variants – Completing the Picture}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=rJNtFmzuWH},
}
Figure