11institutetext: CNRS & University of Bordeaux, Bordeaux, France
11email<EMAIL_ADDRESS>
22institutetext: Sapienza University of Rome, Rome, Italy
22email: {croce<EMAIL_ADDRESS>
# QDEF and Its Approximations in OBDM

Gianluca Cima 11 0000-0003-1783-5605 Federico Croce 22 0000-0001-6779-4624
Maurizio Lenzerini 22 0000-0003-2875-6187

###### Abstract

Given an input dataset (i.e., a set of tuples), query definability in
Ontology-based Data Management (OBDM) amounts to find a query over the
ontology whose certain answers coincide with the tuples in the given dataset.
We refer to such a query as a _characterization_ of the dataset with respect
to the OBDM system. Our first contribution is to propose approximations of
perfect characterizations in terms of recall (complete characterizations) and
precision (sound characterizations). A second contribution is to present a
thorough complexity analysis of three computational problems, namely
verification (check whether a given query is a perfect, or an approximated
characterization of a given dataset), existence (check whether a perfect, or a
best approximated characterization of a given dataset exists), and computation
(compute a perfect, or best approximated characterization of a given dataset).

##  1 Introduction

As first introduced for relational databases [39, 36, 6, 5], query
definability is the reverse engineering task that, given a set of tuples and a
database, aims at finding a query whose answers over such database are exactly
the tuples in the set. In other words, the goal of this task is to derive an
intensional definition (the query) of an extensionally defined set. Over the
years, researchers have found several interesting applications of this
problem, spanning from simplifying query formulation by non-experts, to
debugging facilities for data engineers. Moreover, the query definability has
been studied as a useful tool for data exploration, data analysis, usability,
data security and more [26, 28]. With the rise of Machine Learning (ML), we
argue that this topic could be also beneficial for providing meaningful
reformulations of what is called a training dataset in any typical supervised
ML-based classification task. In this context, the training set used in a
classification task is seen as a set of tuples in a database schema, and the
query derived by solving the query definability problem results into an
intensional definition of the input training set. In a sense, the expression
derived can be used as an explanation of the intensional properties of the
training set. The idea is that an intensional characterization of the training
set can help understanding the behaviour of a classifier, a very important
task for wide and safe adoption of machine learning and data mining
technologies, especially in dealing with bias.

In this paper, we address the problem of query definability in the context of
Ontology-based Data Management (OBDM), which is a paradigm for accessing data
using a conceptual representation of the domain of interest expressed as an
ontology. OBDM relies on a three-level architecture, consisting of the schema
of the data layer $\mathcal{S}$ (which we assume constituted by a relational
database), the ontology $\mathcal{O}$, a declarative and explicit
representation of the domain of interest for the organization, and the mapping
$\mathcal{M}$ between the two. Consequently, an OBDM specification is
formalized as the triple $J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$
which, together with an $\mathcal{S}$-database $D$, form a so-called OBDM
system $\Sigma=\langle J,D\rangle$. In this context, we are going to tackle
the problem of query definability by leveraging the notion of evaluation of a
query with respect to an OBDM system, in turn based on the notion of certain
answers to a query over an OBDM system. Intuitively, given an OBDM system
$\Sigma=\langle J,D\rangle$ and a $D$-dataset $\lambda$, our goal is to derive
a query expression over $\mathcal{O}$ that suitably _characterizes_ $\lambda$
w.r.t. $\Sigma$. In other words, we aim at deriving a “good” definition of
$\lambda$ using a query expressed over the concepts and roles of the ontology
of $J$.

Inspired by the works in [22, 29] about query definability in Description
Logics (DLs), we consider the query whose certain answers with respect to
$\Sigma=\langle J,D\rangle$ is exactly $\lambda$ as the perfect
characterization for $\lambda$. We note that, since in this paper we tackle
the query definability problem in OBDM, differently from the works in [22,
29], this work has the added complexity of considering the mapping layer of
the OBDM system, which is, to the best of our knowledge, novel to this field.
This work has also been inspired by the concept learning tools presented in
[7, 19, 34], and by the notion of query abstraction [15, 13, 14]. We differ
from the former because in that work the goal is to learn a concept expression
capturing a given dataset, whereas our goal is to derive a full-blown query
that, evaluated over the ontology, returns the dataset as answers. We differ
from the latter because, although the goal is stil to derive a query
expression over the ontology, in that work the input is a query over the data
layer, whereas in query definability the input is a set of tuples. It follows
that the two tasks are completely different and require different technical
solutions: in the present work we aim at finding a query over the ontology
such that the certain answers of the query w.r.t. the OBDM system are equal to
the given specific dataset, whereas in [15, 13, 14], the goal is to find a
query over the ontology such that the certain answers of the query are equal
to the evaluation of the given query over the database schema, for all
possible databases of the OBDM system. In the framework section of this paper
we will better characterize the relationship between the two notions of query
definability and query abstraction.

Virtually all the above-mentioned works point out that in many cases a perfect
ontological characterization of a given dataset does not exist. We argue that,
in these cases, reasonable and useful ontological characterizations can still
be provided. In particular, we propose to resort to suitable approximations of
the perfect characterizations, in terms of recall and precision. To this end,
we introduce the notions of sound and complete characterizations. The former
is a query whose certain answers form a subset of the $D$-dataset $\lambda$ in
input, whereas the certain answers of the latter, form a superset of the
$D$-dataset $\lambda$. Obviously, we are interested in computing the best
approximated characterizations, which we call maximally sound and minimally
complete characterizations, respectively. A maximally sound (resp., minimally
complete) characterization is a sound (resp., complete) characterization such
that no other sound (resp., complete) characterization exists that better
approximates the $D$-dataset $\lambda$.

This paper provides the following contributions.

  * •

We present a general, formal framework for the various notions of ontological
characterizations mentioned above. The framework includes the definition of
three tasks that are relevant for reasoning about characterizations of a
dataset, namely verification (verify whether a given query is a sound,
complete, or perfect characterizations), computation (compute a
characterization of a certain type), and existence (check whether a
characterization of a certain type exists).

  * •

We provide computational complexity results for the three reasoning tasks
mentioned above in a scenario that uses the most common languages in the OBDM
literature, namely where the ontology language is $\textit{DL-
Lite}_{\mathcal{R}}$, the mapping language is GLAV, and the query language to
express characterizations is the one of union of conjunctive queries. As for
the two decision problems of verification and existence, we provide both upper
bounds and matching lower bounds. As for the computation task, we provide
algorithms for computing perfect, minimally complete, and maximally sound
characterizations, provided they exist.

The paper is organized as follows. After the preliminaries in Section 2,
Section 3 illustrates the framework, and Sections 4, 5, and 6 present the
results on the three reasoning tasks, i.e., verification, computation and
existence, respectively. Finally, Section 7 concludes the paper by discussing
possible future work.

##  2 Preliminaries

We recall some notations and languages about relational databases [1],
Description Logics (DLs) [4], and the Ontology-based Data Management (OBDM)
paradigm [24].

### Databases, Datasets, and Queries:

A _relational database schema_ (or simply _schema_) $\mathcal{S}$ is a finite
set of predicate symbols, each with a specific arity. Given a schema
$\mathcal{S}$, an _$\mathcal{S}$ -database_ $D$ is a finite set of _facts_
satisfying all integrity constraints in $\mathcal{S}$ whose form is
$s(\vec{c})$, where $s$ is an $n$-ary predicate symbol of $\mathcal{S}$, and
$\vec{c}=(c_{1},\ldots,c_{n})$ is an $n$-tuple of constants, each taken from a
countable infinite set of symbols denoted by $\mathsf{Const}$. We denote by
$\mathit{dom}(D)$ the finite set of constants occurring in $D$. Observe that
$\mathit{dom}(D)\subseteq\mathsf{Const}$.

Given a schema $\mathcal{S}$ and an $\mathcal{S}$-database $D$, a _$D$
-dataset_ $\lambda$ of arity $n$ is a finite set of $n$-tuples $\vec{c}$ of
constants occurring in $D$, i.e., $\lambda\subseteq\mathit{dom}(D)^{n}$.

A _query_ $q_{\mathcal{S}}$ over a schema $\mathcal{S}$ is an expression in a
certain query language $\mathcal{Q}$ using the predicate symbols of
$\mathcal{S}$ and arguments of predicates are _variables_ , i.e., we disallow
constants to occur in queries. Each query has an associated arity. The
_evaluation_ of a query $q_{\mathcal{S}}$ of arity $n$ over an
$\mathcal{S}$-databases $D$ is a set of _answers_ $q_{\mathcal{S}}^{D}$, each
answer being an $n$-tuple of constants occurring in $\mathit{dom}(D)$, i.e.,
$q_{\mathcal{S}}^{D}\subseteq\mathit{dom}(D)^{n}$. We are particularly
interested in _conjunctive queries_ and unions thereof.

A _conjunctive query (CQ)_ over a schema $\mathcal{S}$ is an expression of the
form
$q_{\mathcal{S}}=\\{\vec{x}\mid\exists\vec{y}\mbox{\bf.}\phi(\vec{x},\vec{y})\\}$
such that (_i_) $\vec{x}=(x_{1},\ldots,x_{n})$, called the _target list_ of
$q_{\mathcal{S}}$, is an $n$-tuple of _distinguished variables_ , where $n$ is
the arity $q_{\mathcal{S}}$ (_ii_) $\vec{y}=(y_{1},\ldots,y_{m})$ is an
$m$-tuple of _existential variables_ ; and (_iii_) $\phi(\vec{x},\vec{y})$,
called the _body_ of $q_{\mathcal{S}}$, is a finite conjunction of atoms of
the form $s(v_{1},\ldots,v_{p})$, where $s$ is a $p$-ary predicate symbol of
$\mathcal{S}$ and $v_{i}$ is either a distinguished or an existential
variable, i.e., $v_{i}\in\vec{x}\cup\vec{y}$, for each $i=[1,p]$. Variables
belong to a countable infinite set of symbols denoted by $\mathcal{V}$, where
$\mathsf{Const}\cap\mathcal{V}=\emptyset$. A _union of conjunctive queries
(UCQ)_ is a finite set of CQs with same arity, called its _disjuncts_.

For a conjunction of atoms $\phi(\vec{x},\vec{y})$, we denote by
$\mathit{set}(\phi)$ the set of all the atoms occurring in $\phi$. For a set
of atoms $\mathcal{C}$ and a tuple $\vec{c}=(c_{1},\ldots,c_{n})$ of
constants, we denote by $\mathit{query}(\mathcal{C},\vec{c})$ the CQ
$\\{\vec{x}\mid\exists\vec{y}\mbox{\bf.}\phi(\vec{x},\vec{y})\\}$, where (_i_)
$\phi(\vec{x},\vec{y})$ is the conjunction of all the atoms occurring in the
set of atoms $\mathcal{C}^{\prime}$, where $\mathcal{C}^{\prime}$ is obtained
from $\mathcal{C}$ by replacing everywhere each constant $c_{i}$ occurring in
$\vec{c}$ with a fresh variable $x_{c_{i}}$ and each constant $c$ not
occurring in $\vec{c}$ with a fresh variable $y_{c}$, (_ii_)
$\vec{x}=(x_{c_{1}},\ldots,x_{c_{n}})$, and (_iii_) $\vec{y}$ is the tuple of
all variables occurring in $\mathcal{C}^{\prime}$ that do not occur in
$\vec{x}$.

Following the terminology of [35], we say that a query $q_{\mathcal{S}}$ over
a schema $\mathcal{S}$ _defines a $D$-dataset $\lambda$ inside an
$\mathcal{S}$-database $D$_ if $q_{\mathcal{S}}^{D}=\lambda$, and say that
$\lambda$ is _$\mathcal{Q}$ -definable inside $D$_, for a query language
$\mathcal{Q}$, if there exists a query $q_{\mathcal{S}}\in\mathcal{Q}$ that
defines $\lambda$ inside $D$.

Given a set of atoms $\mathcal{C}$, we denote by $\mathit{dom}(\mathcal{C})$
the set of all constants and variables occurring in a set of atoms
$\mathcal{C}$. Observe that
$\mathit{dom}(\mathcal{C})\subseteq\mathsf{Const}\cup\mathcal{V}$. Let
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ be two sets of atoms. We say that a
function
$h:\mathit{dom}(\mathcal{C}_{1})\rightarrow\mathit{dom}(\mathcal{C}_{2})$ is a
_homomorphism_ from $\mathcal{C}_{1}$ to $\mathcal{C}_{2}$ if
$h(\mathcal{C}_{1})\subseteq h(\mathcal{C}_{2})$, where $h(\mathcal{C}_{1})$
is the image of $\mathcal{C}_{1}$ under $h$, i.e.,
$h(\mathcal{C}_{1})=\\{h(\alpha)\mid\alpha\in\mathcal{C}_{1}\\}$ with
$h(s(t_{1},\ldots,t_{n}))=s(h(t_{1}),\ldots,h(t_{n}))$ for each atom
$\alpha=s(t_{1},\ldots,t_{n})$. For two sets of atoms $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ and two tuples of terms $\vec{t_{1}}$ and $\vec{t_{2}}$, we
write $(\mathcal{C}_{1},\vec{t_{1}})\rightarrow(\mathcal{C}_{2},\vec{t_{2}})$
if there is a function $h$ from $\mathit{dom}(\mathcal{C}_{1})\cup\vec{t_{1}}$
to $\mathit{dom}(\mathcal{C}_{2})\cup\vec{t_{2}}$ such that (_i_) $h$ is a
homomorphism from $\mathcal{C}_{1}$ to $\mathcal{C}_{2}$, and (_ii_)
$h(\vec{t_{1}})=\vec{t_{2}}$ (where, for a tuple of terms
$\vec{t}=(t_{1},\ldots,t_{n})$, $h(\vec{t})=(h(t_{1}),\ldots,h(t_{n}))$),
$(\mathcal{C}_{1},\vec{t_{1}})\not\rightarrow(\mathcal{C}_{2},\vec{t_{2}})$
otherwise.

Observe that for an $\mathcal{S}$-database $D$ and a CQ
$q_{\mathcal{S}}=\\{\vec{x}\mid\exists\vec{y}\mbox{\bf.}\phi(\vec{x},\vec{y})\\}$
over $\mathcal{S}$ of arity $n$, the set of answers $q_{\mathcal{S}}^{D}$
corresponds to the set of $n$-tuples $\vec{c}$ of constants occurring in $D$
for which $(\mathit{set}(\phi),\vec{x})\rightarrow(D,\vec{c})$.

### Syntax and Semantics of $\textit{DL-Lite}_{\mathcal{R}}$:

DLs are fragments of First-order logic languages using only unary and binary
predicates, called _atomic concepts_ and _atomic roles_ , respectively. In
this paper, a _DL ontology_ (or simply _ontology_) $\mathcal{O}$ is a TBox
(“Terminological Box”) expressed in a specific DL, that is, a set of
assertions stating general properties of concepts and roles built according to
the syntax of the specific DL, which represents the intensional knowledge of a
modeled domain.

We are interested in DL ontologies expressed in $\textit{DL-
Lite}_{\mathcal{R}}$, the member of the DL-Lite family [10] that underpins OWL
2 QL, i.e., the OWL 2 profile especially designed for efficient query
answering [27]. A $\textit{DL-Lite}_{\mathcal{R}}$ ontology $\mathcal{O}$ is a
finite set of _assertions_ of the form:

$\begin{array}[t]{lll}B_{1}\sqsubseteq B_{2}&\quad R_{1}\sqsubseteq
R_{2}&\quad\mbox{(concept/role inclusion)}\\\\[2.84526pt] B_{1}\sqsubseteq\neg
B_{2}&\quad R_{1}\sqsubseteq\neg R_{2}&\quad\mbox{(concept/role
disjointness)}\end{array}$

where $B_{1}$, $B_{2}$ are basic concepts, i.e., expressions of the form $A$,
$\exists P$, or $\exists P^{-}$, with $A$ and $P$ an atomic concept (atomic
concepts include the universal one $\top$ and the bottom one $\bot$) and an
atomic role, respectively, and $R_{1}$ and $R_{2}$ basic roles, i.e.,
expressions of the form $P$, or $P^{-}$.

Given a $\textit{DL-Lite}_{\mathcal{R}}$ ontology $\mathcal{O}$, we denote by
$V_{\mathcal{O}}$ the _$\mathcal{O}$ -violation query_, i.e., the boolean UCQ
obtained by including a disjunct of the form $\\{()\mid\exists
y\mbox{\bf.}A_{1}(y)\wedge A_{2}(y)\\}$ (respectively, $\\{()\mid\exists
y_{1},y_{2}\mbox{\bf.}A_{1}(y_{1})\wedge R(y_{1},y_{2})\\}$, $\\{()\mid\exists
y_{1},y_{2},y_{3}\mbox{\bf.}R_{1}(y_{1},y_{2})\wedge R_{2}(y_{1},y_{3})\\}$,
and $\\{()\mid\exists y_{1},y_{2}\mbox{\bf.}R_{1}(y_{1},y_{2})\wedge
R_{2}(y_{1},y_{2})\\}$) for each disjointness assertion $A_{1}\sqsubseteq\neg
A_{2}$ (respectively, $A_{1}\sqsubseteq\neg\exists R$ or $\exists
R\sqsubseteq\neg A_{1}$, $\exists R_{1}\sqsubseteq\neg\exists R_{2}$, and
$R_{1}\sqsubseteq\neg R_{2}$) occurring in $\mathcal{O}$, where an atom of the
form $R(y,y^{\prime})$ stands for either $P(y,y^{\prime})$ if $R$ denotes an
atomic role $P$, or $P(y^{\prime},y)$ if $R$ denotes the inverse of an atomic
role, i.e., $R=P^{-}$.

The semantics of DL ontologies is specified through the notion of
interpretation: an _interpretation_ $\mathcal{I}$ for an ontology
$\mathcal{O}$ is a pair
$\mathcal{I}=\langle\Delta^{\mathcal{I}},\cdot^{\mathcal{I}}\rangle$, where
the _interpretation domain_ $\Delta^{\mathcal{I}}$ is a non-empty, possibly
infinite set of constants, and the _interpretation function_
$\cdot^{\mathcal{I}}$ assigns to each atomic concept $A$ a set of domain
objects $A^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}$, and to each atomic
role $P$ a set of pairs of domain objects
$P^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$. For
the constructs of $\textit{DL-Lite}_{\mathcal{R}}$, the interpretation
function extends to other basic concepts and basic roles as follows:
$\top^{\mathcal{I}}=\Delta^{\mathcal{I}}$, $\bot^{\mathcal{I}}=\emptyset$,
$(\exists P)^{\mathcal{I}}=\\{o\mid\exists o^{\prime}.\ (o,o^{\prime})\in
P^{\mathcal{I}}\\}$, and
$(P^{-})^{\mathcal{I}}=\\{(o,o^{\prime})\mid(o^{\prime},o)\in
P^{\mathcal{I}}\\}$. We often treat interpretations $\mathcal{I}$ for
ontologies $\mathcal{O}$ as a (possibly infinite) set of facts over (the
atomic concepts and roles in the alphabet of) $\mathcal{O}$.

