Συστήματα Διαχείρισης Μεγάλων Δεδομένων (πρώην Βάσεις 2) — Φεβρουάριος 2021¶

Μεταγραφή από το κείμενο του February_2021.pdf (σελίδες 1–2).

February_2021.pdf¶

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ ΠΟΛΥΤΕΧΝΙΚΗ ΣΧΟΛΗ ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ

ΒΑΣΕΙΣ ΔΕΔΟΜΕΝΩΝ ΙI¶

ΚΑΘΗΓΗΤΗΣ : Β. ΜΕΓΑΛΟΟΙΚΟΝΟΜΟΥ

ΟΝΟΜΑΤΕΠΩΝΥΜΟ: __________________________________________________

ΑΜ: ________________________ ΕΤΟΣ: ___________________________________

Θέμα 1^ο Γενικές ερωτήσεις (30%)¶

Ποια είναι τα πλεονεκτήματα των ευρετηρίων με την χρήση B-trees σε σχέση με τα ευρετήρια που χρησιμοποιούν κατακερματισμό; (10 μονάδες)
Γιατί η μέθοδος των space filling curves (SFC) είναι σημαντική στην δεικτοδότηση χωρικών και γενικότερα πολυδιάστατων δεδομένων; Περιγράψετε δύο γνωστούς τύπους καμπυλών. Αναφέρετε έναν τρόπο αξιολόγησης μιας SFC. (10 μονάδες)
Συμπληρώστε τον παρακάτω πίνακα δηλώνοντας με Χ την συμμετοχή κάθε γραμμής στην αντίστοιχη στήλη. (10 μονάδες)

	OLTP	OLAP
Μικρής διάρκειας συναλλαγές
Σύνθετα ερωτήματα
επαναλαμβανόμενες ενέργειες
Μεγάλης διάρκειας ερωτήματα
διερευνητικά ερωτήματα

Θέμα 2^ο Βελτιστοποίηση Επερωτήσεων (30%)¶

Θεωρείστε τη σχέση:

GAMES (Title, Price, Publisher, Platform, Description)¶

και τα ακόλουθα χαρακτηριστικά:

NGAMES = 32768 εγγραφές FGAMES = 64 εγγραφές ανά μπλοκ V (Price, GAMES) = 512 διακριτές εγγραφές V (Platform, GAMES) = 16 διακριτές εγγραφές

V (Publisher, GAMES) = 64 διακριτές εγγραφές

Για τον υπολογισμό της επιλεκτικότητας (selection cardinality) θεωρείστε ότι έχουμε ομοιόμορφη κατανομή τιμών.

A. Θεωρείστε την πράξη επιλογής σTitle = ‘Pacman’(GAMES)
Βρείτε το πλήθος των προσπελάσεων σε αριθμό μπλοκ (στη μέση περίπτωση), αν εφαρμόσουμε σειριακή αναζήτηση.
Αν το αρχείο που περιέχει τις εγγραφές είναι διατεταγμένο ως προς το πεδίο Title , ποιο είναι το αντίστοιχο πλήθος προσπελάσεων;
B. Θεωρήστε την πράξη επιλογής σPublisher = ‘EA Sports’(GAMES)
Βρείτε το πλήθος των προσπελάσεων σε αριθμό μπλοκ, αν εφαρμόσουμε ακολουθιακή σάρωση.
Αν το αρχείο είναι διατεταγμένο ως προς το πεδίο Publisher , ποιο είναι το πλήθος των προσπελάσεων σε αριθμό μπλοκ;

Θέμα 3^ο Δοσοληψίες (20%)¶

Έστω το χρονοπρόγραμμα:

S1: W1(X); R2(Y); R3(X); W1(Y); W2(X); R4(Y); R4(X);¶

Όπου:

Ri(X): η δοσοληψία Ti διαβάζει (READ) το στοιχείο X και Wi(X): η δοσοληψία Ti γράφει (WRITE) το στοιχείο X

Είναι το χρονοπρόγραμμα σειριοποιήσιμο; Να δικαιολογήσετε την απάντησή σας.
Ακολουθεί το χρονοπρόγραμμα το πρωτόκολλο κλειδώματος δύο φάσεων (two phase locking); Να δικαιολογήσετε την απάντησή σας.

Θέμα 4^ο Indexing (20%)¶

Να σχεδιάσετε το point quad-tree που προκύπτει από τη διαδοχική εισαγωγή των παρακάτω σημείων (με συντεταγμένες που δίνονται στις παρενθέσεις):

A (5, 7)
B (8, 9)
C (6, 4)
D (2, 5)
E (7, 8)
F (4, 1)

Καλή επιτυχία!

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2021-02.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): February_2021_1.pdf, q-opt.jpg, Screenshot_34.png, 20210630_174418.jpg

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: χειρόγραφες λύσεις φοιτητή, φωτογραφίες κοινοποιημένες στο Discord (2021-06)

Προσοχή

Θέμα 2, Α2: γράφεται «log2(br) = 2.7 ≃ 3», αλλά log2(512) = 9 (br = 512 όπως στο A1). Η τιμή 2.7 δεν αντιστοιχεί στον τύπο. Θέμα 2, Β2 (q-opt.jpg): ο λογάριθμος υπολογίζεται ως log(64) = 1,8 (δεκαδικός λογάριθμος). Με log2(64) = 6 ο τύπος δίνει 6 + 8 - 1 = 13 προσπελάσεις, όχι 8,8 ≃ 9. Στο Discord (2021-06-30) σχολιάζεται ότι χρησιμοποιήθηκε λογάριθμος με βάση 10. Θέμα 2, Β2 (Screenshot_34.png): γράφεται «Log2(V(Publisher,GAMES)) = 15», αλλά log2(64) = 6· το αποτέλεσμα 22 δεν είναι συνεπές με τον τύπο. Η διαφορά από το q-opt.jpg (9 προσπελάσεις) δείχνει ότι οι δύο φοιτητικές λύσεις διαφωνούν. Θέμα 4 (20210630_174418.jpg): το σχήμα της φωτογραφίας είναι συνεπές με τη σειρά εισαγωγής A(5,7), B(8,9), C(6,4), D(2,5), E(7,8), F(4,1). Ο κόμβος του SW τμήματος της ρίζας A φέρει την ονομασία «P» στη φωτογραφία, ενώ το σημείο της εκφώνησης στη θέση αυτή είναι το D(2,5)· η ονομασία δεν επαληθεύεται από το κείμενο.

Λύσεις (φοιτητικές) — Φεβρουάριος 2021¶

Λύσεις φοιτητή, όχι επίσημο κλειδί. Θέμα 2 (q-opt.jpg, Screenshot_34.png) και Θέμα 4 (20210630_174418.jpg). Η μεταγραφή είναι αυτούσια από τα βοηθητικά αρχεία. Δεν έχουν ελεγχθεί από τον διδάσκοντα.

q-opt.jpg¶

Θέμα 2, Φεβρουαρίου 2021

A1) \(br = \frac{nr}{fr} = 512\)

Avg. Case: #προσπελάσεων = \(\frac{br}{2} = 256\)

A2) Το Title είναι κλειδί άρα: #προσπελάσεων = \(\log_2(br) = 2.7 \simeq 3\)

B1) \(br = \frac{nr}{fr} = 512\) προσπελάσεις

B2) Το Publisher είναι απλό γνώρισμα: \(SC(\text{Publisher},\text{GAMES}) = \frac{nr}{V(\text{Publisher},\text{GAMES})} = 512\)

\(b(\text{Publisher},\text{GAMES}) = \log(V(\text{Publisher},\text{GAMES})) + \frac{SC(\text{Publisher},\text{GAMES})}{fr} - 1 = 1,8 + 8 - 1 = 8,8 \simeq 9\) προσπελάσεις

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

Screenshot_34.png¶

\(\text{Πλήθος προσπελάσεων} = \text{Log2}(V(\text{Publisher},\text{GAMES}) + SC(\text{Publisher},\text{GAMES})/\text{Fgames} - 1 = 15 + 8 - 1 = 22\)

20210630_174418.jpg¶

[Σχήμα: χειρόγραφο δέντρο quadtree. Ρίζα ο κόμβος A με τέσσερα τμήματα NW | SW | NE | SE. Από το τμήμα SW βέλος προς τον κόμβο P, από το τμήμα NE βέλος προς τον κόμβο B, και από το τμήμα SE βέλος προς τον κόμβο C (χωρίς υποδέντρο). Ο κόμβος P έχει τμήματα NW | SW | NE | SE και από το τμήμα SE βέλος προς τον κόμβο F. Ο κόμβος B έχει τμήματα NW | SW | NE | SE και από το τμήμα SW βέλος προς τον κόμβο E.]

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή