Advanced techniques for flexible database queries

The thesis tackles the problem of Big Data Analytics by focusing on how to extract synopsis from it, that is find recurring patterns in the data. We will show how these patterns can be used to get the gist out of data, that is, to represent in a succinct way the data’s most frequent properties. These properties can be used as a compact representation of data as well as a basis for making efficient decisions. Moreover, we will see how the use of aggregates is decisive in Big Data because it allows for better analysis of data itself. The first aim of the thesis is to propose novel applications of data mining techniques to provide advanced database functionalities. In particular we focus on extracting frequent information from a dataset in order to use it for query answering, that is allowing users to query the frequent patterns rather than the data. We consider such patterns as intensional information because they represent a dataset in terms of a set of properties rather than in terms of the data (which is called extensional information). Our goal is to propose a methodology for the XML scenario that uses association rules to represent intensional knowledge and provides an automatic strategy for translating user queries over the original dataset to queries over the mined association rules. In fact, intensional knowledge provides (often hidden) information about the actual data contained in the database. Such information is particularly valuable when the original documents are not available or reachable anymore or when the user prefers to obtain a synthetic, possibly faster but partial, answer. From the XML tree-based scenario we take a step further into analyzing a similar but more complex representation, that is, graph-based data. We present DatalogFS, an extension of Datalog that allows to introduce more flexibility into the querying process by using count-based aggregates. Our approach allows users to write queries in terms of programs in DatalogFS , which are considered synopsis of expanded Datalog programs. We provide a rewriting of DatalogFS programs into Datalog and a semantics that allows us to keep the simple and elegant least-fixpoint semantics of Datalog and all of its optimizations, such as the differential fixpoint and magic sets. We will see how to write DatalogFS programs that implement Apriori and PageRank, making our proposal helpful in the process of analyzing both relational and web-based data. Moreover, we will also focus on the application of DatalogFS programs for the analysis of data coming from social networks. For example, using the Markov Chains and Diffusion Models we will show how DatalogFS can be efficiently used to analyze the role of retweets in the Twitter network.

La tesi affronta il problema dell'analisi dei Big Data focalizzandosi su come estrarre sinopsi da essi, ovvero trovare pattern ricorrenti. Verra` mostrato come tali pattern possano essere usati per estrarre il "succo" dai dati, ovvero per rappresentare in maniera compatta le loro proprieta` piu` frequenti. Tali proprieta` sono sia una visione succinta dei dati che una valida base per prendere decisioni efficienti. Inoltre, verra` mostrato come l'uso degli aggregati sia decisivo nei Big Data perche' permette una migliore analisi dei dati stessi. Il primo obiettivo della tesi e` identificare nuove applicazioni di tecniche di data mining per fornire funzionalita` avanzate nelle basi di dati. Ci si focalizza sull'estrarre informazioni frequenti da una base di dati con lo scopo di usarle per fornire risposte alle interrogazioni ossia permettere agli utenti di interrogare i pattern frequenti invece dei dati stessi. Tali pattern sono considerati informazioni intensionali perche' rappresentano la base di dati in termini delle sue proprieta` invece che dei dati (che sono chiamati informazioni estensionali). La tesi propone una metodologia per lo scenario XML in cui vengono usate le regole di associazione per rappresentare la conoscenza intensionale e provvede una strategia automatica per tradurre le interrogazioni degli utenti dirette alla base di dati originale in interrogazioni che possono essere eseguite sulle regole di associazione estratte. La conoscenza intensionale fornisce informazioni (spesso nascoste) sui dati contenuti nella base di dati e tali informazioni sono molto utili quando il documento originale non e` piu` disponibile oppure quanto l'utente preferisce una risposta sintetica e possibilmente veloce, nonostante parziale. Dallo scenario XML si passa ad analizzare una rappresentazione simile ma piu` complessa, ovvero i dati rappresentati sotto forma di grafi. Nella tesi viene introdotto DatalogFS, un'estensione di Datalog che permette di introdurre piu` flessibilita` nel processo di interrogazione tramite l'uso di aggregati di count. L'approccio proposto consente agli utenti di scrivere le interrogazioni in termini di programmi in DatalogFS che sono considerati delle sinopsi di programmi Datalog. Viene quindi fornita una riscrittura di programmi DatalogFS in Datalog e una semantica che permette di mantenere la semantica di Datalog e tutte le sue ottimizzazioni, quali il differential fixpoint e i magic sets. Viene mostrato come DatalogFS possa essere usato per esprimere algoritmi quali Apriori e PageRank e come, tramite l'uso di catene di Markov e modelli di diffusione, permetta di analissare il ruolo dei retweet nella rete di Twitter.