Κατά την τελευταία δεκαετία παρατηρούμε μία τεράστια αύξηση του πλήθους σημασιολογικών δεδομένων τα οποία είναι διαθέσιμα στο διαδίκτυο και για ένα μεγάλο αριθμό δραστηριοτήτων. Δεδομένα από επιχειρήσεις, κυβερνήσεις ή ακόμα και από απλούς χρήστες παύουν να αποτελούν “ιδιωτική” πληροφορία μέσα στον χώρο παραγωγής τους, δημοσιεύονται και βρίσκονται διαθέσιμα προς χρήση από ενδεχόμενους καταναλωτές, όπως εφαρμογές/υπηρεσίες, ανεξάρτητους χρήστες ή και κοινότητες χρηστών. Σε αυτό το πλαίσιο, το Ιστός των Δεδομένων (Web of Data) επεκτείνει τον τρέχον Παγκόσμιο Ιστό σε ένα παγκόσμιο χώρο δεδομένων που συνδέει πληροφορίες από διάφορους τομείς. Το γεγονός αυτό αυξάνει την αξία της υποστήριξης αποφάσεων και εφαρμογών επιχειρηματικής νοημοσύνης (business intelligence) και επιτρέπει τη δημιουργία νέου τύπου υπηρεσιών στη βάση ενός παγκόσμιου χώρου δεδομένων χωρίς όρια, και όχι απλά σε ένα αυστηρά καθορισμένο σύνολο πηγών δεδομένων, όπως στην περίπτωση των Web 2.0 mashups. Δεδομένου ότι η RDF είναι το lingua franca για τα Linked Open Data και ως εκ τούτου για το βασικό μοντέλο δεδομένων στον Παγκόσμιο Ιστό, ένα κεντρικό ζήτημα εδώ είναι η διαχείριση και η χρήση των RDF δεδομένων, και πιο συγκεκριμένα η αποτελεσματική και αποδοτική υποστήριξη για την αποθήκευση και αναζήτηση τους μέσω επερωτήσεων.
Σε αυτή την εργασία επικεντρωνόμαστε στο πρόβλημα της κλιμακώσιμης επεξεργασίας και βελτιστοποίησης SPARQL επερωτήσεων χρησιμοποιώντας σύγχρονες σχεσιακές μηχανές. Οι υπάρχουσες γηγενείς (native) μηχανές και οι μηχανές βασισμένες σε SQL για την επεξεργασία επερωτήσεων SPARQL, στηρίζονται σε μεγάλο βαθμό στη χρήση στατιστικών που αφορούν τους αποθηκευμένους RDF γράφους, καθώς επίσης και σε αλγόριθμους σχεδίασης οι οποίοι χρησιμοποιούν μοντέλα κόστους προκειμένου να βελτιστοποιήσουν σύνθετες επερωτήσεις σύζευξης (join). Τέτοιου τύπου στατιστικά είναι αρκετά ακριβά τόσο στον υπολογισμό όσο και στην διατήρηση τους για μεγάλης κλίμακας εξελισσόμενα σημασιολογικά δεδομένα τουΠαγκόσμιου Ιστού. Η βασική πρόκληση που τίθεται είναι η επινόηση τεχνικών βελτιστοποίησης για τη κατασκευή πλάνων εκτέλεσης επερωτήσεων βασισμένων σε ευρετικούς κανόνες, οι οποίοι δημιουργούν πλάνα όσο δυνατόν βέλτιστα πλάνα εκτέλεσης χωρίς την χρήση οποιασδήποτε γνώσης για τα αποθηκευμένα RDF δεδομένα. Για αυτό το λόγο προτείνουμε τον πρώτο κατασκευαστή πλάνων για SPARQL επερωτήσεις βασισμένο σε ευρετικούς κανόνες (heuristic-based SPARQL planning - HSP), ικανό να αναγνωρίζει τις συντακτικές παραλλαγές των προτύπων πρόσβασης τριάδας (triple pattern) σε μία επερώτηση προκειμένου να επιλέξει το βέλτιστο δυνατό πλάνο εκτέλεσης χωρίς τη χρήση μοντέλου κόστους. Στην εργασία αυτή, τα HSP πλάνα έχουν υλοποιηθεί πάνω από τη MonetDB, ένα Σύστημα Διαχείρισης Βάσεων Δεδομένων που βασίζεται στην τεχνολογία κολόνων (column-based DBMS). Μεγάλη προσοχή δώθηκε στην αποδοτική υλοποίηση των λογικών πλάνων HSP στην μηχανή εκτέλεσης επερωτήσεων της MonetDB, με την μετάφραση των HSP πλάνων στην φυσική άλγεβρα της MonetDB (MAL). Τέλος, αποτιμήσαμε πειραματικά την ποιότητα και τον χρόνο εκτέλεσης των HSP πλάνων και συγκρίναμε τα μεγέθη αυτά με τα πλάνα που παρήγαγε ο αλγόριθμος Cost-based Dynamic Programming (CDP). Το γηγενές σύστημα επεξεργασίας SPARQL επερωτήσεων RDF-3X χρησιμοποιήθηκε για την εκτέλεση των CDP πλάνων. Για την πειραματική αυτή αποτίμηση χρησιμοποιήσαμε τόσο συνθετικά όσο και πραγματικά RDF δεδομένα.
Σε όλες τις επερωτήσεις που χρησιμοποιήσαμε, οι αλγόριθμοι HSP και CDP παρήγαγαν πλάνα με τον ίδιο αριθμό πράξεων σύζευξης με συγχώνευση (merge join) και κατακερματισμό (hash join). Η διαφορά των παραγόμενων πλάνων έγκειται στις μεταβλητές οι οποίες χρησιμοποιούνται στις πράξεις σύζευξης με συγχώνευση, καθώς και στην σειρά εκτέλεσης των πράξεων σύζευξης η οποία επηρεάζει το μέγεθος των ενδιάμεσων αποτελεσμάτων. Στην πλειοψηφία των επερωτήσεων, ο χρόνος εκτέλεσης των HSP πλάνων στη MonetDB έχουν καλύτερος μέχρι και 3 τάξεις μεγέθους από τον χρόνο εκτέλεσης των CDP πλάνων τα οποία εκτελούνται στην μηχανή RDF-3X. Πιο συγκεκριμένα, ο αλγόριθμος HSP προσπαθεί να παράγει πλάνα τα οποία μεγιστοποιούν τον αριθμό πράξεων σύζευξης με συγχώνευση πάνω από ταξινομημένες μεταβλητές που είναι κοινές στα πρότυπα πρόσβασης τριάδων μιας επερώτησης. Βασίζεται σε ένα σύνολο ευρετικών κανόνων για να αποφασίσει ποιες ταξινομημένες μεταβλητές θα χρησιμοποιηθούν στις πράξεις επιλογής και σύζευξης. Οι ευρετικές αυτές μέθοδοι χρησιμοποιούνται επίσης για να αποφασίσουν τις σχέσεις (ταξινομημένες σχέσεις τριάδων στην MonetDB) πάνω στις οποίες θα αποτιμηθούν τα πρότυπα πρόσβασης τριάδων της επερώτησης.
(EL)
During the last decade we have witnessed a tremendous increase in the amount of semantic data available on the Web in almost every field of human activity. More and more corporate, governmental, or even user-generated datasets break the walls of ``private'' management within their production site, are published, and become available for potential data consumers, i.e., applications/services, individual users and communities. In this context, The Web of Data extends current Web to a global data space connecting data from diverse domains. This gives added value for decision support and business intelligence applications, and enables new types of services that operate on top of an unbound, global data space and not on a fixed set of data sources as in Web 2.0 mashups.
A central issue in this respect is the manipulation and usage of data based on their meaning by using effective and efficient support for storing, querying, and manipulating semantic RDF data, the lingua franca of Linked Open Data and hence the default data model for the Web of Data.
In this thesis we are focusing on the problem of scalable processing and optimization of semantic queries expressed in SPARQL using modern relational engines.
Existing native or SQL-based engines for processing SPARQL queries heavily rely on statistics regarding the stored RDF graphs as well as adequate cost based planning algorithms to optimize complex join queries. Extensive data statistics are quite expensive to compute and maintain for large scale evolving semantic data over the Web. The main challenge in this respect is to devise heuristics-based query optimization techniques generating near to optimal execution plans without any knowledge of the underlying datasets. For this reason we propose the first heuristics-based SPARQL planner (HSP) that is capable of exploring the syntactic variations of triple patterns in a query in order to choose a near to optimal execution plan without the use of a cost model. Furthermore, we have implemented HSP plans on top of the MonetDB column-based DBMS. We have paid particular attention to the efficient implementation of HSP logical plans to the underlying MonetDB query execution engine by translating them into MonetDB's physical
algebra (MAL). We have finally, experimentally evaluated the quality and execution time of the plans produced by HSP with a state-of-the-art Cost-based Dynamic Programming (CDP) algorithm employed by RDF-3X using synthetically generated and real RDF datasets.
In all queries of our workload, HSP produce plans with the same number of merge and hash joins as CDP. Their differences lie on the employed ordered variables as well as
the execution order of joins which essentially affect the size of intermediate results. With the exception of queries which are not substantially different in their syntax, HSP plans executed on MonetDB outperform those of CDP executed in RDF-3X up to three orders of magnitude. More precisely, HSP tries to produce plans that maximize the number of merge joins over the ordered variables which are shared among the triple patterns of a query and relies on various heurists to decide which ordered variables will be used in selections and joins as well as which underlying access paths will be exploited for evaluating the triple patterns (essentially sorted triple relations in MonetDB).
(EN)
