In the context of the communication of formal representations, it is interesting to warrant the preservation of the meaning of the representations. More precisely, between two languages L and L', a representation o of L is transformed in a representation τ(o) in L' (where τ: L→L'). We study semantic interoperability through such transformations.
Ensuring semantic interoperability can be defined by the two complementary equations:
∀δ∈L, o⊨Lδ => τ(o)⊨L'τ(δ)
∀δ∈L, τ(o)⊨L'τ(δ) => o⊨Lδ
Ensuring general interoperability is, of course, out of reach. Consequently we study restricted cases of these equations.
Goal: Characterising, for particular sets of techniques, how they can warrant interoperability (the equations above). Listing the conditions under which these techniques work correctly.
Instead of studying general semantic properties, we can focus on a particular language and the properties preserved by "natural transformations" on this language's objects. We consider here graph-based languages that can encode knowledge expressed in different formalisms (which instances can be RDF or Conceptual Graphs).
We will study how elementary graph transformations preserve the semantics in the sense of equations (1) and (2). [Baget 2001] proposes problem reductions for different graph-based knowledge representation formalisms (mainly Conceptual Graphs-based). These reductions often rely on elementary transformations such as:
These transformations (with polynomial - and often linear - time complexity) do not only preserve positive instances for the entailment-problem, but they also preserve all models (more precisely, equivalence classes for these models).
Though akin to problem reduction in the algorithmic traditional sense, our transformations can be quite different. Indeed, though polynomial complexity is desirable, it is not required; our transformations do not have to be complete; and the answer "yes" or "no" to a decision problem is not sufficient, since we are interested in the preservation of models.
This work can be used as the foundations for a library of transformations of semantically grounded labeled graphs. Analysis of these transformations should take into account the following properties:
We have started classifying the manifestations of equation (1) for language-to-language transformations. This reveals various cases:
We have established various implications between properties of this type. This allows the determination of the property satisfied by a compound transformations used for transforming from a language to another. We still have to complete these first results and integrate property composition in Transmorpher.
Producing the semantic properties cited in the previous sections is not obvious. But it is possible to take advantage of particular structures related to languages or theories. We have considered two types of structures, which, applied to the representation, facilitates the access to properties.
A family of languages is a set of languages which share constructors having the same interpretation in all the languages. A family can be structured such that there always exist a language L∨L' such that any formula of L or L' is a formula of L∨L'. A good example of a family of languages is the description logics for which an extensive hierarchy of languages has been defined [Baader 2003].
This structure has been used for the development of DLML [Euzenat 2001e]. We have experimented with the description logic family, the proof of semantic properties for transformations when the properties are known for elementary transformations [Stuckenschmidt2001a, Euzenat2003a]. Assigning properties to transformations enables the search of a path (implemented by the composition of transformations) in the languages of the family such that the property is preserved.
In the general case, it is possible that two languages share a common structure (as opposed to common constructors). This is particularly true when they come from the same source. A trend consists of adapting the concept of "pattern" from software engineering to ontology development [Staab 2001]. The instantiation of a pattern p in a language L amounts to producing a morphism μ: p→L.
The goal of patterns is to share common parts and to facilitate translation from one language to another. Formally, when a morphism is reversible (i.e. the element used in L for expressing the concept corresponding to p are not used for something else), it is the possible to define the transformation τ=μ-1oμ'. This transformation will faithfully transcribe the notion described by p.
In order to obtain tangible results on patterns, it is necessary to further define them and their possible instantiation mechanisms. Indeed, concrete languages correspond to the instantiation of several patterns to which a few particular constructions are added. Relevant languages will be dependant of the kind of property to be satisfied.
|< Transformations and properties