Μελέτη Μοντέλων Σχέσεων Κατεύθυνσης

Abstract

Την τελευταία δεκαετία υπάρχει αυξανόμενο ενδιαφέρον για τηνανάπτυξη συστημάτων που αποθηκεύουν και διαχειρίζονται χωρική πληροφορία. Η εργασία αυτή ασχολείται με τη μοντελοποίηση σχέσεων κατεύθυνσης μεταξύ χωρικών οντοτήτων. Επιπρόσθετα, μελετάμε προβλήματα που άπτονται της αποδοτικής αποτίμησης ερωτήσεων, οι οποίες εκφράζονται χρησιμοποιώντας σχέσεις κατεύθυνσης. Αρχικά εξετάζουμε το μοντέλο των Goyal και Egenhofer. Το μοντέλο περιγράφει σχέσεις κατεύθυνσης μεταξύ δύο περιοχών, πάνω στο καρτεσιανό επίπεδο. Παρουσιάζουμε από τη σχετική βιβλιογραφία τρεις αλγόριθμους για τον υπολογισμό των σχέσεων στο παραπάνω μοντέλο. Υλοποιούμε τους αλγόριθμους αυτούς και μετράμε πειραματικά την απόδοσή τους. Η ανάπτυξη αποδοτικών αλγορίθμων, οι οποίοι εξάγουν τηζητούμενη σχέση κατεύθυνσης από τις πολυγωνικές αναπαραστάσεις των περιοχών, συμβάλει καθοριστικά στην αποδοτική αποτίμηση ερωτήσεων που χρησιμοποιούν σχέσεις κατεύθυνσης. Στη συνέχεια εξετάζουμε το μοντέλο των Billen και Clementini. Το μοντέλο περιγράφει σχέσεις κατεύθυνσης μεταξύ τριών περιοχών. Παρουσιάζουμε δύο αλγορίθμους που αναπτύξαμε για τον υπολογισμό των σχέσεων κατεύθυνσης στο μοντέλο αυτό, καθώς και τις προτάσεις μας για την υλοποίησή τους. Τέλος, λαμβάνοντας υπόψη μας τα πλεονεκτήματα και τα μειονεκτήματα των παραπάνω μοντέλων, ορίζουμε αυστηρά μία νέα οικογένεια μοντέλων σχέσεων κατεύθυνσης. Τα μοντέλα που προτείνουμε, αποτελούν μία απλοποιημένη εκδοχή του μοντέλου των Goyal και Egenhofer. Χωρίς να χάνουμε σε εκφραστικότητα, καταφέρνουμε να μειώσουμε σημαντικά των αριθμό των σχέσεων του μοντέλου. Η παραπάνω μελέτη συμπληρώνεται μετην επίλυση του προβλήματος της σύνθεσης δύο σχέσεων κατεύθυνσης. Το πρόβλημα αυτό σχετίζεται άμεσα με την αποδοτική αποτίμηση ερωτήσεων σε περιβάλλοντα βάσεων δεδομένων.