# Temporalising Unique Characterisability and Learnability of Ontology-
Mediated Queries

Jean Christoph Jung
TU Dortmund University, UK
<EMAIL_ADDRESS>
&Vladislav Ryzhikov
Birkbeck, University of London, UK
<EMAIL_ADDRESS>
&Frank Wolter
University of Liverpool, UK
<EMAIL_ADDRESS>
&Michael Zakharyaschev
Birkbeck, University of London, UK
<EMAIL_ADDRESS>
###### Abstract

Recently, the study of the unique characterisability and learnability of
database queries by means of examples has been extended to ontology-mediated
queries. Here, we study in how far the obtained results can be lifted to
temporalised ontology-mediated queries. We provide a systematic introduction
to the relevant approaches in the non-temporal case and then show general
transfer results pinpointing under which conditions existing results can be
lifted to temporalised queries.

##  1 Introduction

Temporal ontology-mediated query answering provides a framework for accessing
temporal data using background knowledge in the form of a logical theory,
often called an ontology. Within this framework, queries are usually
constructed by combining a domain query language such as conjunctive queries
(CQs) with linear temporal logic (LTL) operators. Ontologies range from pure
description logic (DL) ontologies [11, 16], which hold at all timepoints, to
suitable combinations of DLs with LTL [7, 9, 28, 10, 48]. On the query side,
LTL is combined with domain queries formulated usually as conjunctive queries
(CQs). To ensure good semantic and computational properties, one often
restricts the use of LTL operators to monotone operators and the domain
queries to acyclic CQs such as the class ELIQ of CQs that are equivalent to
$\mathcal{ELI}$-queries. On the ontology side, the most popular languages are
based on the DL-Lite family of DLs, which underpins the OWL2 DL profile of the
W3C standard for ontology-based data access [17, 6].

Our aim in this paper is (i) to find out in how far temporal queries can be
(polynomially) characterised using temporal data instances if ontologies
encoding background knowledge are present and (ii) to apply the results to
study the (polynomial) learnability of temporal queries in Angluin’s framework
of exact learning [4]. Investigating the computation, size, and shape of
unique characterisations of queries by data examples contributes to the
_query-by-example_ paradigm in databases [37] as the data examples can be
naturally used to illustrate, explain, and construct queries. Unique
characterisations also provide a ‘non-procedural’ necessary condition for
(polynomial time) exact learnability using membership queries, where
membership queries to the oracle take the form ‘does
$\mathcal{O},\mathcal{D}\models{\bm{q}}_{T}(a)$ hold?’ and thus provide access
to query answers of the target query ${\bm{q}}_{T}$ to be learned. We focus
our investigation on temporal extensions of the class ELIQ with operators
$\bigcirc$ (‘in the next time point’), $\Diamond$ (’at some point in the
future’), and $\mathbin{\mathsf{U}}$ (‘until’).

Recently, significant progress has been made in understanding the unique
characterisability and learnability of non-temporal ELIQs mediated by DL
ontologies [44, 26]. Also, rather general results have been obtained about the
characterisation and learnability of temporal queries, but so far without
ontologies [22]. From a technical viewpoint, in this paper we combine these
two directions to study the temporalisation of unique characterisability and
learnability under DL ontologies.

We next provide an overview of our results. Let $\mathcal{O}$ be an ontology
and $\mathcal{Q}$ a class of conjunctive queries, which we assume for
simplicity to have a single answer variable. We say that a query
${\bm{q}}\in\mathcal{Q}$ _fits_ a pair $E=(E^{+},E^{-})$ of finite sets
$E^{+}$ and $E^{-}$ of pointed data instances $(\mathcal{D},a)$ wrt
$\mathcal{O}$ if $\mathcal{O},\mathcal{D}\models{\bm{q}}(a)$ for all
$(\mathcal{D},a)\in E^{+}$, and
$\mathcal{O},\mathcal{D}\not\models{\bm{q}}(a)$ for all $(\mathcal{D},a)\in
E^{-}$. Then $E$ _uniquely characterises_ ${\bm{q}}$ wrt $\mathcal{O}$ within
$\mathcal{Q}$ if ${\bm{q}}$ is the only (up to equivalence modulo
$\mathcal{O}$) query in $\mathcal{Q}$ that fits $E$ wrt $\mathcal{O}$. An
ontology language $\mathcal{L}$ _admits (polysize) characterisations within
$\mathcal{Q}$_ if every ${\bm{q}}\in\mathcal{Q}$ has a (polysize)
characterisation wrt to any $\mathcal{L}$-ontology within $\mathcal{Q}$.

#### Non-temporal case.

We begin by summarising the relevant results that will be used as a black box
in our investigation of temporalised queries. Let $\mathcal{O}$ be an FO-
ontology (typically in some DL). Given queries ${\bm{q}}_{1}$, ${\bm{q}}_{2}$,
we write ${\bm{q}}_{1}\models_{\mathcal{O}}{\bm{q}}_{2}$ and say that
${\bm{q}}_{1}$ is _contained_ in ${\bm{q}}_{2}$ wrt $\mathcal{O}$ if
$\mathcal{O},\mathcal{D}\models{\bm{q}}_{1}(a)$ implies
$\mathcal{O},\mathcal{D}\models{\bm{q}}_{2}(a)$, for any pointed data instance
$\mathcal{D},a$. We utilise a well-known reduction of containment to query
entailment. An ontology $\mathcal{O}$ _admits containment reduction_ if, for
any CQ ${\bm{q}}(x)$, there is a pointed data instance $(\hat{{\bm{q}}},a)$
such that ${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime}$ iff
$\mathcal{O},\hat{{\bm{q}}}\models{\bm{q}}^{\prime}(a)$, for any CQ
${\bm{q}}^{\prime}(x)$ (we also demand a few minor technical conditions given
in teh paper). An ontology language $\mathcal{L}$ _admits containment
reduction_ if every $\mathcal{L}$-ontology does. It is easy to see that if
$\mathcal{L}$ admits both (polysize) unique characterisations within
$\mathcal{Q}$ and containment reduction, then every ${\bm{q}}\in\mathcal{Q}$
has a (polysize) _singular +characterisation_ $E$ within $\mathcal{Q}$ with
$E^{+}=\\{\hat{{\bm{q}}}\\}$. Containment reduction is a rather general
condition (unfortunately not shared by temporalisations, see below): FO
without equality including DLs such as $\mathcal{ALCHI}$ and $\textsl{DL-
Lite}_{\mathcal{H}}$ [17] (aka $\textsl{DL-
Lite}_{\textit{core}}^{\mathcal{H}}$ [6]) and also some DLs with limited
counting such as $\textsl{DL-Lite}_{\mathcal{F}}$ [17] (aka $\textsl{DL-
Lite}^{\mathcal{F}}_{\textit{core}}$ [6]) admit containment reduction but
$\mathcal{ALCQ}$ does not.

The two main approaches to compute $E^{-}$ and obtain
singular+characterisations for languages with containment reduction are based
on frontiers and splittings (aka dualities) [44]. A _frontier of ${\bm{q}}$
wrt $\mathcal{O}$ within $\mathcal{Q}$_ is any set
$\mathcal{F}_{{\bm{q}}}\subseteq\mathcal{Q}$ such that $(a)$
${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime}$ and
${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}$, for all
${\bm{q}}^{\prime}\in\mathcal{F}_{{\bm{q}}}$; and $(b)$ if
${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$ for
${\bm{q}}^{\prime\prime}\in\mathcal{Q}$, then
${\bm{q}}^{\prime\prime}\models_{\mathcal{O}}{\bm{q}}$ or there is
${\bm{q}}^{\prime}\in\mathcal{F}_{{\bm{q}}}$ with
${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$. An ontology
language $\mathcal{L}$ _admits(polysize) finite frontiers within
$\mathcal{Q}$_ if every ${\bm{q}}\in\mathcal{Q}$ has a (polysize) finite
frontier wrt to any $\mathcal{L}$-ontology within $\mathcal{Q}$. The following
theorem summarises what is currently known about frontiers of ELIQs. While
$(i)$ and $(ii)$ are shown in [26], we show $(iii)$ in this paper.

######  Theorem 1.

$(i)$ $\textsl{DL-Lite}_{\mathcal{H}}$ and the fragment $\textsl{DL-
Lite}_{\mathcal{F}}^{-}$ of $\textsl{DL-Lite}_{\mathcal{F}}$, in which $R^{-}$
is not functional for any $B\sqsubseteq\exists R$, admit polysize frontiers
within ELIQ. $(ii)$ $\textsl{DL-Lite}_{\mathcal{F}}$ does not admit finite
frontiers within ELIQ. $(iii)$ $\mathcal{EL}$ does not admit finite frontiers
within ELIQ.

The frontier of a query supplies the negative examples for a singular+unique
characterisation.

######  Theorem 2.

If $\mathcal{L}$ admits both (polysize) frontiers within $\mathcal{Q}$ and
containment reduction, then $\mathcal{L}$ admits (polysize)
singular+characterisations within $\mathcal{Q}$, with
$E^{-}=\mathcal{F}_{{\bm{q}}}$, for any ${\bm{q}}\in\mathcal{Q}$.

The second path to singular+characterisations is via finite splittings, which
only exist if a finite signature $\sigma$ of predicates is fixed. Let
$\mathcal{Q}$ be a class of queries and $\mathcal{Q}^{\sigma}$ its restriction
to $\sigma$, $Q\subseteq\mathcal{Q}^{\sigma}$ finite, and $\mathcal{O}$ a
$\sigma$-ontology. A set $\mathcal{S}(Q)$ of pointed $\sigma$-data instances
$(\mathcal{A},a)$ is called a _split-partner_ for $Q$ wrt $\mathcal{O}$ within
$\mathcal{Q}^{\sigma}$ if, for all ${\bm{q}}^{\prime}\in\mathcal{Q}^{\sigma}$,
we have $\mathcal{O},\mathcal{A}\models{\bm{q}}^{\prime}(a)$ for some
$(\mathcal{A},a)\in\mathcal{S}(Q)$ iff
${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}$ for all ${\bm{q}}\in Q$.
An ontology language $\mathcal{L}$ _has general split-partners within
$\mathcal{Q}^{\sigma}$_ if all finite sets of $\mathcal{Q}^{\sigma}$-queries
have split partners wrt any $\sigma$-ontology in $\mathcal{L}$. We show the
following results.

######  Theorem 3.

$(i)$ $\mathcal{ALCHI}$ has exponential-size general split-partners within
$\sigma$-ELIQ, $(ii)$ even wrt to the empty ontology, no polysize split-
partners exit within $\sigma$-ELIQ [22].

Thus, $\mathcal{EL}$ has finite general split-partners but no frontiers within
ELIQ, and $\textsl{DL-Lite}^{-}_{\mathcal{F}}$ has finite frontiers but no
finite general split-partners within ELIQ. This is in contrast to the
ontology-free case where frontiers and splittings are more closely linked
[44]. One can now show the following analogue of Theorem 2 for splittings:

######  Theorem 4.

If $\mathcal{L}$ admits (polysize) general split-partners within
$\mathcal{Q}^{\sigma}$ and containment reduction, then $\mathcal{L}$ admits
(polysize) singular+characterisations within $\mathcal{Q}$, with
$E^{-}=\mathcal{S}(\\{{\bm{q}}\\})$, for any
${\bm{q}}\in\mathcal{Q}^{\sigma}$.

#### Temporalisation.

A _temporal data instance_ is a sequence
$\mathcal{A}_{0},\dots,\mathcal{A}_{n}$ of domain data instances
$\mathcal{A}_{i}$ with $i$ regarded as a _timestamp_. To query temporal data,
we equip standard CQs with the operators of linear temporal logic LTL. Within
this framework, various query languages that admit (polysize) unique
characterisations and learnability have been identified in the case when no
background ontology is present [22]. Here, we assume that the temporal data is
mediated by a standard (atemporal) DL ontology whose axioms are supposed to be
true at all times. We consider a few families of temporal queries defined in
[22] that are built from domain queries in a given class $\mathcal{Q}$ (say,
ELIQ or conjunctions of concept names, denoted $\mathcal{P}$) using $\wedge$
and the temporal operators $\bigcirc$ (at the next moment), $\Diamond$ (some
time later), $\Diamond_{\\!r}$ (now or later), and $\mathbin{\mathsf{U}}$
(strict until): the family
$\textsl{LTL}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}_{p}(\mathcal{Q})$
of _path queries_ of the form

${\bm{q}}=\bm{r}_{0}\land{\bm{o}}_{1}(\bm{r}_{1}\land{\bm{o}}_{2}(\bm{r}_{2}\land\dots\land{\bm{o}}_{n}\bm{r}_{n})),$

where
${\bm{o}}_{i}\in\\{{\raisebox{1.07639pt}{\text{$\bigcirc$}}},\Diamond,\Diamond_{\\!r}\\}$
and $\bm{r}_{i}\in\mathcal{Q}$; the family
$\textsl{LTL}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}_{p}(\mathcal{Q}^{\sigma})$
of _path queries_

${\bm{q}}=\bm{r}_{0}\land(\bm{l}_{1}\mathbin{\mathsf{U}}(\bm{r}_{1}\land(\bm{l}_{2}\mathbin{\mathsf{U}}(\dots(\bm{l}_{n}\mathbin{\mathsf{U}}\bm{r}_{n})\dots)))),$

where $\bm{r}_{i}\in\mathcal{Q}^{\sigma}$,
$\bm{l}_{i}\in\mathcal{Q}^{\sigma}\cup\\{\bot\\}$; and its subfamily
$\textsl{LTL}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}_{pp}(\mathcal{Q}^{\sigma})$
of _peerless queries_ in which $\bm{r}_{i}\not\models_{\mathcal{O}}\bm{l}_{i}$
and $\bm{l}_{i}\not\models_{\mathcal{O}}\bm{r}_{i}$. The subfamily
$\textsl{LTL}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}_{p}(\mathcal{Q})$
restricts
$\textsl{LTL}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}_{p}(\mathcal{Q})$
to the operators $\bigcirc$ and $\Diamond$; note that
$\Diamond{\bm{q}}\equiv{\raisebox{1.07639pt}{\text{$\bigcirc$}}}\Diamond_{r}{\bm{q}}$.

Temporal queries have a few essential differences from the domain ones. First,
no example set can distinguish the query $\Diamond_{\\!r}(A\wedge B)$ from
$\Diamond_{\\!r}(A\land(\Diamond_{\\!r}B\land\Diamond_{\\!r}(A\land\dots)))$
with sufficiently many alternating $A$, $B$. A syntactic criterion (excluding
proper conjunctions that do not have a $\bigcirc$-neighbour) of unique
characterisability of queries in
$\textsl{LTL}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}_{p}(\mathcal{P})$,
called _safety_ , was found in [22]. Second, containment reduction does not
work any more since to characterise, say, $\Diamond A$ _two_ positive examples
are needed. By generalising safety in a natural way, we obtain our first
transfer result:

######  Theorem 5.

Let $\mathcal{L}$ admit (polysize) singular+characterisations within
$\mathcal{Q}$ and $\mathcal{O}$ be a $\mathcal{L}$-ontology that admits
containement reduction. Then

$(i)$

${\bm{q}}\in\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
is (polysize) uniquely characterisable wrt $\mathcal{O}$ within
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
iff ${\bm{q}}$ is safe wrt $\mathcal{O}$;

$(ii)$

all
${\bm{q}}\in\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}(\mathcal{Q})$
are (polysize) uniquely characterisable wrt $\mathcal{O}$.

$(iii)$

If $\mathcal{O}$ admits polysize singular+characterisations within
$\mathcal{Q}$, then
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
is polynomially characterisable for bounded temporal depth.

As a consequence of the above results, we obtain, e.g., that every safe query
in
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
is polynomially characterisable wrt any $\textsl{DL-Lite}_{\mathcal{H}}$ or
$\textsl{DL-Lite}^{-}_{\mathcal{F}}$ ontology and exponentially
characterisable wrt any $\mathcal{ALCHI}$-ontology. Our second transfer result
is as follows:

######  Theorem 6.

Let $\mathcal{L}$ have (exponential-size) general split-partners within
$\mathcal{Q}^{\sigma}$ and let $\mathcal{O}$ be a $\sigma$-ontology in
$\mathcal{L}$ that admits containment reduction. Then every
${\bm{q}}\in\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$
is (exponential-size) uniquely characterisable within
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$.

As a consequence, we obtain that every query in
$\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$,
where $\mathcal{Q}^{\sigma}$ is the class of $\sigma$-ELIQs, is exponentially
uniquely characterisable within
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$
wrt any $\mathcal{ALCHI}$ ontology.

#### Learning.

We apply our results on characterisability to learnability of queries in
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
wrt ontologies in Angluin’s framework of exact learning [4]. In the non-
temporal case, exact learning of queries has recently been studied [44, 24,
26, 25]. Given some class $\mathcal{Q}$ of queries and an ontology
$\mathcal{O}$, the _learner_ aims to identify a target query
${\bm{q}}_{T}\in\mathcal{Q}$ using membership queries of the form ‘does
$\mathcal{O},\mathcal{D}\models{\bm{q}}(a)$ hold?’ to the _teacher_. It is
assumed that the target query ${\bm{q}}_{T}$ uses only symbols that occur in
the ontology $\mathcal{O}$. We call $\mathcal{Q}$ polynomial query
(polynomial-time) learnable wrt $\mathcal{L}$-ontologies using membership
queries if there is a learning algorithm that receives an
$\mathcal{L}$-ontology $\mathcal{O}$ and an example $(\mathcal{D},a)$ with
$\mathcal{O},\mathcal{D}\models{\bm{q}}_{T}(a)$ with $\mathcal{D}$ satisfiable
under $\mathcal{O}$, and constructs ${\bm{q}}_{T}$ (up to equivalence wrt
$\mathcal{O}$) using polynomially-many queries of polynomial size (in time
polynomial) in the size of ${\bm{q}}_{T},\mathcal{O},\mathcal{D}$.

As we always construct example sets effectively, our unique (exponential)
characterisability results imply (exponential-time) learnability with
membership queries. Obtaining polynomial-time learnability from polynomial
characterisations is more challenging and, in fact, not always possible. We
concentrate on ontologies formulated in fragments $\mathcal{L}$ of the DL
$\mathcal{ELHIF}$ which are in normal form [12], but conjecture that our
results continue to hold in general. $\mathcal{L}$ _admits polytime instance
checking_ if $\mathcal{O},\mathcal{D}\models A(a)$, for a concept name $A$,
can be decided in polynomial time. _Meet-reducibility_ is in polytime if it
can be checked in polytime whether an ELIQ is equivalent to a proper
conjunction of ELIQs wrt to an $\mathcal{L}$-ontology. The following is shown
by lifting the techniques developed for the non-temporal setting in [25, 26]
to the temporal case:

######  Theorem 7.

Let $\mathcal{L}$ be an ontology language that contains only
$\mathcal{ELHIF}$-ontologies in normal form and that admits polysize frontiers
within ELIQ that can be computed. Then:

$(i)$

The class of safe queries in
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
is polynomial query learnable wrt $\mathcal{L}$-ontologies using membership
queries.

$(ii)$

The class
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
is polynomial query learnable wrt $\mathcal{L}$-ontologies using membership
queries if the learner knows the temporal depth of the target query in
advance.

$(iii)$

$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}(\text{ELIQ})$
is polynomial query learnable wrt $\mathcal{L}$-ontologies using membership
queries.

If $\mathcal{L}$ further admits polynomial-time instance checking and
polynomial-time computable frontiers within ELIQ, then in $(ii)$ and $(iii)$,
polynomial query learnability can be replaced by polynomial-time learnability.
If, in addition, meet-reducibility wrt $\mathcal{L}$-ontologies is in
polynomial time, then also in $(i)$ polynomial query learnability can be
replaced by polynomial-time learnability.

Theorem 7 fully applies to $\textsl{DL-Lite}_{\mathcal{F}}^{-}$ as it enjoys
all properties mentioned, while $\textsl{DL-Lite}_{\mathcal{H}}$ enjoys all
properties mentioned except that meet-reducibility can be checked in poly-
time. Most importantly, $\textsl{DL-Lite}_{\mathcal{F}}^{-}$ and $\textsl{DL-
Lite}_{\mathcal{H}}$ admit polynomial time computable frontiers [26].

##  2 Related Work

Recently, the unique characterisation framework for temporal formulas
introduced in [22] and underpinning this article has been generalised to allow
for finitely representable transfinite words as examples in characterising
sets [41]. The results are not directly applicable to the problems we are
concerned with as the queries have no DL component and no ontology is present.
We conjecture, however, that it is possible to extend the techniques used in
[41] to the more general languages considered here.

Our work is closely related to work on exact learnability of finite automata
and temporal logic formulas. In fact, the seminal paper by Angluin [3] has
given rise to a large body of work on exact learning of (variations of) finite
automata, for example, [42, 1, 19, 30]. This work has mainly focused on
learning using a combination of membership queries with other powerful types
of queries such as equivalence queries. The use of two or more types of
queries is motivated by the fact that otherwise one cannot efficiently learn
the respective automata models. The main difference between this article and
work on automata learning is that we focus on queries for which the
corresponding formal languages form only a small subset of the regular
languages and this restriction enables us to focus on characterisability and
learnability with membership queries.

