Towards Scalable and Complete Query Explanation with
OWL 2 EL Ontologies
Zhe Wang
School of Info. & Comm. Tech.
Griffith University, Australia
zhe.wang@griffith.edu.au
Mahsa Chitsaz
School of Info. & Comm. Tech.
Griffith University, Australia
mahsa.chitsaz@
griffithuni.edu.au
Kewen Wang
School of Info. & Comm. Tech.
Griffith University, Australia
k.wang@griffith.edu.au
Jianfeng Du
Cisco School of Informatics
Guangdong University of
Foreign Studies, China
jfdu@mail.gdufs.edu.cn
ABSTRACT
Ontology-mediated data access and management systems
are rapidly emerging. Besides standard query answering,
there is also a need for such systems to be coupled with
explanation facilities, in particular to explain missing query
answers (i.e. desired answers of a query which are not deriv-
able from the given ontology and data). This support is
highly demanded for debugging and maintenance of big data,
and both theoretical results and algorithms proposed. How-
ever, existing query explanation algorithms either cannot
scale over relative large data sets or are not guaranteed to
compute all desired explanations. To the best of our knowl-
edge, no existing algorithm can efficiently and completely
explain conjunctive queries (CQs) w.r.t. ELH
⊥
ontologies.
In this paper, we present a hybrid approach to achieve this.
An implementation of the proposed query explanation algo-
rithm has been developed using an off-the-shelf Prolog en-
gine and a datalog engine. Finally, the system is evaluated
over practical ontologies. Experimental results show that
our system scales over large data sets.
Categories and Subject Descriptors
I.2.4 [Artificial Intelligence]: Knowledge Representation
Formalisms and Methods—Representations; H.4.0 [Information
Systems Applications]: General
Keywords
Abductive reasoning; description logics; conjunctive query.
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full cita-
tion on the first page. Copyrights for components of this work owned by others than
ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re-
publish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from Permissions@acm.org.
CIKM’15, October 19–23, 2015, Melbourne, Australia.
c
2015 ACM. ISBN 978-1-4503-3794-6/15/10 ...$15.00.
DOI: http://dx.doi.org/10.1145/2806416.2806547.
1. INTRODUCTION
One promising solution to the effective access and man-
agement of the ever-growing sea of digital information has
been to use computers in setting up databases of informa-
tion, completed with ontologies that assist in organization
and access. In such an ontology-mediated data access frame-
work, ontologies are used as virtual schemas over data sets to
enrich query answering with ontological knowledge through
logical reasoning, while making use of practical database
management systems to scale over very large data sets. The
standardised web ontology language OWL 2 and its three
profiles, EL, QL and RL
1
, are based on description logics
(DLs), and conjunctive queries (CQs) are used as a vital
querying tool.
Besides standard query answering, explanation services
are often required by end-users to understand why certain
answers are derived or missing. For instance, suppose on-
tology O specifies that a PhD student is a student, i.e.,
PhD v Student, each PhD student has some supervisor, i.e.,
PhD v ∃hasSupervisor.Person, Tom is a PhD student and
Mary is a student, i.e., PhD(Tom) and Student(Mary). For
the query to retrieve those individuals who have supervisors,
which can be expressed as Q(x) = ∃y.hasSupervisor(x, y),
“Tom” is an answer whereas “Mary” is not. One explana-
tion for “Mary” being missing is that PhD(Mary) is absent.
Such explanation services are critical for knowledge manage-
ment to identify specific pieces of the knowledge that need to
be revised. For example, the observation that Mary should
have a supervisor indicates that the current knowledge is
incomplete and PhD(Mary) could be added.
On the other hand, however, the implementation of ex-
isting OWL reasoners does not support such an explanation
mechanism even through tracing the execution of query an-
swering. For this reason, extensive efforts have been devoted
to equip ontology-based systems with various explanation fa-
cilities [22, 23, 4, 15, 24, 6]. While early research was mainly
on explaining derived answers (a.k.a. positive answers, like
“Tom” in the above example), explaining missing answers
(a.k.a. negative answers, like “Mary”) has attracted much
attention lately [3, 6]. Such an explanation facility is es-
sential to understand why the ontology-based system fails
1
http://www.w3.org/TR/owl2-profiles/