Long rewritings, short rewritings
Stanislav Kikot, Roman Kontchakov, Vladimir Vladimirovich Podolskii, Michael Zakharyaschev · BIROn (Birkbeck, University of London) · 2012
An ontology language L is said to enjoy FO-rewritability if any conjunctive query (CQ) q over any ontology T , given in L, can be transformed into an FOformula q′ such that, for any data A, all answers to q over the knowledge base (T ,A) can be found by querying q′ over A using a standard relational database management system (RDBMS). Ontology languages with this property include the OWL2QL profile of OWL2, which is based on description logics of the DL-Lite family [7, 16, 2], and fragments of Datalog± such as linear or sticky TGDs [5, 6]. Various rewriting techniques have been implemented in the systems QuOnto [1], REQUIEM [15], Presto [22], Nyaya [8], IQAROS and Quest. The idea of using languages with FO-rewritability for ontology-based data access (OBDA) relies on the empirical fact that RDBMSs are usually very efficient in practice. However, the first rewritings of CQs over OWL2QL ontologies [7, 15] turned out to be too lengthy even for modern RDBMSs. The attempts to employ various optimisation techniques still produced rewritings of exponential size in the worst case: O((|T | · |q|)|q|) [22, 8, 20, 21]. The alternative two-step combined approach [14, 13]—first expand the data by applying the ontology axioms to the data and introducing (some of) the missing individuals, and only then rewrite the query over the expanded data—resulted in a simple polynomial rewriting only for the fragment of OWL2QL without role inclusions; for the full language, the rewriting remained exponential. Two seemingly contradictory results, presented at DL 2011, added more spice to the quest for short rewritings: [9] showed that one can construct, in polynomial time, a nonrecursive Datalog (NDL) rewriting for some fragments of Datalog± containing OWL2QL, while [11] argued that no FO-rewriting for OWL2QL can be constructed in polynomial time. The aim of this paper is twofold. First, we investigate the worst-case size of FOand NDL-rewritings for CQs over OWL2QL ontologies. We distinguish between ‘pure’ rewritings, which can use the signature of the original query and ontology as well as =, 6= (cf. [7]), and ‘impure’ rewritings, where other means such as new constants are allowed. Here is a summary of the obtained results: