First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics


  • David Toman University of Waterloo
  • Grant Weddell University of Waterloo



Knowledge Representation And Reasoning (KRR)


We consider first-order (FO) rewritability for query answering in ontology mediated querying (OMQ) in which ontologies are formulated in Horn fragments of description logics (DLs). In general, OMQ approaches for such logics rely on non-FO rewriting of the query and/or on non-FO completion of the data, called a ABox. Specifically, we consider the problem of FO rewritability in terms of Beth definability, and show how Craig interpolation can then be used to effectively construct the rewritings, when they exist, from the Clark’s completion of Datalog-like programs encoding a given DL TBox and optionally a query. We show how this approach to FO rewritability can also be used to (a) capture integrity constraints commonly available in backend relational data sources, (b) capture constraints inherent in mapping such sources to an ABox , and (c) can be used an alternative to deriving so-called perfect rewritings of queries in the case of DL-Lite ontologies.




How to Cite

Toman, D., & Weddell, G. (2022). First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5897-5905.



AAAI Technical Track on Knowledge Representation and Reasoning