There has hardly been any work directly concerned with exact learning of
temporal formulas [18]. In contrast, passive learning of LTL-formulas has
recently received significant attention; see [36, 39, 18, 21, 23].

In the database and KR communities, there has been extensive work on
identifying queries and concept descriptions from data examples [43, 34, 45,
40, 44]. For instance, in reverse engineering of queries, the goal is
typically to decide whether there is a query that fits (or separates) a set of
positive and negative examples. Relevant work under the closed world
assumption include [5, 13] and under the open world assumption [35, 29, 27,
31].

The use of unique characterisations to explain and construct schema mappings
has been promoted and investigated by Kolaitis [33] and Alexe et al. [2].

Unique characterisability of modal logic formulas has recently been studied in
[46]. In contrast to our work, this is done under the closed world assumption
and without ontologies.

##  3 Preliminaries

We begin by introducing ‘two-dimensional’ query languages that combine
instance queries over the object domain in the standard description logics
$\mathcal{EL}$ and $\mathcal{ELI}$ [12] or more general conjunctive queries
with temporal LTL-queries over the temporal domain [8]. Background knowledge
over the object domain is assumed to be given by a standard one-dimensional
description logic ontology whose axioms are supposed to be true at all times.

###  3.1 Ontologies and Queries over the Object Domain

By a _relational signature_ we mean in this paper any non-empty finite set,
$\sigma$, of unary and binary predicate symbols, typically denoted $A,B$ and
$P,R$, respectively. A $\sigma$-_data instance_ , $\mathcal{A}$, is any non-
empty finite set of _atoms_ of the form $A(a)$ and $P(a,b)$ with
$A,P\in\sigma$ and _individual names_ (or _constants_) $a,b$, and also
$\top(a)$, which simply says that the domain contains the individual $a$. We
denote by $\textit{ind}(\mathcal{A})$ the set of individual names in
$\mathcal{A}$ and by $P^{-}$ the _inverse_ of $P$ (with $P^{--}=P$), assuming
that $P^{-}(a,b)\in\mathcal{A}$ iff $P(b,a)\in\mathcal{A}$. We assume that $S$
ranges over binary predicates and their inverses. A _pointed data instance_ is
a pair $(\mathcal{A},a)$ with $a\in\textit{ind}(\mathcal{A})$.

In general, an _ontology_ , $\mathcal{O}$, is a finite set of first-order (FO)
sentences over the given signature $\sigma$. Ontologies and data instances are
interpreted in structures
$\mathcal{I}=(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}})$ with domain
$\Delta^{\mathcal{I}}\neq\emptyset$,
$A^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}$ for unary $A$,
$P^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$ for
binary $P$, and $a^{\mathcal{I}}\in\Delta^{\mathcal{I}}$ for individual names
$a$. As usual in database theory, we assume that
$a^{\mathcal{I}}\not=b^{\mathcal{I}}$ for distinct $a,b$; moreover, to
simplify notation, we adopt the _standard name assumption_ and interpret each
individual name by itself, i.e., take $a^{\mathcal{I}}=a$. Thus, $\mathcal{I}$
is a _model_ of a data instance $\mathcal{A}$ if $a\in A^{\mathcal{I}}$ and
$(a,b)\in P^{\mathcal{I}}$, for all $A(a)\in\mathcal{A}$ and
$P(a,b)\in\mathcal{A}$ (remember that
$\top^{\mathcal{I}}=\Delta^{\mathcal{I}}$). $\mathcal{I}$ is a _model_ of an
ontology $\mathcal{O}$ if all sentences in $\mathcal{O}$ are true in
$\mathcal{I}$. $\mathcal{O}$ and $\mathcal{A}$ are _satisfiable_ if they have
a model.

The concrete ontology languages we deal with in this paper are certain members
of the DL-Lite family, $\mathcal{ALCHI}$, $\mathcal{ELHIF}$, and some
fragments thereof. For the reader’s convenience, we define these languages
below (in FO-terms):

$\textsl{DL-Lite}_{\mathcal{F}}$

[17] (aka $\textsl{DL-Lite}^{\mathcal{F}}_{\textit{core}}$ [6]) allows axioms
of the following forms:

$\forall x\,(B(x)\to B^{\prime}(x)),\quad\forall x\,(B(x)\land
B^{\prime}(x)\to\bot),\quad\forall x,y,z\,(S(x,y)\land S(x,z)\to(y=z)),$ (1)

where _basic concepts_ $B(x)$ are either $A(x)$ or $\exists y\,S(x,y)$. In the
DL parlance, the first two axioms in (1) are written as $B\sqsubseteq
B^{\prime}$ and $B\sqcap B^{\prime}\sqsubseteq\bot$ and called a _concept
inclusion_ (CI) and _concept disjointness constraint_ , respectively. The
third axiom, written $\geq 2\,S\sqsubseteq\bot$ or $\text{fun}(S)$ in DL,
states that relation $S^{-}$ is _functional_ , and so is called a
_functionality constraint_.

$\textsl{DL-Lite}_{\mathcal{F}}^{-}$

[26] is a fragment of $\textsl{DL-Lite}_{\mathcal{F}}$, in which CIs
$B\sqsubseteq B^{\prime}$ cannot have $B^{\prime}=\exists S$ with functional
$S^{-}$.

$\textsl{DL-Lite}_{\mathcal{H}}$

[17] (aka $\textsl{DL-Lite}_{\textit{core}}^{\mathcal{H}}$ [6]) is obtained
from $\textsl{DL-Lite}_{\mathcal{F}}$ by disallowing the functionality
constraint in (1) and adding axioms of the form

$\forall x,y\,(S(x,y)\to S^{\prime}(x,y))$ (2)

known as _role inclusions_ and often written as $S\sqsubseteq S^{\prime}$.

$\mathcal{ALCHI}$

[12] has the same role inclusions as in (2) but more expressive concept
inclusions $\forall x\,(C_{1}(x)\to C_{2}(x))$, in which the _concepts_
$C_{i}$ are defined inductively starting from atoms $\top(x)$ (which is always
true) and $A(x)$ and using the constructors $C(x)\land C^{\prime}(x)$, $\neg
C(x)$, and $\exists y\,(S(x,y)\land C(y))$, for a fresh $y$—or $C\sqcap
C^{\prime}$, $\neg C$, and $\exists S.C$ in DL terms.

$\mathcal{ELHIF}^{\bot}$

[12] has role inclusions (2), functionality constrains, and concept
inclusions with concepts built from atoms and $\bot$ using $\land$ and
$\exists y\,(S(x,y)\land C(y))$ only. $\mathcal{ELFI}^{\bot}$ is the fragment
of $\mathcal{ELHIF}^{\bot}$ without role inclusions.

We reserve the character $\mathcal{L}$ to denote an ontology language.

The most general query language over the object domain we consider in this
paper consists of _conjunctive queries_ (CQs) ${\bm{q}}(x)$ over the given
signature $\sigma$ with a single _answer variable_ $x$. We usually think of
${\bm{q}}(x)$ as the set of its atoms and denote by $\textit{var}({\bm{q}})$
the set of individual variables in ${\bm{q}}$. We say that ${\bm{q}}(x)$ is
_satisfiable_ wrt an ontology $\mathcal{O}$ if the set
$\mathcal{O}\cup\\{{\bm{q}}(x)\\}$ has a model. The set of predicate symbols
in ${\bm{q}}$ is denoted by $\textit{sig}({\bm{q}})$. The restriction of
${\bm{q}}(x)$ to a set $V$ of variables is the CQ that is obtained from
${\bm{q}}(x)$ by omitting the atoms with a variable not in $V$.

Given a CQ ${\bm{q}}(x)$, an ontology $\mathcal{O}$, and a data instance
$\mathcal{A}$, we say that $a\in\textit{ind}(\mathcal{A})$ is a (_certain_)
_answer to ${\bm{q}}$ over $\mathcal{A}$ wrt $\mathcal{O}$_ and write
$\mathcal{O},\mathcal{A}\models{\bm{q}}(a)$ if $\mathcal{I}\models{\bm{q}}(a)$
for all models $\mathcal{I}$ of $\mathcal{O}$ and $\mathcal{A}$. Recall that
$\emptyset,\mathcal{A}\models{\bm{q}}(a)$ iff there is function
$h\colon\textit{var}({\bm{q}})\to\mathcal{A}$ such that $h(x)=a$,
$A(y)\in{\bm{q}}$ implies $A(h(y))\in\mathcal{A}$, and $P(y,z)\in{\bm{q}}$
implies $P(h(y),h(z))\in\mathcal{A}$. Such a function $h$ is called a
_homomorphism_ from ${\bm{q}}$ to $\mathcal{A}$, written
$h\colon{\bm{q}}\to\mathcal{A}$; $h$ is _surjective_ if
$h(\textit{var}({\bm{q}}))=\textit{ind}(\mathcal{A})$.

We say that a CQ ${\bm{q}}_{1}(x)$ is _contained_ in a CQ ${\bm{q}}_{2}(x)$
wrt an ontology $\mathcal{O}$ and write
${\bm{q}}_{1}\models_{\mathcal{O}}{\bm{q}}_{2}$ if
$\mathcal{O},\mathcal{A}\models{\bm{q}}_{1}(a)$ implies
$\mathcal{O},\mathcal{A}\models{\bm{q}}_{2}(a)$, for any data instance
$\mathcal{A}$ and any $a\in\textit{ind}(\mathcal{A})$. If
${\bm{q}}_{1}\models_{\mathcal{O}}{\bm{q}}_{2}$ and
${\bm{q}}_{2}\models_{\mathcal{O}}{\bm{q}}_{1}$, we say that ${\bm{q}}_{1}$
and ${\bm{q}}_{2}$ are _equivalent wrt $\mathcal{O}$_, writing
${\bm{q}}_{1}\equiv_{\mathcal{O}}{\bm{q}}_{2}$. For $\mathcal{O}=\emptyset$,
we often write ${\bm{q}}_{1}\equiv{\bm{q}}_{2}$ instead of
${\bm{q}}_{1}\equiv_{\emptyset}{\bm{q}}_{2}$. We call ${\bm{q}}_{1}$ and
${\bm{q}}_{2}$ _compatible wrt $\mathcal{O}$_ if
${\bm{q}}_{1}\wedge{\bm{q}}_{2}$ is satisfiable wrt $\mathcal{O}$.

Two smaller query languages we need are $\mathcal{ELI}$-_queries_ (or ELIQs,
for short) that can be defined by the grammar

${\bm{q}}\quad:=\quad\top\quad\mid\quad A\quad\mid\quad\exists
S.{\bm{q}}\quad\mid\quad{\bm{q}}\land{\bm{q}}^{\prime}$

and $\mathcal{EL}$-_queries_ (or ELQs), which are ELIQs without inverses
$P^{-}$. Semantically, ${\bm{q}}$ has the same meaning as the _tree-shaped CQ_
${\bm{q}}(x)$ that is defined inductively starting from atoms $\top(x)$ and
$A(x)$ and using the constructors $\exists y\,(S(x,y)\land{\bm{q}}(y))$, for a
fresh $y$, and ${\bm{q}}(x)\land{\bm{q}}^{\prime}(x)$. The only free (i.e.,
answer) variable in ${\bm{q}}$ is $x$. We reserve the character $\mathcal{Q}$
for denoting a class of queries with answer variable $x$ such that whenever
${\bm{q}}_{1},{\bm{q}}_{2}\in\mathcal{Q}$, then
${\bm{q}}_{1}\land{\bm{q}}_{2}\in\mathcal{Q}$; by $\mathcal{Q}^{\sigma}$ we
denote the class of those queries in $\mathcal{Q}$ that are built from
predicates in $\sigma$. The classes of all $\sigma$-ELIQs and $\sigma$-ELQs
are denoted by ELIQσ and ELQσ, respectively.

It will be convenient to include the ‘inconsistency query’ $\bot(x)$ into all
of our query classes. By definition, we have
$\mathcal{O},\mathcal{A}\models\bot(a)$ iff $\mathcal{O}$ and $\mathcal{A}$
are inconsistent.

We say that an ontology $\mathcal{O}$ _admits containment reduction_ if, for
any CQ ${\bm{q}}(x)$, there is a pointed data instance $(\hat{{\bm{q}}},a)$
such that the following conditions hold:

(cr1)

${\bm{q}}(x)$ is satisfiable wrt $\mathcal{O}$ iff $\mathcal{O}$ and
$\hat{{\bm{q}}}$ are satisfiable;

(cr2)

there is a surjective homomorphism $h\colon{\bm{q}}\to\hat{{\bm{q}}}$ with
$h(x)=a$;

(cr3)

if ${\bm{q}}(x)$ is satisfiable wrt $\mathcal{O}$, then for every CQ
${\bm{q}}^{\prime}(x)$, we have
${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime}$ iff
$\mathcal{O},\hat{{\bm{q}}}\models{\bm{q}}^{\prime}(a)$.

An ontology language $\mathcal{L}$ is said to _admit containment reduction_ if
every $\mathcal{L}$-ontology does. If $(\hat{{\bm{q}}},a)$ is computable in
polynomial time for every $\mathcal{O}$ in $\mathcal{L}$, we say that
$\mathcal{L}$ _admits tractable containment reduction_. In the next theorem,
we illustrate this definition by a few examples.

######  Lemma 1.

$(1)$ FO without equality admits tractable containment reduction; in
particular, both $\textsl{DL-Lite}_{\mathcal{H}}$ and $\mathcal{ALCHI}$ admits
tractable containment reduction.

$(2)$ $\textsl{DL-Lite}_{\mathcal{F}}$ admits tractable containment reduction.

$(3)$ The ontology $\mathcal{O}$ with the single axiom

$\forall
x,y_{1},y_{2},y_{3}\,\big{(}\bigwedge_{i=1,2,3}P(x,y_{i})\to\bigvee_{i\neq
j}(y_{i}=y_{j})\big{)}$

(or $\mathcal{O}=\\{\geq 3\,P\sqsubseteq\bot\\}$ in the DL parlance) does not
admit containment reduction.

###### Proof.

(1) We use the following fact [15, Proposition 5.9]: for any FO-ontology
$\mathcal{O}$ without =, any CQ ${\bm{q}}$, and any pointed data instances
$\mathcal{A}_{1},a_{1}$ and $\mathcal{A}_{2},a_{2}$, if there is a
homomorphism $h\colon\mathcal{A}_{1}\to\mathcal{A}_{2}$ with $h(a_{1})=a_{2}$,
then $\mathcal{O},\mathcal{A}_{1}\models{\bm{q}}(a_{1})$ implies
$\mathcal{O},\mathcal{A}_{2}\models{\bm{q}}(a_{2})$.

Let $(\hat{{\bm{q}}}(x),a)$ be _induced_ by ${\bm{q}}(x)$, that is, obtained
from ${\bm{q}}$ by replacing its variables by distinct constants, with $x$
replaced by $a$. Suppose $\mathcal{O},\hat{{\bm{q}}}\models{\bm{q}}^{\prime}$
and $\mathcal{O},\mathcal{A}\models{\bm{q}}(a)$ but
$\mathcal{O},\mathcal{A}\not\models{\bm{q}}^{\prime}(a)$. Take a model
$\mathcal{I}$ witnessing $\mathcal{O},\mathcal{A}\not\models{\bm{q}}_{2}(a)$.
Then $\mathcal{I}\models{\bm{q}}_{1}(a)$ and this is witnessed by a
homomorphism $h:{\bm{q}}_{1}\rightarrow\mathcal{I}$. Take the image
$h({\bm{q}}_{1})$. Then
$\mathcal{O},\widehat{h({\bm{q}}_{1})}\not\models{\bm{q}}_{2}(x)$ is witnessed
by $\mathcal{I}$, and so
$\mathcal{O},\hat{{\bm{q}}}_{1}\not\models{\bm{q}}_{2}(x)$, which is a
contradiction.

(2) Let $\mathcal{O}$ be a $\textsl{DL-Lite}_{\mathcal{F}}$ ontology. Given a
CQ ${\bm{q}}(x)$, define an equivalence relation $\sim$ on
$\textit{var}({\bm{q}})$ as the transitive closure of the following relation:
$y\sim^{\prime}z$ iff there is $u\in\textit{var}({\bm{q}})$ such that
$S(u,y),S(u,z)\in{\bm{q}}$, for a functional $S$ in $\mathcal{O}$. Let
${\bm{q}}/_{\sim}$ be obtained by identifying (glueing together) all of the
variables in each equivalence class $y/_{\sim}$. Clearly,
${\bm{q}}/_{\sim}(x/_{\sim})$ is a homomorphic image of ${\bm{q}}(x)$ and
${\bm{q}}(x)\equiv_{\mathcal{O}}{\bm{q}}/_{\sim}(x/_{\sim})$. We define
$(\hat{{\bm{q}}},a)$ as the pointed data instance induced by
${\bm{q}}/_{\sim}(x/_{\sim})$. Conditions (cr1) and (cr2) are obvious, and
(cr3) follows from the fact that
${\bm{q}}/_{\sim}\models_{\mathcal{O}}{\bm{q}}^{\prime}/_{\sim}$ iff
${\bm{q}}/_{\sim}\models_{\mathcal{O}^{\prime}}{\bm{q}}^{\prime}/_{\sim}$,
where $\mathcal{O}^{\prime}$ is obtained from $\mathcal{O}$ by omitting all of
its functionality constraints, which is in the scope of part (1).

(3) Consider the CQ ${\bm{q}}(x)=\\{P(x,y_{i}),A_{i}(y_{i})\mid i=1,2,3\\}$
and suppose there is a suitable pointed data instance $(\hat{{\bm{q}}},a)$. As
$\mathcal{O}$ and the data instance induced by ${\bm{q}}$ are not satisfiable
and in view of (cr2), $\hat{{\bm{q}}}$ contains at most three individuals,
say, $\hat{{\bm{q}}}=\\{P(a,b),A_{1}(b),A_{2}(b),P(a,c),A_{3}(c)\\}$. But
then, by (cr3),
${\bm{q}}^{\prime}(x)=\\{P(x,y),A_{1}(y),A_{2}(y),P(x,z),A_{3}(z)\\}$ should
satisfy ${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime}$, which not the case
as witnessed by $\mathcal{A}=\\{P(a,b),A_{1}(b),P(a,c),A_{2}(c),A_{3}(c)\\}$
because $\mathcal{O},\mathcal{A}\models{\bm{q}}(a)$ but
$\mathcal{O},\mathcal{A}\not\models{\bm{q}}^{\prime}(a)$. ∎

In what follows, we only consider ontology languages that admit containment
reduction and assume that $(\hat{{\bm{q}}},a)$ is a pointed data instance
satisfying (cr1)–(cr3) for given ${\bm{q}}$ and $\mathcal{O}$.

An _example set_ is a pair $E=(E^{+},E^{-})$, where $E^{+}$ and $E^{-}$ are
finite sets of pointed data instances $(\mathcal{D},a)$. A CQ ${\bm{q}}(x)$
_fits_ $E$ wrt $\mathcal{O}$ if
$\mathcal{O},\mathcal{D}^{+}\models{\bm{q}}(a^{+})$ and
$\mathcal{O},\mathcal{D}^{-}\not\models{\bm{q}}(a^{-})$, for all
$(\mathcal{D}^{+},a^{+})\in E^{+}$ and $(\mathcal{D}^{-},a^{-})\in E^{-}$. We
say that $E$ _uniquely characterises ${\bm{q}}$ wrt $\mathcal{O}$ within a
given class $\mathcal{Q}$ of queries_ if ${\bm{q}}$ fits $E$ and
${\bm{q}}\equiv_{\mathcal{O}}{\bm{q}}^{\prime}$, for any
${\bm{q}}^{\prime}\in\mathcal{Q}$ fitting $E$. Note that if $E^{+}=\emptyset$,
then ${\bm{q}}\equiv_{\mathcal{O}}\bot$, and so ${\bm{q}}$ is not satisfiable
wrt $\mathcal{O}$. We call a unique characterisation $E=(E^{+},E^{-})$ of
${\bm{q}}$ wrt $\mathcal{O}$ _singular +_ if $E^{+}=\\{(\hat{{\bm{q}}},a)\\}$.

######  Lemma 2.

Suppose $\mathcal{O}$ admits containment reduction, ${\bm{q}}\in\mathcal{Q}$
is satisfiable wrt $\mathcal{O}$ and has a unique characterisation
$E=(E^{+},E^{-})$ wrt $\mathcal{O}$ within $\mathcal{Q}$. Then
$E^{\prime}=((\\{\hat{{\bm{q}}},a)\\},E^{-})$ is a unique characterisation of
${\bm{q}}$ wrt $\mathcal{O}$ within $\mathcal{Q}$, too. Thus, every uniquely
characterisable ${\bm{q}}\in\mathcal{Q}$ within $\mathcal{Q}$ wrt an ontology
admitting containment reduction has a singular+characterisation.

###### Proof.

