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

ΕίδοςΔιδακτορικό
ΚωδικόςPHD-1994-1
ΤίτλοςΘεωρητικά Προβλήματα σε Βάσεις Δεδομένων με Χρονικούς Περιορισμούς
ΣυγγραφέαςΜανόλης Κουμπαράκης
Έτος1994
Λέξεις κλειδιάβάσεις δεδομένων με περιορισμούς, ελλειπής πληροφορία, χρονικοί περιορισμοί, constraint databases, incomplete information, temporal constraints
ΠερίληψηΣε πολλές προχωρημένες εφαρμογές είναι σημαντικό να μπορούμε να αναπαραστήσουμε πλήρη, ελλειπή, πεπερασμένη και άπειρη χρονική πληροφορία. Αυτή τη στιγμή δεν υπάρχει κανένα μοντέλο βάσεων δεδομένων που να προσφέρει αυτές τις δυνατότητες σ' ένα ενοποιημένο περιβάλλον. Πιστεύουμε ότι ο συνδυασμός των σχεσιακών βάσεων και των χρονικών περιορισμών προσφέρει ένα ισχυρό μοντέλο που μπορεί να ανταποκριθεί στις παραπάνω απαιτήσεις. Σ' αυτή τη διατριβή αναπτύσουμε την θεωρία των βάσεων δεδομένων με χρονικούς περιορισμούς και των ελλειπών βάσεων δεδομένων με χρονικούς περιορισμούς επεκτείνοντας το σχεσιακό μοντέλο. Αρχικά, αναπτύσουμε τρία παραμετροποιημένα μοντέλα βάσεων δεδομένων: τις M-σχεσιακές βάσεις, τις L-περιορισμένες βάσεις και τις ελλειπείς L-περιορισμένες βάσεις. Η γλώσσα L, η παράμετρος, ορίζει το αλφάβητο των περιορισμών και η M είναι η δομή που ερμηνεύει τους L-περιορισμούς. Τα τελευταία δύο μοντέλα είναι αυτά που θα μας απασχολήσουν ιδιαίτερα. Το μοντέλο των M-σχεσιακών βάσεων είναι απλώς ένα θεωρητικό εργαλείο για την ανάπτυξη της σημασιολογίας των άλλων δύο μοντέλων. Στη συνέχεια μελετούμε τα μοντέλα των βάσεων δεδομένων με χρονικούς περιορισμούς και των ελλειπών βάσεων δεδομένων με χρονικούς περιορισμούς σαν συγκεκριμένα παραδείγματα των παραπάνω παραμετροποιημένων μοντέλων. Καθ' οδόν αναπτύσσουμε αλγόριθμους απόφασης και απαλειφής ποσοδεικτών για μια σειρά από θεωρίες χρονικών περιορισμών. Οι σπουδαιότερες θεωρίες που εξετάζουμε είναι υποθεωρίες της αριθμητικής του Presburger (στην περίπτωση του διακριτού χρόνου) και της θεωρίας της πρόσθεσης των πραγματικών αριθμών με διάταξη (στην περίπτωση του πυκνού χρόνου). Κατόπιν, χρησιμοποιούμε αυτά τα αποτελέσματα για την ανάλυση της υπολογιστικής πολυπλοκότητας της απάντησης ερωτήσεων σε βάσεις δεδομένων με χρονικούς περιορισμούς και ελλειπείς βάσεις δεδομένων με χρονικούς περιορισμούς. Η ανάλυση μας δείχνει ότι η πολυπλοκότητα χειρότερης περίπτωσης του προβλήματος απάντησης ερωτήσεων του σχεσιακού λογισμού σε σχεσιακές βάσεις, και του σχεσιακού λογισμού με χρονικούς περιορισμούς σε βάσεις δεδομένων με χρονικούς περιορισμούς είναι η ίδια. Το ίδιο ισχύει και στις αντίστοιχες περιπτώσεις ελλειπών βάσεων.
ΚατηγορίαConstraint Databases
Αρχείο Επισκόπηση


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