Query Answering in DL-Lite with Datatypes: A Non-Uniform Approach

André Hernich, Julio Lemos, Frank WolterAAAI 2017 · DOI

Abstract

This paper investigates the computational complexity of answering ontology-mediated queries (OMQs) in the DL-Lite family of description logics when extended with datatypes. By establishing a formal link between OMQs and Constraint Satisfaction Problems (CSPs), the authors introduce a non-uniform analysis framework. They identify the Bounded Match Depth Property (BMDP) as a key condition for decidability and provide a complete complexity classification for the rational numbers with order $(\mathbb{Q}, \le)$, distinguishing between tractable (PTime) and hard (coNP-complete) query patterns.

Introduction

In Ontology-Based Data Management (OBDM), the DL-Lite family of description logics is a cornerstone for efficient query answering over large, heterogeneous datasets. However, the integration of expressive datatypes—such as numerical comparisons for ages, prices, or timestamps—presents a significant challenge. Even basic comparisons like "is price A less than price B?" can escalate the computational complexity to NP-hard or render the problem undecidable.

To maintain tractability, standard languages like OWL 2 QL impose severe restrictions on datatype usage. This paper argues that such "one-size-fits-all" restrictions are overly conservative. Instead, the authors propose a "non-uniform" approach to identify specific patterns of datatype usage that remain computationally efficient.

Theoretical Framework and Methods

The core of the research involves bridging Description Logics with Constraint Satisfaction Problems (CSPs). The authors developed several technical innovations to facilitate this link:

  1. Universal Pre-Models: Standard DL-Lite uses a "chase" procedure to generate a canonical model. When datatypes are involved, the authors introduce "pre-models" that utilize placeholders (data nulls). This allows for reasoning about constraints without immediate commitment to specific numerical values.
  2. Bounded Match Depth Property (BMDP): To ensure decidability, the authors propose the BMDP. This property guarantees that answering a query only requires inspecting a limited "depth" of the inferred data.
  3. The CSP Link: The authors prove that for queries satisfying BMDP, query answering is polynomially reducible to the complement of a CSP over the relevant datatype. This reduction allows the application of extensive CSP research to the field of ontology-mediated querying.
Structural representation of a pre-model used to analyze query patterns and their interaction with datatypes.

The figure above illustrates the complex structural relationships within a pre-model, showing how individuals (nodes) and roles (edges) interact. Such structures are central to determining whether a specific query pattern satisfies the BMDP and how it maps to a corresponding CSP.

Key Insights and Results

The research yields a comprehensive classification of complexity for specific datatypes:

  • Dichotomy for $(\mathbb{Q}, \le)$: For the datatype of rational numbers with the "less than or equal" relation, the authors establish a dichotomy. Query patterns are either tractable (PTime) or hard (coNP-complete), with no intermediate complexity.
  • Syntactic Safe Zones: The study identifies "min-patterns" and "max-patterns" (specific ways of structuring inequalities) that are guaranteed to be tractable. For instance, "one-to-many" or "many-to-one" comparison structures (star shapes) typically fall into the efficient category.
  • Undecidability and Bounds: The paper warns that for datatypes like integers $(\mathbb{Z}, \le)$ or equality on rationals $(\mathbb{Q}, =)$, query answering can be undecidable without the BMDP restriction. Furthermore, the simplest tractable patterns are shown to reside within the NLogSpace complexity class.

Conclusion and Future Work

This work provides a robust theoretical foundation for expanding the expressiveness of DL-Lite with datatypes without sacrificing efficiency. By shifting from a uniform restriction to a pattern-based analysis, the authors open the door for more flexible OBDM systems.

Future research directions include extending this framework to other critical datatypes such as strings, spatial data, and temporal relations. Additionally, the practical integration of these "safe patterns" into existing query engines is a vital next step to validate the theoretical findings in real-world Semantic Web applications.

Summary updated

BibTeX
@inproceedings{hernich2017query,
  author = {André Hernich and Julio Lemos and Frank Wolter},
  title = {{Query Answering in DL-Lite with Datatypes: A Non-Uniform Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10689},
}
Figure