Alignment API: Algebraic operations

Algebraic operations are possible on networks of ontologies, alignments, relations and confidence measures.

They are increasingly supported by using Algebras of relations. We present below the algebraic interface offered by each class of the API.

Operations on Networks of ontologies

The OntologyNetwork interface of the API defines the following operators:

invert()
returns the network of ontologies with all alignments inverted.

In addition, our BasicOntologyNetwork implementation offers:

close(boolean reflexive, boolean symmetric, boolean transitive)
computes the reflexive-symmetric-transitive closure of a network of ontologies by adding to it the reflexive, symmetric, or composition of alignments found in the network.
meet(OntologyNetwork)
Returns the ontology network made of all ontologies and alignment from any of the networks ;
join(OntologyNetwork)
Returns the ontology network made of all ontologies and alignment present in both networks. The alignments are computed through the join operation .

Operations on Alignments

The Alignment interface of the API defines the following operators:

inverse()
From an alignment between o1 and o2, returns an alignment between o2 and o1 based on the converse of relations (Relation.inverse()). A-1={c-1; c∈ A} such that c-1 is the converse of cell c;
meet(Alignment)
Returns an alignment which contains all correspondences which are in any of the alignments. A⊕A'={c; c∈ A ∨ c∈ A'};
join(Alignment)
Returns an alignment which contains all correspondences which are in both alignments. In order to be correct, such operation requires to decide when two correspondences have an intersection. A⊗ A'={c; c∈ A ∧ c∈ A'}.
diff(Alignment)
Returns an alignment which contains all correspondences which are in the first alignment but not in the second. As for join, such operation requires to decide what part of a correspondence is part of another. A⊖A'={c; c∈ A ∧ c∉ A'};
compose(Alignment)
A⊙A'={c⊙c'; c∈ A ∧ c'∈ A'} in which c⊙ c' is the composition of cells;

In addition, our BasicAlignment implementation offers:

aggregate(modality, Alignment...)
Computes an alignment containing all correspondences of the alignments provided as input, with a confidence aggregated according to the modality (min/max/avg/pool).
cut(modality, threshold)
Suppresses from the alignment all correspondences whose confidence is below a threshold intepreted according to the modality (perc/best/hardgap/propgap/hard/span/prop).

Operations on Cells

The Cell interface of the API the following operations:

compose(Cell)
⟨ e,e',n,r⟩⊙⟨ e',e'',n',r'⟩=⟨ e,e'',n⊗ n',r⊙ r'⟩ in which r⊙ r' is the composition of relations and n⊗ n' the conjunction of confidences;
inverse()
⟨e,e',n,r⟩-1=⟨e',e,n,r-1⟩ such that r-1 is the converse of relation r;

Strictly speaking, if one considers the semantics of relations and confidence measures, the composition of two cells should provide a set (conjunction of cells).

Operations on Relations

The Relation interface of the API offers the following operations:

