---
title: "Ontology-Mediated Queries with Closed Predicates"
authors:
  - "Carsten Lutz"
  - "Inanç Seylan"
  - "Frank Wolter"
doi: ""
url: "https://ijcai.org/proceedings/2015/440"
pdf: "https://ijcai.org/proceedings/2015/0440.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "3120-3125"
track: "Special Track on Knowledge Representation and Reasoning"
keywords:
---

# Ontology-Mediated Queries with Closed Predicates

Carsten Lutz, Inanç Seylan, Frank Wolter

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 3120-3125.

## 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.