Characterizing the Program Expressive Power of Existential Rule Languages
Article Images
Authors
- Heng Zhang Tianjin University
- Guifei Jiang Nankai University
DOI:
https://doi.org/10.1609/aaai.v36i5.20540Keywords:
Knowledge Representation And Reasoning (KRR)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.How to Cite
Zhang, H., & Jiang, G. (2022). Characterizing the Program Expressive Power of Existential Rule Languages. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5950-5957. https://doi.org/10.1609/aaai.v36i5.20540
Issue
Section
AAAI Technical Track on Knowledge Representation and Reasoning