Λεπτομέρειες

ΕίδοςΔιδακτορικό
ΚωδικόςPHD-2001-1
ΤίτλοςΘέματα Αποτίμησης Ερωτήσεων σε Βάσεις Δεδομένων με Περιορισμούς
ΣυγγραφέαςΣπύρος Σκιαδόπουλος
Έτος2001
Λέξεις κλειδιάΠεριορισμοί κατεύθυνσης, Γραμμικοί περιορισμοί, Λογισμός με περιορισμούς, Βάσεις δεδομένων με περιορισμούς, Αποτίμηση ερωτήσεων, Cardinal direction relations, Linear constraints, Constraint databases, Query evaluation
ΠερίληψηΤην τελευταία δεκαετία, υπάρχει αυξανόμενο ενδιαφέρον για την ανάπτυξη συστημάτων που αποθηκεύουν και διαχειρίζονται χωρική πληροφορία. Η διατριβή αυτή ασχολείται με τη μοντελοποίηση χωρικών δεδομένων και την αποδοτική αποτίμηση σχετικών ερωτήσεων σε περιβάλλοντα βάσεων δεδομένων με περιορισμούς. Αρχικώς, υιοθετείται από τη σχετική βιβλιογραφία το μοντέλο των βάσεων δεδομένων με μη-πλήρως ορισμένους περιορισμούς. Το εν λόγω μοντέλο μπορεί να αναπαραστήσει πλήρη, ελλιπή, πεπερασμένη και άπειρη χωρική πληροφορία. Η αποτίμηση ερωτήσεων στο παραπάνω μοντέλο αποτελεί ένα υπολογιστικά δύσκολο πρόβλημα. Κρίνεται, λοιπόν, αναγκαία η αναζήτηση περιπτώσεων όπου η αποτίμηση αυτή μπορεί να γίνει αποδοτικά, δηλαδή σε πολυωνυμικό χρόνο. Υποθέτοντας μια γενική κλάση περιορισμών $\\cal C$ καταδεικνύονται κλάσεις βάσεων δεδομένων με μη-πλήρως ορισμένους περιορισμούς και ερωτήσεις για τις οποίες το πρόβλημα αποτίμησης μπορεί να λυθεί αποδοτικά. Ακολούθως, αναζητούνται κατάλληλα στιγμιότυπα για τη γενική κλάση περιορισμών $\\cal C$ από υποκλάσεις των γραμμικών διαζευκτικών περιορισμών Horn. Δείχνεται ότι η κλάση των περιορισμών UTVPI$^{\\ne}$ είναι η μεγαλύτερη υποκλάση των γραμμικών διαζευκτικών περιορισμών Horn με την ιδιότητα της απαλοιφής μεταβλητών σε πολυωνυμικό χρόνο. Παράλληλα παρέχονται αποδοτικοί αλγόριθμοι για τον υπολογισμό της συνέπειας καθώς και της ολικής συνέπειας. Επαναδιατυπώνται τα γενικά θεωρήματα θέτοντας τη γενική κλάση να είναι μια από τις παραπάνω κλάσεις και αποδεικνύεται ότι τα αποτελέσματα ορίζουν επακριβώς το όριο μεταξύ αποδοτικών και μη-αποδοτικών περιπτώσεων αποτίμησης ερωτήσεων. Στη συνεχεία εξετάζονται πιο περιγραφικοί περιορισμοί για χωρικά δεδομένα. Αρχικά, ορίζουμε ένα νέο και αυστηρό μοντέλο για σχέσεις κατεύθυνσης μεταξύ συνεκτικών χωρικών περιοχών. Η προσέγγιση αυτή επεκτείνεται έτσι ώστε να περιλαμβάνει (α) μη-συνεκτικές περιοχές και περιοχές με οπές και (β) σημεία, γραμμές και περιοχές από τις οποίες απορρέουν γραμμές. Ακολούθως, παρουσιάζεται ο πρώτος αλγόριθμος για τον έλεγχο της συνέπειας ενός συνόλου από περιορισμούς κατεύθυνσης και αποδεικνύεται την ορθότητα του. Χρησιμοποιώντας τον αλγόριθμο αυτό δείχνεται ότι ο έλεγχος της συνέπειας ενός συνόλου από βασικούς (αντίστοιχα τυχαίους) περιορισμούς κατεύθυνσης γίνεται σε πολυωνυμικό χρόνο(αντίστοιχα είναι NP-complete). Στη συνέχεια, μελετάται η σύνθεση δύο σχέσεων κατεύθυνσης και προτείνονται εναλλακτικές μέθοδοι εξαγωγής νέας πληροφορίας. Τέλος, εξετάζονται τα προβλήματα της συνέπειας και της σύνθεσης για τις επεκτάσεις του βασικού μοντέλου.
ΚατηγορίαConstraint Databases


Επιστροφή στην αρχική σελίδα