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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01302832
Contributor : Michaël Thomazo <>
Submitted on : Friday, April 15, 2016 - 11:10:17 AM
Last modification on : Friday, June 14, 2019 - 1:58:56 AM
Long-term archiving on : Tuesday, November 15, 2016 - 4:05:09 AM

File

ijcai-16-rt-tr.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01302832, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

192

Files downloads

472