Combined Complexity of Answering Tree-like Queries in OWL 2 QL

Bienvenu M.; Kikot S.; V. V. Podolskii

Publications

?

Combined Complexity of Answering Tree-like Queries in OWL 2 QL

P. 1–4.

Bienvenu M., Kikot S., Podolskii V. V.

Language: English

Text on another site

Keywords: combined complexity queries

In book

Description Logics Workshop, Proceedings of the 28th International Workshop on Description Logics, Athens, Greece, June 7th to 10th, 2015.

Vol. 1350. , CEUR Workshop Proceedings, 2015.

The complexity of ontology-based data access with OWL2QL and bounded treewidth queries

Podolskii V. V., Zakharyaschev M., Bienvenu M. et al., , in: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems* F127745.: ACM, 2017. P. 201–216.

Our concern is the overhead of answering OWL 2QL ontology-mediated queries (OMQs) in ontology-based data access compared to evaluating their underlying tree-shaped and, more generally, bounded treewidth conjunctive queries (CQs). We show that OMQs with bounded depth ontologies have nonrecursive datalog (NDL) rewritings that can be constructed and evaluated in LOGCFL for combined complexity, and ...

Added: September 17, 2017