achieve FO-rewritability start from a CQ or a UCQ
(that is, a set of CQs) and end up producing a UCQ
that is an expansion of the initial query. These techniques are based on variants of clausal resolution
(Leitsch 1997): every rewriting step essentially corresponds to the application of clausal resolution
between a CQ among the ones already generated and
a concept or role inclusion axiom of the ontology.
The rewriting process terminates when a fix-point is
reached, that is, when no new CQ can be generated.
The results published by Calvanese et al. (2007)
and Poggi et al. (2008) show that, following the technique illustrated earlier, conjunctive query answering
is indeed first-order rewritable in DL-Lite, implying
that answering (unions of) conjunctive queries can
be reduced to query evaluation over a relational database, for which we can rely on standard relational
DBMSs. This property also implies that CQ answering
is in AC0 (a subclass of LOGSPACE) in data complexity. Indeed, this implication is an immediate consequence of the fact that the complexity of the aforementioned phase of query rewriting is independent
of the data source and that the final rewritten query
is an SQL expression. An important question is
whether we can further extend the ontology specification language of OBDM without losing the nice
computational property of the query rewriting phase.
Calvanese et al. (2013) show that adding any of the
main concept constructors considered in description
logics and missing in DL-LiteA (for example, negation, disjunction, qualified existential restriction,
range restriction) causes a jump of the data complexity of conjunctive query answering in OBDM, which
goes beyond the class AC0. This issue has been further investigated by Artale et al. (2009). As for the
query language, we note that going beyond unions of
CQs is problematic from the point of view of
tractability, or even decidability. For instance, adding
negation to CQs causes query answering to become
undecidable (Gutiérrez-Basulto et al. 2015).
This basic technique, introduced by Calvanese et
al. (2007), has been the subject of many investigations in the last decade, with the goal of improving
its performance (Pérez-Urbina, Horrocks, and Motik
2009; Chortaras, Trivela, and Stamou 2011;
Kontchakov et al. 2011; Di Pinto et al. 2013; Gottlob
et al. 2014a) and extending its applicability (
Lenzerini, Lepore, and Poggi 2016). More generally, the issue
of designing automated reasoning algorithms for
query answering in OBDM has been addressed by
many scientific works and projects. New ideas of how
to answer queries for different ontology languages
have been proposed (see, for example, Rosati and
Almatelli 2010; Chortaras, Trivela, and Stamou 2011;
Gottlob et al. 2014b; Lutz and Sabellek 2017) and various extensions to the basic ontology languages have
been explored, such as extensions based on Datalog
(see Calì et al. 2010) or on existential rules (see Gottlob, Manna, and Pieris 2015; Grau et al. 2013; König
et al. 2015).
Finally, there has been interesting and promising
work on extending query rewriting to more expressive, not necessarily first-order rewritable, ontology
languages (Pérez-Urbina, Horrocks, and Motik 2009;
Chortaras, Trivela, and Stamou 2011; Eiter et al.
2012; Calì, Gottlob, and Lukasiewicz 2012; Kaminski, Nenov, and Grau 2016; Bienvenu et al. 2014).
While computing certain answers of queries under
the classical semantics has been the main subject of
the research investigation on OBDM, there are sever-
al other services that an OBDM system should pro-
vide. A brief overview of two services, and an explo-
ration of one issue, follows.
Data Quality Assessment
Besides ontology-mediated querying and other data
management tasks, recent works argue that OBDM is
a promising tool for assessing the quality of data,
especially in the presence of multiple, independent
data sources (Console and Lenzerini 2014; Catarci et
al. 2017). Some of the reasons are as follows: ( 1) basing data quality assessments on a formal conceptualization of the domain of interest allows us to easily
blur out all the meaningless details of the single data
source and focus on real data quality issues; ( 2) different data sources can be analyzed using the same
yardstick, that is, the ontology, and hence accessed
and compared in terms of their quality; and ( 3) the
use of conceptualizations shared among the different
assets of an organization allows for data quality
assessments that are easy to present and use in many
Quality assessment is carried out through different
dimensions, such as consistency, accuracy, completeness, and confidentiality. We briefly discuss consistency, which is the quality dimension dealing with
Table 1. DL-LiteA Assertions.
Symbols in square brackets may or may not be present, and R–(x, y) stands
for R(y, x).
Type DL Syntax FOL Semantics
1 C1 ;;;;;;;C2; ;x.C1(x) ;;;;C2(x)
2 ;R;;;;;;;;;;;C R;;;(x, y) ; C(x)
3 C;;;;;;;;;R;;; C(x) ; ;y.R;;;;x, y)
4 R1;;; ;;;;;;;; R2;;; R1;;; (x, y) ; ;;;R2;;;(x, y)
5 (functR;;;) R[−](x, y) ; R;;;(x, z);; y = z