Εβδομαδιαίες αναθέσεις εργασίας
1. Σχεσιακό Μοντέλο
Κριτική Ανάγνωση
Διαβάστε το άρθρο καλά. Μετά, διαβάστε και το σχετικό κεφάλαιο από ένα από τα κλασικά textbooks βάσεων δεδομένων.
- Τι διαφορές βλέπετε στη σχεσιακή άλγεβρα μεταξύ των δύο αναγνωσμάτων?
Επιπλέον Αναγνώσματα
Άρθρο προς βιβλιογραφική σύνοψη
Διαλέξτε ένα από τα δύο: είτε το άθρο του Codd για το σχεσιακό μοντέλο, είτε το άρθρο του Chamberlin για τη SEQUEL
2. Ανατομία ενός ΣΔΒΔ
Εμβάθυνση
Στην ενότητα "The Roots" υπάρχουν διάφορα άρθρα σχετικά με την αρχιτεκτονική συστημάτων διαχείρισης βάσεων δεδομένων. Διαβάστε τα δύο άρθρα σχετικά με το System R. Μετά, διαβάστε και το σχετικό κεφάλαιο από ένα από τα κλασικά textbooks βάσεων δεδομένων.
Επιπλέον Αναγνώσματα
- Μπορείτε να δείτε το υλικό για αντίπαλον δέος του System R, την Ingres, την εποχή που τα πρώτα RDBMS ανέτειλαν.
Άρθρο προς βιβλιογραφική σύνοψη
Για παράδοση την μεθεπόμενη φορά, κάτι τελείως διαφορετικό σε σχέση με την αρχιτεκτονική ΣΔΒΔ. Ο σκοπός είναι να προπονηθείτε στα θέματα κριτικής ανάγνωσης της βιβλιογραφίας. Δέστε την δουλειά από το πανεπιστήμιο του Cornell σχετικά με l-diversity στο συνέδριο ICDE 2006 και γράψτε μια κριτική περίληψή της. Το εν λόγω directory σας δίνει κάποιες ενδιαφέρουσες/σημαντικές δημοσιεύσεις για το χώρο του privacy, ώστε να πάρετε ιδέες και για την αναφορά, και για το θέμα της εργασίας.
3. Επεξεργασία Ερωτήσεων
Εμβάθυνση
Διαβάστε από το κλασικό survey του Graefe τα κεφάλαια 1, 2 και 5.
Επειδή το survey μπορεί να σας δυσκολέψει, δέστε τα αντίστοιχα κεφάλαια, σε απλοποιημένη μορφή, σε οποιοδήποτε από τα κλασικά textbooks βάσεων δεδομένων.
Επιπλέον Αναγνώσματα
- Διαβάστε το άρθρο για t-closeness στο συνέδριο ICDE 2007 (άλλη μια εκδοχή της ιδιωτικότητας σε ΒΔ), το οποίο περιέχει μια ενδιαφέρουσα σύνοψη και κριτική ανάγνωση για το προηγούμενο άρθρο (l-diversity) με διαφορά ενός χρόνου στην εμφάνισή τους.
- Στη σελίδα του μαθήματος έχω ανεβάσει τις διαφάνειες του προπτυχιακού μου μαθήματος, σχετικά με (α) επεξεργασία ερωτήσεων και (β) βελτιστοποίηση ερωτήσεων. Μπορεί να σας φανούν χρήσιμες.
- Διαβάστε για hash joins σε κάποιο από τα κλασικά textbooks βάσεων δεδομένων. Για όσους ενδιαφέρονται παραπάνω, μπορείτε να δείτε πώς οι hash joins ενσωματώθηκαν σε εμπορικό επίπεδο στον SQL Server (Graefe et al, VLDB 1998), καθώς και επιπλέον χρήσεις του hash join είτε σε συνδυασμό με group-by είτε για on-line, streaming data (βλ. και directory hashing στο κάτω μέρος της σελίδας "επιπλέον υλικό").
Άρθρο προς βιβλιογραφική σύνοψη
Για παράδοση στις 24/11, μια κριτική ανάγνωση του άρθρου του Shapiro, "Join Processing in Database Systems with Large Main Memories". TODS 11(3): 239-264 (1986) που αφορά στη χρήση hash-joins. To άρθρο βρίσκεται στη σελίδα "Readings in databases".
Προσοχή: προς επισκόπηση είναι το άρθρο του Shapiro και όχι τα μεταγενέστερα που αναφέρθηκαν παραπάνω!
4. Βελτιστοποίηση Ερωτήσεων
Εμβάθυνση
Επιμένω να διαβάσετε από το κλασικό survey του Graefe τα κεφάλαια 1, 2 και 5. Επιπλέον, για τις επόμενες αγωνιστικές, θα χρειαστούν ΚΑΙ τα κεφάλαια 7 και 4.
Επειδή το survey μπορεί να σας δυσκολέψει, δέστε τα αντίστοιχα κεφάλαια, σε απλοποιημένη μορφή, σε οποιοδήποτε από τα κλασικά textbooks βάσεων δεδομένων.
Επιπλέον Αναγνώσματα
- Διαβάστε το άρθρο J. M. Hellerstein, M. Stonebraker and J. Hamilton. Architecture of a Database System. Foundations and Trends in Databases 1(2). για να βοηθείτε στην κατανόηση των ΣΔΒΔΒ
Άρθρο προς βιβλιογραφική σύνοψη
Αντί άρθρου, για παράδοση στις 01/12, απαντήστε τα εξής (τα οποία θα συζητήσουμε και στο μάθημα):
- Εξηγείστε τον ρόλο των iterators στο εσωτερικό ενός DBMS. Εξηγείστε πώς λειτουργούν στην επεξεργασία ερωτήσεων.
- Εξηγείστε τον μηχανισμό του δυναμικού προγραμματισμού. Πότε μπορούμε να χρησιμοποιούμε δυναμικό προγραμματισμό σε προβλήματα? Δώστε ένα παράδειγμα (εκτός από τη βελτιστοποίηση ερωτήσεων, προφανώς).
- Εξηγείστε τι είναι memoization. Δώστε ένα παράδειγμα δυναμικού προγραμματισμού με memoization. Σχετίστε το άρθρο Selinger et al. με την τεχνική του memoization.
5. Συναλλαγές και ταυτοχρονισμός
Εμβάθυνση
Διαβάστε το άρθρο του Jim Gray et al "GRANULARITY OF LOCKS IN A LARGE SHARED DATA BASE", VLDB 1975, το οποίο και θα συζητήσουμε στην επόμενη διάλεξη.
Επιπλέον Αναγνώσματα
- Διαβάστε για συναλλαγές και ταυτοχρονισμό σε οποιοδήποτε από τα κλασικά textbooks βάσεων δεδομένων.
Άρθρο προς βιβλιογραφική σύνοψη
Για τις 15/12: Το άρθρο Mohan et al "Transaction Management in the R* Distributed Database Management System". Διατηρείστε με ευλάβεια το προτεινόμενο LNCS format για την σύνοψή σας (αλλιώς η εργασία δε θα γίνει δεκτή). Επιπλέον της κριτικής θεώρησης, αναλύστε μέσα στη σύνοψή σας σε 3-4 σελίδες:
- Περιγράψτε το βασικό αλγόριθμο 2PC (normal operation) σαν σειρά βημάτων από τα εμπλεκόμενα sites
- Εξηγείστε τη βασική φιλοσοφία για το πρωτόκολλο Presume abort
Απαγορεύεται να χρησιμοποιήσετε τα σχήματα του άρθρου -- κατασκευάστε δικά σας που να πείθουν ότι καταλάβατε.
6. Όψεις
Εμβάθυνση
Στην επόμενη διάλεξη θα συζητήσουμε το άρθρο των Jonathan Goldstein, Per-Ake Larson στο SIGMOD 2001.
Επιπλέον Αναγνώσματα
- Διαβάστε το survey του Halevy, VLDBJ 2001, τμήματα από το οποίο θα συζητήσουμε στην επόμενη διάλεξη.
Άρθρο προς βιβλιογραφική σύνοψη
Τίποτε. Αναμένω να ολοκληρώσετε τις εκκρεμότητές σας, όσοι από σας έχετε.
Τελευταία ενημέρωση: 2009/09/26