Skip to Main content Skip to Navigation
New interface
Conference papers

Expressivity of Datalog Variants – Completing the Picture

Sebastian Rudolph 1, * Michaël Thomazo 2 
* Corresponding author
1 International Center For Computational Logic [TU Dresden]
Institute of Artificial Intelligence [Dresden]
2 CEDAR - Rich Data Analytics at Cloud Scale
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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 (semi-positive Datalog) and/or a linear order (order-invariant Datalog). When classifying the expressiv-ity 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.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Michaël Thomazo Connect in order to contact the contributor
Submitted on : Friday, April 15, 2016 - 11:10:17 AM
Last modification on : Friday, February 4, 2022 - 3:12:18 AM
Long-term archiving on: : Tuesday, November 15, 2016 - 4:05:09 AM


Files produced by the author(s)


  • HAL Id : hal-01302832, version 1


Sebastian Rudolph, Michaël Thomazo. Expressivity of Datalog Variants – Completing the Picture. 25th International Joint Conference on Artificial Intelligence, Jul 2016, New-York, United States. ⟨hal-01302832⟩



Record views


Files downloads