To show that $E^{\prime}$ is as required, we first observe that ${\bm{q}}$
fits $E^{\prime}$ by (cr1) and (cr3). Suppose
${\bm{q}}^{\prime}\not\equiv_{\mathcal{O}}{\bm{q}}$ for some
${\bm{q}}^{\prime}\in\mathcal{Q}$. We show that then either
$\mathcal{O},\hat{{\bm{q}}}\not\models{\bm{q}}^{\prime}$ or
$\mathcal{O},\mathcal{D}\models{\bm{q}}^{\prime}$ for some $\mathcal{D}\in
E^{-}$. Let ${\bm{q}}\not\models_{\mathcal{O}}{\bm{q}}^{\prime}$. Then
$\mathcal{O},\hat{{\bm{q}}}\not\models{\bm{q}}^{\prime}$ by (cr3). Let
${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime}$ and
${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}$. Then
$\mathcal{O},\mathcal{D}\models{\bm{q}}^{\prime}$ for all $\mathcal{D}\in
E^{+}$, and so $\mathcal{O},\mathcal{D}\models{\bm{q}}^{\prime}$, for some
$\mathcal{D}\in E^{-}$, because $E$ is a unique characterisation of ${\bm{q}}$
wrt $\mathcal{O}$. ∎

We now give two sufficient conditions of singular+characterisability: the
existence of frontiers and the existence of split-partners.

Let $\mathcal{O}$ be an ontology, $\mathcal{Q}$ a class of queries, and
${\bm{q}}\in\mathcal{Q}$ a satisfiable query wrt $\mathcal{O}$. A _frontier of
${\bm{q}}$ wrt $\mathcal{O}$ within $\mathcal{Q}$_ is any set
$\mathcal{F}_{{\bm{q}}}\subseteq\mathcal{Q}$ such that

  * •

${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime}$ and
${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}$, for all
${\bm{q}}^{\prime}\in\mathcal{F}_{{\bm{q}}}$;

  * •

