Μάθημα : Συστήματα Βάσεων Δεδομένων

Περιεχόμενο μαθήματος (Syllabus)

Έλεγχος συνδρομικότητας (σειριοποιησιμότητα, διφασικό κλείδωμα, αισιόδοξος έλεγχος συνδρομικότητας, ειδικοί αλγόριθμοι για Β+ δένδρα), Ανάκαμψη (αλγόριθμος προενημερωμένου ημερολογίου και ειδικότερα ο αλγόριθμος ARIES), Βελτιστοποίηση και Επεξεργασία Επερωτήσεων (αλγόριθμοι ζεύξης με κατακερματισμό και συγχώνευση σάρωση παρουσία μεγάλης μνήμης, αλγόριθμος βελτιστοποίηση βασισμένος στον δυναμικό προγραμματισμό, πιθανοτικοί αλγόριθμοι βελτιστοποίησης, χρήση ιστογραμμάτων για στατιστική προσέγγιση δεδομένων), Πολυδιάστατες Δομές Δεδομένων (R- δένδρα), Διαχείριση Ενδιάμεσης Μνήμης (αλγόριθμοι αντικατάστασης σελίδων ανάλογα με την μορφή προσπέλασης των δεδομένων), Παράλληλες και Κατανεμημένες Βάσεις Δεδομένων (μορφές παραλληλίας, επεξεργασία ερωτημάτων και γενικευμένων ροών δεδομένων σε περιβάλλον νέφους), παρελθόν και μέλλον των συστημάτων βάσεων δεδομένων.

Διαλέξεις

Διαλέξεις Χειμερινού Εξαμήνου 2022-2023

Τρίτη 15:00 - 18:00, Αίθουσα Ζ

Τετάρτη 15:00 - 18:00, Αίθουσα Ζ

Παρασκευή 15:00 - 18:00, Αίθουσα Ζ

Θα υπάρχει έγκαιρη ενημέρωση για το ποιες διαλέξεις (οποιδήποτε υποσύνολο, πιθανόν και οι τρεις) θα πραγματοποιούνται κάθε εβδομάδα.

Για την επαύξηση της προφύλαξης όλων από την πανδημία, οι διαλέξεις μπορεί να πραγματοποιούνται και χωρίς ουσιαστικό διάλειμμα.

Η συμμετοχή στις συζητήσεις την ώρα του μαθήματος θεωρείται απαραίτητη, ώστε να μεγιστοποιηθεί η αποδοτικότητα όλων κατά την διάρκειά του. Ελπίζω ότι οι διαλέξεις θα πάρουν την μορφή διαλόγου, καθότι αυτό είναι που θα τις κάνει ενδιαφέρουσες για όλους.

Ανθρώπινο Δυναμικό

Διδάσκων

Γιάννης Ιωαννίδης (yannis papaki di teleia uoa teleia gr, B12) - ώρες γραφείου: με προσυνεννόηση

Βαθμολογία

Ο τελικός βαθμός του μαθήματος θα υπολογισθεί ως εξής: τελικό διαγώνισμα (50%), εργασία (50%). Για να περάσει κανείς θα πρέπει να έχει βαθμό τουλάχιστον 5 στην εργασία και τουλάχιστον 5 στο διαγώνισμα.

Στην απευκταία περίπτωση που υπάρξει αδυναμία εύρεσης βοηθών για την απαραίτητη στενότερη παρακαλούθηση των εργασιών, ο τελικός βαθμός μπορεί να βασιστεί αποκλειστικά στο τελικό διαγώνισμα.

Συνιστώμενη Βιβλιογραφία

Εκτός από τις περιπτώσεις όπου αναφέρεται κάτι διαφορετικό, τα άρθρα είναι από την 3η έκδοση του βιβλίου Readings in Database Systems των Mike Stonebraker και Joe Hellerstein (και με κάποιες εξαιρέσεις και στην 4η έκδοση). Όλα βρίσκονται στη σελίδα του μαθήματος, στο σύνδεσμο "Αναγνώσματα" του εργαλείου "Έγγραφα". Οι διαφάνειες του τελευταίου άρθρου βρίσκονται κάτω από τον αντίστοιχο σύνδεσμο "Παρουσιάσεις".

Επεξεργασία Δοσοληψιών (Transaction Management)

• Gray, J., et al., "Granularity of Locks and Degrees of Consistency in a Shared Database", Stonebraker-Hellerstein, σελίδες 175-193.
• Kung, H., και J. Robinson, "On Optimistic Methods for Concurrency Control", Stonebraker-Hellerstein, σελίδες 194-200.
• Lehman, P, και S. B. Yao, "Efficient Locking for Concurrent Operations on B-Trees", Stonebraker-Hellerstein, σελίδες 224-234.
• Franklin, M., et al., "Crash Recovery in Client-Server EXODUS", Proc. 1992 International ACM SIGMOD Conference, San Diego, CA, June 1992, σελίδες 165-175 (μόνο την ενότητα 3).
• Mohan, et al., "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking", Stonebraker-Hellerstein, σελίδες 251-285.

