Data and knowledge management in cloud computing environment

Abstract

In this Ph.D. thesis, we study the problem of efficiently evaluating basic graph pattern (BGP) queries over a large amount of linked data (RDF data) in parallel and provide four approaches. In this context, we consider that the data graph has been partitioned into graph segments and the initial query Q is decomposed into a set of BGP subqueries. In the first three approaches, the widely used MapReduce framework is used for querying a large amount of linked data. In the first approach, a generic two-phase, MapReduce algorithm is presented. The algorithm is based on the idea that the data graph has been arbitrarily partitioned into graph segments which are stored in different nodes of a cluster of commodity machines. To answer a user query Q, Q is also decomposed into a set of random BGP subqueries. In the first phase, the subqueries are applied to each graph segment, in isolation, and intermediate results are computed. The intermediate results are appropriately combined in the second phase to obtain the answers of the initial query Q. The proposed algorithm computes the answers to a given query correctly, independently of a) the data graph partitioning, b) the way that graph segments are stored, c) the query decomposition, and d) the algorithm used for calculating (partial) results. In the second approach, we present a method which focusing on the decomposition of the query Q, into a set of generalized star queries, which are queries that allow both subject-object and object-subject edges from a specific node, called central node. It is proved that each query Q can be transformed into a set of subject-object star subqueries. The data graph has also been arbitrarily partitioned into graph segments and a two-phase, scalable MapReduce algorithm is proposed that efficiently results from the answer of the initial query Q by computing and appropriately combining the generalized subqueries answers. The third approach is based on the assumptions that data graphs are partitioned in the distributed file system in such a way so as replication of data triples between the data segments is allowed. Data triples are replicated in such a way so as answers of generalized star queries, can be obtained from a single data segment. One and a half phase, scalable, MapReduce algorithm is proposed that efficiently computes the answer of the initial query Q by computing and appropriately combining the subquery answers. It is proved that, under certain conditions, the query can be answered in a single MapReduce phase. In the fourth approach, we propose an effective data model for storing RDF data in a document database using a maximum replication factor of 2 (i.e., in the worst-case scenario, the data graph will be doubled in storage size). The proposed storage model is utilized for efficiently evaluating BGP queries in a distributed manner. Each query is decomposed into a set of generalized star queries. The proposed data model ensures that no joining operations over multiple datasets are required to evaluate generalized star queries. The results of the evaluation of the generalized star subqueries of a query Q are then properly combined, in order to compute the answers of the initial query Q. The proposed approach has been implemented using MongoDB and Apache Spark.

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