Πληροφορική και Τηλεπικοινωνίες 515
Θέματα Συστημάτων Βάσεων Δεδομένων
Χειμερινό Εξάμηνο 2005

Καθηγητής Γιάννης Ιωαννίδης
Γραφείο: Α24 Κτήρια Πληροφορικής
Ώρες Γραφείου: Δευτέρα 16:30-18:00
Τηλέφωνο Γραφείου: (210) 727-5224
Ηλεκτρονική Διεύθυνση: yannis-παπάκι-di-τελεία-uoa-τελεία-gr
Ιστοσελίδα μαθήματος: http://www.di.uoa.gr/~pms515/

Περιεχόμενα

ΝΕΑ

Να ελέγχετε τον χώρο αυτό για τις τρέχουσες ανακοινώσεις. (Τελευταία ενημέρωση στις 24/6/2006.)

Πλήρης Βαθμολογία

Η πλήρης βαθμολογία, εργασιών και διαγωνισμάτων είναι έτοιμη.

Βαθμολογία

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

Μάθημα 16ης Ιανουαρίου 2006

Παρά την ανακοίνωση του έκτακτου προγράμματος μαθημάτων της τρέχουσας εβδομάδας, το μάθημα των Βάσεων θα γίνει κανονικά 6-9μμ, στην Αίθουσα ΣΤ'.

Προτεινόμενες εργασίες

Η λίστα των προτεινόμενων εργασιών του μαθήματος είναι διαθέσιμη.

ΑΝΑΣΚΟΠΗΣΕΙΣ ΔΙΑΛΕΞΕΩΝ

5/12/05

Δομές πολυδιάστατων δεδομένων. R-δένδρα: ιδιότητες, αλγόριθμοι αναζήτησης και εισαγωγής.

28/11/05

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

21/11/05

Εισαγωγή στους αλγορίθμους εκτέλεσης του τελεστή ζεύξης στα σχεσιακά συστήματα. Περιγραφή των διαφόρων μορφών του αλγορίθμου εμφωλιασμένων βρόχων (επιπέδου πλειάδας, επιπέδου μπλοκ, επιπέδου ομάδας μπλοκ, μέσω ευρετηρίου). Περιγραφή του αλγορίθμου συγχώνευσης-σάρωσης. Περιγραφή των διαφόρων μορφών της ζεύξης κατακερματισμού και επεξήγηση των αλγορίθμων της Απλής Ζεύξης Κατακερματισμού, της Ζεύξης Κατακερματισμού GRACE, και της Υβριδικής Ζεύξης Κατακερματισμού. Ανάλυση του κόστους εισόδου/εξόδου (I/O) όλων των αλγορίθμων.

14/11/05

Ολοκλήρωση της περιγραφής ανάκαμψης βάσεων δεδομένων. Αλγόριθμος Προενημερωμένου Ημερολογίου (Write Ahead Log). Ενέργειες κατά τη διαδικασία της ανάκαμψης μετά από βλάβη (επανάληψη και αναίρεση). Ιδιαιτερότητες του αλγορίθμου ARIES.

7/11/05

Συνέχεια της περιγραφής ανάκαμψης βάσεων δεδομένων. Αλγόριθμος Προενημερωμένου Ημερολογίου (Write Ahead Log). Σημεία ελέγχου. Ενέργειες κατά τη διαδικασία της ανάκαμψης μετά από βλάβη (ανάλυση). Ιδιαιτερότητες του αλγορίθμου ARIES.

31/10/05

Ολοκλήρωση ελέγχου συνδρομικότητας σε B+ δένδρα με τον αλγόριθμο του άρθρου Lehman and Yao για τους ενημερωτές (εισαγωγείς) δεδομένων. Εισαγωγή στην ανάκαμψη βάσεων δεδομένων. Τύποι βλαβών. Αλγόριθμος Προενημερωμένου Ημερολογίου (Write Ahead Log). Ενέργειες κατά την κανονική λειτουργία του συστήματος.

24/10/05

Αισιόδοξος έλεγχος συνδρομικότητας (optimistic concurrency control). Φάσεις δοσοληψιών και αιτούμενες συνθήκες στην φάση επικύρωσης (validation). Αλγόριθμος σειριακής επικύρωσης. Κόστος αισιόδοξου ελέγχου συνδρομικότητας και μερική σύγκριση με το διφασικό κλείδωμα. Έλεγχος συνδρομικότητας σε ευρετήρια με δομή δένδρου (συγκεκριμένα, B+ δένδρα). Κίνητρα δημιουργίας διαφορετικών αλγορίθμων. Ανάλυση αλγορίθμου του άρθρου Lehman and Yao για τους αναγνώστες.