We say that an interpretation $\mathcal{I}$ for an ontology $\mathcal{O}$
satisfies $\mathcal{O}$, denoted by $\mathcal{I}\models\mathcal{O}$, if
$\mathcal{I}$ satisfies every assertion in $\mathcal{O}$. For the $\textit{DL-
Lite}_{\mathcal{R}}$ assertions, an interpretation $\mathcal{I}$ satisfies a
concept inclusion assertion $B_{1}\sqsubseteq B_{2}$ (respectively, role
inclusion assertion $R_{1}\sqsubseteq R_{2}$) if $B_{1}^{\mathcal{I}}\subseteq
B_{2}^{\mathcal{I}}$ (respectively, $R_{1}^{\mathcal{I}}\subseteq
R_{2}^{\mathcal{I}}$), and it satisfies a concept disjointness assertion
$B_{1}\sqsubseteq\neg B_{2}$ (respectively, role disjointness assertion
$R_{1}\sqsubseteq\neg R_{2}$) if $B_{1}^{\mathcal{I}}\cap
B_{2}^{\mathcal{I}}=\emptyset$ (respectively, $R_{1}^{\mathcal{I}}\cap
R_{2}^{\mathcal{I}}=\emptyset$).

Whenever we speak about queries $q_{\mathcal{O}}$ over ontologies
$\mathcal{O}$, we mean queries in a certain language $\mathcal{Q}$ using the
atomic concepts and roles in the alphabet of $\mathcal{O}$ as predicates. For
a UCQ $q_{\mathcal{O}}$ over a $\textit{DL-Lite}_{\mathcal{R}}$ ontology
$\mathcal{O}$, we denote by $\mathsf{PerfectRef}(\mathcal{O},q_{\mathcal{O}})$
the UCQ computed by executing the algorithm $\mathsf{PerfectRef}$ [10] on
$\mathcal{O}$ and $q_{\mathcal{O}}$.

### Ontology-based Data Management:

According to [32, 24], an _Ontology-based Data Management (OBDM)_
specification is a triple
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$, where $\mathcal{O}$ is
a DL ontology, $\mathcal{S}$ is a relational database schema, also called
_source schema_ , and $\mathcal{M}$ is a _mapping_ , i.e., a finite set of
assertions over the signature $\mathcal{S}\cup\mathcal{O}$ relating the source
schema $\mathcal{S}$ to the ontology $\mathcal{O}$. An OBDM system is a pair
$\Sigma=\langle J,D\rangle$, where
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ is an OBDM specification
and $D$ is an $\mathcal{S}$-database.

The semantics of an OBDM system
$\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$ is
given in terms of interpretations
$\mathcal{I}=\langle\Delta^{\mathcal{I}},\cdot^{\mathcal{I}}\rangle$ for
$\mathcal{O}$ in which the interpretation function $\cdot^{\mathcal{I}}$
further assigns to each constant $c\in\mathit{dom}(D)$ a domain object
$c\in\Delta^{\mathcal{I}}$. Specifically, we say that an interpretation
$\mathcal{I}$ for $\mathcal{O}$ is a _model_ of an OBDM system
$\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$ if
(_i_) $\mathcal{I}\models\mathcal{O}$, and (_ii_) the pair
$\langle\mathcal{I},D\rangle\models\mathcal{M}$. We say that an OBDM system
$\Sigma$ is _consistent_ if it has at least one model, _inconsistent_
otherwise.

The set of _certain answers_ of a query $q_{\mathcal{O}}$ over an ontology
$\mathcal{O}$ w.r.t. an OBDM system $\Sigma=\langle J,D\rangle$ with
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$, denoted by
$\mathit{cert}_{q_{\mathcal{O}},J}^{D}$, is the set of tuples of constants
$(c_{1},\ldots,c_{n})$ such that
$(c_{1}^{\mathcal{I}},\ldots,c_{n}^{\mathcal{I}})\in
q_{\mathcal{O}}^{\mathcal{I}}$ for each model $\mathcal{I}$ of $\Sigma$, where
$\mathcal{I}$ is seen as a set of facts over $\mathcal{O}$. If $\Sigma$ is
inconsistent, then the set of certain answers of any query $q_{\mathcal{O}}$
over $\mathcal{O}$ w.r.t. $\Sigma$ is simply the set of all possible tuples of
constants occurring in $D$ whose arity is the one of the query. We say that
two queries $q_{1}$ and $q_{2}$ are equivalent w.r.t. an OBDM system
$\Sigma=\langle J,D\rangle$ if
$\mathit{cert}_{q_{1},J}^{D}=\mathit{cert}_{q_{2},J}^{D}$.

As for the mapping component of an OBDM system, in this paper we are
interested in _GLAV_ assertions [17], which are assertions of the form
$q_{\mathcal{S}}\rightarrow q_{\mathcal{O}},$ where $q_{\mathcal{S}}$ and
$q_{\mathcal{O}}$ are CQs over $\mathcal{S}$ and over $\mathcal{O}$,
respectively, with the same target list $\vec{x}=(x_{1},\ldots,x_{n})$.
Special cases of GLAV assertions highly considered in the data integration
literature are GAV and LAV assertions [23]: in a GAV (resp., LAV) mapping,
$q_{\mathcal{O}}$ (resp., $q_{\mathcal{S}}$) is simply an atom without
existential variables. A GLAV (resp., GAV, LAV, GAV$\cap$LAV) mapping is a
finite set of GLAV (resp., GAV, LAV, both GAV and LAV) assertions.

Given a GLAV mapping $\mathcal{M}$ relating $\mathcal{S}$ to $\mathcal{O}$, an
interpretation $\mathcal{I}$ for $\mathcal{O}$, and an $\mathcal{S}$-database
$D$, we have that $\langle\mathcal{I},D\rangle\models\mathcal{M}$ if
$(c_{1},\ldots,c_{n})\in q_{\mathcal{S}}^{D}$ implies
$(c_{1}^{\mathcal{I}},\ldots,c_{n}^{\mathcal{I}})\in
q_{\mathcal{O}}^{\mathcal{I}}$ for each mapping assertion
$q_{\mathcal{S}}\rightarrow q_{\mathcal{O}}$ occurring in $\mathcal{M}$ and
for each possible tuple $(c_{1},\ldots,c_{n})$ of constants occurring in $D$.

Let $J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ be an OBDM
specification where $\mathcal{O}=\emptyset$, i.e., $\mathcal{O}$ has no
assertions, and $\mathcal{M}$ is a GLAV mapping. From results of [20, 11], it
is well-known that, given a UCQ $q_{\mathcal{O}}$ over $\mathcal{O}$, by
splitting the GLAV mapping $\mathcal{M}$ into a GAV mapping followed by a LAV
mapping over an intermediate alphabet, it is always possible to compute a UCQ
over $\mathcal{S}$, denoted by $\mathsf{MapRef}(\mathcal{M},q_{\mathcal{O}})$,
such that
$\mathsf{MapRef}(\mathcal{M},q_{\mathcal{O}})^{D}=\mathit{cert}_{q_{\mathcal{O}},J}^{D}$
for each $\mathcal{S}$-database $D$.

Let now $J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ be an OBDM
specification where $\mathcal{O}$ is a $\textit{DL-Lite}_{\mathcal{R}}$
ontology and $\mathcal{M}$ is a GLAV mapping. For a UCQ $q_{\mathcal{O}}$ over
$\mathcal{O}$, we denote by $\mathsf{rew}_{q_{\mathcal{O}},J}$ the following
UCQ over $\mathcal{S}$:
$\mathsf{rew}_{q_{\mathcal{O}},J}:=\mathsf{MapRef}(\mathcal{M},\mathsf{PerfectRef}(\mathcal{O},q_{\mathcal{O}}))$.
By combining the above observation with results of [10], we have that (_i_)
$\mathit{cert}_{q_{\mathcal{O}},J}^{D}=\mathsf{rew}_{q_{\mathcal{O}},J}^{D}$,
for each UCQ $q_{\mathcal{O}}$ over $\mathcal{O}$ and for each
$\mathcal{S}$-database $D$ such that $\langle J,D\rangle$ is consistent, and
(_ii_) $\langle J,D\rangle$ is inconsistent if and only if
$\mathsf{rew}_{V_{\mathcal{O}},J}^{D}=\\{\langle\rangle\\}$, for each
$\mathcal{S}$-database $D$. We note that $\textit{DL-Lite}_{\mathcal{R}}$ is
insensitive to the adoption of the unique name assumption for UCQ answering
[3].

### Canonical Structure:

Given an $\mathcal{S}$-database $D$ and a GLAV mapping $\mathcal{M}$ relating
a schema $\mathcal{S}$ to an ontology $\mathcal{O}$, the _chase_ [9] of $D$
with respect to $\mathcal{M}$, denoted by $\mathcal{M}(D)$, is the set of
atoms computed as follows: (_i_) we start with $\mathcal{M}(D):=\emptyset$;
then (_ii_) for every GLAV assertion
$\\{\vec{x}\mid\exists\vec{y}\mbox{\bf.}\phi_{\mathcal{S}}(\vec{x},\vec{y})\\}\rightarrow\\{\vec{x}\mid\exists\vec{z}\mbox{\bf.}\varphi_{\mathcal{O}}(\vec{x},\vec{z})\\}$
in $\mathcal{M}$ and for every tuple of constants $\vec{c}$ such that
$(\mathit{set}(\phi_{\mathcal{S}}),\vec{x})\rightarrow(D,\vec{c})$, we add to
$\mathcal{M}(D)$ the image of the set of atoms
$\mathit{set}(\varphi_{\mathcal{O}})$ under $h^{\prime}$, that is,
$\mathcal{M}(D):=\mathcal{M}(D)\cup
h^{\prime}(\varphi_{\mathcal{O}}(\vec{x},\vec{z}))$, where $h^{\prime}$
extends $h$ by assigning to each variable $z$ occurring in $\vec{z}$ a
different fresh variable of $\mathcal{V}$ still not present in
$\mathit{dom}(\mathcal{M}(D))$. Observe that $\mathcal{M}(D)$ is guaranteed to
be finite and can be always computed in exponential time.

We conclude this section with the following observation used in the technical
development of the next sections. Let
$\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$ be
an OBDM system where $\mathcal{O}$ is a $\textit{DL-Lite}_{\mathcal{R}}$
ontology and $\mathcal{M}$ is a GLAV mapping. We call the _canonical
structure_ of $\mathcal{O}$ with respect to $\mathcal{M}$ and $D$, denoted by
$\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)}$, the (possibly infinite) set of
atoms obtained by first computing $\mathcal{M}(D)$ as described before, and
then by chasing $\mathcal{M}(D)$ with respect to the inclusion assertions of
$\mathcal{O}$ as described in [10, Definition 5] but using the alphabet
$\mathcal{V}$ of variables whenever a new element is needed in the chase.
Observe that this latter is a _fair_ deterministic strategy, i.e., it is such
that if at some point an assertion is applicable, then it will be eventually
applied. By combining results of [18, Proposition 4.2] with [10, Theorem 29],
it is well-known that, for a UCQ
$q_{\mathcal{O}}=\\{\vec{x_{1}}\mid\exists\vec{y_{1}}\mbox{\bf.}\phi^{1}_{\mathcal{O}}(\vec{x_{1}},\vec{y_{1}})\\}\cup\ldots\cup\\{\vec{x_{p}}\mid\exists\vec{y_{p}}\mbox{\bf.}\phi^{p}_{\mathcal{O}}(\vec{x_{p}},\vec{y_{p}})\\}$
over $\mathcal{O}$ and a tuple of constants $\vec{c}$, if $\Sigma=\langle
J,D\rangle$ is consistent, then we have
$\vec{c}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$ if and only if
$(\mathit{set}(\phi^{i}_{\mathcal{O}}),\vec{x_{i}})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})$
for some $i\in[1,p]$.

##  3 Framework

In what follows, $\Sigma=\langle J,D\rangle$ refers to an OBDM system where
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ is an OBDM specification
and $D$ is an $\mathcal{S}$-database. Intuitively, given a set $\lambda$ of
$n$-tuples of constants occurring in $D$ (i.e., $\lambda$ is a $D$-dataset of
arity $n$), we aim at finding a query $q_{\mathcal{O}}$ over $\mathcal{O}$ in
a certain query language $\mathcal{Q}$ characterizing $\lambda$ w.r.t. the
OBDM system $\Sigma$. Since the evaluation of queries is based on certain
answers, we are naturally led to the following definition.

###### Definition 1

$q_{\mathcal{O}}\in\mathcal{Q}$ is a _perfect $\Sigma$-characterization_ of
$\lambda$ in the query language $\mathcal{Q}$, if
$cert^{D}_{q_{\mathcal{O}},J}=\lambda$.

Clearly, if a perfect $\Sigma$-characterization of $\lambda$ exists, then it
is unique up to $\Sigma$-equivalence, and therefore in the following we will
always refer to _the_ perfect $\Sigma$-characterization of $\lambda$ in the
query language $\mathcal{Q}$.

###### Example 1

Let $\Sigma=\langle J,D\rangle$ be as follows.
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ is the OBDM
specification such that
$\mathcal{O}=\\{\textsf{MathStudent}\sqsubseteq\textsf{ Student},\textsf{
ForeignStudent}\sqsubseteq\textsf{ Student}\\}$,
$\mathcal{S}=\\{s_{1},s_{2},s_{3},s_{4},s_{5}\\}$, and $\mathcal{M}$ contains
the GAV assertions:

$\displaystyle\\{(x)\mid s_{1}(x)\\}\rightarrow\\{(x)\mid\textsf{
Student}(x)\\}$ $\displaystyle\\{(x)\mid
s_{2}(x)\\}\rightarrow\\{(x)\mid\textsf{ Student}(x)\\}$
$\displaystyle\\{(x_{1},x_{2})\mid
s_{3}(x_{1},x_{2})\\}\rightarrow\\{(x_{1},x_{2})\mid\textsf{
EnrolledIn}(x_{1},x_{2})\\}$ $\displaystyle\\{(x)\mid\exists
y\mbox{\bf.}s_{3}(x,y)\wedge s_{4}(y)\\}\rightarrow\\{(x)\mid\textsf{
MathStudent}(x)\\}$ $\displaystyle\\{(x)\mid\exists
y\mbox{\bf.}s_{3}(x,y)\wedge s_{5}(y)\\}\rightarrow\\{(x)\mid\textsf{
ForeignStudent}(x)\\}\vspace*{-.12cm}$

And the $\mathcal{S}$-database is
$D=\\{s_{1}(c_{4}),s_{2}(c_{3}),s_{4}(b_{1}),s_{5}(d_{1}),\\\
s_{3}(c_{1},b_{1}),s_{3}(c_{2},d_{1}),s_{3}(c_{3},e_{1}),s_{3}(c_{4},e_{2}),s_{3}(c_{5},e_{3})\\}$.
For the $D$-dataset $\lambda=\\{(c_{1}),(c_{2}),(c_{3})\\}$, since
$q_{\mathcal{O}}^{1}=\\{(x)\mid\textsf{ Student}(x)\\}$ and
$q_{\mathcal{O}}^{2}=\\{(x)\mid\exists
y\mbox{\bf.}\textsf{EnrolledIn}(x,y)\\}$ are such that
$\mathit{cert}_{q_{\mathcal{O}}^{1},J}^{D}=\\{(c_{1}),(c_{2}),(c_{3}),(c_{4})\\}$
and
$\mathit{cert}_{q_{\mathcal{O}}^{2},J}^{D}=\\{(c_{1}),(c_{2}),(c_{3}),(c_{4}),(c_{5})\\}$,
and since $q_{\mathcal{O}}^{3}=\\{(x)\mid\textsf{MathStudent}(x)\\}$ and
$q_{\mathcal{O}}^{4}=\\{(x)\mid\textsf{ ForeignStudent}(x)\\}$ are such that
$\mathit{cert}_{q_{\mathcal{O}}^{3},J}^{D}=\\{(c_{1})\\}$ and
$\mathit{cert}_{q_{\mathcal{O}}^{4},J}^{D}=\\{(c_{2})\\}$, one can verify that
no perfect $\Sigma$-characterization of $\lambda$ in UCQ exists.

Notice the difference with the notion of _abstraction_ [13, 14], introduced in
[12] and studied under various scenarios [25, 15, 16]. In abstraction, we are
given an OBDM specification
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ and a query
$q_{\mathcal{S}}$ over $\mathcal{S}$, and the aim is to find a query
$q_{\mathcal{O}}$ over $\mathcal{O}$, called _the perfect $J$-abstraction of
$q_{\mathcal{S}}$_, such that
$\mathit{cert}_{q_{\mathcal{O}},J}^{D}=q_{\mathcal{S}}^{D}$ _for each
$\mathcal{S}$-database $D$_ for which $\langle J,D\rangle$ is consistent.
Conversely, here we are also given an $\mathcal{S}$-database $D$, and instead
of a query $q_{\mathcal{S}}$ we have a set of tuples $\lambda$ of constants
taken from $D$, and the aim is to find a query $q_{\mathcal{O}}$ over
$\mathcal{O}$ such that $\mathit{cert}_{q_{\mathcal{O}},J}^{D}=\lambda$. The
following proposition establishes the relationship between the notion of
characterization introduced here and the notion of abstraction.

###### Proposition 1

Let $\Sigma=\langle J,D\rangle$ be a consistent OBDM system, $\lambda$ be a
$D$-dataset, and $q_{\mathcal{S}}$ be a query that defines $\lambda$ inside
$D$. If a query $q_{\mathcal{O}}\in\mathcal{Q}$ is the perfect $J$-abstraction
of $q_{\mathcal{S}}$, then $q_{\mathcal{O}}$ is the perfect
$\Sigma$-characterization of $\lambda$ in $\mathcal{Q}$.

###### Proof

Suppose $q_{\mathcal{O}}\in\mathcal{Q}$ is the perfect $J$-abstraction of
$q_{\mathcal{S}}$, i.e.,
$\mathit{cert}_{q_{\mathcal{O}},J}^{D^{\prime}}=q_{\mathcal{S}}^{D^{\prime}}$
for each $\mathcal{S}$-database $D^{\prime}$ for which $\langle
J,D^{\prime}\rangle$ is consistent. Since $\Sigma=\langle J,D\rangle$ is
consistent and since $q_{\mathcal{S}}^{D}=\lambda$ by assumption that
$q_{\mathcal{S}}$ defines $\lambda$ inside $D$, we have that
$\mathit{cert}_{q_{\mathcal{O}},J}^{D}=q_{\mathcal{S}}^{D}=\lambda$, which
means that $q_{\mathcal{O}}$ is a perfect $\Sigma$-characterization of
$\lambda$ in $\mathcal{Q}$.

The next example shows that the converse of the above proposition does not
necessarily hold, thus stressing the fact that the two problems are indeed
different.

###### Example 2

Let $\Sigma=\langle J,D\rangle$ be as follows: (_i_)
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ is such that
$\mathcal{O}=\emptyset$, $\mathcal{S}=\\{s_{1},s_{2}\\}$, and
$\mathcal{M}=\\{m_{1},m_{2}\\}$ with $m_{1}=\\{(x)\mid
s_{1}(x)\\}\rightarrow\\{(x)\mid A(x)\\}$ and $m_{2}=\\{(x)\mid
s_{2}(x)\\}\rightarrow\\{(x)\mid A(x)\\}$; and (_ii_) $D=\\{s_{1}(c)\\}$.

For the $D$-dataset $\lambda=\\{(c)\\}$, one can verify that
$q_{\mathcal{S}}=\\{(x)\mid s_{1}(x)\\}$ is such that
$q_{\mathcal{S}}^{D}=\lambda$ and that $q_{\mathcal{O}}=\\{(x)\mid A(x)\\}$ is
such that $\mathit{cert}_{q_{\mathcal{O}},J}^{D}=\lambda$, i.e.,
$q_{\mathcal{O}}$ is the perfect $\Sigma$-characterization of $\lambda$ in CQ.
However, the query $q_{\mathcal{O}}$ is not a perfect $J$-abstraction of
$q_{\mathcal{S}}$, since for the $\mathcal{S}$-database
$D^{\prime}=\\{s_{2}(c)\\}$ we have
$\mathit{cert}_{q_{\mathcal{O}},J}^{D^{\prime}}=\\{(c)\\}$ whereas
$q_{\mathcal{S}}^{D^{\prime}}=\emptyset$.

Clearly, the more expressive the query language $\mathcal{Q}$, the more likely
we can express the implicit relationship between the tuples in $\lambda$ by
means of the operators in $\mathcal{Q}$, and therefore the more likely the
perfect characterization in $\mathcal{Q}$ exists. Unfortunately, the next
example shows that, even without any restriction on the query language,
perfect characterizations are not guaranteed to exist even in trivial cases.

###### Example 3

Recall the OBDM specification $J$ of the previous example, and let
$\Sigma=\langle J,D\rangle$ be the OBDM system with
$D=\\{s_{1}(c_{1}),s_{2}(c_{2})\\}$. For the $D$-dataset
$\lambda=\\{(c_{1})\\}$, one can trivially verify that, whatever is the query
language $\mathcal{Q}$, there is no query $q_{\mathcal{O}}\in\mathcal{Q}$ for
which $\mathit{cert}_{q_{\mathcal{O}},J}^{D}=\lambda$.

Note the importance of the role played by the mapping $\mathcal{M}$ in order
to reach this conclusion. Indeed, if we replace $m_{2}$ with $\\{(x)\mid
s_{2}(x)\\}\rightarrow\\{(x)\mid B(x)\\}$, then the perfect
$\Sigma$-characterization of $\lambda$ would be the CQ $\\{(x)\mid A(x)\\}$.

Borrowing the ideas from [15] to remedy situations where perfect abstractions
do not exist, we now introduce approximations of perfect characterizations in
terms of recall (complete) and precision (sound).

###### Definition 2

$q_{\mathcal{O}}\in\mathcal{Q}$ is a _complete_ (resp., _sound_)
$\Sigma$-_characterization_ of $\lambda$ in the query language $\mathcal{Q}$,
if $\lambda\subseteq cert^{D}_{q_{\mathcal{O}},J}$ (resp.,
$cert^{D}_{q_{\mathcal{O}},J}\subseteq\lambda$).

###### Example 4

Refer to Example 1. We have that $q_{\mathcal{O}}^{1}$ and
$q_{\mathcal{O}}^{2}$ are complete $\Sigma$-characterization of $\lambda$,
whereas $q_{\mathcal{O}}^{3}$ and $q_{\mathcal{O}}^{4}$ are sound
$\Sigma$-characterization of $\lambda$.

As the above example manifests, there may be several complete and sound
characterizations relative to a query language $\mathcal{Q}$. In those cases,
the interest is unquestionably in those that best approximate the perfect one.

###### Definition 3

$q_{\mathcal{O}}$ is a $\mathcal{Q}$-_minimally complete_ (resp.,
$\mathcal{Q}$-_maximally sound_) $\Sigma$-_characterization_ of $\lambda$, if
$q_{\mathcal{O}}$ is a complete (resp., sound) $\Sigma$-characterization of
$\lambda$ in $\mathcal{Q}$ and there is no
$q^{\prime}_{\mathcal{O}}\in\mathcal{Q}$ such that (_i_)
$q^{\prime}_{\mathcal{O}}$ is a _complete_ (resp., sound)
$\Sigma$-characterization of $\lambda$ and (_ii_)
$cert^{D}_{q^{\prime}_{\mathcal{O}},J}\subset cert^{D}_{q_{\mathcal{O}},J}$
(resp., $cert^{D}_{q_{\mathcal{O}},J}\subset
cert^{D}_{q^{\prime}_{\mathcal{O}},J}$).

###### Example 5

Refer again to Example 1. The CQ $q_{\mathcal{O}}^{1}$ is a UCQ-minimally
complete $\Sigma$-characterization of $\lambda$, whereas $q_{\mathcal{O}}^{2}$
is not. Both $q_{\mathcal{O}}^{3}$ and $q_{\mathcal{O}}^{4}$ are CQ-maximally
sound $\Sigma$-characterizations of $\lambda$, but neither of them is a UCQ-
maximally sound $\Sigma$-characterization of $\lambda$. Indeed, a UCQ-
maximally sound $\Sigma$-characterization of $\lambda$ is
$q_{\mathcal{O}}^{5}=q_{\mathcal{O}}^{3}\cup q_{\mathcal{O}}^{4}$.

Given this general framework, there are (at least) three computational
problems to consider, with respect to an ontology language
$\mathcal{L}_{\mathcal{O}}$, a mapping language $\mathcal{L}_{\mathcal{M}}$,
and a query language $\mathcal{Q}$. Given an OBDM system
$\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$ and
a $D$-dataset $\lambda$, where $\mathcal{O}\in\mathcal{L}_{\mathcal{O}}$ and
$\mathcal{M}\in\mathcal{L}_{\mathcal{M}}$:

  * •

_Verification:_ given $q_{\mathcal{O}}\in\mathcal{Q}$, check whether
$q_{\mathcal{O}}$ is a perfect (resp., complete, sound)
$\Sigma$-characterization of $\lambda$.

  * •

_Computation:_ compute the perfect in $\mathcal{Q}$ (resp.,
$\mathcal{Q}$-minimally complete, or $\mathcal{Q}$-maximally sound)
$\Sigma$-characterization of $\lambda$, provided it exists.

  * •

_Existence:_ check whether there exists a perfect in $\mathcal{Q}$ (resp.,
$\mathcal{Q}$-minimally complete, or $\mathcal{Q}$-maximally sound)
$\Sigma$-characterization of $\lambda$.

In what follows, if not otherwise stated, we refer to the following scenario
which considers by far the most popular languages for the OBDM paradigm: (_i_)
$\mathcal{L}_{\mathcal{O}}$ is $\textit{DL-Lite}_{\mathcal{R}}$, (_ii_)
$\mathcal{L}_{\mathcal{M}}$ is GLAV, and (_iii_) $\mathcal{Q}$ is UCQ.

In this scenario, there are two interesting properties that are worth
mentioning. First, since the UCQ language allows for the conjunction (resp.,
union) operator, if an UCQ-minimally complete (resp., UCQ-maximally sound)
$\Sigma$-characterization of $\lambda$ exists, then it is unique up to
$\Sigma$-equivalence.

###### Proposition 2

If $q_{1}$ and $q_{2}$ are UCQ-minimally complete (resp., UCQ-maximally sound)
$\Sigma$-characterizations of $\lambda$, then they are equivalent w.r.t.
$\Sigma$.

###### Proof

Similar to [13, Proposition 3.2].

Due to the above property, in what follows we simply refer to _the_ UCQ-
minimally complete (resp., UCQ-maximally sound) $\Sigma$-characterization of
$\lambda$.

Second, as expected, in this scenario perfect characterizations are less
likely to exist than in the plain relational database case.

###### Proposition 3

Let $\Sigma=\langle J,D\rangle$ be a consistent OBDM system, and $\lambda$ be
a $D$-dataset. If there exists a perfect $\Sigma$-characterization of
$\lambda$ in UCQ, then $\lambda$ is UCQ-definable inside $D$.

###### Proof

Suppose there exists a perfect $\Sigma$-characterization of $\lambda$ in UCQ,
i.e., there is a UCQ $q_{\mathcal{O}}$ over $\mathcal{O}$ for which
$\mathit{cert}_{q_{\mathcal{O}},J}^{D}=\lambda$. Recall from Section 2 that
the UCQ $\mathsf{rew}_{q_{\mathcal{O}},J}$ over $\mathcal{S}$ is such that
$\mathit{cert}_{q_{\mathcal{O}},J}^{D^{\prime}}=\mathsf{rew}_{q_{\mathcal{O}},J}^{D^{\prime}}$
for each $\mathcal{S}$-database $D^{\prime}$ for which $\langle
J,D^{\prime}\rangle$ is consistent. Since $\Sigma=\langle J,D\rangle$ is
consistent, we have
$\lambda=\mathit{cert}_{q_{\mathcal{O}},J}^{D}=\mathsf{rew}_{q_{\mathcal{O}},J}^{D}$,
from which immediately follows that $\mathsf{rew}_{q_{\mathcal{O}},J}$ defines
$\lambda$ inside $D$, and thus $\lambda$ is UCQ-definable inside $D$.

In general, the converse of the above proposition does not hold. Indeed, in
Example 3, while there is no perfect $\Sigma$-characterization of $\lambda$ in
any query language $\mathcal{Q}$, the CQ $q_{\mathcal{S}}=\\{(x)\mid
s_{1}(x)\\}$ witnesses that $\lambda$ is CQ-definable inside $D$.

##  4 Verification

We now define the verification problems for $X$-query definability
($X$-VQDEF), where $X$={Perfect, Complete, Sound}. These decision problems are
parametric with respect to the ontology language $\mathcal{L}_{\mathcal{O}}$
to express $\mathcal{O}$, the mapping language $\mathcal{L}_{\mathcal{M}}$ to
express $\mathcal{M}$, and the query language $\mathcal{Q}$ to express
$q_{\mathcal{O}}$.

Problem: X-VQDEF($\mathcal{L}_{\mathcal{O}}$, $\mathcal{L}_{\mathcal{M}}$,
$\mathcal{Q}$) Input: An OBDM system
$\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$, a
$D$-dataset $\lambda$, and a query $q_{\mathcal{O}}\in\mathcal{Q}$ over
$\mathcal{O}$, where $\mathcal{O}\in\mathcal{L}_{\mathcal{O}}$ and
$\mathcal{M}\in\mathcal{L}_{\mathcal{M}}$. Question: Is $q_{\mathcal{O}}$ a X
$\Sigma$-characterization of $\lambda$?

In what follows, given a syntactic object $x$ such as a query, an ontology, or
a mapping, we denote by $\sigma(x)$ its size.

###### Theorem 4.1

Complete-VQDEF($\textit{DL-Lite}_{\mathcal{R}}$, GLAV, UCQ) is in NP.

###### Proof

We now show how to check whether $q_{\mathcal{O}}$ is a complete
$\Sigma$-characterization of $\lambda$ (i.e.,
$\lambda\subseteq\mathit{cert}_{q_{\mathcal{O}},J}^{D}$) in NP, where
$\Sigma=\langle J,D\rangle$ with
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$.

Let $n$ be the arity of the tuples in the $D$-dataset $\lambda$. For each
$n$-tuple of constants $\vec{c}\in\lambda$, we first guess (_i_) a CQ
$q^{\prime}_{\mathcal{O}}$ over $\mathcal{O}$ which is either of arity $n$ and
size at most $\sigma(q_{\mathcal{O}})$, or a boolean one capturing a
disjointness assertion $d$ (e.g., $\\{()\mid\exists y\mbox{\bf.}A_{1}(y)\wedge
A_{2}(y)\\}$ capturing $d=A_{1}\sqsubseteq\neg A_{2}$); (_ii_) a sequence
$\rho_{\mathcal{O}}$ of ontology assertions; (_iii_) a CQ $q_{\mathcal{S}}$
over $\mathcal{S}$ of size at most
$\sigma(\mathcal{M})\cdot\sigma(q^{\prime}_{\mathcal{O}})$ which is either of
arity $n$ and of the form
$\\{\vec{x}\mid\exists\vec{y}\mbox{\bf.}\phi_{\mathcal{S}}(\vec{x},\vec{y})\\}$,
or a boolean one of the form
$\\{()\mid\exists\vec{y}\mbox{\bf.}\phi_{\mathcal{S}}(\vec{y})\\}$; (_iv_) a
sequence $\rho_{\mathcal{M}}$ of mapping assertions; and (_v_) a function $f$
from the variables occurring in $q_{\mathcal{S}}$ to $\mathit{dom}(D)$.

Then, we check in polynomial time whether (_i_) by means of
$\rho_{\mathcal{O}}$, either we can rewrite a disjunct of $q_{\mathcal{O}}$
into $q^{\prime}_{\mathcal{O}}$ through $\mathcal{O}$ (i.e.,
$q^{\prime}_{\mathcal{O}}\in\mathsf{PerfectRef}(\mathcal{O},q_{\mathcal{O}})$),
or we can rewrite a disjunct of $V_{\mathcal{O}}$ into
$q^{\prime}_{\mathcal{O}}$ through $\mathcal{O}$ (i.e.,
$q^{\prime}_{\mathcal{O}}\in\mathsf{PerfectRef}(\mathcal{O},V_{\mathcal{O}})$);
(_ii_) by means of $\rho_{\mathcal{M}}$ we can rewrite
$q^{\prime}_{\mathcal{O}}$ into $q_{\mathcal{S}}$ through $\mathcal{M}$ (i.e.,
$q_{\mathcal{S}}\in\mathsf{MapRef}(\mathcal{M},q^{\prime}_{\mathcal{O}})$, and
thus either $q^{\prime}_{\mathcal{O}}\in\mathsf{rew}_{q_{\mathcal{O}},J}$ or
$q^{\prime}_{\mathcal{O}}\in\mathsf{rew}_{V_{\mathcal{O}},J}$); and finally
(_iii_) $f$ consists in a homomorphism witnessing either
$(\mathit{set}(\phi_{\mathcal{S}}),\vec{x})\rightarrow(D,\vec{c})$, i.e.,
$\vec{c}\in q_{\mathcal{S}}^{D}$ (and therefore
$\vec{c}\in\mathsf{rew}_{q_{\mathcal{O}},J}^{D}$, which means
$\vec{c}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$), or
$(\mathit{set}(\phi_{\mathcal{S}}),())\rightarrow(D,())$, i.e., $D\models
q_{\mathcal{S}}$ (and therefore
$\mathsf{rew}_{V_{\mathcal{O}},J}^{D}=\\{\langle\rangle\\}$, which means that
$\Sigma$ is inconsistent and thus
$\vec{c}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$ by definition).

###### Theorem 4.2

Sound-VQDEF($\textit{DL-Lite}_{\mathcal{R}}$, GLAV, UCQ) is in coNP.

###### Proof

We now show how to check whether $q_{\mathcal{O}}$ is not a sound
$\Sigma$-characterization of $\lambda$ (i.e.,
$\mathit{cert}_{q_{\mathcal{O}},J}^{D}\not\subseteq\lambda$) in NP, where
$\Sigma=\langle J,D\rangle$ with
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$.

We first guess (_i_) a tuple of constants $\vec{c}$, and, exactly as in the
proof of Theorem 4.1, (_ii_) $q^{\prime}_{\mathcal{O}}$, $\rho_{\mathcal{O}}$,
$q_{\mathcal{S}}$, $\rho_{\mathcal{M}}$, and $f$. Then, we check in polynomial
time whether (_i_) $\vec{c}$ contains only constants from $\mathit{dom}(D)$
and $\vec{c}\not\in\lambda$ (i.e.,
$\vec{c}\in\mathit{dom}(D)^{n}\setminus\lambda$), and (_ii_) using
$q^{\prime}_{\mathcal{O}}$, $\rho_{\mathcal{O}}$, $q_{\mathcal{S}}$,
$\rho_{\mathcal{M}}$, and $f$, we follow exactly the same polynomial time
procedure in the proof of Theorem 4.1 to check whether
$\vec{c}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$.

Recall that a decision problem is in DP if and only if it is the conjunction
of a decision problem in NP and a decision problem in coNP [30]. Since
$q_{\mathcal{O}}$ is a perfect $\Sigma$-characterization of $\lambda$ if and
only if it is both a sound, and a complete $\Sigma$-characterization of
$\lambda$, we immediately derive the following upper bound.

###### Corollary 1

Perfect-VQDEF($\textit{DL-Lite}_{\mathcal{R}}$, GLAV, UCQ) is in DP.

We now provide matching lower bounds. We show that they already hold for the
same, very simple, fixed OBDM system $\Sigma$ and dataset $\lambda$, and for
single, unary CQs as queries.

###### Theorem 4.3

There is an OBDM system
$\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$
such that $\mathcal{O}=\emptyset$ and $\mathcal{M}$ is a GAV$\cap$LAV mapping,
and a $D$-dataset $\lambda$ containing only a unary tuple for which the
problem Complete-VQDEF($\emptyset$, GAV$\cap$LAV, CQ) (resp., Sound-
VQDEF($\emptyset$, GAV$\cap$LAV, CQ), Perfect-VQDEF($\emptyset$, GAV$\cap$LAV,
CQ)) is NP-hard (resp., coNP-hard, DP-hard).

###### Proof

Let $\Sigma=\langle J,D\rangle$ be the OBDM system such that (_i_)
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ is an OBDM specification
in which $\mathcal{O}=\emptyset$ is an empty ontology whose alphabet contains
two atomic roles $P_{1}$ and $P_{2}$, $\mathcal{S}=\\{s_{1},s_{2}\\}$, and
$\mathcal{M}$ contains the following two GAV$\cap$LAV assertions:

$\displaystyle\\{(x_{1},x_{2})\mid
s_{1}(x_{1},x_{2})\\}\rightarrow\\{(x_{1},x_{2})\mid P_{1}(x_{1},x_{2})\\},$
$\displaystyle\\{(x_{1},x_{2})\mid
s_{2}(x_{1},x_{2})\\}\rightarrow\\{(x_{1},x_{2})\mid P_{2}(x_{1},x_{2})\\},$

which simply mirrors source predicate $s_{i}$ to atomic role $P_{i}$, for
$i=[1,2]$, and (_ii_) $D$ is the $\mathcal{S}$-database composed of the
following facts:

$\displaystyle\\{s_{1}(x,y)\mid x=\\{r^{\prime},g^{\prime},b^{\prime}\\}\text{
and }y=\\{r^{\prime},g^{\prime},b^{\prime}\\}\text{ and }x\neq y\\}\cup$
$\displaystyle\\{s_{1}(x,y)\mid x=\\{r,g,b,y\\}\text{ and
}y=\\{r,g,b,y\\}\text{ and }x\neq y\\}\cup$
$\displaystyle\\{s_{2}(x,c_{3})\mid
x=\\{r^{\prime},g^{\prime},b^{\prime}\\}\\}\cup\\{s_{2}(x,c_{4})\mid
x=\\{r,g,b,y\\}\\}.$

Let, moreover, $\lambda$ be the $D$-dataset $\lambda=\\{(c_{4})\\}$.

Let $G=(V,E)$ be a finite and undirected graph without loops or isolated
nodes, where $V=\\{y_{1},\ldots,y_{n}\\}$. We define a CQ
$q_{G}=\\{(x)\mid\exists\vec{y}\mbox{\bf.}\phi_{\mathcal{O}}(x,\vec{y})\\}$
over $\mathcal{O}$ as follows:

$q_{G}=\\{(x)\mid\exists
y_{1},\ldots,y_{n}\mbox{\bf.}\bigwedge_{(y_{i},y_{j})\in
E}(P_{1}(y_{i},y_{j}))~{}\wedge\bigwedge_{y_{i}\in V}(P_{2}(y_{i},x))\\}$

Finally, notice that the CQ $q_{G}$ can be constructed in LogSpace from an
input graph $G$.

By inspecting the OBDM system $\Sigma=\langle J,D\rangle$, for any graph $G$,
the set of certain answers $\mathit{cert}_{q_{G},J}^{D}$ is an element of the
power set of $\\{(c_{3}),(c_{4})\\}$. More specifically, the following
property holds:

###### Claim

For both $i=3$ and $i=4$, we have that a graph $G=(V,E)$ is $i$-colourable if
and only if $(c_{i})\in\mathit{cert}_{q_{G},D}^{D}$.

###### Proof

First of all, notice that $\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)}$ is
composed of the following facts:

$\displaystyle\\{P_{1}(x,y)\mid x=\\{r^{\prime},g^{\prime},b^{\prime}\\}\text{
and }y=\\{r^{\prime},g^{\prime},b^{\prime}\\}\text{ and }x\neq y\\}\cup$
$\displaystyle\\{P_{1}(x,y)\mid x=\\{r,g,b,y\\}\text{ and
}y=\\{r,g,b,y\\}\text{ and }x\neq y\\}\cup$
$\displaystyle\\{P_{2}(x,c_{3})\mid
x=\\{r^{\prime},g^{\prime},b^{\prime}\\}\\}\cup\\{P_{2}(x,c_{4})\mid
x=\\{r,g,b,y\\}\\}.$

“Only-if part:” Suppose $G=(V,E)$ is 3-colourable (resp., 4-colourable), that
is, there exists a function
$f:V\rightarrow\\{r^{\prime},g^{\prime},b^{\prime}\\}$ (resp.,
$f:V\rightarrow\\{r,g,b,y\\}$) such that $f(y_{i})\neq f(y_{j})$ for each
$(y_{i},y_{j})\in E$. Let $\phi_{\mathcal{O}}$ be the body of $q_{G}$, and
consider the extension of $f$ which assigns to the distinguished variable $x$
of $q_{G}$ the constant $c_{3}$ (resp., $c_{4}$). It can be readily seen that
$f$ consists in a homomorphism from $\mathit{set}(\phi_{\mathcal{O}})$ to
$\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)}$ such that $f(x)=c_{3}$ (resp.,
$f(x)=c_{4}$). In other words, $f$ witnesses that
$(\mathit{set}(\phi_{\mathcal{O}}),(x))\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},(c_{3}))$
(resp.,
$(\mathit{set}(\phi_{\mathcal{O}}),(x))\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},(c_{4}))$).
Thus, $(c_{3})\in\mathit{cert}_{q_{G},J}^{D}$ (resp.,
$(c_{4})\in\mathit{cert}_{q_{G},J}^{D}$), as required.

“If part:” Suppose $G=(V,E)$ is not 3-colourable (resp., not 4-colourable),
that is, each possible function
$f:V\rightarrow\\{r^{\prime},g^{\prime},b^{\prime}\\}$ (resp.,
$f:V\rightarrow\\{r,g,b,y\\}$) is such that $f(y_{i})=f(y_{j})$ for some
$(y_{i},y_{j})\in E$. Clearly, this implies that
$(\mathit{set}(\phi_{\mathcal{O}}),(x))\not\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},(c_{3}))$
(resp.,
$(\mathit{set}(\phi_{\mathcal{O}}),(x))\not\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},(c_{4}))$).
Thus, $(c_{3})\not\in\mathit{cert}_{q_{G},J}^{D}$ (resp.,
$(c_{4})\not\in\mathit{cert}_{q_{G},J}^{D}$), as required. ∎

With the above property at hand, and the fact that
$\mathit{cert}_{q_{G},J}^{D}$ is an element of the power set of
$\\{(c_{3}),(c_{4})\\}$ for each possible finite and undirected graph
$G=(V,E)$ without loops or isolated nodes, we are now ready to prove the
claimed lower bounds.

As for the complete case, the proof of NP-hardness is by a LogSpace reduction
from the _4-colourability problem_ , which is NP-complete [21]. In particular,
a graph $G$ is 4-colourable if and only if
$(c_{4})\in\mathit{cert}_{q_{G},J}^{D}$, i.e., if and only if
$\lambda\subseteq\mathit{cert}_{q_{G},J}^{D}$. So, checking whether the CQ
$q_{G}$ is a complete $\langle\mathcal{O},\Sigma\rangle$-explanation of
$\lambda$ is NP-hard.

As for the sound case, the proof of coNP-hardness is by a LogSpace reduction
from the _complement of 3-colourability problem_ , which is coNP-complete
[21]. In particular, a graph $G$ is not 3-colourable if and only if
$(c_{3})\not\in\mathit{cert}_{q_{G},J}^{D}$, i.e., if and only if
$\mathit{cert}_{q_{G},J}^{D}\subseteq\lambda$. So, checking whether the CQ
$q_{G}$ is a sound $\langle\mathcal{O},\Sigma\rangle$-explanation of $\lambda$
is coNP-hard.

Finally, as for the perfect case, the proof of DP-hardness is by a LogSpace
reduction from the _exact-4-colourability problem_ , which is DP-complete
[33]. In particular, a graph $G$ is exact-4-colourable (i.e., 4-colourable and
not 3-colourable) if and only if $\mathit{cert}_{q_{G},J}^{D}=\\{(c_{4})\\}$,
i.e., if and only if $\mathit{cert}_{q_{G},J}^{D}=\lambda$. So, checking
whether the CQ $q_{G}$ is a perfect
$\langle\mathcal{O},\Sigma\rangle$-explanation of $\lambda$ is DP-hard. ∎

###### Corollary 2

Complete-VQDEF($\textit{DL-Lite}_{\mathcal{R}}$, GLAV, UCQ), Sound-
VQDEF($\textit{DL-Lite}_{\mathcal{R}}$, GLAV, UCQ), and Perfect-
VQDEF($\textit{DL-Lite}_{\mathcal{R}}$, GLAV, UCQ) are NP-complete, coNP-
complete, and DP-complete, respectively.

Finally, the lower bound proof of Theorem 4.3 can be easily adapted for the
plain relational database case. Thus, given a schema $\mathcal{S}$, an
$\mathcal{S}$-database $D$, a $D$-dataset $\lambda$, and a UCQ
$q_{\mathcal{S}}$ over $\mathcal{S}$, it is DP-complete the problem of
deciding whether $q_{\mathcal{S}}$ defines $\lambda$ inside $D$ (the DP
membership of this problem directly follows from Corollary 1).

##  5 Computation

In this section, we address the computation problem. We start by considering
the case when the OBDM system $\Sigma$ at hand is inconsistent as a separate
case. Given an inconsistent OBDM system $\Sigma=\langle J,D\rangle$ and a
$D$-dataset $\lambda$ of arity $n$, we point out that any query
$q_{\mathcal{O}}$ over the ontology $\mathcal{O}$ of the OBDM specification
$J$ is the UCQ-minimally complete $\Sigma$-characterization of $\lambda$
(recall that the certain answers of any query $q_{\mathcal{O}}$ of arity $n$
w.r.t. an inconsistent OBDM system $\Sigma$ is the set of all possible
$n$-tuples of constants occurring in $D$). Furthermore, if
$\lambda=\mathit{dom}(D)^{n}$, then any query $q_{\mathcal{O}}$ is also the
UCQ-maximally sound (and therefore the perfect) $\Sigma$-characterization of
$\lambda$; otherwise, i.e., $\lambda\subsetneq\mathit{dom}(D)^{n}$, no sound
(and therefore, no UCQ-maximally sound and no perfect)
$\Sigma$-characterization of $\lambda$ exists.

Having thoroughly covered the case of inconsistent OBDM systems, in what
follows in this section, unless otherwise stated, we implicitly assume to only
deal with consistent OBDM systems.

Specifically, given a consistent OBDM system $\Sigma=\langle J,D\rangle$ and a
$D$-dataset $\lambda$, we provide exponential time algorithms for computing
UCQ-minimally complete and UCQ-maximally sound $\Sigma$-characterizations of
$\lambda$, thus proving that, in this case, they always exist. As already
observed in Proposition 2, in our scenario all UCQ-minimally complete (resp.,
UCQ-maximally sound) characterizations of $\lambda$ are unique up to logical
equivalence w.r.t. $\Sigma$, and therefore we refer to _the_ UCQ-minimally
complete (resp., UCQ-maximally sound) $\Sigma$-characterization of $\lambda$.

Before illustrating the main techniques to compute such best
characterizations, we provide two crucial properties about the canonical
structure that we will use to establish the correctness of our algorithms.

###### Proposition 4

Let $\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$
be an OBDM system, $q_{\mathcal{O}}$ be a UCQ over $\mathcal{O}$, and
$\vec{c}$ and $\vec{b}$ be two tuples of constants such that
$(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$.
If $\vec{c}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$, then
$\vec{b}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$.

###### Proof

If $\Sigma$ is inconsistent, the claim is trivial. If $\Sigma$ is consistent,
from Section 2 we know that $\vec{c}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$
implies the existence of a disjunct
$q=\\{\vec{x}\mid\exists\vec{y}\mbox{\bf.}\phi(\vec{x},\vec{y})\\}$ in
$q_{\mathcal{O}}$ for which
$(\mathit{set}(\phi),\vec{x})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})$.
Let $h$ be the homomorphism witnessing that
$(\mathit{set}(\phi),\vec{x})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})$,
and let $h^{\prime}$ be the homomorphism witnessing that
$(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$,
which holds by the premises of the proposition. The composition function
$h^{\prime\prime}=h^{\prime}\circ h$ is then a homomorphism witnessing that
$(\mathit{set}(\phi),\vec{x})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$.
It follows that $\vec{b}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$, as
required.∎

###### Proposition 5

Let $\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$
be a consistent OBDM system, $\vec{b}$ and $\vec{c}$ be two tuples of
constants, and $q_{\vec{c}}$ be the CQ
$q_{\vec{c}}=\mathit{query}(\mathcal{M}(D),\vec{c})$. We have that
$\vec{b}\in\mathit{cert}_{q_{\vec{c}},J}^{D}$ if and only if
$(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$.

###### Proof

Suppose that
$(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$,
and let $h$ be the homomorphism witnessing it. Consider the query
$q_{\vec{c}}=\mathit{query}(\mathcal{M}(D),\vec{c})=\\{\vec{x}\mid\exists\vec{y}\mbox{\bf.}\phi(\vec{x},\vec{y})\\}$.
Observe that $\mathit{set}(\phi)$ is obtained from $\mathcal{M}(D)$ by
appropriately replacing each occurrence of each constant
$c\in\mathit{dom}(\mathcal{M}(D))$ either with a distinguished variable
$x_{c}\in\vec{x}$ or with an existential variable $y_{c}\in\vec{y}$. This
means that $h$ can be immediately transformed into a homomorphism witnessing
that
$(\mathit{set}(\phi),\vec{x})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$,
thus implying that $\vec{b}\in\mathit{cert}_{q_{\vec{c}},J}^{D}$.

Suppose now that $\vec{b}\in\mathit{cert}_{q_{\vec{c}},J}^{D}$. Since $\Sigma$
is consistent, it follows that there is a homomorphism $h$ witnessing that
$(\mathit{set}(\phi),\vec{x})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$,
where
$q_{\vec{c}}=\mathit{query}(\mathcal{M}(D),\vec{c})=\\{\vec{x}\mid\exists\vec{y}\mbox{\bf.}\phi(\vec{x},\vec{y})\\}$.
By considering again the relationship between $\mathit{set}(\phi)$ and
$\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)}$, the homomorphism $h$ can be
immediately transformed into a homomorphism $h^{\prime}$ that witnesses
$(\mathcal{M}(D),\vec{c})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$.
It is now not hard to verify that $h^{\prime}$ can be extended into a
homomorphism $h^{\prime\prime}$ witnessing that
$(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$.

We are now ready to present our techniques. We start with the complete case,
and provide the algorithm MinCompCharacterization for computing UCQ-minimally
complete characterizations.

Algorithm MinCompCharacterization

1:

2:OBDM system $\Sigma=\langle J,D\rangle$ with
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$;

3:$D$-dataset $\lambda=\\{\vec{c_{1}},\ldots,\vec{c_{n}}\\}$

4:

5:UCQ $q_{\mathcal{O}}$ over $\mathcal{O}$

6:

7:Compute $\mathcal{M}(D)$

8:$q_{\mathcal{O}}\leftarrow query(\mathcal{M}(D),\vec{c_{1}})$
$\cup\ldots\cup query(\mathcal{M}(D),\vec{c_{n}})$

9:return $q_{\mathcal{O}}$

Informally, for each $\vec{c_{i}}\in\lambda$, the algorithm obtains from the
set of atoms $\mathcal{M}(D)$ the CQ
$\mathit{query}(\mathcal{M}(D),\vec{c_{i}})$. Finally, the output is the union
of all such CQs.

###### Example 6

Let $J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ be the same OBDM
specification of Example 1. One can verify that for the $\mathcal{S}$-database
$D=\\{s_{1}(c_{1}),s_{3}(c_{2},b),s_{3}(c_{3},b)\\}$ and the $D$-dataset
$\lambda=\\{(c_{1}),(c_{2})\\}$, MinCompCharacterization($\langle
J,D\rangle,\lambda$) returns the UCQ
$q_{\mathcal{O}}=\mathit{query}(\mathcal{M}(D),(c_{1}))$ $\cup$
$\mathit{query}(\mathcal{M}(D),(c_{2}))$, where
$\mathit{query}(\mathcal{M}(D),(c_{1}))$ = $\\{(x_{c_{1}})\mid\exists
y_{c_{2}},y_{c_{3}},y_{b}\mbox{\bf.}\textsf{Student}(x_{c_{1}})\wedge\textsf{EnrolledIn}(y_{c_{2}},y_{b})\wedge\textsf{EnrolledIn}(y_{c_{3}},y_{b})\\}$
and $\mathit{query}(\mathcal{M}(D),(c_{2}))$ = $\\{(x_{c_{2}})\mid\exists
y_{c_{1}},y_{c_{3}},y_{b}\mbox{\bf.}\textsf{EnrolledIn}(x_{c_{2}},y_{b})\wedge\textsf{EnrolledIn}(y_{c_{3}},y_{b})\wedge\textsf{Student}(y_{c_{1}})\\}$.
Furthermore, one can see that $q_{\mathcal{O}}$ is the UCQ-minimally complete
$\Sigma$-characterization of $\lambda$, where $\Sigma=\langle J,D\rangle$.

The following theorem establishes termination and correctness of the
MinCompCharacterization algorithm.

###### Theorem 5.1

MinCompCharacterization($\Sigma,\lambda$) terminates and returns the UCQ-
minimally complete $\Sigma$-characterization of $\lambda$.

###### Proof

Termination of the algorithm as well as completeness of the UCQ
$q_{\mathcal{O}}$ returned are straightforward.

To prove that $q_{\mathcal{O}}$ is also the UCQ-minimally complete
$\Sigma$-characterization of $\lambda$, it is enough to show that any query
$q$ over $\mathcal{O}$ that is a complete $\Sigma$-characterization of
$\lambda$ is such that
$\mathit{cert}_{q_{\mathcal{O}},J}^{D}\subseteq\mathit{cert}_{q,J}^{D}$, where
$\Sigma=\langle J,D\rangle$. We do this by contraposition. Let $q$ be a UCQ
for which
$\mathit{cert}_{q_{\mathcal{O}},J}^{D}\not\subseteq\mathit{cert}_{q,J}^{D}$,
i.e., for a tuple of constants $\vec{b}$ we have
$\vec{b}\not\in\mathit{cert}_{q,J}^{D}$ but
$\vec{b}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$. This latter means that
$\vec{b}\in\mathit{cert}_{q_{\vec{c}},J}^{D}$ for some
$q_{\vec{c}}=\mathit{query}(\mathcal{M}(D),\vec{c})$ with $\vec{c}\in\lambda$.
By Proposition 5, one can see that
$\vec{b}\in\mathit{cert}_{q_{\vec{c}},J}^{D}$ implies
$(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$.
By Proposition 4, it follows that each UCQ $q^{\prime}$ over $\mathcal{O}$
containing tuple $\vec{c}$ in its set of certain answers w.r.t. $\Sigma$ must
contain also tuple $\vec{b}$ in such a set. Thus, since
$\vec{b}\not\in\mathit{cert}_{q,J}^{D}$, we derive that
$\vec{c}\not\in\mathit{cert}_{q,J}^{D}$ as well. Since $\vec{c}\in\lambda$,
this latter clearly implies that $q$ is not a complete
$\Sigma$-characterization of $\lambda$, as required.∎

We now turn to the sound case, and provide the algorithm
MaxSoundCharacterization for computing UCQ-maximally sound
$\Sigma$-characterizations.

Algorithm MaxSoundCharacterization

1:

2:Consistent OBDM system $\Sigma=\langle J,D\rangle$ with
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$;

3:$D$-dataset $\lambda=\\{\vec{c_{1}},\ldots,\vec{c_{m}}\\}$ of arity $n$

4:

5:UCQ $q_{\mathcal{O}}$ over $\mathcal{O}$

6:

7:$\lambda^{-}\leftarrow\mathit{dom}(D)^{n}\setminus\lambda$

8:$q_{\mathcal{O}}\leftarrow\\{\vec{x}\mid\bot(\vec{x})\\}$, where
$\vec{x}=(x_{1},\ldots,x_{n})$

9:Compute $\mathcal{M}(D)$

10:for each $i\leftarrow 1,\ldots,m$ do

11: $q_{i}\leftarrow query(\mathcal{M}(D),\vec{{c_{i}}})$

12: if $cert^{D}_{q_{i},J}\cap\lambda^{-}=\emptyset$ then

13: $q_{\mathcal{O}}\leftarrow q_{\mathcal{O}}\cup q_{i}$

14: end if

15:end for

16:return $q_{\mathcal{O}}$

Intuitively, starting from the UCQ
$\mathit{query}(\mathcal{M}(D),\vec{c_{1}})\cup\ldots\cup\mathit{query}(\mathcal{M}(D),\vec{c_{m}})$,
the algorithm simply discards all those disjuncts whose set of certain answers
w.r.t. $\Sigma$ contain a tuple $\vec{b}\not\in\lambda$. We recall from
Section 2 that the set of certain answers of a CQ $q_{i}$ w.r.t. a consistent
OBDM system $\Sigma=\langle J,D\rangle$ can be computed by first obtaining its
reformulation $\mathsf{rew}_{q_{i},J}$ over the source schema $\mathcal{S}$,
and then by evaluating this latter query directly over the
$\mathcal{S}$-database $D$.

###### Example 7

Refer to Example 6. Since the certain answers of
$\mathit{query}(\mathcal{M}(D),(c_{2}))$ w.r.t. $\Sigma=\langle J,D\rangle$
include also $(c_{3})\not\in\lambda$,
MaxSoundCharacterization($\Sigma,\lambda$) returns the CQ
$q_{\mathcal{O}}=\mathit{query}(\mathcal{M}(D),(c_{1}))$, which is the UCQ-
maximally sound $\Sigma$-characterization of $\lambda$.

The following theorem establishes termination and correctness of the
MaxSoundCharacterization algorithm.

###### Theorem 5.2

MaxSoundCharacterization($\Sigma,\lambda$) terminates and returns the UCQ-
maximally sound $\Sigma$-characterization of $\lambda$.

###### Proof

Termination of the algorithm as well as soundness of the UCQ $q_{\mathcal{O}}$
returned are straightforward.

To prove that $q_{\mathcal{O}}$ is also the UCQ-maximally sound
$\Sigma$-characterization of $\lambda$, it is enough to show that any query
$q$ over $\mathcal{O}$ that is a sound $\Sigma$-characterization of $\lambda$
is such that
$\mathit{cert}_{q,J}^{D}\subseteq\mathit{cert}_{q_{\mathcal{O}},J}^{D}$, where
$\Sigma=\langle J,D\rangle$. We do this by contraposition. Let $q$ be a UCQ
for which
$\mathit{cert}_{q,J}^{D}\not\subseteq\mathit{cert}_{q_{\mathcal{O}},J}^{D}$,
i.e., for a tuple of constants $\vec{b}$ we have
$\vec{b}\in\mathit{cert}_{q,J}^{D}$ but
$\vec{b}\not\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$. If
$\vec{b}\not\in\lambda$, then we immediately get that $q$ is not a sound
$\Sigma$-characterization of $\lambda$, and we are done. So, assume that
$\vec{b}\in\lambda$. Since
$\vec{b}\not\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$ and $\vec{b}\in\lambda$,
it is easy to see that the algorithm discarded the disjunct
$q_{\vec{b}}=\mathit{query}(\mathcal{M}(D),\vec{b})$ (otherwise, we would
trivially derive that $\vec{b}\in\mathit{cert}_{q_{\vec{b}},J}^{D}$, and thus
$\vec{b}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$, which is a contradiction to
the fact that $\vec{b}\not\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$). From the
algorithm, one can see that the only reason $q_{\vec{b}}$ was discarded is
because $\vec{g}\in\mathit{cert}_{q_{\vec{b}},J}^{D}$ for at least a tuple
$\vec{g}\not\in\lambda$ (i.e.,
$\vec{g}\in\mathit{dom}(D)^{n}\setminus\lambda$). By Proposition 5, one can
see that $\vec{g}\in\mathit{cert}_{q_{\vec{b}},J}^{D}$ implies
$(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{g})$.
By Proposition 4, it follows that each UCQ $q^{\prime}$ over $\mathcal{O}$
containing tuple $\vec{b}$ in its set of certain answers w.r.t. $\Sigma$ must
contain also tuple $\vec{g}$ in such a set. Thus, since
$\vec{b}\in\mathit{cert}_{q,J}^{D}$, we derive that
$\vec{g}\in\mathit{cert}_{q,J}^{D}$ as well. Since $\vec{g}\not\in\lambda$,
this latter clearly implies that $q$ is not a sound $\Sigma$-characterization
of $\lambda$, as required.∎

Notice that, in all the cases in which a perfect characterization exists, it
is clear that both the above algorithms return the same query
$\mathit{query}(\mathcal{M}(D),\vec{c_{1}})\cup\ldots\cup\mathit{query}(\mathcal{M}(D),\vec{c_{n}})$.
As a direct consequence of both Theorem 5.1 and Theorem 5.2, we get the
following result.

###### Corollary 3

Either the UCQ
$\mathit{query}(\mathcal{M}(D),\vec{c_{1}})\cup\ldots\cup\mathit{query}(\mathcal{M}(D),\vec{c_{n}})$
is a perfect $\Sigma$-characterization of
$\lambda=\\{\vec{c_{1}},\ldots,\vec{c_{n}}\\}$, or a perfect
$\Sigma$-characterization of $\lambda$ in UCQ does not exist.

Furthermore, the combination of Corollary 3 and Proposition 5 allow us to
provide a semantic test for the existence of perfect characterizations in UCQ
in the OBDM case, which can be seen as the analogous of the semantic tests
given in [5] and [29] for the plain relational database case and the ontology-
mediated query answering case, respectively. More specifically, given a
consistent OBDM system
$\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$ and
a $D$-dataset $\lambda$ of arity $n$, there exists a perfect
$\Sigma$-characterization of $\lambda$ in UCQ if and only if it is the case
that
$(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{c})\not\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},\vec{b})$
for each $\vec{c}\in\lambda$ and each
$\vec{b}\in\mathit{dom}(D)^{n}\setminus\lambda$.

In the next section, we study the computational complexity of the problem of
deciding, given
$\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$ and
$\lambda$, whether a perfect $\Sigma$-characterization of $\lambda$ exists.

##  6 Existence

We now address the existence problem. For the scenario under consideration in
this paper, the existence problem for both UCQ-minimally complete and UCQ-
maximally sound characterizations is trivial, since by Theorems 5.1 and 5.2
they always exist. So, we only consider the perfect case, by defining a
variant of the QDEF problem as defined in [29], where also a mapping in some
mapping language is given as input.

Problem: QDEF($\mathcal{L}_{\mathcal{O}}$, $\mathcal{L}_{\mathcal{M}}$,
$\mathcal{Q}$) Input: An OBDM system
$\Sigma=\langle\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle,D\rangle$ and
a $D$-dataset $\lambda$, where $\mathcal{O}\in\mathcal{L}_{\mathcal{O}}$ and
$\mathcal{M}\in\mathcal{L}_{\mathcal{M}}$. Question: Is there a query
$q_{\mathcal{O}}\in\mathcal{Q}$ over $\mathcal{O}$ such that $q_{\mathcal{O}}$
is the perfect $\Sigma$-characterization of $\lambda$?

In what follows, we show that the computational complexity of the above QDEF
decision problem differs depending on the mapping language
$\mathcal{L}_{\mathcal{M}}$ adopted. A key difference between GLAV and the
special cases GAV and LAV is in the size of $\mathcal{M}(D)$. In GLAV mappings
$\mathcal{M}(D)$ can be exponentially large due to the simultaneous presence
of joins in the left-hand side, and existential variables in the right-hand
side, of assertions (e.g., take $D=\\{s_{i}(0),s_{i}(1)\mid 1\leq i\leq n\\}$
and $\mathcal{M}$ containing the GLAV assertion: $\\{(x_{1},\ldots,x_{n})\mid
s_{1}(x_{1})\wedge\ldots\wedge
s_{n}(x_{n})\\}\rightarrow\\{(x_{1},\ldots,x_{n})\mid\exists
y\mbox{\bf.}P(x_{1},y)\wedge\ldots\wedge P(x_{n},y)\\}$). Conversely, in both
LAV and GAV mappings, $\mathcal{M}(D)$ is always polynomially bounded since
the former do not allow for joins in the left-hand side of assertions, whereas
the latter do not allow for existential variables in the right-hand side of
assertions and the arity of ontology predicates is fixed to at most $2$.

GAV and LAV mappings, however, differ for the effort in computing
$\mathcal{M}(D)$. While in LAV mappings $\mathcal{M}(D)$ can be always
computed in polynomial time, in GAV mappings there are CQs on the left-hand
side of assertions, and so $\mathcal{M}(D)$ can not be computed in polynomial
time (unless P=NP).

We start by characterizing the computational complexity of the simplest LAV
case, then the GAV case, and finally the most general GLAV case.
Interestingly, all the provided matching lower bounds hold even for fixed
ontologies $\mathcal{O}=\emptyset$, i.e., ontologies without assertions, fixed
$D$-dataset $\lambda$ containing a single unary tuple, and for both CQs and
UCQs as query languages.

Importantly, for the scenario under consideration, due to Corollary 3, the
question in QDEF can be reformulated equivalently as follows: “is
$q_{\mathcal{O}}=\mathit{query}(\mathcal{M}(D),\vec{c_{1}})\cup\ldots\cup\mathit{query}(\mathcal{M}(D),\vec{c_{n}})$
also a sound (and so, a perfect) $\Sigma$-characterization of
$\lambda=\\{\vec{c_{1}},\ldots,\vec{c_{n}}\\}$?”.

###### Theorem 6.1

QDEF($\textit{DL-Lite}_{\mathcal{R}}$, LAV, UCQ) is coNP-complete.

###### Proof

As for the membership in coNP, we can first compute $\mathcal{M}(D)$ in
polynomial time, and then, exactly as illustrated in Theorem 4.2, we can check
in coNP whether
$\mathit{query}(\mathcal{M}(D),\vec{c_{1}})\cup\ldots\cup\mathit{query}(\mathcal{M}(D),\vec{c_{n}})$
is also a sound (and so, a perfect) $\Sigma$-characterization of
$\lambda=\\{\vec{c_{1}},\ldots,\vec{c_{n}}\\}$.

coNP-hardness directly follows from the plain relational database case [2].

Recall that the complexity class ${\Theta_{2}^{p}}$ has many
characterizations: ${\Theta_{2}^{p}}=\text{P}^{\textrm{NP}[\text{O}(\text{log
}n)]}=$ P _with a constant number of rounds of parallel queries to an_ NP
_oracle_ [8] (see also [38] for further characterizations).

###### Theorem 6.2

QDEF($\textit{DL-Lite}_{\mathcal{R}}$, GAV, UCQ) is
${\Theta_{2}^{p}}$-complete.

###### Proof

As for the upper bound, for each pair of constants
$(c_{1},c_{2})\in\mathit{dom}(D)^{2}$ (resp., constant $c\in\mathit{dom}(D)$)
and for each atomic role $P$ (resp., concept $A$) in the alphabet of
$\mathcal{O}$ we ask, all together with a single round of parallel queries to
an NP oracle, whether $P(c_{1},c_{2})\in\mathcal{M}(D)$ (resp.,
$A(c)\in\mathcal{M}(D)$). Then, with a second and final round, due to Theorem
4.2, we can ask with a single query to an NP oracle whether
$\mathit{query}(\mathcal{M}(D),\vec{c_{1}})\cup\ldots\cup\mathit{query}(\mathcal{M}(D),\vec{c_{n}})$
is also a sound (and so, a perfect) $\Sigma$-characterization of
$\lambda=\\{\vec{c_{1}},\ldots,\vec{c_{n}}\\}$.

As for the lower bound, the proof of ${\Theta_{2}^{p}}$-hardness is by a
LogSpace reduction from the _odd clique problem_ , which is
${\Theta_{2}^{p}}$-complete [37]. _Odd clique_ is the problem of deciding,
given a finite and undirected graph without loops $G=(V,E)$, whether the
maximum clique size of $G$ is an odd number. Without loss of generality, we
may assume that $E$ contains at least an edge and that the cardinality of $V$
is an even number (indeed, it is always possible to add fresh isolated nodes
to the graph $G$ without changing its maximum clique size).

Let $V=\\{v_{1},\ldots,v_{n}\\}$, we define an OBDM system $\Sigma_{G}=\langle
J_{G},D_{G}\rangle$ as follows:
$J_{G}=\langle\mathcal{O},\mathcal{S}_{G},\mathcal{M}_{G}\rangle$ is an OBDM
specification such that $\mathcal{O}=\emptyset$,
$\mathcal{S}_{G}=\\{e,s_{1},\ldots,s_{n}\\}$, and $\mathcal{M}_{G}$ has the
following GAV assertions, for each possible odd number $i\in[1,n]$:

$\displaystyle\\{(x)\mid\exists
y_{1},\ldots,y_{i}\mbox{\bf.}s_{i}(x)\wedge\mathit{cl}_{i}\\}\rightarrow\\{(x)\mid
A_{i}(x)\\},$ $\displaystyle\\{(x)\mid\exists
y_{1},\ldots,y_{i+1}\mbox{\bf.}s_{i+1}(x)\wedge\mathit{cl}_{i+1}\\}\rightarrow\\{(x)\mid
A_{i}(x)\\},$

where $A_{i}$ is an atomic concept in the alphabet of $\mathcal{O}$, and, for
each $p\in[1,n]$:

$\mathit{cl}_{p}=\bigwedge_{\\{(k,j)\mid 1\leq k<j\leq p\\}}e(y_{k},y_{j}).$

Intuitively, $\mathit{cl}_{p}$ asks whether $G$ contains a clique of size $p$.
Finally, $D_{G}=\\{e(x_{1},x_{2})\mid(x_{1},x_{2})\in
E\\}\cup\\{e(x_{2},x_{1})\mid(x_{1},x_{2})\in E\\}\cup\\{s_{i}(c)\mid 1\leq
i\leq n\text{ and }i\text{ is odd}\\}\cup\\{s_{i}(c^{\prime})\mid 2\leq i\leq
n\text{ and }i\text{ is even}\\}$. Let, moreover, $\lambda$ be the fixed
$D_{G}$-dataset $\lambda=\\{(c)\\}$.

Notice that $\lambda$ is fixed, whereas the OBDM system $\Sigma_{G}$ can be
constructed in LogSpace from an input graph $G$.

The correctness of the reduction is mainly based on the following property:

###### Claim

Let $i\in[1,n]$ be an odd number. We have that:

  1. 1.

$A_{i}(c)\in\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$ if and only if
$G$ contains a clique of size $i$.

  2. 2.

$A_{i}(c^{\prime})\in\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$ if
and only if $G$ contains a clique of size $i+1$.

###### Proof

As for 1, since $s_{i}(c)\in D_{G}$, it is easy to see that the query
$q_{i}=\\{(x)\mid\exists
y_{1},\ldots,y_{i}\mbox{\bf.}s_{i}(x)\wedge\mathit{cl}_{i}\\}$ is such that
$(c)\in q_{i}^{D_{G}}$ if and only if $G$ has a clique of size $i$. Thus, due
to the GAV assertion $q_{i}\rightarrow\\{(x)\mid A_{i}(x)\\}$ occurring in
$\mathcal{M}_{G}$, we have
$A_{i}(c)\in\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$ if and only if
$G$ has a clique of size $i$.

As for 2, since $s_{i+1}(c^{\prime})\in D_{G}$, it is easy to see that the
query $q_{i+1}=\\{(x)\mid\exists
y_{1},\ldots,y_{i+1}\mbox{\bf.}s_{i+1}(x)\wedge\mathit{cl}_{i+1}\\}$ is such
that $(c^{\prime})\in q_{i+1}^{D_{G}}$ if and only if $G$ has a clique of size
$i+1$. Thus, due to the GAV assertion $q_{i+1}\rightarrow\\{(x)\mid
A_{i}(x)\\}$ occurring in $\mathcal{M}_{G}$, if $G$ has a clique of size
$i+1$, then
$A_{i}(c^{\prime})\in\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$.
Conversely, suppose that $G$ has not a clique of size $i+1$. On the one hand,
the assertion $q_{i+1}\rightarrow\\{(x)\mid A_{i}(x)\\}$ does not make
$A_{i}(c^{\prime})$ true in
$\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$. On the other hand, since
$s_{i}(c^{\prime})\not\in D_{G}$, not even the assertion $\\{(x)\mid\exists
y_{1},\ldots,y_{i}\mbox{\bf.}s_{i}(x)\wedge\mathit{cl}_{i}\\}\rightarrow\\{(x)\mid
A_{i}(x)\\}$ makes $A_{i}(c^{\prime})$ true in
$\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$. Thus,
$A_{i}(c^{\prime})\not\in\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$.
∎

With the above property at hand, we can now prove that the maximum clique size
of a graph $G$ is an odd number if and only if the CQ
$q_{\mathcal{O}}=\mathit{query}(\mathcal{M}_{G}(D_{G}),c)$ is also a sound
(and so, a perfect) $\Sigma_{G}$-characterization of $\lambda$, thus showing
the claimed lower bound.

“Only-if part:” Suppose that the maximum clique size of $G$ is $p$, where $p$
is an odd number. Due to the above claim, we have that
$\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}=\\{A_{1}(c),A_{1}(c^{\prime}),A_{3}(c),A_{3}(c^{\prime}),\ldots,A_{p}(c)\\}$
(observe that
$A_{p}(c^{\prime})\not\in\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$
because $G$ has not a clique of size $p+1$ by assumption), and so
$q_{\mathcal{O}}=\mathit{query}(\mathcal{M}_{G}(D_{G}),c)=\\{(x_{c})\mid\exists
y_{c^{\prime}}\mbox{\bf.}\phi_{\mathcal{O}}(x_{c},y_{c^{\prime}})\\}$, where
$\phi_{\mathcal{O}}(x_{c},y_{c^{\prime}})$ = $A_{1}(x_{c})\wedge
A_{1}(y_{c^{\prime}})\wedge A_{3}(x_{c})\wedge
A_{3}(c^{\prime})\wedge\ldots\wedge A_{p}(x_{c})$. It is straightforward to
verify that
$(\mathit{set}(\phi_{\mathcal{O}}),(x_{c}))\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})},(c))$
but
$(\mathit{set}(\phi_{\mathcal{O}}),(x_{c}))\not\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})},(c^{\prime}))$.
It follows that $\mathit{cert}_{q_{\mathcal{O}},J_{G}}^{D_{G}}=\\{(c)\\}$,
i.e., $q_{\mathcal{O}}$ is a perfect $\Sigma_{G}$-characterization of
$\lambda$.

“If part:” Suppose that the maximum clique size of $G$ is $r$, where $r$ is an
even number. Due to the above claim, we have that
$\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}=\\{A_{1}(c),A_{1}(c^{\prime}),A_{3}(c),A_{3}(c^{\prime}),\ldots,A_{r-1}(c),A_{r-1}(c^{\prime})\\}$
(observe that
$A_{r-1}(c^{\prime})\in\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$ and
$A_{r+1}(c)\not\in\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})}$ because
by assumption $G$ has a clique of size $r$ but not of size $r+1$), and so
$q_{\mathcal{O}}=\mathit{query}(\mathcal{M}_{G}(D_{G}),c)=\\{(x_{c})\mid\exists
y_{c^{\prime}}\mbox{\bf.}\phi_{\mathcal{O}}(x_{c},y_{c^{\prime}})\\}$, where
$\phi_{\mathcal{O}}(x_{c},y_{c^{\prime}})$ = $A_{1}(x_{c})\wedge
A_{1}(y_{c^{\prime}})\wedge A_{3}(x_{c})\wedge
A_{3}(c^{\prime})\wedge\ldots\wedge A_{r-1}(x_{c})\wedge
A_{r-1}(y_{c^{\prime}})$. It is straightforward to verify that
$(\mathit{set}(\phi_{\mathcal{O}}),(x_{c}))\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}_{G}(D_{G})},(c^{\prime}))$.
It follows that
$(c^{\prime})\in\mathit{cert}_{q_{\mathcal{O}},J_{G}}^{D_{G}}$, i.e.,
$q_{\mathcal{O}}$ is not a sound (and so, not a perfect)
$\Sigma_{G}$-characterization of $\lambda$. ∎

###### Theorem 6.3

QDEF($\textit{DL-Lite}_{\mathcal{R}}$, GLAV, UCQ) is coNExpTime-complete.

###### Proof

We start by discussing the upper bound. We show how to check whether
$q_{\mathcal{O}}=\mathit{query}(\mathcal{M}(D),\vec{c_{1}})\cup\ldots\cup\mathit{query}(\mathcal{M}(D),\vec{c_{m}})$
is not a sound (and so, not a perfect) $\Sigma$-characterization of
$\lambda=\\{\vec{c_{1}},\ldots,\vec{c_{m}}\\}$ in NExpTime.

As a first step, we compute
$q_{\mathcal{O}}=\mathit{query}(\mathcal{M}(D),\vec{c_{1}})\cup\ldots\cup\mathit{query}(\mathcal{M}(D),\vec{c_{m}})$
in exponential time (note that $\mathcal{M}(D)$ can be exponentially large,
and so also the UCQ $q_{\mathcal{O}}$). Then, we can proceed similarly as in
the proof of Theorem 4.2. We guess (_i_) a tuple of constants $\vec{c}$, and
(_ii_) $q^{\prime}_{\mathcal{O}}$, $\rho_{\mathcal{O}}$, $q_{\mathcal{S}}$,
$\rho_{\mathcal{M}}$, and $f$ (which now can be objects of exponential size).
Finally, we check in exponential time whether (_i_)
$\vec{c}\in\mathit{dom}(D)^{n}\setminus\lambda$, where $n$ is the arity of the
tuples in $\lambda$, and (_ii_) the following condition holds:
$\vec{c}\in\mathit{cert}_{q_{\mathcal{O}},J}^{D}$ or $\Sigma$ is inconsistent.

As for the lower bound, the proof of coNExpTime-hardness is by a polynomial
time reduction from the _complement of the succinct clique problem_. The
_succinct clique problem_ is known to be NExpTime-complete [31]. here we show
that QDEF($\textit{DL-Lite}_{\mathcal{R}}$, GLAV, UCQ) is coNExpTime-hard.

To simplify the readability of the proof, we first illustrate the main idea
behind it. In particular, as a first step we provide an alternative proof of
coNP-hardness of UCQ-definability in the plain relational database case. The
coNP-hardness proof is by a LogSpace reduction from the _complement of the
clique problem_. We have a schema $\mathcal{S}=\\{e,P\\}$. Let $\langle
G,k\rangle$ be an instance of the _clique problem_ , where $G=(V,E)$ is a
finite undirected graph without loops and with $E\neq\emptyset$, and $k$ is a
natural number (written in unary). Starting from $G$, we define an
$\mathcal{S}$-database $D=D_{k}\cup D_{G}$ as follows:

$\displaystyle D_{k}=\\{e(y_{i},y_{j})\mid 1\leq i<j\leq
k\\}\cup\\{P(c,y_{i})\mid 1\leq i\leq k\\}$ $\displaystyle
D_{G}=\\{e(v_{i},v_{j})\mid(v_{i},v_{j})\in
E\\}\cup\\{e(v_{j},v_{i})\mid(v_{i},v_{j})\in E\\}\cup\\{P(c^{\prime},v)\mid
v\in V\\}$

Finally, $\lambda$ is the fixed $D$-dataset $\\{(c)\\}$. Intuitively, $D_{k}$
represents a clique of size $k$, whereas $D_{G}$ represents the graph $G$.

Notice that $D$ can be constructed in LogSpace from $G$. Let
$q_{k}=\mathit{query}(D_{k},(c))$, which is equivalent to:

$\\{(x)\mid\exists y_{1},\ldots,y_{k}\mbox{\bf.}P(x,y_{1})\wedge\ldots\wedge
P(x,y_{k})\wedge\bigwedge_{1\leq i<j\leq k}(e(y_{i},y_{j}))\\}.$

One can easily verify that $\lambda$ is UCQ-definable inside $D$ if and only
if $q_{k}^{D}=\\{(c)\\}$. Indeed, $q_{k}$ is similar to the canonical UCQ
$\mathit{query}(D,(c))$ [BaRo17], where, however, only constants _reachable_
from $c$ are taken into account in the query. More specifically, by
construction, the evaluation of $q_{k}$ over $D$ is either $\\{(c)\\}$, or
$\\{(c),(c^{\prime})\\}$. Indeed, $q_{k}^{D}$ always contain the tuple $(c)$,
and it contains the tuple $(c^{\prime})$ if and only if
$(D_{k},(c))\rightarrow(D_{G},(c^{\prime}))$ (obviously,
$(D_{k},(c))\rightarrow(D_{G},(c^{\prime}))$ if and only if
$(\mathit{set}(\phi),(x))\rightarrow(D,(c^{\prime}))$, where $\phi$ is the
body of $q_{k}$). In the next property, we are going to show that this latter
is the case if and only if $G$ has a clique of size $k$, thus proving the
claimed coNP-hardness.

###### Claim

$G$ has a clique of size $k$ if and only if
$(D_{k},(c))\rightarrow(D_{G},(c^{\prime}))$.

###### Proof

“Only-if part:” Suppose $G$ has a clique of size $k$, i.e., there are $k$
nodes in $G$ forming a clique. This immediately implies the existence of a
homomorphism $h$ from $\mathit{dom}(D_{k})$ to $\mathit{dom}(D_{G})$ mapping
(_i_) $c$ to $c^{\prime}$, and (_ii_) constant $y_{i}$ to a constant $v_{i}$
representing a node in such a clique, for each possible $i\in[1,k]$. Thus, we
have $(D_{k},(c))\rightarrow(D_{G},(c^{\prime}))$, as required.

“If part:” Suppose $(D_{k},(c))\rightarrow(D_{G},(c^{\prime}))$, i.e., there
is a homomorphism $h$ from $\mathit{dom}(D_{k})$ to $\mathit{dom}(D_{G})$ with
$h(c)=c^{\prime}$. This immediately implies that the set of facts
$\\{e(h(y_{i}),h(y_{j}))\mid e(y_{i},y_{j})\in D_{k}\\}$ that must occur in
$D_{G}$ due to the assumption that $h$ is a homomorphism from
$\mathit{dom}(D_{k})$ to $\mathit{dom}(D_{G})$ denotes a clique of size $k$
inside the graph $G$. ∎

