Interrogazione Efficiente di Documenti XML Interrogazione Efficiente di Documenti XML Temporali e una sua Applicazione in Ambito Temporali e una sua Applicazione in Ambito
Normativo Normativo
Enrico RonchettiEnrico Ronchetti
Università degli Studi di Modena e Reggio Emilia Università degli Studi di Modena e Reggio Emilia
Facoltà di Ingegneria - Corso di Laurea in Ingegneria Informatica Facoltà di Ingegneria - Corso di Laurea in Ingegneria Informatica
Relatore:
Relatore:
Prof. Paolo Tiberio Prof. Paolo Tiberio
Correlatori:
Correlatori:
Dott. Federica Mandreoli Dott. Federica Mandreoli Ing. Riccardo Martoglia Ing. Riccardo Martoglia
Anno Accademico 2002/2003 Anno Accademico 2002/2003
Controrelatore:
Controrelatore:
Prof. Sonia Bergamaschi Prof. Sonia Bergamaschi
sviluppare un Temporal XML Query Processor per l’interrogazione efficiente di grandi quantità di documenti che soddisfano un modello XML temporale.
La presente Tesi di Laurea è stata svolta all’interno del Progetto Nazionale MIUR 2001: “La dinamica della norma nel tempo: aspetti giuridici e informatici”
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
Obiettivo della Tesi
tempo Testo
normativo originale
1
Modifiche : Temporali
Ad esempio:
Proroga di un termine 2
nuova
versione 3
nuova versione
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
comma articolo capo
articolato Sostituzione di una frase
Testuali
Dinamica del testo normativo
Risulta molto difficile conoscere l’esatta formulazione di una legge:
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:
2) Testuale 1) Strutturale
3) Temporale
Problema
2) Appartenente al Sistema Giuridico Italiano nel giorno Y 3) Applicabile a casi concreti nel giorno Z
1) Memorizzata nel Sistema Informativo nel giorno X
4) Come era al momento della sua pubblicazione sulla Gazzetta Ufficiale
Estensione temporale DTD pubblicata dal
progetto Norme In Rete
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 è Transaction time memorizzato nel database
•Valid time: rappresenta il tempo in cui la norma è in vigoreValid time
•Efficacy time: rappresenta il tempo in cui la norma è applicabile Efficacy time al caso concreto
•Publication time: rappresenta il tempo in cui il testo normativo Publication time viene pubblicato sulla gazzetta ufficiale
Gli attributi che individuano le 4 dimensioni temporali sono all’interno di ogni elemento (Temporal Attributes)TA
Modello XML temporale
2) Versione appartenente al Sistema Giuridico nel giorno Y 3) Versione applicabile a casi concreti nel giorno Z
1) Versione memorizzata nel Sistema Informativo nel giorno X4) Versione al momento della sua pubblicazione sulla Gazzetta Ufficiale
LEGGE ARTICOLO 1
COMMA 1
VER 1 TA
VER 1 TA
COMMA 2 ARTICOLO 2
importazione di cereali…
…testo X
VER 2 TA importazione
di cereali…
…testo Y FOR $a IN legge//comma//text()
WHERE contains( $a,
‘importazione AND cereali’) AND <vincoli temporali>
RETURN $a
Interrogazione scritta con XQuery:
Esempio di documento conforme al modello XML temporale
R E P O S I T O R Y
X M L X M L E N G I N E S T R A T U M
U S E R
Approccio precedente
R E P O S I T O R Y
X M L T E M P O R A L X M L Q U E R Y P R O C E S S O R
U S E R
Approccio in questa Tesi 2) testuali
…si parla di importazione di cereali…
3) temporali
…nella versione memorizzata nel Sistema il giorno 1/1/1980 e in modo che sia valida ed
applicabile fra il 1979 ed il 1981.
Architetture
1) componenti utilizzati 2) costi di comunicazione fra componenti 3) preprocessing e postprocessing Differenze:
1) strutturali
…le leggi in cui nel testo all’interno dei commi…
Vincoli:
Vista la possibilità di:
Associare i TA ad ogni livello della gerarchia (anche dove i TA non sono espressi)
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
Un set completo di attributi temporali per una caratterizzazione temporale completa
Si è ideata una struttura, che chiameremo Tupla, contenente:
Granularità:
Intero documento XML temporale
Tupla
IN GENERALE
Intero atto normativo
Disposizione Normativa IN AMBITO NORMATIVO
Suddivisione in Strutture Tupla (1)
D B
id a t t r 1 a t t r 2 a t t r 3
Tupla ( id,
) Ogni vincolo è verificato in fase di interrogazione sui rispettivi attributi STRUCTURAL JOIN: approccio in
letteratura che permette la risoluzione dei vincoli strutturali su documenti XML con il modello relazionale
< SET COMPLETO DI ATTRIBUTI
STRUTTURALI >,
< SET COMPLETO DI ATTRIBUTI
TEMPORALI >,
<TESTO>
Suddivisione in Strutture Tupla (2)
1) ALGORITMO PER LA LETTURA DELLE TUPLE DAL DB Grazie agli algoritmi ideati ed alla suddivisione effettuata è
possibile evitare un gran numero di accesi a disco inutili
R E P O S I T O R Y
X M L T E M P O R A L X M L Q U E R Y P R O C E S S O R
U S E R
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
legge comma text
T1 C1
1 SOLUZIONE L1
Algoritmi interni al Temporal XML Query Processor
È stato ideato per avere la certezza di generare risultati in cui COESISTANO tutte le Tuple coinvolte in una soluzione
Esempio sul
Transaction Time:
Legge Comma Text
Verificato Non verificato Può avvenire:
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
verifica dell’operatore OVERLAPS in almeno un chronon di ogni dimensione temporale del modello
Controllo di consistenza
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 per la generazione pseudo-casuale dei documenti XML temporali basati sul modello adottato
Dataset Documenti MB disco Tuple
1 5000 120 290000
2 10000 240 580000
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 (1)
1 2
1 2 0 M B 2 4 0 M B 4 8 0 M B
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
Il prototipo sviluppato (2)
• Stesso modello adottato
• Stessi documenti (5000 documenti su 120 MB)
• Stesse query
Tempi di risoluzione: Per alcune query i risultati sono comparabili, ma per altre la differenza è di più di un
ordine di grandezza
(scala logaritmica) Ogni interrogazione del
prototipo sviluppato nella presente Tesi richiede una quantità di memoria minima rispetto a quella richiesta nel sistema TeX
3400 ms 135000 ms
Confronto di efficienza con il sistema TeX
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
implementazione di server per rispondere ad interrogazioni su una grande base di dati XML temporale ad elevata multiutenza
sistema per l’interrogazione di testi normativi via internet
INTERNET
BROWSER
SISTEMA