17/10/05

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

10/10/05

Εισαγωγή στους ορισμούς των δοσοληψιών (transactions) και των προβλημάτων σύνδρομης προσπέλασης (concurent access). Διερεύνηση της έννοιας της δοσοληψίας. Ορισμοί χρονοπρογραμμάτων (schedules), σειριακών (serial) και σειριοποιήσιμων (serializable) χρονοπρογραμμάτων, ισοδυναμίας χρονοπρογραμμάτων, γράφου σειριοποίησης, και συνθηκών σειριοποιησιμότητας. Αλγόριθμος διφασικού κλειδώματος (two-phase locking) και οι ιδιότητές του. Υλοποίηση του διφασικού κλειδώματος (πίνακας κλειδωμάτων).

3/10/05

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

ΠΕΡΙΓΡΑΦΗ ΜΑΘΗΜΑΤΟΣ

Το μάθημα 515 του Προγράμματος Μεταπτυχιακών Σπουδών του Τμήματος Πληροφορικής και Τηλεπικοινωνιών ``Θέματα Συστημάτων Βάσεων Δεδομένων'' θα καλύψει έναν αριθμό από προηγμένα θέματα στην περιοχή των συστημάτων βάσεων δεδομένων. Τα συγκεκριμένα θέματα που θα συζητηθούν περιλαμβάνουν τεχνικές ελέγχου ταυτόχρονης/σύνδρομης προσπέλασης (concurrency control) και ανάκαμψης (recovery), στρατηγικές επεξεργασίας επερωτήσεων (query processing) για σχεσιακά συστήματα βάσεων δεδομένων, προηγμένες δομές δεδομένων και οργανώσεις αρχείων, την αλληλεπίδραση του λειτουργικού συστήματος και ενός συστήματος βάσεων δεδομένων (database operating systems), παράλληλα συστήματα βάσεων δεδομένων, κατανεμημένα συστήματα βάσεων δεδομένων, αντικειμενοστρεφή συστήματα βάσεων δεδομένων, και την απόδοση συστημάτων βάσεων δεδομένων. Το υλικό του μαθήματος θα αντληθεί από μερικά κλασσικά άρθρα της περιοχής καθώς και από την πρόσφατη βιβλιογραφία των βάσεων δεδομένων.

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

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

ΔΙΑΛΕΞΕΙΣ

Διάλεξη: Δευτέρα 6:00-9:00, Αίθουσα ΣΤ, Κτήρια Πληροφορικής

ΒΙΒΛΙΟ

 Η πλειοψηφία των αναγνωσμάτων περιλαμβάνονται στο βιβλίο Readings in Database Systems (3η έκδοση), συνταχθέν από τούς Mike Stonebraker και Joe Hellerstein. Τα άρθρα που έχουν επιλεγεί από το βιβλίο συμπληρώνονται από ένα μικρό σύνολο άλλων άρθρων από την πρόσφατη βιβλιογραφία των βάσεων δεδομένων.

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

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

ΒΑΘΜΟΛΟΓΙΑ

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

ΔΙΑΓΩΝΙΣΜΑ

Τελικό διαγώνισμα:   θα ανακοινωθεί αργότερα

ΕΡΓΑΣΙΑ

 Τμήμα του μαθήματος είναι η εκτέλεση κάποιας εργασίας. Υπάρχει ήδη μία λίστα με προτεινόμενα θέματα , από τα οποία και θα πρέπει να διαλέξετε. Στην περίπτωση που θέλετε να κάνετε κάτι διαφορετικό από τα προτεινόμενα, θα πρέπει πρώτα να έρθετε σε συνεννόηση μαζύ μου, ώστε να κρίνω αν το ζητούμενο είναι κατάλληλο θέμα εργασίας για το μάθημα. Σε κάθε περίπτωση, σύντομα (μέχρι τις 24/10/05), θα ήθελα να μου δώσετε μία μικρή περιγραφή της εργασίας που έχετε επιλέξει, ώστε να είμαστε όλοι συγχρονισμένοι. Επίσης στο τέλος του εξαμήνου, θα γράψετε μία αναφορά όπου θα περιγράφετε τα αποτελέσματα της όλης προσπάθειας.

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