Risoluzione efficiente di interrogazioni XPath su documenti XML con attributi e riferimenti

Piu` in dettaglio, le fasi che hanno portato alla realizzazione del presente lavoro
di tesi hanno riguardato: lo studio del linguaggio XML con attributi e riferimenti;
l’identificazione di un frammento di XPath per interrogare documenti con attributi
e riferimenti, con specifica della sua sintassi e semantica; l’ideazione dell’algorit-
mo per la risoluzione di interrogazioni nel frammento XPath scelto ed analisi della
complessita` computazionale; implementazione in linguaggio C del processore di in-
terrogazioni; test di efficienza e confronto con un processore efficiente noto nella
comunita` scientifica internazionale.
4
Capitolo 1
Uno sguardo a XML
1.1 Che cos’e` XML?
XML (eXtensible Markup Language) e` un linguaggio che consente di definire dati
semistrutturati.
Un dato semistrutturato e` una tipologia di dato che contiene al suo interno alcune
informazioni sulla sua struttura oltre al dato in se. Spesso questo tipologia di dati
viene anche definita senza schema (schemaless) o auto-descrittiva (self-describing)
[2]. Tipicamente quando si memorizzano delle informazioni di solito se ne definisce
prima la struttura, lo schema, e successivamente si inseriscono i valori, definiti anche
istanze. Utilizzando dati semistrutturati e` possibile unire le due operazioni prece-
denti tramite l’utilizzo di una semplice sintassi in grado di definire la struttura ed il
valore dei dati contemporaneamente. Proprio per questa natura di sintesi informati-
va i documenti XML sono molto utilizzati per le applicazioni di trasferimento dati,
soprattutto su Internet. Un altro grande vantaggio dei documenti XML e` il fatto
che essi sono scritti in puro formato testuale, un formato universalmente accettato
da tutti i sistemi hardware e software.
L’eXtensible Markup Language e` nato nel febbraio 1998 da una raccomandazione
[3] del W3C (World Wide Web Consortium1), uno dei consorzi di aziende piu` impor-
tanti per la creazione di standard utilizzati su Internet.
XML e` un linguaggio derivato dallo standard SGML (Standard Generalized Mark-
1http://www.w3c.org
5
up Language2), un metalinguaggio, ossia un linguaggio per la creazione di altri lin-
guaggi, utilizzato per la creazione di Markup Language. XML e` un sottonsieme
molto snello dell’SGML. Secondo le specifiche [3] del consorzio W3C gli obiettivi piu`
importanti che hanno spinto alla creazione dello standard XML sono stati:
• facilita` di utilizzo su Internet;
• ampio supporto di applicazioni;
• compatibilita` con l’SGML;
• facilita` di implementazione di programmi che utilizzano documenti XML;
• facilita` di lettura ed interpretazione dei documenti XML;
• facilita` nella creazione di documenti XML;
Molto spesso l’XML viene confrontato con l’HTML (HyperText Markup Language),
il linguaggio utilizzato per la creazione delle pagine web [4]. L’HTML e` un linguaggio
rigido utilizzato semplicemente per impaginare pagine web, l’XML e` un linguaggio
flessibile che consente di descrivere il contenuto di un documento, come ad esempio
una pagina web. La differenza e` fondamentale tanto che l’HTML puo` essere con-
siderato come un sottoinsieme dell’XML. L’XML puo` essere utilizzato anche come
database per la memorizzazione di grandi quantitativi di dati, anche se con alcune
limitazioni [5, 6, 7]. Anche se l’XML non e` stato progettato come strumento per la
memorizzazione di grandi quantita` di informazioni esistono diverse applicazioni che
utilizzano con successo database nativi XML [8, 9].
1.2 La sintassi XML
Un documento XML e` una rappresentazione testuale di informazioni identifi-
cate per mezzo di tag, ossia di stringhe racchiuse tra i simboli < e >. Attraverso
l’utilizzo dei tag e` possibile definire la struttura di un documento XML. Il compo-
nente fondamentale di un documento XML e` l’elemento, una stringa costituita da
un tag di apertura, un valore, eventualmente vuoto, e un tag di chiusura (ad esempio
2Standard ISO 8879 del 1986
6
<name>Alan</name> e` la definizione di un elemento name che contiene il valore
Alan). Il contenuto di un tag identifica in qualche modo la tipologia del dato. Nell’e-
sempio precedente il tag <name> ci fornisce un’informazione chiara e sintetica sulla
sua semantica, ad esempio in questo caso risulta evidente che si sta` definendo il nome
di una persona.
I tag di apertura e quelli di chiusura vengono anche chiamati markup3.
Attraverso l’utilizzo dei tag si possono definire delle strutture dati di tipo gerar-
chico dove gli elementi sono costituiti da piu` elementi figli che a loro volta possono
essere costituiti da altri elementi, figli dei figli, e cos`ı via. Ad esempio in Figura 1.1
e` riportato un elemento <person> definito da 3 elementi figli <name>, <surname>
e <age>.
<person>
<name>Alan</name>
<surname>Turing</surname>
<age>42</age>
</person>
Figura 1.1: Esempio di elemento XML di tipo gerarchico
I tag possono essere di qualsiasi tipo e possono essere scelti liberamente da chi
realizza il documento XML a patto di rispettare alcune regole: devono iniziare con un
carattere o con un underscore ( ); non possono inziare con numeri; possono contenere
un qualsiasi numero di lettere, numeri, trattini, punti ed underscore; non possono
contenere spazi; sono case-sensitive quindi, ad esempio, <Name> e <name> sono
elementi differenti; conviene evitare di utilizzare tag riservati del linguaggio, come
ad esempio <xml>.
Gli elementi di un documento XML possono contenere anche degli attributi ossia
dei valori racchiusi tra apici o doppi apici definiti all’interno dello stesso tag del-
l’elemento, ad esempio <age unit=’years’>42</age> definisce l’attributo unit,
dell’elemento <age>, con valore pari a ’years’. Gli attributi vengono utilizzati per
definire proprieta` specifiche di un elemento, nell’esempio precedente l’attributo unit
specifica l’unita` di misura dell’eta` della persona, espressa in anni (years). I nomi
3
In questa tesi si utilizzera` la parola inglese markup al posto della sua traduzione italiana
marcatore.
7
degli attributi possono essere scelti liberamente a patto di rispettare le stesse regole
di nomenclatura dei tag viste in precedenza. Inoltre ogni attributo puo` comparire
una sola volta all’interno dello stesso tag, non e` quindi possibile avere un tag che pre-
senti due volte lo stesso attributo (questo per evitare ambiguita` in fase di lettura del
documento XML). Esistono degli attributi riservati che non possono essere utilizzati
liberamente ma solo con il significato che e` stato loro attribuito.
Alcuni di questi attributi riservati sono:
• xml:lang= it | en | . . . , indica la lingua del tag corrente;
• xml:space= preserve | default, indica se gli spazi del contenuto testuale del tag
devono essere considerati (preserve) oppure possono essere considerati superflui
(default).
• xml:attribute= ”. . .”: permette di rinominare gli attributi per evitare conflitti
in fase di lettura o di utilizzo di altre tecnologie XML.
Esistono poi alcuni caratteri che non possono essere inseriti come valori testuali
cos`ı come sono all’interno di un documento XML, ad esempio i caratteri < e > non
possono essere inseriti come valori poiche` verrebbero confusi con la definizione di un
elemento XML.
Per evitare questo possibile conflitto e` necessario utilizzate un codice, denominato
entity-name, al posto del carattere che si desidera inserire, ad esempio in Figura 1.2
sono riportati alcuni entity-name di alcuni caratteri particolari.
Entity-name Carattere
&amp; &
&lt; <
&gt; >
&quot; ”
&apos; ’
&#x??; Chr(??)
Figura 1.2: Alcuni entity-name XML.
L’ultimo entity-name della tabella di Figura 1.2 consente di rappresentare qual-
siasi caratteri a partire dal suo codice ASCII, espresso in esadecimale, al posto di
??.
8
In un documento XML possono essere inseriti dei commenti tramite il tag di
apertura <!- - e tramite il tag di chiusura - ->. In questo modo il testo compreso tra
<!- - e - -> non verra` considerato durante la lettura del documento XML.
Una regola fondamentale per la creazione di documenti XML e` quella relativa al
prologo (header) del documento. Ogni documento XML deve iniziare con il seguente
tag particolare:
<?xml version=”versione” enconding=”codifica” standalone=”yes/no”?>
Questo tag viene chiamato processing instruction e serve per indicare che si tratta
di un documento XML nella versione specificata, che utilizza la codifica specificata
e se ha o meno una definizione di struttura (standalone) autonoma o esterna.
Un’altra regola fondamentale e` quella dell’unicita` dell’elemento di primo livello;
ossia ogni documento XML deve avere un solo elemento che racchiude tutti gli altri
elementi XML.
1.3 Documenti XML ben formati
Un documento XML di dice ben formato (well formed) quando rispetta le re-
gole sintattiche definite in precedenza. Un documento XML deve essere ben for-
mato per poter essere utilizzato da un software che dovra` leggerlo ed interpretarlo4
correttamente. Ad esempio il seguente documento XML non e` ben formato:
<?xml version="1.0"?>
<person>
<Name>Alan</name>
<surname>Turing</surname>
<age 1unit="years">42</age>
</person>
poiche` il tag di apertura <Name> e` diverso dal tag di chiusura </name> ed ancora
perche` la definizione dell’attributo 1unit non puo` iniziare con un numero.
4
I software che leggono ed interpretano i documenti XML si dicono parser in quanto analizzano
pezzo per pezzo la struttura del documento.
9
1.4 Document Type Definition (DTD)
Fino a questo momento abbiamo parlato solo di sintassi XML e abbiamo visto
come realizzare un documento XML ben formato, ora discuteremo della possibilita`
di associare una struttura ad un documento XML e quindi in un certo senso della
possibilita` di associare una semantica ad un documento XML.
Il processo con il quale viene verificata la correttezza sintattica (leggibilita`) e la
correttezza strutturale di un documento XML viene denominato validazione.
Per definire la struttura di un documento XML si possono utilizzare fondamen-
talmente due tecniche:
• DTD (Document Type Definition) si tratta della prima tecnologia utilizzata
per definire la struttura di un documento XML. E’ supportata praticamente
da tutti i parser XML.
• XSD (Xml Schema Definition) e` una raccomandazione del 2001 del W3C che
rappresenta ormai uno standard per la validazione XML. Tutti i produttori di
parser si stanno orientando verso questo tipo di tecnologia.
In questa tesi discuteremo solo dello standard DTD analizzando soltanto un sot-
toinsieme della sua sintassi anche perche` il processo di validazione di un documento
XML e` secondario rispetto alle finalita` della tesi.
Le DTD possono essere di due tipi:
• Pubbliche: disponibili liberamente e consultabili da chiunque. Su Internet si
possono trovare degli archivi (repository) contenenti DTD standard, ad esempio
HTML e` definito tramite DTD pubbliche depositate presso il W3C.
• Di sistema: riservate. Sono riservate solo per un utilizzo interno del sistema e
non possono essere consultate liberamente.
Per poter associare uno schema DTD ad un documento XML si possono utiliz-
zare due alternative: possiamo inserire la DTD come parte integrante del documen-
to (DTD interna) oppure possiamo utilizzare una definizione esterna, di sistema o
pubblica (DTD esterna).
Nel caso di DTD interna la sintassi da utilizzare e` la seguente:
10
<?xml version="1.0" ... ?>
<!DOCTYPE nome [contenuto della DTD]>
Nel caso di DTD esterna di sistema la sintassi risulta essere:
<?xml version="1.0" ... ?>
<!DOCTYPE nome SYSTEM "URL del file DTD">
e nel caso di DTD esterna pubblica:
<?xml version="1.0" ... ?>
<!DOCTYPE nome PUBLIC "URL del file DTD">
Con uno schema DTD e` possibile definire la struttura di un documento XML a
partire dalla composizione degli elementi e degli attributi. Per definire la struttura
di un elemento XML all’interno di una DTD e` necessario utilizzare la parola chiave
ELEMENT attraverso il seguente tag:
<!ELEMENT nome regola_DTD>
dove nome e` il nome dell’elemento XML (il tag), la regola DTD indica invece il tipo
di contenuto che questo tag avra` ed eventualmente la sua relazione con altri contenuti
descritti nella DTD. I valori che possono essere assegnati ad una regola DTD sono:
• ANY: indica che il contenuto del tag e` libero.
• PCDATA (Parsed Character Data): indica che il contenuto e` solo ed unica-
mente di tipo testo.
• EMPTY: indica che il tag sara` costituito solo da attributi e non conterra` altri
elementi al suo interno.
• Gruppi di elementi: indica che l’elemento e` costituito da altri elementi.
Prima di procedere oltre con la definizione della sintassi DTD analizziamo il
seguente documento XML che rappresenta una semplice base dati di una banca
definita attraverso una DTD di sistema memorizzata nel file bank.dtd:
11
<?xml version="1.0"?>
<!DOCTYPE bank SYSTEM "bank.dtd">
<bank>
<customer customer-id="C1" accounts="A1 A2" type="old">
<name>Alan</name>
<surname>Turing</surname>
</customer>
<customer customer-id="C2" accounts="A2" type="new">
<name>Isaac</name>
<surname>Newton</surname>
</customer>
<account account-number="A1" owners="C1">
<branch-name>Londra</branch-name>
<balance>1500</balance>
</account>
<account account-number="A2" owners="C1 C2">
<branch-name>Cambridge</branch-name>
<balance>2500</balance>
</account>
</bank>
Ad esempio una possibile definizione DTD dell’elemento name puo` essere:
<!ELEMENT name (#PCDATA)>
Come ad esempio una possibile definizione DTD dell’elemento customer:
<!ELEMENT customer (name,surname)>
12
In quest’ultimo caso definiamo l’elemento customer composto dagli elementi name
e surname.
Nella definizione di gruppi di elementi puo` essere utilizzato il carattere | per indi-
care un’alternativa, ad esempio la definizione <!ELEMENT customer (name | surname)>
indica che l’elemento customer puo` essere costituito da un elemento name o da un
elemento surname ma non da entrambi o da nessuno dei due.
Qualora sia necessario indicare una molteplicita` di elementi si possono utilizzare
i seguenti simboli:
• ? che indica zero o 1;
• + che indica da 1 a infinite volte;
• * che indica da zero a infinite volte.
Ad esempio per indicare che l’elemento bank e` costituito da un numero arbi-
trario, eventualmente nullo, di elementi customer ed account si utilizza la seguente
definizione DTD:
<!ELEMENT bank (customer*, account*)>
Fino a questo momento abbiamo visto come definire la struttura di un elemento
XML ora analizziamo della definizione della struttura degli attributi.
Per poter definire la struttura di un attributo e` necessario utilizzare la seguente
sintassi DTD:
<!ATTLIST elemento nome_attributo tipo valore_default>
dove elemento e` il nome del tag del quale stiamo definendo l’attributo, il nome attributo
e` l’attributo, tipo e` la specifica della definizione del tipo di attributo e valore default
e` l’eventuale valore predefinito.
In Figura 1.3 sono riportati alcuni tipi di attributi che possono essere specificati
all’interno di una definizione DTD.
13