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.
Cite
Text
Zhang and Jiang. "Characterizing the Program Expressive Power of Existential Rule Languages." AAAI Conference on Artificial Intelligence, 2022. doi:10.1609/AAAI.V36I5.20540Markdown
[Zhang and Jiang. "Characterizing the Program Expressive Power of Existential Rule Languages." AAAI Conference on Artificial Intelligence, 2022.](https://mlanthology.org/aaai/2022/zhang2022aaai-characterizing/) doi:10.1609/AAAI.V36I5.20540BibTeX
@inproceedings{zhang2022aaai-characterizing,
title = {{Characterizing the Program Expressive Power of Existential Rule Languages}},
author = {Zhang, Heng and Jiang, Guifei},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2022},
pages = {5950-5957},
doi = {10.1609/AAAI.V36I5.20540},
url = {https://mlanthology.org/aaai/2022/zhang2022aaai-characterizing/}
}