if ${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$ for a
${\bm{q}}^{\prime\prime}\in\mathcal{Q}$, then
${\bm{q}}^{\prime\prime}\models_{\mathcal{O}}{\bm{q}}$ or there is
${\bm{q}}^{\prime}\in\mathcal{F}_{{\bm{q}}}$ with
${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$.

(Note that if ${\bm{q}}\equiv_{\mathcal{O}}\top$, then
$\mathcal{F}_{{\bm{q}}}=\emptyset$.) An ontology $\mathcal{O}$ is said to
_admit_ (_finite_) _frontiers within $\mathcal{Q}$_ if every
${\bm{q}}\in\mathcal{Q}$ satisfiable wrt $\mathcal{O}$ has a (finite) frontier
wrt $\mathcal{O}$ within $\mathcal{Q}$. Further, if such frontiers can be
computed in polynomial time, we say that $\mathcal{O}$ _admits polynomial-time
computable frontiers._

######  Theorem 8.

Suppose $\mathcal{Q}$ is a class of queries, an ontology $\mathcal{O}$ admits
containment reduction, ${\bm{q}}\in\mathcal{Q}$ is satisfiable wrt
$\mathcal{O}$, and $\mathcal{F}_{{\bm{q}}}$ is a finite frontier of ${\bm{q}}$
wrt $\mathcal{O}$ within $\mathcal{Q}$. Then
$(\\{(\hat{{\bm{q}}},a)\\},\\{(\hat{\bm{r}},a)\mid\bm{r}\in\mathcal{F}_{{\bm{q}}}\\})$
is a singular+characterisation of ${\bm{q}}$ wrt $\mathcal{O}$ within
$\mathcal{Q}$.

###### Proof.

By (cr2), $\mathcal{O},\hat{{\bm{q}}}\models{\bm{q}}(a)$. To show
$\mathcal{O},\hat{\bm{r}}\not\models{\bm{q}}(a)$ for all
$\bm{r}\in\mathcal{F}_{{\bm{q}}}$, we observe that
$\bm{r}\not\models_{\mathcal{O}}{\bm{q}}$ by the definition of
$\mathcal{F}_{{\bm{q}}}$, so $\bm{r}(x)$ is consistent with $\mathcal{O}$ and
by (cr3) for $\bm{r}$, from which
$\mathcal{O},\hat{\bm{r}}\not\models{\bm{q}}(a)$. Thus, ${\bm{q}}$ fits $E$.

Suppose ${\bm{q}}^{\prime}\in\mathcal{Q}$ and
${\bm{q}}\not\equiv_{\mathcal{O}}{\bm{q}}^{\prime}$. We show that either
$\mathcal{O},\hat{{\bm{q}}}\not\models{\bm{q}}^{\prime}$ or
$\mathcal{O},\hat{\bm{r}}\models{\bm{q}}^{\prime}$ for some
$\bm{r}\in\mathcal{F}_{{\bm{q}}}$. If
${\bm{q}}\not\models_{\mathcal{O}}{\bm{q}}^{\prime}$, then, since
$\mathcal{O}$ admits containment reduction and ${\bm{q}}(x)$ is satisfiable
wrt $\mathcal{O}$, we obtain
$\mathcal{O},\hat{{\bm{q}}}\not\models{\bm{q}}^{\prime}$ by (cr3). So suppose
${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime}$ and
${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}$. As
$\mathcal{F}_{{\bm{q}}}$ is a frontier of ${\bm{q}}$ wrt $\mathcal{O}$, there
is $\bm{r}\in\mathcal{F}_{{\bm{q}}}$ with
$\bm{r}\models_{\mathcal{O}}{\bm{q}}^{\prime}$. If $\bm{r}(x)$ is
unsatisfiable wrt $\mathcal{O}$, then $\mathcal{O}$ and $\hat{\bm{r}}$ are
unsatisfiable by (cr1), and so
$\mathcal{O},\hat{\bm{r}}\models{\bm{q}}^{\prime}$. And if $\bm{r}(x)$ is
satisfiable wrt $\mathcal{O}$, we obtain
$\mathcal{O},\hat{\bm{r}}\models{\bm{q}}^{\prime}(a)$ by (cr3). ∎

The two main ontology languages that admit polynomial-time computable
frontiers within ELIQ are $\textsl{DL-Lite}_{\mathcal{H}}$ and $\textsl{DL-
Lite}_{\mathcal{F}}^{-}$, whereas $\textsl{DL-Lite}_{\mathcal{F}}$ itself does
not admit finite ELIQ-frontiers [26]. By Theorem 8 and Lemma 1, we then
obtain:

######  Theorem 9 ([26]).

If an ELIQ ${\bm{q}}$ is satisfiable wrt a $\textsl{DL-Lite}_{\mathcal{H}}$ or
$\textsl{DL-Lite}_{\mathcal{F}}^{-}$ ontology $\mathcal{O}$, then ${\bm{q}}$
has a polysize singular+characterisation wrt $\mathcal{O}$ within ELIQ.

We also require the following observation on singleton frontiers. A query
$\bm{r}\in\mathcal{Q}$ is called _meet-reducible_ [38] (or _conjunct_) wrt
$\mathcal{O}$ within $\mathcal{Q}$ if there are
$\bm{r}_{1},\bm{r}_{2}\in\mathcal{Q}$ such that

$\bm{r}\equiv_{\mathcal{O}}\bm{r}_{1}\land\bm{r}_{2}\quad\text{and}\quad\bm{r}\not\equiv_{\mathcal{O}}\bm{r}_{i},\
\text{ for $i=1,2$}.$

######  Lemma 3.

$(i)$ If an ontology $\mathcal{O}$ admits frontiers within $\mathcal{Q}$, then
${\bm{q}}\in\mathcal{Q}$ is meet-reducible wrt $\mathcal{O}$ within
$\mathcal{Q}$ iff $|\mathcal{F}_{{\bm{q}}}|\geq 2$ provided that, for any
distinct ${\bm{q}}^{\prime},{\bm{q}}^{\prime\prime}\in\mathcal{F}_{{\bm{q}}}$,
we have ${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$.

$(ii)$ If an ontology $\mathcal{O}$ admits singular+characterisations within
$\mathcal{Q}$, then, for any meet-reducible ${\bm{q}}\in\mathcal{Q}$ wrt
$\mathcal{O}$ within $\mathcal{Q}$, we have $|\mathcal{N}_{{\bm{q}}}|\geq 2$
in every singular+ characterisation
$(\\{\hat{{\bm{q}}}\\},\mathcal{N}_{{\bm{q}}})$ of ${\bm{q}}$ wrt
$\mathcal{O}$ within $\mathcal{Q}$.

###### Proof.

$(i,\,\Leftarrow)$ Let $\bm{r}_{1},\bm{r}_{2}\in\mathcal{F}_{{\bm{q}}}$ be
distinct. Consider $\bm{r}=\bm{r}_{1}\land\bm{r}_{2}$. If
${\bm{q}}\not\equiv_{\mathcal{O}}\bm{r}$, then there is
$\bm{r}^{\prime}\in\mathcal{F}_{{\bm{q}}}$ with
$\bm{r}^{\prime}\models_{\mathcal{O}}\bm{r}$, and so
$\bm{r}^{\prime}\models_{\mathcal{O}}\bm{r}_{i}$, which is impossible.

$(i,\,\Rightarrow)$ Suppose
${\bm{q}}\equiv_{\mathcal{O}}{\bm{q}}_{1}\land{\bm{q}}_{2}$ and
${\bm{q}}\not\equiv_{\mathcal{O}}{\bm{q}}_{i}$, for $i=1,2$. Then there are
$\bm{r}_{i}\in\mathcal{F}_{{\bm{q}}}$ with
$\bm{r}_{i}\not\equiv_{\mathcal{O}}{\bm{q}}_{i}$. Clearly, $\bm{r}_{1}$ and
$\bm{r}_{2}$ are distinct because otherwise
$\bm{r}_{i}\models_{\mathcal{O}}{\bm{q}}$.

$(ii)$ Suppose ${\bm{q}}\equiv_{\mathcal{O}}{\bm{q}}_{1}\land{\bm{q}}_{2}$ and
${\bm{q}}\not\equiv_{\mathcal{O}}{\bm{q}}_{i}$, for $i=1,2$. If
$\mathcal{N}_{{\bm{q}}}=\\{\hat{\bm{r}}\\}$, then
$\mathcal{O},\hat{\bm{r}}\models{\bm{q}}_{i}$, for $i=1,2$, because if
$\mathcal{O},\hat{\bm{r}}\not\models{\bm{q}}_{i}$, then ${\bm{q}}_{i}$ would
fit $(\\{\hat{{\bm{q}}}\\},\mathcal{N}_{{\bm{q}}})$, and so equivalent to
${\bm{q}}$ wrt $\mathcal{O}$, which is impossible. ∎

######  Lemma 4.

$(i)$ Deciding whether an ELIQ ${\bm{q}}$ is meet-reducible wrt to a
$\textsl{DL-Lite}_{\mathcal{F}}^{-}$-ontology can be done in polynomial time.

$(ii)$ Deciding whether an ELIQ ${\bm{q}}$ is meet-reducible wrt to a
$\textsl{DL-Lite}_{\mathcal{H}}$-ontology is NP-complete.

###### Proof.

$(i)$ We first compute a frontier $\mathcal{F}_{{\bm{q}}}$ of ${\bm{q}}$ in
polynomial time [26]. Then we remove from $\mathcal{F}_{{\bm{q}}}$ every
${\bm{q}}^{\prime\prime}$ for which there is a different
${\bm{q}}^{\prime}\in\mathcal{F}_{{\bm{q}}}$ with
${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$. This can also
be done in polynomial time because query containment in $\textsl{DL-
Lite}_{\mathcal{F}}$ is tractable. It remains to use Lemma 3 $(i)$ to check if
the resulting set is a singleton.

$(ii)$ Consider the ontologies $\mathcal{O}$, ABox $\\{A_{0}(a)\\}$, and
$\mathcal{ELI}$-queries ${\bm{q}}$ constructed in the proof of [32, Theorem 1]
for Boolean CNFs. As shown in that proof, the problem
$\mathcal{O},A_{0}(a)\models{\bm{q}}(a)$ is NP-hard. If we take copies
$\mathcal{O}^{\prime}$ and ${\bm{q}}^{\prime}$ by replacing all predicates
except $A_{0}$ by fresh predicates, then ${\bm{q}}\wedge{\bm{q}}^{\prime}$ is
a lone conjunct iff
$\mathcal{O}\cup\mathcal{O}^{\prime},A_{0}(a)\not\models{\bm{q}}(a)$. ∎

We next introduce splittings (aka homomorphism dualities). Suppose
$\mathcal{Q}^{\sigma}$ is a class of $\sigma$-queries, for a finite signature
$\sigma$ of predicate symbols, $\mathcal{O}$ an ontology in the signature
$\sigma$, and $Q\subseteq\mathcal{Q}^{\sigma}$ is a finite set queries. A set
$\mathcal{S}(Q)$ of pointed $\sigma$-data instances $(\mathcal{A},a)$ is
called a _split-partner_ for $Q$ wrt $\mathcal{O}$ within
$\mathcal{Q}^{\sigma}$ if, for all ${\bm{q}}^{\prime}\in\mathcal{Q}^{\sigma}$,
we have

$\mathcal{O},\mathcal{A}\models{\bm{q}}^{\prime}(a)\text{ for some
$(\mathcal{A},a)\in\mathcal{S}(Q)$}\quad\text{iff}\quad{\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}\text{
for all ${\bm{q}}\in Q$.}$ (3)

An ontology language $\mathcal{L}$ is said to _have general split-partners
within $\mathcal{Q}^{\sigma}$_ if all finite sets of
$\mathcal{Q}^{\sigma}$-queries have split partners wrt any
$\mathcal{L}$-ontology in the signature $\sigma$. If this holds for all
singleton subsets of $\mathcal{Q}^{\sigma}$, we say that $\mathcal{L}$ _has
split-partners within $\mathcal{Q}^{\sigma}$_.

We illustrate the notion of split-partner by a few examples, the last of which
shows that without the restriction to a finite signature $\sigma$, split-
partners almost never exist.

######  Example 1.

$(i)$ Let $\mathcal{O}$ be any ontology such that $\mathcal{A}$ and
$\mathcal{O}$ are satisfiable for all data instances $\mathcal{A}$; for
example, $\mathcal{O}=\\{A\sqsubseteq B\\}$. Let $\mathcal{Q}^{\sigma}$ be any
class of $\sigma$-CQs, for some signature $\sigma$. Then the split-partner
$\mathcal{S}_{\bot}$ of $\bot(x)$ wrt $\mathcal{O}$ in $\mathcal{Q}^{\sigma}$
is the set

$\mathcal{S}_{\bot}=\\{\mathcal{B}_{\sigma}\\}\quad\text{with}\quad\mathcal{B}_{\sigma}=\\{R(a,a)\mid
R\in\sigma\\}\cup\\{A(a)\mid A\in\sigma\\}.$

Clearly, $\mathcal{O},\mathcal{B}_{\sigma}\models{\bm{q}}$, for any
${\bm{q}}\in\mathcal{Q}^{\sigma}$ different from $\bot$.

$(ii)$ For $\mathcal{O}=\\{A\sqcap B\sqsubseteq\bot\\}$ and
$\sigma=\\{A,B\\}$, we have $\mathcal{S}_{\bot}=\\{\\{A(a)\\},\
\\{B(a)\\}\\}$.

$(iii)$ There does not exist a split-partner for $Q=\\{A(x)\\}$ wrt the empty
ontology $\mathcal{O}$ within ELIQ. To show this, observe that
$B(x)\not\models_{\mathcal{O}}A(x)$ for any unary predicate $B\not=A$. Hence,
as any data instance $\mathcal{A}$ is finite, there is no finite set
$\mathcal{S}(\\{A(x)\\})$ satisfying (3).

In contrast, for frontiers and unique characterisations, restrictions to sets
of predicate symbols containing all symbols in the query and ontology do not
make any difference. Indeed, let $\sigma$ contain all symbols in $\mathcal{O}$
and ${\bm{q}}$. Then, for any class $\mathcal{Q}$ of queries, a set
$\mathcal{F}_{{\bm{q}}}$ is a frontier for ${\bm{q}}$ wrt $\mathcal{O}$ within
$\mathcal{Q}$ if it is a frontier for ${\bm{q}}$ wrt $\mathcal{O}$ within the
restriction of $\mathcal{Q}$ to $\sigma$. The reason is that if
${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime}$ for a CQ ${\bm{q}}^{\prime}$
then ${\bm{q}}^{\prime}$ does not contain any symbols not in ${\bm{q}}$ or
$\mathcal{O}$ if ${\bm{q}}$ is satisfiable wrt $\mathcal{O}$. The same holds
for characterisations $E$ of ${\bm{q}}$ wrt $\mathcal{O}$.

######  Theorem 10.

$\mathcal{ALCHI}$ has general split-partners within ELIQσ, which can be
computed in exponential time.

###### Proof.

Suppose a finite set $Q\subseteq\text{ELIQ}^{\sigma}$ and an
$\mathcal{ALCHI}$-ontology $\mathcal{O}$ in the signature $\sigma$ are given.
Let $\textit{sub}_{\mathcal{O},Q}$ be the closure under single negation of the
set of subconcepts of concepts in $Q$ and $\mathcal{O}$. A _type for_
$\mathcal{O}$ is any maximal subset
$\textit{tp}\subseteq\textit{sub}_{\mathcal{O},Q}$ consistent with
$\mathcal{O}$. Let ${\bm{T}}$ be the set of all types for $\mathcal{O}$.
Define a $\sigma$-data instance $\mathcal{A}$ with
$\textit{ind}(\mathcal{A})={\bm{T}}$, $A(\textit{tp})\in\mathcal{A}$ for all
concept names $A\in\sigma$ and tp such that $A\in\textit{tp}$, and
$P(\textit{tp},\textit{tp}^{\prime})\in\mathcal{A}$ for all role names
$P\in\sigma$, tp and $\textit{tp}^{\prime}$ such that tp and
$\textit{tp}^{\prime}$ can be satisfied by the domain elements of a model of
$\mathcal{O}$ that are related via $P$. We consider an interpretation
$\mathcal{I}_{\mathcal{A}}$ with
$\Delta^{\mathcal{I}_{\mathcal{A}}}=\\{\textit{ind}(\mathcal{A})\\}$,
$A^{\mathcal{I}_{\mathcal{A}}}=\\{\textit{tp}\mid
A(\textit{tp})\in\mathcal{A}\\}$ for concept names $A\in\sigma$,
$A^{\mathcal{I}_{\mathcal{A}}}=\emptyset$ for $A\not\in\sigma$,
$P^{\mathcal{I}_{\mathcal{A}}}=\\{(\textit{tp},\textit{tp}^{\prime})\mid
P(\textit{tp},\textit{tp}^{\prime})\in\mathcal{A}\\}$ for role names
$P\in\sigma$, $P^{\mathcal{I}_{\mathcal{A}}}=\emptyset$ for $P\not\in\sigma$.
It can be readily checked that, for any ${\bm{q}}\in\mathcal{Q}^{\sigma}$,

$\displaystyle\mathcal{I}_{\mathcal{A}}\models\mathcal{O},\mathcal{A},$ (4)
$\displaystyle{\bm{q}}\in\textit{tp}\quad\text{iff}\quad\mathcal{I}_{\mathcal{A}},\textit{tp}\models{\bm{q}}\quad\text{iff}\quad\mathcal{O},\mathcal{A}\models{\bm{q}}(\textit{tp}).$
(5)

Let $Q=\\{{\bm{q}}_{1},\dots,{\bm{q}}_{n}\\}$ and let $\mathcal{A}^{n}$ be the
$n$-times direct product of $\mathcal{A}$. Set

$\mathcal{S}(Q)=\\{(\mathcal{A}^{n},(\textit{tp}_{1},\dots,\textit{tp}_{n}))\mid\neg{\bm{q}}_{i}\in\textit{tp}_{i}\text{
for all }1\leq i\leq n\\}.$

We prove (3) for an arbitrary ${\bm{q}}^{\prime}\in\mathcal{Q}^{\sigma}$. For
the $(\Rightarrow)$ direction, suppose
$\mathcal{O},\mathcal{A}^{n}\models{\bm{q}}^{\prime}(\vec{\textit{tp}})$ for
some $(\mathcal{A}^{n},\vec{\textit{tp}})\in\mathcal{S}(Q)$ and
$\vec{\textit{tp}}=(\textit{tp}_{1},\dots,\textit{tp}_{n})$. Fix
$i\in\\{1,\dots,n\\}$. Observe that the _projection_ map
$h((\textit{tp}_{1}^{\prime},\dots,\textit{tp}_{n}^{\prime}))=\textit{tp}_{i}^{\prime}$
for $(\textit{tp}_{1}^{\prime},\dots,\textit{tp}_{n}^{\prime})\in{\bm{T}}^{n}$
is a homomorphism from $\mathcal{A}^{n}$ to $\mathcal{A}$ such that
$h(\vec{tp})=\textit{tp}_{i}$. As in the proof of Lemma 1 $(1)$, we obtain
$\mathcal{O},\mathcal{A}\models{\bm{q}}^{\prime}(\textit{tp}_{i})$. Recall
that $\neg{\bm{q}}_{i}\in\textit{tp}_{i}$. Then, by (5), we have
$\mathcal{I}_{\mathcal{A}},\textit{tp}_{i}\models{\bm{q}}^{\prime}$,
$\mathcal{I}_{\mathcal{A}},\textit{tp}_{i}\not\models{\bm{q}}_{i}$, and so
using (4) we obtain ${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}_{i}$.
For the opposite direction, suppose
${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}_{i}$ for all $1\leq i\leq
n$. It follows that, for each $i$, there exists $\textit{tp}_{i}\in{\bm{T}}$
such that ${\bm{q}}^{\prime},\neg{\bm{q}}_{i}\in\textit{tp}_{i}$. Let
$\vec{\textit{tp}}=(\textit{tp}_{1},\dots,\textit{tp}_{n})$. Clearly,
$(\mathcal{A}^{n},\vec{tp})\in\mathcal{S}(Q)$ and it remains to show that
$\mathcal{O},\mathcal{A}^{n}\models{\bm{q}}^{\prime}(\vec{\textit{tp}})$.
Observe that, for each $\textit{tp}_{i}$, by (5), there exists a homomorphism
$h_{i}$ that maps ${\bm{q}}^{\prime}$ into $\mathcal{I}_{\mathcal{A}}$ with
its root mapped to $\textit{tp}_{i}$. By the construction of
$\mathcal{I}_{\mathcal{A}}$, the same holds for $\mathcal{A}$ in place of
$\mathcal{I}_{A}$. Because $\mathcal{A}^{n}$ is a direct product, there exists
a homomorphism that maps ${\bm{q}}^{\prime}$ into $\mathcal{A}^{n}$ with its
root mapped to $\vec{tp}$. Thus,
$\mathcal{A}^{n}\models{\bm{q}}^{\prime}(\bm{\vec{\textit{tp}}})$. ∎

Our second sufficient condition of unique characterisability is as follows:

######  Theorem 11.

Suppose $\mathcal{Q}$ is a class of queries, $\mathcal{O}$ an ontology that
admits containment reduction, ${\bm{q}}\in\mathcal{Q}$ is satisfiable wrt
$\mathcal{O}$, and $\sigma$ is a signature containing the predicate symbols in
${\bm{q}}$ and $\mathcal{O}$. If $\mathcal{S}_{{\bm{q}}}$ is a split-partner
for $\\{{\bm{q}}\\}$ wrt $\mathcal{O}$ within $\mathcal{Q}^{\sigma}$, then
$(\\{(\hat{{\bm{q}}},a)\\},\mathcal{S}_{{\bm{q}}})$ is a
singular+characterisation of ${\bm{q}}$ wrt $\mathcal{O}$ within
$\mathcal{Q}$.

###### Proof.

Clearly, ${\bm{q}}$ fits $E$ as $\mathcal{O},\hat{{\bm{q}}}\models{\bm{q}}(a)$
and $\mathcal{O},\mathcal{A}\not\models{\bm{q}}(a)$ for any
$(\mathcal{A},a)\in\mathcal{S}_{{\bm{q}}}$ as otherwise
${\bm{q}}\not\models_{\mathcal{O}}{\bm{q}}$. Now, suppose
${\bm{q}}^{\prime}\not\equiv_{\mathcal{O}}{\bm{q}}$. If
${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}$, then
${\bm{q}}\not\models_{\mathcal{O}}{\bm{q}}^{\prime}$, and so
$\mathcal{O},\hat{{\bm{q}}}\not\models{\bm{q}}^{\prime}(a)$. Hence
${\bm{q}}^{\prime}$ does not fit $E$. If
${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}$, then there exists
$(\mathcal{A},a)\in\mathcal{S}_{{\bm{q}}}$ with
$\mathcal{O},\mathcal{A}\models{\bm{q}}^{\prime}(a)$, and so again
${\bm{q}}^{\prime}$ does not fit $E$. ∎

As a consequence of Theorem 10, 11 and Lemma 1, we obtain the following:

######  Theorem 12.

If ${\bm{q}}\in\text{ELIQ}^{\sigma}$ is satisfiable wrt an
$\mathcal{ALCHI}$-ontology $\mathcal{O}$ in a signature $\sigma$, then
${\bm{q}}$ has a singular+characterisation wrt $\mathcal{O}$ within ELIQσ.

The sufficient conditions for singular+characterisations of Theorems 8 and 11
use the notions of frontier and split-partner, respectively. We now give
examples showing that there are rather simple queries (and ontologies) with
frontiers but no split-partners and vice versa. Hence these two notions are
not equivalent. The query witnessing that frontiers can exist where split-
partners do not exist provides a counterexample even if one admits frontiers
containing CQs. In more detail, a _CQ-frontier_ for an ELIQ ${\bm{q}}$ wrt to
an ontology $\mathcal{O}$ is a set $\mathcal{F}_{{\bm{q}}}$ of CQs such that

  * •

if ${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$, for a CQ
${\bm{q}}^{\prime}\in\mathcal{F}_{{\bm{q}}}$ and an ELIQ
${\bm{q}}^{\prime\prime}$, then
${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$ and
${\bm{q}}^{\prime\prime}\not\models_{\mathcal{O}}{\bm{q}}$;

  * •

if ${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$ and
${\bm{q}}^{\prime\prime}\not\models_{\mathcal{O}}{\bm{q}}$, for an ELIQ
${\bm{q}}^{\prime\prime}$, then there exists
${\bm{q}}^{\prime}\in\mathcal{F}_{{\bm{q}}}$ such that
${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$.

Clearly standard ELIQ frontiers defined above are also CQ-frontiers.

######  Theorem 13.

$\mathcal{EL}$ does not admit finite CQ-frontiers within ELIQ.

###### Proof.

We show that the query ${\bm{q}}=A\wedge B$ does not have a finite CQ-frontier
wrt the ontology

$\mathcal{O}=\\{A\sqsubseteq\exists R.A,\ \exists R.A\sqsubseteq A\\}$

within ELIQs. Suppose otherwise. Let $\mathcal{F}_{{\bm{q}}}$ be such a CQ-
frontier. Consider the ELIQs $\bm{r}_{n,m}=\exists R^{n}\exists{R^{-}}^{m}.B$
with $n>m>0$. Clearly, ${\bm{q}}\not\models_{\mathcal{O}}\bm{r}_{n,m}$, and so
$\bm{r}_{n,m}$ cannot be entailed wrt $\mathcal{O}$ by any CQ in
$\mathcal{F}_{{\bm{q}}}$. Thus, if
${\bm{q}}^{\prime}\in\mathcal{F}_{{\bm{q}}}$ and $B(x)$ is in
${\bm{q}}^{\prime}(x)$, then we cannot have an $R$-cycle in
${\bm{q}}^{\prime}$ reachable from $x$ along an $R$-path as otherwise we would
have ${\bm{q}}^{\prime}\models_{\mathcal{O}}\bm{r}_{n,m}$ for suitable $n,m$.

Consider now the ELIQs ${\bm{q}}_{n}=B\wedge\exists R^{n}.\top$, for all
$n\geq 1$. Clearly, ${\bm{q}}\models_{\mathcal{O}}{\bm{q}}_{n}$. As
${\bm{q}}_{n}\not\models_{\mathcal{O}}{\bm{q}}$, infinitely many
${\bm{q}}_{n}$ are entailed by some
${\bm{q}}^{\prime}\in\mathcal{F}_{{\bm{q}}}$ wrt $\mathcal{O}$. Take such a
${\bm{q}}^{\prime}$. Since $B(x)\in{\bm{q}}^{\prime}$ because of
${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}_{n}$, no $R$-cycle is
reachable from $x$ via an $R$-path in ${\bm{q}}^{\prime}$. Note also that no
$y$ with $A(y)\in{\bm{q}}^{\prime}$ can be reached from $x$ along an $R$-path
as otherwise ${\bm{q}}^{\prime}\models_{\mathcal{O}}B\wedge\exists R^{k}.A$
for some $k\geq 0$ and, since $B\wedge\exists
R^{k}.A\models_{\mathcal{O}}{\bm{q}}$ by the second axiom in $\mathcal{O}$, we
would have ${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}$.

To derive a contradiction, we show now that there is an $R$-path of any length
$n$ starting at $x$ in ${\bm{q}}^{\prime}$. Suppose this is not the case. Let
$n$ be the length of a longest $R$-path starting at $x$ in
${\bm{q}}^{\prime}$. We construct a model $\mathcal{I}$ of $\mathcal{O}$ and
${\bm{q}}^{\prime}$ refuting ${\bm{q}}_{n+l}$, for any $l\geq 1$. Define
$\mathcal{I}$ by taking

  * •

$\Delta^{\mathcal{I}}=\textit{var}({\bm{q}}^{\prime})\cup\\{d_{1},d_{2},\dots\\}$,
for fresh $d_{i}$;

  * •

$a\in B^{\mathcal{I}}$ if $B(a)\in{\bm{q}}^{\prime}$;

  * •

$a\in A^{\mathcal{I}}$ if there is an $R$-path in ${\bm{q}}^{\prime}$ from $a$
to some $y$ with $A(y)\in{\bm{q}}^{\prime}$ or $a=d_{i}$ for some $i$;

  * •

$(a,b)\in R^{\mathcal{I}}$ if $R(a,b)\in{\bm{q}}^{\prime}$ or there is an
$R$-path in ${\bm{q}}^{\prime}$ from $a$ to some $y$ with
$A(y)\in{\bm{q}}^{\prime}$ and $b=d_{1}$, or $a=d_{i}$ and $b=d_{i+1}$.

By the construction and the fact that no $y$ with $A(y)\in{\bm{q}}^{\prime}$
can be reached from $x$ along an $r$-path, $\mathcal{I}$ is a model of
$\mathcal{O}$ and ${\bm{q}}^{\prime}$ refuting ${\bm{q}}_{n+l}$. ∎

######  Example 2.

On the other hand, the following set of pointed data instances is a split-
partner of $\\{{\bm{q}}\\}$ wrt $\mathcal{O}$ from the proof of Theorem 13
within ELIQ{A,B,R}; here all arrows are assumed to be labelled with $R$:

$a$$A$$b$$A,B$$a$$B$$b$$A,B$

######  Theorem 14.

There exist a $\textsl{DL-Lite}^{-}_{\mathcal{F}}$ ontology $\mathcal{O}$, a
query ${\bm{q}}$ and a signature $\sigma$ such that $\\{{\bm{q}}\\}$ does not
have a finite split-partner wrt $\mathcal{O}$ within ELIQσ.

###### Proof.

Consider ${\bm{q}}=A$ and
$\mathcal{O}=\\{\text{fun}(P),\text{fun}(P^{-}),B\sqcap\exists
P^{-}\sqsubseteq\bot\\}$. We show that $Q=\\{{\bm{q}}\\}$ does not have a
finite split partner wrt $\mathcal{O}$ within ELIQ{A,B,P}. Suppose otherwise
and $\mathcal{S}(Q)$ is such a split-partner. Then there is
$(\mathcal{A},a)\in\mathcal{S}(Q)$ with $\mathcal{O},\mathcal{A}\models
B\sqcap\exists P^{n}.\top(a)$ for all sufficiently large $n$ because
$B\sqcap\exists P^{n}.\top\not\models_{\mathcal{O}}A$. Then $\mathcal{A}$ must
contain $n$ nodes if $\mathcal{O}$ and $\mathcal{A}$ are satisfiable, so
$\mathcal{S}(Q)$ is infinite.

On the other hand, $\\{\top\\}$ is a frontier for $A$ wrt $\mathcal{O}$ within
ELIQ. ∎

Our final example in this section combines the examples of the two previous
theorems and shows that even by taking frontiers and splittings together we do
not obtain a universal method for constructing singular+unique
characterisations.

######  Example 3.

Consider the ELIQ ${\bm{q}}=A\wedge B$ and the
$\mathcal{ELFI}^{\bot}$-ontology

$\mathcal{O}=\\{A\sqsubseteq\exists R.A,\ \exists R.A\sqsubseteq A,\
\text{fun}(P),\ \text{fun}(P^{-}),\ E\sqcap\exists P^{-}\sqsubseteq\bot\\}.$

It can be shown in the same way as above that ${\bm{q}}$ has no frontier wrt
$\mathcal{O}$ within ELIQ and that ${\bm{q}}$ does not have any split-partner
wrt $\mathcal{O}$ within ELIQ{A,B,R,P,E}. However, a singular+unique
characterisation of ${\bm{q}}$ wrt $\mathcal{O}$ within ELIQ is obtained by
taking $E^{+}=\\{\hat{{\bm{q}}}\\}$ and $E^{-}$ the same as in Example 2. (To
show the latter one only has to observe that $E^{-}$ is a split-partner of
${\bm{q}}$ wrt $\mathcal{O}$ within ELIQ{A,B,R} and that
$\mathcal{O},\hat{{\bm{q}}}\not\models\bm{r}$ for any $\bm{r}$ containing any
of the symbols $P$ or $E$.)

###  3.2 Two-dimensional Queries

A _temporal $\sigma$-data instance_, $\mathcal{D}$, is a finite sequence
$\mathcal{A}_{0},\dots,\mathcal{A}_{n}$ of $\sigma$-data instances, where,
intuitively, each $\mathcal{A}_{i}$ comprises the facts with timestamp $i$. We
assume that all $\textit{ind}(\mathcal{A}_{i})$ are the same, adding $\top(a)$
to $\mathcal{A}_{i}$ if needed, and set
$\textit{ind}(\mathcal{D})=\textit{ind}(\mathcal{A}_{0})$. The _length_ of
$\mathcal{D}$ is $\max(\mathcal{D})=n$ and the _size_ of $\mathcal{D}$ is
$|\mathcal{D}|=\sum_{i\leq n}|\mathcal{A}_{i}|$. Within a temporal
$\sigma$-data instance, we often denote by $\emptyset$ the data instance
$\\{\top(a)\mid a\in\textit{ind}(\mathcal{D})\\}$.

_Two-dimensional queries_ , ${\bm{q}}$, for accessing temporal data instances
we propose in this paper are built from domain queries in a given class
$\mathcal{Q}$ (say, ELIQs) using $\wedge$ and the (future-time) temporal
operators from the standard linear temporal logic LTL over the time flow
$(\mathbb{N},<)$: unary $\bigcirc$ (at the next moment), $\Diamond$ (some time
later), $\Diamond_{\\!r}$ (now or later), and binary $\mathbin{\mathsf{U}}$
(until); see below for the precise semantics. The class of such 2D-queries
that only use the operators from a set
$\Phi\subseteq\\{{\raisebox{1.07639pt}{\text{$\bigcirc$}}},\Diamond,\Diamond_{\\!r},\mathbin{\mathsf{U}}\\}$
is denoted by $\textsl{LTL}^{\Phi}(\mathcal{Q})$. The class
$\textsl{LTL}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}_{p}(\mathcal{Q})$
comprises _path queries_ of the form

${\bm{q}}=\bm{r}_{0}\land{\bm{o}}_{1}(\bm{r}_{1}\land{\bm{o}}_{2}(\bm{r}_{2}\land\dots\land{\bm{o}}_{n}\bm{r}_{n})),$
(6)

where
${\bm{o}}_{i}\in\\{{\raisebox{1.07639pt}{\text{$\bigcirc$}}},\Diamond,\Diamond_{\\!r}\\}$
and $\bm{r}_{i}\in\mathcal{Q}$; _path queries_ in
$\textsl{LTL}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}_{p}(\mathcal{Q})$
take the form

${\bm{q}}=\bm{r}_{0}\land(\bm{l}_{1}\mathbin{\mathsf{U}}(\bm{r}_{1}\land(\bm{l}_{2}\mathbin{\mathsf{U}}(\dots(\bm{l}_{n}\mathbin{\mathsf{U}}\bm{r}_{n})\dots)))),$
(7)

where $\bm{r}_{i}\in\mathcal{Q}$ and either $\bm{l}_{i}\in\mathcal{Q}$ or
$\bm{l}_{i}=\bot$. We use the character $\mathcal{C}$ to refer to classes of
2D queries. The _size_ $|{\bm{q}}|$ of ${\bm{q}}$ is the number of symbols in
${\bm{q}}$, and the _temporal depth_ $\textit{tdp}({\bm{q}})$ of ${\bm{q}}$ is
the maximum number of nested temporal operators in ${\bm{q}}$.

An (atemporal) ontology $\mathcal{O}$ and temporal data instance
$\mathcal{D}=\mathcal{A}_{0},\ldots,\mathcal{A}_{n}$ are _satisfiable_ if
$\mathcal{O}$ and $\mathcal{A}_{i}$ are satisfiable for each $i\leq n$. For
satisfiable $\mathcal{O}$ and $\mathcal{D}$, the _entailment relation_
$\mathcal{O},\mathcal{D},\ell,a\models{\bm{q}}$ with $\ell\in\mathbb{N}$ and
$a\in\textit{ind}(\mathcal{D})$ is defined by induction as follows, where
$\mathcal{A}_{\ell}=\emptyset$, for $\ell>n$:

$\displaystyle\mathcal{O},\mathcal{D},\ell,a\models{\bm{q}}\ \text{ iff \
$\mathcal{O},\mathcal{A}_{\ell}\models{\bm{q}}(a)$, for any
${\bm{q}}\in\mathcal{Q}$},$
$\displaystyle\mathcal{O},\mathcal{D},\ell,a\models{\bm{q}}_{1}\land{\bm{q}}_{2}\text{
iff }\mathcal{O},\mathcal{D},\ell,a\models{\bm{q}}_{1}\text{ and
}\mathcal{O},\mathcal{D},\ell,a\models{\bm{q}}_{2},$
$\displaystyle\mathcal{O},\mathcal{D},\ell,a\models{\raisebox{1.07639pt}{\text{$\bigcirc$}}}{\bm{q}}\
\text{ iff }\ \mathcal{O},\mathcal{D},\ell+1,a\models{\bm{q}},$
$\displaystyle\mathcal{O},\mathcal{D},\ell,a\models\Diamond{\bm{q}}\ \text{
iff }\ \mathcal{O},\mathcal{D},m,a\models{\bm{q}},\text{ for some $m>\ell$},$
$\displaystyle\mathcal{O},\mathcal{D},\ell,a\models\Diamond_{\\!r}{\bm{q}}\
\text{ iff }\ \mathcal{O},\mathcal{D},m,a\models{\bm{q}},\text{ for some
$m\geq\ell$},$
$\displaystyle\mathcal{O},\mathcal{D},\ell,a\models{\bm{q}}_{1}\mathbin{\mathsf{U}}{\bm{q}}_{2}\
\text{ iff \ \ there is $m>\ell$ such that
}\mathcal{O},\mathcal{D},m,a\models{\bm{q}}_{2}\text{ and }$
$\displaystyle\hskip
110.96556pt\mathcal{O},\mathcal{D},k,a\models{\bm{q}}_{1},\text{ for all $k$,
$\ell<k<m$}.$

If $\mathcal{O}$ and $\mathcal{D}$ are not satisfiable, we set
$\mathcal{O},\mathcal{D},\ell,a\models{\bm{q}}$ for all ${\bm{q}}$, $\ell$ and
$a$.

Observe that for ontologies $\mathcal{O}$, which are not Horn, there is an
alternative natural semantics based on temporal structures. A _temporal
structure_ $\mathcal{I}$ is a sequence
$\mathcal{I}_{0},\mathcal{I}_{1},\ldots$ of domain structure $\mathcal{I}_{i}$
as introduced above such that
$a^{\mathcal{I}_{n_{1}}}=a^{\mathcal{I}_{n_{2}}}$ for any individual $a$ and
$n_{1},n_{2}\in\mathbb{N}$. $\mathcal{I}$ is a model of
$\mathcal{D}=\mathcal{A}_{0},\ldots,\mathcal{A}_{n}$ if each $\mathcal{I}_{i}$
is a model of $\mathcal{A}_{i}$ for $i\leq n$ and it is a model of
$\mathcal{O}$ if each $\mathcal{I}_{i}$ is a model of $\mathcal{O}$. The truth
relation $\mathcal{I},\ell,a\models{\bm{q}}$ is defined in the obvious way and
$\mathcal{O},\mathcal{D},\ell,a\models_{c}{\bm{q}}$ iff
$\mathcal{I},\ell,a\models{\bm{q}}$ for every model $\mathcal{I}$ of
$\mathcal{O}$ and $\mathcal{D}$. It is easy to see that $\models$ coincides
with $\models_{c}$ for any ontology $\mathcal{O}$ formulated in the Horn-
fragment of FO [20], in particular all DL-Lite dialects considered in this
paper and $\mathcal{ELHIF}^{\bot}$. Thus, the results presented in this paper
also hold under $\models_{c}$ if one considers such ontologies. In general,
however, the two entailment relations do not coincide: consider the ontology
$\mathcal{O}=\\{\top\sqsubseteq A\sqcup B\\}$ and the data instance
$\mathcal{D}=\emptyset,\mathcal{A}_{1},\emptyset,\mathcal{A}_{3}$ with
$\mathcal{A}_{1}=\\{A(a)\\}$ and $\mathcal{A}_{3}=\\{B(a)\\}$. Then
$\mathcal{O},\mathcal{D},0,a\models_{c}\Diamond(A\wedge{\raisebox{1.07639pt}{\text{$\bigcirc$}}}B)$
but
$\mathcal{O},\mathcal{D},0,a\not\models\Diamond(A\wedge{\raisebox{1.07639pt}{\text{$\bigcirc$}}}B)$.
In what follows we consider $\models$ only and leave an investigation for
$\models_{c}$ in the non-Horn case as future work.

An _example set_ is a pair $E=(E^{+},E^{-})$ with finite sets $E^{+}$ and
$E^{-}$ of pointed temporal data instances $\mathcal{D},a$ with
$a\in\textit{ind}(\mathcal{D})$. We say that a query ${\bm{q}}$ _fits_ $E$ wrt
$\mathcal{O}$ if $\mathcal{O},\mathcal{D}^{+},0,a^{+}\models{\bm{q}}$ and
$\mathcal{O},\mathcal{D}^{-},0,a^{-}\not\models{\bm{q}}$, for all
$\mathcal{D}^{+},a^{+}\in E^{+}$ and $\mathcal{D}^{-},a^{-}\in E^{-}$. As
before, $E$ _uniquely characterises ${\bm{q}}$ wrt $\mathcal{O}$ within a
class $\mathcal{C}$ of 2D-queries_ if ${\bm{q}}$ fits $E$ wrt $\mathcal{O}$
and every ${\bm{q}}^{\prime}\in\mathcal{C}$ fitting $E$ wrt $\mathcal{O}$ is
equivalent to ${\bm{q}}$ wrt $\mathcal{O}$. (Equivalence of 2D-queries wrt an
ontology is defined similarly to the 1D case.) If all ${\bm{q}}\in\mathcal{C}$
are uniquely characterised by some $E$ wrt $\mathcal{O}$ within
$\mathcal{C}^{\prime}\supseteq\mathcal{C}$, we call $\mathcal{C}$ _uniquely_
_characterisable wrt $\mathcal{O}$ within $\mathcal{C}^{\prime}$_. Let
$\mathcal{C}^{n}$ be the set of queries in $\mathcal{C}$ of temporal depth
$\leq n$. We say that $\mathcal{C}$ is _polynomially characterisable wrt
$\mathcal{O}$ for bounded temporal depth_ if there is a polynomial $f$ such
that every ${\bm{q}}\in\mathcal{C}^{n}$ is characterised by some $E$ of size
$\leq f(n)$ within $\mathcal{C}^{n}$.

Note that $\Diamond\bm{r}$ is equivalent to
${\raisebox{1.07639pt}{\text{$\bigcirc$}}}\Diamond_{\\!r}\bm{r}$, so
$\Diamond$ does not add any expressive power to
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
and
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})=\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond_{r}}}(\mathcal{Q})$;
however,
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}(\mathcal{Q})\subsetneq\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$

In the remainder of the paper, we investigate unique characterisability of 2D
queries with respect to various query classes defined above.

##  4
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$

The aim of this section is to give a criterion for (polynomial) unique
characterisability of queries in the class
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
under certain conditions on the ontology and on $\mathcal{Q}$.

It will be convenient to represent queries ${\bm{q}}$ of the form (6) as a
sequence

${\bm{q}}=\bm{r}_{0}(t_{0}),R_{1}(t_{0},t_{1}),\dots,\bm{r}_{m-1}(t_{m-1}),R_{m}(t_{m-1},t_{m}),\bm{r}_{m}(t_{m}),$
(8)

where $R_{i}\in\\{\textit{suc},<,\leq\\}$, $\textit{suc}(t,t^{\prime})$ stands
for $t^{\prime}=t+1$, and the $t_{i}$ are variables over $(\mathbb{N},<)$. We
set $\textit{var}({\bm{q}})=\\{t_{0},\dots,t_{m}\\}$ (so we do not take into
account the non-answer variables in the $\bm{r}_{i}$ here).

######  Example 4.

Below are a 2D-query ${\bm{q}}$ and its representation of the form (8):

$\exists P.B\land{\raisebox{1.07639pt}{\text{$\bigcirc$}}}(\exists
P.A\land\Diamond A)\ \ \leadsto\ \ \exists
P.B(t_{0}),\textit{suc}(t_{0},t_{1}),\exists
P.A(t_{1}),(t_{1}<t_{2}),A(t_{2})$

with $\textit{var}({\bm{q}})=\\{t_{0},t_{1},t_{2}\\}$.

We divide ${\bm{q}}$ of the form (8) into _blocks_ ${\bm{q}}_{i}$ such that

$\displaystyle{\bm{q}}={\bm{q}}_{0}\mathcal{R}_{1}{\bm{q}}_{1}\dots\mathcal{R}_{n}{\bm{q}}_{n},$
(9)

where $\mathcal{R}_{i}=R_{1}^{i}(t_{0}^{i},t_{1}^{i})\dots
R_{n_{i}}^{i}(t_{n_{i}-1}^{i},t_{n_{i}}^{i})$ with $R_{j}^{i}\in\\{<,\leq\\}$
and

$\displaystyle{\bm{q}}_{i}=\bm{r}_{0}^{i}(s_{0}^{i})\textit{suc}(s_{0}^{i},s_{1}^{i})\bm{r}_{1}^{i}(s_{1}^{i})\dots\textit{suc}(s_{k_{i}-1}^{i},s_{k_{i}}^{i})\bm{r}_{k_{i}}^{i}(s_{k_{i}}^{i})$
(10)

with $s_{k_{i}}^{i}=t_{0}^{i+1}$, $t_{n_{i}}^{i}=s_{0}^{i}$. If $k_{i}=0$, the
block ${\bm{q}}_{i}$ is called _primitive_.

######  Example 5.

The query ${\bm{q}}$ from Example 4 has two blocks

${\bm{q}}_{0}=\exists P.B(t_{0}),\textit{suc}(t_{0},t_{1}),\exists
P.A(t_{1})\quad\text{and}\quad{\bm{q}}_{1}=A(t_{2}),$

connected by $(t_{1}<t_{2})$. It contains one primitive block, ${\bm{q}}_{1}$.

Suppose we are given an ontology $\mathcal{O}$ and a class $\mathcal{Q}$ of
domain queries. Then a primitive block
${\bm{q}}_{i}=\bm{r}_{0}^{i}(s_{0}^{i})$ with $i>0$ in ${\bm{q}}$ of the form
(9) is called a _lone conjunct wrt $\mathcal{O}$ within $\mathcal{Q}$_ if
$\bm{r}_{0}^{i}$ is meet-reducible wrt $\mathcal{O}$ within $\mathcal{Q}$.

######  Example 6.

Let $\mathcal{P}$ be the class of conjunctions of unary atoms; we call such
queries _propositional_. The query $\Diamond A$, which is represented by the
sequence $\top(t_{0}),(t_{0}<t_{1}),A(t_{1})$, does not have any lone
conjuncts wrt the empty ontology within $\mathcal{Q}$, but $A$ is a lone
conjunct of $\Diamond A$ wrt $\mathcal{O}=\\{A\equiv B\land C\\}$ within
$\mathcal{Q}$.

The query ${\bm{q}}=\Diamond A$ is uniquely characterised wrt the empty
ontology within
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{P})$
by the example set $E=(E^{+},E^{-})$, where $E^{+}$ contains two temporal data
instances $\emptyset,\\{A\\}$ and $\emptyset,\emptyset,\\{A\\}$ and $E^{-}$
consists of one instance $\emptyset$. However, the same ${\bm{q}}$ cannot be
uniquely characterised wrt $\mathcal{O}=\\{A\equiv B\land C\\}$ within
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{P})$
as shown in [22]. Observe also that $A$ is a lone conjunct in
${\bm{q}}^{\prime}=\Diamond(A\land\Diamond_{\\!r}D)$ wrt
$\mathcal{O}^{\prime}=\mathcal{O}\cup\\{D\sqsubseteq A\\}$ but for the
simplification ${\bm{q}}^{\prime\prime}=\Diamond D$ of ${\bm{q}}^{\prime}$ we
have ${\bm{q}}^{\prime\prime}\equiv_{\mathcal{O}^{\prime}}{\bm{q}}^{\prime}$
and ${\bm{q}}^{\prime\prime}$ does not have any lone conjuncts wrt
$\mathcal{O}^{\prime}$.

