Expressivity of Datalog Variants - Completing the Picture

Sebastian RudolphSebastian Rudolph, Michaël ThomazoMichaël Thomazo

Download

Sebastian Rudolph, Michaël Thomazo
Expressivity of Datalog Variants - Completing the Picture
In Subbarao Kambhampati, eds., Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'16), 1230-1236, July 2016. AAAI Press

Details
Bibtex

KurzfassungAbstract
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.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{RT2016,
  author    = {Sebastian Rudolph and Micha{\"{e}}l Thomazo},
  title     = {Expressivity of Datalog Variants - Completing the Picture},
  editor    = {Subbarao Kambhampati},
  booktitle = {Proceedings of the 24th International Joint Conference on
               Artificial Intelligence (IJCAI'16)},
  publisher = {AAAI Press},
  year      = {2016},
  month     = {July},
  pages     = {1230-1236}
}