Università degli Studi di Modena e Reggio Emilia
Facoltà di Ingegneria - Corso di Laurea in Ingegneria Informatica
Interrogazione Efficiente di Documenti XML
Temporali e una sua Applicazione in Ambito
Normativo
Enrico Ronchetti
Relatore:
Correlatori:
Prof. Paolo Tiberio
Dott. Federica Mandreoli
Controrelatore:
Ing. Riccardo Martoglia
Prof. Sonia Bergamaschi
Anno Accademico 2002/2003
La presente Tesi di Laurea è stata svolta all’interno del Progetto
Nazionale MIUR 2001: “La dinamica della norma nel tempo: aspetti
giuridici e informatici”
Obiettivo della Tesi
sviluppare un Temporal XML Query Processor per l’interrogazione
efficiente di grandi quantità di documenti che soddisfano un modello
XML temporale.
APPLICAZIONE IN AMBITO NORMATIVO: si ritiene che un atto
normativo sia un valido esempio di documento “dinamico”, la cui
evoluzione passa attraverso successive modifiche che generano versioni
nel tempo
Dinamica del testo normativo
Testo
normativo
originale
1
nuova
versione
2
nuova
versione
3
tempo
Modifiche :
Ad esempio:
Temporali
Proroga di un termine
Testuali
Sostituzione di una frase
Le modifiche non sono applicate all’intero
documento, ma ad ogni livello della gerarchia
articolato-capo-articolo-comma, ed ognuna
influenza tutti i livelli sottostanti
articolato
capo
articolo
comma
Problema
Risulta molto difficile conoscere l’esatta formulazione di una legge:
1) Memorizzata nel Sistema Informativo nel giorno X
2) Appartenente al Sistema Giuridico Italiano nel giorno Y
3) Applicabile a casi concreti nel giorno Z
4) Come era al momento della sua pubblicazione sulla Gazzetta Ufficiale
Esempio: voglio tutte le leggi in cui nel testo all’interno dei commi si parla
di importazione di cereali, nella versione memorizzata nel Sistema il giorno
1/1/1980 e in modo che sia valida ed applicabile fra il 1979 ed il 1981.
Vincoli individuabili:
1) Strutturale
2) Testuale
3) Temporale
Modello XML temporale
DTD pubblicata dal
progetto Norme In Rete
Estensione
temporale
Modello XML temporale
per la descrizione di
testi normativi
mutevoli nel tempo
Le dimensioni temporali supportate:
•Transaction time: rappresenta il tempo in cui il testo normativo è
memorizzato nel database
•Valid time: rappresenta il tempo in cui la norma è in vigore
•Efficacy time: rappresenta il tempo in cui la norma è applicabile
al caso concreto
•Publication time: rappresenta il tempo in cui il testo normativo
viene pubblicato sulla gazzetta ufficiale
Gli
attributi
che individuano
4Informativo
dimensioni
temporali
sono
1)
memorizzata
nel
giorno
3)
Versione
applicabile
adella
casi
concreti
nel
giorno
Znel
2)
appartenente
al Sistema
Giuridico
nel
giorno
Y X Ufficiale
4)Versione
al momento
sua le
pubblicazione
sulla
Gazzetta
all’interno di ogni elemento TA (Temporal Attributes)
Esempio di documento conforme al modello XML temporale
LEGGE
Interrogazione scritta
con XQuery:
ARTICOLO 1
FOR $a IN legge//comma//text()
WHERE contains( $a,
‘importazione AND cereali’)
AND <vincoli temporali>
RETURN $a
VER 1
importazione
di cereali…
…testo X
VER 1
ARTICOLO 2
TA
COMMA 1
TA
VER 2
COMMA 2
TA
importazione
di cereali…
…testo Y
Architetture
USER
STRATUM
XML
ENGINE
Vincoli:
1) strutturali
…le leggi in cui nel testo
all’interno dei commi…
2) testuali
…si parla di importazione di
cereali…
3) temporali
XML
REPOSITORY
Approccio
precedente
…nella versione memorizzata
nel Sistema il giorno 1/1/1980 e in
modo che sia valida ed
applicabile fra il 1979 ed il 1981.
USER
TEMPORAL
XML QUERY
PROCESSOR
XML
REPOSITORY
Approccio in
questa Tesi
1) componenti utilizzati
Differenze: 2) costi di comunicazione fra componenti
3) preprocessing e postprocessing
Suddivisione in Strutture Tupla (1)
Vista la possibilità di:
Si è ideata una struttura, che
chiameremo Tupla, contenente:
Associare i TA ad ogni livello
della gerarchia (anche dove i
TA non sono espressi)
Un set completo di attributi temporali
per una caratterizzazione temporale
completa
Suddividere l’intero documento
in frazioni minori senza perdere
la gerarchia di base
Un set completo di attributi strutturali
per l’esatta collocazione della Tupla
all’interno del documento XML di
partenza
Granularità:
Intero documento XML temporale
Intero atto normativo
Tupla
Disposizione Normativa
IN GENERALE
IN AMBITO NORMATIVO
Suddivisione in Strutture Tupla (2)
STRUCTURAL JOIN: approccio in
letteratura che permette la risoluzione dei
vincoli strutturali su documenti XML con il
modello relazionale
Tupla ( id,
< SET COMPLETO DI
ATTRIBUTI
STRUTTURALI >,
id
attr1
attr2
attr3
< SET COMPLETO DI
ATTRIBUTI
TEMPORALI >,
<TESTO>
)
DB
Ogni vincolo è verificato
in fase di interrogazione
sui rispettivi attributi
Algoritmi interni al Temporal XML Query Processor
1) ALGORITMO PER LA LETTURA DELLE TUPLE DAL DB
USER
TEMPORAL
XML QUERY
PROCESSOR
XML
REPOSITORY
Grazie agli algoritmi ideati ed alla suddivisione effettuata è
possibile evitare un gran numero di accesi a disco inutili
Le tuple lette soddisfano completamente i vincoli strutturali,
testuali e temporali
2) ALGORITMO PER L’ELABORAZIONE DELLE TUPLE
LETTE
Si genera uno stack per ogni nodo nella query, rispettando
l’ordine di apparizione
Le tuple lette finiscono nel relativo stack e costituiscono le
soluzioni finali
1 SOLUZIONE
L1
C1
T1
legge
comma
text
Controllo di consistenza
È stato ideato per avere la certezza di generare risultati in cui
COESISTANO tutte le Tuple coinvolte in una soluzione
verifica dell’operatore OVERLAPS in almeno un
chronon di ogni dimensione temporale del modello
Esempio sul
Transaction Time:
Legge
Comma
Text
Può avvenire:
Verificato
Non verificato
1.
Al momento della formazione di ogni soluzione (controllo a
posteriori)
2.
Prima dell’inserimento di una tupla negli stack (controllo a priori)
Previene l’overflow degli
stack durante elaborazione
Il prototipo sviluppato (1)
Prototipo sviluppato in Java utilizzando Berkeley DB come database system
PC utilizzato: Athlon XP 2000+, HD EIDE 7200 RPM, 256 MB di RAM con
sistema operativo Windows XP
E’ stato realizzato un algoritmo
Dataset Documenti MB disco
Tuple
per la generazione pseudo-casuale
1
5000
120
290000
dei documenti XML temporali
2
10000
240
580000
basati sul modello adottato
3
20000
480
1160000
Query sottoposte al sistema (il
vincolo strutturale è
sempre presente):
1.
Q1 e Q2, solo vincoli
testuali
2.
Q3, solo vincoli temporali
3.
Q4 e Q5, vincoli temporali
e testuali
Il prototipo sviluppato (2)
Scalabilità:
Al crescere delle dimensioni del data set usato nei test:
•
I tempi di elaborazione crescono in modo sub-lineare per le query
con vincoli testuali, lineare per le altre; rimangono in ogni caso
molto contenuti
•
L’occupazione di memoria rimane pressochè costante per tutta la
durata dell’elaborazione e per tutte le query
1201MB
2 MB
240
480 MB
dimensioni dei data set utilizzati
Confronto di efficienza con il sistema TeX
•
Stesso modello adottato
•
Stessi documenti (5000 documenti su 120 MB)
3400 ms
Stesse query
135000 ms
•
Tempi di risoluzione: Per
alcune query i risultati sono
comparabili, ma per altre la
differenza è di più di un
ordine di grandezza
Ogni interrogazione del
prototipo sviluppato nella
presente Tesi richiede una
quantità di memoria minima
rispetto a quella richiesta nel
sistema TeX
(scala logaritmica)
Conclusioni
La realizzazione del Temporal XML Query Processor ha permesso di
interrogare grandi quantità di documenti XML temporali utilizzando le
metodologie messe a disposizione dalla tecnologia relazionale
L’elaborazione risulta molto efficiente sia in termini di velocità di
elaborazione sia in termini di occupazione di memoria, anche se
confrontata con i risultati avuti in altri sistemi.
minimo utilizzo di memoria
centrale del prototipo sviluppato
sistema per l’interrogazione di testi
normativi via internet
BROWSER
implementazione di server per
rispondere ad interrogazioni su
una grande base di dati XML
temporale ad elevata multiutenza
INTERNET
SISTEMA