Μελέτη Μεθόδων Λήψης Απόφασης Με Πολλαπλά Κριτήρια Μέσω Ερωτημάτων Κορυφογραμμής.

Abstract

Ο σκοπός της διπλωματικής εργασίας ήταν η μελέτη της λήψης αποφάσεων με πολλαπλά κριτήρια σε βάσεις δεδομένων με τη βοήθεια του τελεστή κορυφογραμμής (skyline). Το skyline ενός συνόλου σημείων ορίζεται ως τα σημεία εκείνα που δεν κυριαρχούνται από κανένα άλλο, λαμβάνοντας υπόψη ένα σύνολο από τις διαστάσεις του. Έχουν προταθεί αρκετοί αλγόριθμοι υπολογισμού του skyline. Το βασικό πρόβλημα είναι ότι ένας skyline αλγόριθμος πρέπει να είναι υπολογιστικά αποτελεσματικός και να έχει μικρό κόστος εισόδου εξόδου (Ι/Ο). Ιδιαίτερο ενδιαφέρον παρουσιάζει επίσης η περίπτωση που το skyline μιας βάσης δεδομένων είναι μεγαλύτερο από τη διαθέσιμη μνήμη του συστήματος, φαινόμενο αρκετά συχνό λόγω της ραγδαίας αύξησης του μεγέθους των βάσεων δεδομένων τα τελευταία χρόνια.Στην παρούσα διπλωματική, μελετήθηκαν και υλοποιήθηκαν δύο αλγόριθμοι για τον υπολογισμό του skyline στην εξωτερική μνήμη. Ο ένας αλγόριθμος είναι ο Sort and Limit Skyline Algorithm (SALSA) που αξιοποιεί την ιδέα της ταξινόμησης των δεδομένων εισόδου, έτσι ώστε να περιοριστεί άμεσα ο αριθμός των πλειάδων που θα διαβαστεί και θα λάβει μέρος σε ελέγχους κυριαρχίας (dominance checks). Ταξινομώντας τα σημεία με τη βοήθεια συμμετρικών συναρτήσεων, ο αριθμός των πλειάδων που πρέπει να διαβαστούν ελαχιστοποιείται. Ο δεύτερος αλγόριθμος είναι ο Object Space Partitioning (OSP), που βασίζεται στην ιδέα της οργάνωσης των skyline σημείων σε ένα δέντρο, που ορίζει έναν αναδρομικό κατακερματισμό του χώρου (space partitioning). Mε τη βοήθεια αυτού του skyline δέντρου κάθε υποψήφιο skyline σημείο χρειάζεται να ελεγχθεί για κυριαρχία μόνο με ένα μικρό σύνολο των ήδη υπάρχοντων skyline σημείων, το οποίο μειώνεται, όσο αυξάνεται η διάσταση των σημείων.Καλούμενοι να λύσουμε το πρόβλημα της εύρεσης του skyline σε περιορισμένη κύρια μνήμη οι παραπάνω αλγόριθμοι υλοποιήθηκαν ως external αλγόριθμοι, χρησιμοποιώντας για την αποθήκευση των δεδομένων, αρχεία όπου τα δεδομένα αποθηκεύονται ανά μπλοκ (blockfiles).