Επεξεργασία και Βελτιστοποίηση Επερωτήσεων (Query Processing and Optimization)

• Shapiro, L., "Join Processing in Database Systems with Large Main Memories", Stonebraker-Hellerstein, σελίδες 128-140.
• Ioannidis, Y., "Query Optimization", The Computer Science and Engineering Handbook, 1997, σελίδες 1038-1057.
• Selinger, P., και άλλοι "Access Path Selection in a Relational Database Management System", Stonebraker-Hellerstein, σελίδες 141-152.
• Ioannidis, Y., και Kang, Y., "Randomized Algorithms for Optimizing Large Join Queries", Proc. ACM SIGMOD Conf., Atlantic City, NJ, May 1990, σελίδες 312-321.
• Poosala, V., Y. Ioannidis, P. Haas, και E. Shekita, "Improved Histograms for Selectivity Estimation of Range Predicates", Proc. 1996 International ACM SIGMOD Conference, Montreal, Canada, May 1996, σελίδες 294-305.

Προηγμένες Δομές Δεδομένων (Advanced Access Methods)

• Guttman, A., "R-Trees: A Dynamic Index Structure for Spatial Searching", Stonebraker-Hellerstein, σελίδες 90-100.

Διαχείριση Ενδιάμεσης Μνήμης (Buffer Management)

• Chou, H., και D. DeWitt, "An Evaluation of Buffer Management Strategies for Relational Database Systems", Stonebraker-Hellerstein, σελίδες 113-127.

Κατανεμημένα και Παράλληλα Συστήματα Βάσεων Δεδομένων (Distributed & Parallel Database Systems)

• DeWitt, D. and J. Gray, "Parallel Database Systems: The Future of High Performance Database Systems", Stonebraker-Hellerstein, σελίδες 403-416.
• Kllapi, H., E. Sitaridi, M. Tsangaris, and. Y. Ioannidis,"Schedule Optimization for Data Processing Flows on the Cloud", Proc. 2011 International ACM SIGMOD Conference, Athens, Greece, June 2011, σελίδες 289-300.

Νέες Αρχιτεκτονικές Συστημάτων Βάσεων Δεδομένων (New Database Architectures)

• M. Stonebraker et al., "C-Store: A Column-oriented DBMS", Proc. 31st VLDB Conference, Trondheim, Norway, August 2005.
• A. Pavlo et al., "A Comparison of Approaches to Large-Scale Data Analysis", Proc. 2009 International ACM SIGMOD Conference, Providence, Rhode Island, June 2009.

Προτάσεις Εργασιών

Παρακάτω ακολουθεί μια περιγραφή των διαφόρων εργασιών που θα μπορούσαν να γίνουν στα πλαίσια του μαθήματος 515, "Θέματα Συστημάτων Βάσεων Δεδομένων". Λόγω του μεγάλου πλήθους των φοιτητών αλλά και του πλούτου του όλου χώρου, προηγείται μία γενική προσεγγιστική οργάνωση του χώρου των Συστημάτων Βάσεων Δεδομένων, πάνω στην οποία βασίζεται και η περιγραφή των εργασιών.

ΘΕΜΑΤΟΛΟΓΙΑ

Η θεματολογία των Συστημάτων Βάσεων Δεδομένων μπορεί να οργανωθεί σε τέσσερεις διαστάσεις. Σε κάθε διάσταση, παρατίθεται ένα βασικό σύνολο θεμάτων που αφορούν τη διάσταση. Για μερικά δε από αυτά, παρατίθενται και πιό συγκεκριμένα υποθέματα, που αντιπροσωπεύουν είτε σημαντικά, στενότερα υποπροβλήματα είτε σημαντικές κατευθύνσεις που έχει ακολουθήσει ο χώρος στα θέματα αυτά. Η παρακάτω ταξινόμηση, καθώς και τα στοιχεία κάθε διάστασης, είναι ασφαλώς ενδεικτική και σε καμμία περίπτωση ολοκληρωτική.

Με βάση αυτήν την ταξινόμηση, οι φοιτητές καλούνται να επιλέξουν ένα συνδυασμό από θέματα της κάθε διάστασης (τυπικά 0 ή 1 από κάθε διάσταση, σπανιώτερα 2 ή περισσότερα) και να κάνουν μία εργασία πάνω στα προβλήματα του υποχώρου που προκύπτει με αυτόν τον τρόπο. Για παράδειγμα, βελτιστοποίηση επερωτήσεων σε παράλληλες βάσεις δεδομένων ή απόδοση πολυδιάστατων ευρετηρίων για χωροχρονικά δεδομένα. Υποχώροι που προκύπτουν από θέματα Συστημάτων Βάσεων Δεδομένων που δεν αναφέρονται ήδη σε κάποιες από τις διαστάσεις της παραπάνω ταξινόμησης ασφαλώς και επιτρέπονται.

