
We propose a novel framework for ontologybased access to temporal log data
using a datalog extension datalogMTL of a Horn fragment of the metric temporal
logic MTL. We show that datalogMTL is ExpSpacecomplete even with punctual
intervals, in which case full MTL is known to be undecidable. We also prove
that nonrecursive datalogMTL is PSpacecomplete for combined complexity and in
AC0 for data complexity. We demonstrate by two realworld use cases that
nonrecursive datalogMTL programs can express complex temporal concepts from
typical user queries and thereby facilitate access to temporal log data. Our
experiments with Siemens turbine data and MesoWest weather data show that
datalogMTL ontologymediated queries are efficient and scale on large datasets.

The question whether an ontology can safely be replaced by another, possibly
simpler, one is fundamental for many ontology engineering and maintenance
tasks. It underpins, for example, ontology versioning, ontology modularization,
forgetting, and knowledge exchange. What safe replacement means depends on the
intended application of the ontology. If, for example, it is used to query
data, then the answers to any relevant ontologymediated query should be the
same over any relevant data set; if, in contrast, the ontology is used for
conceptual reasoning, then the entailed subsumptions between concept
expressions should coincide. This gives rise to different notions of ontology
inseparability such as query inseparability and concept inseparability, which
generalize corresponding notions of conservative extensions. We survey results
on various notions of inseparability in the context of description logic
ontologies, discussing their applications, useful modeltheoretic
characterizations, algorithms for determining whether two ontologies are
inseparable (and, sometimes, for computing the difference between them if they
are not), and the computational complexity of this problem.

We investigate the satisfiability problem for Horn fragments of the
HalpernShoham interval temporal logic depending on the type (box or diamond)
of the interval modal operators, the type of the underlying linear order
(discrete or dense), and the type of semantics for the interval relations
(reflexive or irreflexive). For example, we show that satisfiability of Horn
formulas with diamonds is undecidable for any type of linear orders and
semantics. On the contrary, satisfiability of Horn formulas with boxes is
tractable over both discrete and dense orders under the reflexive semantics and
over dense orders under the irreflexive semantics, but becomes undecidable over
discrete orders under the irreflexive semantics. Satisfiability of binary Horn
formulas with both boxes and diamonds is always undecidable under the
irreflexive semantics.

Our concern is the overhead of answering OWL 2 QL ontologymediated queries
(OMQs) in ontologybased data access compared to evaluating their underlying
treeshaped and bounded treewidth conjunctive queries (CQs). We show that OMQs
with boundeddepth ontologies have nonrecursive datalog (NDL) rewritings that
can be constructed and evaluated in LOGCFL for combined complexity, even in NL
if their CQs are treeshaped with a bounded number of leaves, and so incur no
overhead in complexitytheoretic terms. For OMQs with arbitrary ontologies and
boundedleaf CQs, NDLrewritings are constructed and evaluated in LOGCFL. We
show experimentally feasibility and scalability of our rewritings compared to
previously proposed NDLrewritings. On the negative side, we prove that
answering OMQs with treeshaped CQs is not fixedparameter tractable if the
ontology depth or the number of leaves in the CQs is regarded as the parameter,
and that answering OMQs with a fixed ontology (of infinite depth) is
NPcomplete for treeshaped and LOGCFL for boundedleaf CQs.

We present a new metric temporal logic HornMTL over dense time and its
datalog extension datalogMTL. The use of datalogMTL is demonstrated in the
context of ontologybased data access over meteorological data. We show
decidability of answering ontologymediated queries for a practically relevant
nonrecursive fragment of datalogMTL. Finally, we discuss directions of the
future work, including the potential usecases in analyzing log data of engines
and devices.

We investigate the problem whether two ALC knowledge bases are
indistinguishable by queries over a given vocabulary. We give modeltheoretic
criteria in terms of (partial) homomorphisms and products and prove that this
problem is undecidable for conjunctive queries (CQs) but 2EXPTIMEcomplete for
UCQs (unions of CQs). The same results hold if CQs are replaced by rooted CQs.
We also consider the problem whether two ALC TBoxes give the same answers to
any query in a given vocabulary over all ABoxes, and show that for CQs this
problem is undecidable, too, but becomes decidable and 2EXPTIMEcomplete in
HornALC, and even EXPTIMEcomplete in HornALC when restricted to (unions of)
rooted CQs.

We design temporal description logics suitable for reasoning about temporal
conceptual data models and investigate their computational complexity. Our
formalisms are based on DLLite 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. In the temporal
dimension, they capture future and past temporal operators on concepts,
flexible and rigid roles, the operators `always' and `some time' on roles, data
assertions for particular moments of time and global concept inclusions. The
logics are interpreted over the Cartesian products of object domains and the
flow of time (Z,<), satisfying the constant domain assumption. We prove that
the most expressive of our temporal description logics (which can capture
lifespan cardinalities and either qualitative or quantitative evolution
constraints) turn out to be undecidable. However, by omitting some of the
temporal operators on concepts/roles or by restricting the form of concept
inclusions we obtain logics whose complexity ranges between PSpace and
NLogSpace. These positive results were obtained by reduction to various clausal
fragments of propositional temporal logic, which opens a way to employ
propositional or firstorder temporal provers for reasoning about temporal data
models.

Knowledge base exchange is an important problem in the area of data exchange
and knowledge representation, where one is interested in exchanging information
between a source and a target knowledge base connected through a mapping. In
this paper, we study this fundamental problem for knowledge bases and mappings
expressed in OWL 2 QL, the profile of OWL 2 based on the description logic
DLLite_R. More specifically, we consider the problem of computing universal
solutions, identified as one of the most desirable translations to be
materialized, and the problem of computing UCQrepresentations, which optimally
capture in a target TBox the information that can be extracted from a source
TBox and a mapping by means of unions of conjunctive queries. For the former we
provide a novel automatatheoretic technique, and complexity results that range
from NP to EXPTIME, while for the latter we show NLOGSPACEcompleteness.