Graph metrics as predictors of schema evolution for relational databases
Φόρτωση...
Ημερομηνία
Συγγραφείς
Κολοζώφ, Μιχάλης–Ρωμανός
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Databases evolve over time and their evolution does not only concern their contents,
but also their internal structure, or schema. Schema evolution impacts deeply, both
the database itself, and the surrounding applications that need to adapt too. The
study of the mechanisms and patterns via which database schemata evolve is
important as it can allow the in-advance planning of design, maintenance and
resource allocation with a view to the future.
In this thesis, we focus on the study of the evolution of foreign keys in the context of
schema evolution. Foreign keys are mechanisms that constraint data entry in
relational tables, imposing that the domain of the contents of a table’s attribute is a
subset of the contents of an attribute of another, lookup, table. Despite the
importance of foreign keys, as an integrity constraint that guarantees consistency
among the values of different tables, the study of their evolution is a topic that –to
the best of our knowledge- has never been studied in the literature before.
We have studied the schema histories of a six free, open-source databases that
contained foreign keys. To facilitate a quantitative study, we model each version of
the schema as a graph, with tables as nodes and foreign keys as directed edges
(stemming from the referencing table to the referenced one). Our findings concerning
the growth of nodes verify previous results that schemata slowly grow over time in
terms of tables. Moreover, we have come to several surprising, new findings in terms
of the schema edges (foreign keys). Foreign keys appear to be fairly scarce in the
projects that we have studied and they do not necessarily grow in synch with table
growth. In fact, we have observed different “cultures” for the handling of foreign
keys, ranging from full sync with the growth of nodes to the unexpected extreme of
full removal of foreign keys from the schema of the database. Node degrees and survival are related with an inverse gamma pattern: the few nodes with high degrees
stand higher chances of survival than average. Similarly, nodes with inciting edges
with high values for edge betweenness centrality frequently (but not always) stand
higher chances to survive compared to the nodes with a single or zero inciting edges,
which have significantly higher chances of removal.
Οι βάσεις δεδομένων εξελίσσονται με την πάροδο του χρόνου και η εξέλιξη τους δεν αφορά μόνο το περιεχόμενό τους, αλλά και την εσωτερική τους δομή, ή το Σχήμα. Η εξέλιξη του Σχήματος επιδρά βαθιά, στην ίδια τη βάση δεδομένων, και στις γύρω εφαρμογές που πρέπει να προσαρμοστούν πολύ, προκειμένου να αποφευχθεί (α) η αποτυχία λειτουργίας (λόγω αναφορών σε ανύπαρκτα στοιχεία του σχήματος), (β) η απώλεια πληροφοριών (λόγω της μη-συσχέτιση των νέων δεδομένων), ή (γ) οι σημασιολογικές αντιφάσεις (σε περίπτωση που η σημασιολογία των απόψεων αλλάξει). Η μελέτη των μηχανισμών και των προτύπων μέσω των οποίων εξελίσσονται τα σχήματα βάσης δεδομένων είναι σημαντική, καθώς μπορεί να επιτρέψει τον εκ των προτέρων σχεδιασμό για την ανάπτυξη εφαρμογών, συντήρησης της βάσης δεδομένων και την κατανομή των πόρων, με στόχο το μέλλον. Προς το παρών οι γνώσεις μας για τέτοιους μηχανισμούς ή μοτίβα είναι ακόμα στα πρώτα της βήματα, κυρίως λόγω της επί μακρόν έλλειψης ιστοριών σχήματος. Μέχρι σήμερα, η σχετική βιβλιογραφία μετράει μόνο λίγες μελέτες επί του θέματος, αξιοποιώντας κυρίως τις ιστορίες σχήματος των ελεύθερων, ανοικτού κώδικα έργων που δημοσιεύουν ολόκληρο τον κώδικά τους (συμπεριλαμβανομένου του σχήματος της υποκείμενης βάσης δεδομένων τους) σε αποθήκες δημόσιου λογισμικού. Σε αυτή την εργασία, θα επικεντρωθούμε στη μελέτη της εξέλιξης των ξένων κλειδιών στο πλαίσιο της εξέλιξης του σχήματος. Ξένα κλειδιά είναι οι μηχανισμοί που περιορίζουν την εισαγωγή δεδομένων σε σχεσιακούς πίνακες, επιβάλλοντας ότι ο τομέας των περιεχομένων του χαρακτηριστικού ενός πίνακα είναι ένα υποσύνολο των περιεχομένων ενός χαρακτηριστικού του άλλου, πίνακας αναζήτησης, (παρέχοντας ό, τι είναι επίσης γνωστό ως active domain του αναφερόμενου χαρακτηριστικού). Έτσι, τα ξένα κλειδιά αποτελούν βασικό μηχανισμό για τη διασφάλιση της ακεραιότητας των δεδομένων και τη συνοχή μεταξύ των τιμών σε διαφορετικούς πίνακες. Παρά τη σημασία των ξένων κλειδιών, ως περιορισμό ακεραιότητας, η μελέτη της εξέλιξής τους είναι ένα θέμα που – από όσο γνωρίζουμε – δεν έχει ποτέ μελετηθεί στη βιβλιογραφία πριν. Η συσχετιζόμενη δουλειά έχει επικεντρωθεί στην μελέτη για την εξέλιξη των πινάκων και των χαρακτηριστικών, αφήνοντας τη μελέτη των ξένων κλειδιών ανέγγιχτη. Έχουμε συλλέξει τις ιστορίες σχημάτων από έξι βάσεις δεδομένων ανοικτού κώδικα που περιείχαν ξένα κλειδιά, και τις επεξεργαστήκαμε για να ανακαλύψουμε τις αλλαγές που συνέβησαν στια συνεχόμενα releases τους. Έτσι, η ιστορία των εκδόσεων έχει συμπληρωθεί από ένα ιστορικό μεταβάσεων μεταξύ μεταγενέστερες εκδόσεις. Στη συνέχεια, μελετήσαμε τα χαρακτηριστικά της εξέλιξης των ξένων κλειδιών. Για να διευκολυνθεί μια ποσοτική μελέτη, μοντελοποιήσαμε κάθε σχήμα ως γράφημα, με τους πίνακες ως κόμβους και τα ξένα κλειδιά ως κατευθυνόμενες ακμές (που προκύπτει από τον πίνακα αντιστοίχησης με τον αναφερόμενο). Επιπλέον, με την πράξη της ένωση της ιστορίας αυτών των γραφημάτων, δημιουργήσαμε τον Διαχρονικό Γράφο της ιστορίας του σχήματος ο οποίος περιέχει όλους τους πίνακες και όλα τα ξένα κλειδιά που υπήρξαν ποτέ στην ιστορία του σχήματος. Βάση αυτού του μοντελοποιημένου γραφήματος, αξιολογήσαμε πολλές γράφο-θεωρητικές ιδιότητες, τόσο όσον αφορά το σύνολο του σχήματος αλλά και από την άποψη των μεμονωμένων κόμβων και ακμών. Η προσπάθειά μας έχει διευκολυνθεί από ένα εργαλείο που έχουμε αναπτύξει, με το όνομα Παρμενίδεια Αλήθεια, το οποίο (α) κατασκευάζει το Διαχρονικό Γράφο της ιστορίας, (β) τον χρησιμοποιεί ως μέσο συνοχής για την οπτικοποίηση της κάθε διαφορετικής έκδοσης του σχήματος, (γ) εξάγει την ιστορία του σχήματος ως μια παρουσίαση σε PowerPoint, βίντεο, ένα σύνολο εικόνων, και ένα σύνολο αρχείων GraphML, και (δ) παράγει αναφορές για διαφορετικές γραφοθεωρητικες μέτρικες σε csv αρχεία, διευκολύνοντας έτσι την μετέπειτα ανάλυσή τους. Τα ευρήματά μας συνοψίζονται ως εξής: Τα Σχήματα αυξάνονται με την πάροδο του χρόνου από την σκοπιά των κόμβων (πίνακες). Η ανάπτυξη είναι ομαλή και αργή, με αρκετές περιόδους ηρεμίας. Αυτό είναι ένα πολύ γνωστό αποτέλεσμα από την υπάρχουσα βιβλιογραφία που έχει επίσης επαληθευτεί από τη μελέτη μας. Οι ακμές (ξένα κλειδιά) δεν αναπτύσσονται απαραίτητα σε συγχρονισμό με την ανάπτυξη των πινάκων. Στην πραγματικότητα, έχουμε παρατηρήσει διαφορετικές "κουλτούρες" για το χειρισμό των ξένων κλειδιών. Σε δύο περιπτώσεις που αφορούν επιστημονικές βάσεις δεδομένων (Atlas, Biosql), τα ξένα κλειδιά αποτελούν αναπόσπαστο μέρος του σχήματος, εκτείνονται σε ένα τεράστιο ποσοστό των πινάκων και συνεξελίσσονται μαζί τους. Σε δύο άλλες περιπτώσεις, επίσης επιστημονικής φύσης (Egee και Castor), μόνο ένα υποσύνολο των πινάκων συμμετέχουν σε συσχετίσεις ξένων κλειδιών και η εξέλιξή τους είναι διττή: Η Egee (με πολύ μικρού μεγέθους Σχήμα) έχει μια ισχυρή συσχέτιση μεταξύ πινάκων και εξέλιξης ξένων κλειδιών, ενώ ο Castor (με ένα μικρό ποσοστό των πινάκων να εμπλέκονται σε ξένα κλειδιά) έχει ανάμικτη συμπεριφορά σε όλη την ιστορία της εξέλιξή του. Η μεγαλύτερη έκπληξη ήρθε από τα σχήματα Συστήματος Διαχείρισης Περιεχομένου (CMS), SlashCode και Zabbix, όπου τα ξένα κλειδιά εμπλέκονται μόνο σε μια μικρή μειοψηφία των πινάκων. Προς μεγάλη μας έκπληξη, τα ξένα κλειδιά σε αυτά τα έργα, μετά από μια περίοδο ανάπτυξης, αφαιρούνται από το σύστημα (α) με μια απότομη απομάκρυνση στην πρώτη περίπτωση, και (β) με μια αργή αλλά σταθερή ταχύτητα απομάκρυνσης στην δεύτερη. Η συνολική μας εντύπωση είναι ότι, με την εξαίρεση κάποιων περιβαλλόντων με αυστηρή τήρηση των υπαγορεύσεων της σχεσιακής θεωρίας, τα ξένα κλειδιά είναι σπάνια και ενίοτε ανεπιθύμητα. Όσον αφορά τη συμπεριφορά μεμονωμένων κόμβων, φαίνεται ότι ο βαθμός και η επιβίωση σχετίζονται θετικά μεταξύ τους, και, στην πραγματικότητα, υπάρχει ένα μοτίβο αντίστροφου - Γ στο συσχετισμό βαθμού και επιβίωσης. Το μοτίβο προτείνει ότι οι χαμηλοί σε βαθμούς κόμβοι φέρουν μη αμελητέα πιθανότητα απομάκρυνσης για τους αντίστοιχους πίνακες- ταυτόχρονα, οι υψηλόβαθμοι, αν και αρκετά σπάνια, φέρουν πιθανότητα διαγραφής 5% -19% χαμηλότερα από το μέσο όρο. Έχουμε μελετήσει επίσης κόμβους για τον συντελεστή ομαδοποίησή τους και την κεντρικότητά τους με μάλλον αμφίβολα αποτελέσματα όσον αφορά την επιβίωση του κόμβου. Τέλος, φαίνεται ότι οι κόμβοι που εφάπτονται με υψηλά score σε betweenness - centrality, συχνά (αλλά όχι πάντα) έχουν υψηλότερες πιθανότητες επιβίωσης από κόμβους με μία ή καμία προσκείμενη ακμή.
Οι βάσεις δεδομένων εξελίσσονται με την πάροδο του χρόνου και η εξέλιξη τους δεν αφορά μόνο το περιεχόμενό τους, αλλά και την εσωτερική τους δομή, ή το Σχήμα. Η εξέλιξη του Σχήματος επιδρά βαθιά, στην ίδια τη βάση δεδομένων, και στις γύρω εφαρμογές που πρέπει να προσαρμοστούν πολύ, προκειμένου να αποφευχθεί (α) η αποτυχία λειτουργίας (λόγω αναφορών σε ανύπαρκτα στοιχεία του σχήματος), (β) η απώλεια πληροφοριών (λόγω της μη-συσχέτιση των νέων δεδομένων), ή (γ) οι σημασιολογικές αντιφάσεις (σε περίπτωση που η σημασιολογία των απόψεων αλλάξει). Η μελέτη των μηχανισμών και των προτύπων μέσω των οποίων εξελίσσονται τα σχήματα βάσης δεδομένων είναι σημαντική, καθώς μπορεί να επιτρέψει τον εκ των προτέρων σχεδιασμό για την ανάπτυξη εφαρμογών, συντήρησης της βάσης δεδομένων και την κατανομή των πόρων, με στόχο το μέλλον. Προς το παρών οι γνώσεις μας για τέτοιους μηχανισμούς ή μοτίβα είναι ακόμα στα πρώτα της βήματα, κυρίως λόγω της επί μακρόν έλλειψης ιστοριών σχήματος. Μέχρι σήμερα, η σχετική βιβλιογραφία μετράει μόνο λίγες μελέτες επί του θέματος, αξιοποιώντας κυρίως τις ιστορίες σχήματος των ελεύθερων, ανοικτού κώδικα έργων που δημοσιεύουν ολόκληρο τον κώδικά τους (συμπεριλαμβανομένου του σχήματος της υποκείμενης βάσης δεδομένων τους) σε αποθήκες δημόσιου λογισμικού. Σε αυτή την εργασία, θα επικεντρωθούμε στη μελέτη της εξέλιξης των ξένων κλειδιών στο πλαίσιο της εξέλιξης του σχήματος. Ξένα κλειδιά είναι οι μηχανισμοί που περιορίζουν την εισαγωγή δεδομένων σε σχεσιακούς πίνακες, επιβάλλοντας ότι ο τομέας των περιεχομένων του χαρακτηριστικού ενός πίνακα είναι ένα υποσύνολο των περιεχομένων ενός χαρακτηριστικού του άλλου, πίνακας αναζήτησης, (παρέχοντας ό, τι είναι επίσης γνωστό ως active domain του αναφερόμενου χαρακτηριστικού). Έτσι, τα ξένα κλειδιά αποτελούν βασικό μηχανισμό για τη διασφάλιση της ακεραιότητας των δεδομένων και τη συνοχή μεταξύ των τιμών σε διαφορετικούς πίνακες. Παρά τη σημασία των ξένων κλειδιών, ως περιορισμό ακεραιότητας, η μελέτη της εξέλιξής τους είναι ένα θέμα που – από όσο γνωρίζουμε – δεν έχει ποτέ μελετηθεί στη βιβλιογραφία πριν. Η συσχετιζόμενη δουλειά έχει επικεντρωθεί στην μελέτη για την εξέλιξη των πινάκων και των χαρακτηριστικών, αφήνοντας τη μελέτη των ξένων κλειδιών ανέγγιχτη. Έχουμε συλλέξει τις ιστορίες σχημάτων από έξι βάσεις δεδομένων ανοικτού κώδικα που περιείχαν ξένα κλειδιά, και τις επεξεργαστήκαμε για να ανακαλύψουμε τις αλλαγές που συνέβησαν στια συνεχόμενα releases τους. Έτσι, η ιστορία των εκδόσεων έχει συμπληρωθεί από ένα ιστορικό μεταβάσεων μεταξύ μεταγενέστερες εκδόσεις. Στη συνέχεια, μελετήσαμε τα χαρακτηριστικά της εξέλιξης των ξένων κλειδιών. Για να διευκολυνθεί μια ποσοτική μελέτη, μοντελοποιήσαμε κάθε σχήμα ως γράφημα, με τους πίνακες ως κόμβους και τα ξένα κλειδιά ως κατευθυνόμενες ακμές (που προκύπτει από τον πίνακα αντιστοίχησης με τον αναφερόμενο). Επιπλέον, με την πράξη της ένωση της ιστορίας αυτών των γραφημάτων, δημιουργήσαμε τον Διαχρονικό Γράφο της ιστορίας του σχήματος ο οποίος περιέχει όλους τους πίνακες και όλα τα ξένα κλειδιά που υπήρξαν ποτέ στην ιστορία του σχήματος. Βάση αυτού του μοντελοποιημένου γραφήματος, αξιολογήσαμε πολλές γράφο-θεωρητικές ιδιότητες, τόσο όσον αφορά το σύνολο του σχήματος αλλά και από την άποψη των μεμονωμένων κόμβων και ακμών. Η προσπάθειά μας έχει διευκολυνθεί από ένα εργαλείο που έχουμε αναπτύξει, με το όνομα Παρμενίδεια Αλήθεια, το οποίο (α) κατασκευάζει το Διαχρονικό Γράφο της ιστορίας, (β) τον χρησιμοποιεί ως μέσο συνοχής για την οπτικοποίηση της κάθε διαφορετικής έκδοσης του σχήματος, (γ) εξάγει την ιστορία του σχήματος ως μια παρουσίαση σε PowerPoint, βίντεο, ένα σύνολο εικόνων, και ένα σύνολο αρχείων GraphML, και (δ) παράγει αναφορές για διαφορετικές γραφοθεωρητικες μέτρικες σε csv αρχεία, διευκολύνοντας έτσι την μετέπειτα ανάλυσή τους. Τα ευρήματά μας συνοψίζονται ως εξής: Τα Σχήματα αυξάνονται με την πάροδο του χρόνου από την σκοπιά των κόμβων (πίνακες). Η ανάπτυξη είναι ομαλή και αργή, με αρκετές περιόδους ηρεμίας. Αυτό είναι ένα πολύ γνωστό αποτέλεσμα από την υπάρχουσα βιβλιογραφία που έχει επίσης επαληθευτεί από τη μελέτη μας. Οι ακμές (ξένα κλειδιά) δεν αναπτύσσονται απαραίτητα σε συγχρονισμό με την ανάπτυξη των πινάκων. Στην πραγματικότητα, έχουμε παρατηρήσει διαφορετικές "κουλτούρες" για το χειρισμό των ξένων κλειδιών. Σε δύο περιπτώσεις που αφορούν επιστημονικές βάσεις δεδομένων (Atlas, Biosql), τα ξένα κλειδιά αποτελούν αναπόσπαστο μέρος του σχήματος, εκτείνονται σε ένα τεράστιο ποσοστό των πινάκων και συνεξελίσσονται μαζί τους. Σε δύο άλλες περιπτώσεις, επίσης επιστημονικής φύσης (Egee και Castor), μόνο ένα υποσύνολο των πινάκων συμμετέχουν σε συσχετίσεις ξένων κλειδιών και η εξέλιξή τους είναι διττή: Η Egee (με πολύ μικρού μεγέθους Σχήμα) έχει μια ισχυρή συσχέτιση μεταξύ πινάκων και εξέλιξης ξένων κλειδιών, ενώ ο Castor (με ένα μικρό ποσοστό των πινάκων να εμπλέκονται σε ξένα κλειδιά) έχει ανάμικτη συμπεριφορά σε όλη την ιστορία της εξέλιξή του. Η μεγαλύτερη έκπληξη ήρθε από τα σχήματα Συστήματος Διαχείρισης Περιεχομένου (CMS), SlashCode και Zabbix, όπου τα ξένα κλειδιά εμπλέκονται μόνο σε μια μικρή μειοψηφία των πινάκων. Προς μεγάλη μας έκπληξη, τα ξένα κλειδιά σε αυτά τα έργα, μετά από μια περίοδο ανάπτυξης, αφαιρούνται από το σύστημα (α) με μια απότομη απομάκρυνση στην πρώτη περίπτωση, και (β) με μια αργή αλλά σταθερή ταχύτητα απομάκρυνσης στην δεύτερη. Η συνολική μας εντύπωση είναι ότι, με την εξαίρεση κάποιων περιβαλλόντων με αυστηρή τήρηση των υπαγορεύσεων της σχεσιακής θεωρίας, τα ξένα κλειδιά είναι σπάνια και ενίοτε ανεπιθύμητα. Όσον αφορά τη συμπεριφορά μεμονωμένων κόμβων, φαίνεται ότι ο βαθμός και η επιβίωση σχετίζονται θετικά μεταξύ τους, και, στην πραγματικότητα, υπάρχει ένα μοτίβο αντίστροφου - Γ στο συσχετισμό βαθμού και επιβίωσης. Το μοτίβο προτείνει ότι οι χαμηλοί σε βαθμούς κόμβοι φέρουν μη αμελητέα πιθανότητα απομάκρυνσης για τους αντίστοιχους πίνακες- ταυτόχρονα, οι υψηλόβαθμοι, αν και αρκετά σπάνια, φέρουν πιθανότητα διαγραφής 5% -19% χαμηλότερα από το μέσο όρο. Έχουμε μελετήσει επίσης κόμβους για τον συντελεστή ομαδοποίησή τους και την κεντρικότητά τους με μάλλον αμφίβολα αποτελέσματα όσον αφορά την επιβίωση του κόμβου. Τέλος, φαίνεται ότι οι κόμβοι που εφάπτονται με υψηλά score σε betweenness - centrality, συχνά (αλλά όχι πάντα) έχουν υψηλότερες πιθανότητες επιβίωσης από κόμβους με μία ή καμία προσκείμενη ακμή.
Περιγραφή
Λέξεις-κλειδιά
Databases, Database schema evolution, Foreign key evolution, Graph metrics, Βάσεις δεδομένων, Εξέλιξη σχήματος ΒΔ, Εξέλιξη ξένων κλειδιών, Γραφοθεωρητικές μετρικές
Θεματική κατηγορία
Databases
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Βασιλειάδης, Παναγιώτης
Εξεταστική επιτροπή
Βασιλειάδης, Παναγιώτης
Πιτουρά, Ευαγγελία
Ζάρρας, Απόστολος
Πιτουρά, Ευαγγελία
Ζάρρας, Απόστολος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογράφία : σ. 85-86
Ονόματα συντελεστών
Αριθμός σελίδων
87 σ.