Example 6 shows that the notion of lone conjunct is dependent on the
presentation of the query. To make lone conjuncts semantically meaningful, we
introduce a normal form. Given an ontology $\mathcal{O}$ and a query
${\bm{q}}$ of the form (9), we say that ${\bm{q}}$ is in _normal form wrt
$\mathcal{O}$_ if the following conditions hold:

(n1)

$\bm{r}_{0}^{i}\not\equiv_{\mathcal{O}}\top$ if $i>0$, and
$\bm{r}_{k_{i}}^{i}\not\equiv_{\mathcal{O}}\top$ if $i>0$ or $k_{i}>0$ (thus,
of all the first/last $\bm{r}$ in a block only $\bm{r}_{0}^{0}$ can be
trivial);

(n2)

each $\mathcal{R}_{i}$ is either a single $t_{0}^{i}\leq t_{1}^{i}$ or a
sequence of $<$;

(n3)

$\bm{r}_{k_{i}}^{i}\not\models_{\mathcal{O}}\bm{r}_{0}^{i+1}$ if
${\bm{q}}_{i+1}$ is primitive and $R_{i+1}$ is $\leq$;

(n4)

$\bm{r}_{0}^{i+1}\not\models_{\mathcal{O}}\bm{r}_{k_{i}}^{i}$ if $i>0$,
${\bm{q}}_{i}$ is primitive and $R_{i+1}$ is $\leq$;

(n5)

$\bm{r}_{k_{i}}^{i}(x)\land\bm{r}_{0}^{i+1}(x)$ is satisfiable wrt
$\mathcal{O}$ whenever $R_{i+1}$ is $\leq$.

######  Lemma 5.

Let $\mathcal{O}$ be an FO-ontology (possibly with $=$). Then every query
${\bm{q}}\in\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
is equivalent wrt $\mathcal{O}$ to a query in normal form of size at most
$|{\bm{q}}|$ and of temporal depth at most the temporal depth of ${\bm{q}}$.
This query can be computed in polynomial time if containment between queries
in $\mathcal{Q}$ wrt $\mathcal{O}$ is decidable in polynomial time. For ELIQs,
this is the case for $\textsl{DL-Lite}_{\cal{F}}$ but not for $\textsl{DL-
Lite}_{\mathcal{H}}$ (unless $\textup{P}=\textup{NP}$).

###### Proof.

The transformation is straightforward: to ensure (n1), drop any
$\bm{r}_{0}^{i}$ and $\bm{r}_{k_{i}}^{i}$ for which (n1) fails and add one $<$
to the relevant $\mathcal{R}_{i}$. To ensure (n2), replace any
$\mathcal{R}_{i}$ containing at least one occurrence of $<$ with the sequence
obtained from $\mathcal{R}_{i}$ by dropping all occurrences of $\leq$ and
replace any $\mathcal{R}_{i}$ not containing any occurrence of $<$ by a single
$\leq$. To ensure (n3), drop any $\bm{r}_{0}^{i+1}$ with
$\bm{r}_{k_{i}}^{i}\models_{\mathcal{O}}\bm{r}_{0}^{i+1}$ if ${\bm{q}}_{i+1}$
is primitive and $\mathcal{R}_{i+1}$ is $\leq$. To ensure (n4) drop any
$\bm{r}_{k_{i}}^{i}$ with
$\bm{r}_{0}^{i+1}\models_{\mathcal{O}}\bm{r}_{k_{i}}^{i}$ if $i>0$,
${\bm{q}}_{i}$ is primitive and $\mathcal{R}_{i+1}$ is $\leq$. Finally, to
ensure (n5), replace $\leq$ by $<$ if $\bm{r}_{k_{i}}^{i},\bm{r}_{0}^{i+1}$
are $\mathcal{O}$-compatible and $\mathcal{R}_{i+1}$ is $\leq$.

The second part follows from the fact that query containment in $\textsl{DL-
Lite}_{\mathcal{F}}$ is in P and NP-hard in $\textsl{DL-Lite}_{\mathcal{H}}$
[32]. ∎

We call a query
${\bm{q}}\in\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
_safe wrt $\mathcal{O}$_ if it is equivalent wrt $\mathcal{O}$ to an
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$-query
in normal form that has no lone conjuncts.

It is to be noted that our temporal query languages do not admit containment
reduction as, for example, there is no temporal data instance $\hat{\bm{q}}$
for ${\bm{q}}={\raisebox{1.07639pt}{\text{$\bigcirc$}}}(A\wedge\Diamond B)$
because it will have to fix the number of steps between 0 and the moment where
$B$ holds.

We are now in a position to formulate the main result of this section.

######  Theorem 15.

Suppose an ontology $\mathcal{O}$ admits singular+characterisations within a
class of domain queries $\mathcal{Q}$. Then the following hold:

  1. $(i)$

A query
${\bm{q}}\in\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
is uniquely characterisable within
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
wrt $\mathcal{O}$ iff ${\bm{q}}$ is safe wrt $\mathcal{O}$.

  2. $(ii)$

If $\mathcal{O}$ admits polynomial-size singular+characterisations within
$\mathcal{Q}$, then those queries that are uniquely characterisable within
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
are actually polynomially characterisable within
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$.

  3. $(iii)$

The class
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
is polynomially characterisable for bounded temporal depth if $\mathcal{O}$
admits polynomial-size singular+characterisations within $\mathcal{Q}$.

  4. $(iv)$

The class
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}(\mathcal{Q})$
is uniquely characterisable. It is polynomially characterisable if
$\mathcal{O}$ admits polynomial-size singular+characterisations within
$\mathcal{Q}$.

To prove Theorem 15 we first provide some notation for talking about the
entailment relation $\mathcal{O},\mathcal{D}\models{\bm{q}}$. Let
$\mathcal{D}=\mathcal{A}_{0},\ldots,\mathcal{A}_{n}$,
$a\in\textit{ind}(\mathcal{D})$, and let ${\bm{q}}$ take the form (8). A map
$h\colon\textit{var}({\bm{q}})\to[0,\max(\mathcal{D})]$ is called a _root
$\mathcal{O}$-homomorphism_ from ${\bm{q}}$ to $(\mathcal{D},a)$ if
$h(t_{0})=0$, $\mathcal{O},\mathcal{A}_{h(t)}\models\bm{r}(a)$ if
$\bm{r}(t)\in{\bm{q}}$, $h(t^{\prime})=h(t)+1$ if
$\textit{suc}(t,t^{\prime})\in{\bm{q}}$, and $h(t)\,R\,h(t^{\prime})$ if
$R(t,t^{\prime})\in{\bm{q}}$ for $R\in\\{<,\leq\\}$. It is readily seen that
$\mathcal{O},\mathcal{D},a,0\models{\bm{q}}$ iff there exists a root
$\mathcal{O}$-homomorphism from ${\bm{q}}$ to $(\mathcal{D},a)$.

Let $b\geq 1$. The instance $\mathcal{D}$ is said to be _$b$ -normal wrt
$\mathcal{O}$_ if it takes the form

$\mathcal{D}=\mathcal{D}_{0}\emptyset^{b}\mathcal{D}_{1}\ldots\emptyset^{b}\mathcal{D}_{n},\text{
where }\mathcal{D}_{i}=\mathcal{A}_{0}^{i}\ldots\mathcal{A}_{k_{i}}^{i},$ (11)

with $b>k_{i}\geq 0$ and
$\mathcal{A}_{0}^{i}\not\equiv_{\mathcal{O}}\emptyset$ if $i>0$, and
$\mathcal{A}_{k_{i}}^{i}\not\equiv_{\mathcal{O}}\emptyset$ if $i>0$ or
$k_{i}>0$ (thus, of all the first/last $\mathcal{A}$ in a $\mathcal{D}_{i}$
only $\mathcal{A}_{0}^{0}$ can be trivial). Following the terminology for
queries, we call each $\mathcal{D}_{i}$ _a block of_ $\mathcal{D}$. For a
block $\mathcal{D}_{i}$ in $\mathcal{D}$, we denote by $I(\mathcal{D}_{i})$
the subset of $[0,\max(\mathcal{D})]$ occupied by $\mathcal{D}_{i}$. Then we
call a root $\mathcal{O}$-homomorphism $h\colon{\bm{q}}\to\mathcal{D}$ _block
surjective_ if every $j\in I(\mathcal{D}_{i})$ with a block $\mathcal{D}_{i}$
is in the range $\textit{ran}(h)$ of $h$. We next aim to state that after
‘weakening’ the non-temporal data instances in blocks, no root
$\mathcal{O}$-homomorphism from ${\bm{q}}$ to $\mathcal{D}$ exists. This is
only required if the non-temporal data instances are obtained from queries in
$\mathcal{Q}$, and so we express ‘weakening’ using singular+characterisations
of queries in $\mathcal{Q}$ wrt $\mathcal{O}$.

In detail, suppose $\mathcal{A}^{i}_{j}=\hat{\bm{s}}^{i}_{j}$, for queries
$\bm{s}^{i}_{j}\in\mathcal{Q}$. Given $\bm{s}\in\mathcal{Q}$, take the
singular+characterisation $(\\{\hat{\bm{s}}\\},\mathcal{N}_{\bm{s}})$ of
$\bm{s}$ wrt $\mathcal{O}$ within $\mathcal{Q}$, where $\\{\hat{\bm{s}}\\}$ is
the only positive data instance, and $\mathcal{N}_{\bm{s}}$ is the set of
negative data instances. To make our notation more uniform, we think of the
pointed data instances in $\mathcal{N}_{\bm{s}}$ as having the form
$\hat{\bm{s}}^{\prime}$, for a suitable CQ $\bm{s}^{\prime}$ (which is not
necessarily in $\mathcal{Q}$).

For $\ell\in\textit{ran}(h)$, let

$\bm{r}_{\ell}=\bigwedge_{\bm{r}(t)\in{\bm{q}},h(t)=\ell}\bm{r}.$

Then $h$ is called _data surjective_ if
$\mathcal{O},\hat{\bm{s}}\not\models\bm{r}_{\ell}(a)$, for any
$\bm{s}\in\mathcal{N}_{\bm{s}^{i}_{j}}$ and any $\ell\in\textit{ran}(h)$ such
that ${\bm{s}}^{i}_{j}\not\equiv\top$, where $\hat{\bm{s}}^{i}_{j}$ is the
data instance placed at $\ell$ in $\mathcal{D}$.

We call the root $\mathcal{O}$-homomorphism $h:{\bm{q}}\rightarrow\mathcal{D}$
a _root $\mathcal{O}$-isomorphism_ if it is data surjective and, for the
blocks ${\bm{q}}_{0},\dots,{\bm{q}}_{m}$ of ${\bm{q}}$, we have $n=m$ and $h$
restricted to $\textit{var}({\bm{q}}_{i})$ is a bijection onto
$I(\mathcal{D}_{i})$ for all $i\leq n$ (in particular, $h$ is block
surjective). Intuitively, if we have a root $\mathcal{O}$-isomorphism
$h\colon{\bm{q}}\rightarrow\mathcal{D}$, then ${\bm{q}}$ is almost the same as
$\mathcal{D}$ except for differences between the sequences $\mathcal{R}_{i}$
in ${\bm{q}}$ and the gaps between blocks in $\mathcal{D}$.

Let $\mathcal{Q}$, $\mathcal{O}$, ${\bm{q}}$, and $\mathcal{D}$ be as before
with $\mathcal{D}$ of the form (11), where
$\mathcal{A}^{i}_{j}=\hat{\bm{s}}^{i}_{j}$, for
$\bm{s}^{i}_{j}\in\mathcal{Q}$. The following rules will be used to define the
negative examples in the unique characterisation of ${\bm{q}}$ and as steps in
the learning algorithm. They are applied to $\mathcal{D}$:

  1. (a)

replace some $\hat{\bm{s}}^{i}_{j}$ with
$\bm{s}^{i}_{j}\not\equiv_{\mathcal{O}}\top$ by an
$\hat{\bm{s}}\in\mathcal{N}_{\bm{s}^{i}_{j}}$, for $i,j$ such that
$(i,j)\not=(0,0)$—that is, the rule is not applied to $\bm{s}_{0}^{0}$;

  2. (b)

replace some pair $\hat{\bm{s}}^{i}_{j}\hat{\bm{s}}^{i}_{j+1}$ within block
$i$ by $\hat{\bm{s}}^{i}_{j}\emptyset^{b}\hat{\bm{s}}^{i}_{j+1}$;

  3. (c)

replace some $\hat{\bm{s}}_{j}^{i}$ with
$\bm{s}_{j}^{i}\not\equiv_{\mathcal{O}}\top$ by
$\hat{\bm{s}}_{j}^{i}\emptyset^{b}\hat{\bm{s}}_{j}^{i}$, where
$k_{i}>j>0$—that is, the rule is not applied to $\bm{s}_{j}^{i}$ if it is on
the border of its block;

  4. (d)

replace $\hat{\bm{s}}^{i}_{k_{i}}$ ($k_{i}>0$) by
$\hat{\bm{s}}\emptyset^{b}\hat{\bm{s}}^{i}_{k_{i}}$, for some
$\hat{\bm{s}}\in\mathcal{N}_{\bm{s}^{i}_{k_{i}}}$, or replace
$\hat{\bm{s}}^{i}_{0}$ ($k_{i}>0$) by
$\hat{\bm{s}}^{i}_{0}\emptyset^{b}\hat{\bm{s}}$, for some
$\hat{\bm{s}}\in\mathcal{N}_{\bm{s}^{i}_{0}}$;

  5. (e)

