Ce chapitre propose une modélisation formelle des types d'éléments des documents structurés. Il propose également un ensemble de relations entre ces types sur lesquelles nous fondons les principes de la transformation présentée dans la section suivante. Nous abordons ici une étude du système de types des documents qui fait suite à une réflexion plus générale sur les systèmes de types dans les langages de programmation. Dans cette réflexion, donnée en annexe A, nous décrivons l'algorithme d'unification permettant de calculer l'équivalence de deux types.
Il existe une analogie entre les systèmes de types des langages de programmation, qui définissent des types de données, et ceux des documents structurés qui définissent des types d'éléments de documents. Cette analogie laisse à penser que les algorithmes de vérification de type, d'inférence et d'unification (voir A) peuvent s'appliquer à la transformation de documents structurés. Dans ce chapitre, nous présentons les différences entre les deux notions de type au point de vue de leur conception mais aussi dans l'utilisation qui en est faite.
Les différences entre les structures génériques de documents structurés et les systèmes de types des langages de programmation sont en partie dues à la différence de nature de l'information traitée : les documents structurés détiennent une dimension sémantique qui n'est pas accessible aux applications de traitement, alors que l'ensemble de l'information d'un programme - à l'exception des commentaires - est interprétée par le compilateur. Les documents sont également traités de façon plus incrémentale que les programmes : un programme doit être complet avant d'être compilé ou exécuté, tandis que les applications documentaires, en particulier les éditeurs, travaillent sur les documents en cours de leur construction. Par conséquent, ces applications doivent pouvoir représenter et traiter des documents qui ne sont pas complets.
Ces différences de nature entre documents et programmes se répercutent sur les systèmes de types.
Lors de son élaboration, un document, comme un programme, passe par des phases pendant lesquelles sa structure est incomplète. Les programmes incomplets ne peuvent être compilés ni exécutés car le système à besoin de la totalité de la sémantique pour l'exécution. Si certaines parties du programme ne sont pas implémentées, les interface des fonctions externes - utilisées par le reste du programme - doivent cependant exister pour que le programme soit conforme au système de types du langage.
Il existe plusieurs niveaux de conformité du document par rapport à la structure générique d'une classe. Suivant les applications, les besoins de conformité peuvent être plus ou moins stricts. L'algorithme présenté dans l'annexe A détermine une conformité au sens strict du document par rapport à la structure générique qui définit la classe à laquelle il appartient. Un document présentant cette propriété est un document valide. Cet algorithme est utilisé par les programmes de vérification de la validité des documents [W3C a] et les analyseurs XML validants [W3C b].
Certaines applications documentaires doivent pouvoir traiter les documents non complets et donc non valides. C'est le cas des éditeurs qui doivent permettre de stocker, d'ouvrir, de modifier et d'échanger des documents en cours de réalisation. En revanche, d'autres applications, par exemples utilisées pour la publication ou l'archivage, nécessitent qu'un document soit valide pour pouvoir le traiter.
Ces deux niveaux de conformité de documents se retrouvent dans la norme XML qui différencie les documents valides des documents bien formés.
Une composante importante des documents structurés que l'on ne retrouve pas dans les systèmes de types concerne les attributs. Ceux-ci servent à expliciter une partie de la sémantique inhérente au contenu du document. Ils sont interprétés par les différentes applications pour procéder à des traitements particuliers. Ces traitements sont, par exemple, l'indexation automatique et la mise en valeur des mots portant un attribut mot important ou le choix du dictionnaire lors de la correction orthographique d'un document multilingue qui est déterminé par un attribut langue.
Les normes de documents structurés XML et SGML définissent des types d'attributs : ceux-ci peuvent être énumérés, textuels ou désigner des entités externes comme d'autres documents ou des ressources d'une autre nature (images, graphiques, etc.). Dans une DTD, un ensemble d'attributs est défini relativement à un type d'élément, les attributs peuvent être obligatoires ou optionnels. Le modèle de types doit donc être étendu pour que chaque noeud du graphe de types puisse supporter des attributs.
Thot permet de définir quatre types d'attributs : les attributs entiers, énumérés, textuels et référence. Les attributs référence désignent des éléments de structure dont le type peut être fixé ou non. Comme dans SGML et XML, les attributs sont relatifs à un type d'élément, mais ils peuvent également être définis de façon globale et être alors associés à tout type d'élément.
Les systèmes de documents structurés proposent des mécanismes permettant une modularité des documents de façon que des structures génériques puissent être partagées par plusieurs classes de documents.
SGML et XML permettent l'inclusion d'éléments externes par l'intermédiaire des entités. Une extension de XML appelée namespaces [Bray 98b] définit un mécanisme pour intégrer des éléments de plusieurs DTD dans un même document. Ce mécanisme permet à plusieurs applications d'ajouter des éléments spécifiques dans un document en utilisant son propre espace de noms, c'est le cas XSL, présenté dans la section 3.3.3.7 qui définit un espace de nom xsl pour représenter les directives de transformation.
D'autres applications utilisent les espaces de noms pour définir des objets de natures différentes, tout en utilisant le même modèle de documents structurés. Ainsi, Amaya permet de mélanger la structure HTML avec des équations mathématiques définies par la DTD MathML. Thot utilise également les namespaces pour représenter des natures qui permettent l'inclusion d'éléments de structures génériques différentes dans un document. Ainsi les classes de documents rapport, chapitre, exposé et lettre partagent la même définition des paragraphes, des tables et des graphiques.
La modularité des structures génériques implique que plusieurs systèmes de types coexistent au sein d'un même document. Ces systèmes de types utilisent les mêmes constructeurs (agrégat, liste, choix, identité) mais définissent des espaces de noms de types différents. Deux types définis dans des structures génériques différentes et portant le même nom peuvent coexister dans le même document.
Toutes les normes de documents structurés permettent de définir des éléments optionnels dans la DTD. Ces éléments peuvent être présents dans la structure du document, mais ne sont pas requis pour la conformité du document. Cela implique que certaines parties du graphe de types ne doivent pas être utilisées systématiquement par les algorithmes de comparaison de types.
Thot et SGML proposent des mécanismes d'inclusion et d'exclusion, permettant respectivement d'autoriser ou d'interdire certains types d'éléments dans la construction d'un autre type d'élément. Par exemple, une archive de messages tels que ceux donnés dans la figure 14, qui contient des messages anonymes ou non et leur attribue un numéro d'archivage peut être définie par la DTD SGML suivante qui autorise la présence d'un élément idarchive dans les éléments anonyme et message et exclut l'élément expéditeur des éléments messages contenus dans les éléments anonyme :
<!ELEMENT archive - - (anonyme|message)+ +idarchive > <!ELEMENT anonyme - - (message) -expéditeur>
Dans la section précédente nous avons présenté les différences d'interprétation par les applications de la sémantique liée aux systèmes de types selon que ces applications soient du domaine de la gestion de documents ou de la programmation. Comme les langages de programmation, les documents structurés utilisent des systèmes de types particuliers. Au delà de leur utilisation par les applications, les systèmes de types proposés par les normes comme SGML et XML ne sont pas adaptés à la comparaison de types «classique».
Le premier argument implique que la part de sémantique contenue par le type d'un objet de base dans un langage de programmation n'est pas représentée dans le système de type des documents structurés. Cette sémantique est remontée au niveau du contenu textuel de l'élément et réclame des outils d'analyse plus puissants que ceux proposés par les algorithmes de l'annexe A. Les deux autres arguments révèlent une incapacité plus fonctionnelle de ces algorithmes, ne leur permettant pas de s'appliquer à un arbre de types déduit directement de la DTD.
Nous définissons donc une représentation adaptée des systèmes de types des documents permettant de prendre en compte ces facteurs. De plus, les informations nécessaires à la transformation sont représentées dans ce système de types qui précise la définition des documents structurés énoncée en 2.3.1.
Dans la deuxième partie de ce chapitre nous nous servirons de ce système de type pour définir des relations entre les structures des types source et cible pour permettre la transformation.
Avant de définir les relations entre types que nous utiliserons pour la comparaison, il convient de donner une définition précise de la représentation des types d'éléments de document que nous utilisons. Nous proposons donc ici un système de types adapté à la transformation de documents. Ce système de types précise la définition des documents structurés énoncée en 2.3.1.
Dans la norme XML, le système de types est décrit dans les
règles de définition d'une DTD (règle
elementDecl de la spécification [Bray 98a]). Pour faciliter le stockage et
l'échange des documents, la norme XML ne décrit qu'un seul type
de base : le type texte (CDATA), les autres composantes atomiques du document
(images, vidéo, graphiques) sont des références à
des objets externes au document. Ces références sont
définies par des attributs textuels.
Pour conserver la nature des objets de base des documents lors des
transformations de structure, nous avons choisi d'intégrer ces
références dans le système de types des documents
structurés. Pour une meilleure lisibilité, nous donnons comme
nom aux types de base de notre système, les types des
éléments désignés par les
références. Ainsi un élément faisant
référence à une image (par exemple,
l'élément vide <IMG
href="http://www.inria.fr/logo.gif"> en HTML), sera pour nous un
élément de type Image. Nous définissons ainsi un
ensemble de type de base commun à l'ensemble des DTD :
B = {texte, symbole, graphique,
image, référence}.
Pour intégrer les éléments vides qui ne référencent pas d'objets externes nous étendons l'ensemble B avec les représentants de ces types pour former l'ensemble des types de base définis par une DTD S, noté BS.
Les constructeurs que nous définissons dans notre système sont :
Un élément dont le constructeur de type est l'identité n'a qu'un seul fils. Dans une DTD XML, un élément de type identité est déclaré par :
<!ELEMENT annexe section >
<!ELEMENT para (simple | list | titré) >
Le langage S, qui permet de définir les structures génériques de Thot, permet d'exprimer un intervalle donnant les cardinalités maximale et minimale d'un élément de type liste. Dans une DTD XML, un élément dont le constructeur de type est liste est défini de la façon suivante :
<!ELEMENT list (item)+ >
<!ELEMENT description (nom, adresse, (tel)?) >
Le langage S permet de définir des agrégats ordonnés et non ordonnés. Un agrégat non ordonné ne définit pas l'ordre dans lequel apparaissent les éléments fils.
Ce constructeur n'existe pas dans la norme XML mais il peut être replacé par une liste d'élément dont le constructeur est le choix. La sémantique des ces constructeur n'est cependant pas la même : un fils d'un agrégat ne peut être représenté qu'une seule fois dans la structure du document, tandis qu'un type défini dans une liste de choix peut avoir plusieurs occurrences.
Le rôle des constructeurs dans le système de types de documents permet de faire le parallèle avec les types de données. Le constructeur liste s'apparente au constructeur tableau (une séquence d'éléments du même type), l'agrégat s'apparente au type structure du langage C, et le constructeur choix à l'union.
Dans le système de types que nous proposons pour les documents
structurés, nous notons l'ensemble des constructeurs de type
C. Ces constructeurs sont : C =
{Choix, Liste, Agrégat et
Identité}.
Chaque structure générique de document, décrite par une DTD, peut être décrite par une expression de type. Les types définis par la DTD sont nommés et peuvent être circulaires. Comme les expressions de type des langages de programmation, les structures génériques des documents structurés peuvent être représentées sous forme de graphes de types orientés. La figure 28 montre un exemple de fragment de DTD et le graphe de types associé. Dans le graphe, les noms des types d'éléments sont présentés en caractères italiques, les constructeurs et les types de base sont indiqués en caractères romains.
<!ELEMENT répertoire (entrée)+ > <!ELEMENT entrée (nom, (ref_entrée | description) > <!ELEMENT description (adr_perso, tel, adr_prof, tel) > <!ELEMENT adr_perso (adresse) > <!ELEMENT adr_prof (adresse) > <!ELEMENT nom (#PCDATA) > <!ELEMENT adresse (#PCDATA) > <!ELEMENT tel (#PCDATA) > <!ELEMENT ref_entrée EMPTY > <!ATTLIST ref_entrée referred CDATA >[Here is a Drawing]
Figure 28 - DTD de la classe de documents Répertoire et graphe de types associé
La représentation de graphe n'est pas une structure de données adaptée à la comparaison. En effet, la recherche de relations autres que l'équivalence entre graphes est un problème difficile. Aussi allons nous définir une structure d'arbre adaptée aux algorithmes de comparaison que nous proposons dans le chapitre suivant.
Une structure générique S définit un ensemble de types TS de façon récursive à l'aide des règles de constructions suivantes :
Un arbre de types canonique [Akpotsui 93] est un développement du graphe de type. Ce graphe est exploré depuis le type qui doit être représenté et chaque noeud rencontré au cours de ce parcours provoque la création d'un noeud dans l'arbre canonique. Ainsi la figure 29 présente-t-elle l'arbre canonique du type description de l'exemple présenté ci-dessus. Dans cette représentation, les noeuds adresse et tel ont été répliqués pour obtenir une arborescence.
[Here is a Drawing]Figure 29 - Arbre canonique du type description
Une DTD peut définir des types d'éléments de façon récursive. Dans ce cas, le graphe de types comporte des cycles et il n'est pas possible de créer un arbre de type. Nous définissons un pseudo-type de base, appelé récurrence, qui est associé aux types qui ont une définition récurrente. Ainsi, nous pouvons représenter tout graphe de type sous forme d'arbre canonique. L'algorithme de comparaison présenté dans le chapitre suivant prend en compte les noeuds définis récursivement en effectuant un traitement particulier des noeuds terminaux du type récurrence.
Ces définitions étant posées nous allons nous intéresser à une relation portant sur les arbres de types servant de base à un système de transformation de document permettant la réalisation de classes de transformation que nous avons identifiées au chapitre 2.
La section 4.1 a montré les spécificités des systèmes de types des documents structurés. Il en ressort que la notion d'équivalence diffère entre types de données et types d'éléments.
Pour la transformation de structures, les applications documentaires requièrent une relation entre types moins stricte que la relation d'équivalence utilisée par les compilateurs des langages de programmation. Par conséquent, nous définissons une relation de transformabilité entre types permettant de réaliser les deux principales classes de transformations que nous avons identifiées au chapitre 2 : les structurations et les réductions. Cette relation met en correspondance les noeuds de l'arbre des types des éléments source avec un arbre de type donné.
La première classe de transformations que nous considérons est celle des structurations. Une structuration est une transformation qui nécessite la création d'éléments de structure intermédiaires. Par exemple, la transformation d'un élément de type abonné, défini par la DTD annuaire donnée dans la figure 30, en un élément de type entrée défini dans la DTD répertoire nécessite la création de l'élément contenu qui n'a pas d'équivalent dans la structure annuaire au sens de l'équivalence défini par l'algorithme d'unification.
<!ELEMENT annuaire
(département)* >
<!ELEMENT département
(commune)* >
<!ELEMENT commune (abonné)* >
<!ELEMENT abonné
|
<!ELEMENT répertoire (entrée)*> <!ELEMENT entrée (nom,contenu)> <!ELEMENT contenu (adr,tel)> <!ELEMENT nom (#PCDATA) > <!ELEMENT adr (#PCDATA) > <!ELEMENT tel (#PCDATA) > |
|
Classe annuaire |
Classe répertoire |
Figure 30 - DTD et graphes de types des classes de documents
répertoire et annuaire
L'équivalence entre les arbres de types abonné et entrée n'est pas établie par l'algorithme d'unification à cause de la présence du noeud contenu. Cependant il est possible de transformer un élément du type annuaire en répertoire. Pour cela nous définissons une relation anti-symétrique d'un arbre de type dans un autre appelée relation de massif. Cette relation injective met en correspondance chaque noeud de l'arbre de types source avec un noeud de l'arbre de types destination ayant le même constructeur, en préservant les relations structurales de parenté et d'ordre entre les noeuds.
Sous-forêt : un ensemble de noeuds {t1, ..., tn} est une sous-forêt d'un noeud t si et seulement si :
Dans la figure 31, l'ensemble {t1.1, t1.2, t2, t3.2, t4} est une sous-forêt du noeud t.
Figure 31 - Sous-forêt d'un arbre de types
Massif : un ensemble de noeuds {t1, ..., tn} est un massif d'un noeud t si et seulement si " i Î [1, n], ti est un descendant de t.
Dans la figure 32, l'ensemble {t, t1.1, t1.2, t2 , t3, t3.1.1, t3.1.3, t3.2} est un massif du noeud t.
Figure 32 - Massif d'un arbre de types
Relation de massif : Une relation de massif entre un arbre de type t et un arbre de type t' est une relation injective M de t dans t' telle que le massif image de t par M préserve les constructeurs et les relations hiérarchiques des noeuds de t. M est formellement de définie par :
Dans la figure 33, une relation de massif associe les noeuds de l'arbre de types t et un massif de l'arbre de types t', présenté en rouge.
Figure 33 - Relation de massif entre arbre de types
La relation de massif a la propriété de conserver les relations hiérarchiques entre éléments : si un noeud ti est un descendant de t dans l'arbre de types source, le noeud M(ti) est un descendant du noeud M(t) dans l'arbre de types cible.
S'il existe une relation de massif entre un arbre de types U et un arbre de types V nous noterons U Í V.
Les réductions sont les transformations inverses des structurations : ces transformations induisent l'élimination d'éléments de structure car un ensemble de noeuds de l'arbre de type source n'ont pas de correspondance dans l'arbre de types cible. Un exemple de réduction est la transformation inverse de la précédente qui permet de transformer une instance d'annuaire dans le type répertoire. Cette différence implique que les arbres de types source et cible ne peuvent pas être mis en correspondance par l'algorithme d'unification ni par une relation de massif.
Nous définissons une nouvelle relation entre un arbre de types source et un arbre de type cible représentant une structure réduite : la relation d'absorption.
Noeud absorbable : un noeud t d'un arbre de types est absorbable si et seulement si il est défini par un constructeur c et son noeud parent est défini par le même constructeur.
Dans l'exemple de la figure 30, le noeud contenu est absorbable car son constructeur est agrégat et le constructeur de son père (entrée) est également agrégat.
Équivalence à un noeud près : Nous définissons l'équivalence à un noeud près comme une approximation de l'équivalence calculée par l'algorithme d'unification, en ignorant un noeud dans l'arbre source et un noeud ayant la même position dans l'image par la relation d'équivalence E.
Deux arbres de types t et t' sont équivalents à t0, t'0 près si et seulement si :
Relation d'absorption : il existe une relation d'absorption N entre deux arbres de types t et t' si et seulement si il existe un noeud ta = c (t1,¼, tn) appartenant à la descendance de t et un noeud t'a = c (t'1,¼, t'm) descendant de t' tels que :
Un type peut être absorbé si l'image de son parent peut contenir les images de ses fils. Ainsi dans l'exemple, le type abonné est en relation avec le type entrée par absorption du type contenu : les constructeurs des ces trois types sont des agrégats et les fils du type contenu sont équivalents aux types adresse et tel.
Figure 34 - Relation d'absorption entre les types abonné et entrée
La relation d'absorption a les mêmes propriétés que la relation de massif : elle conserve l'ensemble des types de base de l'arbre de types source, car par définition, seuls des noeuds intermédiaires d'un arbre de types peuvent avoir un constructeur similaire à celui de leur parent. Les noeuds feuille sont des types de base. Les relations hiérarchiques entre les noeuds de l'arbre sont également conservées.
La relation d'absorption ne permet pas d'effectuer l'ensemble des réductions possibles d'un type d'élément. Certaines transformations sont fondées sur des relations qui suppriment des éléments dont le type n'est pas absorbable ; c'est en particulier le cas lorsqu'une alternative d'un type choix n'est représenté ni dans la DTD cible, ni dans la structure du document source. Pour prendre en compte ces transformations, nous proposons dans le chapitre suivant une extension de la notion d'absorption qui consiste à éliminer de l'arbre de types source les noeuds qui ne sont pas instanciés dans la structure du document source (voir chapitre 5, section 5.4.3).
Les transformations les plus courantes ne sont généralement pas de simples réduction ou structurations, mais une combinaison de ces relations. Pour cette raison, nous définissons la relation de transformabilité, qui est une combinaison de relations d'absorption et d'une relation de massif.
Relation de transformabilité : soit t et t' deux arbre de types, il existe une relation de transformabilité entre t et t' si seulement si il existe un ensemble d'arbres de types t0, ..., tn tel que :
Par composition des relations, les noeuds terminaux de l'arbre de type source sont conservés par la relation de transformabilité. De même, les images conservent la hiérarchie des noeuds de l'arbre source.
La figure 35 montre la composition de relations d'absorption et de massif qui mettent en relation les arbres de types des structures génériques annuaire et répertoire.Les deux absorptions permettent de supprimer les noeuds commune (1) et département (2) qui ne peuvent pas être représentés dans la structure répertoire. Une relation de massif (3) met en correspondances le noeud de l'arbre de type image de ces deux absorptions avec les noeuds de l'arbre de types répertoire.
<!ELEMENT annuaire (départ)* > <!ELEMENT départ (commune)*> <!ELEMENT commune (abonné)* > <!ELEMENT abonné |
<!ELEMENT répertoire (entrée)*> <!ELEMENT entrée (nom,contenu)> <!ELEMENT contenu (adr,tel)> <!ELEMENT nom (#PCDATA) > <!ELEMENT adr (#PCDATA) > <!ELEMENT tel (#PCDATA) > |
Figure 35 - Composition de relations d'absorption et de massif pour la transformation d'annuaire en répertoire
Dans le chapitre suivant nous proposons un algorithme de recherche de ces relations appliqué aux structures génériques de documents.
Quelques systèmes de transformation s'appuient sur les définitions génériques des types pour spécifier les transformations en terme de schémas de traduction entre grammaires. Comme dans les systèmes présentés dans le chapitre précédent, ces systèmes peuvent utiliser une approche dirigée par la source ou implémenter une sémantique de transformation qui leur est propre (contraintes, actions explicites).
[Hirvonnen 95] présente des études de cas de transformations élémentaires incluant la création, la suppression, le renommage des éléments. Ces études de cas mènent à la définition de relations élémentaires de transformation : l'extension (ajout d'éléments), la surpression, le renommage, l'application d'un ordre sur les éléments, le recherche d'éléments spécifiques et l'adoption d'éléments par un nouvel élément père.
Un langage de transformation explicite permettant de combiner ces transformations élémentaires est proposé. Ce langage implémente une méthode de transformation dirigée par la source et une génération linéaire. Pour ordonner les éléments un système de buffers est utilisé.
Les relations de transformations proposées dans [Hirvonnen 95] portent une sémantique plus importante que les relations de facteur et de massif qui se situent au niveau syntaxique dans l'expression des structures. Un algorithme de recherche automatique de similarités de structures dans le but de transformation ne peut avoir la connaissance de la sémantique nécessaire pour l'identification de ces relations. La sélection sémantique est opérée par le langage de transformation. L'approche que nous proposons dans ce travail est différente : nous nous basons sur des similarités syntaxiques (au sens des systèmes de types) représentées par les relations de massif et d'absorption, la sémantique étant introduite dans une phase de désambiguisation du résultat (voir chapitre 6).
[Akpotsui 97] propose un modèle fonctionnel pour représenter les types d'éléments et formalise la notion d'adoption d'éléments. Ce modèle se fonde sur une relation d'isomorphisme dont nous avons montré les limites dans la section 4.3.
Dans [Furuta 88b], le problème de la relation entre opérations élémentaires de transformation et conformité du documents à sa structure générique est adressé. Les auteurs posent les fondements d'un langage de transformation basé sur des opérateurs de modification des règles de production des grammaires définissant les structures génériques.
Le système SIMON [Feng 93] définit des schémas, nommés Higher-order Attribute Grammar (HAG) qui sont des extensions des grammaires attribuées. Les HAG spécifient à la fois des traductions dirigées par la source et des actions sémantiques incluses dans les parties droites des règles de la grammaire attribuée.
La transformation est effectuée en trois phases (figure 36) :
[Here is a Drawing]
Figure 36 - Transformation de structure basée sur les HAG
SYNDOC [Kuikka 93] permet des transformations par l'intermédiaire de grammaires à clauses définies (Definite Clause Grammar ou DCG) qui sont également une généralisation des grammaires hors-contexte, mais qui sont exécutables car elles sont une variante rationnelle d'une classe de programmes Prolog.
Ces systèmes sont proches de ceux étudiés dans le chapitre précédent car ils se fondent sur une déclaration explicite des transformations. Nous avons choisi de faire figurer ces systèmes dans cette partie car les expressions de transformation ne s'appuient pas sur les structures d'éléments mais sur les structures génériques définissant les documents.
La principale critique que l'on peut faire à ces systèmes est qu'ils réclament une connaissance experte des structures des documents manipulés et de leur représentation sous forme de grammaire. D'autre part, bien que ces systèmes permettent une spécification des transformations au niveau des structures génériques, la spécification d'un nombre important de transformations est nécessaire dès lors que de multiples classes de documents sont impliquées.
Dans ce chapitre nous avons défini la notion de type au sens des langages de programmation (types de données) et dans les documents structurés (types d'éléments.
Les méthodes de conversion de variables entre types de données (coercition) et de typage des données s'appuient sur une notion d'équivalence calculée par l'algorithme d'unification qui est présenté dans l'annexe A.
Une comparaison des systèmes types de données et des types d'éléments de document a permis d'identifier les spécificités de ces derniers. Ces spécificités se situent au niveau de la définition d'un type :
et au niveau de l'utilisation des données typées que font les applications comme :
Ces différences entre ces systèmes de types font que l'équivalence telle qu'elle est définie pour la vérification et l'interprétation de programmes est une notion trop stricte pour être appliquée à la transformation de documents.
Des éléments de structure pouvant être créés ou disparaître au cours de la transformation, nous avons besoin d'une relation mettant en correspondance des types ayant des structures différentes. Nous proposons une relation entre types qui prend en compte ces différences.
Les relations antisymétriques de massif et d'absorption permettent d'associer un type source avec un type cible dont les structures diffèrent par le nombre de noeuds. Cependant des similitudes persistent entre les types ayant de telles relations :
Ces propriétés impliquent qu'un système de transformation basé sur ces relations conserve l'ordre des éléments dans le document et garantisse que l'intégralité du contenu des éléments source soient conservés.
Dans le chapitre suivant, nous définissons un processus de transformation de documents structurés basé sur la comparaison des structures génériques et la recherche de relations de massif et d'absorption.