  Existential rule languages are a family of ontology languages that have been
widely used in ontology-mediated query answering (OMQA). However, for most of
them, the expressive power of representing domain knowledge for OMQA, known as
the program expressive power, is not well-understood yet. In this paper, we
establish a number of novel characterizations for the program expressive power
of several important existential rule languages, including tuple-generating
dependencies (TGDs), linear TGDs, as well as disjunctive TGDs. The
characterizations employ natural model-theoretic properties, and
automata-theoretic properties sometimes, which thus provide powerful tools for
identifying the definability of domain knowledge for OMQA in these languages.

Logic in Computer Science;Artificial Intelligence;Databases