Completamento Compilazione ed Esecuzione Query in XPeer

Donato Ferrante e Michele Freschi

Facoltà Di Scienze Matematiche Fisiche e NaturaliCorso di Laurea in Informatica

Tutore Accademico: prof. Giorgio Ghelli

• Database XML Distribuito;

• Pensato per il Resource Discovery;

• Basato su un infrastruttura Peer-To-Peer;

• In grado di autoamministrarsi;

• Compilazione ed Esecuzione in fasi distinte.

Cos’è XPeer

root

superpeervirtuali

peer

interrogazione

risultato

Sistema

•Ad ogni peer è associato uno schema

•Ad ogni SuperPeer è associato un super-schema

SP 1 SP n

SuperPeer Virtuale

SuperPeer

SuperPeer Virtuale

• È un insieme di superpeer con stato condiviso

Cloning

SPV1 è sovraccarico…

SPV 1

SP1

SPV1 aumenta la propria cardinalità

SPV 1

SP1 SP2

Cloning

P1 P2 P7

SPV 1

SP1

SPV 1 ha costi disincronizzazione

elevati

SP8

Splitting

• SPV1 dimezza la propria cardinalità• I figli di SPV1 vengono ridistribuiti

P5 P7

SPV 1a

SP1

P1 P9

SPV 1b

SP4 SP5 SP8

Splitting

SPV3

Px

root

SPV1

Py

SPV5 SPV6

SPV2

invoker

{ Px }

SPV4

(TTSIQ=4)

(TTSIQ=3)

(TTSIQ=2)

(TTSIQ=2)

(TTSIQ=1)

MetaSearchRicerca di risorse nella rete.

P1 P2 P4 P5

SPV3SPV2

P3

root

Sc_1 Sc_2 Sc_3 Sc_4 Sc_5

Sc_v2 =union {Sc_2, Sc_3}

Sc_v3 =union {Sc_4, Sc_5}

Sc_v1 = {Sc_1}

Sc_root =union {Sc_v1, Sc_v2, Sc_v3}

Px

Sc_x

SPV1

Gestisce la corretta sincronizzazione dello stato del sistema.

Sc_v1 = union {Sc_x, Sc_1}

Sc_root =union {Sc_v1, Sc_v2, Sc_v3}

MetaUpdate (SchemaUpdate)

• Fase di Compilazione• innescata da un Peer (invoker);• identifica i Peer con dati “interessanti”.

• Fase di Esecuzione• i peer individuati vengono coordinati dall’invoker

per l’esecuzione dell’interrogazione.

Compilazione ed Esecuzione

Tree-guide

• Albero di nodi etichettati• Inferito dai documento XML• Descrive in modo sintetico il documento XML:

• Rappresenta tutte le possibili navigazioni • Valori contenuti (Filtri di Bloom, Liste di valori)

<cdl> <corso> <docente>Giorgio Ghelli</docente> <sigla>BDL</sigla> <cfu>6</cfu> </corso> <corso> <docente>Marco Vanneschi</docente> <sigla>ASE</sigla> <cfu>9</cfu> </corso></cdl>

• Il tree-guide viene confrontato con l’interrogazione• Per sapere se l’esecuzione sul corrispettivo documento

XML produrrebbe qualche risultato

• L’algoritmo di confronto prende il nome di schema-match • verifica compatibilità di uno schema con una

interrogazione• compatibile: l’esecuzione reale potrebbe produrre qualche

risultato• non compatibile: se l’esecuzione reale non produrrebbe

alcun risultato

Query e Tree-guide

p1 p2

root

SPV1

p3 p5 p7 p8

SPV3SPV2

p6

Compilazione: un esempio

Peer interessanti:{p2}Peer interessanti:{p2, p3, p5}

Esecuzione• Decomposizione dell’interrogazione in sotto-interrogazioni (“pipe”)• Le sotto-interrogazioni sono spedite ai rispettivi peer remoti

– Ogni peer remoto ottimizza ed esegue la sotto-interrogazione– Il peer che ha inoltrato l’interrogazione riceve i risultati

Path

Sigma

Path

Sigma

Union

Return

pipe-2pipe-1

p1

SPV SPV

Conclusioni e Risultati Sperimentali

• Risultati relativi alla precisione delle interrogazioni in relazione alla dimensione dei filtri di bloom

• Buona parte del lavoro di tirocinio è consistito nell’integrazione del treeguide e nel testing e misurazione di tutta la fase di compilazione

• Prof. Giorgio Ghelli

• Dott. Carlo Sartiani

Ringraziamenti