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

Μεταγραφή από τις φωτογραφίες 1687860947197.jpg (πρώτη σελίδα) και 1687860947170.jpg (δεύτερη σελίδα).

1687860947197.jpg¶

Θέμα 1º Γενικές ερωτήσεις (40%)

Αναφέρετε τις βασικές διαφοροποιήσεις μεταξύ των DSMSs (Data Stream Management Systems) και των DBMSs. (13 μονάδες)
Ποιές είναι οι διαφορές της HBASE με τα RDBMS? (13 μονάδες)
Αναφέρετε τις βασικές διαφορές των μοντέλων κατανομής δεδομένων Sharding και Replication, περιγράφοντας συνοπτικά τον τρόπο διαμερισμού των δεδομένων που υποστηρίζουν, τους βασικούς στόχους που προσπαθούν να επιτύχουν τα μοντέλα αυτά, και τον τρόπο με τον οποίο επιτυγχάνονται. (14 μονάδες).

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

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

ΦΟΙΤΗΤΗΣ(Κωδικός, Όνομα, Επώνυμο, ID_Τμήματος)

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

\(n_{\text{ΦΟΙΤΗΤΗΣ}} = 4000\) εγγραφές
\(f_{\text{ΦΟΙΤΗΤΗΣ}} = 20\) εγγραφές ανά μπλοκ
\(V(\text{Όνομα}, \text{ΦΟΙΤΗΤΗΣ}) = 128\)
\(V(\text{Επώνυμο}, \text{ΦΟΙΤΗΤΗΣ}) = 50\)
\(V(\text{ID\_Τμήματος}, \text{ΦΟΙΤΗΤΗΣ}) = 15\)

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

A. Θεωρήστε την πράξη επιλογής \(\sigma_{\text{Κωδικός} = \text{'534'}}\) (ΦΟΙΤΗΤΗΣ)

1. Βρείτε το πλήθος των προσπελάσεων σε αριθμό μπλοκ (στη μέση περίπτωση), αν εφαρμόσουμε σειριακή αναζήτηση.

2. Αν το αρχείο που περιέχει τις εγγραφές είναι διατεταγμένο ως προς το πεδίο Κωδικός, ποιο είναι το αντίστοιχο πλήθος προσπελάσεων;

B. Θεωρήστε την πράξη επιλογής \(\sigma_{\text{Επώνυμο} = \text{'Μητρόπουλος'}}\) (ΦΟΙΤΗΤΗΣ)

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

1687860947170.jpg¶

Βρείτε το πλήθος των προσπελάσεων σε αριθμό μπλοκς, αν εφαρμόσουμε ακολουθιακή σάρωση.
Αν το αρχείο είναι διατεταγμένο ως προς το πεδίο Επώνυμο, ποιο είναι το πλήθος προσπελάσεων σε αριθμό μπλοκς;

Γ. Θεωρήστε την πράξη επιλογής \(\sigma_{\text{Όνομα} = \text{'Ανδρέας'}}(\text{ΦΟΙΤΗΤΗΣ})\). Ας υποθέσουμε ότι χρησιμοποιούμε ως δομή δεικτοδότησης ένα πρωτεύον (primary) ευρετήριο πάνω στο πεδίο Όνομα, με fan-out = 4.

Βρείτε το πλήθος των επιπέδων του ευρετηρίου.
Ποιο είναι το πλήθος των προσπελάσεων σε αριθμό μπλοκς για την απάντηση του παραπάνω ερωτήματος;

Θέμα 3ο: Χωρικές Δομές Δεδομένων (30%)

Γιατί η μέθοδος των space filling curves (SFC) είναι σημαντική στην δεικτοδότηση χωρικών και γενικότερα πολυδιάστατων δεδομένων; Περιγράψετε δύο γνωστούς τύπους καμπυλών. (10 μονάδες)
Για το σύνολο δεδομένων A(8, 2) B(5, 4), C(3, 3), D(4, 7), E(7, 5), F(9, 6) σχεδιάστε το point Quadtree εισάγοντας τα σημεία με την σειρά που αναφέρονται (10 μονάδες)
Για το ίδιο σύνολο δεδομένων θεωρώντας το στατικό

a. Σχεδιάστε στην κόλλα των θεμάτων τα βέλτιστα ελάχιστα περιοριστικά ορθογώνια (optimal minimum bounding rectangles) που αντιστοιχούν σε R-tree με fan-out=3 προκειμένου να δεικτοδοτηθούν όλα τα δεδομένα. Να δικαιολογήσετε την απάντησή σας. (5 μονάδες).

b. Σχεδιάστε το αντίστοιχο R-tree που προκύπτει. (5 μονάδες)

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

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

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2023-02¶

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

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

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

DSMSs έναντι DBMSs:
Τα DBMS διαχειρίζονται αποθηκευμένα, πεπερασμένα και επίμονα δεδομένα, με τυχαία προσπέλαση και ad-hoc/one-time ερωτήματα.
Τα DSMS διαχειρίζονται συνεχείς ροές δεδομένων (ενδεχομένως άπειρες), με δεδομένα που φτάνουν με σειρά άφιξης και επεξεργάζονται μία φορά (one-pass).
Στα DSMS κυριαρχούν συνεχή ερωτήματα (continuous queries), παράθυρα (sliding/tumbling windows), προσεγγιστικές απαντήσεις/synopses, περιορισμένη μνήμη, απαιτήσεις πραγματικού χρόνου, QoS και τεχνικές όπως load shedding/backpressure.
Τα DBMS στοχεύουν κυρίως σε ακρίβεια, ACID και αποθήκευση σε δίσκο· τα DSMS σε άμεση απόκριση και επεξεργασία ροών.
HBase έναντι RDBMS:
HBase: NoSQL, κατανεμημένη αποθήκευση key-value/column-family πάνω σε HDFS, ευέλικτο και αραιό σχήμα, δεδομένα ταξινομημένα κατά row key, αυτόματο sharding/region splitting, replication, οριζόντια κλιμάκωση. Δεν προσφέρει πλήρες SQL, joins και καθολικές ACID συναλλαγές πολλών γραμμών.
RDBMS: σχεσιακό μοντέλο, σταθερό σχήμα, SQL, joins, περιορισμοί ακεραιότητας, ACID συναλλαγές και συνήθως κάθετη κλιμάκωση.
Sharding έναντι Replication:
Sharding: οριζόντιος διαμερισμός των δεδομένων σε διαφορετικούς κόμβους, π.χ. με range/hash partitioning. Κάθε shard περιέχει διαφορετικό υποσύνολο δεδομένων. Στόχος: κλιμάκωση χωρητικότητας, κατανομή φόρτου, παράλληλη επεξεργασία. Επιτυγχάνεται με συνάρτηση διαμερισμού, δρομολόγηση ερωτημάτων, rebalancing και κατανεμημένες συναλλαγές.
Replication: αντίγραφα των ίδιων δεδομένων σε πολλούς κόμβους. Στόχος: διαθεσιμότητα, ανοχή βλαβών, κλιμάκωση αναγνώσεων, μείωση καθυστέρησης. Επιτυγχάνεται με master-slave/multi-master, quorum/consensus και αντιγραφή logs, με συμβιβασμούς συνέπειας. Τα δύο μοντέλα συχνά συνδυάζονται.

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

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Πλήθος μπλοκ της σχέσης:
[ b=\left\lceil \frac{n_{\text{ΦΟΙΤΗΤΗΣ}}}{f_{\text{ΦΟΙΤΗΤΗΣ}}}\right\rceil =\left\lceil \frac{4000}{20}\right\rceil=200. ]

Α. Για την \(\sigma_{\text{Κωδικός}=\text{'534'}}(\text{ΦΟΙΤΗΤΗΣ})\), θεωρώ ότι το πεδίο Κωδικός είναι μοναδικό κλειδί, άρα η επιλεκτικότητα είναι \(SC=1\).

Με σειριακή αναζήτηση, στη μέση περίπτωση απαιτούνται περίπου
[ \frac{b}{2}=\frac{200}{2}=100 ] μπλοκ (με σύμβαση \((b+1)/2\) περίπου \(101\)).
Αν το αρχείο είναι διατεταγμένο ως προς Κωδικό, εφαρμόζεται δυαδική αναζήτηση: [ \left\lceil \log_2 200\right\rceil=8 ] προσπελάσεις μπλοκ.

Β. Για \(\sigma_{\text{Επώνυμο}=\text{'Μητρόπουλος'}}(\text{ΦΟΙΤΗΤΗΣ})\):
[ SC=\frac{n}{V(\text{Επώνυμο})}=\frac{4000}{50}=80 \text{ εγγραφές}. ]

Με ακολουθιακή σάρωση χωρίς ταξινόμηση ή ευρετήριο πρέπει να διαβαστούν όλα τα μπλοκ: [ 200 ] προσπελάσεις.
Αν το αρχείο είναι διατεταγμένο ως προς Επώνυμο, βρίσκω πρώτα με δυαδική αναζήτηση την πρώτη εμφάνιση και μετά σαρώνω τα συνεχόμενα μπλοκ με ταιριαστές εγγραφές. Τα μπλοκ που περιέχουν τις 80 εγγραφές είναι: [ \left\lceil \frac{80}{20}\right\rceil=4. ] Άρα, με τη σύμβαση ότι το πρώτο μπλοκ των ταιριασμάτων έχει ήδη προσπελαστεί από τη δυαδική αναζήτηση: [ \left\lceil \log_2 200\right\rceil+4-1=8+4-1=11 ] προσπελάσεις μπλοκ.

Γ. Για \(\sigma_{\text{Όνομα}=\text{'Ανδρέας'}}(\text{ΦΟΙΤΗΤΗΣ})\):
[ SC=\frac{n}{V(\text{Όνομα})}=\frac{4000}{128}=31.25\approx 32 \text{ εγγραφές}. ]

