Συστήματα Βάσεων Δεδομένων
Αλέξης Δελής
Το μάθημα στοχεύει τόσο στην εισαγωγή των φοιτητών στις εσωτερικές λεπτομέρειες των βάσεων δεδομένων, όσο και στο να τους δώσει κίνητρο για τη χρήση και μελέτη διαφόρων σύγχρονων προσεγγίσεων στη διαχείριση δεδομένων. Τέτοιου είδους προσεγγίσεις καθιστούν δυνατή την ανάπτυξη μηχανισμών για τη μοντελοποίηση ετερογενών δεδομένων που χρησιμοποιούνται σε σύγχρονες εφαρμογές, ενώ παίζουν σημαντικό ρόλο στην περαιτέρω ανάπτυξη των μοντέρνων συστημάτων λογισμικού.
Το μάθημα καλύπτει μια σειρά θεματικών περιοχών, όπως: σχεσιακή μοντελοποίηση και η γλώσσα SQL, αποθήκευση και δομές αρχείων, προσεγγίσεις ευρετηριοποίησης συμπεριλαμβανομένου του κατακερματισμού, γραμμικός κατακερματισμός, πολυδιάστατα ευρετήρια και χάρτες bit (bitmaps), οι μέθοδοι επεξεργασίας επερωτήσεων, προσεγγίσεις βελτιστοποίησης επερωτήσεων βασισμένες σε συντακτικούς μετασχηματισμούς, μέθοδοι βασισμένες σε κόστος, ευριστικές και πολλαπλές επερωτήσεις για τη συγκρότηση πλάνων αξιολόγησης, επεξεργασία δοσοληψιών και κριτήρια ορθότητας, μηχανισμοί για την επίτευξη παράλληλης επεξεργασίας δοσοληψιών με υψηλό βαθμό εξυπηρέτησης, καθώς και τεχνικές ανάκαμψης σε περίπτωση εμφάνισης αποτυχιών. Προχωρημένα θέματα συζητούνται επίσης, όπως: πολυεπίπεδες αρχιτεκτονικές διαχείρισης δεδομένων, παράλληλες και κατανεμημένες βάσεις δεδομένων, νέοι τύποι δεδομένων, και ρεύματα δεδομένων.
ΛιγότεραΤο μάθημα στοχεύει τόσο στην εισαγωγή των φοιτητών στις εσωτερικές λεπτομέρειες των βάσεων δεδομένων, όσο και στο να τους δώσει κίνητρο για τη χρήση και μελέτη διαφόρων σύγχρονων προσεγγίσεων στη διαχείριση δεδομένων. Τέτοιου είδους προσεγγίσεις καθιστούν δυνατή την ανάπτυξη μηχανισμών για τη μοντελοποίηση ετερογενών δεδομένων που χρησιμοποιούνται σε σύγχρονες εφαρμογές, ενώ παίζουν σημαντικό ρόλο στην περαιτέρω ανάπτυξη των μοντέρνων συστημάτων λογισμικού.
Το μάθημα καλύπτει μια σειρά θεματικών περιοχών, όπως: σχεσιακή μοντελοποίηση και η γλώσσα SQL, αποθήκευση και δομές αρχείων, προσεγγίσεις ευρετηριοποίησης συμπεριλαμβανομένου του κατακερματισμού, γραμμικός κατακερματισμός, πολυδιάστατα ευρετήρια και χάρτες bit (bitmaps), οι μέθοδοι επεξεργασίας επερωτήσεων, προσεγγίσεις βελτιστοποίησης επερωτήσεων βασισμένες σε συντακτικούς μετασχηματισμούς, μέθοδοι βασισμένες σε κόστος, ευριστικές και πολλαπλές επερωτήσεις για τη συγκρότηση πλάνων αξιολόγησης, επεξεργασία δοσοληψιών και κριτήρια ο
Το μάθημα στοχεύει τόσο στην εισαγωγή των φοιτητών στις εσωτερικές λεπτομέρειες των βάσεων δεδομένων, όσο και στο να τους δώσει κίνητρο για τη χρήση και μελέτη διαφόρων σύγχρονων προσεγγίσεων στη διαχείριση δεδομένων. Τέτοιου είδους προσεγγίσεις καθιστούν δυνατή την ανάπτυξη μηχανισμών για τη μοντελοποίηση ετερογενών δεδομένων που χρησιμοποιούνται σε σύγχρονες εφαρμογές, ενώ παίζουν σημαντικό ρόλο στην περαιτέρω ανάπτυξη των μοντέρνων συστημάτων λογισμικού.
Το μάθημα καλύπτει μια σειρά θεματικών περιοχών, όπως: σχεσιακή μοντελοποίηση και η γλώσσα SQL, αποθήκευση και δομές αρχείων, προσεγγίσεις ευρετηριοποίησης συμπεριλαμβανομένου του κατακερματισμού, γραμμικός κατακερματισμός, πολυδιάστατα ευρετήρια και χάρτες bit (bitmaps), οι μέθοδοι επεξεργασίας επερωτήσεων, προσεγγίσεις βελτιστοποίησης επερωτήσεων βασισμένες σε συντακτικούς μετασχηματισμούς, μέθοδοι βασισμένες σε κόστος, ευριστικές και πολλαπλές επερωτήσεις για τη συγκρότηση πλάνων αξιολόγησης, επεξεργασία δοσοληψιών και κριτήρια ο
Περίγραμμα
Περιεχόμενο μαθήματος
Έλεγχος συνδρομικότητας (σειριοποιησιμότητα, διφασικό κλείδωμα, αισιόδοξος έλεγχος συνδρομικότητας, ειδικοί αλγόριθμοι για Β+ δένδρα), Ανάκαμψη (αλγόριθμος προενημερωμένου ημερολογίου και ειδικότερα ο αλγόριθμος ARIES), Βελτιστοποίηση και Επεξεργασία Επερωτήσεων (αλγόριθμοι ζεύξης με κατακερματισμό και συγχώνευση σάρωση παρουσία μεγάλης μνήμης, αλγόριθμος βελτιστοποίησης βασισμένος στον δυναμικό προγραμματισμό, πιθανοτικοί αλγόριθμοι βελτιστοποίησης, χρήση ιστογραμμάτων για στατιστική προσέγγιση δεδομένων), Πολυδιάστατες Δομές Δεδομένων (R- δένδρα), Διαχείριση Ενδιάμεσης Μνήμης (αλγόριθμοι αντικατάστασης σελίδων ανάλογα με την μορφή προσπέλασης των δεδομένων), Παράλληλες και Κατανεμημένες Βάσεις Δεδομένων (έλεγχος συνδρομικότητας δια ψήφου, διφασική επικύρωση, αλγόριθμοι ζεύξης σε κατανεμημένο περιβάλλον, η μηχανή βάσεων δεδομένων GAMMA, μελλοντικές εξελίξεις στις παράλληλες βάσεις δεδομένων), Αντικειμενοστρεφείς Βάσεις Δεδομένων (στοιχεία αντικειμενοσχεσιακών βάσεων δεδομένων, το αντικειμενοστρεφές σύστημα ObjectStore), παρελθόν και μέλλον των συστημάτων βάσεων δεδομένων.
Μαθησιακοί στόχοι
Το μάθημα στοχεύει τόσο στην εισαγωγή των φοιτητών στις εσωτερικές λεπτομέρειες των βάσεων δεδομένων, όσο και στο να τους δώσει κίνητρο για τη χρήση και μελέτη διαφόρων σύγχρονων προσεγγίσεων στη διαχείριση δεδομένων. Τέτοιου είδους προσεγγίσεις καθιστούν δυνατή την ανάπτυξη μηχανισμών για τη μοντελοποίηση ετερογενών δεδομένων που χρησιμοποιούνται σε σύγχρονες εφαρμογές, ενώ παίζουν σημαντικό ρόλο στην περαιτέρω ανάπτυξη των μοντέρνων συστημάτων λογισμικού.
Προαπαιτούμενα
- Βασικές γνώσεις Βάσεων Δεδομένων, Αλγορίθμων και Λειτουργικών Συστημάτων
- Προγραμματισμός σε περιβάλλον Unix
- Γνώση C/C++ ή Java
- Προπτυχιακό Μάθημα: Κ29 Σχεδίαση και Χρήση Βάσεων Δεδομένων
Βιβλιογραφία
Βιβλία
- D. Ullman, Principles of Database and Knowledge Database Systems: Volumes I & II, Computer Science Press, Principles of Computer Science Series, Rockville, MD, 1988
Άρθρα
- Meijer and G. Bierman, A co-Relational Model of Data for Large Shared Data Banks, ACM Queue Magazine, vol. 9, no. 3, March 2011.
- Poosala, Zipf's Law, Technical Report, 900 839 0750, CS, Univ. of Wisconsin, Madison, WI, 1995 based on "G.K. Zipf, Human Hehavior and the Principle of Least Effort, Addison-Wesley, Reading, MA, 1949".
- A. Patterson, G. Gibson and R. H. Katz, A Case for Redundant Arrays of Inexpensive Disks (RAID), Proc. of ACM SIGMOD Int. Conf. on Management of Data pp. 109-116, Chigago, IL, June 1987
- N. Gray, R.A. Lorie, G.R. Putzolu and I.L. Traiger, "Granularity of Locks and Degrees of Consistency in a Shared Database" IFIP Working Conference on Modelling of Database Management Systems, Freudenstadt, Germany, December 1975.
- T. Kung and J. Robinson, "On Optimistic Methods for Concurrency Control", ACM Transactions on Database Systems, vol. 6, no. 2, pp. 213-226, 1981.
- Comer, Ubiquitous B-Tree ACM Computing Surveys, vol. 11 , no. 2, June 1979.
- Jannink, Deletion in B+-trees. ACM SIGMOD RECORD, vol.24, no.1, pp. 33-38, 1995.
- Stonebraker, Operating system support for database management , Communications of the ACM, vol. 24 no. 7, July 1981.
- J. Carey and W.A. Muhanna, The performance of multiversion concurrency control algorithms. ACM Trans. Comput. Syst. vol. 4, no. 4 Sep. 1986.
- P. Reed, Implementing atomic actions on decentralized data. , ACM Trans. Comput. Syst. vol. 1, no. 1, Feb. 1983
- Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, vol. 19. no. 9, pp. 509-517, Sept. 1975.
- Fagin, J. Nievergelt, N. Pippenger, H.R. Strong, Extendible hashing--a fast access method for dynamic files, ACM Transaction on Database Systems, vol. 4, no. 3, pp 315-344, September 1979.
- Witold, Linear hashing: A new tool for file and table addressing, Proc. 6th Conference on Very Large Databases, 1980. (an related note on Linear Hashing by D. Zhang et al.)
- Shapiro, Join Processing in Database Systems with Large Memories, ACM Transactions on Database Systems, vol.11, pp. 239-264, 1986.
- Chou and D.DeWitt, An Evaluation of Buffer Management Strategies for Relational Database Systems, Proceedings of the VLDB Conf. pp.127-141, 1985.
- Lomet, Simple, Robust and Highly Concurrent B-trees with Node Deletion, Proc. of IEEE Int. Conf. on Data Engineering (ICDE), Boston, MA, March 2004.
- Ioannidis, Query Optimization, ACM Computing Surveys, pp. 103--114, 1996.
- Guttman, R-trees: A Dynamic Index Structure for Spatial Searching, Proceedings of the ACM SIGMOD Conf., pp. 47-57, 1984.
- Sharaf, P.K. Chrysanthis, A. Labrinidis, and K. Pruhs, Algorithms and Metrics for Processing Multiple Heterogeneous Continuous Queries, ACM Trans. on Database Systems, vol. 32, no. 1, pp. 1-43, March 2008.
- T. Sellis Multiple-query optimization, ACM Trans. on Database Systems, vol. 13, no. 1, pp. 23-52, March 1988.
Προτεινόμενα συγγράμματα
P.A. Bernstein, V. Hatzilacos and N. Goodman, Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, Reading, MA, 1987.
Silberschatz, H.F. Korth and S. Sudarshani, Database System Concepts, 5th or 6th Edition, McGraw-Hill, NY, NY 2006.
J. Gray and A. Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers, San Fransisco, CA, 1993.
Διδάσκοντες
Αλέξης Δελής
Καθηγητής του Τμήματος Πληροφορικής και Τηλεπικοινωνιών
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Έλεγχος συνδρομικότητας (σειριοποιησιμότητα, διφασικό κλείδωμα, αισιόδοξος έλεγχος συνδρομικότητας, ειδικοί αλγόριθμοι για Β+ δένδρα), Ανάκαμψη (αλγόριθμος προενημερωμένου ημερολογίου και ειδικότερα ο αλγόριθμος ARIES), Βελτιστοποίηση και Επεξεργασία Επερωτήσεων (αλγόριθμοι ζεύξης με κατακερματισμό και συγχώνευση σάρωση παρουσία μεγάλης μνήμης, αλγόριθμος βελτιστοποίησης βασισμένος στον δυναμικό προγραμματισμό, πιθανοτικοί αλγόριθμοι βελτιστοποίησης, χρήση ιστογραμμάτων για στατιστική προσέγγιση δεδομένων), Πολυδιάστατες Δομές Δεδομένων (R- δένδρα), Διαχείριση Ενδιάμεσης Μνήμης (αλγόριθμοι αντικατάστασης σελίδων ανάλογα με την μορφή προσπέλασης των δεδομένων), Παράλληλες και Κατανεμημένες Βάσεις Δεδομένων (έλεγχος συνδρομικότητας δια ψήφου, διφασική επικύρωση, αλγόριθμοι ζεύξης σε κατανεμημένο περιβάλλον, η μηχανή βάσεων δεδομένων GAMMA, μελλοντικές εξελίξεις στις παράλληλες βάσεις δεδομένων), Αντικειμενοστρεφείς Βάσεις Δεδομένων (στοιχεία αντικειμενοσχεσιακών βάσεων δεδομένων, το αντικειμενοστρεφές σύστημα ObjectStore), παρελθόν και μέλλον των συστημάτων βάσεων δεδομένων.
Το μάθημα στοχεύει τόσο στην εισαγωγή των φοιτητών στις εσωτερικές λεπτομέρειες των βάσεων δεδομένων, όσο και στο να τους δώσει κίνητρο για τη χρήση και μελέτη διαφόρων σύγχρονων προσεγγίσεων στη διαχείριση δεδομένων. Τέτοιου είδους προσεγγίσεις καθιστούν δυνατή την ανάπτυξη μηχανισμών για τη μοντελοποίηση ετερογενών δεδομένων που χρησιμοποιούνται σε σύγχρονες εφαρμογές, ενώ παίζουν σημαντικό ρόλο στην περαιτέρω ανάπτυξη των μοντέρνων συστημάτων λογισμικού.
- Βασικές γνώσεις Βάσεων Δεδομένων, Αλγορίθμων και Λειτουργικών Συστημάτων
- Προγραμματισμός σε περιβάλλον Unix
- Γνώση C/C++ ή Java
- Προπτυχιακό Μάθημα: Κ29 Σχεδίαση και Χρήση Βάσεων Δεδομένων
Βιβλία
- D. Ullman, Principles of Database and Knowledge Database Systems: Volumes I & II, Computer Science Press, Principles of Computer Science Series, Rockville, MD, 1988
Άρθρα
- Meijer and G. Bierman, A co-Relational Model of Data for Large Shared Data Banks, ACM Queue Magazine, vol. 9, no. 3, March 2011.
- Poosala, Zipf's Law, Technical Report, 900 839 0750, CS, Univ. of Wisconsin, Madison, WI, 1995 based on "G.K. Zipf, Human Hehavior and the Principle of Least Effort, Addison-Wesley, Reading, MA, 1949".
- A. Patterson, G. Gibson and R. H. Katz, A Case for Redundant Arrays of Inexpensive Disks (RAID), Proc. of ACM SIGMOD Int. Conf. on Management of Data pp. 109-116, Chigago, IL, June 1987
- N. Gray, R.A. Lorie, G.R. Putzolu and I.L. Traiger, "Granularity of Locks and Degrees of Consistency in a Shared Database" IFIP Working Conference on Modelling of Database Management Systems, Freudenstadt, Germany, December 1975.
- T. Kung and J. Robinson, "On Optimistic Methods for Concurrency Control", ACM Transactions on Database Systems, vol. 6, no. 2, pp. 213-226, 1981.
- Comer, Ubiquitous B-Tree ACM Computing Surveys, vol. 11 , no. 2, June 1979.
- Jannink, Deletion in B+-trees. ACM SIGMOD RECORD, vol.24, no.1, pp. 33-38, 1995.
- Stonebraker, Operating system support for database management , Communications of the ACM, vol. 24 no. 7, July 1981.
- J. Carey and W.A. Muhanna, The performance of multiversion concurrency control algorithms. ACM Trans. Comput. Syst. vol. 4, no. 4 Sep. 1986.
- P. Reed, Implementing atomic actions on decentralized data. , ACM Trans. Comput. Syst. vol. 1, no. 1, Feb. 1983
- Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, vol. 19. no. 9, pp. 509-517, Sept. 1975.
- Fagin, J. Nievergelt, N. Pippenger, H.R. Strong, Extendible hashing--a fast access method for dynamic files, ACM Transaction on Database Systems, vol. 4, no. 3, pp 315-344, September 1979.
- Witold, Linear hashing: A new tool for file and table addressing, Proc. 6th Conference on Very Large Databases, 1980. (an related note on Linear Hashing by D. Zhang et al.)
- Shapiro, Join Processing in Database Systems with Large Memories, ACM Transactions on Database Systems, vol.11, pp. 239-264, 1986.
- Chou and D.DeWitt, An Evaluation of Buffer Management Strategies for Relational Database Systems, Proceedings of the VLDB Conf. pp.127-141, 1985.
- Lomet, Simple, Robust and Highly Concurrent B-trees with Node Deletion, Proc. of IEEE Int. Conf. on Data Engineering (ICDE), Boston, MA, March 2004.
- Ioannidis, Query Optimization, ACM Computing Surveys, pp. 103--114, 1996.
- Guttman, R-trees: A Dynamic Index Structure for Spatial Searching, Proceedings of the ACM SIGMOD Conf., pp. 47-57, 1984.
- Sharaf, P.K. Chrysanthis, A. Labrinidis, and K. Pruhs, Algorithms and Metrics for Processing Multiple Heterogeneous Continuous Queries, ACM Trans. on Database Systems, vol. 32, no. 1, pp. 1-43, March 2008.
- T. Sellis Multiple-query optimization, ACM Trans. on Database Systems, vol. 13, no. 1, pp. 23-52, March 1988.
P.A. Bernstein, V. Hatzilacos and N. Goodman, Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, Reading, MA, 1987.
Silberschatz, H.F. Korth and S. Sudarshani, Database System Concepts, 5th or 6th Edition, McGraw-Hill, NY, NY 2006.
J. Gray and A. Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers, San Fransisco, CA, 1993.
|
Αλέξης ΔελήςΚαθηγητής του Τμήματος Πληροφορικής και Τηλεπικοινωνιών Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών |
Συστήματα Διαχείρισης Βάσεων Δεδομένων (ΣΔΒΔ), Εφαρμογές Βάσεων Δεδομένων, Σκοπός Βάσεων Δεδομένων, Επίπεδα Αφαίρεσης, Στιγμιότυπα και Σχήματα, Μοντέλα Δεδομένων, Γλώσσα Χειρισμού Δεδομένων, Γλώσσα Ορισμού Δεδομένων, SQL, Σχεδιασμός Βάσεων Δεδομένων, Το Μοντέλο Οντοτήτων-Συσχετίσεων, Αντικειμενοσχεσιακά Μοντέλα Δεδομένων, XML, Εσωτερικά Στοιχεία ΣΒΔΒ, Αρχιτεκτονικές Βάσεων Δεδομένων.
Τύποι χαρακτηριστικών, Σχεσιακό Σχήμα και Στιγμιότυπο, Κλειδιά, Σχεσιακές Γλώσσες Επερωτήσεων, Επιλογή Εγγραφών και Στηλών, Πράξεις με Σχέσεις (Καρτεσιανό Γινόμενο, Ένωση, Τομή, κτλ.).
Ανασκόπηση της γλώσσας SQL, Ορισμός δεδομένων, Βασική δομή επερωτήσεων, Επιπρόσθετες βασικές λειτουργίες, Λειτουργίες συνόλων, Τιμές NULL, Συναρτήσεις συνάθροισης, Εμφωλευμένες επερωτήσεις, Τροποποίηση Βάσης Δεδομένων.
Εκφράσεις Join, Όψεις (Views), Δοσοληψίες (Transactions), Περιορισμοί Ακεραιότητας, Τύποι δεδομένων και Σχήματα SQL, Εξουσιοδότηση (Authorization).
Πρόσβαση στην SQL από γλώσσες προγραμματισμού, Δυναμική χρήση SQL, JDBC και ODBC, Embedded SQL, Τύποι δεδομένων και Σχήματα SQL, Συναρτήσεις και δομές διαδικασιών, Triggers, προχωρημένα στοιχεία συνάθροισης, OLAP.
Ανασκόπηση φυσικών μέσων αποθήκευσης, Μαγνητικοί δίσκοι, RAID, τριτοβάθμια αποθήκευση, Πρόσβαση Αποθήκευσης, Οργάνωση αρχείων, Οργάνωση εγγραφών σε αρχεία, Αποθήκευση Δεδομένων-Λεξικών.
Βασικές έννοιες, Ταξινομημένα ευρετήρια, Αρχεία ευρετηρίων B+-δέντρων, Αρχεία ευρετηρίων Β-δέντρων, Στατικός κατακερματισμός, Δυναμικός κατακερματισμός, Σύγκριση ταξινομημένης ευρετηριοποίησης και κατακερματισμού, Ορισμός ευρετηρίων στην SQL, Πρόσβαση με πολλαπλά κλειδιά.
Ανασκόπηση, Μετρικές κόστους επερωτήσεων, Λειτουργία επιλογής, ταξινόμηση, λειτουργία ένωσης, άλλες λειτουργίες, αξιολόγηση εκφράσεων.
Εισαγωγή στη βελτιστοποίηση επερωτήσεων, μετασχηματισμός σχεσιακών εκφράσεων, Πληροφορία καταλόγου για εκτίμηση κόστους, Στατιστική πληροφορία για εκτίμηση κόστους, βελτιστοποίηση βάσει κόστους, Δυναμικός προγραμματισμός για την επιλογή πλάνων αξιολόγησης, Υλοποιημένες όψεις (Materialized views).
Η έννοια της δοσοληψίας, Κατάσταση δοσοληψίας, παράλληλες εκτελέσεις, δυνατότητα σειριοποίησης (serializability), δυνατότητα ανάκαμψης, υλοποίηση Απομόνωσης, Ορισμός δοσοληψίας στην SQL, Έλεγχος δυνατότητας σειριοποίησης.
Πρωτόκολλα βασισμένα στο κλείδωμα (lock-based), Πρωτόκολλα βασισμένα στη χρονική στιγμή (timestamp-based), Πρωτόκολλα βασισμένα στην εγκυρότητα (validation-based), Πολλαπλά επίπεδα λεπτομέρειας (multiple granularity), Σχήματα πολλαπλών εκδόσεων (multi-version schemes), Λειτουργίες εισαγωγής και διαγραφής, Παραλληλία σε δομές ευρετηρίων.
Κατηγοριοποίηση αποτυχιών, Δομή αποθήκευσης, Ανάκαμψη και ατομικότητα, Ανάκαμψη βάσει logs, Συστήματα απομακρυσμένης λήψης αντιγράφων.
Ανοικτό Ακαδ. Μάθημα
Αρ. Επισκέψεων : 0
Αρ. Προβολών : 0
Ημερολόγιο
Ανακοινώσεις
- - Δεν υπάρχουν ανακοινώσεις -
