Abstract
The main topic of this doctoral dissertation is to extend the ontology-mediated query rewriting paradigm to the case where the ontology, the query and the data are temporally characterised. We follow an approach of the combination of standard DL-Lite fragments with standard (propositional) temporal logics into logics with a two-dimensional semantics, where one dimension is for time and the other for the DL domain. Therefore, the temporal extension we provide is interpreted over sequences of standard DL-Lite interpretations. The ontological axioms are interpreted globally, that is, they are assumed to hold in all points in time, but the extension of both concepts and roles can vary in time. The temporal ontology and the temporal query generalise the classical counterparts by allowing the use of the LTL operators such as ``in the next (previous) moment of time'' and ``always in the future (in the past)''. The temporal data assertions are time-stamped unary (for concepts) and binary (for roles) predicates that hold at the specified moments of time. For temporal ontology-mediated query answering we combine the first-order rewriting techniques for the conventional query answering in logics of the DL-Lite family with a new technique developed to rewrite temporal constraints.
Hence, in the dissertation we provide an algorithm for temporal ontology-mediated query answering which preserves a distinguishing feature of classical DL-Lite: low computational complexity of the reasoning tasks (in the size of the data). These temporal extensions of DL-Lite can perform efficient reasoning in data-oriented applications: some even without loosing the original AC0 efficiency. Additionally, we discover types of temporal ontology-mediated queries of NC1 data complexity: these problems are known to be easy to solve in parallel.
Therefore, our dissertation successfully pave the way for practical algorithms for temporal query answering over ontologies expressed using temporal DL-Lite fragments.