Συστήματα Διαχείρισης Μεγάλων Δεδομένων (πρώην Βάσεις 2) — Ιούνιος 2024¶
Μεταγραφή από τη φωτογραφία 158.png (μόνο το Θέμα 2).
158.png¶
Θέμα 2º Βελτιστοποίηση Επερωτήσεων (30%)
Θεωρείστε τη σχέση:
ΚΑΘΗΓΗΤΗΣ (ΑΦΜ, Όνομα, Επώνυμο, Ειδικότητα, IDΣχολείου)
και τα ακόλουθα χαρακτηριστικά:
- \(n_{\text{ΚΑΘΗΓΗΤΗΣ}} = 16384\) εγγραφές
- \(f_{\text{ΚΑΘΗΓΗΤΗΣ}} = 64\) εγγραφές ανά μπλοκ
- \(V(\text{Όνομα}, \text{ΚΑΘΗΓΗΤΗΣ}) = 256\) διακριτές εγγραφές
- \(V(\text{Επώνυμο}, \text{ΚΑΘΗΓΗΤΗΣ}) = 512\) διακριτές εγγραφές
- \(V(\text{Ειδικότητα}, \text{ΚΑΘΗΓΗΤΗΣ}) = 32\) διακριτές εγγραφές
- \(V(\text{IDΣχολείου}, \text{ΚΑΘΗΓΗΤΗΣ}) = 128\) διακριτές εγγραφές
Για τον υπολογισμό της επιλεκτικότητας (selection cardinality) θεωρείστε ότι έχουμε ομοιόμορφη κατανομή τιμών.
-
Θεωρήστε την πράξη επιλογής \(\sigma_{\text{Όνομα} = \text{'Παναγιώτης'}}\) (ΚΑΘΗΓΗΤΗΣ)
a. Βρείτε το πλήθος των προσπελάσεων σε αριθμό μπλοκ, αν εφαρμόσουμε ακολουθιακή σάρωση. (5 μονάδες)
b. Αν το αρχείο είναι διατεταγμένο ως προς το πεδίο Όνομα, ποιο είναι το πλήθος προσπελάσεων σε αριθμό μπλοκ; (10 μονάδες)
-
Θεωρήστε την πράξη επιλογής \(\sigma_{\text{IDΣχολείου} = \text{'3ο Λύκειο Πατρών'}}\) (ΚΑΘΗΓΗΤΗΣ). Ας υποθέσουμε ότι χρησιμοποιούμε ως δομή δεικτοδότησης ένα πρωτεύον (primary) ευρετήριο πάνω στο πεδίο IDΣχολείου, με fan-out = 4.
a. Βρείτε το πλήθος των επιπέδων του ευρετηρίου. (5 μονάδες)
b. Ποιο είναι το πλήθος των προσπελάσεων σε αριθμό μπλοκ για την απάντηση του παραπάνω ερωτήματος; (10 μονάδες)
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2024-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 2º Βελτιστοποίηση Επερωτήσεων¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Δίνονται \(n=16384\) εγγραφές και \(f=64\) εγγραφές/μπλοκ, άρα το πλήθος των μπλοκ της σχέσης είναι
[
B=\left\lceil \frac{n}{f}\right\rceil=\frac{16384}{64}=256.
]
- Για την επιλογή \(\sigma_{\text{Όνομα}=\text{'Παναγιώτης'}}(\text{ΚΑΘΗΓΗΤΗΣ})\):
Η επιλεκτικότητα είναι [ s=\frac{n}{V(\text{Όνομα})}=\frac{16384}{256}=64 ] εγγραφές κατά μέσο όρο.
a. Με ακολουθιακή σάρωση, εφόσον το αρχείο δεν είναι διατεταγμένο ως προς το πεδίο επιλογής, πρέπει να διαβαστούν όλα τα μπλοκ: [ \text{Κόστος}=B=256 \text{ μπλοκ}. ]
b. Αν το αρχείο είναι διατεταγμένο ως προς \(\text{Όνομα}\), χρησιμοποιείται δυαδική αναζήτηση για τον εντοπισμό της πρώτης εγγραφής με την τιμή και μετά σάρωση των εγγραφών που την ικανοποιούν. Με τις τυπικές εκτιμήσεις κόστους: [ \left\lceil \log_2 B\right\rceil+\left\lceil \frac{s}{f}\right\rceil-1 = \left\lceil \log_2 256\right\rceil+\left\lceil \frac{64}{64}\right\rceil-1 =8+1-1=8. ] Άρα απαιτούνται περίπου \(8\) προσπελάσεις μπλοκ.
- Για την επιλογή \(\sigma_{\text{IDΣχολείου}=\text{'3ο Λύκειο Πατρών'}}(\text{ΚΑΘΗΓΗΤΗΣ})\) με πρωτεύον ευρετήριο στο \(\text{IDΣχολείου}\) και fan-out \(=4\):
a. Το πρωτεύον ευρετήριο είναι αραιό και έχει μία καταχώριση ανά μπλοκ δεδομένων, άρα \(256\) καταχωρίσεις. Το πλήθος των επιπέδων είναι [ \left\lceil \log_{4} 256\right\rceil=4, ] αφού \(4^4=256\). Πράγματι: φύλλα \(256/4=64\), επόμενο επίπεδο \(64/4=16\), επόμενο \(16/4=4\), ρίζα \(4/4=1\), δηλαδή \(4\) επίπεδα συνολικά.
b. Η επιλεκτικότητα είναι [ s=\frac{n}{V(\text{IDΣχολείου})}=\frac{16384}{128}=128 ] εγγραφές. Αυτές καταλαμβάνουν [ \left\lceil \frac{s}{f}\right\rceil=\left\lceil \frac{128}{64}\right\rceil=2 ] μπλοκ δεδομένων. Επειδή πρόκειται για πρωτεύον ευρετήριο με ισότητα σε μη-κλειδί, το κόστος είναι [ h_i+\left\lceil \frac{s}{f}\right\rceil=4+2=6 ] προσπελάσεις μπλοκ.