replace $\hat{\bm{s}}_{0}^{0}$ with
$\bm{s}^{0}_{0}\not\equiv_{\mathcal{O}}\top$ by
$\hat{\bm{s}}\emptyset^{b}\hat{\bm{s}}^{0}_{0}$, for
$\hat{\bm{s}}\in\mathcal{N}_{\bm{s}^{0}_{0}}$, if $k_{0}=0$, and by
$\hat{\bm{s}}_{0}^{0}\emptyset^{b}\hat{\bm{s}}_{0}^{0}$ if $k_{0}>0$.

If $k_{i}=0$, $i>0$, and $\bm{s}^{i}_{0}$ is meet-reducible wrt $\mathcal{O}$
within $\mathcal{Q}$, then we say that $\bm{s}^{i}_{0}$ is a _lone conjunct
wrt $\mathcal{O}$ within $\mathcal{Q}$_ in $\mathcal{D}$.

######  Lemma 6.

Assume $\mathcal{Q},\mathcal{O}$, and ${\bm{q}}$ are as above. Let $b$ exceed
the number of $\Diamond$ and $\bigcirc$ in ${\bm{q}}$, let ${\bm{q}}$ be in
normal form, and let $\mathcal{D}$ be $b$-normal without lone conjuncts wrt
$\mathcal{O}$ within $\mathcal{Q}$. If
$\mathcal{O},\mathcal{D}\models{\bm{q}}$ but
$\mathcal{O},\mathcal{D}^{\prime}\not\models{\bm{q}}$, for any
$\mathcal{D}^{\prime}$ obtained from $\mathcal{D}$ by applying any of the
rules $(a)$–$(e)$, then any root $\mathcal{O}$-homomorphim
$h\colon{\bm{q}}\rightarrow\mathcal{D}$ is a root $\mathcal{O}$-isomorphism.

###### Proof.

We assume that ${\bm{q}}$ is constructed using $\bm{r}_{j}^{i}\in\mathcal{Q}$
and $\mathcal{D}$ is constructed using $\bm{s}_{j}^{i}\in\mathcal{Q}$. Let
$\mathcal{O},\mathcal{D}\models{\bm{q}}$. Take a root
$\mathcal{O}$-homomorphism $h\colon{\bm{q}}\rightarrow\mathcal{D}$.

Suppose first that $h$ is not block surjective. Since $h(0)=0$, we find $i,j$
with $(i,j)\not=(0,0)$ such that the time point of $\hat{\bm{s}}_{j}^{i}$ is
not in the range of $h$. If $\hat{\bm{s}}_{j}^{i}$ is not on the border of its
block, that is $0<j<k_{i}$, then we obtain from $h$ a root
$\mathcal{O}$-homomorphism into the data instance $\mathcal{D}^{\prime}$
obtained from $\mathcal{D}$ by rule (b) and have derived a contradiction. If
$0=j$ or $k_{i}=j$, then we obtain from $h$ a root $\mathcal{O}$-homomorphism
into the data instance $\mathcal{D}^{\prime}$ obtained from $\mathcal{D}$ by
rule (a) applied to $\bm{s}^{i}_{j}$ and have derived a contradiction.

Assume next that $h$ is block surjective but not data surjective. Then we find
$\ell\in\textit{ran}(h)$ with $\hat{\bm{s}}^{i}_{j}$ such that
$\bm{s}^{i}_{j}\not\equiv_{\mathcal{O}}\top$ placed at $\ell$ such that
$\mathcal{O},\hat{\bm{s}}\models\bm{r}_{\ell}(a)$ for some
$\bm{s}\in\mathcal{N}_{\bm{s}^{i}_{j}}$. But then $h$ is a root
$\mathcal{O}$-homomorphism into the data instance $\mathcal{D}^{\prime}$
obtained from $\mathcal{D}$ by applying rule (a) to $\bm{s}^{i}_{j}$, that is,
replacing $\hat{\bm{s}}^{i}_{j}$ by $\hat{\bm{s}}$ with
$\bm{s}\in\mathcal{N}_{\bm{s}^{i}_{j}}$.

Suppose now that $h\colon{\bm{q}}\to\mathcal{D}$ is a block and data
surjective, $(t\leq t^{\prime})\in{\bm{q}}$ and $h(t)=h(t^{\prime})=\ell$ lies
in the $i$th block of $\mathcal{D}$. Then
$h^{-1}(\ell)=\\{t_{1},\dots,t_{k}\\}$ with $k\geq 2$ and $(t_{j}\leq
t_{j+1})\in{\bm{q}}$, $1\leq j<k$. Let $\bm{r}_{1},\ldots,\bm{r}_{k}$ be the
queries with $\bm{r}_{j}(t_{j})$ in ${\bm{q}}$. As ${\bm{q}}$ satisfies (n1)
and (n2), there is $j$ with $\bm{r}_{j}\not\equiv_{\mathcal{O}}\top$. Hence,
$\bm{s}^{i}_{j_{0}}\not\equiv_{\mathcal{O}}\top$ for the query
$\bm{s}^{i}_{j_{0}}$ with $\hat{\bm{s}}^{i}_{j_{0}}$ at $\ell$ in
$\mathcal{D}$. Moreover, by data surjectivity,
$\bm{r}_{1}\wedge_{\mathcal{O}}\cdots\wedge_{\mathcal{O}}\bm{r}_{k}\equiv_{\mathcal{O}}\bm{s}^{i}_{j_{0}}$.
Consider possible locations of $j_{0}$ in its block.

_Case_ 1: $j_{0}$ has both a left and a right neighbour in its block. Then
there is $\mathcal{D}^{\prime}$ obtained by (c)—i.e., by replacing
$\hat{\bm{s}}_{j_{0}}^{i}$ with
$\hat{\bm{s}}_{j_{0}}^{i}\emptyset^{b}\hat{\bm{s}}_{j_{0}}^{i}$—and a root
$\mathcal{O}$-homomorphism $h^{\prime}\colon{\bm{q}}\to\mathcal{D}^{\prime}$,
which ‘coincides’ with $h$ except that $h^{\prime}(t_{1})$ is the point with
the first $\hat{\bm{s}}_{j_{0}}^{i}$ and $h^{\prime}(t_{j})$, for
$j=2,\dots,k$, is the point with the second $\hat{\bm{s}}_{j_{0}}^{i}$.

_Case_ 2: $j_{0}$ has no neighbours in its block and $i\not=0$, so this block
is primitive and $\bm{s}^{i}_{j_{0}}$ is not equivalent to a conjunction of
queries as $\mathcal{D}$ has no lone conjuncts by our assumption. Observe that
the blocks of $t_{1},\ldots,t_{k}$ are all different and primitive. As
$\bm{s}^{i}_{j_{0}}$ is not equivalent to a conjunction of queries, we have

$\bm{r}_{1}\equiv_{\mathcal{O}}\cdots\equiv_{\mathcal{O}}\bm{r}_{k}\equiv_{\mathcal{O}}\bm{s}^{i}_{j_{0}}.$

However, $\bm{r}_{j}\not\equiv_{\mathcal{O}}\bm{r}_{j+1}$ by (n3) and (n4).
Thus, Case 2 cannot happen.

_Case_ 3: $j_{0}$ has a left neighbour in its block but no right neighbour.
Then $\bm{r}_{1}\not\models_{\mathcal{O}}\bm{r}_{2}$ in view of (n3), and so
$\bm{r}_{1}\not\models_{\mathcal{O}}\bm{s}^{i}_{j_{0}}$. As
$\bm{s}^{i}_{j_{0}}\models_{\mathcal{O}}\bm{r}_{1}$, there is
$\hat{\bm{s}}\in\mathcal{N}_{\bm{s}^{i}_{j_{0}}}$ with
$\mathcal{O},\hat{\bm{s}}\not\models_{\mathcal{O}}\bm{r}_{1}$. Let
$\mathcal{D}^{\prime}$ be obtained by the first part of (d) by replacing
$\hat{\bm{s}}^{i}_{j_{0}}$ with
$\hat{\bm{s}}\emptyset^{b}\hat{\bm{s}}^{i}_{j_{0}}$. Then there is a root
$\mathcal{O}$-homomorphism $h^{\prime}\colon{\bm{q}}\to\mathcal{D}^{\prime}$
that sends $t_{1}$ to the point of $\bm{s}$ and the remaining $t_{j}$ to the
point of $\bm{s}^{i}_{j_{0}}$.

_Case_ 4: $j_{0}$ has a right neighbour in its block, $i\neq 0$, and it has no
left neighbour. This case is dual to Case 3 and we use the second part of (d).

_Case_ 5: $i=0$ and $j_{0}=0$. If block $0$ is primitive, then all of the
$\bm{r}_{i}(t_{i})$ are primitive blocks in ${\bm{q}}$. By (n3),
$\bm{r}_{1}\not\models_{\mathcal{O}}\bm{r}_{2}$, and so
$\bm{r}_{1}\not\models_{\mathcal{O}}\bm{s}^{i}_{j_{0}}$. Take
$\hat{\bm{s}}\in\mathcal{N}_{\bm{s}^{i}_{j_{0}}}$. By the first part of (e),
we have $\mathcal{D}^{\prime}$ obtained by replacing $\hat{\bm{s}}_{0}^{0}$
with $\hat{\bm{s}}\emptyset^{b}\hat{\bm{s}}^{0}_{0}$. Then there is a root
$\mathcal{O}$-homomorphism $h^{\prime}\colon{\bm{q}}\to\mathcal{D}^{\prime}$
that sends $t_{1}$ to the point of $\bm{s}$ and the remaining $t_{j}$ to the
point of $\bm{s}^{0}_{0}$.

Finally, if block $0$ is not primitive, the second part of (e) gives
$\mathcal{D}^{\prime}$ by replacing $\hat{\bm{s}}_{0}^{0}$ in $\mathcal{D}$
with $\hat{\bm{s}}_{0}^{0}\emptyset^{b}\hat{\bm{s}}_{0}^{0}$. We obtain a root
$\mathcal{O}$-homomorphism from ${\bm{q}}$ to $\mathcal{D}^{\prime}$ by
sending $t_{1}$ to the first $\hat{\bm{s}}_{0}^{0}$ and the remaining $t_{j}$
to the second $\hat{\bm{s}}_{0}^{0}$. ∎

We can now prove Theorem 15. Suppose an ontology $\mathcal{O}$ admits
singular+ characterisations within a class of domain queries $\mathcal{Q}$.
Let
${\bm{q}}\in\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
in normal form wrt $\mathcal{O}$ take the form (9) with ${\bm{q}}_{i}$ of the
form (10). We define an example set $E=(E^{+},E^{-})$ characterising
${\bm{q}}$ under the assumption that ${\bm{q}}$ has no lone conjuncts wrt
$\mathcal{O}$. Let $b$ be the number of $\bigcirc$ and $\Diamond$ in
${\bm{q}}$ plus 1. For every block ${\bm{q}}_{i}$ of the form (10), let
$\hat{{\bm{q}}}_{i}$ be the temporal data instance

$\displaystyle\hat{{\bm{q}}}_{i}=\hat{\bm{r}}_{0}^{i}\hat{\bm{r}}_{1}^{i}\dots\hat{\bm{r}}_{k_{i}}^{i}.$

For any two blocks ${\bm{q}}_{i},{\bm{q}}_{i+1}$ such that
$\bm{r}_{k_{i}}^{i}$ and $\bm{r}_{0}^{i+1}$ are $\mathcal{O}$-compatible, we
take the temporal data instance

$\displaystyle\hat{{\bm{q}}}_{i}\Join\hat{{\bm{q}}}_{i+1}=\hat{\bm{r}}_{0}^{i}\dots\hat{\bm{r}}_{k_{i-1}}^{i}\widehat{\bm{r}_{k_{i}}^{i}\wedge\bm{r}_{0}^{i+1}}\hat{\bm{r}}_{1}^{i+1}\dots\hat{\bm{r}}_{k_{i+1}}^{i+1}.$

Now, the set $E^{+}$ contains the data instances given by

  * –

$\mathcal{D}_{b}=\bar{{\bm{q}}}_{0}\emptyset^{b}\dots\bar{{\bm{q}}}_{i}\emptyset^{b}\bar{{\bm{q}}}_{i+1}\dots\emptyset^{b}\bar{{\bm{q}}}_{n}$,

  * –

$\mathcal{D}_{i}=\bar{{\bm{q}}}_{0}\emptyset^{b}\dots(\bar{{\bm{q}}}_{i}\\!\Join\\!\bar{{\bm{q}}}_{i+1})\dots\emptyset^{b}\bar{{\bm{q}}}_{n}$
if $\mathcal{R}_{i+1}$ is $\leq$,

  * –

$\mathcal{D}_{i}=\bar{{\bm{q}}}_{0}\emptyset^{b}\dots\bar{{\bm{q}}}_{i}\emptyset^{n_{i+1}}\bar{{\bm{q}}}_{i+1}\dots\emptyset^{b}\bar{{\bm{q}}}_{n}$
otherwise.

Here, $\emptyset^{b}$ is a sequence of $b$-many $\emptyset$ and similarly for
$\emptyset^{n_{i+1}}$. The set $E^{-}$ contains all data instances of the form

  * –

$\mathcal{D}_{i}^{-}=\bar{{\bm{q}}}_{0}\emptyset^{b}\dots\bar{{\bm{q}}}_{i}\emptyset^{n_{i+1}-1}\bar{{\bm{q}}}_{i+1}\dots\emptyset^{b}\bar{{\bm{q}}}_{n}$
if $n_{i+1}>1$,

  * –

$\mathcal{D}^{-}_{i}=\bar{{\bm{q}}}_{0}\emptyset^{b}\dots\bar{{\bm{q}}}_{i}\\!\Join\\!\bar{{\bm{q}}}_{i+1}\dots\emptyset^{b}\bar{{\bm{q}}}_{n}$
if $\mathcal{R}_{i+1}$ is a single $<$ and $\bm{r}_{k_{i}}^{i}$ and
$\bm{r}_{0}^{i+1}$ are $\mathcal{O}$-compatible,

  * –

the data instances obtained from $\mathcal{D}_{b}$ by applying to it each of
the rules (a)–(e) in all possible ways exactly once.

We show that $E$ characterises ${\bm{q}}$. Clearly,
$\mathcal{O},\mathcal{D}\models{\bm{q}}$ for all $\mathcal{D}\in E^{+}$. To
establish $\mathcal{O},\mathcal{D}\not\models{\bm{q}}$ for $\mathcal{D}\in
E^{-}$, we need the following:

Claim 1. $(i)$ _There is only one root $\mathcal{O}$-homomorphism
$h\colon{\bm{q}}\to\mathcal{D}_{b}$, and it maps isomorphically each
$\textit{var}({\bm{q}}_{i})$ onto $I(\bar{{\bm{q}}}_{i})$._

$(ii)$ _$\mathcal{O},\mathcal{D}^{-}_{i}\not\models{\bm{q}}$ , for any
$\mathcal{R}_{i}$ different from $\leq$._

$(iii)$ _If $\mathcal{D}_{b}^{\prime}$ is obtained from $\mathcal{D}_{b}$ by
replacing some $\bar{{\bm{q}}}_{i}$ with $\bar{{\bm{q}}}^{\prime}_{i}$ such
that $\mathcal{O},\bar{{\bm{q}}}^{\prime}_{i},\ell\not\models{\bm{q}}_{i}$ for
any $\ell\leq\max(\bar{{\bm{q}}}^{\prime}_{i})$, then
$\mathcal{O},\mathcal{D}_{b}^{\prime}\not\models{\bm{q}}$. In particular,
$\mathcal{O},\mathcal{D}\not\models{\bm{q}}$, for all $\mathcal{D}\in E^{-}$._

_Proof of claim._ $(i)$ Let $h$ be a root $\mathcal{O}$-homomorphism. As
${\bm{q}}$ is in normal form and the gaps between $\bar{{\bm{q}}}_{i}$ and
$\bar{{\bm{q}}}_{i+1}$ are not shorter than any block in ${\bm{q}}$, every
$\textit{var}({\bm{q}}_{i})$, where ${\bm{q}}_{i}$ is a block in ${\bm{q}}$,
is mapped by $h$ to a single $I(\bar{{\bm{q}}}_{j})$, where
$\bar{{\bm{q}}}_{j}$ is a block of $D_{b}$. Hence we can define a function
$f\colon[0,n]\rightarrow[0,n]$ by setting $f(i)=j$ if
$f(\textit{var}({\bm{q}}_{i}))\subseteq I(\bar{{\bm{q}}}_{j})$. Observe that
$f(0)=0$ and $i<j$ implies $f(i)\leq f(j)$. It also follows from the
definition of the normal form that if $f(i)=i$, then $h$ isomorphically maps
$\textit{var}({\bm{q}}_{i})$ onto $I(\bar{{\bm{q}}}_{i})$ and $f(i-1)<i$ and
$f(i+1)>i$ (observe that here ${\bf(n3)}$ and ${\bf(n4)}$ are required as they
prohibit that $\textit{var}({\bm{q}}_{i})$ and $\textit{var}({\bm{q}}_{i+1})$
are merged if $R_{i+1}=\leq$ and $\textit{var}({\bm{q}}_{i})$ or
$\textit{var}({\bm{q}}_{i+1})$ are a singleton). It remains to show that
$f(i)=i$ for all $i$.

We first observe that $f(1)\geq 1$ and $f(j)=j$, for $j=\max\\{i\mid f(i)\geq
i\\}$, from which again $f(j-1)<j$ and $f(j+1)>j$. Then we can proceed in the
same way inductively by considering $h$ and $f$ restricted to the smaller
intervals $[j,n]$ and $[0,j]$.

$(ii)$ Suppose $\mathcal{R}_{i}$ is not $\leq$ but there is a root
$\mathcal{O}$-homomorphism $h\colon{\bm{q}}\to\mathcal{D}^{-}_{i}$. Consider
the location of $h(s^{i}_{0})=\ell$. One can show similarly to $(i)$ that
$\ell\in I(\bar{{\bm{q}}}_{j})$ for some $j\geq i$. Since
$\bm{r}^{i+1}_{k_{i+1}}\not\equiv_{\mathcal{O}}\top$ and by the construction
of $\mathcal{D}^{-}_{i}$, $h(s^{i+1}_{0})$ lies in some
$I(\bar{{\bm{q}}}_{j})$ with $j>i+1$. But then there is a root
$\mathcal{O}$-homomorphism $h^{\prime}\colon{\bm{q}}\to\mathcal{D}_{b}$
different from the one in $(i)$, which is impossible.

$(iii)$ is proved analogously. This completes the proof of the claim.

Now assume that ${\bm{q}}^{\prime}\in\mathcal{Q}$ in normal form is given and
${\bm{q}}^{\prime}\not\equiv_{\mathcal{O}}{\bm{q}}$. We have to show that
${\bm{q}}^{\prime}$ does not fit $E$. If
$\mathcal{O},\mathcal{D}_{b}\not\models{\bm{q}}^{\prime}$, we are done as
$\mathcal{D}_{b}\in E^{+}$. Otherwise, let $h$ be a root
$\mathcal{O}$-homomorphism witnessing
$\mathcal{O},\mathcal{D}_{b}\models{\bm{q}}^{\prime}$. If $h$ is not a root
$\mathcal{O}$-isomorphism, then by Lemma 6, there exists a data instance
$\mathcal{D}$ obtained from $\mathcal{D}_{b}$ by applying one of the rules
(a)–(e) such that $\mathcal{O},\mathcal{D}\models{\bm{q}}^{\prime}$. As
$\mathcal{D}\in E^{-}$, we are done.

So suppose $h\colon{\bm{q}}^{\prime}\to\mathcal{D}_{b}$ is a root
$\mathcal{O}$-isomorphism. Then the difference between ${\bm{q}}^{\prime}$ and
${\bm{q}}$ can only be in the sequences of $\Diamond$ and $\Diamond_{\\!r}$
between blocks. To be more precise, ${\bm{q}}$ is of the form (9),

$\displaystyle{\bm{q}}^{\prime}={\bm{q}}_{0}\mathcal{R}^{\prime}_{1}{\bm{q}}_{1}\dots\mathcal{R}^{\prime}_{n}{\bm{q}}_{n}$
(12)

and $\mathcal{R}_{i}\neq\mathcal{R}^{\prime}_{i}$ for some $i$. Four cases are
possible:

  * –

$\mathcal{R}_{i}=(r_{0}\leq r_{1})$ and
$\mathcal{R}_{i}^{\prime}=(s_{0}<s_{1})\dots(s_{l-1}<s_{l})$, for $l\geq 1$.
In this case, $\mathcal{O},\mathcal{D}_{i}\not\models{\bm{q}}^{\prime}$, for
$\mathcal{D}_{i}\in E^{+}$.

  * –

$\mathcal{R}_{i}=(r_{0}<r_{1})\dots(r_{k-1}<r_{k})$,
$\mathcal{R}_{i}^{\prime}=(s_{0}<s_{1})\dots$ $(s_{l-1}<s_{l})$, for $l>k$.
Then again $\mathcal{O},\mathcal{D}_{i}\not\models{\bm{q}}^{\prime}$.

  * –

$\mathcal{R}_{i}=(r_{0}<r_{1})\dots(r_{k-1}<r_{k})$,
$\mathcal{R}_{i}^{\prime}=(s_{0}\leq s_{1})$, for $k\geq 1$. In this case
$\mathcal{O},\mathcal{D}_{i}^{-}\models{\bm{q}}^{\prime}$, for
$\mathcal{D}^{-}_{i}\in E^{-}$. (Note that the compatibility condition is
satisfied as ${\bm{q}}^{\prime}$ is in normal form.)

  * –

