Presentiamo ora pi`u in dettaglio le espressioni di aggiornamento, il loro utilizzo, comportamento ed i vincoli su di esse.
3.4.1
Insert
La Sintassi dell’espressione:
Q ::= Insert Q′ (as first into | as last into | before | after) Q′′. Questa espressione `e divisa in realt`a in quattro espressioni che differi- scono solo per il punto di inserimento rispetto al target ed `e un’espressione di aggiornamento. L’espressione crea una copia degli alberi che partono dai nodi risultanti dalla valutazione di Q′
(che chiameremo contenuto), ed inse- risce questa copia nella posizione specificata rispetto al nodo risultante dalla valutazione di Q′′ (che chiameremo target).
$y ^ ^ ^ ^ ^ a < < < < < < < < $x ? ? ? ? ? b c d
Figura 3.4: Prima della valutazione della Insert
In figura 3.4 vediamo la struttura di un’ albero prima della valutazione del frammento d’esempio. Vediamo l’esempio:
let x:= a/c return ( for y in a/b return
( Insert $x as first into $y, $y ))
Il frammento copia il sottoalbero radicato in c come primo figlio di b e lo restituisce.
In figura 3.5 vediamo invece come la valutazione del frammento abbia cambiato l’albero. $y ^ ^ ^ ^ ^ a < < < < < < < < $x ? ? ? ? ? b c c ~~~~ ~~~~ d d
Figura 3.5: Dopo la valutazione della Insert
La semantica dell’espressione:
• valutato il target che pu`o essere una query qualsiasi, si verifica che il nodo che diventer`a il padre dei nodi da inserire sia di tipo element o document[7], si verifica che la sua cardinalit`a sia esattamente uno, se cos`ı non `e otteniamo un errore.
• viene valutato il contenuto che pu`o essere una query qualsiasi.
• si crea una copia del contenuto con la stessa struttura dei sottoalberi, e la si inserisce nella posizione specificata dalla clausola.
Chiaramente, se le espressioni di aggiornamento restituiscono liste vuote, ha poco senso inserirle come contenuto di una insert. Si consiglia inoltre di specificare il target di una insert come variabile di un ciclo for, come nell’esempio, questo per prevenire i problemi di cardinalit`a.
3.4.2
Delete
La Sintassi dell’espressione: Q ::= Delete Q
dove “Q” rappresenta la sequenza di nodi da cancellare che possono essere zero o pi`u.
Come gi`a accennato precedentemente, quando si cancella un sottoalbero si deve tener conto del fatto che, ad uno dei suoi nodi potrebbe essere sta- ta legata una variabile, e quindi come comportarsi se la si va ad accedere dopo una cancellazione? Questo problema `e ancor pi`u sentito se si utilizza una semantica con aggiornamento immediato. Nella soluzione sviluppata il sottoalbero non viene cancellato, ma solo staccato dal suo contesto e quindi non pi`u accessibile direttamente, ma tramite una variabile s`ı, come si `e visto nel paragrafo 2.4
Questa soluzione permette di evitare i cosiddetti “dangling reference”, riferimenti mancanti, quello che sarebbe successo se avessimo cancellato del tutto il sottoalbero.
In figura 3.6 vediamo la situazione dell’albero prima della valutazione del frammento d’esempio, i nodi e gli archi di un albero ed una variabile $x che punta al nodo c. L’espressione Delete a/c cancella il nodo, ma quando noi tentiamo di accedervi, questo `e ancora disponibile. Perch`e accedervi dopo? Anche solo per stamparlo.
a xxpppppp pppp pppp && N N N N N N N N N N N N N N $x ? ? ? ? ? c < < < < < < < < b c e f d
Figura 3.6: Prima della valutazione della Delete
let x:= a/c return (Delete $x,
$x)
Il frammento cancella i figli di a con tag c e li restituisce.
In figura 3.7 si vede come la Delete non abbia cancellato i sottoalberi, ma li abbia “staccati”, rendendoli di fatto inaccessibili, se non tramite variabili. In questo caso, il sottoalbero di sinistra non `e pi`u raggiungibile in quanto non vi erano variabili legate ad uno dei suoi nodi.
a $x ? ? ? ? ? c < < < < < < < < b c e f d
Figura 3.7: Dopo la valutazione della Delete
Chiarito questo punto, l’espressione Delete Q, valutata l’espressione Q che restituisce una lista di nodi, stacca questi nodi, rendendoli cos`ı inacces- sibili se non tramite variabili che li puntano.
La semantica dell’espressione:
• l’espressione Q che chiameremo target, pu`o essere una query qualsiasi, anche un’altra espressione di aggiornamento, purch`e non sia il risultato dell’espressione root, nel qual cas`o si ottiene un errore. In caso la lista dei nodi sia vuota, non accade niente e non `e considerato un errore; • se non ci sono errori, tutti i nodi vengono staccati dalla loro sede, e
l’espressione restituisce una lista vuota.
Chiaramente, se le espressioni di aggiornamento restituiscono liste vuote, ha poco senso inserirle come target di una delete.
3.4.3
Replace
La Sintassi dell’espressione: Q ::= Replace Q′
with Q′′
.
Questa espressione sostituisce un sottoalbero risultato della valutazione di Q′
(il target), con il risultato della valutazione di Q′′
.
In figura 3.8 vediamo la situazione dell’albero prima della valutazione del frammento di codice nell’esempio.
$y ^ ^ ^ ^ ^ a < < < < < < < < $x ? ? ? ? ? b c d
Figura 3.8: Prima della valutazione della Replace
let x:= a/c return (for y in a/b return Replace $y with $x)
Il frammento sostituisce i figli di a con tag b con i figli di a con tag c. In figura 3.9 possiamo vedere la l’albero dopo la valutazione della Replace.
$y _ _ _ _ a = = = = = = = = $x ? ? ? ? c ~~~~~~ ~~~~ c d d
Figura 3.9: Dopo la valutazione della Replace La semantica dell’espressione:
• valutato il target che pu`o essere una query qualsiasi, si verifica che la sua cardinalit`a sia esattamente uno, si verifica che il nodo che diventer`a il padre dei nodi da inserire sia di tipo element o document, se cos`ı non `e otteniamo un errore.
• si crea una copia del contenuto, con la stessa struttura dei sottoalberi, si “cancella” il nodo target e si inserisce la copia nella posizione del target.
Anche in questo caso ha poco senso inserire una query di aggiornamento come argomento di una replace, e si suggerisce l’utilizzo di un for per per specificare la variabile per il target.
3.4.4
Rename
La Sintassi dell’espressione: Q ::= Rename Q with l.
Questa semplice espressione, `e un’espressione di aggiornamento. Q `e il target, mentre l `e una stringa. l’espressione modifica il tag del target con la stringa l. Vediamo un esempio:
for x in a/b return Rename $x with ‘‘d’’
Il frammento seleziona i figli di a con tag b e li rinomina con un nuovo tag d.
La semantica dell’espressione:
• il target pu`o essere una query qualsiasi tranne la root, ma la sua cardinalit`a dev’essere esattamente uno.
• se non ci sono errori il tag del nodo viene modificato con la stringa data, e l’espressione restituisce una lista vuota.
`
E sempre una buona idea includere espressioni che necessitano di argomenti con cardinalit`a uno, come questa, all’interno di un ciclo for.
Capitolo 4
Implementazione
Il sistema realizzato fornisce una semplice interfaccia che si pu`o vedere in figura 4.1. L’area di input si trova in basso e consente di scrivere le queries. In alto troviamo una rappresentazione grafica del risultato della query che consente la visualizzazione di foreste di alberi XML. In basso alla finestra vediamo tre bottoni che consentono di avviare la valutazione della query, di annullarla o di visualizzare il log completo.
Sul log si possono visualizzare informazioni relative al parsing della query (espressioni riconosciute, errori di sintassi) ed alla valutazione della query (risultati, errori semantici), in base al livello di logging.
Il sistema non fornisce funzionalit`a circa il salvataggio o caricamento di file contenenti query, n´e lo consente per i dati caricati in memoria.
Nel capitolo precedente sono stati definiti a livello formale gli algoritmi e il modello dei dati. Tutto questo `e stato fatto mantenendo un approccio il pi`u possibile indipendente dall’effettiva implementazione. In questo capitolo verr`a approfondito proprio l’aspetto dell’implementazione.
L’implementazione `e una parte marginale della tesi, in quanto il sistema progettato non prevede alcune componenti fondamentali perch`e il linguaggio possa essere utilizzato. Il typechecking per esempio o la validazione pi`u in generale, non sono stati trattati durante la tesi, il sistema cio`e `e dotato di un cosiddetto processore XML non validante. Ci`o non toglie che il sistema, integrato di un modulo per la validazione, consenta un utilizzo completo del linguaggio. L’integrazione di un’implementazione di tale modulo nel codice richiederebbe poche semplici modifiche.
Per l’implementazione `e stato adottato come linguaggio di programma- zione Java versione 5.0 e librerie standard.
`
E stato scelto Java perch`e permette una discreta rapidit`a nella stesura di programmi di una certa complessit`a, un approccio semplice alle interfacce ed un’ottima integrazione con strumenti per il parsing di documenti XML. An-
Figura 4.1: L’interfaccia
che se, come vedremo in seguito, non sono stati utilizzati parser preesistenti, ma ne `e stato generato uno.
Il sistema contiene il package processor che gestisce le strutture dati, valuta le query che gli arrivano dall’interfaccia grafica, restituisce il risultato di queste e modifica il contenuto delle strutture dati.
Il sistema contiene l’interfaccia grafica nel package gui, questa consen- te di inserire delle query che invia al processor e visualizzarne i risultati. L’interfaccia consente inoltre di visualizzare il log.
Il sistema gestisce un log grazie alla libreria java.util.logging, questo consente l’invio di messaggi strutturati da processor a gui, a cui rinvia l’interfaccia grafica in caso di errori nelle query.
4.1
Il package “processor”
Il package processor contiene il motore di valutazione del linguaggio, nonch`e le strutture dati su cui questo agisce, si occupa del parsing del linguaggio ed
processor Evaluation Engine EvEngine.java Parser del linguaggio Parser.java
Scanner.java Parser XML XmlParser.java
XmlScanner.java Strutture Dati Core.java
Node.java Edge.java Age.java ListNode.java
Figura 4.2: Il package processor
esegue le operazioni sui dati, reperisce i dati richiesti ed effettua le modifiche su di essi. Si occupa inoltre del parsing dei documenti da caricare e della loro sistemazione in memoria. Esaminiamo le parti pi`u imporatnti del package: L’Evaluation Engine. La classe EvEngine.java si occupa della gestione
delle strutture dati, che contengono la rappresentazione della nostra memoria.
Questa classe `e il cuore del sistema: da il via al parsing sia dei do- cumenti che dell’input dall’interfaccia, e valuta le query, inviandone il risultato all’interfaccia e modificando il contenuto delle strutture dati in accordo con il risultato della valutazione.
L’evaluation engine contiene l’implementazione di tutti quegli operatori sullo store (store, che in questa fase del lavoro non `e pi`u astratto, ma `e diventatato un insieme di strutture dati) che abbiamo visto nel paragrafo 3.3.2.
Contiene inoltre molte altre funzioni che non abbiamo precedentemente esaminato, ma che assolvono ai compiti di interrogazione sui dati. Il codice di questa classe si pu`o consultare in appendice A.
Le strutture dati. Le classi Core.java, Node.java, Edge.java, Age.java e ListNode.java, sono l’implementazione di ci`o che nel capitolo 3 ab- biamo chiamato store o memoria, e di altre strutture dati, come le liste dei nodi che abbiamo utilizzato negli operatori su di esso.
La classe Core.java contiene proprio tutte quelle strutture dati per rappresentare la memoria del nostro modello dei dati, mentre No-
de.java, Edge.java e Age.java definiscono gli oggetti che verranno utilizzati in Core.java per rappresentare gli elementi della memoria. Come abbiamo visto dal paragrafo 3.3.2, i nostri operatori restitui- scono liste di nodi; la loro implementazione restituisce valori di tipo ListNode.
Il Parser del Linguaggio. Le classi Parser.java e Scanner.java sono sta- te generate automaticamente da Coco/R[14], un generatore di parser a discesa ricorsiva. Queste due classi, adeguate al progetto, sono state integrate e si occupano del parsing dell’input proveniente dall’interfac- cia e provvedono a chiamare le funzioni dell’evaluation engine, che far`a poi il resto.
Il Parser XML. Le classi XmlParser.java e XmlScanner.java sono sta- te anch’esse generate automaticamente da Coco/R, si occupano del parsing di documenti XML e chiamando l’evaluation engine del loro caricamento nelle strutture dati.
4.2
Il package “gui”
Il package gui contiene un’unica classe: MainFrame.java. L’interfaccia `e semplice, qualche casella di testo e pochi bottoni. Il suo compito `e quello di inviare l’input all’evaluation engine, attenderne i risultati e rappresentarli in finestra come una struttura ad albero. Contiene un’area di log dove e possibile verificare ogni passo dell’applicazione e capire gli errori commessi in fase di inserimento della query.
Capitolo 5
Conclusioni
In questa tesi sono stati affrontati due aspetti principali, la definizione for- male e l’implemantazione del linguaggio.
Il sistema implementato `e in grado di caricare documenti XML, eseguire su di essi query ed aggiornamenti.
Il lavoro `e iniziato con una fase di studio delle problematiche da affrontare e delle tecnologie esistenti.
XML `e oggetto di tutto il resto dello studio di tesi ed XQuery `e una tec- nologia dalla quale non si pu`o prescindere nella realizzazione di un linguaggio d’aggiornamento per XML. Oltre ad essere uno standard, XQuery `e stata la base di molte proposte di linguaggio d’aggiornamento, ed alla base di quel- la parte del linguaggio definito in questo lavoro di tesi, che si occupa delle interrogazioni.
L’analisi di alcune proposte per linguaggi di aggiornamento per XML, ha fortemente influenzato la definizione formale del linguaggio, soprattutto la sintassi, ma anche il modello dei dati e la definizione dei vincoli.
Al di l`a dello scopo di un linguaggio, il suo sviluppo richiede una precisa definizione formale. La definizione di un modello dei dati e la definizione di una semantica, sono state le parti pi`u impegantive della tesi.
Il sistema non `e completo, anche se `e totalmente funzionante ed utiliz- zabile quale prototipo. Il problema del controllo dei tipi sulle operazioni e della validazione dopo gli aggiornamenti non `e stato indagato nella defini- zione formale e non `e stato implementato. Realizzare ci`o avrebbe richiesto dei tempi non compatibili con una sola tesi, ma ci`o non escluede che questi possano essere eventuali sviluppi futuri.
Bibliografia
[1] Oreste Signore: Il ruolo centrale di XML nell’evoluzione del Web Ufficio italiano W3C
[2] Sito web decli XML Working Groups: http://www.w3.org/XML/
[3] Sito web dell’ XML Query Working Group: http://www.w3.org/XML/Query/
[4] Giorgio Ghelli, Cristopher R´e, J´erˆome Sim´eon: XQuery!: An XML query language with side effects
[5] Igor tatarinov, Zachary G. Ives, Alon Y. Halevy, Daniel S. Weld: Updating XML
ACM SIGMOD 2001.
[6] Gargi M Sur, Joachim Hammer, J´erˆome Sim´eon:
An XQuery-Based Language for Processing Updates in XML [7] Don Chamberlain, Daniela Florescu, Jonathan Robie:
XQuery Update Facility [8] James Cheney:
LUX: A lightweight, statically typed XML update language ACM 2006. [9] Li Liu, Menghi Liu, Guoren Wang:
XML-RL Update Language
[10] Don Chamberlain, Michael Carey,Daniela Florescu, Donald Kossman, Jonathan Robie:
XQueryP: Programming with XQuery XMIMEP 2006
[11] Sito web ufficiale su SAX: http://www.saxproject.org
[12] Document Object Model (DOM) Level 2 Core Specification : http://www.w3.org/TR/DOM-Level-2-Core/
W3C Recommendation 2000 [13] JDK 5.0 Documentation:
http://java.sun.com/j2se/1.5.0/docs/index.html [14] The Compiler Generator Coco/R:
Appendice A
EvEngine.java - Il codice
sorgente
La classe EVEngine `e altro il motore di valutazione del linguaggio. In essa troviamo tutti gli operatori del paragrafo 3.3.2.
Le funzioni utilizzano una struttura dati chiamata ListNode, che `e una lista di id di nodi. Per esempio, il risultato di una query `e una ListNode, ed il risultato di un aggiornamento `e una ListNode vuota. La classe contiene anche data di tipo Core, che rappresenta quelle strutture dati che abbiamo visto nel modello dei dati.
package processor; import java.io.File; import java.io.FileInputStream; import java.io.FileWriter; import java.io.IOException; import java.util.logging.Logger; /**
* @author Federico Mameli mameli@cli.di.unipi.it * Evaluation Engine
*/
public class EvEngine {
private File temp=null;
public Core data; // strutture dati
private static Logger logger = Logger.getLogger("Response");
/**
* Il costruttore crea le nuove strutture dati * e inizializza il file temporaneo che consente la * comunicazione con l’interfaccia.
*/ public EvEngine() { data=new Core(); try { temp = File.createTempFile("comunicate","dat"); temp.deleteOnExit();
} catch (IOException e1) { e1.printStackTrace(); }
}
/**
* @param d Lista degli alberi da cancellare. * @throws Exception
* Questa funnzione cancella gli alberi nella lista d
* rimuovendone i collegamenti con gli alberi che lo contenevano. */
public ListNode delete(ListNode d) throws Exception {
if (d!=null&&d.size()>0){
Integer n = (Integer) d.get(0); d.remove(0);
if(n==0){
logger.info("Impossibile cancellare la root"); throw new Exception("Errore, vedi log");
}else{ data.searchANDDestroyE(null,n,true); data.searchANDDestroyA(null,n,true); data.searchANDDestroyA(n,null,true); data.remIfRoot(n); delete(d);} }
return new ListNode(); }
/**
* @param old Lista di un elemento, l’albero da sostituire * @param sost Lista degli alberi da inserire
* @throws Exception
* Cancella l’albero nella lista old e gli sostituisce * quelli nella lista sost.
*/
public ListNode replace(ListNode old,ListNode sost) throws Exception {
if (old!=null&&old.size()==1){ int padre=padre(old.get(0));
Integer min= data.searchANDDestroyA(null,old.get(0),false); Integer max= data.searchANDDestroyA(old.get(0),null,false); delete(old);
copyNodes(sost,padre,min,max); } else{
logger.info("Query ambigua: la posizione di inserimento non chiara\n si chiede di sostituire una lista di nodi,\n mentre ne richiesto solo uno"); throw new Exception("Errore, vedi log");
}
return new ListNode(); }
/**
* @param old Lista di un nodo da rinominare * @param sost il nuovo tag
* @throws Exception
* Modifica il tag del nodo selezionato con la stringa sost */
public ListNode rename(ListNode old,String sost) throws Exception { if (old!=null&&old.size()==1&&old.get(0)!=0&& (data.getNodo(old.get(0)).getType().equalsIgnoreCase("Element") ||data.getNodo(old.get(0)).getType().equalsIgnoreCase("Attribute")) { data.getNodo(old.get(0)).setTag(sost); }else{
logger.info("Impossibile eseguire: stai cercando di rinominare una query vuota o con pi di un elemento, oppure la root");
throw new Exception("Errore, vedi log"); }
return new ListNode(); }
/**
* @param L Lista di alberi da inserire
* @param f Lista di un nodo che sar il padre degli alberi * @throws Exception
* Inserisce una copia degli alberi nella lista L come primi figli di f. * Li inserisce nell’ordine in cui sono stati dati.
*/
public ListNode insertAFInto(ListNode L, ListNode f ) throws Exception { if (f.size()==1){ if (data.getNodo(f.get(0)).getType().equalsIgnoreCase("Element") ||data.getNodo(f.get(0)).getType().equalsIgnoreCase("Document")) {Integer max=figlioMinore(f.get(0)); copyNodes(L,f.get(0),null,max);} else{
logger.info("Impossibile eseguire, Si vuole aggiungere un figlio ad un nodo di tipo " + data.getNodo(f.get(1)).getType()); throw new Exception("Errore, vedi log");
} } else{
logger.info("Query ambigua: la posizione di inserimento non chiara\n si chiede di inserire sotto una lista di nodi,\n
mentre ne richiesto solo uno"); throw new Exception("Errore, vedi log"); }
return new ListNode(); }
/**
* @param L Lista di alberi da inserire
* @param f Lista di un nodo che sar il padre degli alberi * @throws Exception
* Inserisce una copia degli alberi nella lista L come primi figli di f. * Li inserisce nell’ordine in cui sono stati dati.
*/
{ if (p.size()==1){ if (data.getNodo(p.get(0)).getType().equalsIgnoreCase("Element") ||data.getNodo(p.get(0)).getType().equalsIgnoreCase("Document")) {int min=figlioMaggiore(p.get(0)); copyNodes(L,p.get(0),min,null);} else{
logger.info("Impossibile eseguire, Si vuole aggiungere un figlio ad un nodo di tipo " + data.getNodo(p.get(1)).getType()); throw new Exception("Errore, vedi log");
} } else{
logger.info("Query ambigua: la posizione di inserimento non chiara\n si chiede di inserire sotto una lista di nodi,\n
mentre ne richiesto solo uno"); throw new Exception("Errore, vedi log"); }
return new ListNode(); }
/**
* @param L Lista di alberi da inserire
* @param b Lista di un nodo che sar il fratello maggiore degli alberi * @throws Exception
* Inserisce una copia degli alberi nella lista L come fratelli minori di b * Li inserisce nell’ordine in cui sono stati dati.
*/
public ListNode insertBefore(ListNode L, ListNode b ) throws Exception { if (b.size()==1){ if (data.getNodo(b.get(0)).getType().equalsIgnoreCase("Element") ||data.getNodo(b.get(0)).getType().equalsIgnoreCase("Document")) {int padre=padre(b.get(0)); Integer min=data.searchANDDestroyA(null,b.get(0),false); copyNodes(L,padre,min,b.get(0)); }else{
logger.info("Impossibile eseguire, Si vuole aggiungere un figlio ad un nodo di tipo " + data.getNodo(b.get(1)).getType()); throw new Exception("Errore, vedi log");
} else{
logger.info("Query ambigua: la posizione di inserimento non chiara\n si chiede di inserire prima di una lista di nodi,\n
mentre ne richiesto solo uno"); throw new Exception("Errore, vedi log"); }
return new ListNode(); }
/**
* @param L Lista di alberi da inserire
* @param a Lista di un nodo che sar il fratello minore degli alberi * @throws Exception
* Inserisce una copia degli alberi nella lista L come fratelli * maggiori di a.
* Li inserisce nell’ordine in cui sono stati dati. */
public ListNode insertAfter(ListNode L, ListNode a ) throws Exception { Integer padre; if (a!=null&&a.size()==1){ if (data.getNodo(a.get(0)).getType().equalsIgnoreCase("Element") ||data.getNodo(a.get(0)).getType().equalsIgnoreCase("Document")) {padre=padre(a.get(0)); Integer mag=searchANDDestroyA(a.get(0),null,false); copyNodes(L,padre,a.get(0),mag); //ERRore }else{
logger.info("Impossibile eseguire, Si vuole aggiungere un figlio ad un nodo di tipo "
+ data.getNodo(a.get(1)).getType()); throw new Exception("Errore, vedi log");
} } else{
logger.info("Query ambigua: la posizione di inserimento non chiara\n.
si chiede di inserire dopo una lista di nodi,\n mentre ne richiesto solo uno");
throw new Exception("Errore, vedi log"); }
return new ListNode(); }
/**
* @param n Lista di nodi da filtrare