Data and Knowledge Management in Cloud Computing Environment
Date Issued
July 11, 2022
Type
Διδακτορική Διατριβή
Abstract
Στην παρούσα διδακτορική διατριβή μελετάται το πρόβλημα της παράλληλης επεξερ-
γασίας ερωτημάτων σε μεγάλου όγκου διασυνδεδεμένα δεδομένα (κωδικοποιημένα
μέσω της RDF) μέσω τεσσάρων διαφορετικών πρωτότυπων προσεγγίσεων. Σε
όλες τις προσεγγίσεις, τα αρχικά δεδομένα διασπώνται σε υπογράφους (τμήματα),
το ερώτημα Q που είναι και αυτό της μορφής γράφου διασπάται σε μικρότερους υπ-
ογράφους (υποερωτήματα), και στη συνέχεια η επεξεργασία των υποερωτημάτων
στα διάφορα τμήματα πραγματοποιείται παράλληλα.
Στις τρεις πρώτες προσεγγίσεις, η επεξεργασία των δεδομένων βασίζεται στο
ευρέως χρησιμοποιούμενο προγραμματιστικό περιβάλλον MapReduce.
Στην πρώτη προσέγγιση, παρουσιάζεται ένας γενικός αλγόριθμος MapReduce
αποτελούμενος από δύο φάσεις. Ο αλγόριθμος υλοποιείται πάνω σε μεγάλου όγκου
δεδομένα που έχουν διασπαστεί και αποθηκευτεί σε διαφορετικούς κόμβους (nodes)
μιας συστοιχίας υπολογιστών (cluster). Το αρχικό ερώτημα Q, διασπάται σε ένα
πλήθος τυχαίων υποερωτημάτων. Στην πρώτη φάση του αλγορίθμου, το κάθε υπ-
οερώτημα επεξεργάζεται παράλληλα σε κάθε υπογράφο και τα αποτελέσματα των
υποερωτημάτων συνδυάζονται κατάλληλα στη δεύτερη φάση του αλγορίθμου ώστε
να υπολογιστούν τα τελικά αποτελέσματα του αρχικού ερωτήματος Q. Ο προ-
τεινόμενος αλγόριθμος υπολογίζει τις απαντήσεις ανεξάρτητα α) από τον τρόπο
διάσπασης του αρχικού γράφου, β) του τρόπου αποθήκευσης των δεδομένων, γ)
του τρόπου διάσπασης του αρχικού ερωτήματος στα υποερωτήματα και δ) του αλ-
γορίθμου που χρησιμοποιείται για τον υπολογισμό των (μερικών) αποτελεσμάτων.
Η δεύτερη προσέγγιση βασίζεται στη διάσπαση του αρχικού ερωτήματος Q σε
ένα πλήθος υποερωτημάτων που αποκαλούνται ερωτήματα γενικευμένου αστέρα.
΄Ολες οι ακμές αυτού του είδους ερωτημάτων έχουν έναν κοινό κόμβο είτε ως υπ-
οκείμενο, είτε ως αντικείμενο που ονομάζεται κεντρικός κόμβος. Αποδεικνύεται
ότι κάθε ερώτημα Q, μπορεί να διασπαστεί σε ένα πλήθος τέτοιων υποερωτη-
μάτων. Τα αρχικά δεδομένα και πάλι κατανέμονται στους κόμβους της συστοιχίας
των υπολογιστών και ένας επεκτάσιμος αλγόριθμος MapReduce που παρουσιάζε-
ται υπολογίζει αποδοτικά τις απαντήσεις του αρχικού ερωτήματος, αφού πρώτα
υπολογίσει και στη συνέχεια συνδυάσει κατάλληλα τις απαντήσεις των υποερωτη-
μάτων της μορφής γενικευμένου αστέρα.
Η τρίτη προσέγγιση βασίζεται στην αρχική διάσπαση του γράφου των δε-
δομένων με τέτοιο τρόπο ώστε να επιτρέπεται η επανάληψη ίδιων ακμών σε περισ-
σότερα από έναν υπογράφους (τμήματα) με τέτοιο τρόπο ώστε να εξασφαλίζεται
ο υπολογισμός των απαντήσεων ενός υποερωτήματος γενικευμένου αστέρα τοπικά σε κάθε υπογράφο. Ο επεκτάσιμος αλγόριθμος MapReduce που μελετάται για τον
υπολογισμό των απαντήσεων του αρχικού ερωτήματος αποτελείται από ένα και μισό
στάδιο MapReduce. Παρόλα αυτά, αποδεικνύεται πως σε ειδικές περιπτώσεις τα
τελικά αποτελέσματα μπορούν να απαντηθούν και σε ένα μόνο στάδιο MapReduce.
Στην τέταρτη προσέγγιση παρουσιάζεται ένα αποτελεσματικό μοντέλο οργάν-
ωσης και αποθήκευσης των δεδομένων κατάλληλο για επεξεργασία τους σε NoSQL
document βάσεις δεδομένων. Η επανάληψη ίδιων ακμών του αρχικού γράφου στους
υπογράφους γίνεται και πάλι με τέτοιο τρόπο ώστε στη χείριστη περίπτωση τα δε-
δομένα μετά τη διάσπασή τους να μην έχουν μέγεθος μεγαλύτερο (στη χείριστη
περίπτωση) από το διπλάσιο του μεγέθους των αρχικών δεδομένων. Το αρχικό
ερώτημα διασπάται και πάλι σε ένα σύνολο από υποερωτήματα τύπου γενικευμέ-
νου αστέρα. Το προτεινόμενο μοντέλο οργάνωσης των δεδομένων εξασφαλίζει πως
κάθε υποερώτημα τύπου αστέρα μπορεί να απαντηθεί μέσα σε κάθε ξεχωριστό document
της βάσης δεδομένων. Οι απαντήσεις των υποερωτημάτων στη συνέχεια
συνδυάζονται κατάλληλα ώστε να προκύψουν οι τελικές απαντήσεις του αρχικού
ερωτήματος Q. Η προσέγγιση υλοποιήθηκε κάνοντας χρήση της NoSQL document
βάσης δεδομένων MongoDB και του Apache Spark.
Subjects