$\mathcal{R}_{i}=(r_{0}<r_{1})\dots(r_{k-1}<r_{k})$ and
$\mathcal{R}_{i}^{\prime}=(s_{0}<s_{1})\dots$ $(s_{l-1}<s_{l})$, for $l<k$.
Then again $\mathcal{O},\mathcal{D}_{i}^{-}\models{\bm{q}}^{\prime}$.

We now show the converse direction in Theorem 15 $(i)$. Suppose ${\bm{q}}$ in
normal form (9) does contain a lone conjunct ${\bm{q}}_{i}=\bm{r}$ wrt
$\mathcal{O}$ within $\mathcal{Q}$. Let $\bm{r}^{-}$ be the last query of the
block ${\bm{q}}_{i-1}$ and let $\bm{r}^{+}$ be the first query of the block
${\bm{q}}_{i+1}$.

Now let $\bm{r}\equiv_{\mathcal{O}}\bm{r}_{1}\wedge\bm{r}_{2}$ and
$\bm{r}_{i}\not\models_{\mathcal{O}}\bm{r}$, $i=1,2$. Observe that, for
$\bm{s}\in\\{\bm{r}^{-},\bm{r}^{+}\\}$,

  * •

$\bm{s}$ and $\bm{r}_{i}$ are compatible w.r.t. $\mathcal{O}$ if $\bm{r}^{-}$
and $\bm{r}$ are compatible w.r.t $\mathcal{O}$;

  * •

if $\bm{s}\not\models_{\mathcal{O}}\bm{r}$, then
$\bm{s}\not\models_{\mathcal{O}}\bm{r}_{1}$ or
$\bm{s}\not\models_{\mathcal{O}}\bm{r}_{2}$.

Hence one of the queries $\bm{s}^{\prime}_{1}$ or $\bm{s}^{\prime\prime}_{1}$
below is in normal form:

$\displaystyle\bm{s}^{\prime}_{1}={\bm{q}}_{0}\mathcal{R}_{1}\dots\mathcal{R}_{i}\bm{s}_{1}(\leq)\bm{s}_{2}\mathcal{R}_{i+1}\dots\mathcal{R}_{n}{\bm{q}}_{n},$
$\displaystyle\bm{s}^{\prime}_{2}={\bm{q}}_{0}\mathcal{R}_{1}\dots\mathcal{R}_{i}\bm{s}_{1}(\leq)\bm{s}_{2}(\leq)\bm{s}_{1}\mathcal{R}_{i+1}\dots\mathcal{R}_{n}{\bm{q}}_{n},$

where $\\{\bm{s}_{1},\bm{s}_{2}\\}=\\{r_{1},\bm{r}_{2}\\}$. Pick one of
$\bm{s}^{\prime}_{1}$ and $\bm{s}^{\prime}_{2}$, which is in normal form, and
denote it by $\bm{s}^{\prime}_{1}$. For $n\geq 2$, let $\bm{s}^{\prime}_{n}$
be the query obtained from $\bm{s}^{\prime}_{1}$ by duplicating $n$ times the
part $\bm{s}_{1}(\leq)\bm{s}_{2}$ in $\bm{s}^{\prime}_{1}$ and inserting
$\leq$ between the copies. It is readily seen that $\bm{s}^{\prime}_{n}$ is in
normal form. Clearly, ${\bm{q}}\models_{\mathcal{O}}\bm{s}^{\prime}_{n}$ and,
similarly to the proof of Claim 1, one can show that
$\bm{s}^{\prime}_{n}\not\models_{\mathcal{O}}{\bm{q}}$, for any $n\geq 1$.

Suppose $E=(E^{+},E^{-})$ characterises ${\bm{q}}$ and
$n=\max\\{\max(\mathcal{D})\mid\mathcal{D}\in E^{-}\\}+1$. Then there exists
$\mathcal{D}\in E^{-}$ with
$\mathcal{O},\mathcal{D}\models\bm{s}^{\prime}_{n}$, so we have a root
$\mathcal{O}$-homomorphism $h\colon\bm{s}^{\prime}_{n}\to\mathcal{D}$. By the
pigeonhole principle, $h$ maps some variables of the queries
$\bm{s}_{1},\bm{s}_{2}$ in $\bm{s}^{\prime}_{n}$ to the same point in
$\mathcal{D}$. But then $h$ can be readily modified to obtain a root
$\mathcal{O}$-homomorphism $h^{\prime}\colon{\bm{q}}\to\mathcal{D}$, which is
a contradiction. This finishes the proof of $(i)$.

$(ii)$ follows from the proof of $(i)$ as $(E^{+},E^{-})$ is of polynomial
size if the singular+characterisations are of polynomial size.

$(iii)$ We aim to characterise ${\bm{q}}$ in normal form (9), which may
contain lone conjuncts wrt $\mathcal{O}$ within $\mathcal{Q}$ in the class of
queries from
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{Q})$
of temporal depth at most $n=\textit{tdp}({\bm{q}})$. We first observe a
variation of Lemma 6. Extend the rules (a)–(e) by the following rule: if
$\hat{\bm{s}}$ is a block in $\mathcal{D}$ with $\bm{s}$ a lone conjunct in
$\mathcal{D}$, then let
$\mathcal{N}_{{\bm{q}}}=\\{\bm{s}_{1},\dots,\bm{s}_{k}\\}$ with
$\bm{s}_{i}\not\equiv_{\mathcal{O}}\bm{s}_{j}$, for $i\neq j$, and

(fn)

replace $\bm{s}$ with
$(\bm{s}_{1}\emptyset^{b}\cdots\emptyset^{b}\bm{s}_{k})^{n}$.

By Lemma 3 $(ii)$, $|\mathcal{N}_{{\bm{q}}}|\geq 2$. Now Lemma 6 still holds
if we admit lone conjuncts in $\mathcal{D}$ but only consider ${\bm{q}}$ with
at most $n$ blocks and add rule (fn) to (a)–(e). To see this, one only has to
modify the argument for Case 2 in a straightforward way. With the above
modification of Lemma 6, we continue as follows. The set $E^{+}$ of positive
examples is defined as before. The set $E^{-}$ of negative examples is defined
by adding to the set $E^{-}$ defined under $(i)$ the results of applying (fn)
to $\mathcal{D}_{b}$ in all possible ways exactly once.

For the proof that $(E^{+},E^{-})$ characterises ${\bm{q}}$ within the class
of queries of temporal depth at most $n$, observe that
$\mathcal{O},\mathcal{D}^{\prime}\not\models{\bm{q}}$ for the data instance
$\mathcal{D}^{\prime}$ obtained from $\mathcal{D}_{b}$ by applying (fn).

$(iv)$ Assume
${\bm{q}}\in\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}(\mathcal{Q})$
is given. The proof of $(i)$ shows that $(E^{+},E^{-})$, defined in the same
way as in $(i)$, characterises ${\bm{q}}$ wrt $\mathcal{O}$ within
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}(\mathcal{Q})$
even if ${\bm{q}}$ contains lone conjuncts: the proof of Lemma 6 becomes much
simpler as any block and type surjective root $\mathcal{O}$-homomorphism $h$
is now a root $\mathcal{O}$-isomorphism. Note that therefore rules (c), (d),
and (e) are not needed. This completes the proof of Theorem 15.

As an immediate consequence of Lemma 1 and Theorems 9, 12 and 15 we obtain:

######  Theorem 16.

$(i)$ For any $\textsl{DL-Lite}_{\mathcal{H}}$ or $\textsl{DL-
Lite}^{-}_{\mathcal{F}}$ ontology $\mathcal{O}$,

  * •

a 2D-query
${\bm{q}}\in\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{ELI})$
is uniquely characterisable—in fact, polynomially characterisable—wrt
$\mathcal{O}$ within
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{ELI})$iff
${\bm{q}}$ is safe wrt $\mathcal{O}$;

  * •

$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\mathcal{ELI})$
is polynomially characterisable wrt $\mathcal{O}$ for bounded temporal depth;

  * •

$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}(\mathcal{Q})$
is polynomially characterisable wrt $\mathcal{O}$.

$(ii)$ Let $\sigma$ be a signature. Every $\sigma$-ELIQ ${\bm{q}}$ is uniquely
characterisable wrt any $\mathcal{ALCHI}$-ontology $\mathcal{O}$ in $\sigma$
within the class of $\sigma$-ELIQs.

##  5
$\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$

Let $\mathcal{Q}$ be a domain query language and $\sigma$ a finite signature
of predicate symbols. Then $\mathcal{Q}^{\sigma}$ denotes the set of queries
in $\mathcal{Q}$ that only use symbols in $\sigma$. We remind the reader that
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$
is the class of temporal path queries of the form

${\bm{q}}=\bm{r}_{0}\land(\bm{l}_{1}\mathbin{\mathsf{U}}(\bm{r}_{1}\land(\bm{l}_{2}\mathbin{\mathsf{U}}(\dots(\bm{l}_{n}\mathbin{\mathsf{U}}\bm{r}_{n})\dots)))),$
(13)

where each $\bm{r}_{i}\in\mathcal{Q}^{\sigma}$ and each $\bm{l}_{i}$ is either
in $\mathcal{Q}^{\sigma}$ or $\bot$ (recall that ${\bm{q}}$, $\bm{r}_{i}$,
$\bm{l}_{i}$ have a single answer domain variable $x$ and that we evaluate
${\bm{q}}$ at time point $0$). Let $\mathcal{O}$ be an ontology. Then the
class
$\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$
comprises _$\mathcal{O}$ -peerless queries_ in
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$,
in which $\bm{r}_{i}\not\models_{\mathcal{O}}\bm{l}_{i}$ and
$\bm{l}_{i}\not\models_{\mathcal{O}}\bm{r}_{i}$, for all $i\leq n$. In what
follows we write $\mathcal{O},\mathcal{D}\models{\bm{q}}$ instead of
$\mathcal{O},\mathcal{D},0,a\models{\bm{q}}$ when $a$ is clear from context.
We also write $\mathcal{D}\models{\bm{q}}$ instead of
$\emptyset,\mathcal{D}\models{\bm{q}}$ (that is, for the empty ontology).

We illustrate our approach to characterising
$\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$-queries
by a simple example.

######  Example 7.

Suppose ${\bm{q}}={\raisebox{1.07639pt}{\text{$\bigcirc$}}}A$ and
$\sigma=\\{A,B\\}$. Then $E=(E^{+},E^{-})$ with $E^{+}=\\{\emptyset\\{A\\}\\}$
and $E^{-}=\\{\emptyset\\{B\\}\\{A\\}\\}$ uniquely characterises ${\bm{q}}$
within the class
$\textsl{LTL}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{P}^{\sigma})$.
Indeed, if
${\bm{q}}^{\prime}=\bm{r}_{0}\land(\bm{l}_{1}\mathbin{\mathsf{U}}(\bm{r}_{1}\land(\bm{l}_{2}\mathbin{\mathsf{U}}(\dots(\bm{l}_{n}\mathbin{\mathsf{U}}\bm{r}_{n})\dots))))\in\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{P}^{\sigma})$
fits $E$, then ${\bm{q}}^{\prime}\equiv\bm{l}_{1}\mathbin{\mathsf{U}}A$, for
some $\bm{l}_{1}$. Because of $E^{-}$, $\bm{l}_{1}\neq B$. So
$\bm{l}_{1}=\bot$ or $\bm{l}_{1}=A$. In either of these cases,
${\bm{q}}^{\prime}\equiv{\raisebox{1.07639pt}{\text{$\bigcirc$}}}A$.

A ‘systematic way’ of constructing $E^{-}$ for
${\bm{q}}={\raisebox{1.07639pt}{\text{$\bigcirc$}}}A$ would be to include in
it every $\emptyset\bm{l}\\{A\\}$ with
$(\bm{l},a)\in\mathcal{S}(\\{A\\})=\\{(\\{B(a)\\},a)\\}$. On the other hand,
we cannot use the set
$\\{(\hat{\mathbf{m}},a)\mid\mathbf{m}\in\mathcal{F}_{A(x)}\\}=\\{(\top,a)\\}$
in place of $\mathcal{S}(\\{A\\})$. Intuitively, this is because the set of
$\\{\bm{l}_{i}\mid\emptyset\bm{l}_{i}\\{A\\}\in E^{-}\\}$ must be such that,
for every $\bm{l}$ in signature $\sigma$ with $\bm{l}\not\models A$, we must
have that some $\bm{l}_{i}\models\bm{l}$. However, the frontier
$\mathcal{F}_{A}$ guarantees the above only for every $\bm{l}$ satisfying
$A\models\bm{l}$.

In this section, we aim to prove the following general theorem:

######  Theorem 17.

Suppose $\mathcal{Q}$ is a class of domain queries, $\sigma$ a signature,
$\mathcal{L}$ has general split-partners within $\mathcal{Q}^{\sigma}$, and
$\mathcal{O}$ is a $\sigma$-ontology in $\mathcal{L}$ that admits containment
reduction. Then every query
${\bm{q}}\in\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$
is uniquely characterisable wrt $\mathcal{O}$ within
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$.
If a split-partner for any set $Q$ of $\mathcal{Q}^{\sigma}$ queries wrt
$\mathcal{O}$ within $\mathcal{Q}^{\sigma}$ is exponential, then there is an
exponential-size unique characterisation of ${\bm{q}}$ wrt $\mathcal{O}$. If a
split-partner of any set $Q$ as above is polynomial and a split-partner
$\mathcal{S}_{\bot}$ of $\bot(x)$ within $\mathcal{Q}^{\sigma}$ wrt
$\mathcal{O}$ is a singleton, then there is a polynomial-size unique
characterisation of ${\bm{q}}$ wrt $\mathcal{O}$.

The proof is by reduction to the propositional case without ontology. We
remind the reader of the result proved in [22]:

######  Theorem 18 ([22]).

$\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{P}^{\sigma})$
is polynomially characterisable within
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{P}^{\sigma})$
wrt the empty ontology with the characterisation given below:

Let $\mathbf{s}\in\mathcal{P}^{\sigma}\cup\\{\bot\\}$. We treat each such
$\mathbf{s}\neq\bot$ as a set of its conjuncts and define
$\bar{\mathbf{s}}=\\{A(a)\mid A(x)\in\mathbf{s}\\}$. For $\mathbf{s}=\bot$, we
set $\bar{\mathbf{s}}=\varepsilon$, where $\varepsilon$ is the empty word in
the sense that $\varepsilon\mathcal{D}=\mathcal{D}$, for any data instance
$\mathcal{D}$, and $\varepsilon\varepsilon=\varepsilon$. Consider
${\bm{q}}\in\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{P}^{\sigma})$
of the form (13). Then ${\bm{q}}$ is uniquely characterised within
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{P}^{\sigma})$
by the example set $E=(E^{+},E^{-})$, where $E^{+}$ contains all data
instances of the following forms:

$(\mathfrak{p}_{0})$

$\bar{\bm{r}}_{0}\dots\bar{\bm{r}}_{n}$,

$(\mathfrak{p}_{1})$

$\bar{\bm{r}}_{0}\dots\bar{\bm{r}}_{i-1}\bar{\bm{l}}_{i}\bar{\bm{r}}_{i}\dots\bar{\bm{r}}_{n}=\mathcal{D}^{i}_{\bm{q}}$,

$(\mathfrak{p}_{2})$

$\bar{\bm{r}}_{0}\dots\bar{\bm{r}}_{i-1}\bar{\bm{l}}_{i}^{k}\bar{\bm{r}}_{i}\dots\bar{\bm{r}}_{j-1}\bar{\bm{l}}_{j}\bar{\bm{r}}_{j}\dots\bar{\bm{r}}_{n}=\mathcal{D}^{j}_{i,k}$,
for $i<j$, and $k=1,2$;

and $E^{-}$ contains all instances $\mathcal{D}$ with
$\mathcal{D}\not\models{\bm{q}}$ of the forms:

$(\mathfrak{n}_{0})$

$\bar{\sigma}^{n}$ and
$\bar{\sigma}^{n-i}\overline{\sigma\setminus\\{A\\}}\bar{\sigma}^{i}$, for
$A(x)\in\bm{r}_{i}$,

$(\mathfrak{n}_{1})$

$\bar{\bm{r}}_{0}\dots\bar{\bm{r}}_{i-1}\overline{\sigma\setminus
X}\bar{\bm{r}}_{i}\dots\bar{\bm{r}}_{n}$, for $X=\\{A,B\\}$ with
$A(x)\in\bm{l}_{i}$, $B(x)\in\bm{r}_{i}$, $X=\emptyset$, and $X=\\{A\\}$ with
$A(x)\in\bm{l}_{i}$,

$(\mathfrak{n}_{2})$

for all $i$ and $A(x)\in\bm{l}_{i}\cup\\{\bot(x)\\}$, _some_ data instance

$\mathcal{D}^{i}_{\\!A}=\bar{\bm{r}}_{0}\dots\bar{\bm{r}}_{i-1}(\overline{\sigma\setminus\\{A\\}})\bar{\bm{r}}_{i}\bar{\bm{l}}_{i+1}^{k_{i+1}}\dots\bar{\bm{l}}_{n}^{k_{n}}\bar{\bm{r}}_{n},$
(14)

if any, such that $\max(\mathcal{D}^{i}_{\\!A})\leq(n+1)^{2}$ and
$\mathcal{D}^{i}_{\\!A}\not\models{\bm{q}}^{\dagger}$ for ${\bm{q}}^{\dagger}$
obtained from ${\bm{q}}$ by replacing $\bm{l}_{j}$, for all $j\leq i$, with
$\bot$. Note that $\mathcal{D}^{i}_{\\!A}\not\models{\bm{q}}$ for peerless
${\bm{q}}$.

Returning to proof of Theorem 17, assume a signature $\sigma$, an ontology
$\mathcal{O}$ in $\sigma$, and a
${\bm{q}}\in\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$
of the form (13) are given. We may assume that
$\bm{r}_{n}\not\equiv_{\mathcal{O}}\top$. We obtain the set $E^{+}$ of
positive examples as

$(\mathfrak{p}_{0}^{\prime})$

$\hat{\bm{r}}_{0}\dots\hat{\bm{r}}_{n}$,

$(\mathfrak{p}_{1}^{\prime})$

$\hat{\bm{r}}_{0}\dots\hat{\bm{r}}_{i-1}\hat{\bm{l}}_{i}\\_i\dots\hat{\bm{r}}_{n}=\mathcal{D}^{i}_{\bm{q}}$,

$(\mathfrak{p}_{2})^{\prime}$

$\hat{\bm{r}}_{0}\dots\hat{\bm{r}}_{i-1}\hat{\bm{l}}_{i}^{k}\hat{\bm{r}}_{i}\dots\hat{\bm{r}}_{j-1}\hat{\bm{l}}_{j}\hat{\bm{r}}_{j}\dots\hat{\bm{r}}_{n}=\mathcal{D}^{j}_{i,k}$,
for $i<j$ and $k=1,2$.

We obtain the set $E^{-}$ of negative examples by taking the following data
instances $\mathcal{D}$ whenever $\mathcal{D}\not\models{\bm{q}}$:

$(\mathfrak{n}_{0}^{\prime})$

$\mathcal{A}_{1},\ldots,\mathcal{A}_{n}$ and
$\mathcal{A}_{1},\ldots,\mathcal{A}_{n-i},\mathcal{A},\mathcal{A}_{n-i+1},\ldots,\mathcal{A}_{n}$,
for $(\mathcal{A},a)\in\mathcal{S}(\\{\bm{r}_{i}\\})$ and
$(\mathcal{A}_{1},a),\ldots,(\mathcal{A}_{n},a)\in\mathcal{S}_{\bot}$;

$(\mathfrak{n}_{1}^{\prime})$

$\mathcal{D}=\hat{\bm{r}}_{0}\dots\hat{\bm{r}}_{i-1}\mathcal{A}\hat{\bm{r}}_{i}\dots\hat{\bm{r}}_{n}$,
where
$(\mathcal{A},a)\in\mathcal{S}(\\{\bm{l}_{i},\bm{r}_{i}\\})\cup\mathcal{S}(\\{\bm{l}_{i}\\})\cup\mathcal{S}_{\bot}$;

$(\mathfrak{n}_{2}^{\prime})$

for all $i$ and
$(\mathcal{A},a)\in\mathcal{S}(\\{\bm{l}_{i},\bm{r}_{i}\\})\cup\mathcal{S}(\\{\bm{l}_{i}\\})\cup\mathcal{S}_{\bot}$,
_some_ data instance

$\mathcal{D}^{i}_{\mathcal{A}}=\hat{\bm{r}}_{0}\dots\hat{\bm{r}}_{i-1}\mathcal{A}\hat{\bm{r}}_{i}\hat{\bm{l}}_{i+1}^{k_{i+1}}\hat{\bm{r}}_{i+1}\dots\hat{\bm{l}}_{n}^{k_{n}}\bm{r}_{n},$

if any, such that $\max(\mathcal{D}^{i}_{\mathcal{A}})\leq(n+1)^{2}$ and
$\mathcal{D}^{i}_{\mathcal{A}}\not\models{\bm{q}}^{\dagger}$ for
${\bm{q}}^{\dagger}$ obtained from ${\bm{q}}$ by replacing all $\bm{l}_{j}$,
for $j\leq i$, with $\bot$.

