ML Anthology

Ontology-Mediated Queries with Closed Predicates

Carsten Lutz, Inanç Seylan, Frank Wolter
IJCAI 2015 pp. 3120-3126
/ijcai/2015/lutz2015ijcai-ontology/

Abstract

In the context of ontology-based data access with description logics (DLs), we study ontology-mediated queries in which selected predicates can be closed (OMQCs). In particular, we contribute to the classification of the data complexity of such queries in several relevant DLs. For the case where only concept names can be closed, we tightly link this question to the complexity of surjective CSPs. When also role names can be closed, we show that a full complexity classification is equivalent to classifying the complexity of all problems in coNP, thus currently out of reach. We also identify a class of OMQCs based on ontologies formulated in DL-LiteR that are guaranteed to be tractable and even FO-rewritable.

PDF IJCAI Semantic Scholar

Cite

Text

Lutz et al. "Ontology-Mediated Queries with Closed Predicates." International Joint Conference on Artificial Intelligence, 2015.

Markdown

[Lutz et al. "Ontology-Mediated Queries with Closed Predicates." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/lutz2015ijcai-ontology/)

BibTeX

@inproceedings{lutz2015ijcai-ontology,
  title     = {{Ontology-Mediated Queries with Closed Predicates}},
  author    = {Lutz, Carsten and Seylan, Inanç and Wolter, Frank},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2015},
  pages     = {3120-3126},
  url       = {https://mlanthology.org/ijcai/2015/lutz2015ijcai-ontology/}
}