Your browser does not support JavaScript!

Αρχική    Heuristic Optimization of SPARQL queries over Column-Store DBMS  

Αποτελέσματα - Λεπτομέρειες

Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου 000370106
http://elocus.lib.uoc.gr//dlib/2/c/c/metadata-dlib-1322123539-434628-19267.tkl
Τίτλος Heuristic Optimization of SPARQL queries over Column-Store DBMS
Άλλος τίτλος Ευρετική βελτιστοποίηση ερωτήσεων SPARQL σε ΣΔΒΔ βασισμένα σε κολόνες
Συγγραφέας Αναγνωστόπουλος-Τσιαλιαμάνης, Πέτρος Βασίλειος
Σύμβουλος διατριβής Χριστοφίδης, Βασίλης
Περίληψη Κατά την τελευταία δεκαετία παρατηρούμε μία τεράστια αύξηση του πλήθους σημασιολογικών δεδομένων τα οποία είναι διαθέσιμα στο διαδίκτυο και για ένα μεγάλο αριθμό δραστηριοτήτων. Δεδομένα από επιχειρήσεις, κυβερνήσεις ή ακόμα και από απλούς χρήστες παύουν να αποτελούν “ιδιωτική” πληροφορία μέσα στον χώρο παραγωγής τους, δημοσιεύονται και βρίσκονται διαθέσιμα προς χρήση από ενδεχόμενους καταναλωτές, όπως εφαρμογές/υπηρεσίες, ανεξάρτητους χρήστες ή και κοινότητες χρηστών. Σε αυτό το πλαίσιο, το Ιστός των Δεδομένων (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) πάνω στις οποίες θα αποτιμηθούν τα πρότυπα πρόσβασης τριάδων της επερώτησης.
Φυσική περιγραφή vi, 76 σ. : εικ., πίν. ; 30 εκ.
Γλώσσα Αγγλικά
Θέμα Query Optimization
Query Procssing
SPARQL
Semantic Web
Βελτιστοποίηση επερωτήσεων
Σημασιολογικός ιστός
Ημερομηνία έκδοσης 2011-11-18
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Εμφανίσεις 516

Ψηφιακά τεκμήρια
No preview available

Κατέβασμα Εγγράφου
Προβολή Εγγράφου
Εμφανίσεις : 12