Διαχείριση Πληροφορίας Και Αβεβαιότητας Σε Περιβάλλον Πολλαπλών Ετερογενών Πηγών Πληροφόρησης.

Abstract

Η συγκεκριμενη διατριβη ξεκινα με την πολυπλοκοτητα του προβληματος περιεκτικοτητας ερωτηματων σε βασεις με αβεβαιοτητα και γενεαλογια, για συνεκτικες επερωτησεις και ενωσεις τους, η οποια παραμενει οπως και στις κλασσικες βασεις NP-Complete για πεντε νεα ειδη σημασιολογιας.Επειτα γινεται αναλυση του προβληματος της ανταλλαγης ετερογενων δεδομενων για βασεις δεδομενων με αβεβαιοτητα και γενεαλογια. Παρουσιαζεται ενας νεος αλγοριθμος και αποδεικνυεται πως μπορει να χρησιμοποιηθει για την απαντηση συνεκτικων επερωτησεων με πολυπλοκοτητα υπολογισμου βεβαιων απαντησεων πολυωνυμικου χρονου οταν το συνολο απεικονισεων μεταξυ αρχικου και τελικου σχηματος ειναι ενα αδυναμως ακυκλικο συνολο περιορισμων δημιουργιας tuples. Αντιθετα αν εχουμε απεικονισεις που παραγουν ισοτητες τοτε το προβλημα εχει αυξημενη πολυπλοκοτητα NP-hard.Στη συνεχεια γινεται αναλυση του προβληματος της απαντησης συνεκτικων επερωτησεων πανω σε αβεβαιες βασεις με γενεαλογια και προσαρτηση ενδεχομενικων βαθμων αβεβαιοτητα. Αποδεικνυεται οτι το μοντελο αυτο βασεων ειναι κλειστο για συνεκτικες επερωτησεις και επισης πως συνεκτικες επερωτησεις μπορουν να υπολογισθουν με χαμηλη πολυωνυμικη πολυπλοκοτητα σε αντιθεση με την υπαρχουσα υψηλη πολυπλοκοτητα #P οπου γινεται χρηση πιθανοτητων.Το τεταρτο προβημα που μελεταται αφορα την αναλυση και μελετη του προβληματος του αποτελεσματικου υπολογισμου συνενοτικων επερωτηματων και συγκεκριμενα απαντησεων για το αθροισμα SUM πανω σε δεδομενα μεγαλου ογκου κανοντας χρηση μιας μικρης χρησιμης γενεαλογιας αντι των πολυ μεγαλων αρχικων δεδομενων. Παρουσιαζεται ο Αλγοριθμος Comp- Lineage που υπολογιζει σε χρονο πολυωνυμικο μια Aggregate Lineage με μικρο μεγεθος που ειναι ανεξαρτητο του μεγεθους των αρχικων δεδομενων. Αποδεικνυεται οτι η μικρη αυτη Aggregate Lineage μπορει να χρησιμοποιηθει για την καλη προσεγγιση οποιασδηποτε SUM επερωτησης της οποιας η απαντηση-αθροισμα ειναι μεγαλη, με χρονικη πολυπλοκοτητα που σχετιζεται με το μικρο της Lineage και αρα ανεξαρτητη με το μεγαλο μεγεθος των αρχικων δεδομενων.Τελος γινεται αναλυση, μελετη και προγραμματιστικη υλοποιηση σε παραλληλο περιβαλλον MapReduce του προβληματος υπολογισμου της διμερους συζευξης για μεγαλα δεδομενα που μπορει να εχουν ανισομερη κατανομη, μεσω ενος νεου αλγοριθμου που εχει το ελαχιστο δυνατο κοστος επικοινωνιας. Επιπλεον γινεται προγραμματιστικη υλοποιηση σε Java/Hadoop του αλγοριθμου με πειραματα που επαληθευουν το θεωρητικο ελαχιστο κοστος επικοινωνιας.