Implementation of Database Systems
Σημασιολογική Σχεδίαση
Πραγματοποιείται με το σημασιολογικό μοντέλο οντοτήτων-συσχετίσεων.
Περιλαμβάνει την αναγνώριση και κατηγοριοποίηση των οντοτήτων (π.χ., πελάτες, προϊόντα) και των σχέσεων μεταξύ τους.
Σκοπός: να αποτυπώσει τις απαιτήσεις της επιχείρησης και τη δομή των δεδομένων με έναν κατανοητό και αναπαραστατικό τρόπο.
Λογική Σχεδίαση
Μετατρέπει το σημασιολογικό μοντέλο σε ένα λογικό σχήμα, βασισμένο στο σχεσιακό μοντέλο.
Το λογικό σχήμα αποτελείται από πίνακες, πρωτεύοντα κλειδιά, ξένα κλειδιά και τους περιορισμούς τους.
Σκοπός: να περιγράψει τη δομή της βάσης δεδομένων με τρόπο ανεξάρτητο από τη φυσική υλοποίηση, αλλά ικανό να υποστηρίξει τις απαιτήσεις των χρηστών και των εφαρμογών, προσδιορίζοντας με ακρίβεια τη διαχείριση των δεδομένων και τις σχέσεις τους.
Φυσική Σχεδίαση
Μετατρέπει το λογικό σχήμα σε φυσικό σχήμα, με στόχο τη βελτιστοποίηση της αποθήκευσης και διαχείρισης των δεδομένων σε συγκεκριμένα αποθηκευτικά μέσα.
Περιλαμβάνει την επιλογή δομών ευρετηρίων, την οργάνωση της αποθήκευσης, την κατανομή των δεδομένων σε σελίδες και αρχεία, καθώς και την επιλογή μηχανισμών ταξινόμησης.
Σκοπός: Η βελτίωση της απόδοσης του συστήματος, εξασφαλίζοντας γρήγορη και αποδοτική πρόσβαση στα δεδομένα, με βάση τις απαιτήσεις της εφαρμογής και των χρηστών.
Το φυσικό σχήμα απεικονίζεται μέσω του λειτουργικού σε δίσκο.
Υλοποίηση ΣΔΒΔ
Γίνεται κατά κύριο λόγο στις γλώσσες C, C++, Java
Επικοινωνία με τον Δίσκο
Το φυσικό σύστημα επικοινωνεί με τον δίσκο μέσω του λειτουργικού συστήματος.
Αποθήκευση Πινάκων
Πώς να αποθηκεύσουμε τους πίνακες σε μέσα φυσικής αποθήκευσης (αρχεία)?
Πρόσβαση σε γραμμές/στήλες (π.χ., δίσκος, RAM, συστοιχίες υπολογιστών).
Μέγεθος Πινάκων
Μικροί Πίνακες (π.χ., <1GB): εργαλεία που ήδη γνωρίζουμε.
Μεγάλοι Πίνακες; (π.χ., TBs, PetaBytes?)
Δομές Δεδομένων & Αλγόριθμοι
Συνδεδεμένες λίστες, Πίνακες, Δέντρα, Πίνακες Κατακερματισμού.
Επέκταση των “εργαλείων μας” με προηγμένες μεθόδους Ταξινόμησης, Κατακερματισμού, Δυναμικού Προγραμματισμού, Επεξεργασίας γράφων, κτλ.
Μοντέλο I/O (Εισόδου/Εξόδου)
Μεταφορά και χρήση δεδομένων στην RAM.
RAM + HD/SSDs + Ομαδοποίηση Δεδομένων (data clustering).
Γλώσσες/Βιβλιοθήκες
python/c++, pandas, βιβλιοθήκες, ή δημιουργία δικών μας “Γλώσσα Διαχείρισης Δεδομένων” + Βιβλιοθήκες.
Κλιμάκωση των δεδομένων I/O * .
Ταξινόμηση Φυσικών Μονάδων Αποθήκευσης
Ταχύτητα προσπέλασης στα δεδομένα.
Κόστος αποθήκευσης.
Αξιοπιστία.
Απώλεια δεδομένων σε κατάρρευση του συστήματος ή πτώση τάσης.
Φυσικές αποτυχίες της μονάδας αποθήκευσης.
Διαχωρισμός Αποθήκευσης
Ασταθής (volatile) αποθήκευση: χάνεται το περιεχόμενο όταν απενεργοποιηθεί η μηχανή.
Σταθερή (non-volatile) αποθήκευση: Τα δεδομένα μένουν σταθερά ακόμη και αν απενεργοποιηθεί η συσκευή
Ιεραρχία Αποθήκευσης
L1,L2 Cache: MBs, 3-10 ns, ασταθής αποθήκευση.
S-RAM: GBs, 10-100 ns
D-RAM: 1-10 TBs, 50-100 µs, δευτερεύουσα ή on-line αποθήκευση.
Flash/SSD: TB to 10+ TB, 5-10 ms, σταθερή αποθήκευση.
Hard Drive (Magnetic): TB to PB, 10-60 seconds, τριτεύουσα ή off-line αποθήκευση.
Tape
Φυσικές Μονάδες Αποθήκευσης
Cache: Γρήγορη και πιο ακριβή αποθήκευση, Τη διαχειρίζεται το υλικό του υπολογιστικού συστήματος.
Κύρια μνήμη (RAM): Γρήγορη προσπέλαση(10 με 100 nanoseconds), Πολύ μικρή (η πολύ ακριβή) για να χωρέσει μια ΒΔ (Χωρητικότητα μέχρι λίγα Gigabytes).
Flash Μνήμες και SSD Δίσκοι (Solid State Disks): Αποθηκεύει δεδομένα σε διόδους (transistors) που είναι οργανωμένες σε κελί και σε μπλοκ.
Μαγνητικοί Δίσκοι: Τα δεδομένα αποθηκεύονται σε ένα περιστρεφόμενο δίσκο, με μαγνητικό διάβασμα/γράψιμο. Τυπικά αποθηκεύει ολόκληρη τη βάση δεδομένων.
Οπτικοί Δίσκοι: Η ανάγνωση των δεδομένων γίνεται οπτικά από ένα περιστρεφόμενο δίσκο με χρήση laser. CD-ROM (640 MB) και DVD (4.7 to 17 GB) και Blue Ray είναι οι πιο δημοφιλείς τύποι.
Ταινίες: Πολύ μεγάλη χωρητικότητα (υπάρχουν ταινίες 40 με 300 GB).
Juke-box: Υπάρχουν jukeboxes για οπτικούς δίσκους και ταινίες για αποθήκευση μεγάλου όγκου δεδομένων.
Δομή Μαγνητικού Δίσκου
Άτρακτος: Οι δίσκοι χωρίζονται σε ομόκεντρες κυκλικές ατράκτους σε κάθε επιφάνεια του δίσκου.
Τομέας: Μια άτρακτος χωρίζεται σε μικρότερους τομείς επειδή συνήθως περιέχει μεγάλη ποσότητα πληροφοριών.
Μπλοκ: Μια άτρακτος χωρίζεται σε μπλοκ.
Πακέτο Δίσκων
Περιέχει πολλούς μαγνητικούς δίσκους συνδεδεμένους σε έναν περιστρεφόμενο άξονα.
Ένας δίσκος είναι διπλής όψης όταν χρησιμοποιούνται και οι δύο επιφάνειές του για αποθήκευση.
Ελεγκτής Δίσκου
Είναι η διασύνδεση μεταξύ υπολογιστικού συστήματος και μονάδας δίσκου.
Δέχεται υψηλού επιπέδου εντολές ανάγνωσης γραψίματος σε μια περιοχή του δίσκου.
Ενεργοποιεί λειτουργίες όπως η κίνηση του βραχίονα στη σωστή άτρακτο και το διάβασμα ή γράψιμο δεδομένων.
Υπολογίζει και καταγράφει δείκτες ελέγχου σε κάθε τομέα για να πιστοποιήσει τη σωστή λειτουργία.
Εξασφαλίζει επιτυχές γράψιμο διαβάζοντας μετά το γράψιμο.
Εκτελεί νέα απεικόνιση των κατεστραμμένων τομέων.
Μέσω ενός ελεγκτή συνδέονται πολλοί δίσκοι σε ένα υπολογιστικό σύστημα.
Τυπικές οικογένειες διασυνδέσεων δίσκων: ATA, SATA, SCSI, SAS
Διάβασμα Μπλοκ
Εντοπισμός ατράκτου: η μετακίνηση του βραχίονα στην άτρακτο του μπλοκ.
Περιστροφή δίσκου: ο δίσκος περιστρέφεται για να βρεθεί η κεφαλή στην αρχή του μπλοκ.
Ανάκτηση Δεδομένων: Η κεφαλή ανακτά τα δεδομένα του τομέα, μέσω περιστροφής του δίσκου από την αρχή στο τέλος του μπλοκ
Μέτρα Απόδοσης Δίσκων
Χρόνος Προσπέλασης: ο απαιτούμενος χρόνος από το αίτημα για ανάγνωση ή γράψιμο μέχρι να ξεκινήσει η μεταφορά δεδομένων.
Χρόνος εντοπισμού: χρόνος που απαιτείται για μετακίνηση του βραχίονα στη σωστή άτρακτο.
Καθυστέρηση Περιστροφής: ο απαιτούμενος χρόνος να βρεθεί κάτω από την κεφαλή ο σωστός τομέας.
Ρυθμός Μεταφοράς Δεδομένων: ο ρυθμός ανάκτησης των δεδομένων ή το γράψιμο των δεδομένων στο δίσκο.
Τεχνικές Αποδοτικής Πρόσβασης σε Δεδομένα
Χρήση της ενδιάμεσης μνήμης.
Κατάλληλη οργάνωση των δεδομένων στον δίσκο (data clustering).
Ανάγνωση δεδομένων πριν ζητηθούν.
Κατάλληλη χρονοδρομολόγηση των αιτημάτων Ι/Ο.
Χρήση δίσκων καταγραφής για την αποθήκευση προσωρινών εγγραφών (Write-Ahead Logging).
Κόστος Εκτέλεσης Αλγορίθμου & Ενδιάμεση Μνήμη
Το ΙΟ του Δίσκου (R/W) κυριαρχεί στο κόστος του αλγορίθμου.
Ο μαγνητικός Δίσκος είναι πολύ πιο αργός τόσο σε σχέση με την κύρια μνήμη, όσο και σε σχέση με τον επεξεργαστή.
Στόχος: Μείωση των επισκέψεων (Γράψιμο & Διάβασμα) στον σκληρό δίσκο.
Ενδιάμεση μνήμη (buffer)
Είναι ένα μέρος της κύριας μνήμης που χρησιμοποιείται για προσωρινή διαχείριση δεδομένων του δίσκου από μία διεργασία.
Ένα μέρος της κύριας μνήμης χρησιμοποιείται για να αποθηκεύσει τα ενδιάμεσα δεδομένα.
Η ενδιάμεση μνήμη έχει συγκεκριμένο μέγεθος σε block.
Η Βάση δεδομένων διατηρεί και διαχειρίζεται την δική της ενδιάμεση μνήμη.
Διαχειριστής Ενδιάμεσης Μνήμης
Ο διαχειριστής της ενδιάμεσης μνήμης κρατά δομές στην μνήμη με όλη την χρήσιμη πληροφορία.
Ποιο μπλοκ του δίσκου είναι σε ποιο μπλοκ της μνήμης.
Ένα βρώμικο μπιτ για κάθε μπλοκ μνήμης για το οποίο αν άλλαξε ή όχι από την μεταφορά του προς τον δίσκο.
Πότε χρησιμοποιήθηκε τελευταία φορά κάθε μπλοκ στη μνήμη.
Επιλογή Μπλοκ Μνήμης Προς Αντικατάσταση
Στρατηγική αντικαταστάσεων μπλοκ μνήμης από μπλοκ που έρχεται από τον δίσκο.
Οι στρατηγικές που είναι κατάλληλες για ΣΔΒΔ δεν είναι απαραίτητα αυτές των Λειτουργικών Συστημάτων.
Λιγότερο Πρόσφατα Χρησιμοποιημένο (LRU).
Πλέον Πρόσφατα Χρησιμοποιημένο (MRU).
Άλλα Θέματα Διαχειριστή Ενδιάμεσης Μνήμης
Καρφιτσωμένα μπλοκ.
Σπρώξιμο μπλοκ στο δίσκο.
Λειτουργικό Σύστημα και Βάση Δεδομένων
Σχέση à Πίνακας.
Πλειάδα à Γραμμή.
Χαρακτηριστικό à Στήλη.
Δόμηση Πεδίων Σε Εγγραφή
Κάθε πεδίο έχει σταθερό μήκος σε όλες τις εγγραφές.
Κάθε πεδίο έχει μεταβλητό μήκος ανά εγγραφή.
Δόμηση Εγγραφών σε Μπλοκ
Σταθερά πακεταρισμένα.
Εγγραφές πλήρως σε 1 μπλοκ.
Μεταβλητό μήκος εγγραφών με ευρετήριο εγγραφών και κεφαλίδα.
Ανάθεση Εγγραφών σε Μπλοκ
Κριτήριο: ταχύτητα στην αναζήτηση των εγγραφών με βάση τις συνθήκες αναζήτησης
Αρχείο Σωρού (heap file)
Χώρος Δομών Ευρετηρίων
Πράξεις σε Αρχεία
OPEN
FIND
FINDNEXT
READ
INSERT
DELETE
MODIFY
CLOSE
REORGANIZE
READ_ORDERED