Reasoning on a network of aligned ontologies has been investigated in di erent contexts where the semantics given to correspondences di ers from one to another. In this paper, we introduce a new semantics of correspondences which is weaker than the usual one and propose a procedure for reasoning over a network of aligned ontologies with link keys [1] in a decentralized manner, i.e. reasoning can be independently performed on di erent sites This process allows to reduce polynomially global reasoning to local reasoning. To achieve such results for a network of ontologies expressed in the description logic ALC, the semantics of a correspondence, denoted C ! D where C and D are concepts in ontologies Oi and Oj respectively, is de ned as an implication of concept unsatis abilities (i.e. unsatis ability of D implies unsatis ability of C) rather than a concept subsumption as usual. This weakened semantics allows to reduce the reasoning complexity over a network of aligned ontologies since (i) only individual equalities and concept unsatis abilities such as a b, C v ? can be propagated from one to another ontology, and (ii) if a concept is locally unsati able in an ontology then it remains unsatis able when adding to the ontology individual equalites or concept unsatis abilities. The weakened semantics would be relevant for correspondences between ontologies of di erent nature. Given two ontologies about equipment and staff and a correspondence Computer ! Developer between them. With this correspondence, the weakened semantics tells us that if there is no developer then there is no computer. The standard semantics is irrelevant in this case. n n We use hfOigi=1; fAij gi=1;j=2;i<j i to denote a network of ontologies where each Oi is an ontology expressed in ALC and each Aij contains individual correspondences, link keys with the usual semantics, or concept correspondences with the weakened semantics. Such a network is consistent if there is a model Ii of each ontology Oi which satis es all correspondences in each Aij . We will present our algorithms for a network composed of two ontologies O1; O2 and an alignment A12. These algorithms can be straightforwardly extended to a general network of aligned ontologies.
As discussed in Section 1, the weakened semantics of alignments allows us to decompose checking consistency of a network into two steps which consist in propagating knowledge from one to another ontology.
Propagating individual equalities. This step discovers all inferred individual equalities by applying link keys in the alignment and using local reasoners for entailment on ontologies. For example, a new individual correspondence a b will be discovered and added to A12 if fhP; QiglinkkeyhC; Di 2 A12, c d 2 A12 and P (a; c) 2 O1, Q(b; d) 2 O2. A new equality a c will be discovered and added to O1 if a b; c b 2 A12. When a local reasoner is called to check whether Oi j= a b, it needs only one Oi for reasoning.
Propagating concept unsatis abilities. This step uses local reasoners associated with ontologies to discover from each ontology Oi new unsatis able concepts which can result from unsatis able concepts in Oj via concept correspondences. For instance, if O1 j= C v ? and C D 2 A12 then a new axiom D v ? will be added to O2. As the previous step, each local reasoner needs only one Oi for reasoning.
The main algorithm executes these two steps until either an inconsistency is found, or a stationary state is reached. If O1, O2 are consistent, and A12 does not contain any pair a b; a 6 b, then the network itself is consistent. Our algorithm runs in polynomial time in the size of the network since the propagation procedures add only axioms and assertions which are composed of (sub-)concepts and named individuals occurring in the ontologies and alignments. Moreover, these algorithms never remove anything from the network.
Implementation and tests. The algorithms has been implemented and
integrated within DRAOn [