We show that ${\bm{q}}$ is uniquely characterised by the example set
$E=(E^{+},E^{-})$ wrt $\mathcal{O}$ within
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$.
Consider any query

${\bm{q}}^{\prime}=\bm{r}^{\prime}_{0}\land(\bm{l}^{\prime}_{1}\mathbin{\mathsf{U}}(\bm{r}^{\prime}_{1}\land(\bm{l}^{\prime}_{2}\mathbin{\mathsf{U}}(\dots(\bm{l}^{\prime}_{m}\mathbin{\mathsf{U}}\bm{r}^{\prime}_{m})\dots))))$

in
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{Q}^{\sigma})$
such that ${\bm{q}}^{\prime}\not\equiv_{\mathcal{O}}{\bm{q}}$. We can again
assume that $\bm{r}_{m}^{\prime}\not\equiv_{\mathcal{O}}\top$. Thus, in what
follows we can safely ignore what the ontology $\mathcal{O}$ entails after the
timepoint $\max\mathcal{D}$ for any database $\mathcal{D}$ as these points do
not contribute to entailment of ${\bm{q}}$ or ${\bm{q}}^{\prime}$. In order to
show that ${\bm{q}}$ fits $E$ and ${\bm{q}}^{\prime}$ does not fit $E$, we
need a few definitions.

We define a map $f$ that reduces the 2D case to the 1D case. Consider the
alphabet

$\Gamma=\\{\bm{r}_{0},\dots,\bm{r}_{n},\bm{l}_{1},\dots,\bm{l}_{n},\bm{r}^{\prime}_{0},\dots,\bm{r}_{m},\bm{l}^{\prime}_{1},\dots,\bm{l}^{\prime}_{m},\\}\setminus\\{\bot\\},$

in which we regard the CQs
$\bm{r}_{i},\bm{l}_{i},\bm{r}^{\prime}_{j},\bm{l}^{\prime}_{j}$ as symbols.
Let $\hat{\Gamma}=\\{(\hat{\bm{a}},a)\mid\bm{a}\in\Gamma\\}$, that is,
$\hat{\Gamma}$ consists of the pointed databases corresponding to the CQs
$\bm{a}\in\Gamma$. For any CQ $\bm{a}$, we set

$f(\bm{a})=\\{\bm{b}(x)\mid\bm{b}\in\Gamma\text{ and
}\mathcal{O},\hat{\bm{a}}\models\bm{b}(a)\\}.$

Similarly, for any pointed data instance $(\mathcal{A},a)$, we set

$f(\mathcal{A},a)=\\{\bm{b}(x)\mid\bm{b}\in\Gamma\text{ and
}\mathcal{O},\mathcal{A}\models\bm{b}(a)\\}$

and, for any temporal data instance
$\mathcal{D}=\mathcal{A}_{0},\ldots,\mathcal{A}_{k}$ with point $a$, set

$f(\mathcal{D},a)=(f(\mathcal{A}_{0},a),\dots,f(\mathcal{A}_{k},a)),$

which is a temporal data instance over the signature $\Gamma$. Finally, we
define an
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{P}^{\Gamma})$-query

$f({\bm{q}})=\rho_{0}\land(\lambda_{1}\mathbin{\mathsf{U}}(\rho_{1}\land(\lambda_{2}\mathbin{\mathsf{U}}(\dots(\lambda_{n}\mathbin{\mathsf{U}}\rho_{n})\dots))))$

by taking $\rho_{i}=f(\bm{r}_{i})$ and $\lambda_{i}=f(\bm{l}_{i})$, and
similarly for ${\bm{q}}^{\prime}$. It follows immediately from the definition
that, for any data instance $\mathcal{D}$, we have
$\mathcal{O},\mathcal{D}\models{\bm{q}}$ iff $f(\mathcal{D},a)\models
f({\bm{q}})$ and $\mathcal{O},\mathcal{D}\models f({\bm{q}}^{\prime})$ iff
$f(\mathcal{D},a)\models f({\bm{q}}^{\prime})$.

We first observe that $f({\bm{q}})$ is a peerless
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{P}^{\Gamma})$-query:
indeed, since $\mathcal{O},\hat{\bm{r}}_{i}\not\models\bm{l}_{i}(a)$, we have
$\bm{l}_{i}\in f(\bm{l}_{i})\setminus f(\bm{r}_{i})$, and since
$\mathcal{O},\hat{\bm{l}}_{i}\not\models\bm{r}_{i}(a)$, we have $\bm{r}_{i}\in
f(\bm{r}_{i})\setminus f(\bm{l}_{i})$. It follows that $f({\bm{q}})\not\equiv
f({\bm{q}}^{\prime})$

Let $E_{\text{prop}}=(E_{\text{prop}}^{+},E_{\text{prop}}^{-})$ be the example
set defined for $f({\bm{q}})$ using $(\mathfrak{p}_{0})$–$(\mathfrak{p}_{2})$
and $(\mathfrak{n}_{0})$–$(\mathfrak{n}_{2})$. By Theorem 18, $f({\bm{q}})$
fits $E_{\text{prop}}$ and $f({\bm{q}}^{\prime})$ does not fit
$E_{\text{prop}}$.

A _satisfying root $\mathcal{O}$-homomorphism_ for any query

$\bm{r}_{0}\land(\bm{l}_{1}\mathbin{\mathsf{U}}(\bm{r}_{1}\land(\bm{l}_{2}\mathbin{\mathsf{U}}(\dots(\bm{l}_{n}\mathbin{\mathsf{U}}\bm{r}_{n})\dots))))$

in $\mathcal{D},a=(\mathcal{A}_{0},a)\ldots,(\mathcal{A}_{k},a)$ is a map $h$
from $\\{0,\ldots,n\\}$ to $\mathbb{N}$ such that $h(0)=0$ and $h(i)<h(i+1)$
for $i<n$ and

  * •

$\mathcal{O},\mathcal{A}_{f(i)}\models\bm{r}_{i}(a)$;

  * •

$\mathcal{O},\mathcal{A}_{i^{\prime}}\models\bm{l}_{i}(a)$ for all
$i^{\prime}\in(f(i),f(i+1))$.

Clearly, such a root $\mathcal{O}$-homomorphism exists iff the query is
satisfied in $\mathcal{D},a$. If the query is in
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\mathcal{P}^{\sigma})$
and $\mathcal{O}$ is empty, then we call the homomorphism above a _satisfying
homomorphism_.

We are now in a position to show that ${\bm{q}}$ fits $E$ but
${\bm{q}}^{\prime}$ does not fit $E$. It is immediate from the definitions
that ${\bm{q}}$ fits $E$. So we show that ${\bm{q}}^{\prime}$ does not fit
$E$.

Assume first that $f({\bm{q}}^{\prime})$ is not entailed by some example in
$E^{+}_{p}$. Then ${\bm{q}}^{\prime}$ is not entailed by some example in
$E^{+}$ as the examples from $(\mathfrak{p}_{0})$–$(\mathfrak{p}_{2})$ are
exactly the $f$-images of the examples
$(\mathfrak{p}^{\prime}_{0})$–$(\mathfrak{p}^{\prime}_{2})$.

Assume now that $f({\bm{q}}^{\prime})$ is entailed by all data instances in
$E_{\text{prop}}^{+}$ and is also entailed by some $\mathcal{D}$ from
$E_{\text{prop}}^{-}$. We show that then there is a data instance in $E^{-}$
that entails ${\bm{q}}^{\prime}$ under $\mathcal{O}$.

If $\mathcal{D}=\Gamma^{n}$, then it follows that the temporal depth of
$f({\bm{q}}^{\prime})$ is less than the temporal depth of $f({\bm{q}})$. Then
$m<n$ and the query ${\bm{q}}^{\prime}$ is entailed by some
$\mathcal{A}_{1},\ldots,\mathcal{A}_{n}\in E^{-}$ with
$(\mathcal{A}_{i},a)\in\mathcal{S}_{\bot}$: we obtain $\mathcal{A}_{i}$ by
taking $(\mathcal{A}_{i},a)\in\mathcal{S}_{\bot}$ such that
$\mathcal{O},\mathcal{A}_{i}\models\bm{r}_{i}^{\prime}(a)$.

Suppose
$\mathcal{D}=\Gamma^{n-i}(\Gamma\setminus\\{\bm{a}\\})\Gamma^{i}\models
f({\bm{q}}^{\prime})$. Observe that the only satisfying homomorphim that
witnesses this is the identity mapping. So we have
$f(\bm{r}_{n-i})\not\subseteq\Gamma\setminus\\{\bm{a}\\}$ and therefore
$\mathcal{O},\hat{\bm{r}}_{n-i}\models\bm{a}(a)$ but
$f(\bm{r}^{\prime}_{n-i})\subseteq\Gamma\setminus\\{\bm{a}\\}$. Then
$\mathcal{O},\hat{\bm{r}}^{\prime}_{n-i}\not\models\bm{a}(a)$, and so
$\bm{r}^{\prime}_{n-i}\not\models_{\mathcal{O}}\bm{r}_{i}$. Therefore, there
is $(\mathcal{A},a)\in\mathcal{S}(\\{\bm{r}_{n-i}\\})$ such that
$\mathcal{O},\mathcal{A}\models\bm{r}^{\prime}_{n-i}(a)$. Observe that also
$\mathcal{O},\mathcal{A}\not\models\bm{r}_{n-i}(a)$.

Now take, for any $j\not=n-i$, some $(\mathcal{A}_{j},a)\in\mathcal{S}_{\bot}$
with $\mathcal{O},\mathcal{A}_{j}\models\bm{r}_{j}^{\prime}$. Then

$\mathcal{O},\mathcal{A}_{0}\cdots\mathcal{A}_{n-i-1}\mathcal{A}\mathcal{A}_{n-i+1}\cdots\mathcal{A}_{n}\not\models{\bm{q}}\quad\text{
and
}\quad\mathcal{O},\mathcal{A}_{0}\cdots\mathcal{A}_{n-i-1}\mathcal{A}\mathcal{A}_{n-i+1}\cdots\mathcal{A}_{n}\not\models{\bm{q}}^{\prime}.$

Assume next that $\mathcal{D}$ is from $(\mathfrak{n}_{1})$. We have
$\mathcal{D}\models f({\bm{q}}^{\prime})$ and $\mathcal{D}\not\models
f({\bm{q}})$. As $\mathcal{D}\models f({\bm{q}}^{\prime})$, we have a
satisfying homomorphism $h$ for $f({\bm{q}}^{\prime})$ in $\mathcal{D}$.

If there is $j$ such that $h(j)=i$, then let $\bm{r}=\bm{r}_{j}$. Otherwise,
there is $j$ such that $h(j)<i<h(j+1)$. Then let $\bm{r}=\bm{l}_{j}$. In both
cases $f(\bm{r})\subseteq Y$, where $Y$ depends on $\mathcal{D}$ and is
either:

  1. 1.

$\Gamma\setminus\\{\bm{a},\bm{b}\\}$ with
$\mathcal{O},\hat{\bm{l}}_{i}\models\bm{a}(a)$ and
$\mathcal{O},\hat{\bm{r}}_{i}\models\bm{b}(a)$ or

  2. 2.

$\Gamma\setminus\\{\bm{a}\\}$ with
$\mathcal{O},\hat{\bm{l}}_{i}\models\bm{a}(a)$ or

  3. 3.

$\Gamma$ (only if $\bm{l}_{i}=\bot$) or

  4. 4.

$\Gamma\setminus\\{\bm{b}\\}$.

_Case_ 1\. We have $\mathcal{O},\hat{\bm{r}}\not\models\bm{a}(a)$ and
$\mathcal{O},\hat{\bm{r}}\not\models\bm{b}(a)$. Hence
$\mathcal{O},\hat{\bm{r}}\not\models\bm{l}_{i}(a)$ and
$\mathcal{O},\hat{\bm{r}}\not\models\bm{r}_{i}(a)$. By the definition of
split-partners, there exists
$(\mathcal{A},a)\in\mathcal{S}(\\{\bm{l}_{i},\bm{r}_{i}\\})$ such that
$\mathcal{O},\mathcal{A}\models\bm{r}(a)$. But then $h$ is also a satisfying
root $\mathcal{O}$-homomorphism in $\mathcal{D}^{\prime},a$ witnessing that
${\bm{q}}^{\prime}$ is entailed by
$\mathcal{D}^{\prime}=\hat{\bm{r}}_{0}\dots\hat{\bm{r}}_{i-1}\mathcal{A}\hat{\bm{r}}_{i}\hat{\bm{r}}_{i+1}\dots\bm{r}_{n}$
wrt $\mathcal{O}$.

It remains to show that $\mathcal{O},\mathcal{D}^{\prime}\not\models{\bm{q}}$.
Assume otherwise. Take a satisfying root $\mathcal{O}$-homomorphism $h^{\ast}$
witnessing $\mathcal{O},\mathcal{D}^{\prime}\models{\bm{q}}$. By peerlessness
of ${\bm{q}}$, $h^{\ast}(j)=j$ for all $j<i$. But then
$\mathcal{O},\mathcal{A}\models\bm{l}_{i}$ or
$\mathcal{O},\mathcal{A}\models\bm{r}_{i}$ which both contradict to
$(\mathcal{A},a)\in\mathcal{S}(\\{\bm{l}_{i},\bm{r}_{i}\\})$.

_Case_ 2\. We have $\mathcal{O},\hat{\bm{r}}\not\models\bm{a}(a)$. Hence
$\mathcal{O},\hat{\bm{r}}\not\models\bm{l}_{i}(a)$. We now distinguish two
cases. If also $\mathcal{O},\hat{\bm{r}}\not\models\bm{r}_{i}(a)$, then we
proceed as in the previous case and choose a split-partner
$(\mathcal{A},a)\in\mathcal{S}(\\{\bm{l}_{i},\bm{r}_{i}\\})$ such that
$\mathcal{O},\mathcal{A}\models\bm{r}(a)$. We proceed as in Case 1.

If $\mathcal{O},\hat{\bm{r}}\models\bm{r}_{i}(a)$, then we proceed as follows.
Choose a split-partner $(\mathcal{A},a)\in\mathcal{S}(\\{\bm{l}_{i}\\})$ such
that $\mathcal{O},\mathcal{A}\models\bm{r}(a)$. Then $h$ is also a satisfying
root $\mathcal{O}$-homomorphism in $\mathcal{D}^{\prime},a$ witnessing that
${\bm{q}}^{\prime}$ is entailed by
$\mathcal{D}^{\prime}=\hat{\bm{r}}_{0}\dots\hat{\bm{r}}_{i-1}\mathcal{A}\hat{\bm{r}}_{i}\hat{\bm{r}}_{i+1}\dots\bm{r}_{n}$
wrt $\mathcal{O}$.

It remains to show that $\mathcal{O},\mathcal{D}^{\prime}\not\models{\bm{q}}$.
Assume otherwise. Take a satisfying root $\mathcal{O}$-homomorphism $h^{\ast}$
in $\mathcal{D}^{\prime},a$ witnessing $\mathcal{D}^{\prime}\models{\bm{q}}$.
By peerlessness of ${\bm{q}}$, $h^{\ast}(j)=j$ for all $j<i$. Then
$h^{\ast}(i)=i$ as $\mathcal{O},\mathcal{A}\models\bm{l}_{i}$ would contradict
$(\mathcal{A},a)\in\mathcal{S}(\\{\bm{l}_{i}\\})$. But then $h^{\ast}$ is a
satisfying homomorphism in $\mathcal{D},a$ witnessing $\mathcal{D}\models
f({\bm{q}})$ and we have derived a contradiction.

_Case_ 3\. We set
$\mathcal{D}^{\prime}=\hat{\bm{r}}_{0}\dots\hat{\bm{r}}_{i-1}\mathcal{A}\hat{\bm{r}}_{i}\hat{\bm{l}}_{i+1}^{k_{i+1}}\hat{\bm{r}}_{i+1}\dots\hat{\bm{l}}_{n}^{k_{n}}\bm{r}_{n}$
for some $(\mathcal{A},a)\in\mathcal{S}_{\bot}$ with
$\mathcal{O},\mathcal{A}\models\bm{r}_{i}^{\prime}$. It directly follows from
$\mathcal{D}\models f({\bm{q}}^{\prime})$ that
$\mathcal{O},\mathcal{D}^{\prime}\models{\bm{q}}^{\prime}$ and also from
$\mathcal{D}\not\models f({\bm{q}})$ that
$\mathcal{O},\mathcal{D}^{\prime}\not\models{\bm{q}}$.

_Case_ 4\. We have $\mathcal{O},\hat{\bm{r}}\not\models\bm{b}(a)$. Hence
$\mathcal{O},\hat{\bm{r}}\not\models\bm{r}_{i}(a)$. We distinguish two cases.
If also $\mathcal{O},\hat{\bm{r}}\not\models\bm{l}_{i}(a)$, then we proceed as
in Case 1 and choose split-partner
$(\mathcal{A},a)\in\mathcal{S}(\\{\bm{l}_{i},\bm{r}_{i}\\})$ such that
$\mathcal{O},\mathcal{A}\models\bm{r}(a)$.

If $\mathcal{O},\hat{\bm{r}}\models\bm{l}_{i}(a)$, then we proceed as follows.
Choose a split-partner $(\mathcal{A},a)\in\mathcal{S}(\\{\bm{r}_{i}\\})$ such
that $\mathcal{O},\mathcal{A}\models\bm{r}(a)$. Then $h$ is also a satisfying
root $\mathcal{O}$-homomorphism in $\mathcal{D}^{\prime},a$ witnessing that
${\bm{q}}^{\prime}$ is entailed by
$\mathcal{D}^{\prime}=\hat{\bm{r}}_{0}\dots\hat{\bm{r}}_{i-1}\mathcal{A}\hat{\bm{r}}_{i}\hat{\bm{r}}_{i+1}\dots\bm{r}_{n}$
wrt $\mathcal{O}$.

It remains to show that $\mathcal{O},\mathcal{D}^{\prime}\not\models{\bm{q}}$.
Assume otherwise. Take a satisfying root $\mathcal{O}$-homomorphism $h^{\ast}$
in $\mathcal{D}^{\prime},a$ witnessing
$\mathcal{O},\mathcal{D}^{\prime}\models{\bm{q}}$. By peerlessness of
${\bm{q}}$, $h^{\ast}(j)=j$ for all $j<i$. Then $h^{\ast}(i)>i$ as
$\mathcal{O},\mathcal{A}\models\bm{r}_{i}(a)$ would contradict the definition
of $\mathcal{A}$. But then, as $\Gamma\setminus\\{\bm{b}\\}\models
f(\bm{l}_{i})$, $h^{\ast}$ is also a satisfying homomorphism in
$\mathcal{D},a$ witnessing $\mathcal{D}\models f({\bm{q}})$ and we have
derived a contradiction.

The case when $\mathcal{D}$ is from $(\mathfrak{n}_{2})$ is considered
similarly to $(\mathfrak{n}_{1})$.

As a consequence of Theorems 17, 10, and [22, Theorem 30], we obtain:

######  Theorem 19.

$(i)$ Every
${\bm{q}}\in\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\text{ELIQ}^{\sigma})$
is exponentially uniquely characterisable wrt any
$\textit{horn}\mathcal{ALCHI}$ ontology in $\sigma$ within
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\text{ELIQ}^{\sigma})$.

$(ii)$ Every
${\bm{q}}\in\textsl{LTL}_{pp}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\text{ELQ}^{\sigma})$
is polynomially uniquely characterisable wrt the empty ontology within
$\textsl{LTL}_{p}^{\smash{\scriptstyle\mathbin{\mathsf{U}}}}(\text{ELQ}^{\sigma})$.

##  6 Learning

We apply the results on unique characterisability to exact learnability of
queries in
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
wrt ontologies. More precisely, given some class $\mathcal{Q}$ of two-
dimensional queries and an ontology $\mathcal{O}$, we aim to identify a target
query ${\bm{q}}_{T}\in\mathcal{Q}$ using queries to an oracle. It is assumed
that ${\bm{q}}_{T}$ uses only symbols that occur in $\mathcal{O}$. A positive
example (for ${\bm{q}}_{T}$ wrt $\mathcal{O}$ ) is a pointed temporal data
instance $\mathcal{D},a$ with
$\mathcal{O},\mathcal{D},0,a\models{\bm{q}}_{T}$. A _membership query_ is then
a pointed temporal data instance $\mathcal{D},a$, and the (truthful) answer of
the oracle is ‘yes’ if $\mathcal{D},a$ is a positive example and ‘no’
otherwise. Let $\mathcal{L}$ be an ontology language. We call $\mathcal{Q}$
polynomial-time learnable wrt $\mathcal{L}$-ontologies using membership
queries if there is a learning algorithm that receives an
$\mathcal{L}$-ontology $\mathcal{O}$ and a positive example $\mathcal{D},a$
with $\mathcal{D}$ satisfiable wrt $\mathcal{O}$, and constructs
${\bm{q}}_{T}$ (up to equivalence wrt $\mathcal{O}$) in time polynomial in the
size of ${\bm{q}}_{T},\mathcal{O}$, and $\mathcal{D}$. We also consider a
weaker complexity measure that only bounds the number of queries but not the