Vladimir V. Podolskii

Ontology-Mediated Queries: Combined Complexity and Succinctness of\n Rewritings via Circuit Complexity

2016 · arXiv (Cornell University)

We give solutions to two fundamental computational problems in ontology-based\ndata access with the W3C standard ontology language OWL 2 QL: the succinctness\nproblem for first-order rewritings of ontology-mediated queries (OMQs), and the\ncomplexity problem for OMQ answering. …