=Paper=
{{Paper
|id=None
|storemode=property
|title=DRAOn: A Distributed Reasoner for Aligned Ontologies
|pdfUrl=https://ceur-ws.org/Vol-1015/paper_14.pdf
|volume=Vol-1015
|dblpUrl=https://dblp.org/rec/conf/ore/DucLZC13
}}
==DRAOn: A Distributed Reasoner for Aligned Ontologies==
https://ceur-ws.org/Vol-1015/paper_14.pdf
DRAOn: A Distributed Reasoner for Aligned Ontologies
Chan Le Duc1 , Myriam Lamolle1 , Antoine Zimmermann2 , and Olivier Curé3
1
LIASD Université Paris 8 - IUT de Montreuil, France
{chan.leduc, myriam.lamolle}@iut.univ-paris8.fr
2
École Nationale Supérieure des Mines, FAYOL-ENSMSE, LSTI, F-42023 Saint-Étienne,
France antoine.zimmermann@emse.fr
3
LIGM Université Paris-Est, France
ocure@univ-mlv.fr
Abstract. DRAOn is a distributed reasoner which offers inference services for
a network of OWL ontologies correlated by alignments. Reasoning with such
networks of ontologies depends on the semantics we define for alignments with
respect to ontologies. DRAOn supports two semantics for a network of ontolo-
gies: the standard Description Logics (DL) semantics for non-distributed reason-
ing, and the Integrated Distributed Description Logics (IDDL) semantics for dis-
tributed reasoning. Unlike the DL semantics where alignments are considered as
inter-ontology axioms, the IDDL semantics interprets alignments as correspon-
dences enabling to propagate non-emptiness (always satisfiable) and unsatisfia-
bility of atomic concepts from an ontology to another one. Consequently, this
makes distributed reasoning for a network of ontologies possible since consis-
tency of the whole network can be decided from consistency of each ontology
with axioms built from alignments such that these axioms ensure just necessary
propagations of knowledge.
1 Introduction
We present DRAOn, a reasoner for a distributed network of aligned ontologies. The goal
of DRAOn is to be able to reason on a set of independently developed ontologies that
may overlap in concepts but are following different modelling perspectives, granularity,
coverage, etc. To be able to do that, we assume that there exists explicit correspondences
between different ontologies, that have been built by automatic ontology matchers, by
humans, or partly by both. Therefore, the structure that DRAOn is reasoning with is not
a monolithical theory, but a network of aligned ontologies. Moreover, DRAOn is able
to make use of existing reasoners as black boxes for some of its tasks.
The issues faced when reasoning with heterogeneous, distributed ontologies, even
when they have been already matched, are twofold: (a) the semantics of cross-ontology
correspondences can be tricky to define when ontologies have different modelling per-
spectives because a correspondence of terms from different ontologies does not neces-
sarily translates directly to an axiom in the ontology language (or languages); and (b)
the distribution of ontologies, and possibly of reasoning services associated with them
may influence the design of the global reasoner.
2 Background and related work
In this paper, we assume that ontologies are all Description Logic theories and we as-
sume some familiarity with DLs. We simply repeat that DL ontologies are interpreted
according to an interpretation function ·I over a domain ∆I , and interpretations that
satisfy all the axioms of an ontology are called models of the ontology. There are a
number of existing OWL DL reasoners such as HermiT [1], Pellet [2] or FacT++ [3].
In order to use several ontologies for reasoning, we assume the existence of cor-
respondences between ontologies of the form (ei , ej , r), where ei is a term from one
ontology, ej a term from another ontology, and r denotes a fixed binary relation such as
equality, subsumption, disjointness, etc. In this paper, only correspondences where r is
= (equality of individuals), ∈ (class membership) or v (subsumption) will be consid-
ered. A set of correspondences between a pair of ontologies is an ontology alignment
(or alignment for short). A set of ontologies together with their pairwise alignments is
called a network of aligned ontologies (NAO). We will use bold face to denote sets, and
therefore, the notation for an NAO will generally be hO, Ai.
Reasoning with NAOs strongly depends on the semantics of alignments. We say
that a certain semantics of alignments defines a distributed logic (sometimes called
“contextual logic“ or even “modular ontology language”). In a distributed logic L, cor-
respondences map to formula of the logic in question, so we will use a function τL to
denote the logical formula associated to the correspondence. For instance, the simplest
form of distributed logic is normal DL. An NAO can be interpreted as a DL ontology
by mapping (ei , ej , v) (resp. (ei , ej , =), (ei , ej , ∈)) to τDL (ei , ej , v) = ei v ej (resp.
ei = ej , ej (ei )). Reasoning over an NAO is then the same as reasoning with an ontology
formed by the union of all the ontologies in the NAO, and the axioms corresponding to
the correspondences.
A number of authors, including ourselves, have argued that this is not satisfying
when dealing with heterogeneous ontologies. Therefore, several other distributed log-
ics were proposed. Here we focus on the ones that are adopting a Local Model Se-
mantics (LMS [4]), among which we find Distributed Description Logics (DDL [5]),
E-connections [6], and IDDL [7]. LMS states that ontologies in an NAO have to be
interpreted separately (i.e., an interpretation of an NAO has a set of DL interpretations)
and the NAO is satisfied if each ontology is locally satisfied, and some extra knowledge,
such as alignments, can constrain further that satisfying models of the NAO. In DDL, a
v
correspondence is interpreted as a bridge rule τDDL (ei , ej , v) = i:ei −→ j:ej which
intuitively states that, from the view point of ej ’s ontology, the term ei is a subclass of
the term ej . In E-connections, correspondences can take many more forms but can be
translated into axioms using links, that are terms similar to DL roles, but which denote
binary relations between elements of different interpretations domains. More precisely,
τEconn (ei , ej , v) = ei v ∃hLiej , where L is a link, says that the elements of ei in the
first ontology are in relationship with the elements of ej in the second ontology, via link
L. Such a link axiom would be part of ontology ei , which means that it represents a fact
from ei ’s ontology point of view.
As opposed to E-connections and DDL, which treats correspondences as subjec-
tive views of an ontology wrt another ontology’s terms, we proposed Integrated Dis-
tributed Description Logics (IDDL) as a distributed logic that assumes local ontologies
are agnostic to each others, and correspondences express knowledge of a mediation
v
view that ties together the ontologies. In IDDL, τDDL (ei , ej , v) = i:ei ←→ j:ej is
simply called a correspondence. An IDDL interpretation of an NAO hO, Ai is a struc-
ture hI, i such that I = {Io }o∈O is a set of DL interpretations of the ontologies, and
= {o : ∆Io → ∆}o∈O is a set of functions (so called equalising functions) from
local domains of interpretations to a set called the global domain. The composition of
a local interpretation function ·Ii with its corresponding equalising function i defines
v
the global interpretations of local terms. A correspondence i:ei ←→ j:ej is satisfied iff
I
i (eIi i ) ⊆ j (ej j ).4
There are implementations of DDL (Drago, a tableau-based peer-to-peer reasoner [8])
and E-connections (embedded in an earlier version of Pellet. DRAOn, the reasoner de-
scribed here, implements both the classical DL semantics of NAOs, and the IDDL se-
mantics, according to our algorithm described in [9].
3 Implementation and Architecture
DRAOn implements the algorithm in [9] in Java, and provides a Java API. We first
present an overview of the algorithm before giving more implementation details.
3.1 Algorithm
Let hO, Ai be an NAO where O is a set of DL decidable ontologies, and A is a set of
alignments between these ontologies. We assume that each ontology o ∈ O is attached
to a reasoner that can be queried with a set X of DL axioms and answer whether o ∪ X
is consistent. Then, checking the consistency of an NAO amounts to querying the lo-
cal reasoners multiple times with a well chosen set of axioms. The main idea is that,
when correspondences are restricted to cross-ontology subsumption, equality or mem-
bership, alignments can only influence the vacuity (unsatisfiability) and non-vacuity
(non-emptiness) of concepts or roles appearing in the alignments.
The main steps of the algorithm are the following:
1. build an alignment ontology, noted A, which corresponds to the translation of cor-
respondences into OWL axioms (using τDL mentioned in Sect. 2);
2. if A is inconsistent then the NAO is inconsistent;
3. choose a subset S (resp. P ) of the concepts (resp. roles) appearing in A to build a
global configuration Ω consisting of axioms Ci (x) (non-emptiness) with x a fresh
individual name for each Ci ∈ S and Cj v ⊥ (unsatisfiability) for each Cj 6∈ S
(resp., Ri (x, y) for R ∈ P and > v ∀Rj .⊥ instead);
4. for a given ontology o, define a local configuration wrt o as the subset of Ω which
involves only terms from o, noted ωo ;
5. if A ∪ Ω is inconsistent, then go back to step 3;
6. for each o ∈ O, query the local reasoner attached to o using the axioms in ωo ; if
all local reasoners answer positively, then the network is consistent. Otherwise, go
back to step 3 until there are no more configuration available.
4
For a set S, (S) has to be understood as the set {(x) | x ∈ S}.
3.2 Architecture
In terms of system architecture, DRAOn consists of a global OWL reasoner and several
local OWL reasoners. The global reasoner is in charge of (i) computing global config-
urations Ω, (ii) checking consistency of A ∪ Ω for each global configuration Ω and
(iii) sending a local configuration to each local reasoner. Each local reasoner checks
consistency of o ∪ Ω.
The distributed behavior of the algorithm results from a feature of IDDL which does
not enforce a strong relationship between alignments and ontologies. Instead of merging
ontologies and alignments into a unique ontology, DRAOn distributes reasoning tasks
over ontologies to different local reasoners. In addition to early improvements, we im-
plement optimizations for reducing the number of configurations to be considered and
for improving communication protocol between global and local reasoners. The main
ideas are:
– Global configurations are built in an incremental way, and results obtained from
checking previous configurations are reused. For each configuration, we check en-
tailment rather than consistency. This allows for putting forward eventual back-
tracking points. For example, if Oi |= Ci v ⊥ (resp. Oi |= Ci (x)) then we do not
need to check the configurations that contain Oi |= Ci (x) (resp. Ci v ⊥).
– If there is a set of concepts (or roles) which are equivalent, we need to check only
configurations which contain one representative concept (or role) from this set.
– Configurations consisting of non-emptiness axioms Ci (x) are checked prior to
those consisting of unsatisfiability axioms Cj v ⊥. This idea is based on the fact
that concepts are commonly satisfiable in ontologies.
– The communication protocol between global and local reasoners is parallelized,
that means, configurations are sent to local reasoners in a broadcasting way rather
than a sequential one. The global reasoner uses Java threads to manage communica-
tion with the local reasoners. We have to use sockets to establish the communication
between global and local reasoners instead of OWLLink5 . This is due to efficiency
question and an intrinsic characteristic of IDDL.
Apart from checking consistency of an NAO, the current version of DRAOn im-
plements entailment services under the IDDL semantics for some kinds of entailment
concept axioms. Therefore, DRAOn offers the following inference services:
– Checking consistency of an NAO under the DL semantics in a non-distributed way.
In this setting, DRAOn creates a unique OWL ontology, namely global ontology,
that is obtained by merging the axioms of all ontologies and the correspondences
of alignments. Reasoning on the global ontology is performed in a non-distributed
way, that means, a OWL reasoner is used for checking consistency of the global
ontology. The network is consistent if and only if the global ontology is consistent
– Checking entailment of an OWL axiom by an NAO under the DL semantics in a
non-distributed way;
5
http://www.owllink.org/
– Checking consistency of an NAO based on the IDDL semantics in a non-distributed
way, that is, all reasoning over ontologies and alignments is sequentially performed
at one site on a computer.
– Checking consistency of an NAO based on the IDDL semantics in a distributed
way.
– Checking entailment of some kinds of OWL axioms by a network of aligned on-
tologies based on the IDDL semantics in a distributed way.
4 Experiments
DRAOn uses the OWL API6 to manipulate ontologies, the Alignment API [10] to deal
with alignments, and the HermiT (version 1.3.6) 7 reasoner to check locally consistency
of ontologies and alignments. We have performed some experiments with well-known
ontologies and alignment methods. The following table presents empirical results ob-
tained from the current version of DRAOn8 . These experiments have run on a MAC
with 4Gb RAM, 2.4 GHz Intel Core i5. The result for the distributed IDDL reasoning
was obtained with a computer network consisting of the MAC and a DELL with 2Gb
RAM, 1.06GHz Intel i2.
Ontology 1 Ontology 2 Alignment DL non-distr. IDDL distr. IDDL
Small NCI Small FMA Alcomo Map. 7,5s 46s 30s
(10,000 axioms, (3,800 axioms, (2,800 corr.)
6,500 entities) 3,700 entities)
Human Mouse Ref. Map. 6s 4.5s 4s
(5,500 axioms, ( 4,500 axioms, (1516 corr.)
3,300 entities) 2,750 entities)
IDDL reasoning performances depend on the two services OWLReasoner.getTy-
pes(.) and OWLReasoner.getUnsatisfiableClasses() which are called
for checking unsatisfiability and non-emptiness of concepts involved in alignments.
These services check for unsatisfiability and non-emptiness every concept name oc-
curring in an ontology while the algorithm for IDDL consistency requires to check for
unsatisfiability and non-emptiness only concepts involved in alignments. Consequently,
HermiT raises an “OutOfMemoryError ” when it is called for getTypes(.) on the
ontology “Small SNOMED”.
Theoretically, response time of inference services under the DL and IDDL seman-
tics increases, respectively, double exponentially and exponentially in the number of
ontologies (and the size of alignments). To make this difference occur, we might need
a very large network of aligned ontologies. In addition, it might be required to perform
further experiments to establish relationships between kinds of aligned ontologies and
IDDL reasoning performance.
6
http://owlapi.sourceforge.net/
7
http://www.hermit-reasoner.com/
8
http://iddl.gforge.inria.fr/
5 Conclusion
We have presented an OWL-based distributed reasoner, called DRAOn, which offers
inference services for a network of aligned OWL ontologies. The distributed behavior
of DRAOn is based on a feature of the IDDL semantics which allows a reasoner to dis-
tribute reasoning tasks over ontologies to different reasoners. In terms of performance,
DRAOn is considerably penalized by unavailability of specific services of an OWL
reasoner, for instance, returning all unsatisfiable concepts which belong to a given set
of concepts; or returning all non-empty concepts which belong to a given set of con-
cepts. Availability of such services in a future release of OWL reasoners may improve
dramatically the performance of DRAOn.
We intend to extend DRAOn to reasoning on a network with disjointness corre-
spondences in alignments. This may require us to develop new optimizations since the
current algorithm for such a network is highly intractable.
References
1. Shearer, R., Motik, B., Horrocks, I.: HermiT: A Highly-Efficient OWL Reasoner. In: Proc.
of the OWLED 2008. (2008)
2. Sirin, E., Parsia, B., Grau, B.C., Kalyanpur, A., Katz, Y.: Pellet: a pratical OWL-DL reasoner.
Journal of Web Semantics 5(2) (2007) 51–53
3. Tsarkov, D., Horrocks, I.: FaCT++ description logic reasoner: System description. In: Proc.
of IJCAR 2006. Volume 4130., Springer (2006) 292–297
4. Ghidini, Giunchiglia: Local Models Semantics, or contextual reason-
ing=Locality+Compatibility. ai 127(2) (2001) 221–259
5. Borgida, A., Serafini, L.: Distributed description logics : Assimilating information from peer
sources. Journal Of Data Semantics (1) (2003) 153–184
6. Kutz, O., Lutz, C., Wolter, F., Zakharyaschev, M.: E-connections of abstract description
systems. Artif. Intell. 156(1) (2004) 1–73
7. Zimmermann, A.: Integrated distributed description logics. In: Proceedings of the Interna-
tional Workshop on Description Logics. (2007)
8. Serafini, L., Tamilin, A.: Drago: Distributed reasoning architecture for the semantic web. In:
Proceedings of the Europeen Semantic Web Conference. (2005) 361–376
9. Zimmermann, A., Le Duc, C.: Reasoning with a network of aligned ontologies. In: RR.
(2008) 43–57
10. David, J., Euzenat, J., Scharffe, F., dos Santos, C.T.: The Alignment API 4.0. In: Semantic
web journal. Volume 2(1). (2011) 3–10