Alma Mater Studiorum · Università di Bologna
FACOLTÀ DI SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di Laurea Triennale in Informatica
Assegnamento di tipi condizionali
in XSDL 1.1: tecniche di verifica statica
della corretta derivazione di tipi
Tesi di Laurea in Tecnologie Web/Internet
Relatore:
Chiar.mo Prof.
FABIO VITALI
Presentata da:
MAURIZIO CASIMIRRI
Correlatore:
Dott.
PAOLO MARINELLI
Sessione III
Anno Accademico 2006/2007
Indice
1 Introduzione
5
2 XSDL 1.1 e Conditional Type Assignment
2.1
2.2
13
Co-occurrence constraint . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1
Classificazione dei co-constraint . . . . . . . . . . . . . . . . . 14
2.1.2
Importanza dei co-constraint . . . . . . . . . . . . . . . . . . . 16
2.1.3
Supporto ai co-constraint nei linguaggi di validazione . . . . . 17
Supporto ai co-constraint in XSDL 1.1 . . . . . . . . . . . . . . . . . 18
2.2.1
Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2
Conditional Type Assignment . . . . . . . . . . . . . . . . . . 20
3 Verifica statica dei vincoli di restrizione con CTA
25
3.1
CTA e restrizione di tipi complessi . . . . . . . . . . . . . . . . . . . 25
3.2
Tecniche per la verifica dei vincoli di restrizione . . . . . . . . . . . . 27
3.3
3.2.1
Prefix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2
Vincolare il numero delle alternative . . . . . . . . . . . . . . 31
3.2.3
Run-time Checking . . . . . . . . . . . . . . . . . . . . . . . . 31
Prodotto Cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.1
Normalizzazione delle type table . . . . . . . . . . . . . . . . . 42
3.3.2
Prodotto Cartesiano con type table normalizzate . . . . . . . . 44
3.3.3
Confronto con Run-Time Checking . . . . . . . . . . . . . . . 47
4 Implementazione
4.1
Xerces e XML Schema API . . . . . . . . . . . . . . . . . . . . . . . 50
4.1.1
4.2
49
XSModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Architettura globale
. . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.1
Visita generica del XSModel . . . . . . . . . . . . . . . . . . . 53
4.2.2
Gerarchia dei tipi . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.3
XNI e SchemaPreprocessor . . . . . . . . . . . . . . . . . . . 55
3
4
INDICE
4.3
4.4
4.5
4.2.4 Semplificazione degli XPath
Prodotto Cartesiano . . . . . . . .
Test . . . . . . . . . . . . . . . . .
4.4.1 Parser e validatore di test .
4.4.2 Integrazione in SchemaPath
4.4.3 TestSuite . . . . . . . . . .
Limitazioni . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
57
57
59
59
59
59
61
5 Conclusioni
63
5.1 Sviluppi futuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Capitolo 1
Introduzione
L’introduzione dell’assegnamento condizionale del tipo (Conditional Type Assignment o CTA) in XML Schema 1.1 porta con sè il problema della verifica della
corretta restrizione dei tipi complessi che fanno uso di questo meccanismo. Nelle
specifiche è suggerita, ma non imposta, una tecnica per effettuare tale controllo in
fase di validazione. In questa tesi sarà mostrato che è possibile risolvere il problema
attraverso un approccio parzialmente statico, ossia in parte a tempo di compilazione
dello schema ed in parte a tempo di validazione delle istanze.
L’assegnamento di tipo condizionale è un meccanismo che consente di decidere il
tipo di un elemento sulla base della valutazione di condizioni XPath. Le regole che
CTA consente di esprimere appartengono alla classe dei co-constraint, ovvero vincoli
incrociati sulla presenza o sul valore dei nodi di un documento.
Nella strutturazione e validazione di dati machine understandable, non poter esprimere una vasta categoria di vincoli come i co-constraint significa escluderne il controllo dal processo di validazione, richiedendo che tali controlli siano effettuati da
componenti apposite, ed impedendo di specificare in modo formale i requisiti del
sistema sui dati. Questo può portare ad un indebolimento dell’interoperabilità tra
le componenti dei sistemi stessi.
CTA risponde alla necessità di estendere XML Schema per il supporto dei coconstraint, consentendo specificare in modo esaustivo le regole di composizione dei
documenti.
Attraverso XML è possibile marcare i documenti con meta-informazioni sul contentuto. Gli autori di documenti XML possono scegliere il markup da utilizzare per
imporre loro una struttura logica. I linguaggi di schema permettono di descrivere, in
maniera formale, classi di documenti XML. Attraverso il loro uso è possibile definire
una struttura specifica per i linguaggi di markup basati su sintassi XML, ed effet5
6
1. Introduzione
tuare controlli sulla correttezza delle loro istanze. Il loro impiego è fondamentale in
ogni campo applicativo che coinvolge l’uso di XML.
Un linguaggio di schema permette di definire regole secondo le quali un documento XML appartiene ad una particolare categoria. Nello specifico essi consentono la
descrizione di regole, prevalentemente sulla struttura, che un documento deve rispettare affinchè sia valido.
Una importante categoria di restrizioni è rappresentata dai co-constraint. I coconstraint sono vincoli incrociati sull’occorrenza dei nodi all’interno di un documento
XML. Per mezzo di essi è possibile, ad esempio, imporre che un documento contenga
uno specifico elemento solo in presenza di un attributo con un valore particolare.
I co-constraint dunque sono vincoli sulla struttura o sul contenuto di un documento
in dipendenza del contesto. La categoria dei co-constraint è molto ampia. Tuttavia
possiamo identificare alcune tipologie principali.
Una prima importante tipologia di co-constraint è costituita dai vincoli incrociati
sul contenuto di attributi o di elementi, ovvero le regole del tipo: se l’attributo x ha
valore y allora l’elmento <e> deve contenere un figlio <f>. Inoltre sono co-constraint
anche i vincoli di mutua dipendenza tra nodi, ad esempio: se è presente l’attributo link l’elemento <content> non deve avere figli. Infine possiamo identificare
una terza categoria fondamentale di co-constraint tra quelli che vincolano il dominio di elementi o attributi al valore di altri nodi. Un semplice esempio è il seguente:
il valore dell’attributo min non deve essere mai superiore al valore dell’attributo max.
Per avere un’idea di quanto siano importanti i co-constraint nella descrizione di
linguaggi basati su sintassi XML basta prendere in esame alcuni linguaggi molto
diffusi. Tra le loro regole di validità troviamo numerose restrizioni sul contenuto
che fanno riferimento alla categoria dei co-constraint. In XHTML ad esempio non è
possibile annidare gli elementi <a>, mentre in XSLT è imposto che in un elemento
<template> compaia almeno uno tra gli attributi match o name.
XML Schema 1.0 è l’unico linguaggio di validazione ad aver raggiunto lo stadio
di W3C Recommendation, la fase finale di una ratifica del W3C. Nonostante il suo
largo impiego, in XML Schema non è possibile esprimere i co-constraint. Per dare
una breve idea di quanto questa carenza ne limiti l’espressività basta pensare che
lo schema per XML Schema non è completamente descrivibile nel linguaggio stesso.
I sistemi che necessitano di co-constraint dunque devono ricorrere alla validazione
7
attraverso linguaggi differenti, ad esempio Schematron, o effettuare controlli all’interno di componenti software specifiche.
Il supporto ai co-constraint è stato introdotto in XSDL 1.1 attraverso i meccanismi
di Assertions e Conditional Type Assignment(CTA) e l’ampliamento del linguaggio
con i relativi costrutti. Questi nuovi meccanismi fanno uso di predicati XPath per
identificare i nodi su cui i vincoli sono espressi.
Le asserzioni sono costrutti comuni nell’ambito dei linguaggi di programmazione.
Un’asserzione è un controllo sul flusso dell’esecuzione che assicura il soddisfacimento di determinate condizioni in un preciso punto del programma. Il fallimento di
un’asserzione è indice di un comportamento scorretto. In maniera analoga le asserzioni in XSDL 1.1 specificano quali condizioni debbano soddisfare gli elementi
dichiarati nel content model di un tipo complesso affinchè essi siano validi.
CTA è progettato sulla base di SchemaPath, un’estensione di XSDL 1.0 creata appositamente per fornire supporto ai co-constraint. Allo stesso modo infatti provvede
una sintassi ampliata per le dichiarazioni di elemento, consentendo di specificare il
tipo degli elementi in dipendenza dal contesto del documento d’istanza. In particolare il tipo dell’elemento può essere assegnato in base al verificarsi di predicati
XPath. Ogni dichiarazione di elemento dunque può possedere una type table, ossia
una sequenza di coppie, predicato-tipo, in base alla quale viene assegnato a tempo
di validazione il tipo per i corrispettivi elementi. Una delle caratteristiche di CTA è
che rispetta i principi di modularità ed estendibilità dello schema. In particolare è
possibile derivare da tipi che racchiudono dichiarazioni di elemento condizionali.
A questo proposito, come accennato, l’introduzione di CTA porta con sè alcuni
interrogativi circa le relazioni di restrizione in presenza di assegnamento di tipi condizionale. Dal momento che l’assegnamento dei tipi non è più univoco si possono
infatti verificare situazioni al momento della validazione per cui il tipo condizionale
da assegnare ad un elemento non sia una valida restrizione del corrispettivo tipo per
la dichiarazione nella base o in un tipo antenato.
Si pongono nello specifico due problemi: decidere se uno schema che permette di
violare a run-time i vincoli di restrizione possa essere considerato valido, e decidere
in che modo possa essere verificata la validità altrimenti.
Nel corso della stesura del draft di XSDL 1.1 sono state discusse diverse soluzioni,
8
1. Introduzione
che potremmo identificare sostanzialmente in due tipologie. Un primo insieme di
proposte riguarda l’imposizione di vincoli sintattici al fine di impedire la scrittura di
schemi potenzialmente scorretti. Praticamente tutte queste soluzioni però limitano
l’espressività di CTA restringendone lo spettro di applicabilità. Una seconda categoria di proposte al contrario non impone vincoli a CTA, e mira a rilevare la totalità
delle situazioni erronee sia in fase statica di compilazione dello schema, che in fase
dinamica.
Tra le soluzioni del primo tipo Prefix è particolarmente interessante. Questa, sebbene imponga limitazioni sull’uso di CTA, si propone come valido compromesso tra
espressività e decidibilità statica dei vincoli di restrizione. Sostanzialmente prefix
richiede che la type table di una dichiarazione di elemento sia ripetuta all’inizio delle
type table delle dichiarazioni di elemento che compaiono nei content model ristretti. Sono stati individuati, tuttavia, diversi casi d’uso che non sono contemplati da
questa tecnica, e per questo non è stata presa in considerazione come soluzione adottabile.
Tra le soluzioni che non impongono alcuna restrizione è necessario distinguere ancora
tra soluzioni completamente statiche, completamente dinamiche ed ibride. Sebbene
siano state avanzate alcune proposte di verifica completamente statica, fino ad ora
non sono state individuate tecniche di verifica attuabili1 . Trascuriamo dunque tali
proposte per analizzare una tecnica completamente dinamica nota come Run-Time
Check ed una tecnica ibrida, considerata e ampliata in questa tesi, nota come Prodotto Cartesiano.
Run-Time Check (RTC) consiste nella verifica delle relazioni di restrizione a tempo
di validazione. In particolare per ogni elemento si determina il tipo in dipendenza
dal contesto sia per la dichiarazione effettivamente utilizzata che per le dichiarazioni
racchiuse nei tipi antenati nella gerarchia di restrizione. Su di essi vengono dunque
effettuati i controlli di corretta restrizione.
Un limite osservabile per tale tecnica è che, poichè le relazioni di restrizione sono
proprietà dello schema, è poco conveniente verificare tali relazioni man mano che si
processono gli elementi del documento di istanza.
Su questo assunto si basano le motivazioni del Prodotto Cartesiano (PC). Secondo
questa tecnica la corretta restrizione è controllata in fase statica, enumerando tutte
le possibili situazioni che si possono verificare a run-time attraverso un’analisi delle
1
Queste tecniche infatti dovrebbero preoccuparsi di fare inferenza sulle espressioni XPath
9
type table. I risultati ottenuti in fase statica sono utilizzati dal validatore per assegnare i tipi. Sostanzialmente il PC lavora in fase di compilazione per costruire nuove
type table, in funzione di quelle scritte nello schema, che causano l’assegnamento del
tipo built-in xs:error 2 in presenza di violazione dei vincoli di restrizione.
Il PC ha un costo computazionale proporzionale al prodotto delle type table presenti
in una catena di derivazione, e dunque si propone non come soluzione generale del
problema, ma come tecnica prioritaria sul Run-time Check che permette, per catene
di derivazione di tipi ragionevolmente contenute, l’anticipare e il raccogliere la verifica delle restrizioni per ogni elemento dei documenti d’istanza.
Al fine di ridurre il costo computazionale dell’algoritmo è stata formulata una variante del PC che sfrutta alcune proprietà di equivalenza semantica delle type table. In
particolare si basa su una tecnica, che chiameremo normalizzazione delle type table,
e che consiste nel fondere alcune righe di una type table ottenendone una seconda,
semanticamente equivalente, ma di dimensioni ridotte.
A scopo dimostrativo è stato realizzato dunque un prototipo dell’algoritmo che realizza la tecnica del PC. Dal momento che questa tecnica ha senso soltanto nell’ambito
della validazione, si è resa necessaria l’integrazione dell’algoritmo all’interno di un
validatore esistente. La scelta a tale proposito è caduta su una versione di Xerces,
parser open source, precendentemente modificata per ospitare un validatore SchemaPath.
Per prima cosa è stato adattato il meccanismo di parsing dello schema alla sintassi
di CTA. Per fare questo è stato esteso il modello per le XML Schema API di Xerces
con le interfacce relative alle Schema Component di CTA. Parallelamente sono stati
realizzati ed integrati meccanismi relativi al controllo di vincoli di correttezza dello
schema rispetto alle componenti introdotte. In secondo luogo è stata progettata una
API per utilizzare in modo flessibile il Prodotto Cartesiano all’interno di differenti
validatori, prestando particolare attenzione alla modularità dei meccanismi e a preservare quanto più codice possibile dalla interfaccia nativa di Xerces, in modo da
agevolare futuri aggiornamenti.
I test del prototipo sono organizzati in una testsuite sul modello di quella usata
per XML Schema. É stata creata dunque una serie di schemi e istanze, sia valide
che non valide, in modo da testare il comportamento dei validatori su di esse.
2
xs:error è un tipo introdotto in XSDL 1.1 e non è soddisfatto da nessun valore
10
1. Introduzione
Nel capitolo 2 sarà introdotto il contesto in cui si sviluppa il problema affrontato. In
particolare in sez. 2.1 saranno introdotti i co-constraints, dandone una definizione,
mostrando alcuni casi d’uso interessanti, e discutendo della loro importanza.
Sarà dunque affrontato il loro supporto in XDSL 1.1 in sez. 2.2, dove saranno descritti in dettaglio sia Assertions che Conditional Type Assignment.
Nel capitolo 3 invece affronteremo il problema della restrizione tra tipi in presenza di
CTA. In sez. 3.1 illustreremo brevemente il problema, anche attraverso un esempio.
In sez. 3.2 parleremo delle proposte di soluzione a questo problema, in particolare
in 3.2.1 illustreremo Prefix, mostrandone le caratteristiche e un caso d’uso per cui
non è possibile definire uno schema mediante il suo impiego. In sez. 3.2.3 sarà invece
spiegata dettagliatamente la tecnica di Run-time Checking, fornendo un algoritmo
in pseudo-codice e discutendo il suo costo computazionale.
Nella sezione 3.3 invece introdurremo il Prodotto Cartesiano la soluzione proposta in questa tesi. Sarà dunque mostrato in dettaglio il procedimento di analisi delle
type table e di costruzione delle nuove type table. Mostreremo quindi un esempio e
forniremo un algoritmo in pseudo-codice per la realizzazione di questa tecnica. Effettueremo quindi un’analisi del suo costo computazionale in fase statica e del costo
relativo alla fase dinamica di assegnamento dei tipi.
In sez. 3.3.1 mostreremo alcune proprietà delle type table. In particolare daremo una
definizione di type table deterministica e type table normalizzata. In sez. 3.3.2 mostreremo dunque una variante del PC che si basa su queste proprietà. Daremo quindi
anche in questo caso un algoritmo e un analisi del suo costo, sia in fase statica che
dinamica.
In sezione 3.3.3 effettueremo una comparazione degli algoritmi, evidenziando, in base alla dimensione dell’input, quali sono i casi in cui una soluzione è più conveniente
dell’altra.
Nel capitolo 4 illustreremo dunque il prototipo. In sez. 4.1 saranno descritte molto
brevemente le XML Schema API e la loro implementazione all’interno di Xerces.
Inoltre in questa sezione mostreremo anche quali cambiamenti sulle API di Xerces si
sono resi necessari e come sono stati effettuati per introdurre le componenti di CTA
nel modello esistente.
In sez. 4.2 sarà illustrata in dettaglio l’API proposta per il prototipo. Saranno quindi
11
descritte e motivate tutte le scelte progettuali, accompagnate da esempi d’uso.
In sez. 4.4 sarà mostrata la testsuite realizzata, descrivendo brevemente i test effettuati. Nel capitolo 5 infine riassumeremo quanto mostrato ed effettueremo alcune
considerazioni finali, inoltre in sez. 5.1 mostreremo in che direzione potrebbe essere
sviluppato questo lavoro.
Capitolo 2
XSDL 1.1 e Conditional Type
Assignment
In questo capitolo saranno affrontate le problematiche relative all’introduzione del
supporto per co-constraint in XML Schema Definition Language (XSDL 1.1)[GSMT07],
evidenziandone la necessità e discutendo le soluzioni adottate. Saranno introdotti
quindi alcuni concetti generali riguardanti i Co-constraint. In seguito sarà discussa
la loro importanza e il loro supporto nei linguaggi di schema ed infine sarà dedicata
una sezione ai meccanismi che ne forniscono il supporto in XSDL 1.1.
2.1
Co-occurrence constraint
Con il termine schema XML ci si riferisce in generale ad una descrizione formale
della struttura logica di una classe di documenti XML. In particolare uno schema
definisce un vocabolario di elementi ed attributi e stabilisce in che modo essi debbano apparire nei documenti d’istanza. Per fare ciò impone una serie di restrizioni
sul contenuto dei documenti stessi.
Un sottoinsieme importante di tali restrizioni è costituito dai Co-occurrence costraints (anche detti: “co-constraint”): regole che decidono quali tipi di markup (elementi
o attributi) possono occorrere insieme all’interno di un documento XML [SM06b].
Dei co-constraint fanno parte dunque quelle regole che specificano le relazioni di
occorrenza reciproca tra le parti di un documento. In generale questi vincoli sono
dipendenti dal contesto. Ad esempio essi sono usati per stabilire che in un elemento non compaia un attributo x se è presente l’attributo y, oppure per imporre la
struttura dei figli di un elemento in base al valore di un attributo.
13
14
2. XSDL 1.1 e Conditional Type Assignment
2.1.1
Classificazione dei co-constraint
La classe dei co-constraint è molto ampia ed al suo interno è possibile individuare
diversi sottoinsiemi di vincoli con caratteristiche comuni. Esistono catalogazioni più
o meno specifiche per quanto riguarda le tipologie di co-constraint. Di seguito sarà
illustrata una ristretta serie di casi a scopo esemplificativo. Per una classificazione
più esaustiva si consiglia di consultare [SM06a] o [Zin07].
Vincoli incrociati sul contenuto
Appartengono a questa categoria i vincoli che esprimono restrizioni sul contenuto
di un elemento in base al valore o alla presenza di un attributo o di un altro elemento. Si consideri ad esempio il frammento XML in figura 2.1, supponendo che il
relativo schema definisca una grammatica per descrivere una base di dati di fonti
bibligrafiche. L’elemento <entry> corrisponde ad una fonte bibliografica. Nel caso in
cui la fonte sia una pagina web è lecito aspettarsi che l’URL relativa venga sempre
esplicitata. All’interno dello schema potremmo dunque esprimere questo requisito
mediante un co-constraint del tipo: se l’attributo kind ha valore web-page l’elemento <entry> deve contenere l’elemento <url>.
In questo caso quindi la presenza di un elemento (<url>) sarebbe vincolata al valore
di un attributo (kind). In generale i co-constraint di questo genere sono necessari
quando è richiesto che il contenuto di un elemento sia legato al contenuto di altri
attributi o elementi, imponendo ad esso un content model differente a seconda del
contesto.
Vincoli di mutua dipendenza
Si ha un vincolo di mutua dipendenza quando a seconda della presenza di un componente (attributo od elemento) vengono decise restrizioni su un altro componente,
che può diventare richiesto, non ammesso od opzionale. Nell’esempio in figura 2.1
l’ultimo elemento <entry> rappresenta un articolo appartenente ad una rivista e
sono indicate dall’elemento <pages> anche le pagine in cui esso compare. Nel caso
in cui non venga citato il nome della rivista è insensato che compaia un range delle
sue pagine. Questa restrizione può essere espressa attraverso un vincolo di mutua
dipendenza: la presenza dell’elemento <pages> è opzionale se è presente l’elemento
<journal> e proibita viceversa.
2.1 Co-occurrence constraint
<bibliography>
<entry kind="book" key="e1">
<author>Name</author>
<title>My book</title>
</entry>
<entry kind="web-page" key="e2">
<author>Name</author>
<title>my page</title>
<url>www.example.org/webpage</url>
</entry>
<entry kind="article">
<author>Name</author>
<title>My article</title>
<journal>My journal</journal>
<pages from="50" to="61"/>
</entry>
</bibliography>
Figura 2.1: Un documento XML che descrive una piccola bibliografia.
15
16
2. XSDL 1.1 e Conditional Type Assignment
Vincoli incrociati sul dominio di attributi ed elementi
Sempre considerando l’esempio in figura 2.1, affinchè il range delle pagine sia significativo, è richiesto che il numero della pagina iniziale sia inferiore o uguale a quello
della pagina finale. Anche questo vincolo sul dominio aritmetico delle pagine appartiene alla categoria dei co-costraints. Le restrizioni di dominio sono molto comuni
e possono coinvolgere sia attributi che elementi. Inoltre il rapporto tra i valori può
essere meno banale di quello portato ad esempio. In generale i vincoli di dominio
consentono di governare il dominio dei valori di un attributo o elemento sul valore o
sulla presenza di altri attributi o elementi; ad esempio si potrebbe voler controllare
che il valore di un attributo sia uguale alla somma dei valori di alcuni elementi che
compaiono nel documento.
2.1.2
Importanza dei co-constraint
La semplicità degli esempi proposti in sez. 2.1.1 dà un’idea di come le situazioni
che rientrano tra i casi d’uso dei co-costraint siano del tutto comuni. I co-constraint
hanno un campo di applicabilità vastissimo. Per mostrare la loro rilevanza pratica
faremo dunque riferimento ad alcune restrizioni relative a tre linguaggi molto noti
basati su sintassi XML.
Annidamento degli elementi <a> in XHTML
In XHTML[ea02] l’elemento <a> definisce un collegamento ipertestuale (o hyperlink ) che lega una parte del documento ad una unità esterna o ad un’altra sezione
del documento stesso. In particolare qualsiasi parte di un documento può essere legata mediante un hyperlink. Per questo il contenuto dell’elemento <a> è definito in
maniera libera, ovvero esso può contenere un qualsiasi altro frammento XHTML.
Tuttavia la stessa porzione di documento non può fare riferimento a più di un collegamento ipertestuale. Per evitare ciò le specifiche prevedono che un elemento <a>
non possa essere annidato all’interno di un altro elemento <a>. Questa restrizione
rappresenta effettivamente un co-constraint.
Named templates in XSLT
XSLT(Extensible Stylesheet Language Transformations)[Kay07] prevede due tipi di
dichiarazione di template: per nome (named templates) e per predicato. Il corrispettivo elemento <template> denota l’una o l’altra tipologia a seconda che presenti l’attributo name o l’attributo match. In base alla specifica un elemento <template> deve
2.1 Co-occurrence constraint
contenere almeno uno dei due attributi. Siamo dunque in presenza di un co-constraint
di mutua dipendenza.
Elementi in XML Schema
I requisiti sintattici di XML Schema[TBMM04] presentano molti vincoli che appartengono alla categoria dei co-constraint. Un esempio particolarmente significativo
è dato dalla seguente regola per le dichiarazioni di elemento: un <element> deve
contenere un attributo name e può contenere o un elemento tra <complexType> e
<simpleType> oppure un attributo type. Un <element> locale inoltre può anche
avere un attributo ref, in qual caso non possono apparire né l’attributo name, né
l’attributo type e non possono apparire nemmeno gli elementi <complexType> e
<simpleType>. É evidente che tutte queste restrizioni rispondono alla definizione di
vincoli di co-occorrenza. Il contenuto di <element> è di fatti vincolato sia alla presenza dell’attributo ref che a quella dell’attributo type. Inoltre anche la presenza
di ref rende proibita la presenza di name che viceversa sarebbe obbligatoria.
2.1.3
Supporto ai co-constraint nei linguaggi di validazione
Un linguaggio di validazione è un formalismo mediante il quale è possibile esprimere schemi XML. In particolare possiamo distinguere due tipologie di linguaggi di
validazione:
• linguaggi basati su grammatica, in cui lo schema descrive una grammatica
libera dal contesto come regole di produzione espresse in uno specifico formalismo. Rientrano in questa tipologia XML Schema, Relax NG [CM01] e DTD
[BPSM+ 06].
• linguaggi basati su regole, in cui lo schema racchiude una lista dei predicati
che discrimineranno la correttezza del documento alla validazione. Rientrano
in questa tipologia Schematron [Jel02] e xlinkit [NCEF02].
I linguaggi basati su grammatica sono adatti per natura a descrivere la struttura
logica del documento, e molti di essi consentono di esprimere vincoli, anche sofisticati, sul valore dei nodi. Tuttavia il supporto ai co-constraint è quasi sempre
limitato, qualora non assente: né XML Schema né DTD possiedono costrutti adatti
ad esprimerli. Ciò è probabilmente dovuto alla natura dei formalismi stessi, basati
solitamente sulla descrizione di produzioni grammaticali, che non si prestano facilmente a rappresentare i vincoli di co-occorrenza. Al contrario i linguaggi basati su
regole sono ideali per esprimere co-constraint: di fatto sia Schematron che xlinkit li
17
18
2. XSDL 1.1 e Conditional Type Assignment
supportano pienamente.
Il mancato supporto ai co-constraint in XML Schema 1.0 è chiaramente avvertito
nell’ambito delle tecnologie web. Per nessuna delle situazioni precedentemente esposte (vedi sez. 2.1.1 e 2.1.2) è possibile esprimere una soluzione in XML Schema 1.0,
inoltre è interessante notare come non sia nemmeno possibile descrivere uno schema
XML per XML Schema 1.0 nel linguaggio stesso.
Tuttavia non è corretto affermare che in XML Schema non sia possibile definire
alcun co-constraint. In particolare esitono i cosiddetti identity constraint definition,
ossia costrutti che consentono la definizione di vincoli di identità referenziale sugli
elementi di un documento. Gli identity constraint sono pensati per fornire vincoli
sugli elementi similari a quelli definibili sulle tuple di una base di dati. Ad esempio
essi consentono di imporre che non compaiano due elementi nel documento il cui
attributo name abbia lo stesso valore. Sebbene tali vincoli rientrino in effetti nella
categoria dei co-constraint, essi ne rappresentano solo una minima parte e sono insufficienti nella maggioranza delle situazioni.
La mancanza di costrutti specifici per co-constraint all’interno di XML Schema è
causa di diversi problemi tutt’altro che teorici. L’uso di XML Schema è diffuso in modo particolare per la strutturazione e la validazione di dati machine understandable.
Spesso in questi casi la validità del documento è un parametro critico per assicurare
il corretto funzionamento delle applicazioni. Non poter esprimere una vasta categoria di vincoli come i co-constraint significa escluderne il controllo dal processo di
validazione, indebolendo l’interoperabilità nello scambio dei dati dal momento che
non è possibile specificare per intero i requisiti del sistema.
2.2
Supporto ai co-constraint in XSDL 1.1
XML Schema Definition Language 1.1, attualmente Working Draft del W3C, è presentato come estensione conservativa di XML Schema 1.0. Tra le sue caratteristiche
principali si colloca sicuramente l’introduzione del supporto ai co-constraint. Abbiamo già mostrato in sez. 2.1 quanto siano comuni i casi che richiedono l’impiego
di co-constraint ed accennato alla mancanza di costrutti adeguati per esprimerli in
XML Schema 1.0. Tale carenza è colmata in XSDL 1.1 attraverso l’introduzione di
due meccanismi fondamentali: Assertions e Condidional Type Assignment(CTA).
2.2 Supporto ai co-constraint in XSDL 1.1
2.2.1
Assertions
Il meccanismo delle assertions (asserzioni) in XSDL 1.1 ricalca per molti versi quello
adottato in Schematron. In particolare una assertion ha il medesimo significato
funzionale: esprimere un vincolo attraverso un predicato XPath[BBC+ 07] che deve
risultare sempre vero affinchè il documento sia valido. La schema component cui è
delegata la realizzazione del meccanismo per le asserzioni è molto semplice e dispone
solo delle due seguenti proprietà:
• annotations, una sequenza di annotazioni
• test, una espressione XPath 2.0
Per rappresentare in sintassi XML questa componente è stato introdotto l’elemento
‘<assert>’, che ha un attributo test il cui valore deve essere un’espressione XPath.
A differenza di quanto avviene in Schematron assert non permette di specificare
alcun tipo di messaggistica di errore da parte dell’utente. Inoltre Schematron associa
le asserzioni ad elementi, in XSDL 1.1 le asserzioni sono associate invece ai tipi.
L’elemento <assert> infatti può comparire solo alla fine della dichiarazione di un
Complex Type e pertanto sarà legato a run-time agli elementi d’istanza cui esso verrà
assegnato. La regola di validazione della assertion schema component è dunque la
seguente: un’elemento d’istanza è valido localmente rispetto ad una assertion se il
predicato XPath relativo alla proprietà test è valutato a true.
Consideriamo l’esempio in fig. 2.1, il vincolo sul dominio delle pagine può essere
espresso in XSDL 1.1 specificando il content model di <pages> nel modo seguente:
<xs:complexType>
<xs:attribute name="from" type="xs:integer"/>
<xs:attribute name="to" type="xs:integer"/>
<xs:assert test="@from <= @to"/>
</xs:complexType>
Restrizioni sulle espressioni XPath
Le espressioni XPath lecite per Assertions sono solo un sottinsieme di quelle consentite dal linguaggio. Per comprendere il motivo di questa scelta bisogna fare una
considerazione circa le conseguenze dovute alla verifica di co-constraint su tutto il
documento. Questa pratica difatti influisce sulla politica di validazione dei documenti d’istanza.
XML Schema è progettato in modo da consentire la validazione in streaming di documenti, solitamente necessaria con documenti di grandi dimensioni e di cui non si
19
20
2. XSDL 1.1 e Conditional Type Assignment
dispone per intero nell’arco della validazione. In particolare la validazione in streaming è effettuata sulla base degli eventi prodotti da un parser SAX. Per agevolare
questo tipo di validazione in Schema si adotta una politica secondo cui allo start
element si possa ricavare il tipo di ogni elemento d’istanza e all’end element se ne
conosca la validità. Tale principio è esposto in [MVZ07] ed è identificato con l’acronimo STEVE (Start tag: Type; End tag: Validity Evaluation).
In base a tale principio e al fatto che una assertion è vincolata ad un elemento e
al contenuto specificato dal suo tipo, l’espressione XPath associata alle assertion
ammette solo gli assi attribute, child e descendant. In questo modo la validità
dell’elemento sarà subito disponibile all’end element.
2.2.2
Conditional Type Assignment
Il meccanismo del Conditional Type Assignment (CTA) estende le dichiarazioni di
elemento di XSDL 1.0, permettendo l’assegnamento di tipi in base alla valutazione
di condizioni XPath. In particolare consente di vincolare il tipo di un elemento nel
documento d’istanza in funzione del valore o della presenza di uno o più attributi ad esso locali. Il meccanismo di CTA si basa dichiaratamente sulla soluzione per
l’assegnamento di tipi condizionali di SchemaPath[CMV04], ricalcandone con alcune
differenze i costrutti e le regole di validazione.
In XSDL 1.1 ad ogni dichiarazione di elemento è associata una type table, ossia una
tabella le cui righe sono coppie di predicati XPath e dichiarazioni di tipo. Ogni
entry nella type table corrisponde ad un possibile tipo che l’elemento d’istanza potrà assumere in base al contesto. A livello sintattico la specifica XSDL per quanto
riguarda CTA introduce un nuovo elemento: alternative, corrispondente ad una
precisa schema component riferita nella specifica con il nome di type alternative.
Una type alternative lega appunto un’espressione XPath ad una dichiarazione di
tipo. Ad essa dunque appartengono le seguenti proprietà:
• annotations, una sequenza di annotazioni
• test, una espressione XPath 2.0
• type, una definizione di tipo
Il relativo elemento <alternative> può comparire solo all’interno di una dichiarazione di elemento e coinciderà con una entry nella sua type table. Così come per
<assert> (cfr. 2.2.1), anche <alternative> contiene un attributo test con il medesimo ruolo. Inoltre ogni <alternative> deve esplicitare un tipo. Questo può essere
fatto in due modi mutuamente esclusivi: come valore di un attributo type, quindi
2.2 Supporto ai co-constraint in XSDL 1.1
con un riferimento per nome qualificato ad un tipo globale; oppure definendo un
nuovo tipo anonimo locale ad <alternative>.
A grandi linee l’assegnamento di tipo agli elementi d’istanza che fanno riferimento
a dichiarazioni che racchiudono type alternative avviene in questo modo: la prima
type alternative, in ordine di dichiarazione, il cui test XPath sia valutato a true
provoca l’assegnamento del relativo tipo. Se ciò non avviene per nessuna delle type
alternative allora il tipo dell’elemento sarà quello specificato nell’attributo type di
element oppure quello definito localmente ad esso. Di seguito indicheremo quest’ultimo come “declared type” dell’elemento, distinguendolo dai tipi delle type alternative
che identificheremo come “tipi alternativi”. Esiste inoltre la possibilità di dichiarare
una type alternative di default, ossia un elemento <alternative> che compare per
ultimo nell’elemento in cui e racchiuso e che non dichiara nessuna condizione XPath. Attraverso quest’ultima è possibile esplicitare il tipo che deve essere assegnato
qualora la valutazione delle altre alternative non provochi nessuna selezione di tipo.
Un caso d’uso tipico della alternativa di default è l’assegnamento del tipo error. Il
tipo error è introdotto in XSDL 1.1 proprio per CTA, ed è definito come simple
type contro cui nessun contenuto risulta valido. Il suo assegnamento come tipo ad
un elemento provocherà dunque la sua invalidità. Per comprendere l’utilità di error
immaginiamo una dichiarazione di elemento in cui i predicati XPath racchiusi nelle
type alternative siano test sul valore di uno stesso attributo. Assegnando come alternativa di default error, si otterrà una restrizione sul dominio dell’attributo in base
alla quale i soli valori leciti saranno quelli a cui le type alternative fanno riferimento.
Esprimere i co-constraint attraverso CTA
Di seguito sarà mostrato un caso d’uso tipico di CTA riprendendo il documento
portato ad esempio in fig. 2.1 e mostrando in che modo sia possibile definirne uno
schema che sia in grado di esprimere i co-constraint menzionati usando CTA.
Prima però è importante enunciare una restrizione sulla dichiarazione di elementi che racchiudono type alternative 1 : ogni tipo condizionale deve essere derivato in
modo valido dal tipo dichiarato dell’elemento. Questa limitazione, che non compromette comunque l’espressività di CTA, è dovuta prevalentemente alla necessità di
mantenere una relazione tra i tipi che un elemento può assumere.
Uno schema per il documento in fig. 2.1 potrebbe essere il seguente:
1
cfr. ‘Schema Component Constraint: Element Declaration Properties Correct’, punto 7.1 della
sezione 3.3.6 delle specifiche [GSMT07].
21
22
2. XSDL 1.1 e Conditional Type Assignment
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema"
targetNamespace="www.example.com/biblio"
xmlns="www.example.com/biblio">
<xs:complexType name="entry_t">
<xs:sequence>
<xs:element name="author" type="xs:string"/>
<xs:element name="title" type="xs:string"/>
</xs:sequence>
<xs:attribute name="kind" type="xs:QName"/>
<xs:attribute name="key" type="xs:QName"/>
</xs:complexType>
<xs:complexType name="web_entry_t">
<xs:complexContent>
<xs:extension base="entry_t">
<xs:sequence>
<xs:element name="url" type="xs:anyURI"/>
</xs:sequence>
</xs:extension>
</xs:complexContent>
</xs:complexType>
<xs:complexType name="bibliography_t">
<xs:sequence>
<xs:element name="entry"
minOccurs="0" maxOccurs="unbounded"
type="entry_t">
<xs:alternative test="@kind=‘web-page’"
type="web_entry_t"/>
</xs:element>
</xs:sequence>
</xs:complexType>
<xs:element name="bibliography" type="bilbliography_t"/>
</xs:schema>
Restrizioni sulle espressioni XPath
Le espressioni XPath consentite all’interno delle type alternative sono ancora più
ristrette rispetto a quelle lecite per assertions. Per mantenere la coerenza con la
politica STEVE di fatto i vincoli espressi in CTA debbono poter essere verificati
interamente allo start element, poichè il tipo dell’elemento d’istanza deve essere noto
al verificarsi di questo evento. Dunque le espressioni di test non potranno contenere
che attribute step. Per questo attraverso CTA è possibile legare il content model di
2.2 Supporto ai co-constraint in XSDL 1.1
un elemento solo al valore o alla presenza dei suoi attributi, e non ad esempio alla
presenza di figli.
Una considerazione differente riguarda il tipo dei nodi del documento su cui avviene
la valutazione di XPath 2.0. XPath 2.0 introduce un sistema di tipi che comprende i
tipi primitivi di XML Schema e consente una valutazione delle espressioni in base ad
essi. Le informazioni sul tipo dei nodi tuttavia sono ricavate attraverso la validazione
stessa del documento. Ovviamente in questo caso non è possibile effettuare una
valutazione dell’espressione sui nodi tipati poichè al momento della valutazione il
tipo del nodo non è ancora stato assegnato. Per questo motivo il predicato XPath
di una type alternative sarà valutato su nodi untyped.
Differenze con SchemaPath
SchemaPath è un’estensione minimale di XML Schema 1.0 presentata proprio per
aggiungere il supporto ai co-constraint in XML Schema. Abbiamo già accennato al
fatto che CTA sia basato su SchemaPath, in questa sezione evidenzieremo alcune
delle principali differenze tra le due soluzioni. Infatti anche se le differenze sintattiche tra i due costrutti sono minime, esistono una serie di importanti differenze
concettuali. Così come per CTA anche per SchemaPath può essere associata ad ogni
dichiarazione di elemento una sequenza di tipi alternativi selezionati in base alla valutazione di espressioni XPath. Esiste dunque un corrispettivo <alt> dell’elemento
<alternative> anche in SchemaPath con la funzione di dichiarazione di type alternative, che lega quindi una dichiarazione di tipo ad una espressione XPath.
La prima differenza con CTA riguarda le espressioni XPath. In SchemaPath non esistono limitazioni sugli assi selezionabili, dunque anche following e sibilling sono
leciti. Ad esempio si può scrivere un’alternativa che assegni il tipo di un elemento
<E> in base alla presenza di un figlio <F>. In questo caso il principio di STEVE non
è più vero in generale. Infatti, secondo questo esempio, prima di assegnare il tipo ad
<E> il validatore deve ricevere almeno lo start element per l’elemento <F>. In questi
casi SchemaPath adotta una politica di validazione differente proposta in [MVZ07].
Inoltre un’altra differenza fondamentale è che in SchemaPath la presenza di alternative esclude la presenza del declared type. Se nessuna alternativa è soddisfatta in
tal caso si assegna error.
Infine l’ultima notevole differenza è dovuta all’ordine di valutazione e selezione delle
alternative. Se in CTA esso segue l’ordine lessicografico, in SchemaPath le alternative possiedono tutte una priorità, che di default è stabilita in base alla specificità
della condizione XPath, in maniera del tutto analoga a quanto avviene in XSLT, ma
che può essere settata esplicitamente attraverso l’attributo priority di <alt>.
23
Capitolo 3
Verifica statica dei vincoli di
restrizione con CTA
In questo capitolo mostreremo una soluzione parzialmente statica al problema della
verifica dei vincoli di restrizione in presenza di CTA. Per prima cosa sarà introdotto
il problema legato alla restrizione di tipi complessi che racchiudono type alernative.
Poi saranno presentate e discusse alcune proposte per la sua soluzione. Mostreremo
quindi un algoritmo in due varianti che risolva il problema parzialmente a tempo
di compilazione dello schema e uno che invece effettua ogni controllo in fase di
validazione. Inoltre effettueremo una comparazione tra i due algoritmi.
3.1
CTA e restrizione di tipi complessi
L’introduzione di CTA in XSDL 1.1 solleva un problema riguardante le regole
per il controllo della restrizione di tipi complessi in presenza di type alternative.
Consideriamo il seguente documento il cui schema sia definito come in figura 3.1:
<root>
<e a="5" b="2"/>
</root>
A tempo di validazione all’elemento <e> verrà assegnato il tipo t2 in quanto il tipo
dell’elemento <root> è restricted e il predicato “@a > @b” è soddisfatto. Tuttavia
se <root> fosse di tipo base considerando le type alternative per <e> in questo caso
sarebbe assegnato il tipo t1. Dato che però t2 non è definito come restrizione per
t1, possiamo dire che nel contesto del documento d’istanza il tipo dell’elemento <e>
non restringe il corrispettivo tipo di <e> in base. Ma allora lo schema in fig. 3.1 è
corretto?
25
26
3. Verifica statica dei vincoli di restrizione con CTA
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
<xs:complexType name="base">
<xs:sequence>
<xs:element name="e">
<xs:alternative test="@a > @b" type="t1"/>
<xs:alternative test="@a <= @b" type="t2"/>
</xs:element>
</xs:sequence>
<xs:attribute name="a"/>
<xs:attribute name="b"/>
</xs:complexType>
<xs:complexType name="restricted">
<xs:complexContent>
<xs:restriction base="base">
<xs:sequence>
<xs:element name="e">
<xs:alternative test="@a > @b" type="t2"/>
<xs:alternative test="@a <= @b" type="t1"/>
</xs:element>
</xs:sequence>
<xs:attribute name="a"/>
<xs:attribute name="b"/>
</xs:restriction>
</xs:complexContent>
</xs:complexType>
<xs:complexType name="t1">
<xs:sequence>
<xs:element name="t1"/>
</xs:sequence>
</xs:complexType>
<xs:complexType name="t2">
<xs:sequence>
<xs:element name="t2"/>
</xs:sequence>
</xs:complexType>
<xs:element name="root" type="restricted"/>
</xs:schema>
Figura 3.1: Un caso d’uso che presenta una restrizione non valida.
3.2 Tecniche per la verifica dei vincoli di restrizione
Dobbiamo ovviamente chiederci quindi se il complex type restricted è una restrizione valida del complex type base anche in presenza di questa eventualità a run-time. A
questo proposito nelle specifiche di XML Schema 1.1 vale il vincolo seguente1 : “Ogni
sequenza di elementi che sia valida rispetto al complex type ristretto deve essere valida rispetto al complex type base”. In base a questa regola lo schema precedente non
può essere considerato valido. Infatti in generale la sequenza di elementi riconosciuta
per il contenuto di <root> dal tipo restricted non è riconosciuta anche dal tipo
base.
3.2
Tecniche per la verifica dei vincoli di restrizione
A questo punto sorge un nuovo problema: come rilevare allora la presenza di situazioni di restrizione non valida in presenza di alternative? Inoltre quando deve essere
fatto? A tempo di compilazione dello schema o a tempo di validazione dell’istanza?
In questa sezione esamineremo alcune possibili soluzioni avanzate durante la stesura del Draft di XSDL 1.1 nella mailing list dell’intrest group di XML Schema.
Per completezza nella trattazione è giusto evidenziare che durante la discussione di
questo problema sono state avanzate anche proposte molto radicali, quali impedire
che possano comparire dichiarazioni di elemento condizionali, oppure evitare direttamente il controllo, nel qual caso lo schema in fig. 3.1 sarebbe considerato corretto.
Tuttavia in questa dissertazione non le prenderemo in considerazione, concentrandoci nell’esame di tecniche più plausibili in modo da poter fare un raffronto con la
soluzione proposta. Inoltre non prenderemo in considerazione nemmeno l’ipotesi di
una verifica completamente statica della restrizione, per cui si dovrebbero dedurre
i tipi assegnati in base alla semantica dei predicati XPath, cosa probabilmente infattibile. Tra le soluzioni proposte dunque ne illustreremo sia alcune che consentono
una verifica statica della restrizione, limitando però l’esspressività di CTA, sia altre
che demandano il controllo parzialmente o completamente alla fase di validazione.
3.2.1
Prefix
Una prima soluzione è nota con il nome di prefix. Si tratta di fare in modo che la
type table della dichiarazione di elemento condizionale2 nel tipo base sia ripetuta
1
vedi Schema Component Constraint: Content type restricts in sez. 3.4.6 delle specifiche
[GSMT07]
2
Per brevità indicheremo con “dichiarazione di elemento condizionale” le dichiarazioni di
elemento per cui è presente una type table
27
28
3. Verifica statica dei vincoli di restrizione con CTA
all’inizio della type table della dichiarazione corrispondente nel tipo ristretto. Indicheremo quindi l’insieme delle type alternative ripetute nella dichiarazione locale al
tipo ristretto con il termine di “prefisso”.
Essa è stata formulata in due varianti, una influenza solo la semantica del costrutto
di restrizione, l’altra impone anche un vincolo sintattico:
1. Tutte le type alternative presenti nella dichiarazione di elemento locale alla
base vengono automaticamente ereditate da quella locale al tipo ristretto.
2. Chi scrive lo schema deve ripetere, in caso di restrizione, per ogni dichiarazione
nel tipo ristretto tutte le <alternative> presenti nella relativa dichiarazione
nella base, lasciandone inalterato il predicato ma con la possibilità di specificare
un tipo ristretto.
Nel seguito faremo riferimento sempre alla seconda opzione in quanto si presta meglio
ad esemplificazioni. A questo scopo si noti che tra le due essa è la meno restrittiva.
Consideriamo dunque ancora lo schema espresso in fig. 3.1, riscrivendo la dichiarazione per l’elemento <e> locale al tipo ristretto secondo prefix :
<xs:element name="e">
<!-- prefix inherited from base -->
<xs:alternative test="@a > @b" type="t1"/>
<xs:alternative test="@a <= @b" type="t2"/>
<!-- restricted -->
<xs:alternative test="@a > @b" type="t2"/>
<xs:alternative test="@a <= @b" type="t1"/>
</xs:element>
É facile mostrare che possono verificarsi due sole situazioni a run-time nell’assegnamento di tipo per <e>:
• Uno dei predicati nel prefisso è soddisfatto. In questo caso il tipo assegnato
all’elemento è per costruzione della type table un tipo ristretto rispetto a quello
che sarebbe assegnato dalla dichiarazione di base.
• Nessuno dei predicati nel prefisso è soddisfatto. Questo implica che la dichiarazione di <e> in base assegnerebbe il declared type, mentre il content model
ristretto assegnerebbe ad <e> uno tra gli altri tipi condizionali oppure il declared type della dichiarazione in restricted. A questo punto possono accadere
ancora due cose:
3.2 Tecniche per la verifica dei vincoli di restrizione
– Il tipo assegnato secondo la dichiarazione ristretta è derivato per restrizione dal declared type, nel qual caso è sicuramente anche restrizione del
declared type per la dichiarazione nella base.
– Il tipo assegnato secondo la dichiarazione ristretta non è derivato per restrizione dal declared type, nel qual caso non è sicuramente una restrizione
del declared type per la dichiarazione nella base.
Secondo questo stratagemma è possibile verificare la corretta restrizione dei tipi
condizionali semplicemente verificando che il prefisso sia dichiarato correttamente in
fase di compilazione, e modificando in xs:error i tipi condizionali nel content model
ristretto che derivano per estensione il declared type. In pratica prefix è una soluzione
quasi totalmente statica al problema. Tuttavia essa limita troppo l’espressività di
CTA escludendo di fatto numerosi casi d’uso. Consideriamo l’esempio in figura 3.2.
L’intento del tipo InvoiceItem è quello di descrivere il contenuto di una voce in una
fattura fiscale. In particolare l’elemento <amount> dovrà contenere l’importo della
voce, inoltre l’attributo payment consentirà di specificare la modalità di pagamento,
mentre l’attributo type identificherà la categoria della merce a cui si riferisce la
vendita.
Nel caso d’uso proposto si è ipotizzato di non voler accettare un pagamento in
contanti (Cash) inferiore a 20 dollari, inolre nel caso in cui il pagamento avvenga
tramite transazione bancaria ipotizziamo di non accettare un pagamento inferiore
ai 500 dollari. Consideriamo ora il complex type ristretto OverseaInlineItem. Esso
denota una voce di fatturazione per una vendita oltre oceano. Immaginiamo come
nell’esempio di non disporre della merce di tipo “Collection1” e quindi di voler
impedire sintatticamente la sua presenza nella fattura, inoltre immaginiamo che per
ammortizzare il costo di spedizione della merce di tipo “Collection2” si richiede
un ammontare di almeno 1000 dollari.
Sebbene l’esempio non sia completamente realistico, un caso d’uso di questo tipo è
assolutamente ragionevole. Tuttavia i vincoli enunciati non possono essere espressi
con prefix. Vediamo infatti cosa accadrebbe ripetendo il prefisso in questo caso:
<xs:complexType name="OverseaInvoiceItem">
<xs:sequence>
<xs:element name="amount" type="amount_t">
<xs:alternative test="@payment=‘Cash’"
type="greaterThan20_t"/>
<xs:alternative test="@payment=‘Credit Card’"
type="greaterThan0_t"/>
<xs:alternative test="@payment=‘Bank Transfer’"
29
30
3. Verifica statica dei vincoli di restrizione con CTA
<xs:complexType name="InvoiceItem">
<xs:sequence>
<xs:element name="amount" type="amount_t">
<xs:alternative test="@payment=‘Cash’"
type="greaterThan20_t"/>
<xs:alternative test="@payment=‘Credit Card’"
type="greaterThan0_t"/>
<xs:alternative test="@payment=‘Bank Transfer’"
type="greaterThan500_t"/>
</xs:element>
</xs:sequence></xs:complexType>
<xs:complexType name="OverseaInvoiceItem">
<xs:complexContent>
<xs:restriction base="InvoiceItem">
<xs:sequence>
<xs:element name="amount" type="amount_t">
<xs:alternative test="@type=‘Collection1’"
type="xs:error"/>
<xs:alternative test="@type=‘Collection2’"
type="greaterThan1000_t"/>
</xs:element>
</xs:sequence>
</xs:restriction>
</xs:complexContent></xs:complexType>
<xs:complexType name="amount_t">
<xs:simpleContent>
<xs:extension base="xs:decimal">
<xs:attribute name="type" type="type_t"/>
<xs:attribute name="payment" type="payment_t"/>
</xs:extension>
</xs:simpleContent></xs:complexType>
<xs:simpleType name="payment_t">
<xs:restriction base="xs:string">
<xs:enumeration value="Cash"/>
<xs:enumeration value="Credit Card"/>
<xs:enumeration value="Bank Transfer"/>
</xs:restriction></xs:simpleType>
<xs:simpleType name="type_t">
<xs:restriction base="xs:string">
<xs:enumeration value="Collection1"/>
<xs:enumeration value="Collection2"/>
</xs:restriction></xs:simpleType>
Figura 3.2: Uno schema per voci di fatturazione.
3.2 Tecniche per la verifica dei vincoli di restrizione
type="greaterThan500_t"/>
<xs:alternative test="@type=‘Collection1’"
type="xs:error"/>
<xs:alternative test="@type=‘Collection2’"
type="greaterThan1000_t"/>
</xs:element>
</xs:sequence>
</xs:complexType>
É facile notare che i tipi condizionali dichiarati nel content model ristretto non verranno mai selezionati. Quindi il beneficio della restrizione è praticamente annullato.
3.2.2
Vincolare il numero delle alternative
Una seconda possibilità è la seguente: una definizione di tipo che coinvolge CTA può
essere ristretta solo da tipi in cui le dichiarazioni di elemento condizionale espongono
lo stesso numero di alternative e con gli stessi predicati XPath ma con tipi ristretti.
Viceversa se si vuole restringere un tipo che non coinvolge CTA basta verificare
staticamente che le type alternative assegnino un tipo ristretto rispetto ai declared
type. É facile vedere che in questo caso la verifica della restrizione è banalmente
verificabile in fase di compilazione. Tuttavia l’espressività del costrutto per CTA
risulterebbe fortemente mutilata. A tale scopo si fa notare che tale regola è ben più
restrittiva di prefix e non comporta maggiori vantaggi.
3.2.3
Run-time Checking
Una possibilità completamente dinamica relega il controllo della restrizione completamente alla fase di validazione. Questa è la soluzione implicitamente adottata
nel Draft di XML Schema 1.1 ed è riferita come Run-time Checking(RTC). In particolare essa è descritta dal vincolo Conditional Type Substitutable in Restriction
riportato di seguito. Dato un elemento del documento d’istanza <E> e un complex
type T, siano:
• B la definizione del tipo base di T
• TT la type table di <E> in T, se esiste
• TB la type table di E in B, se esiste
• ST la definizione di tipo assegnata per <E> da TT , se TT esiste
• SB la definizione di tipo assegnata per <E> da TB , se TB esiste
31
32
3. Verifica statica dei vincoli di restrizione con CTA
<E> e T soddisfano questo vincolo se e solo se una delle seguenti condizioni è
verificata:
1. TB non esiste
2. TT e TB esistono entrambe ed almeno una delle seguenti condizioni è verificata:
(a) B è xs:anyType e ST è una valida restrizione per SB
(b) T è derivato per restrizione ed ST è valida restrizione per SB , e sia <E> che
B soddisfano questo vincolo.
(c) T è derivato per estensione, e ST è identico ad SB , e sia <E> che B soddisfano
questo vincolo.
A tempo di validazione dunque, una volta ottenuta la type table in base alla dichiarazione di elemento, si ricava da essa il tipo da assegnare (selected type) valutando
i predicati XPath delle relative type alternative. A questo punto è necessario anche
valutare la type table nella dichiarazione di base così da verificare la restrizione tra
il tipo selezionato dalla type table ristretta e quello selezionato da quest’ultima. Si
procede ricorsivamente verificando la relazione di restrizione lungo tutta la catena
di derivazione.
Di seguito è riportata una descrizione in pseudo-codice dell’algoritmo3 che scaturisce
naturalmente dalla definizione di Conditional Type Substitutable in Restriction:
void start-element(QName name, Attribtes attr) {
current-type <- get-current-type()
Type Definition T <- current-type
Type Definition B <- current-type.base
while (B is not xs:anyType) do {
Type Table type-table <- get-corresponding-type-table(name, T)
// selected type
Type Definition ST <- type-table.execute(name, attr)
Type Table base-type-table <- get-corresponding-type-table(name, B)
Type Definition SB <- base-type-table.execute(name, attr)
if (validly-substitutable-restriction(ST, SB)) {
T <- B
3
Il codice proposto è quello di un validatore che riceve l’evento “start element” di un parser SAX
3.2 Tecniche per la verifica dei vincoli di restrizione
33
B <- B.base
} else
report-schema-error(
"Validation Rule: Conditional Type Substitutable in Restriction"
)
}
Type Table type-table <- get-corresponding-type-table(name, current-type)
Type definition selected-type <- type-table.execute(name, attr)
set-current-type(selected-type)
}
É facile vedere che questa soluzione verifica effettivamente la subsumption dei content model 4 poichè eventuali violazioni dipendenti dal contesto saranno evidenziate
a run-time. Inoltre RTC non impone nessuna restrizione sintattica o semantica per
CTA. Va evidenziato anche che una sua eventuale implementazione sarebbe tanto
semplice quanto la sua definizione.
É importante però mostrare un limite di questa tecnica, intrinseco al controllo dinamico: RTC deve controllare, potenzialmente per ogni elemento d’istanza, la restrizione tra tipi. Se infatti la valutazione dei predicati deve essere per forza effettuata
dinamicamente, dal momento che dipende dal contesto, il controllo delle relazioni
tra i tipi potrebbe essere risolto a tempo di compilazione dato che la catena di derivazione è una proprietà intrinseca del solo schema.
Analisi del costo computazionale
Ponendoci nel caso pessimo, il controllo della restrizione sarà lineare sia nella profondità della gerarchia di restrizione, sia nel numero di predicati da valutare. Consideriamo infatti che RTC dovrà al più percorrere l’intera gerarchia dalla foglia di
livello più basso alla radice (anyType). Inoltre ad ogni passo dovrà valutare, sempre
nel caso pessimo, tutti predicati racchiusi in tutte le type table. Supponiamo che la
valutazione di qualsiasi predicato abbia costo costante unitario. Siano quindi:
• c, il numero medio di predicati, coincidenti in questo caso con il numero medio
di alternative, ottenuto come media aritmetica delle dimensioni delle type table.
Secondo quanto detto c rappresenta anche il costo medio della valutazione dei
predicati per una type table.
4
Ovvero controllare che il content model ristretto riconosca un sotto-linguaggio di quello
riconosciuto dal content model di base
34
3. Verifica statica dei vincoli di restrizione con CTA
• n la profondità massima della gerarchia dei tipi.
• a il costo delle operazioni che RTC compie ad ogni ricorsione sulla catena
eccetto la selezione del tipo sulla type table.
Allora il costo computazionale complessivo introddotto da RTC nella validazione di
un elemento è espresso dalla relazione: TRT C = n(a + c).
Dove a è una costante che comprende i costi delle seguenti operazioni, tutte realizzabili in tempo costante:
• trovare la base del tipo corrente
• trovare la type table dell’elemento corrente nel tipo appena ricavato
• controllo della restrizione
• controllo di flusso per il caso base
• chiamata ricorsiva
Supponendo inoltre c costante possiamo evidenziare che TRT C è θ(n).
3.3
Prodotto Cartesiano
La tecnica riferita come Prodotto Cartesiano si basa sull’idea di verificare la restrizione enumerando tutte le possibili situazioni che possono accadere a run-time. In
particolare date T Tr , la type table per la dichiarazione di elemento e nel tipo ristretto, e T Tb , la rispettiva type table nel tipo base, viene costruita una nuova type
table T Tp che consente di assegnare i tipi in maniera equivalente a T Tr eccetto per
le situazioni in cui verrebbe assegnato un tipo scorretto secondo la restrizione, nel
qual caso T Tp assegnerà xs:error.
In questo modo la restrizione è completamente verificata in fase di analisi statica
dello schema. A run-time il validatore effettuerà l’assegnamento di tipo semplicemente valutando le aternative racchiuse in T Tp .
Per mostrare in che modo venga costruita T Tp supponiamo innanzitutto che T Tr
contenga le seguenti alternative nell’ordine specificato:
< cr1 , Tr1 >, < cr2 , Tr2 >, ..., < crm−1 , Trm−1 >, < crm = true, Tr >
e che T Tb contenga le seguenti alternative nell’ordine specificato:
< c1 , T1 >, < c2 , T2 >, ..., < ck−1 , Tk−1 >, < ck = true, T >
3.3 Prodotto Cartesiano
35
Dove T e Tr sono i declared type relativi alle due dichiarazioni di elemento.
A questo punto T Tp è costruita come in figura 3.3.
Consideriamo ancora l’esempio di fig. 3.2. Secondo il PC la type table che assegna il
tipo ad <e> nel tipo ristretto è la seguente:
< @payment=‘Cash’ ∧ @type=‘Collection1’ → xs:error >
< @payment=‘Credit Card’ ∧ @type=‘Collection1’ → xs:error >
< @payment=‘Bank Transfer’ ∧ @type=‘Collection1’ → xs:error >
< @type=‘Collection1’ → xs:error >
< @payment=‘Cash’ ∧ @type=‘Collection2’ → greaterThan1000_t >
< @payment=‘Credit Card’ ∧ @type=‘Collection2’ → greaterThan1000_t >
< @payment=‘Bank Transfer’ ∧ @type=‘Collection2’ → greaterThan1000_t >
< @type=‘Collection2’ → greaterThan1000_t >
< @payment=‘Cash’ → xs:error >
< @payment=‘Credit Card’ → xs:error >
< @payment=‘Bank Transfer’ → xs:error >
< true() → amount_t >
Possiamo dividere la tabella appena riportata in tre tronconi, uno per ogni alternativa della tabella originale di OverseaInvoiceItem. Possiamo vedere inoltre come
ognuna di esse sia ripetuta per ogni possibile alternativa della type table nella base e
che le relative condizioni siano messe in congiunzione. É facile notare come in questo
modo ogni possibile situazione a run-time sia presa in considerazione. Per vedere in
che modo siano rilevate le situazioni di errore, consideriamo il caso che per la type table ristretta venga assegnato il declared type amount_t: poichè amount_t non è restrizione di nessuno tipo tra greaterThan0_t, greaterThan20_t, greaterThan500_t,
in quel caso la type table costruita assegnerà xs:error. Viceversa l’assegnamento
di amount_t è consentito quando anche nel tipo base verrebbe assegnato il declared type, ovvero nessuno dei predicati @payment=‘Cash’, @payment=‘Credit Card’,
36
3. Verifica statica dei vincoli di restrizione con CTA
< cr1 ∧ c1 → (Tr1 | error) >
< cr1 ∧ c2 → (Tr1 | error) >
...
< cr1 ∧ ck−1 → (Tr1 | error) >
< cr1 → (Tr1 | xsd : error) >
< cr2 ∧ c1 → (Tr2 | error) >
< cr2 ∧ c2 → (Tr2 | error) >
...
< cr2 ∧ ck−1 → (Tr2 | error) >
< cr2 → (Tr2 | error) >
..
.
< crm−1 ∧ c1 → (Trm−1 | error) >
< crm−1 ∧ c2 → (Trm−1 | error) >
...
< crm−1 ∧ ck−1 → (Trm−1 | error) >
< crm−1 → (Trm−1 | error) >
< c1 → (Tr | error) >
< c2 → (Tr | error) >
...
< ck−1 → (Tr | error) >
< true → Tr >
Figura 3.3: type table ottenuta con il Prodotto Cartesiano.
3.3 Prodotto Cartesiano
@payment=‘Bank Transfer’ è soddisfatto.
L’algoritmo che date T Tr e T Tb costruisce T Tp può essere formalizzato nel modo
seguente:
perform-single-cartesian-product(type-tabe: Type Table,
base-type-table: Type Table)
: Type Table
beginprocedure
Type Table new-type-table <- empty-type-table()
for each type-alternative in type-table.type-alternatives
do
T <- type-alternative.type
test < type-alternative.test
for each base-type-alternative
in base-type-table.type-alternatives do
B <- base-type-alternative.type
base-test <- base-type-alternative.test
if (T.validly-substitutable-restriction(B))
new-type-table.add(<test & base-test, T>)
else
new-type-table.add(<test & base-test, ERROR>)
endprocedure
Finora abbiamo descritto il Prodotto Cartesiano come una procedura che date due
type table ne costruisce una terza in modo da poter assegnare solo in base ad essa i tipi. Tuttavia questo procedimento va ripetuto per ogni dichiarazione di elemento che fa riferimento ad alternative. Inoltre per ognuna di esse l’assegnamento
deve essere sicuro non solo rispetto alla base, ma anche rispetto agli antenati nella gerarchia dei tipi. Per questo l’intero schema è processato secondo il metodo
appena esposto, procedendo in una visita top-down della gerarchia dei tipi e applicando perform-single-cartesian-product per ogni coppia di type table baseristretta di ogni dichiarazione di elemento. Il processo completo può essere descritto
in pseudo-codice come segue:
perform-all-cartesian-products(S: schema) beginprocedure
for each T in S.types do
T.mapping <- empty set
for each term in T.content_model do
37
38
3. Verifica statica dei vincoli di restrizione con CTA
term-type-table <- get-type-table(term)
T.mapping.add(<term, term-type-table>)
for each T in S.types in a top-down traversal of the hierarchy
do
if (T is not xs:anyType) then
B <- T.base
for each <term, type-table> in T.mapping do
base-type-table <- get-corresponding-type-table(term, B);
// overwrite the term type table
type-table <- perform-single-cartesian-product(type-table,
base-type-table);
endprocedure
Dove si è usata la funzione get-corresponding-type-table che dato un termine all’interno di un tipo complesso ritorna la corrispettiva type table dell’elemento
corrispondente nel tipo base. É importante notare che questo è sempre possibile in
quanto deve valere il vincolo Element Declarations Consistent 5 .
Al momento della validazione, in particolare alla ricezione di eventi “start element”
da un parser SAX, è possibile assegnare il tipo valutando solo la tabella dei tipi
costruita, come espresso di seguito:
start-element(name: QName) beginprocedure
current-type <- get-current-type()
ElementDelcaration D <- current-type.transition(name)
Type Table type-table <- crrent-type.mapping.get(D)
T selected-type <- type-table.execute()
if (selected-type == ERROR) then
report-schema-error(
"Conditional Type Substitutable in Restriction"
)
else
current-type <- selected-type
endprocedure
5
Confrontare Element Declarations Consistent in sez. 3.8.6 delle specifiche [GSMT07]
3.3 Prodotto Cartesiano
Analisi del costo computazionale
In questa sezione effettueremo un’analisi del costo nello spazio e nel tempo dell’algoritmo esposto. Inoltre, poichè il Prodotto Cartesiano influisce sul costo della
validazione, incrementando il numero di alternative da valutare, effettueremo anche
una stima del costo a run-time.
Chiamiamo db la dimensione di T Tb e dr la dimensione di T Tr . Allora la procedura
perform-single-cartesian-product deve cosrtuire db · dr alternative. Sia poi n
la profondità massima della gerarchia di restrizione. La procedura viene richiamata
n volte lungo il cammino dalla base alla foglia, usando come T Tb la T Tp ricavata
al passo precedente. Il costo del passo generico per costruire T Tpi date T Tpi−1 e
Q
T Tri è pari alla dimensione di T Tpi−1 , ovvero ij=1 dj , per la dimensione di T Tri .
Dunque il costo computazionale e lo spazio necessario per l’algoritmo sono asintoticamente equivalenti a g n , dove g è la media geometrica delle dimensioni d1 , ..., dn :
√
n
d1 · ... · dn .
Per quanto riguarda il carico di lavoro introdotto nella fase di validazione consideriamo che esso sia pari al numero di predicati da valutare nel caso pessimo per
assegnare il tipo ad un elemento.
Siano dunque T T1 , ..., T Tn type table di dimensione rispettivamente d1 , ..., dn , dove con dimensione sono intese il numero di alternative in esse racchiuse.
La dimensione di una generica type table T T sarà indicata con dim(T T ). Prima
di operare il Prodotto Cartesiano tra le varie type table, la dimensione di una type
table coincide con il numero di condizioni atomiche presenti in essa, dove con condizioni atomiche sono intese quelle specificate dall’autore dello schema.
Per applicare il Prodotto Cartesiano si deve iterare lungo la catena di type table
T T1 , ..., T Tn eseguendo le seguenti operazioni:
• Passo 1: T T2 × T T1
• Passo 2: T T3 × (T T2 × T T1 )
• ...
• Passo n − 1: T Tn × (...(T T3 × (T T2 × T T1 ))...)
L’operatore “×” è definito tra due type table e dà come risultato una type table. In
particolare, siano T Ta e T Tb due generiche type table, allora T Ta × T Tb corrisponde
39
40
3. Verifica statica dei vincoli di restrizione con CTA
alla type table costruita come mostrato in 3.3, considerando T Ta come type table
ristretta e T Tb come type table di base.
Consideriamo quindi la funzione così definita:

