Indexing Views to Route and Plan Queries in a Peer Data Management System

Κωδικοποίηση Όψεων για Δρομολόγηση και Δημιουργία Πλάνων Επερωτήσεων σε Ομότιμα Συστήματα Διαχείρισης Δεδομένων

Indexing Views to Route and Plan Queries in a Peer Data Management System

Σιδηρουργός, Ελευθέριος (EL)

Sidirourgos, Eleytherios (EN)

text

Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης

2005-12-01

2006-01-23

Τα δυομότιμα (Peer-to-Peer ή πιο απλά P2P) Συστήματα έχουν γίνει ιδιαίτερα δημοφιλή τον τελευταίο καιρό, δεδομένου ότι παρέχουν τα μέσα για την ανάπτυξη συστημάτων υπολογισμού αποτελούμενα από ένα μεγάλο αριθμό ομότιμων κόμβων, εξασφαλίζοντας ταυτόχρονα υψηλή αυτονομία και ανοχή στα σφάλματα. Τα Ομότιμα Συστήματα Διαχείρισης Δεδομένων (ΟΣΔΔ) έχουν προταθεί για να προσφέρουν εξελιγμένες υπηρεσίες στην ανταλλαγή, επερώτηση και ολοκλήρωση (ημί-)δομημένων δεδομένων που βρίσκονται στις βάσεις δεδομένων των κόμβων που τα απαρτίζουν. Στην παρούσα εργασία, διαπραγματευόμαστε ζητήματα δρομολόγησης και δημιουργίας πλάνων για επερωτήσεις σε ένα ΟΣΔΔ, όπου οι κόμβοι δημοσιεύουν τις τοπικές βάσεις δεδομένων τους χρησιμοποιώντας όψεις RDF/S σχημάτων. Παρουσιάζουμε μία πρωτότυπη κωδικοποίηση για αυτές τις όψεις, η οποία μας επιτρέπει να αποφασίζουμε αποδοτικά εάν η όψη της βάσης δεδομένων ενός κόμβου απαντά σε μία επερώτηση. Στηριζόμενοι σε αυτήν την κωδικοποίηση σχεδιάσαμε ένα μηχανισμό για την δρομολόγηση RDF/S επερωτήσεων, που υλοποιήθηκε πάνω από ένα δομημένο δυομότιμο σύστημα βασισμένο σε κατανεμημένους πίνακες κατακερματισμού (DHTs). Σχεδιάσαμε και υλοποιήσαμε ένα μηχανισμό που εναλλάσσει την δρομολόγηση και την δημιουργία πλάνων μίας επερώτησης έτσι ώστε να κατανείμουμε την επεξεργασία της στους κόμβους που απαρτίζουν το ΟΣΔΔ. Τέλος, διεξαγάγαμε μία σειρά από πειράματα για να (α) καταδείξουμε ότι το σύστημα μας μπορεί να κλιμακωθεί σε ένα μεγάλο αριθμό από κόμβους και μεγέθους όψεις RDF/S, (β) για να αποτιμήσουμε τον αριθμό των μηνυμάτων που αποστέλλονται κατά την δρομολόγηση μίας επερώτησης και (γ) για να επιδείξουμε τον βαθμό της κατανομής στο φόρτο εργασίας που επιτυγχάνετε από την εναλλασσόμενη εκτέλεση της δρομολόγησης και δημιουργίας πλάνων μίας επερώτησης. Σύμφωνα με όσα γνωρίζουμε, το σύστημα που παρουσιάζουμε είναι το πρώτο που προσφέρει αυτή την λειτουργικότητα με αυτές τις επιδόσεις. (EL)

P2P computing gains increasing attention lately, since it provides the means for realizing computing systems that scale to very large numbers of participating peers, while ensuring high autonomy and fault-tolerance. Peer Data Management Systems (PDMS) have been proposed to support sophisticated facilities in exchanging, querying and integrating (semi-)structured data hosted by peers. In this thesis, we are interested in routing and planning graph queries in a PDMS, where peers advertise their local bases using fragments of community RDF/S schemas (i.e., views). We introduce an original encoding for these fragments, in order to efficiently check whether a peer view is subsumed by a query. We rely on this encoding to design an RDF/S view lookup service featuring a stateless and a statefull execution over a DHT-based P2P infrastructure. We design and implement a mechanism based on an interleaved execution of the routing and planning activities in order to distribute the processing of a query. We finally evaluate experimentally our system (a) to demonstrate its scalability for large P2P networks and arbitrary RDF/S schema fragments, (b) to estimate the number of routing hops required by the two versions of our lookup service and (c) to demonstrate the degree of distribution achieved by the interleaved query routing and planning. To the best of our knowledge this is the first system offering the aforementioned functionality and performance. (EN)

Πανεπιστήμιο Κρήτης

E-Locus Ιδρυματικό Καταθετήριο

Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης

Elocus