Expressivity of Datalog Variants – Completing the Picture

Sebastian Rudolph 1, * Michaël Thomazo 2
* Auteur correspondant
1 International Center For Computational Logic [TU Dresden]
Institute of Artificial Intelligence [Dresden]
2 CEDAR - Rich Data Analytics at Cloud Scale
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.
Type de document :
Communication dans un congrès
25th International Joint Conference on Artificial Intelligence, Jul 2016, New-York, United States. Proceedings of the 25th International Joint Conference on Artificial Intelligence, 2016
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01302832
Contributeur : Michaël Thomazo <>
Soumis le : vendredi 15 avril 2016 - 11:10:17
Dernière modification le : samedi 18 février 2017 - 01:14:46
Document(s) archivé(s) le : mardi 15 novembre 2016 - 04:05:09

Fichier

ijcai-16-rt-tr.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. Proceedings of the 25th International Joint Conference on Artificial Intelligence, 2016. 〈hal-01302832〉

Partager

Métriques

Consultations de la notice

143

Téléchargements de fichiers

182