Ontology-Mediated Queries with Closed Predicates

Carsten Lutz, Inanç Seylan, Frank Wolter

Abstract

This paper investigates the computational complexity of Ontology-Mediated Queries (OMQs) when a subset of predicates is subject to the Closed World Assumption (CWA). While traditional Ontology-Based Data Access (OBDA) typically operates under the Open World Assumption (OWA), practical applications often involve curated datasets where certain information is known to be complete. The authors establish a significant theoretical link between these queries (OMQCs) and surjective Constraint Satisfaction Problems (CSPs). Their findings reveal that while certain fragments of DL-Lite remain tractable, the closure of role names generally elevates the complexity of query answering to coNP-hardness, effectively simulating NP-complete problems.

Introduction

In the field of Ontology-Based Data Access (OBDA), the standard paradigm is the Open World Assumption (OWA). Under OWA, the absence of a fact in a database is treated as unknown rather than false, which is ideal for integrating incomplete or distributed data sources. However, this assumption is often too permissive for enterprise environments where specific datasets—such as a company's official product catalog or a list of geographic regions—are known to be exhaustive.

To bridge this gap, the authors explore "Ontology-Mediated Queries with Closed Predicates" (OMQCs). This framework allows users to designate specific predicates (categories or relationships) as "closed," meaning they are interpreted under the Closed World Assumption. While this hybrid approach is practically desirable, it introduces significant mathematical complexity. This paper aims to classify the data complexity of OMQCs across various Description Logics (DLs) and identify the boundaries between tractability and NP-hardness.

Methodology

The research utilizes theoretical complexity analysis to categorize OMQCs based on three primary dimensions:

  1. Description Logic Expressivity: The study spans from lightweight logics like DL-Lite and $\mathcal{EL}$ to more expressive logics such as $\mathcal{ALCHI}$.
  2. Closure Scope: The authors distinguish between closing "concept names" (unary predicates representing classes) and "role names" (binary predicates representing relationships).
  3. Query Structure: The analysis compares Conjunctive Queries (CQs) against their quantifier-free counterparts.

A central technical contribution of the paper is the establishment of reductions between OMQCs and Surjective Constraint Satisfaction Problems (CSPs). Unlike standard CSPs, where any mapping satisfying constraints is sufficient, surjective CSPs require the mapping to cover the entire target domain. This connection allows the authors to leverage deep results from graph theory and algebra to analyze the complexity of query answering.

Theoretical Framework: The Surjective Connection

The authors demonstrate that when concept names are closed, the problem of answering OMQCs becomes equivalent to solving surjective CSPs. This is a significant insight because surjective CSPs are notoriously more difficult to classify than standard CSPs. Many cases in surjective CSP theory remain open problems in mathematics, implying that a complete classification of OMQCs with closed concepts depends on future breakthroughs in the study of surjective mappings.

Furthermore, the paper highlights that closing role names (relationships) is significantly more powerful—and computationally expensive—than closing concepts. The authors prove that closing roles allows for the simulation of any NP Turing Machine. This suggests that a general "dichotomy theorem" (a rule stating that every query is either PTIME or NP-hard) for the role-closing case is currently beyond reach.

Key Results and Tractability

The paper provides several critical bounds for the data complexity of OMQCs:

  • General Complexity: For a wide range of expressive description logics, answering OMQCs is shown to be in coNP.
  • The "Safe Zone" for Tractability: The authors identify a specific fragment that remains FO-rewritable. This means the query can be translated into standard SQL and executed efficiently by relational database management systems. This tractability holds for DL-LiteR ontologies when using quantifier-free queries, provided there are no specific structural conflicts between open and closed roles.
  • Hardness of Role Closure: The study establishes that for any NP-complete problem, there exists a corresponding OMQC with closed roles of equivalent hardness. This result underscores the inherent difficulty of managing closed relationships in an automated reasoning context.

Discussion and Future Work

While the paper maps out the complexity landscape of OMQCs, it also identifies several "gaps" for future research. The "Surjective Gap" remains the most prominent; until the complexity of surjective CSPs is fully understood, the exact complexity of OMQCs with closed concepts will remain partially obscured.

Additionally, the current tractable results are largely limited to quantifier-free queries. In many real-world scenarios, existential quantifiers (e.g., "Find all employees who have some certification from a closed list") are essential. Expanding the "safe zone" to include restricted forms of quantification is a vital next step for making OMQCs practical. Finally, while the paper provides the logic for FO-rewritability, the development of production-ready tools and benchmarks is necessary to transition these theoretical insights into the domain of applied OBDA.

Summary updated

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.
BibTeX
@inproceedings{lutz2015ontology,
  author = {Carsten Lutz and Inanç Seylan and Frank Wolter},
  title = {{Ontology-Mediated Queries with Closed Predicates}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure