Συστήματα Διαχείρισης Μεγάλων Δεδομένων (πρώην Βάσεις 2) — Ιούνιος 2021¶
Μεταγραφή από το κείμενο του DB-_2021.pdf (σελίδες 1–2).
DB-_2021.pdf¶
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ ΠΟΛΥΤΕΧΝΙΚΗ ΣΧΟΛΗ ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ¶
ΒΑΣΕΙΣ ΔΕΔΟΜΕΝΩΝ ΙI¶
ΚΑΘΗΓΗΤΕΣ : Β. ΜΕΓΑΛΟΟΙΚΟΝΟΜΟΥ, A. KOMNHNOΣ
ΟΝΟΜΑΤΕΠΩΝΥΜΟ: __________________________________________________
ΑΜ: ________________________ ΕΤΟΣ: ___________________________________
Θέμα 1ο Γενικές ερωτήσεις (50%)¶
-
Δώστε την έννοια της δοσοληψίας. Ποιες ιδιότητες πρέπει να εξασφαλίζει ένα ΣΔΒΔ για να διασφαλίζεται η ακεραιότητα των δεδομένων; (10 μονάδες)
-
Που εξυπηρετεί η χρήση της καμπύλης Hilbert στην δεικτοδότηση στατικών χωρικών δεδομένων με R-trees. (5 μονάδες) (10 μονάδες)
-
Αναφέρετε τις βασικές διαφορές μεταξύ των DSMSs (Data Stream Management Systems) και των DBMSs. (10 μονάδες)
-
Σε ποιες περιπτώσεις ενδείκνυται η χρήση των NoSQL databases και σε ποιες των RDBMSs; (10 μονάδες)
-
Περιγράψτε το lower-bounding λήμμα και πώς αυτό βοηθάει στην αναζήτηση ομοιότητας (βάση της προσέγγισης GEMINI- Generic Multimedia Indexing) πολυμεσικών δεδομένων. (10 μονάδες)
Θέμα 2ο Βελτιστοποίηση Επερωτήσεων (30%)¶
Θεωρείστε τη σχέση:
ΚΑΘΗΓΗΤΗΣ (ΑΦΜ, Όνομα, Επώνυμο, Ειδικότητα, IDΣχολείου) και τα ακόλουθα χαρακτηριστικά: nΚΑΘΗΓΗΤΗΣ = 16384 εγγραφές fΚΑΘΗΓΗΤΗΣ = 64 εγγραφές ανά μπλοκ V(Όνομα, ΚΑΘΗΓΗΤΗΣ) = 256 διακριτές εγγραφές V(Επώνυμο, ΚΑΘΗΓΗΤΗΣ) = 512 διακριτές εγγραφές V(Ειδικότητα, ΚΑΘΗΓΗΤΗΣ) = 32 διακριτές εγγραφές V(IDΣχολείου, ΚΑΘΗΓΗΤΗΣ) = 128 διακριτές εγγραφές
Για τον υπολογισμό της επιλεκτικότητας (selection cardinality) θεωρείστε ότι έχουμε ομοιόμορφη κατανομή τιμών.
-
Θεωρήστε την πράξη επιλογής σΌνομα = 'Παναγιώτης' (ΚΑΘΗΓΗΤΗΣ)
-
a. Βρείτε το πλήθος των προσπελάσεων σε αριθμό μπλοκς, αν εφαρμόσουμε ακολουθιακή σάρωση. (5 μονάδες)
-
b. Αν το αρχείο είναι διατεταγμένο ως προς το πεδίο Όνομα , ποιο είναι το πλήθος προσπελάσεων σε αριθμό μπλοκς; (10 μονάδες)
-
Θεωρήστε την πράξη επιλογής σIDΣχολείου= '3ο Λύκειο Πατρών'(ΚΑΘΗΓΗΤΗΣ). Ας υποθέσουμε ότι χρησιμοποιούμε ως δομή δεικτοδότησης ένα πρωτεύον (primary) ευρετήριο πάνω στο πεδίο IDΣχολείου , με fan-out = 4.
-
a. Βρείτε το πλήθος των επιπέδων του ευρετηρίου. (5 μονάδες)
-
b. Ποιο είναι το πλήθος των προσπελάσεων σε αριθμό μπλοκς για την απάντηση του παραπάνω ερωτήματος; (10 μονάδες)
Θέμα 3ο: Κατανεμημένες Βάσεις Δεδομένων (20%)¶
Έστω οι σχέσεις ΒΙΒΛΙΟ, ΣΥΓΓΡΑΦΕΑΣ oι οποίες είναι αποθηκευμένες στους κόμβους Τ1 και Τ2 αντίστοιχα.
ΒΙΒΛΙΟ¶
ΒΙΒΛΙΟ
| ID | ID_Συγγραφέα | Τίτλος |
|---|---|---|
| 4 bytes | 2 bytes | 60 bytes |
ΣΥΓΓΡΑΦΕΑΣ
| ID | Όνομα |
|---|---|
| 2 bytes | 80 bytes |
Για τις σχέσεις αυτές έχουμε τα παρακάτω στιγμιότυπα:
ΒΙΒΛΙΟ
| ID | ID_Συγγραφέα | Τίτλος |
|---|---|---|
| 1 | S1 | … |
| 2 | S1 | … |
| 3 | S2 | … |
| 4 | S2 | … |
| 5 | S1 | … |
| 6 | S3 | … |
| 7 | S2 | … |
ΣΥΓΓΡΑΦΕΑΣ
| ID | Όνομα |
|---|---|
| S1 | … |
| S2 | … |
| S3 | … |
| S4 | … |
| S5 | … |
Με βάση τα στοιχεία που σας δίνονται, προτείνετε 3 διαφορετικά πλάνα εκτέλεσης για το ερώτημα ΒΙΒΛΙΟ ⋈ ΣΥΓΓΡΑΦΕΑΣ, το οποίο υποβάλλεται από τον κόμβο Τ3. Για κάθε προτεινόμενο πλάνο, περιγράψτε τα βήματά του, υπολογίστε το κόστος εκτέλεσής του και επιλέξτε το βέλτιστο. To ένα από τα τρία πλάνα που θα δημιουργήσετε θα πρέπει να χρησιμοποιεί semi-join.
Σημείωση: το κόστος εκτέλεσης ενός πλάνου εξαρτάται μόνο από τον αριθμό των bytes που μεταφέρονται.
Καλή επιτυχία!
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
-
Δοσοληψία (transaction) είναι μια λογική μονάδα εργασίας που αποτελείται από ένα σύνολο πράξεων ανάγνωσης/εγγραφής και πρέπει να εκτελεστεί είτε ολόκληρη είτε καθόλου, μεταφέροντας τη βάση από μια συνεπή κατάσταση σε άλλη συνεπή κατάσταση. Ένα ΣΔΒΔ πρέπει να εξασφαλίζει τις ιδιότητες ACID: Atomicity (ατομικότητα), Consistency (συνέπεια), Isolation (απομόνωση) και Durability (μονιμότητα). Αυτές υλοποιούνται με μηχανισμούς ανάκαμψης (log, undo/redo), ελέγχου ταυτοχρονισμού (κλειδώματα, χρονοσφραγίδες, σειριοποίηση) και ελέγχου περιορισμών ακεραιότητας.
-
Η καμπύλη Hilbert αντιστοιχίζει χωρικά αντικείμενα σε μονοδιάστατες τιμές διατηρώντας τη χωρική γειτνίαση. Σε στατικά χωρικά δεδομένα χρησιμοποιείται συνήθως για ταξινόμηση/bulk-loading των MBRs και συσκευασία τους σε κόμβους R-tree (π.χ. Hilbert R-tree). Έτσι μειώνονται οι επικαλύψεις μεταξύ MBRs, βελτιώνεται η συστάδωση των κόμβων και μειώνονται οι προσπελάσεις σε ερωτήματα εμβέλειας και εγγύτητας.
-
Βασικές διαφορές DSMS–DBMS: Τα DBMS διαχειρίζονται αποθηκευμένα, πεπερασμένα δεδομένα με τυχαία πρόσβαση και ερωτήματα μίας εκτέλεσης (pull/query-driven), παρέχοντας συνήθως ACID και ακριβή αποτελέσματα. Τα DSMS διαχειρίζονται συνεχώς εισερχόμενες ροές δεδομένων (push-based), μη πεπερασμένες και υψηλού ρυθμού, με συνεχή/μόνιμα ερωτήματα (standing queries), παραθυρικά σύνολα, αλγορίθμους μίας διέλευσης, προσεγγιστικά αποτελέσματα, διαχείριση φορτίου και συχνά χαλαρότερες εγγυήσεις συνέπειας.
-
NoSQL ενδείκνυται όταν απαιτούνται οριζόντια κλιμάκωση, πολύ μεγάλοι όγκοι, υψηλός ρυθμός εγγραφών, ευέλικτο/μεταβαλλόμενο σχήμα, ημιδομημένα ή αδόμητα δεδομένα, κατανεμημένη διαθεσιμότητα και συχνά eventual consistency (key-value, document, column-family, graph). RDBMS ενδείκνυται όταν απαιτούνται ισχυρή συνέπεια/ACID, σύνθετα ερωτήματα και joins, σταθερό σχήμα, ακεραιότητα και ώριμη υποστήριξη συναλλαγών.
-
Το lower-bounding λήμμα στη GEMINI λέει ότι αν ορίσουμε μια συνάρτηση απόστασης \(d_{lb}\) στον χώρο δεικτοδότησης τέτοια ώστε \(d_{lb}(F(x),F(y)) \le d(x,y)\) για κάθε ζεύγος αντικειμένων, τότε αν \(d_{lb}(F(q),F(o)) > \epsilon\) συνεπάγεται \(d(q,o) > \epsilon\). Άρα το \(o\) μπορεί να απορριφθεί με ασφάλεια χωρίς να προσπελαστεί το αρχικό πολυμεσικό δεδομένο. Έτσι δεν έχουμε false dismissals (μόνο false positives), και η αναζήτηση ομοιότητας γίνεται πρώτα στον μικρότερης διάστασης χώρο δεικτοδότησης και μετά γίνεται επαλήθευση των υποψηφίων στην πραγματική απόσταση.
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Δίνονται \(n=16384\), \(f=64\), άρα \(\lceil n/f \rceil=256\) μπλοκ δεδομένων.
- Για \(\sigma_{\text{Όνομα}='\text{Παναγιώτης}'}(ΚΑΘΗΓΗΤΗΣ)\) έχουμε [ SC(\text{Όνομα})=\frac{n}{V(\text{Όνομα})}=\frac{16384}{256}=64 ] εγγραφές.
a. Με ακολουθιακή σάρωση διαβάζονται όλα τα μπλοκ: \(256\) προσπελάσεις μπλοκ.
b. Αν το αρχείο είναι διατεταγμένο ως προς Όνομα, γίνεται δυαδική αναζήτηση για την πρώτη εμφάνιση. Χρειάζονται \(\lceil \log_2 256 \rceil=8\) προσπελάσεις για τον εντοπισμό και περίπου \(\lceil 64/64 \rceil=1\) μπλοκ για τις 64 ταιριαστές εγγραφές. Σύνολο περίπου \(8+1=9\) προσπελάσεις μπλοκ.
- Για \(\sigma_{\text{IDΣχολείου}='3ο\ Λύκειο\ Πατρών'}(ΚΑΘΗΓΗΤΗΣ)\) έχουμε [ SC(\text{IDΣχολείου})=\frac{16384}{128}=128 ] εγγραφές.
a. Πρωτεύον ευρετήριο σημαίνει μία καταχώρηση ανά μπλοκ δεδομένων (sparse), άρα \(256\) καταχωρήσεις. Με fan-out \(=4\): [ \lceil 256/4 \rceil=64,\quad \lceil 64/4 \rceil=16,\quad \lceil 16/4 \rceil=4,\quad \lceil 4/4 \rceil=1. ] Άρα το ευρετήριο έχει \(4\) επίπεδα.
b. Η αναζήτηση στο ευρετήριο κοστίζει \(4\) προσπελάσεις. Οι \(128\) ταιριαστές εγγραφές καταλαμβάνουν \(\lceil 128/64 \rceil=2\) μπλοκ δεδομένων. Άρα το συνολικό κόστος είναι περίπου \(4+2=6\) προσπελάσεις μπλοκ. (Με αυστηρή χειρότερη περίπτωση μη ευθυγράμμισης μπορεί να χρειαστεί έως \(1\) επιπλέον μπλοκ.)
Θέμα 3¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Θεωρώ ότι η συνένωση γίνεται με συνθήκη \(BIBLIO.ID\_Συγγραφέα = ΣΥΓΓΡΑΦΕΑΣ.ID\) και ότι ο κόμβος \(T3\), όπου υποβάλλεται το ερώτημα, μπορεί να εκτελέσει την τελική συνένωση.
Μεγέθη: [ |BIBLIO|=7(4+2+60)=462\text{ bytes}, ] [ |ΣΥΓΓΡΑΦΕΑΣ|=5(2+80)=410\text{ bytes}. ] Στο \(BIBLIO\) εμφανίζονται μόνο οι συγγραφείς \(S1,S2,S3\), άρα όλες οι \(7\) εγγραφές του \(BIBLIO\) βρίσκουν ταίρι. Το αποτέλεσμα έχει \(7\) εγγραφές. Αν κρατηθούν και τα δύο πεδία ID, το μέγεθος εγγραφής είναι \(4+2+60+2+80=148\) bytes, άρα [ |R|=7\cdot 148=1036\text{ bytes}. ] (Αν αφαιρεθεί το διπλό ID συγγραφέα, \(|R|=7\cdot146=1022\) bytes· το βέλτιστο πλάνο δεν αλλάζει.)
-
Πλάνο 1: Μεταφορά του \(BIBLIO\) από \(T1\) στο \(T2\) (\(462\) bytes), τοπική συνένωση στο \(T2\), αποστολή του αποτελέσματος \(R\) στο \(T3\) (\(1036\) bytes). Κόστος: [ 462+1036=1498\text{ bytes}. ]
-
Πλάνο 2: Μεταφορά του \(ΣΥΓΓΡΑΦΕΑΣ\) από \(T2\) στο \(T1\) (\(410\) bytes), τοπική συνένωση στο \(T1\), αποστολή του \(R\) στο \(T3\) (\(1036\) bytes). Κόστος: [ 410+1036=1446\text{ bytes}. ]
-
Πλάνο 3 (με semi-join): Το \(T1\) στέλνει στο \(T2\) την προβολή [ \pi_{ID_Συγγραφέα}(BIBLIO), ] η οποία έχει \(3\) διακριτές τιμές (\(S1,S2,S3\)), άρα μέγεθος \(3\cdot2=6\) bytes. Στο \(T2\) υπολογίζεται το semi-join [ S'=ΣΥΓΓΡΑΦΕΑΣ \ltimes BIBLIO, ] δηλαδή κρατούνται μόνο οι συγγραφείς \(S1,S2,S3\), μέγεθος \(3\cdot82=246\) bytes. Έπειτα το \(T2\) στέλνει το \(S'\) στο \(T3\) (\(246\) bytes) και το \(T1\) στέλνει το \(BIBLIO\) στο \(T3\) (\(462\) bytes), όπου γίνεται η τελική συνένωση. Κόστος: [ 6+246+462=714\text{ bytes}. ] Αν η τελική συνένωση γινόταν στο \(T1\) μετά το semi-join, το κόστος θα ήταν \(6+246+1036=1288\) bytes, δηλαδή χειρότερο.
Το πλάνο μεταφοράς και των δύο σχέσεων απευθείας στο \(T3\) κοστίζει \(462+410=872\) bytes, αλλά είναι επίσης χειρότερο από το παραπάνω semi-join πλάνο.
Βέλτιστο είναι το Πλάνο 3, με κόστος \(714\) bytes.