Managing, querying and analyzing big data on the web

Abstract

In this thesis, we study information management problems that arise in the Semantic Web, focusing on the Resource Description Framework (RDF) model and its associated SPARQL query language. To this end, we focus in three directions, namely (i) RDF data evolution, (ii) storage, indexing and query optimization in RDF/SPARQL engines, and (iii) efficient and scalable information retrieval from multidimensional RDF datasets. We present efficient and scalable methods focused on specific problems in the aforementioned directions, with the ultimate aim to propose advancements in the relevant state of the art. In the first direction (chapters 2 and 3), we study the problem of representing, storing and querying evolving RDF data. To this end, a novel data model and query language are proposed, that address representation of versioning in heterogeneous domains,. Furthermore, in order to assist evaluation of RDF versioning and evolution management engines and frameworks, a novel synthetic dataset generator is introduced. In the second direction (chapters 4, 5 and 6), we tackle the problem of indexing and query optimization, specifically focusing on heavy query workloads in loosely-structured RDF datasets. To this end, we propose a novel indexing and storage scheme for RDF data that relies on the underlying graph schema of the data, as well as query optimization algorithms that take advantage of the underlying schema in order to accelerate processing of complex SPARQL queries that traditional systems fail to address. Furthermore, we provide a method for logical query optimization by triple pattern reordering, in order to further optimize the query processing tasks commonly adopted by database systems. Finally, we introduce a series of algorithms that aim to efficiently transform and compact the underlying RDF schema in order to optimize both storage and query processing. Finally, in the third direction (chapter 7), we define several types of relationships for multidimensional RDF data cubes, and we propose a series of computational algorithms that target efficient retrieval of these relationships. Extensive experimental evaluations of our methods indicate significant performance improvements with respect to the state of the art.

Η παρούσα διδακτορική διατριβή πραγματεύεται θέματα και προβλήματα διαχείρησης δεδομένων που προκύπτουν εντός του Σημασιολογικού Ιστού και εστιάζει στο μοντέλο Resource Description Framework (RDF) και τη γλώσσα επερωτήσεων SPARQL. Σε αυτό το πλαίσιο ακολουθούνται τρεις ερευνητικές κατευθύνσεις, συγκεκριμένα (i) η διαχείρηση εξελισσόμενων RDF δεδομένων, (ii) η αποθήκευση, ευρετηρίαση και βελτιστοποίηση περίπλοκων επερωτήσεων σε συστήματα βάσεων RDF/SPARQL, και (iii) η αποδοτική και κλιμακώσιμη ανάκτηση πληροφορίας από σύνολα πολυδιάστατων RDF δεδομένων. Παρουσιάζονται αποδοτικές και κλιμακώσιμες μέθοδοι, εστιαζόμενες σε συγκεκριμένα προβλήματα των προαναφερθείσων κατευθύνσεων, με τελικό σκοπό να προταθούν προοδευτικές εξελίξεις στην αιχμή της έρευνας.Στην πρώτη κατεύθυνση, και συγκεκριμένα στα κεφάλαια 2 και 3, μελετάται το πρόβλημα της αναπαράστασης, αποθήκευσης και επερώτησης εξελισσόμενων RDF δεδομένων. Υπό αυτό το πρίσμα, προτείνεται ένα νέο μοντέλο δεδομένων και μια νέα γλώσσα επερωτήσεων, στοχεύοντας στην αναπαράσταση της εξέλιξης σε περιστάσεις ετερογενών πεδίων πληροφορίας. Ακολούθως, προτείνεται μια νέα μέθοδος παραγωγής συνθετικών εξελισσόμενων RDF δεδομένων΄, η οποία στοχεύει στην καλύτεηρ αξιολόγηση συστημάτων διαχείρησης εκδόσεων (versioning). Στη δεύτερη κατεύθυνση, και συγκεκριμένα στα κεφάλαια 4, 5 και 6, αντιμετωπίζεται το πρόβλημα της ευρετηρίασης και της αποτίμησης επερωτήσεων, εστιάζοντας συγκεκριμένα σε ερωτήματα βαρέως φόρτου εργασίας σε ημι-δομημένα σύνολα δεδομένων RDF. Υπό αυτό το πρίσμα, προτείνεται μια νέα μέθοδος ευρετηρίασης και αποθήκευσης RDF δεδομένων, η οποία βασίζεται στην ανάκτηση του υποκείμενου σχήματος των δεδομένων, καθώς και νέοι αλγόριθμοι αποτίμησης επερωτήσεων SPARQL που εκμεταλλεύονται το υποκείμενο σχήμα ώστε να βοηθήσουν την αποδοτική και ταχεία αποτίμηση περίπλοκων επερωτήσεων, όπου τα υπάρχοντα συστήματα παρουσιάζουν προβλήματα. Επιπροσθέτως, προτείνεται μια νέα μέθοδος λογικής βελτιστοποίησης βασιζόμενη στην αναπροσαρμογή της σειράς αποτίμησης των τριπλετών (triple pattern reordering). Τέλος, παρουσιάζεται μια σειρά από τεχνικές που στοχεύουν στην σύμπτυξη του υποκείμενου σχήματος με σκοπό την περαιτέρω βελτιστοποίηση της διαδικασίας αποτίμησης.Τέλος, στην τρίτη κατεύθυνση, και συγκεκριμένα στο κεφάλαιο 7, ορίζεται μια σειρά από τύπους συσχετίσεων μεταξύ δεδομένων σε πολυδιάστατωα σύνολα κύβων RDF, και προτείνεται μια σειρά από υπολογιστικές μεθόδους και αλγορίθμους που στοχεύουν στην ταχεία και αποδοτική ανάκτηση αυτών των συσχετίσεων. Η αξιολόγηση των μεθόδων μέσα από μια εκτεταμένη πειραματική διαδικασία, υποδεικνύει ότι οι προτεινόμενες μέθοδοι προσφέρουν σημαντικά πλεονεκτήματα απόδοσης σε σχέση με την τρέχουσα ερευνητική αιχμή.