Data and knowledge management in cloud computing environment
Authors: Καλόγερος Ελευθέριος 
Published: July 2022

Στην παρούσα διδακτορική διατριβή μελετάται το πρόβλημα της παράλληλης επεξεργασίας ερωτημάτων σε μεγάλου όγκου διασυνδεδεμένα δεδομένα (κωδικοποιημένα μέσω της RDF) μέσω τεσσάρων διαφορετικών πρωτότυπων προσεγγίσεων. Σε όλες τις προσεγγίσεις, τα αρχικά δεδομένα διασπώνται σε υπογράφους (τμήματα), το ερώτημα Q που είναι και αυτό της μορφής γράφου διασπάται σε μικρότερους υπογράφους (υποερωτήματα), και στη συνέχεια η επεξεργασία των υποερωτημάτων στα διάφορα τμήματα πραγματοποιείται παράλληλα. Στις τρεις πρώτες προσεγγίσεις, η επεξεργασία των δεδομένων βασίζεται στο ευρέως χρησιμοποιούμενο προγραμματιστικό περιβάλλον MapReduce. Στην πρώτη προσέγγιση, παρουσιάζεται ένας γενικός αλγόριθμος MapReduce αποτελούμενος από δύο φάσεις. Ο αλγόριθμος υλοποιείται πάνω σε μεγάλου όγκου δεδομένα που έχουν διασπαστεί και αποθηκευτεί σε διαφορετικούς κόμβους (nodes) μιας συστοιχίας υπολογιστών (cluster). Το αρχικό ερώτημα Q, διασπάται σε ένα πλήθος τυχαίων υποερωτημάτων. Στην πρώτη φάση του αλγορίθμου, το κάθε υποερώτημα επεξεργάζεται παράλληλα σε κάθε υπογράφο και τα αποτελέσματα των υποερωτημάτων συνδυάζονται κατάλληλα στη δεύτερη φάση του αλγορίθμου ώστε να υπολογιστούν τα τελικά αποτελέσματα του αρχικού ερωτήματος Q. Ο προτεινόμενος αλγόριθμος υπολογίζει τις απαντήσεις ανεξάρτητα α) από τον τρόπο διάσπασης του αρχικού γράφου, β) του τρόπου αποθήκευσης των δεδομένων, γ) του τρόπου διάσπασης του αρχικού ερωτήματος στα υποερωτήματα και δ) του αλγορίθμου που χρησιμοποιείται για τον υπολογισμό των (μερικών) αποτελεσμάτων. Η δεύτερη προσέγγιση βασίζεται στη διάσπαση του αρχικού ερωτήματος Q σε ένα πλήθος υποερωτημάτων που αποκαλούνται ερωτήματα γενικευμένου αστέρα. ΄Ολες οι ακμές αυτού του είδους ερωτημάτων έχουν έναν κοινό κόμβο είτε ως υποκείμενο, είτε ως αντικείμενο που ονομάζεται κεντρικός κόμβος. Αποδεικνύεται ότι κάθε ερώτημα Q, μπορεί να διασπαστεί σε ένα πλήθος τέτοιων υποερωτημάτων. Τα αρχικά δεδομένα και πάλι κατανέμονται στους κόμβους της συστοιχίας των υπολογιστών και ένας επεκτάσιμος αλγόριθμος MapReduce που παρουσιάζεται υπολογίζει αποδοτικά τις απαντήσεις του αρχικού ερωτήματος, αφού πρώτα υπολογίσει και στη συνέχεια συνδυάσει κατάλληλα τις απαντήσεις των υποερωτημάτων της μορφής γενικευμένου αστέρα.Η τρίτη προσέγγιση βασίζεται στην αρχική διάσπαση του γράφου των δεδομένων με τέτοιο τρόπο ώστε να επιτρέπεται η επανάληψη ίδιων ακμών σε περισσότερα από έναν υπογράφους (τμήματα) με τέτοιο τρόπο ώστε να εξασφαλίζεται ο υπολογισμός των απαντήσεων ενός υποερωτήματος γενικευμένου αστέρα τοπικά σε κάθε υπογράφο. Ο επεκτάσιμος αλγόριθμος MapReduce που μελετάται για τον υπολογισμό των απαντήσεων του αρχικού ερωτήματος αποτελείται από ένα και μισό στάδιο MapReduce. Παρόλα αυτά, αποδεικνύεται πως σε ειδικές περιπτώσεις τα τελικά αποτελέσματα μπορούν να απαντηθούν και σε ένα μόνο στάδιο MapReduce. Στην τέταρτη προσέγγιση παρουσιάζεται ένα αποτελεσματικό μοντέλο οργάνωσης και αποθήκευσης των δεδομένων κατάλληλο για επεξεργασία τους σε NoSQL document βάσεις δεδομένων. Η επανάληψη ίδιων ακμών του αρχικού γράφου στους υπογράφους γίνεται και πάλι με τέτοιο τρόπο ώστε στη χείριστη περίπτωση τα δεδομένα μετά τη διάσπασή τους να μην έχουν μέγεθος μεγαλύτερο (στη χείριστη περίπτωση) από το διπλάσιο του μεγέθους των αρχικών δεδομένων. Το αρχικό ερώτημα διασπάται και πάλι σε ένα σύνολο από υποερωτήματα τύπου γενικευμένου αστέρα. Το προτεινόμενο μοντέλο οργάνωσης των δεδομένων εξασφαλίζει πως κάθε υποερώτημα τύπου αστέρα μπορεί να απαντηθεί μέσα σε κάθε ξεχωριστό document της βάσης δεδομένων. Οι απαντήσεις των υποερωτημάτων στη συνέχεια συνδυάζονται κατάλληλα ώστε να προκύψουν οι τελικές απαντήσεις του αρχικού ερωτήματος Q. Η προσέγγιση υλοποιήθηκε κάνοντας χρήση της NoSQL document βάσης δεδομένων MongoDB και του Apache Spark.