We are now ready to come back to show that QDEF($\textit{DL-
Lite}_{\mathcal{R}}$, GLAV, UCQ) is coNExpTime-hard. The proof of coNExpTime-
hardness is by a polynomial time reduction from the _complement of the
succinct clique problem_. Given a succinct representation of a graph $C_{G}$
representing a finite undirected graph $G=(V,E)$ without loops and with
$E\neq\emptyset$, and given a natural number $k$ in unary, _succinct clique_
is the problem of deciding whether the graph represented by $C_{G}$ has a
clique of size $k$. _Succinct clique_ is known to be NExpTime-complete [31].

For a succinct representation $C_{G}$ of a graph $G=(V,E)$ with $m$ nodes,
without loss of generality, we implicitly mean a circuit using $2\cdot b$
input gates $\vec{x}=(x_{1},\ldots,x_{b},x_{b+1},\ldots,x_{2\cdot b})$ (where
$2^{b}=m$) for which on input $(a_{1},\ldots,a_{b},a_{b+1},\ldots,a_{2\cdot
b})$ circuit $C_{G}$ outputs true if and only if the two nodes $v_{i},v_{j}$
in $V$ represented by $v_{i}=(a_{1},\ldots,a_{b})$ and
$v_{j}=(a_{b+1},\ldots,a_{2\cdot b})$ are such that $(v_{i},v_{j})\in E$ (see
[GaWi83] for more details). Moreover, from a circuit $C_{G}$ with $\vec{x}$ as
input gates, we denote by $F_{C_{G}}(\vec{x},\vec{w})$ the 3-CNF formula
obtained by applying the _Tseitin transformation_ [Tsei83], where $\vec{w}$
are the fresh variables introduced by the transformation. We recall that such
transformation is linear in the size of $C_{G}$. And, among the introduced
variables $\vec{w}$ introduced by the linear transformation, there is one
variable in $\vec{w}$, denoted by $w$, which represents the output gate of the
circuit. More formally, the transformation is such that if on input
$\vec{a}=(a_{1},\ldots,a_{b},a_{b+1},\ldots,a_{2\cdot b})$ circuit $C_{G}$
outputs true, there there is exactly one satisfying assignment of formula
$F_{C_{G}}(\vec{a},\vec{w})$ with $1$ as truth assignment to variable $w$,
otherwise (i.e., $C_{G}$ outputs false on $\vec{a}$) there is no satisfying
assignment of $F_{C_{G}}(\vec{a},\vec{w})$ with $1$ as truth assignment to
variable $w$.

Let $\langle C_{G},k\rangle$ be an instance of the succinct clique problem,
where $C_{G}$ is a circuit with $2\cdot b$ input gates succinctly representing
a graph $G=(V,E)$ of $m=2^{b}$ nodes, and $k$ is a natural number written in
unary. Let $F_{C_{G}}(\vec{x},\vec{w})=p_{1}\wedge\ldots\wedge p_{r}$ be the
3-CNF formula associated to $C_{G}$, where each clause $p_{i}$ is a
disjunction of three literals, each literal being either a variable in
$\vec{x}\cup\vec{w}$ or its negated. For $i\in[1,p]$, we denote by
$o_{i_{1}},o_{i_{2}},o_{i_{3}}$ the first, the second, and the third,
respectively, variable appearing (either positive or negated) in clause
$p_{i}$.

Starting from $\mathcal{C}_{G}$, we define an OBDM system $\Sigma=\langle
J,D\rangle$ and a $D$-dataset $\lambda$ as follows, where
$J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ is an OBDM specification
and $D$ is an $\mathcal{S}$-database. First, $\mathcal{O}=\emptyset$ is an
empty set of assertions containing binary predicates $e$, $P$, and $V_{i}$ for
each $i\in[1,b]$. Intuitively, as in the reduction from normal clique, $e$
denotes the edges of graphs and $P$ connects constants $c$ and $c^{\prime}$ to
nodes of the $k$-clique graph and the input graph $G$, respectively. The
additional predicates $V_{i}$’s are used to encode nodes of the graphs.
Second, $\mathcal{S}=\mathcal{S}_{k}\cup\mathcal{S}_{G}$, where
$\mathcal{S}_{k}=\\{s_{e},s_{p},s_{v}\\}$ and
$\mathcal{S}_{G}=\\{s^{\prime},s_{w},p_{1},\ldots,p_{r}\\}$ with $s^{\prime}$
and $s_{w}$ unary predicates, $s_{e}$ and $s_{p}$ binary predicates, $p_{1}$,
$p_{2}$, $\ldots$, and $p_{r}$ ternary predicates, and $s_{v}$ a $b+1$
predicate. Third, the $\mathcal{S}$-database $D=D_{k}\cup D_{G}$ is as
follows. For each $i\in[1,k]$, $D_{k}$ contains (_i_) $k-1$ constants
$y_{i}^{1},\ldots,y_{i}^{k-1}$ used to represent the clique without ever
repeating the same constant, and (_ii_) $b$ constants
$d_{i}^{1},\ldots,d_{i}^{b}$ used to encode node $y_{i}$ and ensuring that the
distinct constants $y_{i}^{1},\ldots,y_{i}^{k-1}$ actually denote the same
node $y_{i}$.

$\displaystyle D_{k}=$ $\displaystyle\\{s_{e}(y_{i}^{j},y_{l}^{i})\mid 1\leq
i\leq j<k\text{ and }l=j+1\\}\cup$ $\displaystyle\\{s_{p}(c,y_{i}^{l})\mid
1\leq i\leq k\text{ and }1\leq l<k\\}\cup$
$\displaystyle\\{s_{v}(y_{i}^{l},d_{i}^{1},\ldots,d_{i}^{b})\mid 1\leq i\leq
k\text{ and }1\leq l<k\\}$

For example, if $k=4$ and $b=2$, then we have
$D_{k}=\\{e(y_{1}^{1},y_{2}^{1}),e(y_{1}^{2},y_{3}^{1}),e(y_{1}^{3},y_{4}^{1}),e(y_{2}^{2},y_{3}^{2}),e(y_{2}^{3},y_{4}^{2}),e(y_{3}^{3},y_{4}^{3})\\}\cup\\{s_{p}(c,y_{i}^{1})\mid
1\leq i\leq 4\\}\cup\\{s_{p}(c,y_{i}^{2})\mid 1\leq i\leq
4\\}\cup\\{s_{p}(c,y_{i}^{3})\mid 1\leq i\leq
4\\}\cup\\{s_{v}(y_{i}^{1},d_{i}^{1},d_{i}^{2})\mid 1\leq i\leq
4\\}\cup\\{s_{v}(y_{i}^{2},d_{i}^{1},d_{i}^{2})\mid 1\leq i\leq
4\\}\cup\\{s_{v}(y_{i}^{3},d_{i}^{1},d_{i}^{2})\mid 1\leq i\leq 4\\}$.
Informally, $e$ contains a clique of size $k=4$ without ever repeating a node,
while relation $s_{v}$ ensures that, for each $i\in[1,4]$, the distinct
constants $y_{i}^{1},y_{i}^{2},y_{i}^{3}$ actually denote the same node
$y_{i}$ because they are connected with same elements $d_{i}^{1},d_{i}^{2}$ in
$s_{v}$.

As for $D_{G}$, we have $s^{\prime}(c^{\prime})\in D_{G}$ and $s_{w}(1)\in
D_{G}$. Observe that for each clause $p_{i}$ there are exactly seven
satisfying truth assignments of the clause, each of the form
$(t_{j_{1}}^{i},t_{j_{2}}^{i},t_{j_{3}}^{i})$, where $j\in[1,7]$ and each
$t_{j_{l}}^{i}$ is the truth assignment (i.e., either constant $0$ or constant
$1$) given to the variable $o_{i_{l}}$ by $j$. The predicate $p_{i}$ in
$D_{G}$ associated to the clause simply list such satisfying assignments:

$D_{G}=\\{p_{i}(t_{j_{1}}^{i},t_{j_{2}}^{i},t_{j_{3}}^{i})\mid 1\leq i\leq
r\text{ and }1\leq j\leq
7\\}\cup\\{s^{\prime}(c^{\prime})\\}\cup\\{s_{w}(1)\\}$

For example, if the circuit $C_{G}$ succinctly representing $G$ corresponds to
formula $x_{1}\text{ }\mathsf{XOR}\text{ }x_{2}$ (note $b=1$), then the 3-CNF
formula is $F_{C_{G}}=\exists x_{1},x_{2},w\mbox{\bf.}(\neg x_{1}\vee\neg
x_{2}\vee\neg w)\wedge(x_{1}\vee x_{2}\vee\neg w)\wedge(x_{1}\vee\neg
x_{2}\vee w)\wedge(\neg x_{1}\vee x_{2}\vee w)$ (with $w$ the output gate
being the only fresh variable introduced by the Tseitin transformation) and
$D_{G}$ is as follows:

$\displaystyle D_{G}=$ $\displaystyle\\{s^{\prime}(c^{\prime}),s_{w}(1),$
$\displaystyle
p_{1}(0,0,0),p_{1}(0,0,1),p_{1}(0,1,0),p_{1}(0,1,1),p_{1}(1,0,0),p_{1}(1,0,1),p_{1}(1,1,0),$
$\displaystyle
p_{2}(0,0,0),p_{2}(0,1,0),p_{2}(0,1,1),p_{2}(1,0,0),p_{2}(1,0,1),p_{2}(1,1,0),p_{2}(1,1,1),$
$\displaystyle
p_{3}(0,0,0),p_{3}(0,0,1),p_{3}(0,1,1),p_{3}(1,0,0),p_{3}(1,0,1),p_{3}(1,1,0),p_{3}(1,1,1)$
$\displaystyle
p_{4}(0,0,0),p_{4}(0,0,1),p_{4}(0,1,0),p_{4}(0,1,1),p_{4}(1,0,1),p_{4}(1,1,0),p_{4}(1,1,1)\\}$

The fixed $D$-dataset is $\lambda=\\{(c)\\}$. It remains to describe the GLAV
mapping $\mathcal{M}$ in the OBDM system $\Sigma$. We have
$\mathcal{M}=\mathcal{M}_{k}\cup\mathcal{M}_{G}$, where
$\mathcal{M}_{k}=\\{m_{k}^{1},m_{k}^{2},m_{k}^{3}\\}$ and
$\mathcal{M}_{G}=\\{m_{G}\\}$ such that $\mathcal{M}_{k}$ is simply as
follows:

$\displaystyle m^{1}_{k}:$ $\displaystyle\\{(x^{\prime},x^{\prime\prime})\mid
s_{e}(x^{\prime},x^{\prime\prime})\\}\rightarrow\\{(x^{\prime},x^{\prime\prime})\mid
e(x^{\prime},x^{\prime})\\}$ $\displaystyle m^{2}_{k}:$
$\displaystyle\\{(x,x^{\prime})\mid
s_{p}(x,x^{\prime})\\}\rightarrow\\{(x,x^{\prime})\mid P(x,x^{\prime})\\}$
$\displaystyle m^{3}_{k}:$ $\displaystyle\\{(x,x_{1},\ldots,x_{b})\mid
s_{v}(x,x_{1},\ldots,x_{b})\\}\rightarrow$
$\displaystyle\\{(x,x_{1},\ldots,x_{b})\mid V_{1}(x,x_{1})\wedge\ldots\wedge
V_{b}(x,x_{b})\\}$

and $m_{G}\in\mathcal{M}_{G}$ is the following GLAV assertion:

$\displaystyle\\{(x,x_{1},\ldots,x_{2\cdot
b})\mid\exists\vec{w}\mbox{\bf.}s^{\prime}(x)\wedge
p_{1}(o_{1,1},o_{1,2},o_{1,3})\wedge\ldots\wedge
p_{r}(o_{r,1},o_{r,2},o_{r,3})\wedge s_{w}(w)\\}\rightarrow$
$\displaystyle\\{(x,x_{1},\ldots,x_{2\cdot b})\mid\exists
z_{1},z_{2}\mbox{\bf.}e(z_{1},z_{2})\wedge e(z_{2},z_{1})\wedge
P(x,z_{1})\wedge P(x,z_{2})\wedge$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad
V_{1}(z_{1},x_{1})\wedge\ldots\wedge V_{b}(z_{1},x_{b})\wedge$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad
V_{1}(z_{2},x_{b+1})\wedge\ldots\wedge V_{b}(z_{2},x_{2\cdot b})\\}$

For example, for the circuit $C_{G}$ given before, the GLAV assertion $m_{G}$
is:

$\displaystyle\\{(x,x_{1},x_{2})\mid\exists
w_{1}\mbox{\bf.}s^{\prime}(x)\wedge p_{1}(x_{1},x_{2},w)\wedge
p_{2}(x_{1},x_{2},w)\wedge$ $\displaystyle\qquad\qquad\qquad\qquad\qquad
p_{3}(x_{1},x_{2},w)\wedge p_{4}(x_{1},x_{2},w)\wedge s_{w}(w)\\}\rightarrow$
$\displaystyle\\{(x,x_{1},x_{2})\mid\exists
z_{1},z_{2}\mbox{\bf.}e(z_{1},z_{2})\wedge e(z_{2},z_{1})\wedge
P(x,z_{1})\wedge P(x,z_{2})\wedge$
$\displaystyle\qquad\qquad\qquad\quad\quad\quad V_{1}(z_{1},x_{1})\wedge
V_{1}(z_{2},x_{2})\\}$

Observe that
$\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)}=\mathcal{M}(D)=\mathcal{M}_{k}(D_{k})\cup\mathcal{M}_{G}(D_{G})$.
Informally, the extension of predicate $e$ in $\mathcal{M}_{k}(D_{k})$
describes a $k$-clique graph without ever repeating a node, while the
extensions of predicates $V_{i}$’s in $\mathcal{M}_{k}(D_{k})$ ensure that,
for each $i\in[1,k]$, the distinct constants $y_{i}^{1},\ldots,y_{i}^{k-1}$
actually denote the same node $y_{i}$ because they are connected with same
elements $d_{i}^{1},\ldots,d_{i}^{b}$. Finally, the extension of predicate $P$
in $\mathcal{M}_{k}(D_{k})$ simply contains $(c,y_{i}^{l})$ for each constant
$y_{i}^{l}$ occurring in the extension of $e$ in $\mathcal{M}_{k}(D_{k})$.

As for $\mathcal{M}_{G}(D_{G})$, let
$\vec{a}=(a_{1},\ldots,a_{b},a_{b+1},a_{2\cdot b})$ be an input to the circuit
$C_{G}$. By construction, one can easily verify that $C_{G}$ outputs true if
and only if $(c,a_{1},\ldots,a_{b},a_{b+1},a_{2\cdot b})$ is a tuple in the
evaluation of the left-hand side query of $m_{G}$ over $D_{G}$. Thus, for each
edge $((a_{1},\ldots,a_{b}),(a_{b+1},a_{2\cdot b}))\in E$ represented by
circuit $C_{G}$, the chase $\mathcal{M}_{G}(D_{G})$ produces two fresh
variables $z_{1}$ and $z_{2}$ that simulates, respectively,
$v_{1}=(a_{1},\ldots,a_{b})$ and $v_{2}=(a_{b+1},\ldots,a_{2\cdot b})$ and
connect them trough predicate $e$ (simulating so the edge $(v_{1},v_{2})\in E$
described by circuit $C_{G}$). Moreover, both the freshly introduced variables
$z_{1}$ and $z_{2}$ are connected trough the extensions of predicates
$V_{i}$’s in the following way:
$V_{1}(z_{1},a_{1}),\ldots,V_{b}(z_{1},a_{b}),V_{1}(z_{2},a_{b+1}),\ldots,V_{b}(z_{2},a_{2\cdot
b})$. This ensures that two distinct variables $z$ and $z^{\prime}$ that
actually denote the same node in $G$, denote the same node also in
$\mathcal{M}_{G}(D_{G})$ because they are connected with same elements.
Finally, the extension of predicate $P$ in $\mathcal{M}_{G}(D_{G})$ simply
contains $(c^{\prime},z)$ for each freshly introduced variable $z$ by the
application of the chase.

Notice that $\lambda=\\{(c)\\}$ is a fixed $D$-dataset and both the OBDM
specification $J=\langle\mathcal{O},\mathcal{S},\mathcal{M}\rangle$ and the
$\mathcal{S}$-database $D$ can be always constructed in polynomial time from
$C_{G}$. Let $q_{k}=\mathit{query}(\mathcal{M}(D_{k}),(c))$, which is
equivalent to:

