---
title: "Expressivity of Datalog Variants - Completing the Picture"
authors:
  - "Sebastian Rudolph"
  - "Michaël Thomazo"
doi: ""
url: "https://ijcai.org/proceedings/2016/178"
pdf: "https://ijcai.org/proceedings/2016/0178.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "1230-1235"
track: ""
keywords:
---

# Expressivity of Datalog Variants - Completing the Picture

Sebastian Rudolph, Michaël Thomazo

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 1230-1235.

## 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.