Query Optimization Under Bag And Bag-set Semantics For Multiple Heterogeneous Data Sources

Abstract

Στην συγκεκριμένη διατριβή, μελετάμε ανάπτυξη τεχνικών βελτιστοποίησης ερωτημάτων με την χρήση όψεων, σε σχεσιακές και XML βάσεις δεδομένων. Ειδικότερα, επικεντρωνόμαστε στα ακόλουθα βασικά προβλήματα βελτιστοποίησης ερωτημάτων: την περιεκτικότητα ερωτημάτων, την αναδιατύπωση ερωτημάτων και την επιλογή όψεων. Στις σχεσιακές βάσεις δεδομένων, επικεντρωνόμαστε στα συζευκτικά ερωτήματα (εν συντομία CQs), που αντιστοιχούν σε SQL ερωτήματα με χρήση των τελεστών select, project και join. Επίσης, χρησιμοποιούμε σημασιολογίες πολυσυνόλου (οι βασικές σχέσεις και οι απαντήσεις των ερωτημάτων είναι πολυσύνολα) και συνόλου-πολυσυνόλου (οι βασικές σχέσεις είναι σύνολα, ενώ οι απαντήσεις είναι πολυσύνολα) για να περιγράψουμε, θεωρητικά, την σημασιολογία της SQL. Για ερωτήματα σε XML δεδομένα χρησιμοποιούμε την γλώσσα XPath, και ειδικότερα επικεντρωνόμαστε στις τρεις βασικές υποκλάσεις της γλώσσας, που σχηματίζεται από την χρήση δύο από τα τρία βασικά συστατικά: wildcard ετικέτες (*), ακμές απογόνου (//) και κλαδιά ([ ]).Στο πλαίσιο της περιεκτικότητας ερωτημάτων μελετάμε το πρόβλημα, καθώς και την πολυπλοκότητα του, για βασικές υποκλάσεις των CQs. Για την γενική κλάση των CQs το πρόβλημα παραμένει ανοικτό εδώ και μια δεκαετία. Επιπλέον, μελετάμε τα προβλήματα περιεκτικότητας και ισοδυναμίας για ενώσεις XPath ερωτημάτων.Για την αναδιατύπωση CQ ερωτημάτων, περιγράφουμε βασικές συνθήκες που πρέπει να πληρούν οι όψεις έτσι ώστε να υπάρχει μία ισοδύναμη αναδιατύπωση. Για τα XPath ερωτήματα που σχηματίζονται από // και *, δείχνουμε ότι η χρήση του τελεστή ένωσης απαιτείται για την εύρεση ισοδύναμης αναδιατύπωσης. Το πρόβλημα επιλογής όψεων μελετάται για CQ ερωτήματα, όπου επικεντρωνόμαστε στον περιορισμό του χώρου αναζήτησης βέλτιστων λύσεων. Ειδικότερα, δείχνομαι ότι εάν η επιλογή του συνόλου όψεων γίνεται βάσει συγκεκριμένων συνθηκών (ως προς την μορφή των όψεων), τότε εξασφαλίζεται η εύρεση τουλάχιστον μίας βέλτιστης λύσης για το πρόβλημα. Έπειτα, επικεντρωνόμενοι σε υποκλάσεις των CQ ερωτημάτων, δείχνουμε ότι για ένα σύνολο ερωτημάτων αλυσίδας, και για τις δύο σημασιολογίες, όψεις που ορίζονται, και αυτές, από ερωτήματα αλυσίδας δεν επαρκούν, πάντα, για την εύρεση βέλτιστης λύσης. Στην περίπτωση, όμως, των ερωτημάτων μονοπατιού, και θεωρώντας σημασιολογία πολυσυνόλου, δείχνουμε ότι οι όψεις που ορίζονται από ερωτήματα μονοπατιού μας εξασφαλίζουν την εύρεση τουλάχιστον μίας βέλτιστης λύσης για το πρόβλημα επιλογής όψεων.