La struttura dei dati che sta alla base degli structural join `e stata introdotta in [16] dove si `e visto che suddividendo documenti XML in nodi rappresentanti elementi veri e propri (ELEMENT) e nodi rappresentanti testo semplice (TEXT) `e possibile frammentare il documento senza perderne la struttura.
28 3. Gli structural join I nodi ELEMENT hanno la struttura: ELEMENT (docId,startPos,endPos, level).
I nodi TEXT sono un po’ pi`u semplici: TEXT (docId, startPos, level). Il campo docId indica l’identificativo del documento XML, qualcosa che lo faccia distinguere dagli altri. I campi startPos ed endPos sono il risultato della numerazione progressiva dei tag di apertura e di chiusura di ogni elemento e l’inizio di ogni elemento di testo. Il campo level indica la profondit`a dell’inne-stamento: l’elemento root avr`a sempre il valore di level minore in quanto (ci`o `e imposto dalla sintassi XML) contiene tutti gli altri elementi e non `e contenuto in nessun altro. Nella figura 3.1 si pu`o vedere come potremmo numerare i tag del nostro documento di esempio. Abbiamo aggiunto il campo “type” a entrambe le strutture per memorizzare il nome del tag.
Figura 3.1: La numerazione degli elementi
La tabella 3.1 rappresenta gli elementi ELEMENT, mentre la tabella 3.2 rappresenta gli elementi TEXT provenienti dal documento di esempio.
Grazie a questa strutturazione `e possibile memorizzare frammenti di docu-menti XML in semplici tabelle. Tali tabelle potrebbero essere ad esempio quelle di un comune database relazionale .
3.1 Struttura dei dati ed algoritmi per gli structural join 29 type docId startPos endPos level
legge 1 1 13 1
articolo 1 2 12 2
comma 1 3 5 3
comma 1 6 8 3
comma 1 9 11 3
Tabella 3.1: Tabella degli elementi ELEMENT type docId startPos level
text 1 4 4
text 1 7 4
text 1 10 4
Tabella 3.2: Tabella degli elementi TEXT
E’ stato poi possibile riscrivere le pi`u importanti relazioni presenti in XPath ed XQuery alla luce di questo nuovo approccio. Le relazioni sono:
• ancestor-descendant • parent-child
• sibling
Siano A e B due nodi, possiamo dire che :
A `e ancestor di B (o B `e descendant di A) se e solo se
(A.startPos < B.startPos) AND (B.endPos < A.endPos)
A `e parent di B (o B `e child di A) se e solo se
(A.startPos < B.startPos) AND (B.endPos < A.endPos) AND ( (A.level +1) = B.level)
30 3. Gli structural join A `e sibling di B , e precede B (o B `e sibling di A , e segue B)
se e solo se
(A.endPos < B.startPoS) AND ( A.level = B.level ) AND (hanno lo stesso parent).
3.2 Algoritmi in letteratura
L’articolo [1] introduce le strutture dati precedentemente enunciate (introdotte in [16]), conia il termine “structural join” e ne presenta interessanti algoritmi per l’elaborazione. L’algoritmo pi`u interessante proposto nell’articolo [1] `e sicu-ramente stack-tree-desc, basato sull’utilizzo di uno stack. Tale algoritmo elabora set di dati di tipo ELEMENT e TEXT ordinati secondo (docId, startPos) partendo da query complesse e strutturate.
Da ora in poi parleremo sempre di relazioni di tipo ancestor-descendant, quelle di tipo parent-child sono considerate identiche tranne che per un semplice controllo sul campo level.
Ipotizziamo di avere la query a//b//c .
Questa query complessa viene suddivisa in un insieme di semplici relazioni strutturali binarie di tipo ancestor-descendant. Facendo questo la query di esem-pio viene suddivisa nelle relazioni binarie a//b e b//c. Gli step per risolvere la query complessiva sono:
1. trovare le corrispondenze di ognuna delle relazioni strutturali binarie nel proprio database
2. unire tutte le relazioni strutturali binarie verificatesi al punto precedente L’approccio di questo algoritmo sul set di dati `e detto set-at-a-time perch´e per ogni nodo ancestor identificato vengono individuati tutti i nodi descendant possibili in un unico ciclo. Approcci precedenti sono considerati perdenti rispetto a questo in quanto erano di tipo node-at-a-time, cio`e per ogni nodo si cercavano tutti i descendant, col problema che era necessario attraversare tutti i nodi del database molte volte.
3.2 Algoritmi in letteratura 31 L’algoritmo stack-tree-desc d`a buoni risultati, ma presenta il problema della dimensione dei risultati intermedi. I risultati intermedi sono quelli generati da ognuna delle relazioni binarie della query (cio`e da a//b e da b//c). La loro mole pu`o essere un problema, in quanto:
1. rappresentano solo una soluzione parziale alla query (non si sa se parte-ciperanno a quella globale), ma non si possono tralasciare se si vuole una soluzione globale
2. possono essere numerose, occupando cos`ı un cospicuo spazio in memoria centrale
Il numero dei risultati intermedi `e in ogni caso indipendente dal numero delle soluzioni globali delle query.
L’articolo [3] introduce per i join strutturali un punto di vista olistico. Olismo: teoria secondo cui un’entit`a `e un tutto superiore alla semplice somma delle parti che la costituiscono.
In tale articolo viene introdotto un algoritmo chiamato PathStack che con-tinua a basarsi sulle stesse strutture di base, ma introduce una serie di stack collegati atti a contenere risultati parziali.
Ipotizziamo di avere la query a//b//c (che potremmo chiamare anche path, percorso) in cui a, b e c sono elementi appartenenti alla tabella ELEMENT (ricordiamo che solo gli elementi foglia possono essere di tipo TEXT, e che le stesse funzioni sono applicabili sia alle strutture ELEMENT sia alle strutture TEXT).
La terminologia legata alla query `e del tipo: • a `e detto root della query
• b `e figlio del nodo a della query
• c `e figlio del nodo b della query ed `e anche un nodo foglia per la query L’algoritmo pi`u importante introdotto da [3] si chiama TwigStack, che ha un funzionamento basato sugli stack come PathStack, ma permette di fare query su
32 3. Gli structural join pi`u di un path. Una unione di pi`u di un path in una query viene detto un twig (letteralmente: rametto); l’importante `e che l’elemento root sia comune a tutti i path del twig.
Un esempio di twig pu`o essere l’unione di path aventi lo stesso elemento root (figura 3.2), ad esempio: • a // b // c • a // d // e
a
b
c
d
e
Figura 3.2: Esempio di twig
3.2.1 Funzionamento di TSGeneric
TSGeneric sta per TwigStack Generic, che `e l’algoritmo stack-based presentato in [10].
I documenti XML di interesse vengono sottoposti al parsing, e memoriz-zati in tabelle consone alle strutture ELEMENT e TEXT introdotte nel paragrafo 3.1. Ora `e possibile utilizzare l’algoritmo TSGeneric per risolvere una query sui dati memorizzati; tale algoritmo `e descritto in figura 3.3 con l’utilizzo di pseudocodice.
3.2 Algoritmi in letteratura 33
TSGeneric(root)
Figura 3.3: Algoritmo TSGeneric
Sia detta Q la query da risolvere, ad esempio a//b//c, e siano detti q i nodi della query. Associato ad ogni nodo della query avremo uno stack ed un cursore nel DB che chiameremo rispettivamente Sq e Cq.
All’interno di ogni iterazione data dal while viene generato un nodo della query (linea 2) che chiameremo nodo corrente.
L’elemento relativo al nodo corrente `e quello puntato dal cursore Cq, e lo chiameremo elemento corrente. Ad ogni iterazione tale elemento viene analizzato e posto negli stack (se verifica certe condizioni).
Le procedure utilizzate all’interno dell’algoritmo sono:
cleanStack(Sq, Cp) verifica che all’interno dello stack Sq ci siano solo ele-menti ancestor dell’elemento individuato da Cp; tutti gli elementi che non soddisfano questa condizione vengono eliminati
push(Sq, Cp, ptr) viene inserita sullo stack Sq una struttura che comprende Cp ed un puntatore ptr che indica l’elemento top dello stack padre
outputPathSolutionWithBloking(Cq) genera una soluzione completa di un path della query (dal nodo radice al nodo foglia)
34 3. Gli structural join