Για κάθε θεματικό υποχώρο που μπορεί να προκύψει, υπάρχουν δύο βασικοί τύποι εργασιών: ανασκοπήσεις και υλοποιήσεις. Οι δύο τύποι αναλύονται λεπτομερειακά παρακάτω. Ανασκοπήσεις θα δοθούν μόνο κατ' εξαίρεση σε ειδικές περιπτώσεις.

ΥΛΟΠΟΙΗΣΕΙΣ

Το ζητούμενο σε μία τέτοια εργασία είναι ο σχεδιασμός, η υλοποίηση, και πιθανώς η αξιολόγηση ενός ή περισσοτέρων (υπο)συστημάτων ή αλγορίθμων που παρέχουν μία συγκεκριμένη υπηρεσία που αφορά το θέμα της εργασίας. Η υλοποίηση αναμένεται να είναι σε πιλοτικό επίπεδο, δηλαδή να δουλεύει αξιοπρεπώς αλλά χωρίς πλήρη προστασία από λάθη χρηστών ή απόλυτη κάλυψη όλων των δυνατών περιπτώσεων. Εκτός απροόπτου, όλες οι εργασίες θα υλοποιηθούν πάνω στο σύστημα Exareme που έχει υλοποιηθεί από ένα μέρος της ομάδας MaDgIK. Πέραν της επίδειξης του υλοποιηθέντος λογισμικού, οι εργασίες αυτές θα πρέπει να παράγουν και μία μικρή αναφορά όπου να περιγράφονται περιληπτικά τα σημαντικότερα στοιχεία της υλοποίησης.

ΑΝΑΣΚΟΠΗΣΕΙΣ

Το ζητούμενο σε μία τέτοια εργασία είναι η μελέτη ενός ικανοποιητικού αριθμού από κείμενα που πραγματεύονται το θέμα της εργασίας, η αναγνώριση των βασικών διαστάσεων και προβλημάτων του θέματος αυτού, και η γενικευμένη περιγραφή των λύσεων που προτείνονται. Το βασικό αποτέλεσμα μιας τέτοιας εργασίας θα είναι μία καλογραμμένη αναφορά. Κάθε τέτοια προσπάθεια μπορεί να εστιαστεί σε ένα ή κάποιο συνδυασμό από τα εξής:

• Ερευνητικά αποτελέσματα: στην περίπτωση αυτή κύρια πηγή πληροφοριών θα είναι ερευνητικά άρθρα από τη βιβλιογραφία. Ένα καλό αρχικό σημείο αναζήτησης τέτοιων άρθρων είναι στο http://www.informatik.uni-trier.de/~ley/db/. Ένα άλλο καλό σημείο είναι η ψηφιακή βιβλιοθήκη του Πανεπιστημίου που βρίσκεται μέσω του http://www.lib.uoa.gr/ και για κάποια πράγματα και η φυσική βιβλιοθήκη του Τμήματος. Σε κάθε περίπτωση, τα πιό σημαντικά περιοδικά και συνέδρια που πρέπει να κοιτάζει κανείς πρώτα για την περιοχή αυτή είναι τα εξής:
      Περιοδικά: ACM TODS, IEEE TKDE, VLDB Journal, Information Systems
      Συνέδρια: ACM SIGMOD, VLDB, IEEE ICDE, EDBT
• Βιομηχανικά Συστήματα Βάσεων Δεδομένων: στην περίπτωση αυτή κύρια πηγή πληροφοριών θα είναι τα εγχειρίδια των κυριοτέρων Συστημάτων Βάσεων Δεδομένων, δηλαδή των Oracle, DB2, SQL Server, Sybase, κτλ. Χρήσιμες πληροφορίες μπορούν επίσης να βρεθούν και σε άρθρα στα παραπάνω περιοδικά ή συνέδρια, όπου πολλές φορές εμφανίζονται δουλειές που αφορούν λεπτομέρειες συγκεκριμένων συστημάτων, καθώς και σε ελεύθερα κείμενα (white papers) που τοποθετούν οι εταιρείες στο διαδίκτυο.
• Διάφορα άλλα συστήματα: στην περίπτωση αυτή οι πηγές πληροφοριών είναι της ίδιας υφής με αυτών της περίπτωσης των βιομηχανικών συστημάτων, μόνο που αφορούν άλλα συστήματα που απλώς ενσωματώνουν τεχνολογία βάσεων δεδομένων, όπως για παράδειγμα το σύστημα SAP.

ΔΙΑΧΕΙΡΙΣΤΙΚΑ

Κάθε εργασία μπορεί να γίνει ομαδικά (το οποίο και συνιστάται) ή ατομικά. Κάθε ομάδα μπορεί να έχει διαφορετικό αριθμό από μέλη, και υπάρχει ελεύθερη επιλογή στην ομάδα που θα ενταχθεί ο καθένας. Κάθε μέλος της ομάδας θα πάρει ξεχωριστό βαθμό ανάλογα με την συνεισφορά του στο όλο έργο. 

Η προθεσμία ολοκλήρωσης των εργασιών είναι η 20/1/2023.