$\displaystyle\\{(x)\mid$ $\displaystyle\exists y_{1}^{1},\ldots,y_{1}^{k-1},\
\ldots\ ,y_{k}^{1},\ldots,y_{k}^{k-1},d_{1}^{1},\ldots,d_{1}^{b},\ \ldots\
,d_{k}^{1},\ldots,d_{k}^{b}\mbox{\bf.}$ $\displaystyle\bigwedge_{1\leq i\leq
j<k\text{ and }l=j+1}(e(y_{i}^{j},y_{l}^{i}))\wedge\bigwedge_{1\leq i\leq
k\text{ and }1\leq l<k}(P(x,y_{i}^{l}))\wedge$ $\displaystyle\bigwedge_{1\leq
i\leq k\text{ and }1\leq l<k}(V_{1}(y_{i}^{l},d_{i}^{1})\wedge\ldots\wedge
V_{b}(y_{i}^{l},d_{i}^{b}))\\}$

One can easily verify that a UCQ-perfect $\Sigma$-characterization of
$\lambda$ exists if and only if $\mathit{cert}_{q_{k},J}^{D}=\\{(c)\\}$.
Indeed, $q_{k}$ is similar to $\mathit{query}(\mathcal{M}(D),(c))$ (i.e., the
UCQ-minimally complete $\Sigma$-characterization of $\lambda$), where,
however, only elements _reachable_ from $c$ in $\mathcal{M}(D)$ are taken into
account in the query. More specifically, by construction, the set of certain
answers of $q_{k}$ with respect to $\Sigma=\langle J,D\rangle$ is either
$\\{(c)\\}$, or $\\{(c),(c^{\prime})\\}$. Indeed,
$\mathit{cert}_{q_{k},J}^{D}$ always contain the tuple $(c)$, and it contains
the tuple $(c^{\prime})$ if and only if
$(\mathcal{M}_{k}(D_{k}),(c))\rightarrow(\mathcal{M}_{G}(D_{G}),(c^{\prime}))$.
Clearly,
$(\mathcal{M}_{k}(D_{k}),(c))\rightarrow(\mathcal{M}_{G}(D_{G}),(c^{\prime}))$
if and only if
$(\mathit{set}(\phi),(x))\rightarrow(\mathcal{C}_{\mathcal{O}}^{\mathcal{M}(D)},(c^{\prime}))$,
where $\phi$ is the body of $q_{k}$ (recall that this latter is equivalent to
$c^{\prime}\in\mathit{cert}_{q_{k},J}^{D}$). In the next property, we are
going to show that
$(\mathcal{M}_{k}(D_{k}),(c))\rightarrow(\mathcal{M}_{G}(D_{G}),(c^{\prime}))$
if and only if the graph $G$ represented by the circuit $C_{G}$ has a clique
of size $k$, thus proving the claimed coNExpTime-hardness and concluding the
proof.

###### Claim

The graph $G$ represented by circuit $C_{G}$ has a clique of size $k$ if and
only if
$(\mathcal{M}_{k}(D_{k}),(c))\rightarrow(\mathcal{M}_{G}(D_{G}),(c^{\prime}))$.

###### Proof

“Only-if part:” Suppose the graph $G$ represented by circuit $C_{G}$ has a
clique of size $k$. Let $(v_{1},v_{2},\ldots,v_{k})$ be the nodes forming such
clique in $G$, where each node $v_{i}$ is encoded by
$v_{i}=(a_{i,1},\ldots,a_{i,b})$ in $C_{G}$ (each $a_{i,x}$ is either $0$ or
$1$). Consider any edge $(v_{i},v_{l})\in E$ (or $(v_{l},v_{i})\in E$) which
by assumption exists for each pair $(i,l)$ with $1\leq i<l\leq k$. Due to the
GLAV assertion $m_{G}\in\mathcal{M}_{G}$, by construction,
$\mathcal{M}_{G}(D_{G})$ introduces two fresh variables (without loss of
generality, let denote them by $z_{i}^{j}$ and $z_{l}^{i}$, where $j=l-1$)
such that (_i_)
$\\{V_{1}(z_{i}^{j},a_{i,1}),\ldots,V_{b}(z_{i}^{j},a_{i,b})\\}\subseteq\mathcal{M}_{G}(D_{G})$,
(_ii_)
$\\{V_{1}(z_{l}^{i},a_{l,1}),\ldots,V_{b}(z_{l}^{i},a_{l,b})\\}\subseteq\mathcal{M}_{G}(D_{G})$,
and (_iii_)
$\\{e(z_{i}^{j},z_{l}^{i}),e(z_{l}^{i},z_{i}^{j})\\}\subseteq\mathcal{M}_{G}(D_{G})$.
Observe that, for each node $v_{i}$, in this way there are $k-1$ fresh
variables $z_{i}^{1},z_{i}^{2},\ldots,z_{i}^{k-1}$ representing $v_{i}$, i.e.,
$\\{V_{1}(z_{i}^{j},a_{i,1}),\ldots,V_{b}(z_{i}^{j},a_{i,b})\\}\subseteq\mathcal{M}_{G}(D_{G})$
for each $j\in[1,k-1]$.

Consider now the function $h$ from $\mathit{dom}(\mathcal{M}_{k}(D_{k}))$ to
$\mathit{dom}(\mathcal{M}_{G}(D_{G}))$ such that (_i_) $h(c)=c^{\prime}$,
(_ii_) $h(y_{i}^{l})=z_{i}^{l}$ for each $i\in[1,k]$ and for each
$l\in[1,k-1]$, and (_iii_) $h(d_{i}^{j})=a_{i,j}$ for each $i\in[1,k]$ and for
each $j\in[1,b]$. It is straightforward to verify that $h$ is a homomorphism
witnessing that
$(\mathcal{M}_{k}(D_{k}),(c))\rightarrow(\mathcal{M}_{G}(D_{G}),(c^{\prime}))$,
as required.

“If part:” Suppose
$(\mathcal{M}_{k}(D_{k}),(c))\rightarrow(\mathcal{M}_{G}(D_{G}),(c^{\prime}))$,
i.e., there is a homomorphism $h$ from $\mathit{dom}(\mathcal{M}_{k}(D_{k}))$
to $\mathit{dom}(\mathcal{M}_{G}(D_{G}))$ with $h(c)=c^{\prime}$. Observe that
$(h(d_{i}^{1}),\ldots,h(d_{i}^{b}))$ is the encoding of a node $v_{i}$ in
circuit $C_{G}$ by construction, for each possible $i\in[1,k]$. Furthermore,
for each $i\in[1,k]$, ontology predicates $V_{1},\ldots,V_{b}$ ensure that
elements $y_{i}^{1},\ldots,y_{i}^{k-1}$ are mapped to distinct fresh variables
introduced by $\mathcal{M}_{G}(D_{G})$ that actually denote the same node,
because it must be the case that
$V_{1}(h(y_{i}^{1}),h(d_{i}^{1}))\in\mathcal{M}_{G}(D_{G}),\ldots,V_{b}(h(y_{i}^{1}),h(d_{i}^{b}))\in\mathcal{M}_{G}(D_{G}),\
\ldots,\
V_{1}(h(y_{i}^{k-1}),h(d_{i}^{1}))\in\mathcal{M}_{G}(D_{G}),\ldots,V_{b}(h(y_{i}^{k-1}),h(d_{i}^{b}))\in\mathcal{M}_{G}(D_{G})$.
Now, it is easy to verify that if in $\mathcal{M}_{G}(D_{G})$ we replace each
variable $z$ introduced by $\mathcal{M}_{G}(D_{G})$ with the value
$v=(a_{1},\ldots,a_{b})$ for which
$V_{1}(z,a_{1})\in\mathcal{M}_{G}(D_{G}),\ldots,V_{b}(z,a_{b})\in\mathcal{M}_{G}(D_{G})$,
then by looking at the extension of $e$ we obtain exactly the graph $G$
represented by circuit $C_{G}$.

From the above observations, and the fact that the set of facts
$\\{e(h(y_{i}^{j}),h(y_{l}^{i}))\mid 1\leq i\leq j<k\text{ and }l=j+1\\}$ must
occur in $\mathcal{M}_{G}(D_{G})$ due to the assumption that $h$ is a
homomorphism from $\mathit{dom}(\mathcal{M}_{k}(D_{k}))$ to
$\mathit{dom}(\mathcal{M}_{G}(D_{G}))$, we immediately derive that the graph
$G$ represented by circuit $C_{G}$ contains a clique of size $k$, as required.
∎

##  7 Conclusions

We have addressed the problem of UCQ-definability in the OBDM context. To
semantically characterize datasets through ontologies even in cases where
perfect characterizations do not exist, we have relaxed the notion of
perfecteness in terms of recall and precision. Finally, in a scenario that
uses the languages commonly adopted in OBDM, we have provided a thorough
complexity analysis of three natural, interesting problems associated with the
framework.

There are many interesting avenues for future work. Some of them are: (_i_)
extending the framework for dealing also with the query-by-example problem, in
which two distinct $\lambda^{+}$ and $\lambda^{-}$ datasets are given, and one
is interested in finding perfect (resp., complete and sound, with their
possible corresponding approximations) characterizations queries over the
ontology, so that the certain answers of such queries capture all tuples in
$\lambda^{+}$ and no tuple in $\lambda^{-}$; (_ii_) investigating the
existence and the computation problems when we adopt CQ as a query language
instead of UCQ; (_iii_) seeking for techniques that allow to obtain, from end
users’ perspectives, more intelligible queries as characterizations; and
(_iv_) evaluating the techniques presented in this paper to real world
settings.

## Acknowledgements

This work has been partially supported by the ANR AI Chair INTENDED
(ANR-19-CHIA-0014), by MIUR under the PRIN 2017 project “HOPE” (prot.
2017MMJJRE), by the EU under the H2020-EU.2.1.1 project TAILOR, grant id.
952215, and by European Research Council under the European Union’s Horizon
2020 Programme through the ERC Advanced Grant WhiteMech (No. 834228).

## References

  * [1] S. Abiteboul, R. Hull, and V. Vianu.  Foundations of Databases.  Addison Wesley Publ. Co., 1995.
  * [2] T. Antonopoulos, F. Neven, and F. Servais.  Definability problems for graph query languages.  In Proceedings of the Sixteenth International Conference on Database Theory (ICDT 2013), pages 141–152, 2013.
  * [3] A. Artale, D. Calvanese, R. Kontchakov, and M. Zakharyaschev.  The DL-Lite family and relations.  Journal of Artificial Intelligence Research, 36:1–69, 2009.
  * [4] F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors.  The Description Logic Handbook: Theory, Implementation and Applications.  Cambridge University Press, 2003.
  * [5] P. Barceló and M. Romero.  The Complexity of Reverse Engineering Problems for Conjunctive Queries.  In M. Benedikt and G. Orsi, editors, 20th International Conference on Database Theory (ICDT 2017), volume 68 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:17, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [6] A. Bonifati, R. Ciucanu, and S. Staworko.  Learning join queries from user examples.  ACM Trans. Database Syst., 40(4):24:1–24:38, Jan. 2016.
  * [7] L. Bühmann, J. Lehmann, P. Westphal, and S. Bin.  Dl-learner structured machine learning on semantic web data.  In Companion Proceedings of the The Web Conference 2018, WWW ’18, pages 467–471, Republic and Canton of Geneva, Switzerland, 2018. International World Wide Web Conferences Steering Committee.
  * [8] S. R. Buss and L. Hay.  On truth-table reducibility to SAT.  Information and Computation, 91(1):86–102, 1991.
  * [9] A. Calì, G. Gottlob, and M. Kifer.  Taming the infinite chase: Query answering under expressive relational constraints.  Journal of Artificial Intelligence Research, 48:115–174, 2013.
  * [10] D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati.  Tractable reasoning and efficient query answering in description logics: The DL-Lite family.  Journal of Automated Reasoning, 39(3):385–429, 2007.
  * [11] D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi.  Query processing under GLAV mappings for relational and graph databases.  Proceedings of the Very Large Database Endowment, 6(2):61–72, 2012\.
  * [12] G. Cima.  Preliminary results on ontology-based open data publishing.  In Proceedings of the Thirtieth International Workshop on Description Logics (DL 2017), volume 1879 of CEUR Electronic Workshop Proceedings, http://ceur-ws.org/, 2017.
  * [13] G. Cima.  Abstraction in Ontology-based Data Management.  PhD thesis, Sapienza University of Rome, 12 2020.
  * [14] G. Cima, M. Console, M. Lenzerini, and A. Poggi.  Abstraction in data integration.  In Proceedings of the Thirty-Sixth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021), pages 1–11. IEEE, 2021.
  * [15] G. Cima, M. Lenzerini, and A. Poggi.  Semantic characterization of data services through ontologies.  In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI 2019), pages 1647–1653, 2019.
  * [16] G. Cima, M. Lenzerini, and A. Poggi.  Non-monotonic ontology-based abstractions of data services.  pages 243–252, 2020.
  * [17] A. Doan, A. Y. Halevy, and Z. G. Ives.  Principles of Data Integration.  Morgan Kaufmann, 2012.
  * [18] R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa.  Data exchange: Semantics and query answering.  Theoretical Computer Science, 336(1):89–124, 2005.
  * [19] N. Fanizzi, G. Rizzo, C. d’Amato, and F. Esposito.  Dlfoil: Class expression learning revisited.  In Proceedings of the Twenty-First International Conference on Knowledge Engineering and Knowledge Management (EKAW 2018), 2018.
  * [20] M. Friedman, A. Levy, and T. Millstein.  Navigational plans for data integration.  In Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI 1999), pages 67–73. AAAI Press, 1999.
  * [21] M. R. Garey, D. S. Johnson, and L. J. Stockmeyer.  Some simplified NP-complete graph problems.  Theoretical Computer Science, 1(3):237–267, 1976.
  * [22] V. Gutiérrez-Basulto, J. C. Jung, and L. Sabellek.  Reverse engineering queries in ontology-enriched systems: The case of expressive horn description logic ontologies.  In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 1847–1853. International Joint Conferences on Artificial Intelligence Organization, 7 2018\.
  * [23] M. Lenzerini.  Data integration: A theoretical perspective.  In Proceedings of the Twentyfirst ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS 2002), pages 233–246, 2002\.
  * [24] M. Lenzerini.  Ontology-based data management.  In Proceedings of the Twentieth International Conference on Information and Knowledge Management (CIKM 2011), pages 5–6, 2011.
  * [25] C. Lutz, J. Marti, and L. Sabellek.  Query expressibility and verification in ontology-based data access.  pages 389–398, 2018.
  * [26] D. M. L. Martins.  Reverse engineering database queries from examples: State-of-the-art, challenges, and research opportunities.  Information Systems, 83:89–100, 2019.
  * [27] B. Motik, B. Cuenca Grau, I. Horrocks, Z. Wu, A. Fokoue, and C. Lutz.  OWL 2 Web Ontology Language profiles (second edition).  W3C Recommendation, World Wide Web Consortium, Dec. 2012.  Available at http://www.w3.org/TR/owl2-profiles/.
  * [28] D. Mottin, M. Lissandrini, Y. Velegrakis, and T. Palpanas.  New trends on exploratory methods for data analytics.  Proc. VLDB Endow., 10(12):1977–1980, Aug. 2017.
  * [29] M. Ortiz.  Ontology-mediated queries from examples: a glimpse at the DL-Lite case.  In Proceedings of the Fifth Global Conference on Artificial Intelligence, volume 65 of EPiC Series in Computing, pages 1–14, 2019\.
  * [30] C. H. Papadimitriou and M. Yannakakis.  The complexity of facets (and some facets of complexity).  Journal of Computer and System Sciences, 28(2):244–259, 1984.
  * [31] C. H. Papadimitriou and M. Yannakakis.  A note on succinct representations of graphs.  Information and Computation, 71(3):181–185, 1986.
  * [32] A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati.  Linking data to ontologies.  Journal on Data Semantics, X:133–173, 2008.
  * [33] J. Rothe.  Exact complexity of exact-four-colorability.  Information Processing Letters, 87(1):7–12, 2003.
  * [34] U. Straccia and M. Mucci.  pfoil-dl: Learning (fuzzy) el concept descriptions from crisp owl data using a probabilistic ensemble estimation.  In Proceedings of the 30th Annual ACM Symposium on Applied Computing, SAC ’15, pages 345–352, New York, NY, USA, 2015. ACM.
  * [35] B. ten Cate and V. Dalmau.  The product homomorphism problem and applications.  In Proceedings of the Eigthteenth International Conference on Database Theory (ICDT 2015), volume 31 of LIPIcs, pages 161–176, 2015\.
  * [36] Q. T. Tran, C.-Y. Chan, and S. Parthasarathy.  Query reverse engineering.  The VLDB Journal, 23(5):721–746, Oct. 2014.
  * [37] K. W. Wagner.  More complicated questions about maxima and minima, and some closures of NP.  Theoretical Computer Science, 51:53–80, 1987.
  * [38] K. W. Wagner.  Bounded query classes.  SIAM Journal on Computing, 19(5):833–846, 1990.
  * [39] M. M. Zloof.  Query-by-example: The invocation and definition of tables and forms.  In Proceedings of the 1st International Conference on Very Large Data Bases, VLDB ’75, pages 1–24, New York, NY, USA, 1975. ACM.