Επεξεργασία ερωτημάτων σε κατανεμημένα περιβάλλοντα αυτόνομων συστημάτων διαχείρισης δεδομένων

Abstract

Large-scale distributed environments, where each node is completely autonomous and offers services to its peers through external communication, pose significant challenges to query processing, allocation and optimization. In this thesis, inspired by e-commerce technology, we recognize queries as commodities and model query optimization as a trading negotiation process. Similarly to query optimization, we examine the problem of query allocation under the perspective of microeconomics theory and show how the latter can be used together with our query trading negotiation framework to construct an efficient decentralized mechanism that maximizes system throughput. In particular, we introduce three solutions that are based on the notion of query markets.

Τα μεγάλης κλίμακας κατανεμημένα περιβάλλοντα, στα οποία κάθε κόμβος είναι απολύτως αυτόνομος και προσφέρει υπηρεσίες στους υπόλοιπους κόμβους, εμφανίζουν σημαντικές προκλήσεις σε θέματα επεξεργασίας, ανάθεσης και βελτιστοποίησης επερωτήσεων. Σε αυτήν τη διατριβή, εμπνευσμένοι από την τεχνολογία του ηλεκτρονικού εμπορίου, θεωρούμε τις επερωτήσεις ως αγαθά και μοντελοποιούμε τη βελτιστοποίησή τους ως μια διαδικασία εμπορικής διαπραγμάτευσης. Απαντήσεις και πλάνα εκτέλεσης υπο-επερωτήσεων τίθενται προς διαπραγμάτευση μεταξύ των κόμβων μέχρι την επίτευξη συμφωνίας. Συγκρινόμενη με τις γενικές εμπορικές διαπραγματεύσεις στο ηλεκτρονικό εμπόριο, η βελτιστοποίηση επερωτήσεων αντιμετωπίζει νέες μοναδικές προκλήσεις που πηγάζουν κυρίως από το γεγονός ότι οι επερωτήσεις έχουν μια περίπλοκη δομή και μπορούν να «κομματιαστούν» σε μικρότερα μέρη. Κατά αντιστοιχία με τη βελτιστοποίηση επερωτήσεων, εξετάζουμε το πρόβλημα της ανάθεσης επερωτήσεων υπό το πρίσμα της θεωρίας μικροοικονομίας και παρουσιάζουμε πώς αυτή μπορεί να χρησιμοποιηθεί μαζί με το πλαίσιο εμπορικής διαπραγμάτευσης επερωτήσεων για την κατασκευή ενός αποδοτικού και αποκεντρωποιημένου μηχανισμού που μεγιστοποιεί τη συνολική απόδοση του συστήματος.