T T
se k = 1,
1
P C(k) =
T T × P C(k − 1) se k > 1.
k
Dove per ogni k in 1, .., n, P C(k) denota una type table.
Siamo quindi interessati a calcolare il numero di condizioni atomiche presenti nella
table P C(n). Siano quindi T T e T T 0 due type table e siano r ed s le loro dimensioni,
ovvero:
• r = dim(T T )
• s = dim(T T 0 )
Indichiamo quindi le r condizioni di T T con c1 , ..., cr e le s condizioni di T T 0 con
c01 , ..., c0s .
La type table risultante sarà quindi composta dalle seguenti alternative:
< c1 ∧ c01 → (T1 |error) >
..
.
< c1 ∧ c0s → (T1 |error) >
..
.
< cr ∧ c01 → (Tr |error) >
< cr ∧ c0s → (Tr |error) >
Come detto dim(T T × T T 0 ) = r · s. Notiamo inoltre che ogni alternativa ha due
condizioni messe in and. Vediamo quindi come varia il numero di condizioni atomiche
nella tabella risultante da P C(n).
Al primo passo otteniamo una type table T T2 × T T1 di dimensione d2 · d1 , in cui ogni
alternativa specifica una condizione composta da due condizioni atomiche messe in
and. Quindi abbiamo che il numero totale di condizioni atomiche presenti nella type
table T T2 × T T1 (indicata anche con P C(2)) è dato da d2 · d1 · 2.
Al secondo passo abbiamo la type table P C(3), ovvero T T3 × (T T2 × T T1 ). Tale type
3.3 Prodotto Cartesiano
table ha dimensione:
dim(P C(3)) = d3 · dim(P C(2)) = d3 · d2 · d1
Ogni alternativa di P C(3) ha una condizione composta due condizioni messe in and :
• una condizione atomica di T T3
• una condizione composta a sua volta di due condizioni atomiche messe in and
(una di T T2 e l’altra di T T1 ).
A questo punto ha senso considerare la funzione N C così definita:

