Characterization of the Expressivity of Existential Rule Queries

Sebastian RudolphSebastian Rudolph, Michaël ThomazoMichaël Thomazo

Download

Sebastian Rudolph, Michaël Thomazo
Characterization of the Expressivity of Existential Rule Queries
Technical Report, TU Dresden, volume IJCAI-15-RT-RR, May 2015

Details
Bibtex

KurzfassungAbstract
Existential rules (also known as Datalog+/- or tuple-generating dependencies) have been intensively studied in recent years as a prominent formalism in knowledge representation and database systems. We consider them here as a querying formalism, extending classical Datalog, the language of deductive databases. It is well known that the classes of databases recognized by (Boolean) existential rule queries are closed under homomorphisms. Also, due to the existence of a semi-decision procedure (the chase), these database classes are recursively enumerable. We show that, conversely, every homomorphism-closed recursively enumerable query can be expressed as an existential rule query, thus arriving at a precise characterization of existential rules by model-theoretic and computational properties. Although the result is very intuitive, the proof turns out to be non-trivial. This result can be seen as a very expressive counterpart of the prominent Lyndon-Los-Tarski-Theorem characterizing the homomorphism-closed fragment of first-order logic. Notably, our result does not presume the existence of any additional built-in structure on the queried data, such as a linear order on the domain, which is a typical requirement for other characterizations in the spirit of descriptive complexity.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@techreport{RT2015,
  author      = {Sebastian Rudolph and Micha{\"{e}}l Thomazo},
  title       = {Characterization of the Expressivity of Existential Rule
                 Queries},
  institution = {TU Dresden},
  year        = {2015},
  month       = {May}
}