Query optimization under bag and bag-set semantics for multiple heterogeneous data sources

Abstract

In this thesis, we investigate techniques for query optimization using a set of views, considering bothrelational and XML databases. In particular, we focus on three fundamental problems of queryoptimization; which are the query containment, the query rewriting and the view selection.For relational databases we focus on the class of select-project-join SQL queries with equalitycomparisons, a.k.a. conjunctive queries (CQs for short). We consider two kinds of semantics totheoretically approximate the SQL semantics: the bag (multiple occurrences of the same tuple areallowed in both base relations and answers of queries) and bag-set semantics (the base relations aresets and the operators are liable for bag-results). For XML databases, we focus on XPath. Especially,we focus on the major fragments of XPath which contain two of the constructs: wildcard, descendantedge and branches.Query containment under both bag and bag-set semantics is investigated through a detailed analysisof special cases of CQs. The complexity in each case is given, as well. For the general case, theproblem remains open for more than a decade. Moreover, we give necessary and sufficientconditions for deciding both containment and equivalence for unions of XPath queries; a problemwhich was not investigated in depth, in the past.The problem of finding an equivalent rewriting is also investigated for both relational and XPathqueries. In particular, for relational queries, we describe the requirements that a set of views have tosatisfy in order to give an equivalent rewriting of a CQ under both bag and bag-set semantics. In thecase of XML databases, we investigate the problem of rewriting an XPath query using multiple views,and prove that in the case that the query contains both descendant edges and wildcards, the unionoperator may be required for finding an equivalent rewriting.The view selection is investigated for workloads of CQs under both bag and bag-set semantics.Especially, we aim to limit the search space of candidate viewsets. We start with the general case,where we give a tight condition that candidate views can satisfy and still the search space doescontain at least one optimal solution. Then we study special cases. We show that for chain queryworkloads under both bag and bag-set semantics, taking only chain views may miss optimal solution,whereas, if we further limit the queries to be path queries, then under bag semantics, path viewssuffice.

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