?
Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries
P. 45–57.
Bienvenu M., Kikot S., Podolskii V. V.
This paper further investigates the succinctness landscape of query rewriting in OWL 2 QL. We clarify the worst-case size of positive existential (PE), non-recursive Datalog (NDL), and first-order (FO) rewritings for various classes of tree-like conjunctive queries, ranging from linear queries up to bounded treewidth queries. More specifically, we establish a superpolynomial lower bound on the size of PE-rewritings that holds already for linear queries and TBoxes of depth 2. For NDL-rewritings, we show that polynomial-size rewritings always exist for tree-shaped queries with a bounded number of leaves (and arbitrary TBoxes), and for bounded treewidth queries and bounded depth TBoxes. Finally, we show that the succinctness problems concerning FO-rewritings are equivalent to well-known problems in Boolean circuit complexity. Along with known results, this yields a complete picture of the succinctness landscape for the considered classes of queries and TBoxes
In book
Vol. 1193: Informal Proceedings of the 27th International Workshop on Description Logics. Vienna, Austria, July 17-20, 2014. , Wien: CEUR Workshop Proceedings, 2014.
Gerasimova O., Kikot S., Podolskii V. V. et al., Artificial Intelligence 2022 Vol. 309 Article 103738
Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description logic ontologies and constructing their optimal rewritings to standard database queries. Originated in ontology-based data access and datalog optimisation, this problem is known to be computationally very complex in general, with no explicit syntactic characterisations available. In this ...
Added: May 30, 2022
Zakharyaschev M., Savateev Y., Ryzhikov V., Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021.
Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) given in linear temporal logic LTL over (Z, <) and deciding whether it is rewritable to an FO(<)-query, possibly with extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering ...
Added: November 6, 2021
CEUR-WS.org, 2019.
Added: October 29, 2019
Gerasimova O., Kikot S., Zakharyaschev M., , in: Description Logic, Theory Combination, and All That.: Berlin: Springer, 2019. P. 329–351.
It has recently been shown that first-order- and datalog-rewritability of ontology-mediated queries (OMQs) with expressive ontologies can be checked in NExpTime using a reduction to CSPs. In this paper, we present a case study for OMQs with Boolean conjunctive queries and a fixed ontology consisting of a single covering axiom 𝐴 -> 𝐹 v 𝑇, A -> F v T, possibly supplemented with ...
Added: July 29, 2019
Berlin: Springer, 2019.
This Festschrift has been put together on the occasion of Franz Baader's 60th birthday to celebrate his fundamental and highly influential scientific contributions. The 30 papers in this volume cover several scientific areas that Franz Baader has been working on during the last three decades, including description logics, term rewriting, and the combination of decision procedures. We hope that ...
Added: July 29, 2019
Zakharyaschev M., Kontchakov R., , in: Artificial Intelligence* 234.: [б.и.], 2016. P. 78–119.
We consider conjunctive query inseparability of description logic knowledge bases with respect to a given signature - a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query inseparability and develop worst-case optimal decision algorithms for fragments of Horn-ALCHI, including the description ...
Added: September 18, 2017
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
Podolskii V. V., Bienvenu M., Kikot S., , in: Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on.: Los Alamitos: IEEE, 2015. P. 317–328.
This paper investigates the impact of query topology on the difficulty of answering conjunctive queries in the presence of OWL 2 QL ontologies. Our first contribution is to clarify the worst-case size of positive existential (PE), non-recursive Data log (NDL), and first-order (FO) rewritings for various classes of tree-like conjunctive queries, ranging from linear queries ...
Added: October 19, 2016
Botoeva E., Kontchakov R., Ryzhikov V. et al., , in: Proceedings, Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR-14).: Palo Alto: AAAI Press, 2014. Ch. 25 P. 25.1–25.10.
We investigate conjunctive query inseparability of description logic (DL) knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We study the data and combined complexity of deciding KB query inseparability for fragments of Horn-ALCHI, including the DLs underpinning OWL 2 QL and OWL ...
Added: March 25, 2015
Mosurovic M., Krdzavac N., Graves H. et al., Journal of Artificial Intelligence Research 2013 Vol. 47 P. 809–851
We design a decidable extension of the description logic SROIQ underlying the Web Ontology Language OWL 2. The new logic, called SR+OIQ, supports a controlled use of role axioms whose right-hand side may contain role chains or role unions. We give a tableau algorithm for checking concept satisfiability with respect to SR+OIQ ontologies and prove ...
Added: March 25, 2015
Artale A., Kontchakov R., Ryzhikov V. et al., ACM Transactions on Computational Logic 2014 Vol. 15 No. 3 P. 25.1–25.50
We design temporal description logics (TDLs) suitable for reasoning about temporal conceptual data models and investigate their computational complexity. Our formalisms are based on DL-Lite logics with three types of concept inclusions (ranging from atomic concept inclusions and disjointness to the full Booleans), as well as cardinality constraints and role inclusions. The logics are interpreted ...
Added: March 25, 2015
Gottlob G., Kikot S., Kontchakov R. et al., Artificial Intelligence 2014 Vol. 213 P. 42–59
We give a solution to the succinctness problem for the size of first-order rewritings of conjunctive queries in ontology-based data access with ontology languages such as OWL 2 QL , linear Datalog± and sticky Datalog±. We show that positive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for intensional predicates in the ...
Added: March 24, 2015
Artale A., Kontchakov R., Wolter F. et al., , in: Proceedings of the 23rd International Joint Conference on Artificial Intelligence.: Beijing: AAAI Press, 2013. Ch. 112 P. 711–718.
Our aim is to investigate ontology-based data access over temporal data with validity time and ontologies capable of temporal conceptual modelling. To this end, we design a temporal description logic, TQL, that extends the standard ontology language OWL 2 QL, provides basic means for temporal conceptual modelling and ensures first-order rewritability of conjunctive queries for ...
Added: March 24, 2015
Kikot S., Kontchakov R., Podolskii V. V. et al., , in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: NY: ACM, 2014. P. 1–10.
We investigate the size of first-order rewritings of conjunctive queries over OWL 2 QL ontologies of depth 1 and 2 by means of hypergraph programs computing Boolean functions. Both positive and negative results are obtained. Conjunctive queries over ontologies of depth 1 have polynomial-size nonrecursive datalog rewritings; tree-shaped queries have polynomial positive existential rewritings; however, ...
Added: October 20, 2014
Gottlob G., Kikot S., Kontchakov R. et al., Artificial Intelligence 2014 Vol. 213 P. 42–59
We give a solution to the succinctness problem for the size of first-order rewritings of conjunctive queries in ontologybased data access with ontology languages such as OWL2QL, linear Datalog and sticky Datalog. We show that positive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for intensional predicates in the case ...
Added: October 20, 2014