Πρωτεύον ευρετήριο με fan-out \(=4\) και ένα index entry ανά μπλοκ δεδομένων, άρα επίπεδο φύλλων με \(200\) entries:
[ \begin{aligned} L_1&=\left\lceil \frac{200}{4}\right\rceil=50,\ L_2&=\left\lceil \frac{50}{4}\right\rceil=13,\ L_3&=\left\lceil \frac{13}{4}\right\rceil=4,\ L_4&=\left\lceil \frac{4}{4}\right\rceil=1. \end{aligned} ] Άρα το ευρετήριο έχει \(4\) επίπεδα.
Προσπέλαση των \(4\) επιπέδων του ευρετηρίου και μετά των μπλοκ δεδομένων που περιέχουν τις ταιριαστές εγγραφές. Επειδή οι εγγραφές είναι συνεχόμενες λόγω διάταξης ως προς Όνομα: [ \left\lceil \frac{31.25}{20}\right\rceil=2 ] μπλοκ δεδομένων. Συνολικά: [ 4+2=6 ] προσπελάσεις μπλοκ (με τη συνήθη εκτίμηση χωρίς επιπλέον μπλοκ λόγω ορίου τιμής).

Θέμα 3ο: Χωρικές Δομές Δεδομένων (30%)¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια

Σημασία των space filling curves (SFC):
Οι SFC απεικονίζουν πολυδιάστατα σημεία σε μία διάσταση, διατηρώντας κατά το δυνατόν τη χωρική γειτνίαση. Έτσι μπορούν να χρησιμοποιηθούν αποδοτικοί μονοδιάστατοι δείκτες, όπως B+-trees, για χωρικά δεδομένα· ερωτήματα περιοχής μετατρέπονται σε διαστήματα τιμών και μειώνεται ο αριθμός των τυχαίων προσπελάσεων δίσκου. Δύο γνωστοί τύποι είναι:
Z-order (Morton) curve: εναλλάσσει τα δυαδικά ψηφία των συντεταγμένων.
Hilbert curve: αναδρομική καμπύλη με καλύτερη διατήρηση γειτνίασης και μικρότερο αριθμό ασυνεχειών.
Point Quadtree με άξονες \(x\) προς τα δεξιά και \(y\) προς τα πάνω. Με σειρά εισαγωγής \(A,B,C,D,E,F\), ο κόμβος \(A(8,2)\) γίνεται ρίζα. Τα παιδιά κάθε κόμβου είναι τα σημεία στα τεταρτημόρια NW, NE, SW, SE ως προς τον κόμβο. Προκύπτει:
Ρίζα: \(A(8,2)\)
- NW: \(B(5,4)\)
- NW: \(D(4,7)\)
- NE: \(E(7,5)\)
- SW: \(C(3,3)\)
- SE: κενό
- NE: \(F(9,6)\)
- SW: κενό
- SE: κενό

Δηλαδή: [ A \rightarrow \begin{cases} NW: B \rightarrow {NW:D,\; NE:E,\; SW:C}\ NE: F\ SW:\varnothing\ SE:\varnothing \end{cases} ]

Για στατικό R-tree με fan-out \(=3\), υιοθετώ τη συνήθη packed οργάνωση με μέγιστη πλήρωση των φύλλων. Τα \(6\) σημεία χωρίζονται σε δύο φύλλα των \(3\) σημείων.

a. Βέλτιστα MBRs:
- \(R_1\) για τα \(\{B(5,4),C(3,3),D(4,7)\}\): [ R_1=[3,5]\times[3,7],\quad \text{εμβαδόν}=2\cdot4=8. ] - \(R_2\) για τα \(\{A(8,2),E(7,5),F(9,6)\}\): [ R_2=[7,9]\times[2,6],\quad \text{εμβαδόν}=2\cdot4=8. ] Το συνολικό εμβαδόν είναι \(8+8=16\). Τα δύο MBR δεν επικαλύπτονται ως προς \(x\), αφού \(R_1\) έχει \(x\in[3,5]\) και \(R_2\) έχει \(x\in[7,9]\). Εναλλακτικοί χωρισμοί \(3+3\), π.χ. πάνω/κάτω, δίνουν μεγαλύτερο συνολικό εμβαδόν, άρα ο παραπάνω είναι βέλτιστος για δύο γεμάτα φύλλα.

b. Αντίστοιχο R-tree:

Root (MBR [3,9] x [2,7])
├── R1 [3,5] x [3,7]
│     ├── B(5,4)
│     ├── C(3,3)
│     └── D(4,7)
└── R2 [7,9] x [2,6]
      ├── A(8,2)
      ├── E(7,5)
      └── F(9,6)

Κάθε φύλλο έχει \(3\le\) fan-out \(=3\) εγγραφές και η ρίζα έχει \(2\le3\) παιδιά.

Σημείωση: αν ως μοναδικό κριτήριο τεθεί το ελάχιστο άθροισμα εμβαδών χωρίς υποχρέωση μέγιστης πλήρωσης των φύλλων, επιτρέπονται και τρία φύλλα των δύο σημείων με συνολικό εμβαδόν \(10\), π.χ. \(\{B,C\},\{A,E\},\{D,F\}\). Η παραπάνω απάντηση ακολουθεί τη συνήθη packed/γεμάτων-φύλλων ερμηνεία για R-tree.

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

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