Διαχείριση Πληροφορίας και Αβεβαιότητας σε Περιβάλλον Πολλαπλών Ετερογενών Πηγών Πληροφόρησης. - Βασιλακόπουλος, Άγγελος (Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, 2014)
Η συγκεκριμένη διατριβή αφορά τη μελέτη πέντε προβλημάτων για βάσεις δεδομένων με αβεβαιότητα και γενεαλογία. Ειδικότερα ξεκινά με την ανάλυση και μελέτη του προβλήματος της περιεκτικότητας και ισοδυναμίας ερωτημάτων (query containment and equivalence) για βάσεις δεδομένων αυτού του είδους. Παρουσιάζονται και ορίζονται πέντε νέα είδη σημασιολογίας της περιεκτικότητας βάσεων δεδομένων με αβεβαιότητα και γενεαλογία. Αποδεικνύεται πως η πολυπλοκότητα του προβλήματος περιεκτικότητας ερωτημάτων για βάσεις δεδομένων με αβεβαιότητα και γενεαλογία και συνεκτικές επερωτήσεις (conjunctive queries) και ενώσεις τους παραμένει όπως και στις κλασσικές βάσεις NP-Complete και για τα πέντε νέα είδη σημασιολογίας της περιεκτικότητας. Αποδεικνύεται πως το ίδιο ισχύει και για της ισοδυναμία ερωτημάτων για τα πρώτα δύο είδη περιεκτικότητας, ενώ για τα τελευταία τρία η πολυπλοκότητα είναι Graph-Isomorphism-complete. Έπειτα γίνεται ανάλυση και μελέτη του προβλήματος της ανταλλαγής δεδομένων (data exchange) για βάσεις δεδομένων με αβεβαιότητα και γενεαλογία. Παρουσιάζεται και ορίζεται μια νέα λογική σημασιολογία βέβαιων απαντήσεων (certain answers) για αυτές τις βάσεις. Παρουσιάζεται ένας νέος u-chase αλγόριθμος που επεκτείνει τον υπάρχοντα chase αλγόριθμο που αφορά κλασσικές βάσεις. Αποδεικνύεται πως ο νέος u-chase μπορεί να χρησιμοποιηθεί για την απάντηση συνεκτικών επερωτήσεων με πολυπλοκότητα υπολογισμού βέβαιων απαντήσεων η οποία παραμένει χαμηλή πολυωνυμικού χρόνου (Ptime) όπως και στις κλασσικές βάσεις όταν το σύνολο απεικονίσεων μεταξύ αρχικού και τελικού σχήματος είναι ένα αδυνάμως ακυκλικό σύνολο περιορισμών δημιουργίας tuples (tuple generating dependencies- tgds). Αποδεικνύεται επιπλέον πως αν έχουμε απεικονίσεις τελικού σχήματος που παράγουν ισότητες (equality generating dependencies - egds) τότε το πρόβλημα query answering για ανταλλαγή δεδομένων με αβεβαιότητα και γενεαλογία έχει αυξημένη πολυπλοκότητα NP-hard. Στη συνέχεια γίνεται ανάλυση και μελέτη του προβλήματος της απάντησης συνεκτικών επερωτήσεων πάνω σε βάσεις δεδομένων με αβεβαιότητα και γενεαλογία με προσάρτηση βαθμών αβεβαιότητας που προέρχονται από μια ενδεχομενική κατανομή (possibility distribution). Αποδεικνύεται ότι το μοντέλο για βάσεις δεδομένων με αβεβαιότητα και γενεαλογία με προσάρτηση βαθμών αβεβαιότητας που προέρχονται από μια ενδεχομενική κατανομή είναι κλειστό για συνεκτικές επερωτήσεις, σε λύση του προβλήματος προηγούμενων αποτελεσμάτων που δείχνουν ότι η ενδεχομενική κατανομή σε αβέβαιες βάσεις (χωρίς γενεαλογία) δεν είναι κλειστή για συνεκτικές επερωτήσεις. Αποδεικνύεται ότι στο μοντέλο βάσεων δεδομένων με αβεβαιότητα και γενεαλογία με προσάρτηση βαθμών αβεβαιότητας που προέρχονται από μια ενδεχομενική κατανομή οι απαντήσεις σε συνεκτικές επερωτήσεις μπορεί να γίνει με χαμηλή πολυωνυμίκη πολυπλοκότητα (Ptime) σε αντίθεση με την υψηλή πολυπλοκότητα #P της υπάρχουσας βιβλιογραφίας στην οποία γίνεται χρήση του πιθανοτικού μοντέλο για τους βαθμούς αβεβαιότητας. Το τέταρτο πρόβήμα που μελετάται αφορά την ανάλυση και μελέτη του προβλήματος του αποτελεσματικού (efficient) υπολογισμού συνενοτικών επερωτημάτων (aggregate queries) και συγκεκριμένα απαντήσεις για το άθροισμα SUM πάνω σε δεδομένα μεγάλου όγκου (big data), κάνοντας χρήση μιας μικρής χρήσιμης γενεαλογίας αντί των πολύ μεγάλων αρχικών δεδομένων. Παρουσιάζεται ο Αλγόριθμος Comp-Lineage που υπολογίζει σε χρόνο πολυωνυμικό μια Aggregate Lineage με μικρό μέγεθος που είναι ανεξάρτητο του μεγέθους των αρχικών δεδομένων. Αποδεικνύεται ότι η μικρή αυτή Aggregate Lineage μπορεί να χρησιμοποιηθεί για την καλή προσέγγιση οποιασδήποτε SUM επερώτησης της οποίας η απάντηση-άθροισμα είναι μεγάλη, με χρονική πολυπλοκότητα που σχετίζεται με το μικρό της Lineage και άρα ανεξάρτητη με το μεγάλο μέγεθος των αρχικών δεδομένων. Τέλος γίνεται ανάλυση, μελέτη και προγραμματιστική υλοποίηση σε παράλληλο περιβάλλον MapReduce του προβλήματος υπολογισμού της διμερούς σύζευξης (2-way Join) για μεγάλα δεδομένα (big data) που μπορεί να έχουν ανισομερή κατανομή (data skew). Παρουσιάζεται ένας νέος αλγόριθμος, κατάλληλος για το περιβάλλον του MapReduce, o oποίος αφορά το πρόβλημα του υπολογισμού της διμερούς σύζευξης (2-way Join) και μπορεί να διαχειριστεί αποτελεσματικά το data skewness σε αντίθεση με τις υπάρχουσες υλοποιήσεις. Αποδεικνύεται ότι ο αλγόριθμος που παρουσιάζεται έχει το ελάχιστο δυνατό κόστος επικοινωνίας. Επιπλέον γίνεται προγραμματιστική υλοποίηση σε Java/Hadoop του αλγορίθμου με πειράματα που επαληθεύουν το θεωρητικό ελάχιστο κόστος επικοινωνίας.