2.3. Notion de projection inverse ou d'expansion des
répliques partielles
Lorsque vient le moment de la synchronisation, il faut
fusionner les différentes mises à jour des différents
co-auteurs; ceci dans le but d'obtenir un document global conforme
2.3. Expansion des répliques partielles 28
Mémoire - ZEKENG NDADJI Milliam Maxime
LIFA
à la grammaire globale. Sachant que les documents
à fusionner (répliques partielles mises à jour) ne sont
pas forcément conformes à de la grammaire globale6 ;
il faut au préalable, trouver des documents conformes au modèle
global et pour lesquels ces répliques partielles sont des projections.
La recherche de ces documents, connue comme étant le problème de
la projection inverse ou expansion, est l'objet de cette
section.
2.3.1. Le problème de la projection inverse
La projection inverse ou expansion d'une
réplique partielle mise à jour tma
'
Vi relativement
{ }
à une grammaire G = (S,P,A) donnée, c'est
l'ensemble Tma ' tma '
iS = iS ? G | ðVi(tma
'
iS ) = tma '
Vi
des documents conformes à G qui admettent
tma '
Vi comme réplique partielle suivant la vue
Vi. Ces documents peuvent être en nombre
infini; en effet si nous considérons la réplique partielle mise
à jour tma '
v1 obtenue en éditant sur le site 1 la
réplique partielle tv1 (tv1 étant obtenue par
projection du document t - conforme à la grammaire Gexpl
- suivant la vue V1 = {A,B}) (figure 2.5), on peut
trouver un nombre illimité de documents tma ' iS
qui sont ses projections inverses (il suffit d'itérer sur la
production C ? C C) comme l'illustre la figure 2.6.
FIGURE 2.6 - Exemple de projections inverses d'une
réplique partielle.
Le calcul des expansions des répliques partielles mises
à jour est primordial étant donné que ce sont les
documents de ces expansions qui seront fusionnés pour déterminer
les documents globaux intégrant toutes les mises à jour (dans le
cas où il n'y a pas de conflits) des différents co-auteurs.
L'expansion d'un document pouvant être infinie, il est souhaitable de ne
pas chercher à calculer tous les documents qui la constituent. Par
ailleurs, même si ces ensembles étaient finis, ce serait
très coûteux de les générer vu que ce n'est qu'une
infime proportion des documents qu'ils contiennent qui sera retenue à
l'issue de la fusion. L'idée proposée dans [BTT08, BTT07, TT09]
est donc d'implémenter les algorithmes d'expansion associés
à chaque vue sous la forme de co-routines qui construisent
6. Pour rappel, les répliques partielles ne sont pas
forcément conformes au modèle grammatical global mais
plutôt à des modèles grammaticaux locaux. Les
modèles locaux peuvent être obtenus en récrivant les
productions du modèle global; une solution (ne s'appliquant qu'à
une certaine classe de grammaire) basée sur ce raisonnement a
été proposé dans [TTTAD14].
2.3. Expansion des répliques partielles 29
Mémoire - ZEKENG NDADJI Milliam Maxime
LIFA
de façon paresseuse7 une
représentation de leur espace de solution respectif; et par la suite, de
faire collaborer ces co-routines pour générer les documents
globaux recherchés. De ce fait, l'expansion d'une réplique
partielle sera représentée par un automate d'arbre qui sera
utilisé pour la génération de ses instances (les documents
de l'expansion).
| 
