Ontology-Mediated Query Answering with Lightweight Temporal Description Logics
MetadataShow full item record
SubjectDL-Lite fragments; LTL operators; Query rewriting; AC0 data complexity; Temporalisation; INF/01
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.
Showing items related by title, author, creator and subject.
Cohen, S; Nutt, W; Sagiv, Y (Association for Computing Machinery (ACM), 2006)The problem of rewriting aggregate queries using views is studied for conjunctive queries with arbitrary aggregation functions and built-in predicates. Two types of queries over views are introduced for rewriting aggregate ...
Darari, F; Prasojo, RE; Nutt, W (Springer, 2014)With the increased availability of data on the Semantic Web, the question whether data sources offer data of appropriate quality for a given purpose becomes an issue. With CORNER, we specifically address the data quality ...
Abiteboul, S; Chan, H; Kharlamov, E; Nutt, W; Senellart, P (ACM, 2010)Sources of data uncertainty and imprecision are numerous. A way to handle this uncertainty is to associate probabilistic annotations to data. Many such probabilistic database models have been proposed, both in the relational ...