Indice
1 XML e XQuery 4
1.1 XML . . . 4
1.1.1 Dtd: Document Type Definition . . . 8
1.2 XQuery . . . 9
2 Proposte di linguaggio 14 2.1 Updating XML - Tatarinov, Ives, Halevy, Weld[5] . . . 14
2.2 UpdateX - Sur, Hammer, Sim´eon[6] . . . 16
2.3 XML-RL Update - Lu, Liu, Wang[9] . . . 17
2.4 XQuery! - Ghelli, R´e, Sim´eon[4] . . . 18
2.5 XQuery Update Facility - Chamberlain, Florescu, Robie[7] . . 20
2.6 XQueryP - Chamberlain, Carey, Florescu[10] . . . 20
3 Definizione Formale del Linguaggio 23 3.1 Sintassi . . . 24
3.2 Il modello dei dati . . . 25
3.3 Formalizzazione semantica . . . 27
3.3.1 Le regole semantiche . . . 29
3.3.2 Operatori sullo Store . . . 30
3.4 Le espressioni di aggiornamento . . . 36 3.4.1 Insert . . . 36 3.4.2 Delete . . . 37 3.4.3 Replace . . . 39 3.4.4 Rename . . . 41 4 Implementazione 42 4.1 Il package “processor” . . . 43 4.2 Il package “gui” . . . 45 5 Conclusioni 46 1
Introduzione
XML, inizialmente proposto come standard per la rappresentazione dei do-cumenti testuali, si sta ora diffondendo come standard per l’interscambio di informazioni tra le diverse applicazioni. L’uso diffuso di XML ne ha cambiato pian piano l’utilizzo, dal semplice formato per scambio di informazioni alla “tecnologia chiave di W3C, un mezzo espandibile e flessibile per modellare il Web, di cui costituisce la lingua franca” [1].
XML `e in realt`a una famiglia di tecnologie collegate, fra queste tecnologie alcune delle pi`u importanti sono XQuery e XPath di cui parleremo nel pa-ragrafo 1.2, che sono linguaggi di interrogazione. A causa della sua notevole diffusione e della diversificazione dei suoi utilizzi, un linguaggio per la sola interrogazione di dati `e insufficiente. “Perch`e XML possa diventare una rap-presentazione universale di dati e formato di scambio fra sistemi qualsiasi, gli utenti devono poter apportare aggiornamenti i documenti XML.”[5] La pos-sibilit`a di aggiornare `e importante, non solo per i documenti, ma anche per propagare cambiamenti attraverso delle viste, magari di database relazionali o di qualsiasi tipo. L’aggiornamento per`o comporta nuove problematiche da risolvere, per esempio la validazione (cio`e la verifica della correttezza della struttura di un documento dopo l’aggiornamento), o i riferimenti mancanti (variabili che puntano a nodi cancellati).
Esistono alcune API, disponibili per molti linguaggi di programmazione, che consentono l’aggiornamento di documenti XML, ma non esiste ancora uno standard per un linguaggio ad alto livello.
Scopo della mia tesi `e la realizzazione di un linguaggio ad alto livello per l’aggiornamento di dati XML.
Nel capitolo 1 descriver`o quelle tecnologie che sono la base di partenza poter affrontare il resto della tesi: XML ed XQuery.
Nel capitolo 2 far`o una panoramica su alcune proposte di altri linguaggi per aggiornare dati XML.
Nel capitolo 3 proceder`o alla definizione formale di un nuovo linguaggio. Mentre nel capitolo 4 descriver`o le scelte fatte a livello implementativo e gli strumenti utilizzati.
Capitolo 1
XML e XQuery
1.1
XML
XML: eXtensible Markup Language, ovvero linguaggio estensibile di marca-tura dalle propriet`a.
XML `e un linguaggio estendibile realizzato per poter utilizzare in modo semplice i documenti strutturati, studiato per il Web e per superare i limiti di HTML (HyperText Markup Language), ma con possibilit`a di utilizzo in ambienti differenti.
In un testo il Markup `e tutto ci`o che ha un significato speciale, che deve essere ben caratterizzato. In XML tutto ci`o che `e compreso tra i caratteri “<”e “>” (angled brackets, parentesi angolari) `e considerato markup, viene detto anche tag (etichetta), ad esempio: <nome>, nome `e un tag. Un tag `e detto di chiusura se inizia con il carattere “/”, ed `e un tag di chiusura per uno di apertura col nome che `e riportato subito dopo il carattere “/”. Un tag vuoto `e un tag che termina con il carattere “/”.
XML `e un metalinguaggio, contrariamente ad HTML che `e un linguaggio predefinito, non ha tag predefiniti ma consente di definire nuovi metalinguag-gi, `e estensibile. Lo sviluppo dell’XML `e iniziato nel 1996. Nel dicembre 1997 le specifiche di XML venivano pubblicate come Proposed Recommendation. Tuttavia, anche se gli obiettivi iniziali della nascita di XML erano rivolti alla soluzione di un problema di standard per il Web, ben presto ci si accorse che XML non era limitato al solo contesto Web. Esso risulta essere abbastanza generale per poter essere utilizzato nei pi`u disparati contesti: dalla defini-zione della struttura di documenti allo scambio di informazioni tra sistemi diversi, dalla rappresentazione di immagini alla definizione di formati di dati.
Gli obiettivi progettuali di XML sono:
1. XML deve essere utilizzabile in modo semplice su Internet.
2. XML deve supportare un gran numero di applicazioni. 3. XML deve essere compatibile con SGML.
4. Deve essere facile lo sviluppo di programmi che elaborino documenti XML.
5. Il numero di caratteristiche opzionali deve essere mantenuto al minimo possibile, idealmente a zero.
6. I documenti XML dovrebbero essere leggibili da un uomo e ragionevol-mente chiari.
7. La progettazione XML dovrebbe essere rapida. 8. La progettazione XML deve essere formale e concisa. 9. I documenti XML devono essere facili da creare.
10. Non `e di nessuna importanza l’economicit`a nel markup XML.
XML non `e un linguaggio di programmazione, `e un insieme di regole per formulare dei file in formato testo che permettano di strutturare dati. Se un documento rispetta queste regole, allora si dir`a “ben formato”.
Poich´e XML `e un formato di testo e usa i tag per delimitare i dati, i file XML sono praticamente sempre pi`u grandi degli analoghi file in bina-rio. Questa `e stata una decisione presa coscientemente dagli sviluppatori dell’XML. Uno dei vantaggi del formato testo `e che permette, se necessario, di controllare i dati pur non disponendo del programma che li ha prodotti, inoltre i formati testo permettono agli sviluppatori un debug pi`u semplice delle applicazioni. Gli svantaggi possono solitamente essere compensati a livelli diversi. Lo spazio su disco diventa sempre meno costoso ed i program-mi di compressione sono in grado di ridurre lo spazio occupato dai file in maniera efficiente. Inoltre, i protocolli di comunicazione usati tra dispositivi di rete, possono comprimere i dati al volo, risparmiando banda esattamente come per i file binari.
Uno dei punti di forza di XML `e che, nei documenti i dati sono strutturati e modellano entit`a complesse qualsiasi.
L’utilizzo di XML semplifica notevolmente la pubblicazione di informa-zioni a livello internazionale, con il grosso vantaggio di essere indipendente dalla piattaforma e dal linguaggio. Inoltre la sintassi di XML `e semplice, di facile apprendimento, ma molto espressiva.
Gli elementi sintattici costitutivi di un documento XML sono dichiarazio-ni, elementi, istruzioni di elaborazione e commenti. Non tutti questi elementi sono indispensabili in un documento XML, alcuni sono opzionali.
1. Gli elementi sono costituiti da un tag vuoto oppure da tutto ci`o che `e racchiuso tra il tag di apertura e il corrispondente tag di chiusura; in un documento `e obbligatoria la presenza di almeno un elemento. 2. Le dichiarazioni, sono elementi il cui tag inizia con il carattere “!” e
sono opzionali.
3. Le istruzioni di elaborazione sono elementi il cui tag inizia e nisce con il carattere“?”, possono essere presenti ovunque in un documento e sono opzionali.
4. I commenti sono elementi il cui tag inizia con i caratteri “! - -” e termina con “- -”, possono essere presenti in un punto qualsiasi del documento, non vengono elaborati dai parser e sono opzionali.
Un documento XML si divide in due parti:
Un prologo opzionale che contiene le dichiarazioni, come <?xml version=“1.0”?>, con cui quasi sempre comincia un documento e che oltre alla versione,
pu`o contenere altri attributi, come il tipo di codifica di caratteri, l’op-zione standalone che definisce se vi saranno riferimenti ad altri file. Altre dichiarazioni possono seguire, come la definizione del DTD (di cui si parler`a nel paragrafo1.1.1) o del tipo di documento
Un corpo obbligatorio e che deve contenere almeno un elemento. Un docu-mento XML `e di per se caratterizzato da una struttura gerarchica. Esso `e composto da elementi. Ciascun elemento rappresenta un componente logico del documento e pu`o contenere altri elementi (sottoelementi) o del testo.Gli elementi possono avere associate altre informazioni che ne descrivono le propriet`a. Queste informazioni sono chiamate attributi. Perch`e un documento si possa dire ben formato deve:
1. contenere almeno un elemento;
2. esistere un tag unico di apertura e di chiusura che contenga l’intero documento; questo tag `e chiamato elemento radice (root);
3. tutti i tag devono essere nidificati (fra un tag di apertura ed il suo corrispettivo di chiusura non ve ne devono essere altri aperti ma non chiusi);
<?xml version="1.0" ?> <primo> <secondo>contenuto</secondo> <secondo/> <secondo/> <secondo> <terzo> <quarto></quarto> </terzo> <secondo/> <secondo/> <secondo> <terzo> <quarto ord="1"></quarto> <quarto ord="2"></quarto> <quarto ord="3"></quarto> <quarto ord="4"></quarto> </terzo> </secondo> </primo>
Figura 1.1: Esempio di struttura ben annidata
La figura 1.1 rappresenta un piccolo documento, nel quale possiamo ve-rificare soddisfatte le caratteristiche per essere “ben formato”.
La radice contiene l’insieme degli altri elementi del documento. Possiamo rappresentare graficamente la struttura di un documento XML tramite un albero, generalmente noto come “document tree”.
Nella figura 1.2 possiamo riconoscere il prologo con la dichiarazione del tipo di documento.
Nel corpo, figura 1.3, possiamo vedere elementi vuoti <secondo/>, con-tenenti sottoelementi <terzo> <quarto/> </terzo>,
attributi <quarto ord=“1”> </quarto> ed elementi contenenti testo <secondo> contenuto </secondo>
<?xml version="1.0" ?> Figura 1.2: Prologo <primo> <secondo>contenuto</secondo> <secondo/> <secondo/> <secondo> <terzo> <quarto/> </terzo> <secondo/> <secondo/> <secondo> <terzo> <quarto ord="1"></quarto> <quarto ord="2"></quarto> <quarto ord="3"></quarto> <quarto ord="4"></quarto> </terzo> </secondo> </primo> Figura 1.3: Corpo
1.1.1
Dtd: Document Type Definition
Un Dtd `e un documento che descrive i tag utilizzabili in un documento XML, la loro reciproca relazione nei confronti della struttura del documento e altre informazioni sugli attributi di ciascun tag. La sintassi di un Dtd si basa prin-cipalmente sulla presenza di due dichiarazioni: <!ELEMENT> e <!ATTLIST>. La prima definisce gli elementi utilizzabili nel documento e la struttura del
documento stesso (cio`e come sono nidificati), la seconda definisce la lista di attributi per ciascun elemento. Si pu`o inoltre specificare il numero di elementi che si possono avere: “*” zero o pi`u elementi, “+” uno o pi`u, “?” zero o uno. In un Dtd si possono definire i tipi di dato di un elemento o di un’attributo, se quest’ultimo `e necessario, opzionale o deve avere un determinato valore. Esistono due modi per indicare il Dtd cui un documento XML fa riferimento. Il primo modo prevede la presenza del Dtd all’interno del documento XML. Nel prologo vi `e una dichiarazione come in figura 1.4. Il secondo modo
pre-<?xml version="1.0"> <!DOCTYPE radice[
...Definizioni del Dtd... ]>
<radice>
...Contenuto del documento XML... </radice>
Figura 1.4: Dtd all’interno di un documento
vede che il Dtd sia definito in un file esterno ed il documento XML abbia un riferimento a tale file: <!DOCTYPE radice SYSTEM “radice.dtd”> il nome del file pu`o essere sostituito da un URL.
Utilizzando i Dtd, quindi, abbiamo un maggior controllo sulla struttura e sull’uso dei tag in un documento XML, inoltre per conoscere la struttura di un documento non abbiamo bisogno di leggere file enormi e difficili da seguire, ne abbiamo un “indice”.
Un documento XML si dice valido, se `e ben formato, contiene un Dtd e rispetta i vincoli posti nel Dtd.
1.2
XQuery
XML mette a disposizione strumenti efficaci per descrivere dati semi-strutturati mediante l’utilizzo di marcatori. Da solo, per`o, XML non d`a i mezzi per identificare specifici sottoinsiemi di dati memorizzati in un documento; al-l’interno del XSLT si sono ormai affermati due linguaggi di interrogazione appartenenti alla famiglia di XML: questi sono XPath ed XQuery.
XPath `e un linguaggio basato sul concetto di percorsi (paths) che con-sentono di raggiungere un gruppo qualsiasi di nodi in un documento XML, ma non lo tratteremo in maniera estesa.
XQuery `e un linguaggio di interrogazione progettato per collezioni di dati XML. XQuery `e un linguaggio funzionale progettato cercando di rispettare la compatibilit`a con altri standard della famiglia XML, e soprattuto con XPath di cui include una parte.
“La missione del progetto XML Query `e quella di consentire query flessibili per estrarre dati da documenti reali e virtuali sul World Wide Web, quindi finalmente permettere l’interazione fra il mondo Web e quello dei database. Infine, collezioni di files XML saranno accessibili come database”[3].
XQuery `e stato sviluppato da un gruppo di lavoro del World Wide Web Consortium, basato su una proposta di linguaggio, Quilt, che traeva carat-teristiche a sua volta da altri linguaggi:
1. Sintassi per navigare all’interno di un documento come in XPath e XQL.
2. Definizione di variabili globali e locali simile a XML-QL. 3. Query come insieme di proposizioni da SQL.
4. Definizione di funzioni come in OQL.
XQuery `e un linguaggio funzionale interamente costituito da espressioni. Le espressioni, a differenza degli statement, vengono valutate e restituiscono un valore senza che si verifichino effetti laterali. Un programma XQuery `e semplicemente un’espressione. Il programma in figura 1.5 ad esempio, resti-tuisce la lista degli speaker per ogni atto dell’Amleto.
In XQuery una variabile `e un nome che inizia col simbolo “$” ($act, $spea-kers). Una variabile pu`o essere legata ad un valore ed utilizzata all’interno dell’espressione che le ha legate (FOR, LET) per rappresentare quel valore.
Esistono diversi tipi di espressioni in XQuery:
1. Espressioni di percorso (paths). XQuery ha una sintassi simile a XPa-th, Un’espressione di percorso `e un insieme di passi, ogni passo `e un movimento all’interno della struttura di un documento. Il risultato `e una lista di nodi. XQuery ha inoltre il predicato RANGE come in XQL, che permette di scegliere un range di elementi.
<html><head/><body> {
for $act in doc("hamlet.xml")//ACT
let $speakers := distinct-values($act//SPEAKER) return
<span>
<h1>{ $act/TITLE/text() }</h1> <ul>
{
for $speaker in $speakers return <li>{ $speaker }</li> }
</ul> </span> }
</body></html>
Figura 1.5: Semplice codice XQuery
2. Costruttori di elemento. In XQuery, un’espressione pu`o incapsulare il risultato di un’altra espressione, in un nuovo elemento.
3. Espressioni FLWR (for let where return, si legge FLoWeR). Un espres-sione FLWR `e formata dalle proposizioni FOR, LET , WHERE e RETURN. Come in SQL, queste dovranno essere in un ordine preciso. Prima una sequenza di FOR e LET, che assegnano un valore ad una o pi`u variabili referenziate nella query, mentre il FOR assegna un valore alla volta, il LET assegna alla variabile una lista di nodi.
L’output della sequenza di FOR `e LET `e una lista di tuple di variabili assegnate, questa viene filtrata con la clausola WHERE, che ammette solo le tuple che verificano la condizione.
L’output `e ancora una volta una lista di tuple, che nel RETURN viene espansa sostituendo i nomi di variabili con i loro valori, valutando le funzioni e generando un frammento XML. Un esempio di espressione FLWR si pu`o vedere in figura 1.5.
4. Espressioni con operatori e funzioni XQuery fornisce gli operatori stan-dard aritmetici, logici e UNION, INTERSECT ed EXCEPT dagli in-siemistici, in pi`u prende da XQL gli operatori BEFORE ed AFTER. 5. Condizionali XQuery utilizza un clssico IF THEN ELSE. Come ogni
espressione XQuery, le espressioni condizionali vengono valutate e re-stituiscono un valore.
6. Quantificatori SOME ed EVERY sono i due quantificatori.
7. Filtraggio La funzione filter `e una proiezione, si utilizza spesso per creare viste o simili.
8. Tipi di dato XQuery supporta i tipi di dato di XML Schema: string, boolean, integer, decimal e float, che non hanno bisogno di costruttori, ed altri come date(“2006-10-13”) che ne necessitano. XQuery permette anche la definizione di tipi da parte dell’utente.
9. Funzioni XQuery fornisce una vasta libreria di funzioni: document, avg, sum, ecc...
declare function local:doubler($x) { $x * 2 }
Figura 1.6: Dichiarazione di funzione in XQuery
In figura 1.5 possiamo riconoscere vari tipi di espressioni combinate insie-me, a parte la clausola FLWR, vediamo funzioni come “doc()” e “distinct-values()”, vediamo paths $act//SPEAKER e costruttori (i tag all’inizio e alla fine). Mentre la figura 1.6 mostra una dichiarazione di funzione.
L’espressione FLWR `e l’espressione pi`u importante in XQuery, ci permet-te di creare ambienti di variabili locali alle funzioni.
Pensiamo ad una ricerca molto complicata (dal punto di vista strutturale), legarla ad una variabile per poi scorrerla con un for, ci permette di scrivere un testo molto pi`u conciso e comprensibile.
Molti template processor, come JSP, PHP, permettono di inserire espres-sioni in un linguaggio di programmazione all’interno di contenuti HTML. Anche XQuery ci da questa possibilit`a, ed in pi`u la possibilit`a di inserire
XML o HTML all’interno di espressioni, e di sostituire le espressioni con i loro valori all’interno di quel contesto.
Con XQuery si possono creare nuovi nodi, ma non modificarli dopo averli creati.
Il linguaggio `e basato su un modello dei dati con struttura ad albero per rappresentare le informazioni di un documento XML. Tale rappresentazio-ne comprende sette tipi di nodo: nodi document, elementi, nodi di testo, attributi, commenti, istruzioni e namespaces. Il type system del linguaggio modella tutti i valori come sequenze, i cui elementi possono essere nodi o valori atomici, ed anche i valori “unici” vengono restiuiti come sequenza di un unico valore.
Capitolo 2
Alcune proposte di linguaggi
d’aggiornamento per XML
Negli ultimi anni il problema dell’aggiornamento di dati XML `e stato af-frontato con diversi approcci. Molte proposte di soluzione si sono basate su XQuery, essendo questo uno standard. Alcune hanno utilizzato un core minimo del linguaggio, altre hanno lavorato partendo dall’intero linguaggio. Questo approccio permette di affrontare direttamente il problema dell’ag-giornamento, inoltre la sintassi di XQuery `e ormai ben nota ed adottare per le istruzioni di aggiornamento una sintassi simile, ne rende pi`u facile la comprensione e l’apprendimento.
alcune propriet`a sono basate sulla “snapshot semantics”, la quale prevede che in presenza di un aggiornamento dei dati questo sia messo “da parte” in un’apposita lista di aggiornamenti pendenti le cui modifiche verranno ap-plicate solo in determinati punti del programma, tipicamente quando si `e valutato un’intera query (cio`e una query che non sia sottoquery di un’altra). Questa tecnica `e utilizzata in [6][7].
I linguaggi proposti hanno spesso caratteristiche simili, ma si possono evidenziare alcune differenze, in figura 2.7 e in figura 2.8 vedremo un’analisi comparativa dei linguaggi proposti, tratta da [8].
2.1
Updating XML - Tatarinov, Ives, Halevy,
Weld[5]
Il progetto si configura come un’estensione di XQuery per gli aggiornamenti. Partendo da XQuery, arricchito con la selezione di attributi, questo viene esteso con le operazioni di aggiornamento.
Il lavoro `e stato pubblicato nel 2001 e molti altri dopo vi si sono ispi-rati. Questo lavoro si concentra particolarmanete sulla valutazione della performance della traduzione da aggiornamenti XML a aggiornamenti SQL applicati a dati XML contenuti in database relazionali.
La sintassi `e semplice ed intuitiva per chi gi`a conosce XQuery, di cui man-tiene lo stile anche dal lato degli aggiornamenti. Vengono definite quattro primitive di aggiornamento: Insert, Delete Replace e Rename, ma non vengo-no combinate con le altre espressioni XQuery. Per applicare l’aggiornamento in maniera ripetuta viene utilizzata una nuova primitiva che prende spunto dall’espressione FLWR di XQuery, l’espressione FLWU. Mentre FLWR `e l’a-cronimo di For, Let, Where e Return, FLWU `e l’al’a-cronimo di For, Let, Where e Update. Vediamo un esempio della sintassi di questa primitiva in figura 2.1.
FOR $p IN document("bio.xml")/paper, $cat IN $p/@category,
$bio IN $p/ref(biologist, "smith1"), $ti IN $p/title UPDATE $p { DELETE $cat, DELETE $bio, DELETE $ti }
Figura 2.1: Esempio di espressione FLWU in Updating XML
Alcune delle clausole della primitiva FLWU sono opzionali o a scelta, come nell’espressione FLWR. Le clausole For e Let possono essere presenti entrambe o solo una di esse, la clausola WHERE `e opzionale, mentre la clausola UPDATE deve essere sempre presente. Per la selezione di nodi viene utilizzato XPath, ma il linguaggio `e stato arricchito per consentire la selezione, e quindi la modifica degli attributi.
L’articolo non `e corredato di una definizione formale semantica, sappiamo per`o che utilizza il modello di dati di XQuery (XDM). L’unico studio formale presentato `e lo studio dei vincoli sulle primitive (cardinali`a di argomenti, tipi etc...).
Non `e chiaro se la semantica del linguaggio utilizzi la tecnica della “snap-shot semantics” o quale altro approccio.
2.2
UpdateX - Sur, Hammer, Sim´
eon[6]
UpdateX `e un’estensione di XQuery. Il linguaggio proposto utilizza espres-sioni XQuery per il calcolo degli argomenti, sia per i target che per i contenuti da aggiornare, mentre non consente di utilizzare istruzioni di aggiornamento all’interno delle Query.
Mentre XQuery si basa sul concetto di espressione, che viene valutata e restituisce dei risultati, UpdateX si basa sugli “statement”, che vengo-no eseguiti e modificavengo-no la memoria invece che restituire semplicemente dei valori.
replace
$auction/site/people/person[@id="person10"]/creditcard with <creditcard>233 3423 3484 2743</creditcard>
Figura 2.2: Esempio di aggiornamenti semplici in UpdateX
La sintassi prevede due categorie di istruzioni di aggiornamento:
aggiornamenti semplici. Sono previste tre istruzioni semplici di aggior-namento INSERT, DELETE e REPLACE. Se ne veda un esempio in figura 2.2.
aggiornamenti complessi. Si costruiscono a partire da istruzioni sempli-ci di aggiornamento inserendole in espressioni FLWR o in espressioni condizionali. Un esempio in figura 2.3.
Il documento presenta una semantica discorsiva delle primitive, descri-vendone vincoli di cardinalit`a e tipo, ma non specifica tutto il framework semantico.
Il modello dei dati `e lo stesso di XQuery.
Il motore di valutazione del linguaggio contiene una fase di controllo se-mantico sui contenuti che procede infine a validare i risultati, ed utilizza la tecnica della “snapshot semantics”.
update
if ($auction/site/categories/category[@id="category4"]) then
replace $auction/site/categories/category
[@id="category4"]/name with <name>2003 Car Sales</name>
else
insert <category id="category4"> <name>2003 Car Sales</name>
<description> <parlist>
<listitem>
<text>New <bold> Toyota Camry </bold> 2003</text> </listitem>
</parlist> </description>
into $auction/site/categories;
Figura 2.3: Esempio di aggiornamenti complessi in UpdateX
2.3
XML-RL Update - Lu, Liu, Wang[9]
A differenza dei precedenti, questo `e un linguaggio dichiarativo, basato su regole. Non si basa su XQuery, ma su XML-RL, un linguaggio di interroga-zione, con sintassi simile ad XPath, ma basato su regole.
XML-RL differisce da XPath perch`e all’interno dei path `e anche possibile fare degli assegnamenti a variabili, caratteristica insolita, ma il linguaggio `e equivalente ad XPath/XQuery.
XML-RL rappresenta i documenti XML, come istanze di un modello di dati basato su oggetti complessi.
Gli oggetti si dividono in cinque tipi di entit`a per oggetti differenti: ele-menti, attributi, tuple per rappresentare relazioni fra elementi e attributi, liste per i valori multipli e oggetti lessicali per le costanti.
Le regole sono composte da due parti, “Querying” e “Updating”. La fase di “Querying” (interrogazione) si basa su XML-RL. La fase di “Updating” composto di una lista di espressioni semplici di aggiornamento. In figura 2.4
`e presentato un esempio di aggiornamento.
I vincoli esaminati a fondo anche in questo articolo sono gli stessi degli altri linguaggi.
Querying (URL)/department/$f(faculty)[name=[firstNeme=Ayse, lastName=Alaca]]/position=$p,
(URL)/department/$s(student)[name=[firstNeme=Mery, lastName=Lee]]
Updating insert-into($f) : @status=full time, replace($p) : Professor,
delete $s
Figura 2.4: Esempio di aggiornamento con XML-RL Update
Non `e presente nell’articolo una definizione semantica formale del linguag-gio.
2.4
XQuery! - Ghelli, R´
e, Sim´
eon[4]
XQuery! (si legga: “XQuery Bang”) `e un estensione di XQuery per l’aggior-namento.
Il linguaggio presenta alcune peculiarit`a rispetto agli altri finora esami-nati.
• La sintassi ci fornisce un’insieme di nuove espressioni che consentono l’aggiornamento, sono espressioni di prima classe, si possono utilizzare insieme alle espressioni XQuery in una sintassi completamente compo-nibile, le espressioni di aggiornamento possono essere utilizzate all’in-terno di espressioni XQuery, come in espressioni di aggiornamento si possono utilizzare espressioni XQuery. Ci`o consente maggior libert`a all’utente, anche se la potenza espressiva `e la stessa di altri linguaggi che non lo permettono.
• La differenza maggiore rispetto ad altri linguaggi `e la presenza di un operatore “snap” che consente all’utente di indicare frammenti dichia-rativi all’interno dei propri programmi, all’interno dei quali `e possibile
utilizzare tecniche di ottimizzazione utilizzate nei database tradizio-nali. Questo operatore ci consente il controllo sul momento di appli-cazione delle modifiche ai dati, sfruttando la tecnica della “snapshot semantics”, ottenedo una sorta di aggiornamento controllato.
Il linguaggio fornisce un insieme di espressioni di aggiornamento, delete, insert, replace e rename, usuali in quasi tutti i linguaggi proposti, in pi`u rende disponibile l’espressione copy, che in altri linguaggi veniva utilizzata nella semantica, ma non era resa disponibile all’utente, oltre chiaramente all’operatore snap che pu`o racchiudere una query qualunque.
Tramite l’operatore snap, il linguaggio fornisce anche il controllo sull’or-dine di applicazione degli aggiornamenti alla memoria. In un linguaggio di aggiornamento, l’ordine `e molto importante: due liste di aggiornamenti, or-dinate diversamente possono produrre risultati diversi. L’operatore snap con l’opzione ordered ci consente, se lo riteniamo necessario, di ottenere dei una valutazione ordinata della lista di aggiornamenti.
In figura 2.5 vediamo un esempio del linguaggio.
let $name := $auction//person[@id = $bidder]/name return
(snap insert { <logentry user="{$name}"
itemid ="{$item/@id}"
date="{current-date()}"/> } into {$log},
snap replace { $log/@count } with {count($log/logentry) })
Figura 2.5: Esempio di aggiornamento con XQuery!
Il modello dei dati `e una modifica del modello dei dati di XQuery (XDM), con l’aggiunta di uno store che consenta l’aggiornamento dei dati. Lo sto-re mantiene le informazioni sui nodi e la struttura dei dati (ad albero co-me in XDM), consentendone la modifica. Sullo store vengono definiti degli operatori corrispondenti a quelli di XDM, pi`u altri per l’aggiornamento.
Il documento presenta una definizione formale approfondita sulla seman-tica delle espressioni e sui vincoli su di esse. A differenza delle altre proposte, questo linguaggio utilizza una tecnica particolare per l’applicazione del de-lete, ossia non cancella tutto il sottoalbero oggetto del dede-lete, ma lo stacca, evitando cos`ı di avere variabili con riferimenti mancanti.
2.5
XQuery Update Facility - Chamberlain,
Florescu, Robie[7]
Il W3C ha presentata la bozza di un linguaggio di aggiornamento che estende XQuery. Questo linguaggio rappresenta un passo verso la definizione di uno standard.
Il linguaggio `e simile a XQuery![4] , visto nel precedente paragrafo 2.5, da cui differisce per l’assenza dell’operatore snap (il motore del linguaggio utiliz-za la tecnica della “snapshot semantics”) e per la presenutiliz-za della espressione transform di cui vediamo un esempio in figura 2.6.
Il linguaggio consente espressioni di aggiornamento come espressioni di prima classe, anche se pone delle limitazioni sull’inserimento di queste espres-sioni in altre come nelle espresespres-sioni FLWOR (la O rappresenta la clausola Order), nelle quali `e consentito inserire espressioni di aggiornamento solo nella clausola return.
for $e in //employee[skill = "Java"] return
transform
copy $je :=$e
modify do delete $je/salary return $je
Figura 2.6: Una espressione transform con XQuery Update facility
2.6
XQueryP - Chamberlain, Carey, Florescu[10]
XQueryP si basa su XQuery Update Facility[7], utilizza tale linguaggio per costruire un linguaggio di programmazione con esso. L’idea relativamente `e nuova per quanto riguarda XML, ma abbiamo gi`a visto linguaggi di questo genere per SQL, basti pensare a PL/SQL di Oracle ed SQL PL di IBM.
XQueryP include caratteristiche tipiche dei linguaggi imperativi, come le variabili, i cicli while, gli assegnamenti e i blocchi.
applicazio-ni senza l’utilizzo di un linguaggio di programmazione generico che immerga funzionalit`a circa XML.
Atomic Selection Style Nondeterminism
Updating XML[5] IDRN XPath Separate Unspecified
XML-RL Update[9] IADR Ad hoc Ad hoc Unspecified
UpdateX[6] IADR XQuery Separate Fixed order
XQuery![4] IADRN XQuery Combined User control
XQuery Update Facility[7] IADRN XQuery Combined User control
XQueryP[8] IADRN XQuery Combined User control
Transform Variables Formal Types
Updating XML[5] No Mutable No No
XML-RL Update[9] No Mutable Yes No
UpdateX[6] No Mutable Yes No
XQuery![4] No Mutable Yes No
XQuery Update Facility[7] Yes Mutable No No
XQueryP[8] Yes Mutable No No
Figura 2.7: Confronto fra le caratteristiche dei linguaggi. la leggenda `e in figura 2.8. Tabella tratta da [8]
Atomic: Quali update atomici sono consentiti? I: inserimento dati prima o dopo un nodo A: attaccare dati alla lista di figli di un nodo D: cancellare un nodo (ed il suo sottoalbero) R: sostituire il valore di un nodo
N: rinominare un nodo
Selection: Che linguaggio si utilizza per la selezione? XPath:
XQuery:
Ad hoc: si utilizza un linguaggio differente
Style: Che stile di programmazione `e usato per le espressioni di aggiornamento, e come interagisce con le espressioni XQuery?
Ad hoc: gli aggiornamenti utilizzano una sintassi differente da XQuery e non correlata con esso
Separate: gli aggiornamenti possono utilizzare XQuery per argomenti, di cui hanno una sintassi simile, ma non il contrario
Combined: gli aggiornamenti si possono usare al posto di espressioni XQuery
Nondeterminism: come `e influenzato il non determinismo del risultato dall’interazione fra effetti laterali e ordine di valutazione?
Unspecified: aspetto non chiarito dall’articolo
Checked: il determinismo `e controllato da controlli dinamici
Fixed order: il determinismo `e controllato fissando un’ordine di valutazione
User control: non determinismo controllato da annotazioni dell’uten-te
Variables: le variabili sono modificabili?
Tranforms: si possono costruire valori XQuery tramite “transformation” (applicando un aggiornamento ad una copia dei dati)?
Formal: la semantica del linguaggio `e descritta formalmente? Types: c’`e un sistema di tipi statico?
Capitolo 3
Definizione Formale del
Linguaggio
La possibilit`a di aggiornare dati XML ha riscosso notevole interesse da parte degli sviluppatori, e mentre nel campo delle API c’erano gi`a degli standard, come SAX[11] e DOM[12], nel campo dei linguaggi ad alto livello gli standard tardano a svilupparsi.
La definizione di un linguaggio di aggiornamento per dati XML presenta alcune scelte fondamentali nella definizione. I linguaggi presentati nel ca-pitolo 2 sono estensioni di XQuery, escluso XML-RL Update, mentre qui `e proposto un linguaggio che utilizza un core minimo di XQuery. XQuery in realt`a integra molte funzionalit`a utili a livello pratico, ma poco interessanti dal punto di vista teorico, che qui non sono state definite.
In altri linguaggi si limitava l’utilizzo delle istruzioni di aggiornamento, tipicamente inserendoli in una instruzione tipo FLWR, questo per cercare di salvaguardare il pi`u possibile la semantica dichiarativa di XQuery.
Alcuni linguaggi permettono alle funzioni di essere oggetti di prima classe (first-class object), cio`e di poter essere trattate come i tipi pi`u comuni (strin-ghe, interi, ecc.): passate come parametri ad altre funzioni, restituite come valori da altre funzioni, associate a variabili, ecc.
In questo linguaggio, come in XQuery![4], le operazioni di aggiornamento sono funzioni di prima classe. Questo anche per rispettare le caratteristiche stesse di XQuery. Ci`o non toglie che le istruzioni di aggiornamento possano essere utilizzate nella clausola “return” di for o let, ma ci`o non `e obbligatorio come in altri linguaggi.
Un linguaggio di aggiornamento, a differenza di uno di interrogazione prevede degli effetti laterali e questo modifica sostanzialmente la formaliz-zazione. Bisogna prevedere delle strutture che consentano gli effetti laterali (sostanzialmente una memori, che poi vedremo nel capitolo 4 come sar`a
lizzata). La memoria proposta definisce una struttura atta a rappresentare una “foresta”, cio`e una sequenza ordinata di alberi, un insieme ordinato di documenti XML.
Dopo aver definito la sintassi del linguaggio e la struttura della memoria, si definir`a una struttura semantica basata su semplici operatori anch’essi definiti in seguito. La semantica delle istruzioni di aggiornamento, come quelle di interrogazione si baser`a su questi semplici operatori.
3.1
Sintassi
Come gi`a detto, le espressioni di aggiornamento, come le altre sono funzioni di prima classe e quindi possono essere composte con le altre liberamente. Questa scelta permette maggior libert`a di espressione per l’utente, anche se la potenza espressiva `e in realt`a la medesima.
Query Q ::= () | root | b | element l[Q] | text l | Q, Q | $x | f or x in Q return Q | let x := Q return Q
| Q/l | Q//l | if P then Q else Q . . . | Delete Q
| Insert Q as f irst into Q | Insert Q as last into Q | Insert Q bef ore Q | Insert Q af ter Q | Replace Q with Q | Rename Q with l
P redicati P ::= not P | P and P | Q = Q
Figura 3.1: Sintassi del linguaggio
Possiamo vedere dalla figura 3.1, come il linguaggio di interrogazione sia stato ridotto rispetto ad XQuery: non abbiamo pi`u la possibilit`a di dichiarare funzioni, n´e di utilizzare la vasta gamma di funzioni di XQuery, ecc...
Il linguaggio `e composto di due sottinsiemi di espressioni: Le espressioni di interrogazione: for, let, i path, ecc...
Le prime sono delle classiche espressioni nello stile XQuery, differenze puramente sintattiche le possiamo ritrovare nelle element l[Q] e text l, equivalenti a quello che in XQuery era la costruzione tramite frammenti XML. Mentre in XQuery for e let erano clausole opzionali dello stesso costrut-to, qui le vediamo separate, anche se chiaramente sono anch’esse equivalenti al loro corrispettivo in XQuerye la clausola where si sostituisce con un con-dizionale. Le espressioni di aggiornamento sono simili a quelle proposte in [7][5][6], ma funzioni di prima classe come in [4].
Le espressioni restituiscono sequenze di alberi (foreste), le espressioni di aggiornamento restituiscono la sequenza vuota.
for $p in /inventory/part
return let $deltap:= $changes/part return if ($deltap/partno = $p/partno) then replace $p/quantity/*
with ($p/quantity + $deltap/quantity)
Figura 3.2: esempio
3.2
Il modello dei dati
L’introduzione di espressioni con effetti laterali modifica necessariamente il modello dei dati, in cui si deve prevedere una memoria (store), che permetta la memorizzazione di dati strutturati come alberi, l’accesso alle informazioni relative ai nodi (tipo, tag, valore), che permetta di identificarne i figli. Pro-prio per raccogliere queste informazioni e modificarle, sono stati definiti degli operatori sulla memoria.
Store S = N, E, A, F N i nodi
E gli archi E ⊆ N × N (n, m) ∈ E significa che n `e il padre di m
A i f ratelli A ⊆ N × N (n, m) ∈ A n `e il fratello immediatamente minore di m F un insieme di funzioni sui nodi che forniscono alcune informazioni
m ~~}}}} }}}} @@ @ @ @ @ @ @ n o p
Figura 3.3: struttura ad albero
La memoria store `e una quadrupla, in cui N `e un insieme finito di nodi, E `e un insieme di archi da padre a figlio, definito da un insieme di coppie ed A `e anch’esso un insieme di coppie che definiscono la relazione fra fratelli immediati; mentre F definisce un’insieme di funzioni parziali su N, F `e una tupla (kind, tag, value).
I nodi possono essere di quattro tipi: element, document, attribute, text. La funzione kind `e totale, e quindi sempre definita.
L’ordinamento, che rispetta quello dato dai documenti se non modificato successivamente, `e ottenuto dato da E, provvista per ogni nodo degli opera-tori padre e figlio e da A, che definisce l’ordinamento fra i fratelli e tramite gli operatori fornisce per ogni nodo, i fratelli maggiore e minore.
L’ordinamento non `e altro che la chiusura transitiva di E ed A.
< = E+
∪ E−)∗ A+
E∗
L’ordinamento cos`ı ottenuto `e un’ordinamento totale sui nodi e rappresenta l’ordinamento del documento.
Per esempio nella figura 3.3 schematizziamo la memoria come N={m; n; o; p}, E={(m,n); (m,o); (m,p)} ed A={(n,o); (o,p)}
L’ordinamento cos`ı ottenuto `e un ordinamento totale irriflessivo e deve verificare alcuni altri vincoli:
∀x, y, z ∈ N. (x, z) ∈ E ∧ (y, z) ∈ E ⇒ x = y (3.1) ∀x, y, z ∈ N. (x, z) ∈ A ∧ (y, z) ∈ A ⇒ x = y (3.2) ∀w, x, y, z ∈ N.(w, x) ∈ A ∧ (y, w) ∈ E ∧ (z, x) ∈ E ⇒ y = z (3.3) ∀x, y ∈ N. (x, y) ∈ E+ ⇒ (y, x) /∈ E+ (3.4) ∀x, y ∈ N ⇒ x ≤ y ∨ y < x (3.5) ∀x ∈ N ⇒ x 6< x (3.6)
Dai vincoli (3.1)-(3.4) si pu`o facilmente dedurre l’aciclicit`a dei grafi rap-presentabili, cio`e la loro struttura ad albero.
3.3
Formalizzazione semantica
Per quanto riguarda la semantica, esistono vari approcci, differendo soprat-tutto sul momento di applicazione delle modifiche alla memoria. Questa scelta modifica fortemente la semantica delle nostre espressioni.
• L’implementazione pi`u semplice `e senza dubbio l’aggiornamento imme-diato, cio`e ogni operazione di aggiornamento modifica subito la memo-ria. Chiaramente questo implica la valutazione di tutte le sottoquery prima di valutare la query che le contiene.
• L’approccio opposto prevede che, ogni aggiornamento sia messo “da parte” in un’apposita lista le cui modifiche verranno applicate solo in determinati punti del programma, tipicamente quando si `e valutato un’intera query (cio`e una query che non sia sottoquery di un’altra). Questa tecnica `e anche detta “snapshot semantics”.
• Una via di mezzo fra le due soluzioni `e l’aggiornamento controllato. In questo approccio gli aggiornamenti sulla memoria vengano effettuati in presenza di determinate istruzioni (p.e. “commit” o snap[4]).
L’aggiornamento immediato `e fra i pi`u diretti e semplici per un’implemen-tazione, ci permette di non preoccuparci di liste di aggiornamenti pendenti. L’approccio presenta degli svantaggi: se si interrompe l’esecuzione dell’ope-razione, per un errore, alcune modifiche potrebbero essere state fatte ed altre no: pensiamo ad un for che si interrompe a met`a.
Per semplicit`a sceglieremo questo approccio. Passiamo a presentare la semantica del linguaggio.
Alcune espressioni, non sono state presentate in quanto molto simili ad altre.
La semantica `e espressa in forma di regole, come la seguente: S; E ⊢ Q1 ⇒ v1; S1
S1; E ⊢ Q2 ⇒ v2; S2
S; E ⊢ Q1, Q2 ⇒ v1, v2; S2
Ogni regola ha una premessa ed una conclusione, la premessa pu`o essere anche vuota. Al di sopra della linea vediamo le premesse, al di sotto le conclusioni derivate dalle premesse.
Esaminiamo una singola asserzione.
S; E ⊢ Q ⇒ v; S1
L’asserzione si legge: in un ambiente E, la valutzione dell’espressione Q trasforma lo store S in S1 e restituisce il valore v.
L’ambiente E `e una funzione che associa un valore ad ogni variabile libera in Q.
Per maggior chiarezza e per adottare uno stile semantico pi`u chiaro, si `e preferito riferirsi nella semantica ad operatori che modifichino lo Store e specificarli separatamente nel paragrafo 3.3.2.
3.3.1
Le regole semantiche
Ora presentiamo la semantica del linguaggio, sotto forma di regole, come quelle espresse nel paragrafo precedente.
Sm; E ⊢ () ⇒ (); Sm S; E ⊢ Q ⇒ v; S1 (S2, n) = NewElement(S1, l, v) S; E ⊢ element l{Q} ⇒ n; S2 S; E ⊢ Q1 ⇒ v1; S1 S1; E ⊢ Q2 ⇒ v2; S2 S; E ⊢ Q1, Q2 ⇒ v1, v2; S2 S; E ⊢ Q ⇒ v; S1 S2 = Delete(S1, v) S; E ⊢ Delete Q ⇒ (); S2 S; E ⊢ Q1 ⇒ v1; S1 S1; E ⊢ Q2 ⇒ v2; S2 S3 = InsertAF Into(S3, v1, v2)
S; E ⊢ Insert Q1as f irst into Q2 ⇒ (); S3
S; E ⊢ Q1 ⇒ v1; S1 S1; E ⊢ Q2 ⇒ v2; S2 S3 = Replace(S2, v1, v2) S; E ⊢ Replace Q1with Q2 ⇒ (); S3 S; E ⊢ Q1 ⇒ n1, . . . , nm; S1 f or i in 1 . . . m : Si; (E + x ⇒ ni) ⊢ Q2 ⇒ vi; Si+1 S; E ⊢ f or x in Q1return Q2 ⇒ v1, . . . , vn; Sm+1 S; E ⊢ Q1 ⇒ v1; S1 S1; (E + x ⇒ v1) ⊢ Q2 ⇒ v2; S2 S; E ⊢ let x = Q2 ⇒ v2; S2
S; E ⊢ P ⇒ true; S1 S1; E ⊢ Q1 ⇒ v; S2 S; E ⊢ if P then Q1else Q2 ⇒ v; S2 S; E ⊢ P ⇒ f alse; S1 S1; E ⊢ Q2 ⇒ v; S2 S; E ⊢ if P then Q1else Q2 ⇒ v; S2 S; E ⊢ Q1 ⇒ v1; S1 S1; E ⊢ Q2 ⇒ v2; S2 b = equal(v1, v2) S; E ⊢ Q1 = Q2 ⇒ b; S2 S; E ⊢ Q1 ⇒ v1; S1 v2 = F ilter (S1, (Children(S1, v1)), l) S; E ⊢ Q/l ⇒ v2; S1
3.3.2
Operatori sullo Store
Gli operatori che seguono, sono quelli che abbiamo visto nel paragrafo pre-cedente all’interno delle regole semantiche , ma ve ne sono alcuni in pi`u.
Questo perch`e non tutti sono disponibili all’utente, alcuni sono di semplice supporto ad altri operatori.
L’operatore Delete sar`a spiegato nel paragrafo 3.4.2.
Delete (Store S, listNode v) case v of
[ ] − > return S
v : vs − > let S′ = StaccaF iglio(S, v) return Delete(S′, vs)
Filter filtra una lista di nodi in base al loro tag che dev’essere uguale a quello passato. Vi sono operatori analoghi per filtri differenti.
Filter(Store S, listNode N, String l) case N of
n : ns − > let (type, tag, val) = F (n)
if tag = l then return n : F ilter(S, ns, l) else return F ilter(S, ns, l)
[ ] − > return null
NewElement crea un nuovo nodo di tipo element e gli assegna una lista di figli. Vi sono operatori analoghi per gli altri tipi.
NewElement(Store S, String tag, listNode L) let (N, E, A, F ) = S
let id = newid(N)
let F′ = (id − > (′′element′′, tag, null))
let N′ = o : N
let S′ = (N′, E, A, F′)
let S′′ = CopyNodes(S′, L, id, null, null) return (S′′, id)
Equal confronta due foreste sia per struttura che per contenuto.
Equal(Store S, listNode L, listNode M) case (L, M) of
(l : ls, m : ms − > if F (l) ! = F (m) then return f alse let NL = ls + + Children(S, l)
let NM = ms + + Children(S, m) return Equal(S, NL, NM)
[ ], [ ] − > return true else return f alse
Children restituisce la lista ordinata dei figli di l, dal minore al maggiore. Se n `e una lista di nodi con pi`u di un’elemento, allora concatena le liste ordinate dei figli di ogni elemento di n.
Children(Store S, listNode n) let (N, E, A, F ) = S case n of
l : ls − > let min = F iglioMinore(E, A, l) let f rat = F ratelliMaggiori(A, min) return min : f rat + + Children(S, ls) [ ] − > return [ ]
L’operatore InsertAFInto sar`a spiegato nel paragrafo 3.4.1.
InsertAFInto(Store S , listNode n, listNode p) case p of
l : [ ] − > let (N, E, A, F ) = S
let max = F iglioMinore(E, A, l) return CopyNodes(S, n, l, null, max) else ERROR
Di seguito presentiamo gli operatori non disponibili per l’utente.
CopyNodes crea una copia profonda degli alberi discendenti dai nodi nella lista l e li “inserisce” come figli di f e fra i fratelli s e b.
CopyNodes(Store S , listNode l, value f, value s, value b) let (N, E, A, F ) = S
case l of
n : ns − > let (S′, id) = NewNode(S, n, f, s, b) let l′ = Children(S′, n)
let S′′ = CopyNodes(S′, l′, id, null, null) let S′′′ = CopyNodes(S′′, ns, f, id, b) return S′′′
[ ] − > return S
FiglioMinore dato un nodo restituisce il figlio minore di quel nodo o se non c’`e restituisce null.
FiglioMinore(Archi E, Fratelli A, value p) case E of
E′ + + (p, n) : E′′− > case A of
A′ + + (b, n) : A′′− > return F iglioMinore(E′ + + E′′, A, p) else − > return n
FratelliMaggiori restituisce la lista ordinata dei fratelli maggiori del nodo dato. FratelliMaggiori(Fratelli A, value l) case A of A′ + + (l, m) : A′′− > m : F ratelliMaggiori(A, m) else return [ ]
Padre dato un nodo restituisce il padre o se non ha padre restituisce null.
Padre(Archi E, value p) case E of
E′ + + (n, p) : E′′− > return n else return null
StaccaFiglio dato un nodo provvede ad eliminare l’arco che lo lega al padre ed i legami con i fratelli.
StaccaFiglio(Store S, value v) let (N, E, A, F ) = S case E of
E′ + + (p, v) : E′′− > let A′ = StaccaF ratelli(A, v) return (N, E′ + +E′′, A′, F ) else return S
StaccaFratelli dato un nodo provvede a staccarlo dai fratelli. StaccaFratelli(Fratelli A, value v) case A of A′ + + (m, v) : A′′− > case A′ + + A′′of A′′′ + + (v, n) : A′′′′− > return A′′′ + + A′′′′ A′ + + (v, n) : A′′− > return A′ + + A′′ else return A
NewNode crea un nodo uguale a n, ma lo inserisce nella foresta nella posizione definita dai parametri.
NewNode(Store S , value n, value p, value min, value max) let (N, E, A, F ) = S
let (type, tag, val) = F (n) let id′ = newid(N)
let N′ = id′ : N
let F′ = (id′ − > (type, tag, value)) : F let E′ = if p ! = null then E : (p, n′)
else E case A of
A′ + + (min, max) : A′′ − > let A′′′ = A′ + + A′′ else let A′′′ = A
let A′′′′ = if min ! = null then A′′′ : (min, n′) else A′′′
let A′′′′′ = if max ! = null then A′′′ : (n′, max) else A′′′′
let S′ = (N′, E′, A′′′′′, F′) return(S′, id′)
3.4
Le espressioni di aggiornamento
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 legasta-ta una variabile, e quindi come comporsta-tarsi 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.
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 generasta-te automaticamensta-te 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 generasta-te automaticamensta-te 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 quel-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.
*/
