Characterizing the Program Expressive Power of Existential Rule Languages

Heng Zhang; Guifei Jiang

AAAI 2022technical4 citations

Characterizing the Program Expressive Power of Existential Rule Languages

Abstract

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.

BibTeX

@inproceedings{aaai2022_characterizingth,
  title = {Characterizing the Program Expressive Power of Existential Rule Languages},
  author = {Heng Zhang and Guifei Jiang},
  booktitle = {AAAI 2022},
  year = {2022}
}