compose(Relation)
(r⊙r') Provides the composition of two relations and null if it does not exists.
inverse()
(r-1) Provide the converse of a relation and null if it does not exist.

In addition, the DisjunctiveRelation interface of the implentation offers:

meet(Relation...)
(r⊕r'...) Returns the disjunction of relations appearing in any of the relations.
join(Relation...)
(r⊗r'...) Returns the disjunction of relations appearing in all the relations.

Various relation languages may be used in the Alignment API. They have to be declared through BasicAlignment.setRelationType( className ) such that classname is the name of a class implementing the Relation interface. It is also recorded in the Alignment format through the relationClass attribute.

By default, the implementation is fr.inrialpes.exmo.align.impl.BasicRelation.

The BasicRelation implementation only has two inverse relations (⊆ and ⊇) the other being self-inverse. It implements the following composition table:

⊆=⊇
⊆⊆⊆⊥
=⊆=⊇
⊇⊥⊇⊇

Other such classes have been implemented in the Alignment API in order to support an increasing number of operations. These are (supported operations in parenthesis):

BasicRelation
Which allows for dealing with simple independent relations.
DisjunctiveRelation (meet,join)
In which each relation is in fact a disjunction of base relations.
AlgebraRelation (inverse,composition)
Which implements relations from an algebras of relation, i.e., supporting join, meet, complement, inverse, and composition.
These classes are abstract by nature, if not by implementation and have to be refined to implement concrete algebras.

Only the AlgebraRelation interface offers the formally defined operations of algebras of relations. The current implementation of the API offers several algebras of relations:

fr.inrialpes.exmo.align.impl.rel.A2RelationAlgebra
for relations between instances,
fr.inrialpes.exmo.align.impl.rel.A5RelationAlgebra
for relations between classes,
fr.inrialpes.exmo.align.impl.rel.A16RelationAlgebra
for relations between classes including empty classes, instances and across them.

Operations on Confidences

There is no Confidence component in the API. However, the implementation of the API has such a generic component, even if all their values are implemented as double.

The confidence measures should implement a triangular co-norm structure.

The BasicConfidence class offers the two operations:

conjunction(double confidence)
(n⊗n') Returns the confidence associated to the conjunction of two statements with attached confidence (it is implemented by the min operation);
disjunction(double confidence)
(n⊕n') Returns the confidence associated to the disjunction of two statements with attached confidence (it is implemented by the max operation).
getTopConfidence()
Returns the highest confidence (implemented as 1.0).
getBottomConfidence()
Returns the lowest confidence, the one which corresponds to ignoring the correspondence (implemented as 0.0).

Using algebras of relations with the Alignment format and EDOAL

Such relations algebra may be used from the Alignment format (including EDOAL alignments), through the use of the relationClass extension in the alignment header: 

<Alignment>
  <xml>yes</xml>
  <level>0</level>
  <type>**</type>
  <relationClass>fr.inrialpes.exmo.align.impl.rel.A5AlgebraRelation</relationClass>
  <onto1>
  ...

Defining a new algebra of relations

In principle, defining a new algebra of relations amounts to provide:

  • The list of base relations;
  • The identity relation;
  • The relation inverse function;
  • The relation composition function.
We have dreamed to provide a framework in which implementing just this would be sufficient.

However, due to Java limitations, we have not been able to do so. The best solution that we found amounts to duplicate an existing algebra such as A5RelationAlgebra and A5BaseRelation and to modify only the parts above.

More precisely, in A5BaseRelation, declare the set of base relations with its label: 

    EQUIV ( "=" ),
    SUBSUMED( "<" ),
    SUBSUME( ">" ),
    OVERLAP( ")(" ),
    DISJOINT( "%" );
Then, in A5RelationAlgebra, declare all these relations and their inverse (the identity relation comes first): 
	declareRelation( A5BaseRelation.EQUIV, A5BaseRelation.EQUIV );
	declareRelation( A5BaseRelation.SUBSUME, A5BaseRelation.SUBSUMED );
	declareRelation( A5BaseRelation.SUBSUMED, A5BaseRelation.SUBSUME );
	declareRelation( A5BaseRelation.OVERLAP, A5BaseRelation.OVERLAP );
	declareRelation( A5BaseRelation.DISJOINT, A5BaseRelation.DISJOINT );
and the composition table: 
	// ---- EQUIV
	o( A5BaseRelation.EQUIV, A5BaseRelation.EQUIV,
	   A5BaseRelation.EQUIV );
	o( A5BaseRelation.EQUIV, A5BaseRelation.SUBSUME,
	   A5BaseRelation.SUBSUME );
	o( A5BaseRelation.EQUIV, A5BaseRelation.SUBSUMED,
	   A5BaseRelation.SUBSUMED );
	o( A5BaseRelation.EQUIV, A5BaseRelation.OVERLAP,
	   A5BaseRelation.OVERLAP );
	o( A5BaseRelation.EQUIV, A5BaseRelation.DISJOINT,
	   A5BaseRelation.DISJOINT );
	// ---- SUBSUME
	o( A5BaseRelation.SUBSUME, A5BaseRelation.EQUIV, 
	   A5BaseRelation.SUBSUME );
	o( A5BaseRelation.SUBSUME, A5BaseRelation.SUBSUME, 
	   A5BaseRelation.SUBSUME );
        ...
Alternatively the composition table can be described through a set of consistent triples (example from the A2 algebra): 
	t( A2BaseRelation.EQUIV, A2BaseRelation.EQUIV, A2BaseRelation.EQUIV );
	t( A2BaseRelation.EQUIV, A2BaseRelation.DIFF, A2BaseRelation.DIFF );
	t( A2BaseRelation.DIFF, A2BaseRelation.DIFF, A2BaseRelation.DIFF );

Finally, in the two Java classes, the names A5BaseRelation and A5RelationAlgebra should be globally replaced by their new names.

The new algebra can be used as the others predefined ones. In fact, it is not even necessary to define A5BaseRelation as public it may be kept private to the Algebra file.

Combining algebras of relations

Alignments may express relations from different standpoints or consider different types of entities (concepts, properties, individuals). Algebras of relations for such situations (such as A16) may be obtained by combining simpler algebras of relations.

This is ongoing work which will come in due time to the Alignement API either through an offline algebra generator (generating Java classes implementing the combined algebra) or through an online combinator (able to interpret the combination of algebras on the fly).

Composing matching algorithms

Besides the composition of alignments, it is possible to compose matching methods.

One of the claimed advantages of providing a format for alignments is the ability to improve alignments by composing matching algorithms. This allows iterative matching: starting with a first alignment, followed by user feedback, subsequent alignment rectification, and so on. A previous alignment can, indeed, be passed to the align method as an argument. The correspondences of this alignment can be incorporated in those of the alignment to be processed.

For instance, it is possible to implement the StrucSubsDistNameAlignment, by first providing a simple substring distance on the property names and then applying a structural distance on classes. The new modular implementation of the algorithm yields the same results.

Moreover, modularizing these matching algorithms offers the opportunity to manipulate the alignment in the middle, for instance, by triming resulting alignments. As an example, the algorithm used above can be obtained by:

  • matching the properties;
  • triming those under threshold;
  • matching the classes with regard to this partial alignment;
  • generating axioms (see below);

http://alignapi.gforge.inria.fr/algebra.html
$Id$