TY - GEN
T1 - Towards universal languages for tractable ontology mediated query answering
AU - Zhang, Heng
AU - Zhang, Yan
AU - You, Jia-Huai
AU - Feng, Zhiyong
AU - Jiang, Guifei
PY - 2020
Y1 - 2020
N2 - ![CDATA[An ontology language for ontology mediated query answering (OMQA-language) is universal for a family of OMQAlanguages if it is the most expressive one among this family. In this paper, we focus on three families of tractable OMQAlanguages, including first-order rewritable languages and languages whose data complexity of the query answering is in AC0 or PTIME. On the negative side, we prove that there is, in general, no universal language for each of these families of languages. On the positive side, we propose a novel property, the locality, to approximate the first-order rewritability, and show that there exists a language of disjunctive embedded dependencies that is universal for the family of OMQAlanguages with locality. All of these results apply to OMQA with query languages such as conjunctive queries, unions of conjunctive queries and acyclic conjunctive queries.]]
AB - ![CDATA[An ontology language for ontology mediated query answering (OMQA-language) is universal for a family of OMQAlanguages if it is the most expressive one among this family. In this paper, we focus on three families of tractable OMQAlanguages, including first-order rewritable languages and languages whose data complexity of the query answering is in AC0 or PTIME. On the negative side, we prove that there is, in general, no universal language for each of these families of languages. On the positive side, we propose a novel property, the locality, to approximate the first-order rewritability, and show that there exists a language of disjunctive embedded dependencies that is universal for the family of OMQAlanguages with locality. All of these results apply to OMQA with query languages such as conjunctive queries, unions of conjunctive queries and acyclic conjunctive queries.]]
UR - https://hdl.handle.net/1959.7/uws:60867
UR - https://aaai.org/Library/AAAI/aaai20contents.php
M3 - Conference Paper
SN - 9781577358350
SP - 3049
EP - 3056
BT - Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, New York, New York, USA, February 7-12, 2020
PB - Association for the Advancement of Artificial Intelligence
T2 - AAAI Conference on Artificial Intelligence
Y2 - 1 January 1980
ER -