Dipartimento di Matematica e Informatica - Tesi di Dottorato

Permanent URI for this collectionhttp://localhost:4000/handle/10955/103

Questa collezione raccoglie le Tesi di Dottorato afferenti al Dipartimento di Matematica e Informatica dell'Università della Calabria.

Browse

Filters

20142

Settings

Subject: search.filters.subject.Elaborazione dati

Search Results

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    DLVDB An ASP System for Data Intensive ApplicationsRisorsa elettronica
    (2014-04-01) Panetta, Claudio; Leone, Nicola; Terracina, Giorgio
    La rapida crescita di sistemi informatici derivanti dalle diverse applicazioni cui Internet si presta, ha rapidamente aumentato la quantit`a di dati e di informazioni disponibili per l’elaborazione. In particolare, l’affermarsi del commercio elettronico, il diffondersi di sistemi per l’e-government delle pubbliche amministrazioni, l’ormai avviato processo di digitalizzazioni degli archivi e dei documenti in essi contenuti, la disponibilit`a di database medici sempre pi`u completi e ricchi di informazioni e, pi`u in generale, il sempre maggiore utilizzo dei sistemi informatici per la gestione strutturata di grandi quantit`a di dati hanno evidenziato l’urgenza di sviluppare nuove tecnologie che consentano di elaborare automaticamente ed efficientemente la quantit`a di dati derivante da questi settori emergenti. Uno degli utilizzi principali dei sistemi di basi di dati (DBMS) consiste nella memorizzazione e nel recupero efficiente di grandi quantit`a di dati. L’elaborazione di tali informazioni, specialmente quella finalizzata all’estrazione di nuova conoscenza, `e ormai riconosciuta come una tematica di ricerca di fondamentale importanza sia nell’ambito delle basi di dati, sia nell’ambito della ricerca industriale, in quanto offre grandi opportunit`a di sviluppo. In tale scenario, applicazioni come “Data Mining”, “Data Werehousing” e “Online Analytical Processing (OLAP)” hanno ulteriormente evidenziato la necessit`a di sviluppare sistemi di basi di dati che supportino linguaggi maggiormente espressivi, in grado di consentire elaborazioni sempre pi`u raffinate delle informazioni contenute nei Database. Il complesso di tali esigenze ha portato alla definizione di diverse estensioni per i modelli di rappresentazione dei dati (Modelli Relazionali basati sul concetto degli Oggetti), nonch´e alla definizione di nuovi costrutti sintattici (ricorsione e costrutti OLAP), ed all’estenzione dei DBMS (DataBase Management Systems) con linguaggi di programmazione di alto livello, basati su UDF (User Defined Functions). Purtroppo, per`o anche i migliori sistemi di basi di dati attualmente in commercio non sono sufficientemente potenti e generali da poter essere efficacemente utilizzati per risolvere molte delle emergenti applicazioni. In generale, gli attuali DBMS non contengono i meccanismi di ragionamento necessari per estrarre conoscenza complessa dai dati disponibili. Tali meccanismi, dovrebbero essere in grado sia di gestire grandi quantit`a di informazioni, sia di realizzare sofisticati processi di inferenza sui dati per trarne nuove conclusioni. Le capacit`a di ragionamento necessarie a tale scopo possono essere fornite dai sistemi basati su linguaggi logici. La Programmazione Logica Disgiuntiva (DLP) `e un formalismo che consente di rappresentare, in maniera semplice e naturale, forme di ragionamento non monotono, planning, problemi diagnostici e, pi`u in generale, problemi di elevata complessit`a computazionale. In DLP, un programma `e una collezione di regole logiche in cui `e consentito l’uso della disgiunzione nella testa delle regole e la negazione nel corpo. Una delle possibili semantiche per tali programmi `e basata sulla nozione di modello stabile (answer set). Ad ogni programma viene associato un insieme di answer set, ognuno corrispondente ad una possibile visione del dominio modellato. i La DLP sotto tale semantica viene comunemente riferita con il termine di Answer Set Programming (ASP). Il recente sviluppo di efficienti sistemi basati sulla programmazione logica come DLV [80], Smodels [101], XSB [114], ASSAT [84, 86], Cmodels [62, 61], CLASP [56], etc., ha rinnovato l’interesse nei campi del ragionamento non-monotono e della programmazione logica dichiarativa per la risoluzione di molti problemi in differenti aree applicative. Conseguentemente, tali sistemi possono fornire le funzionalit`a di inferenza e ragionamento richieste dalle nuove aree di applicazione che interessano i sistemi di basi di dati. Tuttavia, i sistemi basati sulla programmazione logica presentano notevoli limitazioni nella gestione di grandi quantit`a di dati non essendo dotati dell’opportuna tecnologia per rendere efficiente la loro gestione poich´e eseguono le loro elaborazioni facendo uso di strutture dati gestite direttamente in memoria centrale. Inoltre, la maggior parte delle applicazioni di interesse comune coinvolge grandi moli di dati su cui applicare complessi algoritmi di inferenza logica difficilmente elaborabili sia dai sistemi di programmazione logica, sia dai tradizionali database. Queste considerazioni mettono in evidenza la necessit`a di tecniche efficienti ed efficaci che combinino le qualit`a dei sistemi di inferenza logica con quelle dei sistemi di gestione delle basi di dati. In letteratura, le proposte di soluzione a tale problema sono culminate nei Sistemi di Basi di Dati Deduttive (DDS) [25, 52, 23, 63], che combinano le due realt`a dei sistemi logici e dei DBMS. In pratica, i DDS sono il risultato di una serie di tentativi di adattare i sistemi logici, che hanno una visione del mondo basata su pochi dati, ad applicazioni su grandi moli di dati attraverso interazioni intelligenti con le basi di dati. In particolare, i DDS sono forme avanzate di DBMS i cui linguaggi di interrogazione, basati sulla logica, sono molto espressivi. I DDS non memorizzano solo le informazioni esplicite in un database relazionale, ma memorizzano anche regole che consentono inferenze deduttive sui dati memorizzati. L’uso congiunto di tecniche sviluppate nell’ambito delle basi di dati relazionali con quelle della programmazione logica dichiarativa, consente in linea di principio ai DDS di realizzare ragionamenti complessi su grandi quantit`a di dati. Tuttavia, nonostante le loro potenzialit`a lo sviluppo di sistemi DDS a livello industriale non ha ricevuto molta attenzione. Ci`o principalmente `e stato dovuto al fatto che `e estremamente complesso ottenere sistemi particolarmente efficienti ed efficaci; infatti, le attuali implementazioni di DDS sono basate su due approcci estremi: uno basato sul miglioramento dell’elaborazione dei dati da parte dei sistemi logici, l’altro basato sull’aggiunta di capacit`a di ragionamento ai DBMS (ad esempio tramite l’uso di SQL99, o di funzioni esterne). Entrambi tali approcci presentano limitazioni importanti. In particolare, i DDS basati sulla logica possono gestire una quantit`a limitata di dati, dal momento che, gli attuali sistemi logici eseguono i loro ragionamenti direttamente in memoria centrale; inoltre, essi forniscono interoperabilit`a limitate con DBMS esterni. Al contrario, i DDS basati sui database offrono funzionalit`a avanzate di gestione dei dati, ma scarse capacit`a di ragionamento (sia a causa della poca espressivit`a dei linguaggi di interrogazione, sia a causa di problemi di efficienza). Riassumendo, possiamo affermare che: • Gli attuali sistemi di basi di dati implementano moduli sufficientemente robusti e flessibili capaci di gestire grandi quantit`a di dati, ma non possiedono un linguaggio sufficientemente espressivo da consentire ragionamenti complessi su questi dati. • I sistemi basati sulla programmazione logica, possiedono elevate capacit`a di ragionamento e sono in grado di modellare e risolvere con facilit`a problemi di elevata complessit`a ma presentano notevoli limitazioni nella gestione di grandi quantit`a di dati poich´e eseguono le loro elaborazioni facendo uso di strutture dati gestite direttamente in memoria centrale. ii • I sistemi di basi di dati deduttive consentono di gestire i dati memorizzati su DBMS, ma, dal momento che, eseguono i loro ragionamenti direttamente in memoria centrale, possono gestire una quantit`a limitata di dati; Dalle precedenti osservazioni, si evidenzia la necessit`a di realizzare applicazioni che combinino il potere espressivo dei sistemi di programmazione logica con l’efficiente gestione dei dati tipica dei database. Il contributo di questa tesi si colloca nell’area della ricerca sulle basi di dati deduttive con l’obiettivo di colmare il divario esistente tra sistemi logici e DBMS. In questa tesi viene descritto un nuovo sistema, DLVDB, che ha la caratteristica di possedere le capacit`a di elaborazione dati desiderabili da un DDS ma di supportare anche le funzionalit`a di ragionamento pi`u avanzate dei sistemi basati sulla programmazione logica disgiuntiva. DLVDB `e stato progettato come estensione del sistema DLV e combina l’esperienza maturata nell’ambito del progetto DLV nell’ottimizzare programmi logici con le avanzate capacit`a di gestione dei dati implementate nei DBMS esistenti. Ci`o consente di applicare tale sistema in ambiti che necessitano sia di valutare programmi complessi, sia di lavorare su grandi quantit`a di dati. DLVDB `e in grado di fornire, cos`ı sostanziali miglioramenti sia nelle prestazioni relative alla valutazione dei programmi logici, sia nella facilit`a di gestione dei dati di input e di output possibilmente distribuiti su pi`u database. L’interazione con le basi di dati `e realizzata per mezzo di connessioni ODBC che consentono di gestire in modo piuttosto semplice dati distribuiti su vari database in rete. DLVDB consente di applicare diverse tecniche di ottimizzazione sviluppate sia nell’ambito dei sistemi logici, come ad esempio i magic set, sia nell’ambito della gestione delle basi di dati, come ad esempio tecniche di join ordering, inoltre sono stati integrati nel sistema i predicati per l’aggregazione di DLV (count, min, max, avg, sum) che avvicinano il linguaggio alle potenzialit`a di SQL, ma anche la possibilit`a di integrare nel programma logico, per natura dichiarativo, chiamate a funzioni esterne sviluppate con tecniche procedurali; ci`o rende possibile integrare aspetti dichiarativi ed aspetti procedurali di un problema in un’unica framework. Infine, per consentire la gestione di tipi di dati con strutture ricorsive (es. XML) si `e introdotta la possibilit`a di gestire liste di elementi, eventualmente innestate, nel programma logico. Inoltre in questa tesi viene presentata l’attivit`a di analisi di tipo sperimentale effettuata al fine di valutare le prestazioni di DLVDB, soprattutto in riferimento a velocit`a di esecuzione di query e quantit`a di dati gestibili. Questi test hanno dimostrato come il sistema apporta numerosi vantaggi rispetto ai sistemi esistenti, sia in termini di tempi di esecuzione delle query, sia in termini di quantit`a di dati che esso riesce a gestire contemporaneamente. In sintesi, i contributi di questo lavoro possono essere riassunti come segue: • Sviluppo di un sistema in grado di fondere il potere espressivo dei sistemi ASP con l’efficiente gestione dei dati offerta dagli attuali Database; • Sviluppo di una strategia di valutazione dei programmi logici in grado di minimizzare l’utilizzo della memoria centrale massimizzando l’utilizzo delle tecnologie implementate dai DBMS; • Estensione del linguaggio DLP mediante l’introduzione di chiamate a funzioni esterne e il supporto a tipi di dati con strutture ricorsive come le liste; • Realizzazione di un’analisi comparativa tra le prestazioni offerte da DLVDB e le prestazioni dei sistemi esistenti.
  • No Thumbnail Available
    Item
    Advanced Techniques and Systems for Data and Process Management
    (2014-03-31) Granata, Luigi; Greco, Gianluigi; Leone, Nicola
    Il lavoro di tesi viene suddiviso in due parti che trattano rispettivamente di tecniche avanzate e sistemi per la gestione dei dati e per il mining dei processi. Sono state affrontate problematiche relative all’efficienza della risposta alle interrogazioni su una base di dati, l’integrazioni di pi`u sorgenti di dati, e la progettazione di un sistema per il mining di processi. In particolare, i principali contributi della tesi sono: (1) Un nuovo modo di calcolare alberi di decomposizione di una interrogazione i cui query plan garantiscano un tempo di esecuzione al pi`u di complessit`a polinomiale. (2) Lo studio di tecniche emetodologie innovative, basate su logica computazionale, per i sistemi per l’integrazione di sorgenti informative e lo sviluppo di un prototipo che le implementi. (3) Lo studio di tecniche ed algoritmi per il mining di processi e lo sviluppo di una suite che le implementi. (1) Tecniche di risposta alle interrogazioni su basi di dati Rispondere ad interrogazioni su una basa di dati pu`o essere un processomolto costoso da un punto di vista computazionale. Per far fronte a questa problematica, in letteratura sono stati proposti vari approcci. Alcuni di essi sono basati su moduli per l’ottimizzazione delle interrogazioni che sfruttino le informazioni quantitative e statistiche sull’istanza della base di dati, mentre altre tecniche sfruttano le propriet`a strutturali degli ipergrafi delle interrogazioni. I nostri sforzi si sono rivolti in quest’ultima direzione estendendo il metodo di hypertree decomposition, considerato al momento il pi`u potente tra quelli strutturali. Questa nuova versione, chiamata query-oriented hypertree decomposition, mira a gestire esplicitamente le variabili di output e gli operatori aggregati. Basandoci su queste nozioni, `e stato implementato un ottimizzatore ibrido. Esso pu`o essere utilizzato dai DBMS correntemente disponibili per poter calcolare i piani di esecuzione per le interrogazioni. Tale prototipo `e stato integrato nel noto DBMS open source PostgreSQL. In fine questa estensione `e stata validata attraverso una intensa fase sperimentale, portata avanti con PostgreSQL ed un noto DBMS commerciale, che mostra come entrambi i sistemimigliorino significativamente le loro prestazioni utilizzando le hypertree decomposition per l’ottimizzazione delle interrogazioni. 3 (2) Tecniche per l’integrazione di sorgenti informative Per integrazione di informazioni si intende il problema di combinare i dati residenti in varie sorgenti informative, fornendo agli utenti una vista unificata di questi dati, chiamata global schema. Il nostro lavoro `e stato svolto all’interno del progetto INFOMIX. Il suo scopo principale `e stato quello di fornire tecniche avanzate e metodologie innovative per per gli information integration systems. In breve, il progetto ha sviluppato una teoria, comprendente un modello esauriente ed algoritmi per l’integrazione delle informazioni ed l’implementazione di un prototipo di un sistema knowledge based traminte l’utilizzo della logica computazionale che integri i risultati della ricerca sull’acquisizione e la trasformazione dei dati. Un’attenzione speciale `e stata dedicata alla definizione di un meccanismo per l’interazione dichiarativa da parte dell’utente e alle tecniche per la gestione di dati semistrutturati e sorgenti di dati incomplete o inconsistenti. (3) Tecniche per il mining di processi Nel contesto della enterprise automation, il process mining `e recentemente emerso come uno strumento utilissimo per l’analisi e la progettazione di processi di business complessi. Lo scenario tipico per il process mining `e dato da un insieme di tracce che registrano, tramite un sistema transazionale, le attivit`a svolte durante pi`u esecuzioni di un processo e dall’obiettivo ricavare inmaniera (semi)automatica un modello che possa spiegare tutti gli episodi registrati nelle tracce. Noi abbiamo sviluppato una Suite per le applicazioni del process mining con un’architettura aperta ed estendibile che introduce tre elementi innovativi per soddisfare i desiderata di flessibilit`a e scalabilit`a che sorgono negli scenari industriali attuali. • Il concetto di “flusso di mining”, i.e., essa permette di specificare delle catene di mininig complesse basate sulla connessione di task elementari. • La costruzione di applicazioni interattive basate sulla possibilit`a di personalizzare tipi di dati, algoritmi e l’interfaccia grafica utilizzata per l’analisi. • Scalabilit`a su grandi moli di