Memoire Online - Réconciliation par consensus des mises à jour des répliques partielles d'un document structuré.

Pour des besoins de sérialisation, un arbre peut être linéarisé sous la forme d'un mot de Dyck à n lettres où n est la taille de l'alphabet étiquetant les noeuds de l'arbre. Le langage de Dyck à n lettres (Ó_n= {(i,)i | 1 i n}) c'est-à-dire le langage des parenthèses bien formées sur n lettres, est donné par la grammaire

Un mot premier de Dyck code un arbre et un mot de Dyck une suite d'arbres, c'est à dire une forêt. On associe une paire de parenthèses à chaque symbole grammatical puis on effectue un parcours en profondeur de l'arbre à sérialiser comme illustré sur la figure 2.7 avec la réplique partielle mise à jour _tma j

v1 ) : on a associé les symboles de Dyck '(1' et ')1' (resp. '(2' et ')2') au symbole grammatical A (resp. B).

On peut restreindre l'association des paires de parenthèses à un sous-ensemble de symboles grammaticaux (une vue - V par exemple -). La linéarisation des documents sera partielle et ne représentera que les symboles visibles (ceux auxquels on a adjoint une paire de parenthèse) dans le document : on parlera de la trace visible du document en question. Ceci induit que des documents (t1 et t2 par exemple) différents peuvent avoir la même trace visible (t). Dans ce cas, leur trace visible commune n'est rien d'autre que la linéarisation de leurs projections suivant la vue considérée. On en déduit de ce fait que les documents (t1 et t2) en question appartiennent à une même expansion (celle de t).

7. L'évaluation paresseuse ou évaluation par nécessité est une forme d'évaluation dans laquelle les éléments sont calculés uniquement quand leurs résultats sont nécessaires. Contrairement à l'évaluation immédiate, cette technique permet de réaliser des constructions à l'origine impossibles; comme la définition d'une suite infinie...[Has, HPHF99, GHC]

2.3.3. Représentation de l'expansion d'une réplique partielle et

exemple

L'algorithme d'expansion va consister à associer un automate d'arbre à une vue. Cet automate permet à la fois de reconnaître tous les documents de l'expansion mais on peut aussi l'utiliser pour générer (de façon paresseuse) ces documents.

Comme pour la conformité, l'automate de l'expansion sera construit à partir de la grammaire globale G. Cependant, la seule propriété connue des documents de l'expansion que cet automate devra générer est qu'ils ont tous la même trace visible t (la réplique partielle). C'est pourquoi, l'état initial de cet automate sera construit à partir de cette trace visible.

Dans cet exemple, nous construisons un automate d'arbre 91 permettant de reconnaître et/ou de générer tous les documents (conformes à Gexpl) qui sont des expansions de la réplique partielle mise à jour _tma '

v1 ; nous construisons donc 91 à partir de v = {A,B} avec pour état initial l'arbre _tma '

v1 . Nous représentons des listes d'arbres (forêts) par leurs linéa-risations. Dans l'écriture de ces linéarisations, nous utilisons la parenthèse ouvrante '(' et fermante ')' pour représenter les symboles de Dyck associés au symbole visible A et le crochet ouvrant '[' et fermant ']' pour représenter les symboles de Dyck associés au symbole visible B. Chaque transition des automates associés aux répliques partielles suivant la vue {A,B} est conforme à l'un des schémas de transition suivants :

(A,w2) -> (P2,[]) si w2 = å
(B,w3) -> (P3,[(C,u),(A,v)]) si w3 = u(v) (B,w4) -> (P4,[(B,u),(B,v)]) si w4 = [u][v] (C,w5) -> (P5,[(A,u),(C,v)]) si w5 = (u)v (C,w6) -> (P6,[(C,u),(C,v)]) si w6 = uv

Ces schémas de règles sont obtenus à partir des productions de la grammaire et les couples (X,wi) sont des états dans lesquels X est un symbole grammatical et le motif wi est une forêt codée dans le langage de Dyck. Le premier schéma par exemple, stipule que les AST générés à partir de l'état (A,w1) sont ceux obtenus en utilisant la production P1 pour créer un arbre de la forme P1[t1,t2] ; t1 et t2 étant générés respectivement à partir des états (C,u) et (B,v) tel que w1 = u[v]. Dans une telle décomposition (w1 = u[v]), on peut déterminer u et v à partir de w1 par pattern matching (filtrage par motif) facilement et sans ambiguïté : on dit dans ce cas que le motif w1 est déterministe. Les schémas de transition dont les motifs sont non déterministes (le sixième schéma par exemple - w6 = uv -) sont en général responsables de la présence d'une infinité de documents admettant la même trace visible.

Ayant associé les symboles de Dyck '(' et ')' (resp. '[' et ']') au symbole grammatical A (resp. B), la linéarisation de la réplique partielle mise à jour _tma '

v1 donne ((()[()])[()])
(figure 2.7). A étant l'axiome de la grammaire et aussi un symbole visible (appartenant à la vue), l'état initial de l'automate .91 est q0 = (A,(()[()])[()]). En ne considérant que les états accessibles à partir de q0 et en appliquant les schémas de règles présentés précédemment, nous obtenons l'automate d'arbre suivant pour la réplique _tma '

q0	->	(P1,[q1,q2])		avec	q1 = (C,(()[()])) et q2 = (B,())
q1	->	(P5,[q3,q4])		avec	q3 = (A,()[()]) et q4 = (C,å)
q1	->	(P6,[q4,q1]) \|	(P6,[q1,q4])
q2	->	(P3,[q4,q5])		avec	q5 = (A,å)
q3	->	(P1,[q6,q2])		avec	q6 = (C,())
q4	->	(P6,[q4,q4]) \|	(P7,[])
q5	->	(P2,[])
q6	->	(P5,[q5,q4])
q6	->	(P6,[q4,q6]) \|	(P6,[q6,q4])

Il est aisé de vérifier que l'automate présenté ci-dessus, accepte les arbres de la figure

Réconciliation par consensus des mises à jour des répliques partielles d'un document structuré.

2.3.2. Sérialisation d'un document structuré

2.3.3. Représentation de l'expansion d'une réplique partielle et

exemple