TL;DR
This paper introduces a new extension to the DL-Lite family of description logics that allows for n-ary predicates on concrete domains (like numbers and strings). This enables more expressive queries and ontologies, particularly for comparing multiple data values. The authors show how to rewrite these queries into a form that can be efficiently answered by standard database systems, achieving polynomial data complexity.
What Problem Does This Paper Address?
Ontology-based query answering (OBQA) aims to answer queries over data using background knowledge from an ontology. A key challenge is handling "concrete domains" – real-world data like numbers and strings – and the built-in predicates (like >, <, =) used to query them. Previous work on DL-Lite with concrete domains was limited to unary predicates, meaning they could only constrain a single data value at a time. This is insufficient for many real-world scenarios where relationships between multiple data points are crucial (e.g., calculating pulse pressure from systolic and diastolic blood pressure). This paper addresses this limitation by extending DL-Lite to support n-ary concrete domain predicates, enabling more expressive queries and ontologies, and then provides a method for rewriting these queries to maintain efficient computation.
Methods
The core contribution is the development of a query rewriting technique for a new DL-Lite variant that supports n-ary concrete domain predicates. The authors define a set of restrictions on these concrete domains (termed "cr-admissible") that ensure decidability and computational tractability. They then introduce a novel ontology language, DL-Lite(HF)(D), which extends DL-Lite with these n-ary concrete domain predicates.
The rewriting process involves extending existing techniques for DL-Lite query rewriting. They introduce new operators like split and inferd to handle the n-ary predicates. The overall approach involves iteratively applying these operators to transform the original query and ontology into a set of equivalent queries that can be evaluated over a database. This process is designed to achieve "combined rewritability," meaning both the query and the data representation can be transformed, leading to polynomial data complexity. For the specific case of unary concrete domains, they show that their approach subsumes existing FO rewritability results.
Datasets
Not discussed in the paper. The paper focuses on theoretical results and methods rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Beyond Unary Predicates: The most significant insight is the extension of concrete domain reasoning from unary to n-ary predicates. This unlocks a much richer expressiveness for ontologies and queries, allowing for comparisons and relationships between multiple data values, which is crucial for many real-world applications.
- Cr-Admissibility is Key: The paper identifies specific properties for concrete domains (polynomiality, convexity, functionality, constructivity) that are essential for achieving efficient query rewriting. This provides a clear framework for what kinds of concrete domains can be effectively integrated into DL-Lite.
- Unified Rewriting Approach: The authors demonstrate that their combined rewriting approach can handle both the general case of n-ary predicates and also subsume existing results for unary predicates, showing the generality and power of their framework.
- Convexity and Infinitediff Equivalence: For concrete domains with equality predicates, the paper shows an interesting equivalence between convexity and the
infinitediffproperty, which was previously considered separately.
Key Results
- The paper defines a new DL-Lite variant (DL-Lite(HF)(D)) that supports n-ary concrete domain predicates.
- It establishes conditions (cr-admissibility) under which Conjunctive Queries (CQs) with built-in predicates can be combined rewritten with ontologies expressed in this new language.
- This combined rewriting achieves polynomial data complexity for query answering.
- For the specific case of unary concrete domains, the results subsume existing FO rewritability results, demonstrating a generalization.
- The paper shows that for safe and T-restricted CQs, the entailment problem is in P in terms of data complexity.
Limitations and Future Work
- T-Restrictedness: The rewriting approach assumes that queries are "T-restricted," meaning they only use concrete domain predicates that appear in the ontology (TBox). This is a practical limitation, as users might want to query using predicates not explicitly in the TBox.
- Size of Rewriting: While the rewriting is correct and achieves polynomial complexity, the size of the rewritten queries might still be large. Future work aims to investigate more concise rewritings or alternative target languages.
- Concrete Domain Variables in ABox: The current framework does not explicitly support concrete domain variables in the ABox (assertions). Extending this is a direction for future research.
- Local Identification Constraints (Keys): Incorporating keys and functional roles on the right-hand side of inclusions are mentioned as potential extensions to investigate FO rewritability in the general case.
- Empirical Evaluation: The paper is theoretical; future work could involve implementing the rewriting and evaluating its performance on real-world data.
Summary updated