Three Semantics For Distributed Systems and Their Relations With Alignment Composition
Three Semantics For Distributed Systems and Their Relations With Alignment Composition
Three Semantics For Distributed Systems and Their Relations With Alignment Composition
INRIA Rhône-Alpes
Montbonnot Saint-Martin, France
{Antoine.Zimmermann,Jerome.Euzenat}@inrialpes.fr
1 Introduction
2 Related Work
The relation symbol R is out of the ontology languages. So it does not have
to be interpreted in the local semantics. For instance, a temporal relation can
be expressed between two OWL classes. The associated relation R e is fixed, given
a set of relation R. For instance, relation symbol ≡ could be associated to the
relation “=” (equality) over sets.
If all correspondences are satisfied, then it is said that the pair of interpre-
tations is a model of the alignment.
4.3 Models of a DS
Informally, interpretations of a DS are tuples of local interpretations.3
Definition 9 (Interpretation of a DS). An interpretation of a DS h(Oi ), (Aij )i
is a family (mi ) of local interpretations over a common domain D such that for
all i ∈ I, mi is an interpretation of Oi .
Among interpretations, some are said to satisfy the DS. In order to satisfy a
DS, interpretations must satisfy constraints given by (1) the ontologies axioms
and (2) the alignments correspondences.
Definition 10 (Model of a DS). A model of a DS S = h(Oi ), (Aij )i is an
interpretation (mi ) of S such that:
– ∀i ∈ I, mi ∈ Mod(Oi ) (i.e., mi is a (local) model of Oi );
– ∀i, j ∈ I, mi , mj |= Aij .
This is written (mi ) |= S. If a model exists for S, we say that S is satisfiable.
We can see that this definition employs a very global view of the models. All
ontologies and alignments are taken into account at the same time, and there
are strong interdependencies. This is because the DS is seen as a single theory,
with ontologies being but mere modules.
However, it is often the case when we only want to reason about local data,
while taking advantage of external knowledge. So we define local models modulo
a DS:
Definition 11 (Local models modulo a DS). Local models of an ontology
Oi modulo S are the local models ModS (Oi ) = {mi ∈ Mod(Oi ); ∃(mj )j6=i ∈
Mod(Oj ), (mi )i∈I |= S}. It corresponds to the projection of the models of a DS
on the ith component.
With this definition, the models of the full system must be known to compute
the local models. In order to build more efficient reasoners, we define another
notion of models that do not require total integration of all ontologies and align-
ments at once. It is based on an iterative process of gradually reducing the local
models.
3
As in Sect. 3, I denotes a set of indexes and is omitted in expressions like (Aij ),
when there is no ambiguity.
Definition 12 (Models of an ontology modulo alignment). Given an on-
tology O1 aligned with O2 according to alignment A, the models of O1 modulo A
are those models of O1 that can satisfy A:
ModA (O1 ) = {m1 ∈ Mod(O1 ); ∃m2 ∈ Mod(O2 ); m1 , m2 |= A}
Models modulo alignment is the first step of the following iterative definition.
Definition 13 (Iterated local models modulo a DS). Given a DS S =
h(Oi ), (Aij )i, consider Mod0S (Oi ) = Mod(Oi ), and the following iterative defini-
tion:
ModkS (Oi ) = {mi ∈ Modk−1 k−1
S (Oi ); ∀j ∈ I\{i}, ∃mj ∈ ModS (Oj ); mi , mj |= Aij }
ModS (O) denotes the limit of the sequence (ModnS (O)) when n → ∞, i.e.,
ModS (O) = Mod∞
S (O).
/e1
Proof. We give a sketch of the proof4 with a diagram representing the DS.
O1 O e01
O
/e2o /e3o
≡ ≡
≡
O2 O3
In this DS, we have ModnS (Oi ) = Mod(Oi ) for all n ∈ IN and i ∈ {1, 2, 3}. But
ModS (O1 ) is restricted to the models of O1 where e1 and e01 are interpreted as
the same entity. t
u
In spite of this unfavorable property, ModS (O) and ModS (O) are two solu-
] S (Oi ) = {m ∈ Mod(Oi ); ∀j ∈ I \{i}, ∃mj ∈
tions to the fixed-point equation Mod
] S (Oj ); mi , mj |= Aij }. This means that locally reasoning with iterated mod-
Mod
els will not contradict neighborhood reasoning.
The proposed semantics is somewhat strict, with regard to heterogeneous
systems, because it only allows to assert a correspondence when it is fully com-
patible with both ontologies. While it may be desirable in a few applications, this
semantics is not adapted to every ontology alignment use cases. For instance, in
the semantic web, ontologies will vary tremendously in size, scope, scale, point
of view and quality. We consider two semantics that address this problem.
4
For a detailed proof of this proposition, please refer to the following url:
http://www.inrialpes.fr/exmo/people/zimmer/ISWC2006proof.pdf.
5 Dealing with Heterogeneous Domains
The choice of the interpretation domain is not only guided by the interpreter, but
also partly decided by the local language semantics. So we will use the concept
of an equalizing function to help making the domain commensurate.
So equalizing functions not only define a global domain for the interpreta-
tion of the DS, but also define how local domains are correlated in the global
interpretation.
The integrated interpretations that satisfy the DS are given by the following
definition.
ModkS (Oi ) =
{mi ∈ Modk−1 k−1
S (Oi ); ∀j ∈ I \ {i}, ∃mj ∈ ModS (Oj ), ∃γ; γi mi , γj mj |= Aij }
5
The notation γi mi is used to denote the composition of functions γi and mi . In fact,
γi mi is an interpretation of Oi in the global domain.
As with simple distributed semantics, there is a notion of local and global
satisfiability (see Def. 14). The integrated iterated models have the same property
as the simple iterated models (Prop. 1 and Prop. 2).
Proof (of Prop. 2). We give a sketch of the proof6 with a diagram representing
/e2
the DS.
x< bEEE ≡
O2
≡ xx EE
/e1Rh R "e o
x EE
xx
RRRy< 2bDDlDlll6 3
x
| 0
O1 e O3
≡ yyR≡ l
y RlRlRl DD ≡
ylyllll≡ RRRRDRD"
e1o 3
0
y
| v
l (/ e 0
6≡
ModkS (Oi ) =
{mi ∈ Modk−1 k−1
S (Oi ); ∀j ∈ I \ {i}, ∃mj ∈ ModS (Oj ), ∃rji ; mi , rji mj |= Aij }
Again, there is a notion of local and global satisfiability (see Def. 14). The
contextualized iterated models have the same property as the simple iterated
models.
Proof (of Prop. 2). We give a sketch of the proof7 with a diagram representing
the DS.
/e1o ≡
/e2o ≡
/e3o
x<
O1 O3
x
xx
6≡
xx
e1o /e02o
0 ≡ | x
O2
Among the local models of O1 modulo this DS, there are interpretations where
e1 and e01 are interpreted identically, while the global models necessitate that
they are interpreted differently. t
u
6 Composing Alignments
Building alignments is a difficult task that can hardly be done fully automati-
cally. So existing alignments shall be reused to offer faster interoperable applica-
tions. Alignment composition is one of the key operations permitting this. Given
three ontologies O1 , O2 and O3 , with alignments A of O1 and O2 , and B of O2
and O3 , it must be possible to deduce a third alignment of O1 and O3 , which
we call the composition of A and B.
We propose here two notions of composition: the first is the syntactic compo-
sition of alignments, which can straightforwardly be implemented; the second is
“semantic composition”. Semantic composition is informally defined as follows:
given a DS of 3 ontologies and 2 alignments S = hhO1 , O2 , O3 i, hA12 , A23 ii, the
semantic composition is the submodels of Mod(S) that are models of the sub-
system hhO1 , O3 i, ∅i (see below for a more formal definition in each of the three
semantics).
7
For a detailed proof of this proposition, please refer to the following url:
http://www.inrialpes.fr/exmo/people/zimmer/ISWC2006proof.pdf.
Definition 23 (Syntactic composition). Let A12 be an alignment of O1 and
O2 , and A23 an alignment of O2 and O3 . The composition of A12 and A23 ,
noted A23 ◦ A12 is the set of triples he1 , e3 , Ri such that there exist e2 , R1 , R2
s.t. he1 , e2 , R1 i ∈ A12 , he2 , e3 , R2 i ∈ A23 and R = R1 ; R2 with “;00 : R × R → R
being an associative operator.
Remark 1. “;” may also be given by a table of composition. In that case, relations
R ∈ R are sets of primitive relations. Moreover, composition is associative iff “;”
is associative.
In our first semantic approach, the models of A are pairs of interpretations
of O1 and O2 , so Mod(A12 ) is a set-theoretic relation. Relations are composable,
and ideally the composition of A12 and A23 should have equal models as the
composition of Mod(A12 ) and Mod(A23 ).
Let S be a DS having 3 ontologies O1 , O2 , O3 and 2 alignments A12 , A23 .
Definition 24 (Simple semantic composition). The simple semantic com-
position of the simple models of A12 and A23 , noted Mod(A23 ) ◦s Mod(A12 ) is
the set:
{hm1 , m3 i ∈ Mod(O1 ) × Mod(O3 ); ∃m2 ∈ Mod(O2 ), hm1 , m2 , m3 i ∈ Mod(S)}
In the case of the integrated semantics, the definition should include the
equalizing function.
Definition 25 (Integrated semantic composition). The integrated seman-
tic composition of the integrated models of A12 and A23 , noted Mod(A23 ) ◦i
Mod(A12 ) is the set:
{hhm1 , m3 i, hγ1 , γ3 ii; ∃m2 , γ2 , hhm1 , m2 , m3 i, hγ1 , γ2 , γ3 ii ∈ Mod(S)}
Similarly, the contextualized semantics define a composition with domain
relations.
Definition 26 (Contextualized semantic composition). The contextual-
ized semantic composition of the contextualized models of A12 and A23 , noted
Mod(A23 ) ◦c Mod(A12 ) is the set:
{hhm1 , m3 i, hr13 , r31 ii; ∃m2 , r12 , r21 , r23 , r32 , h(mi )i∈{1,2,3} , (rij )i6=j i ∈ Mod(S)}
These definitions are rather intuitive and correspond to what is found in
constraint reasoning literature, with slight variants due to the presence of equal-
izing functions and domain relations. The following section compares the three
ontologies, and shows that composition is semantically sound in the first two
semantics, but not in the contextualized one.
7 Comparing Semantics
Our three semantics do not only differ by their conceptual design. They also
imply technical differences.
7.1 Simple Semantics
The following diagram helps visualizing the idea behind the simple semantics.
Each ontology is treated as a module of a bigger ontology, interpreted in a single
domain.
Syntax level O1 G O24 ··· On
GG 44 w
GG 4 ww
I1 IG 2G 4 ww
G# 4 ···{www In
D = i∈I Di
Semantics level
S
O
domain.
Syntax level 1 O2 ··· On
D
1 G D24 Dn
I1 I2 ··· In
Local semantics level ···
GG 4 w
G 44
γ1 G
ww
wwγn
# {w
γG
2G 4 w
U
GG4 ww···
O
own context.
Syntax level 1 O2 ··· On
D *
1 a j Dn
I1 I2 ··· In
*
r12 r2n
r1n
This approach is very similar to context-based logics approach and the in-
terest of contextualizing inferences is explained in e.g., [2].
However, the following result tend to disqualify this semantics when compos-
ing alignments becomes a necessity:
Proposition 3. Prop. 1 does not hold in contextualized semantics.
Proof. Consider the following DS9 :
/e1o v /e2o v
/e3o
O1 Fb F O3
FFw
FF
/e02o /e03
F" w
O2
t
u
Additionally, we show the generality of our integrated semantics with the
following proposition:
Proposition 4. If a contextualized model exists for a DS, then there exists an
integrated model.
Proof. Let h(mi ), (rij )i be a model of a DS. Let k ∈ I be an indice then
h(mi ), (rik )i∈I i, with rkk = idDk is an integrated model of the DS with global
domain Dk . t
u
This property was in fact predictable. The contextualized semantics has a
different purpose: it interprets semantic relations from one ontology’s point of
view. Composing alignments in this way is not sound because two consecutive
alignments are interpreted according to two different points of view. However,
it has a strong advantage with regard to the integration of external knowledge
into a specific ontology.