1
se k = 1,
N C(k) =
1 + N C(k − 1) se k > 1.
Abusando leggermente della sitnassi, definiamo anche la seguente funzione:

d
se k = 1,
1
dim(k) =
d · dim(k − 1) se k > 1.
k
che calcola la dimensione della type table P C(k). É immediato ora definire una
funzione che calcola il numero totale di condizioni atomiche nella type table P C(k)
come segue:
T N C(k) = dim(k) · N C(k)
Abbiamo quindi che
T N C(n) = dim(n) · N C(n) = g n · n
dove g è la media geometrica dei d1 , ..., dn . Infatti, notiamo immediatamente che:
dim(n) = dn · dn−1 · ... · d1 = g n
N C(n) = 1 + N C(n − 1) = 1 + 1 + N C(n − 1) == 1 + ... + 1 = n
La stessa cosa è possibile dire dunque del costo computazionale riguardante la fase
dinamica. L’assegnamento di tipo che fa riferimento a T Tpn nel caso pessimo richiede
la valutazione di tutti i predicati, che sono appunto n · g n .
41
42
3. Verifica statica dei vincoli di restrizione con CTA
3.3.1
Normalizzazione delle type table
Consideriamo la seguente type table T T :
< c1 → T1 >
< c2 → T2 >
..
.
< cn−1 → Tn−1 >
< true → Tn >
Quando si incontra un elemento <e> che deve essere validato contro questa type table,
le condizioni devono essere valutate nell’ordine specificato. Ovvero sono eseguite le
seguenti operazioni:
if c1 then
T1
else if c2 then
T2
else
...
else if cn-1 then
Tn-1
else
Tn
Consideriamo allora la funzione T (<e>, tt) che assegna il tipo al generico elemento
<e> in base alla type table tt. La seguente affermazione è vera:
T (<e>, T T ) = Ti se e solo se: Ci = ¬c1 ∧ ¬c2 ∧ . . . ∧ ¬ci−1 ∧ ci , con i = 1...k è
vera.
In altre parole affinchè venga assegnato un tipo in base ad una alternativa in T T
devono essere valutati a false tutti i predicati delle alternative che la precedono e
deve essere soddisfatto il predicato dell’alternativa stessa. É facile quindi notare che
la T T è equivaltente alla seguente type table T Tn :
< c1 → T1 >
< ¬c1 ∧ c2 → T2 >
3.3 Prodotto Cartesiano
43
..
.
< ¬c1 ∧ ¬c2 ∧ ... ∧ ¬cn−2 ∧ cn−1 → Tn−1 >
< ¬c1 ∧ ¬c2 ∧ ... ∧ ¬cn−1 , → Tn >
In questo modo si ottiene una type table semanticamente equivalente a quella originale, ma tale per cui dato un qualunque elemento <e> del documento di istanza, <e>
soddisfa una ed una sola delle condizioni (eventualmente l’ultima che è la negazione
di tutte le condizioni precedenti).
Diamo quindi la seguente definizione di type table deterministica: Una type table
è deterministica se per ogni elemento <e> del documento di istanza, <e> soddisfa
una ed una sola condizione.
Secondo quanto mostrato, data una qualunque type table è sempre possibile costruire una type table deterministica equivalente. Si noti inoltre che il costo di questo
processo è chiaramente lineare nella dimensione della type table originale.
Diciamo che una type table è normalizzata se tutte le alternative assegnano un tipo
diverso. Indicheremo che la type table T T è normalizzata con la notazione |T T |.
Mostriamo anche che una qualsiasi type table in forma deterministica può essere
normalizzata applicando la seguente regola: date due alternative qualsiasi di una
type table deterministica < a → Ta > e < b → Tb >, se Ta e Tb sono lo stesso tipo T allora è possibile sostituire le due alternative con una terza della forma:
< a ∨ b → T >.
Si noti che anche questo procedimento può essere realizzato in tempo lineare nella
dimensione della type table originale.
Inoltre è possibile normalizzare una type table qualunque6 applicando la seguente
regola per tutte le sue alternative: date due alternative qualsiasi di una type table
qualsiasi nell’ordine: < ci → Ta > e < cj → Tb >, se Ta e Tb sono lo stesso tipo T
allora è possibile eliminare la seconda alternativa e trasformare la prima come segue:
< ci ∨ (¬ci+1 ∧ .. ∧ ¬cj−1 ∧ cj ) → T >.
Sia dtt il numero di predicati per la tabella T T , allora il numero d|tt| di predicati
6
Non necessariamente deterministica.
44
3. Verifica statica dei vincoli di restrizione con CTA
racchiusi nella rispettiva |T T | ottenuta come descritto risulta essere7 :
d|tt| ≤
d2tt − 2dtt
+1
4
Enunciamo infine la seguente proprietà: data una qualsiasi type table T T e la relativa
type table normalizzata |T T | si ha che |T T | espone un numero di alternative pari al
numero di tipi selezionabili da T T .
3.3.2
Prodotto Cartesiano con type table normalizzate
Una variante del Prodotto Cartesiano, basata sulle proprietà esposte in sez. 3.3.1,
prevede la normalizzazione di tutte le type table costruite durante il processo. Adottando la stessa notazione introdotta in 3.3 dunque, ogni volta che si costruisce T Tp
essa viene normalizzata. L’algoritmo relativo è mostrato di seguito:
perform-single-cartesian-product(type-tabe: Type Table,
base-type-table: Type Table)
: Type Table
beginprocedure
Type Table new-type-table <- empty-type-table()
for each type-alternative in type-table.type-alternatives
do
T <- type-alternative.type
test <- type-alternative.test
for each base-type-alternative
in base-type-table.type-alternatives
do
B <- base-type-alternative.type
base-test <- base-type-alternative.test
if (validly-substitutable-restriction(T, B))
new-type-table.add(<test & base-test, T>)
else
new-type-table.add(<test & base-test, ERROR>)
normalize(new-type-table)
return new-type-table
endprocedure
7
Ci si riferisce al caso pessimo per cui la T T è della forma: < c1 → T1 >, < c2 → T2 >, ..., <
cn−1 → T2 >, < cn → T1 >
3.3 Prodotto Cartesiano
45
Costo computazionale
Secondo quanto detto in sez. 3.3.1, poichè T Tp espone sicuramente gli stessi tipi
di T Tr , |T Tp | ha dimensione uguale o minore della relativa T Tr . Attraverso questo
stratagemma è possibile ridurre il costo computazionale del Prodotto Cartesiano
nella fase statica da O(cn ) ad O(c2 n), dove si è supposto che tutte le type table
abbiano stessa dimensione c. Infatti durante il processo si lavora su type table la cui
dimensione non aumenta più in maniera quadratica rispetto alle originali. Tuttavia
il numero di condizioni XPath da valutare continua a crescere esponenzialmente.
Va detto che però il costo della normalizzazione visto in 3.3.1 considera un caso
pessimo che non si potrà verificare nel PCN8 , infatti non ci interessa ottenere una type
table completamente normalizzata, ci basta ottenerne una lineare nelle dimensioni
di quella originale.
Applicazione a due generiche type table Siano T T e T T 0 due generiche type
table. Siano inoltre r ed s le loro dimensioni. Indichiamo quindi le condizioni di T T
con
c1 , ..., cr
Indichiamo invece le condizioni di T T 0 con
c01 , ..., c0s
La tecnica di normalizzazione mira a costruire una type table T Tpn semanticamente
equivalente alla type table T T × T T 0 , ma la cui dimensione non dipenda da T T 0 e
che sia lineare nella dimensione di T T .
L’idea è quindi quella di costruire una type table in due fasi:
1. nella prima fase si genera una type table T T × T T 0 come descrito in sez. 3.3.
2. nella seconda fase si esegue una procedura di raggruppamento delle condizioni
che assegnano lo stesso tipo, mettendole in disgiunzione.
Consideriamo quindi la fase di raggruppamento delle condizioni. Ci troviamo nel caso
pessimo quando la prima fase genera una type table tale per cui, per ogni i = 1, ..., r,
si ha:
< ci ∧ c01 → Ti >
< ci ∧ c02 → error >
8
Con PCN intendiamo la variante del Prodotto Cartesiano appena descritta.
46
3. Verifica statica dei vincoli di restrizione con CTA
..
.
< ci ∧ c0m−1 → Ti >
< ci ∧ c0m → error >
Dove si sta assumendo per semplicità m pari. In questo caso abbiamo m/2 tipi T i
ed m/2 tipi error. Per ogni i = 1, ..., r, la fase di raggruppamento genera quindi due
alternative:
(ci ∧ c01 ) ∨ (¬(ci ∧ c02 ) ∧ (ci ∧ c03 )) ∨ ... ∨ (¬(ci ∧ c0m−2 ) ∧ (ci ∧ c0m−1 )) → T i
(ci ∧ c02 ) ∨ (¬(ci ∧ c03 ) ∧ (ci ∧ c04 )) ∨ ... ∨ (¬(ci ∧ c0m−1 ) ∧ (ci ∧ c0m )) → error
Possiamo osservare che per la prima alternativa, la condizione ci è ripetuta m − 1
volte. Inoltre, ci sono m − 1 condizioni di T T 0 . Le m − 1 condizioni di T T 0 sono c01 ,
..., c0m−1 .
Analogamente, per la seconda alternativa, la condizione ci è ripetuta m − 1 volte.
Inoltre, ci sono m − 1 condizioni di T T 0 (c02 , ..., c0m )
Inoltre notiamo che la dimensione delle type table risultante dalla fase di ragruppamento è
2·r
Infatti, per ogni alternativa in T T sono generate, nel caso pessimo, le due alternative
descritte sopra.
Applicazione alla catena di type table Supponiamo d’ora in poi che l’operatore × esegua il Prodotto Cartesiano nelle due fasi, come descritto in precedenza. Quindi, consideriamo ancora le tabelle T T1 , ..., T Tn di dimensioni d1 , ..., dn . Ripetiamo
inoltre la definizione di N C(k) data per ogni k in 1, ..., n come:

