Towards Universal Languages for Tractable Ontology Mediated Query Answering

Authors

  • Heng Zhang Tianjin University
  • Yan Zhang Western Sydney University
  • Jia-Huai You University of Alberta
  • Zhiyong Feng Tianjin University
  • Guifei Jiang Nankai University

DOI:

https://doi.org/10.1609/aaai.v34i03.5699

Abstract

An ontology language for ontology mediated query answering (OMQA-language) is universal for a family of OMQA-languages if it is the most expressive one among this family. In this paper, we focus on three families of tractable OMQA-languages, 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 OMQA-languages with locality. All of these results apply to OMQA with query languages such as conjunctive queries, unions of conjunctive queries and acyclic conjunctive queries.

AAAI-20 Proceedings Cover

Downloads

Published

2020-04-03

How to Cite

Zhang, H., Zhang, Y., You, J.-H., Feng, Z., & Jiang, G. (2020). Towards Universal Languages for Tractable Ontology Mediated Query Answering. Proceedings of the AAAI Conference on Artificial Intelligence, 34(03), 3049-3056. https://doi.org/10.1609/aaai.v34i03.5699

Issue

Vol. 34 No. 03: AAAI-20 Technical Tracks 3

Section

AAAI Technical Track: Knowledge Representation and Reasoning