Βελτιστοποίηση ερωτημάτων με πολλαπλά κριτήρια σε βάσεις δεδομένων
Loading...
Date
2007-09-24T08:15:05Z
Authors
Ρήγα, Γεωργία
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Το πρόβλημα της βελτιστοποίησης ερωτημάτων πολλαπλών κριτηρίων σε βάσεις δεδομένων είναι ένα αρκετά δύσκολο και ενδιαφέρον ερευνητικά πρόβλημα, διότι χαρακτηρίζεται από αντικρουόμενες απαιτήσεις. Κάθε βήμα στην απάντηση ενός ερωτήματος μπορεί να εκτελεστεί με παραπάνω από έναν τρόπους. Για την επίλυση τέτοιου είδους ερωτημάτων έχουν προταθεί διάφοροι αλγόριθμοι, με πιο πρόσφατους τους: Mariposa, M' και Generate Partitions. Ο Mariposa και ο Μ' εφαρμόζονται στην βάση δεδομένων Mariposa, η οποία δίνει την δυνατότητα στον χρήστη να καθορίζει την επιθυμητή εξισορόπηση (tradeoff) καθυστέρησης/κόστους για κάθε ερώτημα που θέτει. Ο αλγόριθμος Mariposa ακολουθεί μία προσέγγιση απληστίας (greedy approach) προσπαθώντας σε κάθε βήμα να μεγιστοποιήσει το «κέρδος» ενώ ο Μ' χρησιμοποιεί σύνολα βέτιστων κατά Pareto λύσεων για την επιλογή του επόμενου βήματος στην θέση του κριτηρίου απληστίας. Τέλος, ο αλγόριθμος Generate Partition χρησιμοποιεί έναν διαχωρισμό του χώρου απαντήσεων χρησιμοποιώντας δομές R-trees πετυχαίνοντας πολύ καλή απόδοση.
Description
Keywords
Βήματα, Λειτουργία, Πολυκριτηριακή, Στιγμιότυπο, Επικρατέστερος κατακερματιστής, Συσσωρευτικός βελτιστοποιητής, Ερώτημα