Abstract
We study the complexity and rewritability of ontology-mediated queries (OMQs), that is, database queries enriched with semantic information. Our focus is on temporal data, where database facts are timestamped and ontologies are specified in description logics or datalog extended with operators of linear temporal logic.
For queries mediated by such ontologies, we analyse the complexity of evaluation in two scenarios: when both the query and the database are given as input, and when the query is fixed while the database varies. These correspond to the combined and data complexity perspectives in query answering.
Related is the problem of rewritability checking—the task of deciding whether an OMQ can be rewritten into a standard database query, so that query answering with respect to an ontology is “packed” into a finite formula executable by a conventional database engine. In this thesis, we study this problem for ontology languages where rewritability is non-trivial, since it is not always guaranteed.
Our results are both positive and negative. For TEL°¹, a temporal extension of the description logic EL with the operators ○/○⁻ (next/previous time), we prove that OMQ answering is undecidable, but identify two new fragments where it is tractable. The proofs and algorithms rely on a novel correspondence between TEL° ontologies and conjunctive grammars, a generalisation of context-free grammars by the operation of intersection.
To further clarify the expressive power of our ontology languages, we introduce a logic in the temporal DL-Lite family, and show that rewritability into standard languages is undecidable precisely due to the interaction between the temporal and description logic components.
Finally, for temporal datalog, we obtain a complete and decidable classification of linear connected queries with ○/○⁻, from which we derive procedures for checking rewritability into various standard languages. In contrast, we prove that rewritability becomes undecidable when operators ◇/◇⁻ (once in the future/past) are allowed.