Query Rewriting for Ontology-Mediated Conditional Answers

Medina Andresel, Magdalena Ortiz, Mantas SimkusAAAI 2020 · DOI

Introduction

In modern data management, the integration of domain knowledge via ontologies has become a standard approach to handle incomplete information. Ontology-Mediated Queries (OMQs) allow systems to infer missing facts using logical axioms. However, traditional OMQs are often too rigid, returning only "certain answers"—results that are logically guaranteed to be true. In many real-world scenarios, users benefit more from "conditional answers": results that would be true if specific, plausible assumptions were met. This paper introduces Assumptive Ontology-Mediated Queries (AOMQs), a framework designed to provide these "yes, if..." responses efficiently.

The Challenge of Incomplete Data and the OWA/CWA Tension

Standard OMQs typically operate under the Open-World Assumption (OWA), where anything not explicitly stated is considered unknown. Conversely, traditional relational databases operate under the Closed-World Assumption (CWA), where anything not stated is false. Combining these two paradigms often leads to computational intractability (coNP-hardness).

Furthermore, users often need to know what conditions would make a query successful, rather than just receiving an empty result set. For instance, in a geospatial query for a hotel near a transit hub, a system should ideally identify potential candidates even if the exact transit link is missing from the local database, provided it can be verified elsewhere. The authors address this by allowing "assumptions" to be part of the query process, effectively turning query answering into a form of abduction or explanation generation.

Methodology: A Three-Step Rewriting Algorithm

The core technical contribution of this work is a query rewriting algorithm for the $DL-Lite_R$ description logic. This logic is widely used because it allows queries to be rewritten into standard First-Order (FO) logic, such as SQL, which can be executed by high-performance database engines. The authors extend this to AOMQs with a three-step process:

  1. Positive TBox Rewriting: The system first incorporates the positive axioms of the ontology into the query using established techniques.
  2. Assumption Pattern Rewriting: This novel step identifies sub-queries that could be satisfied by user-defined "assumption patterns." These are transformed into equality constraints that represent the conditions for a valid answer.
  3. Inconsistency Handling: The algorithm incorporates checks to ensure that the assumptions made do not contradict existing data or the ontology's constraints, such as disjointness axioms.

For scenarios involving "closed predicates"—where certain parts of the data are known to be complete—the authors use universal quantification within the rewritten FO query. This ensures that assumptions about closed data strictly respect the existing database state without sacrificing the efficiency of FO-rewritability.

Experimental Evaluation

The researchers evaluated their framework using the MyITS dataset, a benchmark derived from the OpenStreetMap project. The local dataset comprised approximately 227,000 RDF triples, while a simulated remote geospatial database contained over 2 million triples. Five specific AOMQs ($q_1$ through $q_5$) were designed to reflect real-world geospatial information needs, such as finding hotels in residential areas near subway stations, where spatial relations were treated as assumptions to be verified against the remote source.

Experimental Results

The empirical evaluation demonstrated that the AOMQ framework is highly efficient. As shown in the performance data below, evaluating the rewritten queries and constructing minimal conditional answers typically took less than one second for most queries.

Performance metrics for queries q1-q5 comparing the proposed approach to FedSPARQL.

The results indicate that the proposed approach consistently outperforms standard federated SPARQL queries (using Jena Fuseki). In some instances, the federated approach was up to 10 times slower, even without performing full ontological reasoning. This highlights the advantage of local "candidate" identification via rewriting before remote assumption verification.

Key Insights and Future Work

The most significant finding is that by carefully restricting the use of closed predicates within the assumption framework, FO-rewritability is preserved. This allows sophisticated logical reasoning to be offloaded to standard SQL engines.

While the current work focuses on $DL-Lite_R$, the authors show that for many common Description Logics (like $\mathcal{EL}_\perp$), adding assumptions does not increase the worst-case combined complexity of query answering. Future research will explore more expressive logics like $SHIQ$ and different "shapes" for assumption patterns. Additionally, while theoretically efficient, the practical evaluation of universal quantifiers in SQL can be challenging for some optimizers, suggesting a need for further empirical tuning in database execution.

Conclusion

The AOMQ framework provides a robust and efficient solution for querying incomplete databases with ontologies. By enabling conditional answers and maintaining FO-rewritability, the authors bridge the gap between rigid logical guarantees and the flexible needs of real-world data exploration.

Summary updated

BibTeX
@inproceedings{andresel2020query,
  author = {Medina Andresel and Magdalena Ortiz and Mantas Simkus},
  title = {{Query Rewriting for Ontology-Mediated Conditional Answers}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5660},
}
Figure