1
se k = 1,
N C(k) =
1 + N C(k − 1) se k > 1.
Qundi ridefiniamo la funzione che calcola la dimensione della type table P C(k):

d
1
dim(k) =
2 · d
k
se k = 1,
se k > 1.
3.3 Prodotto Cartesiano
47
La funzione che conta il numero di condizioni atomiche per alternativa della type
table P C(k) diventa dunque:

1
se k = 1,
N C(k) =
(dim(k − 1) − 1) + (dim(k − 1) − 1) · N C(k − 1) se k > 1.
che è equivalente a:

1
se k = 1,
N C(k) =
(dim(k − 1) − 1) · (1 + N C(k − 1)) se k > 1.
A questo punto, il numero totale di condizioni presente nella type table P C(k) è
dato dalla formula:
T N C(k) = dim(k) · N C(k)
Dal momento che noi siamo iteressati a calcolarla in n, abbiamo:
T N C(n) = dim(n) · N C(n)
3.3.3
Confronto con Run-Time Checking
L’algoritmo del Prodotto Cartesiano evita i costi intrinseci alla verifica completamente dinamica dei vincoli di restrizione. Tuttavia nelle due varianti introduce un
costo computazionale proporzionale al prodotto delle type table presenti in una catena di derivazione. Nonostante ciò va considerato che uno schema, nella maggior
parte dei casi, non presenta catene di restrizione molto profonde. In molti casi inoltre
è possibile ottimizzare le T Tp effettuando riscritture dei predicati.
É evidente, visto il suo costo computazionale, che il Prodotto Cartesiano è improponibile in un contesto generale. L’idea è quella di combinare entrambi gli algoritmi,
run-time checking (RTC) e Prodotto Cartesiano(PC) o Prodotto Cartesiano con normalizzazione (PCN), ed utilizzarli a seconda della convenienza. Il costo di ciascuno di
essi può essere determinato staticamente sullo schema in tempo lineare nella dimensione della gerarchia dei tipi. A tal proposito, per ciascuno dei tre algoritmi RTC,
PC e PCN, riassumiamo di seguito le formule per il calcolo del costo computazionale
a tempo di validazione:
• TRT C (n, c) = n(a + c)
• TP C (n, g) = n · g n
• TP CN (n) = dim(n) · N C(n)
48
3. Verifica statica dei vincoli di restrizione con CTA
In tabella 3.1 sono riportate alcune valutazioni delle funzioni per cui si è scelto di
imporre c = g, ed è stato assegnato costo unitario ad ogni valutazione di predicato
XPath. Per quanto riguarda RTC sono stati presi in considerazione i pesi 5 e 50 per
a. É possibile vedere in quali casi PC e PCN sono migliori di RTC.
c n
RTC
1 1 1a + 1
1 2 2a + 2
1 3 3a + 3
1 4 4a + 4
1 5 5a + 5
2 1 1a + 2
2 2 2a + 4
2 3 3a + 6
2 4 4a + 8
2 5 5a + 10
3 1 1a + 3
3 2 2a + 6
3 3 3a + 9
3 4 4a + 12
3 5 5a + 15
4 1 1a + 4
4 2 2a + 8
4 3 3a + 12
4 4 4a + 16
4 5 5a + 20
5 1 1a + 5
5 2 2a + 10
5 3 3a + 15
5 4 4a + 20
5 5 5a + 25
PC
1
2
3
4
5
2
8
24
64
160
3
18
81
324
1215
4
32
192
1024
5120
5
50
375
2500
15625
PCN
1
4
6
8
10
2
8
36
120
372
3
24
150
780
3930
4
48
392
2800
19656
5
80
810
7380
66510
RTC(a = 5)
6
12
18
24
30
7
14
21
28
35
8
16
24
32
40
9
18
27
36
45
10
20
30
40
50
RTC(a = 50)
51
102
153
204
255
52
104
156
208
260
53
106
159
212
265
54
108
162
216
270
55
110
165
220
275
Tabella 3.1: Costo introdotto nella fase di validazione da RTC, PC e PCN.
Notiamo quindi che, per certe dimensioni dell’input, l’approccio statico è più conveniente rispetto all’approccio completamente dinamico. Inoltre, nel caso di validazione di documenti multipli, i vantaggi del Prodotto Cartesiano potrebbero essere
maggiori.
Capitolo 4
Implementazione
A scopo dimostrativo è stato realizzato un prototipo in Java degli algoritmi per il
Prodotto Cartesiano (PC, PCN). Dal momento che essi hanno senso solo all’interno
di un processo di validazione, si è scelto di fornirne un’implementazione all’interno
di un parser XML open source esistente: Xerces [xer08]. Per la precisione il prototipo del Prodotto Cartesiano è stato integrato all’interno di una versione “hacked ”
di Xerces che ospita un prototipo di validatore SchemaPath, in modo da disporre in
partenza di un meccanismo di validazione completo di assegnamento condizionale,
pronto per i test.
La versione di Xerces usata per il prototipo SchemaPath è la 2.7.4. In primo luogo
dunque è stato effettuato un avanzamento delle API del parser all’ultima versione
disponibile (2.9.1). Inoltre è stato adattato il parsing alla sintassi di CTA, in quanto
SchemaPath adotta una sintassi XML differente. In seguito è stata progettata una
interfaccia per le feature introdotte, in particolare un meccanismo di pre-processing
del modello ad oggetti di uno schema, implementata dalla classe che realizza il prodotto cartesiano. É stato realizzato inoltre un meccanismo di semplificazione dei
predicati XPath, in modo da ridurre il carico sulla validazione. Infine i componenti
introdotti sono stati integrati prima in un validatore di test creato appositamente,
e poi nel validatore SchemaPath.
Un’ultima fase riguarda la creazione di una piattaforma di test, sul modello della
testsuite di XML Schema[TTC07], comprensiva di una serie di gruppi di test, atti
alla verifica della correttezza dei meccanismi realizzati.
Per prima cosa illustreremo brevemente le XML Schema API, soffermandoci in particolare sulle componenti principali dell’XSModel. In seguito passeremo a descriverne
l’implementazione all’interno di Xerces, mostrando i cambiamenti effettuati per fare
spazio a CTA. Passeremo poi a descrivere l’architettura globale delle API proposte,
descrivendo alcune delle principali classi e mostrando in che modo possono esse49
50
4. Implementazione
re utilizzate. Descriveremo poi la piattaforma di test realizzata, spiegando i test
proposti.
4.1
Xerces e XML Schema API
La rappresentazione interna di un’istanza di schema XSDL, così come i suoi processi di validazione, aderisce in Xerces alla specifica di XML Schema API[Lit04]. Le
XML Schema API forniscono un’interfaccia, indipendente dal linguaggio, cui fanno
riferimento i processi di validazione. Principalmente questa specifica fornisce quattro
categorie di interfacce, in base alla loro funzionalità:
• un modello per la rappresentazione e per la manipolazione delle Schema Component, detta anche XSModel ;
• un’interfaccia per l’accesso e la modifica del contributo della validazione sugli
elementi dei documenti d’istanza;
• un’interfaccia che si occupa della regolamentazione del caricamento di uno
schema, inteso come risorsa, e della creazione della relativa rappresentazione;
• una serie di strutture dati ausiliarie, quali: liste, mappe, set.
Xerces implementa pienamente queste API. Per quanto riguarda il prototipo realizzato tuttavia ci interessa solo una parte dell’interfaccia, in particolare XSModel,
in quanto esso non è coinvolto direttamente nella fase di validazione. Di seguito saranno presentate le classi principali, evidenziando i cambiamenti necessari effettuati
per adeguare l’API a CTA.
4.1.1
XSModel
XSModel è il modello di rappresentazione di uno schema. Esso ospita una struttura
dati di tipo grafo (lo schema), i cui ogni nodo è rappresentazione di una schema component. Ogni particolare schema components implementa l’interfaccia di XSObject,
che racchiude appunto tutte le proprietà comuni ad esse. In particolare qualunque
XSObject possiede una proprietà che consente di identificare il tipo particolare della componente ed il nome ed il namespace cui essa fa riferimento. Ad esempio la
dichiarazione dell’elemento <elem> nello schema:
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema"
targetNamespace="www.example.org/elem">
4.1 Xerces e XML Schema API
<xs:element name="elem"/>
</xs:schema>
Sarà rappresentata da un XSObject che ha proprietà:
• name = “elem”;
• namespace = “www.example.org/elem”;
• type = ELEMENT_DECLARATION;
Ogni schema component dunque ha una relativa interfaccia nel XSModel. Nell’implementazione fornita da Xerces ad ogni XSObject specificato nelle API è associata
una interfaccia, e le componenti che hanno una specifica rappresentazione XML presentano una classe concreta che implementa le interfacce specificate dai supertipi,
ovvero le componenti di cui sono un tipo specifico. Ad esempio una dichiarazione
di elemento, secondo le specifiche di Schema 1.0 e 1.1, è un tipo particolare di term
component. Dunque l’interfaccia di una element declaration è estesa dalla relativa
interfaccia XSTerm oltre che da quella di XSObject.
Dunque in quanto in XSDL 1.1 è stata introdotta la schema component alternative
type, con lo scopo di rappresentare un assegnamento di tipo alternativo, in modo
analogo sono state introdotte durante la realizzazione del prototipo un’interfaccia
XSAlternativeTypeDefinition e la sua implementazione XSAlternativeTypeDef
nell’XSModel. Per lo stesso motivo si sono rese necessarie alcune modifiche all’interfaccia di XSElementDeclaration. Nello specifico è stato introdotto il metodo
getTypeTable() per ottenere la type table associata alla dichiarazione di elemento, ed un metodo hasConditionalType() attraverso cui è possibile sapere se la
dichiarazione di elemento racchiude alternative.
Costruzione dell’XSModel
L’XSModel è costruito in Xerces a partire da un DOM document. Il DOM è attraversato in una visita da differenti traverser, oggetti che hanno il compito di creare ed
assemblare le varie componenti a seconda della loro rappresentazione XML. Esiste
un traverser per ogni component. Le chiamate dei traverser seguono l’annidamento
delle componenti stesse. Ad esempio durante la visita di un nodo di tipo dichiarazione di elemento, il rispettivo traverser, XSDElementTraverser, invocherà il traverser
XSDComplexTypeTraverser qualora incontrerà un elemento DOM <complexType>
tra i figli di quello corrente.
51
52
4. Implementazione
Per la costruzione delle XSAlternativeTypeDefinition è stato realizzato il traverser relativo (AlternativeTypeDefinitionTraverser), che è invocato all’occorrenza di ogni nodo <alternative> dal traverser XSDElementTraverser, opportunamente modificato.
Estensione dei tipi primitivi
Per quanto riguarda CTA inoltre XSDL fa riferimento a due nuovi tipi semplici: xs:error, di cui si è già parlato in sez. 2.2.2, e xs:xpathDefaultNamespace.
Sono stati creati dunque due rispettivi data-type validator in Xerces. Il validatore per xs:error chiaramente lancia sempre un eccezione di valore non valido.
Il validatore per xs:xpathDefaultNamespace invece si comporta allo stesso modo di quello di xs:anyUri ed accetta inoltre anche i valori: ##defaultNamespace,
##targetNamespace e ##local.
Implementazione dei vincoli di correttezza dello schema
Al fine di riprodurre correttamente i meccanismi specificati in XSDL per quanto riguarda CTA, sono stati realizzati i vincoli sulle componenti introdotte, appartenenti
a due categorie: vincoli sulla rappresentazione XML delle componenti e regole di
validità dello schema.
Per quanto riguarda la prima classe di vincoli ci riferiamo alle regole del tipo: un
elemento <alternative> deve necessariamente possedere un attributo type o in
alternativa un elemento <complexType> o <simpleType>. Eventuali violazioni nella rappresentazione XML sono rilevate dai rispettivi traverser in fase di costruzione
degli XSObject. Viceversa le regole di validità dello schema sono implementate all’interno dei metodi di una classe già esistente in Xerces, che ha il compito di verificare
appunto la correttezza dello schema: XSConstraints. In particolare sono stati implementati controlli di corretta restrizione tra il declared type di una dichiarazione
di elemento e i tipi condizionali presenti nella sua type table. Inoltre è stato esteso
il vincolo Element Declarations Consistent in presenza di dichiarazioni condizionali:
nello stesso content model non possono apparire due dichiarazioni condizionali con
stesso nome e namespace, a meno che non abbiano stesso tipo e se presente, stessa
type table.
4.2 Architettura globale
4.2
Architettura globale
In questa sezione presenteremo l’architettura progettuale del prototipo. Saranno descritti in modo generale i modelli per realizzare il Prodotto Cartesiano in Xerces. In
particolare saranno descritte le classi e le interfacce introdotte motivandone la loro
necessità e mostrandone le loro caratteristiche funzionali.
Per prima cosa va detto che ogni componente è integrata in Xerces con un impatto
minimo sul codice esistente. I file dell’implementazione risiedono tutti in un package
java separato: cta. Sono stati adottati diversi accorgimenti in questo senso, ad esempio l’uso di traverser sul XSModel, per implementare operazioni sulle componenti,
piuttosto che la modifica delle interfacce stesse.
4.2.1
Visita generica del XSModel
Ogni lavoro sull’XSModel richiede una visita del grafo che esso rappresenta. A questo scopo è stato realizzato un meccanismo generico di visita delXSModel basato sul
pattern observer, presente nel package cta.traversers. Un traverser, rappresentato
dall’interfaccia ObservableXSModelTraverser, si occupa di navigare il modello e di
sollevare un evento alla visita di ogni componente. Altri oggetti, che sono registrati
sul traverser come listener, si occupano di gestire l’evento svolgendo le operazioni
sugli XSObject. In questo modo il comportamento della visita è separato dalla navigazione del modello. Si noti che, secondo questo meccanismo, è possibile mettere
in pipeline differenti listener, così da realizzare una sequenza di operazioni differenti
in classi separate, ed imporre un ordine nella loro applicazione sulle singole componenti.
L’ordine di visita è imposto dalle sottoclassi di ObservableXSModelTraverser, in
particolare per il prototipo è stato implementato nella classe XSModelDFS l’ordine
depth-first-search(DFS). La classe XSObjectTraversedEvent rappresenta l’evento
relativo alla navigazione di una componente. In quanto tale esso contiene un riferimento all’XSObject relativo. Ogni listener per gli eventi XSObjectTraversedEvent
deve implementare invece l’interfaccia XSObjectTraversingListener.
Per quanto riguarda la creazione degli oggetti di tipo ObservableXSModelTraverser
non è stato realizzato nessun meccanismo specifico. I traverser sono infatti un meccanismo di basso livello, dunque non sono fatti per comparire nel codice client. Inoltre
a causa della presenza di uno stato non è possibile vincolare l’esistenza di un traverser ad una singola istanza, allorchè sarebbe stata una buona scelta farlo. Viceversa
non è previsto un elevato numero di traverser durante l’esecuzione e quindi sono
state scartate ipotesi quali clonazione e prototype.
53
54
4. Implementazione
4.2.2
Gerarchia dei tipi
La componente XSTypeDefinition di XSModel possiede un riferimento al tipo base. Il Prodotto Cartesiano però ha bisogno di percorrere la gerarchia in maniera
top-down, per questo è necessario creare una struttura ad albero che consenta di
attraversare la gerarchia dei tipi in quest’ordine. Anche in questo caso si è scelto chiaramente di adottare un modello separato, lasciando inalterato l’XSModel. Le
classi relative a questo modello si trovano nel package cta.typehierarchy.
La gerarchia di tipi è dunque un albero i cui nodi sono istanze di TypeHierarchyNode.
TypeHierarchyNode è un’interfaccia che consente l’accesso alla relativa dichiarazione di tipo e la navigazione dell’albero. Allo scopo di ottenere un comportamento
modulare, separando la gerarchia dalle operazioni effettuate su di essa, è stato adottato il pattern visitor : ogni nodo espone un metodo accept() che ne consente la
visita.
TypeHierarchyNode è implementata da due sottoclassi: SimpleTypeNode, che rappresenta una dichiarazione di tipo semplice, e ComplexTypeNode, che rappresenta
una dichiarazione di tipo complesso. Attraverso la classe TypeHierarchy è possibile
infine accedere ad una gerarchia di tipi attraverso un riferimento alla sua radice.
La creazione della gerarchia di tipi è effettuata a partire da un XSModel ed è un procedimento complesso. A questo scopo assolve la factory TypeHierarchyFactory.
Il compito specifico della creazione della gerarchia è effettuato attraverso l’uso di
XSModelDFS dalla classe TypeHierarchyBuilder. Una considerazione importante al
proposito va fatta nel caso in cui si voglia estendere una gerarchia esistente con i tipi
appartenenti ad un nuovo XSModel. Per questa situazione TypeHierarchyBuilder
è inteso come oggetto state-full, che mantiene un riferimento alla gerarchia creata,
e un set dei tipi in essa presenti. In questo modo, ogni volta che viene invocato il processo di costruzione su un XSModel, TypeHierarchyBuilder aggiungerà i
nuovi nodi alla gerarchia esistente, senza il rischio di duplicazioni. Ogni istanza di
TypeHierarchyBuilder può essere riutilizzata, per costruire una gerarchia completamente nuova, invocando il metodo reset().
TypeHierarchyFactory dunque assolve a due compiti fondamentali: la creazione
diretta di oggetti di tipo TypeHierarchy a partire da un XSModel e l’istanziazione
di oggetti di tipo TypeHierarchyBuilder, in modo da consentire la creazione di
gerarchie su XSModel differenti.
4.2 Architettura globale
4.2.3
XNI e SchemaPreprocessor
XNI(Xerces Native Interface), interfaccia di Xerces per la costruzione di parser,
consente di costruire pipeline di componenti coinvolti nel processo di parsing e validazione dei documenti XML. Sulla base di quest’interfaccia sono costruiti dunque i
parser SAX e DOM. XNI specifica un’architettura ad eventi, simile a quella di SAX,
al verificarsi dei quali ogni componente del processo di parsing invoca l’handler per
l’evento della componente successiva. La prima componente della pipeline sarà ovviamente uno scanner XML, che innesca il meccanismo.
Questo meccanismo consente di riutilizzare le stesse componenti all’interno di parser
di natura differente.
Ogni validatore in Xerces costituisce una componente per un parser. Si è posto
dunque il problema di fare spazio al Prodotto Cartesiano e più in generale di come processare lo schema prima della validazione e rendere tale procedura riutilizzabile in validatori differenti. Questo compito è delegato alle classi dell’interfaccia
SchemaPreprocessor. Le istanze di SchemaPreprocessor sono incaricate quindi di
processare lo schema, ad esempio per effettuare analisi e ottimizzazioni in dipendenza del particolare algoritmo di validazione. Chiaramente queste operazioni non
possono essere effettuate sempre al caricamento dello schema, poichè variano da validatore a validatore. Tuttavia non è giusto neanche implementarle tutte all’interno
del validatore stesso, in quanto sarebbe ridotta la modularità e la riusabilità del
codice. Per questo si è scelto di creare una classe apposita.
Attraverso SchemaPreprocessor sono implementati, ad esempio, sia il Prodotto
Cartesiano che la semplificazione dei predicati XPath.
Dato che nella fase di pre-processing dello schema è possibile creare strutture dati
da usare durante la validazione, anche le istanze di SchemaPreprocessor sono state
intese come oggetti state-full. Tuttavia lo stato dell’oggetto è diverso a seconda del
suo sottotipo. Per permettere al codice client di accedere allo stato senza dover conoscere il particolare tipo concreto di SchemaPreprocessor, nell’interfaccia è stato
introdotto un metodo getStateByName(String id), il cui scopo è quello di ritornare un generico oggetto di stato associato con l’identificatore id.
In modo analogo sono stati introdotti dei metodi generici per accedere e modificare
le proprietà dell’oggetto. In questo modo è possibile ad esempio settare un flag per
abilitare la stampa di informazioni di debug ed più in generale modificare il comportamento dei pre-processor senza dover usare i metodi specifici delle sottoclassi. É
stata inoltre introdotta un’interfaccia PreprocessorSequence, che estende direttamente SchemaPreprocessor e rappresenta una composizione di più pre-processori.
Essa consente di poter effettuare una sequenza di operazioni distinte su un XSModel
55
56
4. Implementazione
attraverso l’invocazione di un solo metodo.
Creazione di SchemaPreprocessor concreti
Il compito di creare oggetti di tipo SchemaPreprocessor è delegata alla factory
PreprocessorFactory, realizzata come singleton, che si occupa della creazione sia
di singoli sottotipi di SchemaPreprocessor che di sequenze. Poichè però la factory
non conosce direttamente i sottotipi da istanziare, l’istanziazione avviene attraverso
reflection.
I metodi createSchemaPreprocessor e createPreprocessorSequence istanziano
i sottotipi di SchemaPreprocessor in base ad identificatori passati come argomento,
che sono i nomi semplici delle sottoclassi, effettuando un look-up per le classi corrispondenti nel package cta.preprocessor.impl.
Per comprendere meglio la flessibilità di questo meccanismo consideriamo la situazione nel prototipo: un validatore, al caricamento dello schema, deve semplificare
gli XPath presenti nello schema e poi applicare l’algoritmo del prodotto cartesiano.
Fatto ciò, durante la validazione vuole accedere alle type table ricavate per assegnare
il tipo ad un elemento. Nel package cta.preprocessor.impl sono presenti dunque
gli SchemaPreprocessor:
• CartesianProductPreprocessor, che applica il prodotto cartesiano ricavando
una mappa di type table ristrutturate.
• CTAXPathRewriterPreprocessor, che semplifica e riscrive tutti i predicati
XPath banali presenti nello schema.
Il compito precedentemente illustrato può essere assolto dal seguente frammento di
codice nel validatore:
...
PreprocessorFactory pf = PreprocessorFactory.getInstance();
PreprocessorSequence ps =
pf.createPreprocessorSequence(
new String[]{"CTAXPathRewriterPreprocessor",
"CartesianProductPreprocessor"});
XSModel model = loadSchema();
ps.processModel(model);
//now we must retreive the result of the Cartesian Product:
SchemaPreprocessor cp = ps.getComponentProcessors().get(1);
4.3 Prodotto Cartesiano
Map typeTableMap = (Map) cp.getStateByName("typeTableMap");
...
4.2.4
Semplificazione degli XPath
La forma sintattica delle espressioni XPath all’interno dello schema è rilevante in
termini di lavoro al momento della validazione. Considerando che a run-time può
essere necessario valutare più volte gli stessi predicati si è deciso di implementare
un meccanismo di riscrittura e semplificazione delle espressioni XPath. I casi d’uso
ipotizzati in questo caso sono due. Il primo è strettamente correlato con il Prodotto
Cartesiano: la semplificazione contribuirebbe ad accorciare le espressioni all’interno delle type table processate, che per costruzione sono molto lunghe e potrebbero
contenere predicati banali. Un secondo caso d’uso è quello che coinvolge la semplificazione di tutti gli XPath durante la fase statica a prescindere dal Prodotto
Cartesiano, considerato come generica ottimizzazione del processo di valutazione a
run-time.
L’implementazione di questo meccanismo è contenuta nel package cta.rewrite.
L’interfaccia principale di questo meccanismo è costituita da Rewriter. Gli oggetti
di questo tipo espongono due soli metodi reset e rewrite. In particolare questo
secondo metodo è incaricato di effettuare una riscrittura di un’espressione XPath.
Questa interfaccia, come tutto il meccanismo, fa riferimento al modello per le espressioni XPath presente in Xerces. In particolare il metodo rewrite lavora su oggetti di
tipo ExpressionOwner, una classe pensata appositamente per consentire riscritture.
Nelle API di Xerces la classe XPath inoltre implementa ExpressionOwner, dunque
è possibile riscrivere direttamente gli oggetti XPath contenuti nelle type alternative.
Un’implementazione di quest’interfaccia è data dalla classe DefaultRewriter. Questa provvede alla riscrittura dei predicati logici and, or, e not. Le rispettive regole
di riscrittura sono riportate in tabella 4.1.
4.3
Prodotto Cartesiano
Come già accennato l’algoritmo del Prodotto Cartesiano viene richiamato in entrambe le varianti proposte (PC e PCN) dalla la classe CartesianProductPreprocessor.
Tuttavia la sua implementazione è espressa nella classe CartesianProductVisitor
che è un visitor per la gerarchia dei tipi. In pratica l’algoritmo viene applicato
in una visita dei nodi corrispondenti ai complex type della gerarchia. Per questo
CartesianProductPreprocessor deve provvedere a creare la gerarchia ed aggior-
57
58
4. Implementazione
(a) and
(b) or
And
a∧a→a
a ∧ ¬a → f alse
¬a ∧ a → f alse
a ∧ f alse → f alse
f alse ∧ a → f alse
a ∧ true → a
true ∧ a → a
true ∧ true → true
f alse ∧ f alse → f alse
true ∧ f alse → f alse
f alse ∧ true → f alse
Or
a∨a→a
a ∨ ¬a → true
¬a ∨ a → true
a ∨ f alse → a
f alse ∨ a → a
a ∨ true → true
true ∨ a → true
true ∨ true → true
f alse ∨ f alse → f alse
true ∨ f alse → true
f alse ∨ true → true
(c) not
not
¬f alse → true
¬true → f alse
Tabella 4.1: Regole di riscrittura dei predicati implementate nella classe
DefaultRewriter
narla ogni volta che viene chiamato su un XSModel. Una volta ottenuta la gerarchia dei tipi esso può invocare il visitor sulla radice innescando l’algoritmo. La
variante dell’algoritmo può essere selezionata come proprietà del pre-processor attraverso l’apposita chiave riferita dall’URI http://web.cs.unibo.it/~mcasimir/
cp-properties#normalize. Il valore della proprietà è un oggetto di tipo Boolean
attraverso cui si specifica se abilitare o meno la normalizzazione.
Le type table riscritte vengono memorizzate ed indicizzate secondo il complex type e
la dicharazione cui fanno riferimento in una mappa. Nello specifico tale mappa è un
oggetto di tipo java.util.Map che lega una dichiarazione di tipo complesso ad una
seconda mappa contenente l’associazione tra dichiarazione di elemento, intesa come
stringa della forma “namespace:name” con la corrispondente type table processata,
ovvero un oggetto di tipo XSObjectList. L’accesso alla mappa è consentito attraverso il metodo getStateById invocato con paramentro “typeTableMap”. Durante
la visita di un tipo complesso, non visitato in precedenza, si attraversa il content
model e per ogni dichiarazione di elemento incontrata:
1. Si cerca nella mappa delle type table processate la tabella della dichiarazione
corrispondente nel complex type base, se non ce n’è una affinchè lo schema
sia valido deve essere presente una wildcard relativa alla dichiarazione cercata,
dunque si cerca la dichiarazione top-level corrispondente. Qualora non venga
trovata si memorizza la type table corrente nella mappa e si continua con la
4.4 Test
59
prossima dichiarazione dal momento che, se lo schema è corretto, in questo
caso non è necessario effettuare alcuna operazione.
2. Ottenute le due type table si applica il Prodotto Cartesiano.
3. Se la normalizzazione e abilitata si effettua la normalizzazione della tabella
risultante.
4. La tabella processata viene memorizzata nella mappa delle type table
4.4
Test
Durante la realizzazione del prototipo sono stati realizzati numerosi test riguardanti
sia le specifiche componenti, con test mirati effettuati attraverso il framework JUnit,
che il funzionamento globale dei meccanismi realizzati, con una suite di test sul
modello della testsuite di XML Schema, accompagnata da una interfaccia grafica
minimale.
4.4.1
Parser e validatore di test
In primo luogo sono stati realizzati un parser ed un validatore di test, nelle classi
cta.CTAParser e CTAXMLSchemaValidator. Il parser è un parser SAX che include
semplicemente il validatore di test nella propria pipeline. Il validatore usato invece è
costruito sul validatore XML Schema di Xerces, con la sola eccezione che allo start
element assegna i tipi secondo CTA utilizzando le type table riscritte dal Prodotto
Cartesiano.
4.4.2
Integrazione in SchemaPath
Una seconda importante modalità di test è stata effettuata attraverso l’inclusione
del Prodotto Cartesiano nel processo di validazione di SchemaPath. Nel validatore esistente è stato per questo richiamato il pre-processor che applica il Prodotto
Cartesiano sullo schema al momento del suo caricamento.
4.4.3
TestSuite
La testsuite di XML Schema è strutturata in modo da automatizzare i test per la
validazione di schemi XSDL. Fondamentalmente una test suite è costituita da una
serie di coppie schema-istanza, che costituiscono l’oggetto dei test, e da una descrizione XML dei test (test set), che comprende indicazioni circa i file coinvolti, sulla
60
4. Implementazione
documentazione e soprattutto sul risultato atteso per i test.
Un test set è organizzato in test group, ovvero gruppi di test accomunati da una particolare caratteristica da verificare. Ogni test group racchiude una serie di elementi
<schemaTest> e <instanceTest>. Poichè il comportamento dei test varia a seconda
del particolare gruppo, la grammatica del file di descrizione è stata modificata in
modo che gli elementi <testGroup> contengano un attributo type di tipo anyUri.
In questo modo il comportamento delle procedure di test è deciso univocamente all’interno del file di descrizione test set. Parallelamente all’interno del modello per i
test è stata creata una classe TestDriver per ogni tipo di gruppo. Ognuna di esse
è associata ad un URI relativo ad un test group.
Le classi che realizzano la piattaforma di test sono racchiuse all’interno del package
it.unibo.cs.web.mcasimir.cta.test.testsuite.
Di seguito saranno descritti i gruppi di test presenti nel test set.
Correttezza dello schema
Il test di correttezza dello schema, implementato dalla classe SchemaCheckingTest,
carica uno schema ed abilita il controllo totale dei vincoli.
Correttezza del Prodotto Cartesiano
I test di correttezza del Prodotto Cartesiano fanno riferimento ad una serie di schemi,
che racchiudono gerarchie di derivazione per restrizione, più o meno complesse, con
dichiarazioni condizionali. La classe che effettua questo test è CartesianProductTest,
essa non fa altro che caricare lo schema e invocare il metodo processModel di
CartesiaProductPreprocessor sul XSModel risultante, stampando la struttura delle type table prima e dopo il processing.
Validazione
I test della validazione sono stati eseguiti sia attraverso il validatore di test che
attaverso il validatore SchemaPath. La procedura di test prevede il parsing delle
istanze attraverso un parser che include uno di questi validatori nella pipeline. A
seconda del validatore utilizzato questi test sono effettuati dagli oggetti di classe
InstanceValidationTest e SchemapathValidationTest.
4.5 Limitazioni
4.5
Limitazioni
Le limitazioni di questo prototipo riguardano principalmente la dipendenza dal modello per espressioni XPath 1.0 di Xerces. Infatti al fine di aderire correttamente alle
specifiche XSDL 1.1 dovrebbe essere gestita la sintassi XPath 2.0, tuttavia visto lo
scarso numero di implementazioni esistenti, e il suo mancato supporto in SchemaPath si è scelto di adottare il modello di Xerces, basato ancora sulle specifiche della
versione 1.0.
61
Capitolo 5
Conclusioni
In questo lavoro abbiamo mostrato che è possibile verificare i vincoli di restrizione
con CTA attraverso una tecnica parzialmente statica, enumerando tutte le possibili
situazioni a run-time: il Prodotto Cartesiano.
Per prima cosa abbiamo esaminato una serie di tecniche alternative, tra cui abbiamo
presentato sia soluzioni statiche che dinamiche. In merito alle soluzuioni statiche ne
abbiamo considerate alcune che, attraverso restrizioni sintattiche, impediscono la
scrittura di schemi potenzialmente scorretti.
La più importante di esse è Prefix che risolve il problema imponendo la ripetizione
delle type table come prefisso delle type table ristrette. Abbiamo mostrato come questa tecnica limiti in maniera eccessiva l’esspressività dei costrutti per Conditional
Type Assignment. Inoltre una seconda proposta, simile, vincola la struttura delle
type table lungo la catena di restrizione. Ovvero impone che ogni dichiarazione di
elemento che compaia in un tipo derivato per restrizione, abbia la stessa type table
della corrispettiva dichiarazione nel tipo base: stesso numero di alternative, stessi
predicati e tipi assegnati ristretti. Chiaramente questa soluzione manca di espressività ancora più di Prefix.
Abbiamo dunque analizzato una soluzione, totalmente dinamica, che non impone
limiti sintattici. La relativa tecnica di verifica è chiamata Run-time Check (RTC) ed
è stata formalizzata in un algoritmo scaturito dalla definizione del vincolo Conditional Type Substitutable in Restriction, presente nelle specifiche di XSDL 1.1.
RTC ravvisa le condizioni che violano le relazioni di corretta restrizione al momento
della validazione ed in dipendenza dal contesto. A tempo di validazione si dispone
del documento d’istanza, dunque una volta assegnato il tipo in base al contesto e
63
64
5. Conclusioni
secondo una dichiarazione di elemento, RTC provvede a controllare che esso non
violi le restrizioni. A questo proposito abbiamo fatto notare che, poichè le relazioni
di restrizione sono proprietà dello schema, è poco conveniente verificare tali relazioni
man mano che si processono gli elementi del documento di istanza.
Per Run-time Check abbiamo dunque fornito un algoritmo in pseudo-codice e mostrato il costo computazionale. In particolare abbiamo mostrato che la verifica è
lineare nella profondità della catena di derivazione.
Abbiamo quindi proposto la tecnica del Prodotto Cartesiano, che effettua i controlli di restrizione in maniera statica enumerando ed analizzando tutte le possibili
situazioni che si possono verificare durante la validazione. Il Prodotto Cartesiano
deriva da questa analisi un nuovo insieme di type table, che assegnano tipo xs:error
in presenza di situazioni erronee. Queste nuove type table saranno utilizzate a runtime dal validatore per assegnare il tipo agli elementi al posto di quelle originali.
Abbiamo mostrato in che modo vengano costruite le type table e che questo processo ha costo quadratico in termini di spazio e tempo. Inoltre abbiamo esaminato il
costo complessivo dell’algoritmo e mostrato come esso sia proporzionale al prodotto
delle type table presenti in una catena di derivazione, data l’enumerazione di tutte
le situazioni. Abbiamo inoltre definito il numero di predicati all’interno delle type
table risultato in funzione di quelli racchiusi nelle type table originali.
Al fine di ridurre il costo computazionale dell’algoritmo abbiamo introdotto alcune
proprietà delle type table. Nello specifico abbiamo definito il concetto di type table
deterministica, ovvero una type table per cui un solo predicato sia soddisfacibile, e
di type table normalizzata, ovvero una type table in cui non ci sono tipi ripetuti.
Abbiamo dunque mostrato alcune relazioni di equivalenza semantica tra type table
e una tecnica di normalizzazione.
In seguito abbiamo dunque mostrato una variante del Prodotto Cartesiano, PCN,
che effettua una normalizzazione parziale delle tabelle. Abbiamo messo in evidenza come, attraverso questa pratica, il costo dell’intera procedura in fase statica sia
ridotto nel tempo ad una funzione quadratica nella profondità della gerarchia di derivazione. Abbiamo quindi fornito dunque una relazione tra il numero di condizioni
XPath presenti nello schema e quelle presenti nelle type table ristrutturate in questa
maniera, da cui se ne deduce il costo computazionale introdotto a run-time.
Abbiamo mostrato infine una comparazione tra PC, PCN e RTC in base ai costi di
assegnamento dei tipi per un elemento nel caso pessimo.
5.1 Sviluppi futuri
É stato inoltre realizzato un prototipo in java degli algoritmi PC e PCN integrato
nella versione 2.9.1 di Xerces insieme ad un validatore SchemaPath.
In base ai risultati ottenuti concludiamo che una verifica parzialmente statica dei
vincoli di restrizione con CTA è possibile. Tuttavia visto il costo della enumerazione
delle condizioni essa non è attuabile in una situazione generica.
5.1
Sviluppi futuri
La verifica a tempo di compilazione della corretta restrizione fornisce numerosi vantaggi. Innanzitutto l’autore dello schema è messo nelle condizioni di ravvisare alcune
situazioni impreviste in cui i vincoli sono violati, e in secondo luogo essa riduce il
carico dell’assegnamento dei tipi in fase di validazione. Sarebbe interessante a tale
proposito indagare soluzioni differenti. Ad esempio studiando la possibilità di vincoli
sintattici che impediscano le violazioni senza ridurre l’espressività del meccanismo.
65
Bibliografia
[BBC+ 07]
Anders Berglund, Scott Boag, Don Chamberlin, Mary F. Fernández, Michael Kay, Jonathan Robie, and Jérôme Siméon. Xml path language (xpath) 2.0. http://www.w3.org/TR/xpath20, W3C
Recommendation, 23 January 2007.
[BPSM+ 06] T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, and F. Yergeau.
Extensible markup language (xml) 1.0 (fourth edition). http://www.
w3.org/TR/REC-xml, W3C Recommendation, 16 August 2006.
[CM01]
J. Clark and M. Murata. RELAX NG Specification. http://relaxng.
org/, Dicembre 2001.
[CMV04]
Claudio Sacerdoti Coen, Paolo Marinelli, and Fabio Vitali. Schemapath, a minimal extension to xml schema for conditional constraints. In
WWW ’04: Proceedings of the 13th international conference on World
Wide Web, pages 164–174, New York, NY, USA, 2004. ACM.
[ea02]
S. Pemberton et al. Xhtml 1.0 the extensible hypertext markup
language (second edition). http://www.w3.org/TR/xhtml1/, W3C
Recommendation, 1 Agosto 2002.
[GSMT07] S. Gao, C. M. Sperberg-McQueen, and H. S. Thompson. W3C XML
Schema Definition Language (XSDL) 1.1 Part 1: Structures. http:
//www.w3.org/TR/xmlschema11-1/, W3C Working Draft, 30 Agosto
2007.
[Jel02]
R. Jelliffe. The schematron assertion language 1.5. http://xml.ascc.
net/resource/schematron/Schematron2000.html, Ottobre 2002.
[Kay07]
Michael Kay. Xsl transformations (xslt) version 2.0. http://www.w3.
org/TR/xslt20, W3C Recommendation, 23 January 2007.
67
68
BIBLIOGRAFIA
[Lit04]
Elena Litani. XML Schema API. http://www.w3.org/Submission/
2004/SUBM-xmlschema-api-20040122/, W3C Member Submission, 22
January 2004.
[MVZ07]
P. Marinelli, F. Vitali, and S. Zacchiroli. Streaming validation of schemata: the lazy typing discipline. In In Proceedings of Extreme Markup Languages 2007: The Markup Theory and Practice Conference,
Montreal, Canada, 7 August 2007. IDEAlliance.
[NCEF02]
Christian Nentwich, Licia Capra, Wolfgang Emmerich, and Anthony
Finkelstein. xlinkit: a consistency checking and smart link generation
service. ACM Trans. Inter. Tech., 2(2):151–185, 2002.
[SM06a]
C. M. Sperberg-McQueen. Co-constraint use cases - esw wiki. The ESW
Wiki, official W3C wiki for discussing standard and specification, http:
//esw.w3.org/topic/Co-constraint_Use_Cases, 31 Marzo 2006.
[SM06b]
C. M. Sperberg-McQueen. Co-occurrence constraints - esw wiki. The
ESW Wiki, official W3C wiki for discussing standard and specification,
http://esw.w3.org/topic/Co-occurrence_constraints, 28 Marzo
2006.
[TBMM04] H. S. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. Xml schema part 1: Structures. http://www.w3.org/TR/xmlschema-1, W3C
Recommendation, 28 October 2004.
[TTC07]
Henry S. Thompson, John Tebbutt, and Tony Cincotta. XML Schema
Test Suite. http://www.w3.org/XML/2004/xml-schema-test-suite,
20 June 2007.
[xer08]
Xerces java parser readme. http://xerces.apache.org/xerces-j,
Febbraio 2008.
[Zin07]
Jacopo Zingoni. Introduzione di co-constraint nello schema for schema
1.1 normativo. Tesi di laurea universitá di Bologna, 2007.