Μετάβαση στο περιεχόμενο

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

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

DB2-Sept2021.pdf

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

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

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

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

ΑΜ: ________________________ ΕΤΟΣ: __________________________________

Θέμα 1 (15%)

Για το σύνολο δεδομένων A(7, 2) B(5, 4), C(2, 3), D(4, 7), E(9, 6) σχεδιάστε το point Quadtree εισάγοντας τα σημεία με την σειρά που αναφέρονται.

Θέμα 2 (10%)

Σε μια κατανεμημένη βάση δεδομένων, πότε είναι προτιμότερο να έχουμε αντίγραφα δεδομένων (replication of data) και πότε κατατεμαχισμό δεδομένων (fragmentation of data);

Θέμα 3 (10%)

Εξηγείστε γιατί οι ημιενώσεις (semijoins) θεωρούνται χρήσιμες στην βελτιστοποίηση επερωτήσεων σε κατανεμημένες βάσεις δεδομένων.

Θέμα 4 (10%)

Συμπληρώστε τον παρακάτω πίνακα δηλώνοντας με Χ την συμμετοχή κάθε γραμμής στην αντίστοιχη στήλη

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

Θέμα 5 (15%)

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

S1: R3(B);R4(A);W4(B);W3(A);R2(A);R1(B);W2(B);W1(A)

Όπου:

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

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

  1. Είναι το χρονοπρόγραμμα σειριοποιήσιμο; Να δικαιολογήσετε την απάντησή σας. (10 μονάδες).

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

Θέμα 6 (40%)

Θεωρείστε τις σχέσεις: ΛΟΓΑΡΙΑΣΜΟΣ

ΛΟΓΑΡΙΑΣΜΟΣ

ID Α.Φ.Μ._καταθέτη Υπόλοιπο

ΚΑΤΑΘΕΤΗΣ

Α.Φ.Μ. Όνομα Επώνυμο Email Τηλέφωνο

ΣΥΝΑΛΛΑΓΗ

ID Α.Φ.Μ._καταθέτη ID_λογαριασμού Ημερομηνία Ποσό

Για τις παραπάνω σχέσεις έχουμε τις εξής πληροφορίες:

  • V(ID, ΛΟΓΑΡΙΑΣΜΟΣ) = 16.384

  • V(ID, ΚΑΤΑΘΕΤΗΣ) = 8.192

  • V(Όνομα, ΚΑΤΑΘΕΤΗΣ) = 1.000

  • V(Επώνυμο, ΚΑΤΑΘΕΤΗΣ) = 20.000

  • V(ID, ΣΥΝΑΛΛΑΓΗ) = 65.536

  • fΛΟΓΑΡΙΑΣΜΟΣ =128 εγγραφές/block

  • fΚΑΤΑΘΕΤΗΣ =32 εγγραφές/block

  • fΣΥΝΑΛΛΑΓΗ =64 εγγραφές/block

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

Ερωτήσεις

Α[10%]. Έστω η πράξη επιλογής σΌνομα=’Κώστας’(ΚΑΤΑΘΕΤΗΣ)

  1. Βρείτε το πλήθος προσπελάσεων σε αριθμό block μια ακολουθιακής σάρωσης.

  2. Βρείτε το πλήθος των προσπελάσεων σε αριθμό block αν το αρχείο είναι διατεταγμένο ως προς το γνώρισμα Όνομα.

Β[10%]. Έστω η πράξη επιλογής σID=’1234’(ΛΟΓΑΡΙΑΣΜΟΣ). Ας υποθέσουμε ότι χρησιμοποιούμε αραιό ευρετήριο τύπου B-tree ως δομή δεικτοδότησης για το ID, με fan-out=64.

  • § Βρείτε το πλήθος των επιπέδων του ευρετηρίου.

  • § Βρείτε το πλήθος των προσπελάσεων σε αριθμό block.

Γ[20%]. Δίνεται το ερώτημα:

  • «Να βρείτε τα ονόματα των καταθετών που έχουν πραγματοποιήσει αναλήψεις άνω των 5.000 και έχουν κάποιο λογαριασμό με υπόλοιπο κάτω των 2.000»

  • Να εκφράσετε το παραπάνω ερώτημα σε σχεσιακή άλγεβρα.

  • Να γράψετε το πλάνο ερωτήματος (query plan) για το παραπάνω ερώτημα (δενδρική μορφή).

  • Να γράψετε 2 ισοδύναμα πλάνα για το παραπάνω ερώτημα και να σχολιάσετε την αναμενόμενη απόδοσή τους.

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

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

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

Προσοχή

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

AI λύσεις — 2021-09

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

Θέμα 1

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

Με σύμβαση ότι ο άξονας \(y\) αυξάνει προς τα πάνω, η εισαγωγή γίνεται συγκρίνοντας κάθε νέο σημείο με το τρέχον ως προς \(x\) και \(y\):

  • Το \(A(7,2)\) είναι η ρίζα.
  • \(B(5,4)\): \(x<7,\ y>2\), άρα βόρειο-δυτικό παιδί του \(A\).
  • \(C(2,3)\): ως προς \(A\) είναι βορειο-δυτικό, ως προς \(B\): \(x<5,\ y<4\), άρα νοτιο-δυτικό παιδί του \(B\).
  • \(D(4,7)\): ως προς \(A\) βορειο-δυτικό, ως προς \(B\): \(x<5,\ y>4\), άρα βορειο-δυτικό παιδί του \(B\).
  • \(E(9,6)\): \(x>7,\ y>2\), άρα βορειο-ανατολικό παιδί του \(A\).

Το δένδρο είναι: 

A(7,2)
├─ NW: B(5,4)
│   ├─ NW: D(4,7)
│   └─ SW: C(2,3)
├─ NE: E(9,6)
├─ SW: ∅
└─ SE: ∅
Αν χρησιμοποιηθεί η αντίθετη σύμβαση για τον άξονα \(y\), αλλάζουν μόνο οι ονομασίες NW/SW/NE/SE, όχι οι συγκρίσεις.

Θέμα 2

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

Replication προτιμάται όταν το φορτίο είναι κυρίως αναγνώσεις, όταν υπάρχουν πολλοί κατανεμημένοι χρήστες/κόμβοι που διαβάζουν τα ίδια δεδομένα, όταν απαιτείται υψηλή διαθεσιμότητα, ανοχή βλαβών και ταχύτερη τοπική πρόσβαση, και όταν οι ενημερώσεις είναι σχετικά σπάνιες ή το κόστος διάδοσής τους είναι αποδεκτό.

Fragmentation προτιμάται όταν μια μεγάλη σχέση έχει τοπικότητα προσπέλασης, δηλαδή διαφορετικοί κόμβοι χρησιμοποιούν διαφορετικά τμήματα (οριζόντια ή κάθετα), όταν οι ενημερώσεις αφορούν κυρίως ανεξάρτητα τμήματα, όταν επιδιώκεται παραλλελισμός και μείωση μεταφοράς δεδομένων, ή όταν το replication θα προκαλούσε υπερβολικό κόστος ενημερώσεων.

Θέμα 3

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

Οι ημιενώσεις είναι χρήσιμες γιατί επιτρέπουν να φιλτράρονται έγκαιρα οι σχέσεις με βάση μόνο τα γνωρίσματα συζεύξεως, πριν μεταφερθούν ολόκληρες οι εγγραφές. Σε κατανεμημένη βάση το κύριο κόστος είναι η επικοινωνία, οπότε μια ημιένωση \(R \ltimes S\) μπορεί να στείλει στο απομακρυσμένο site μόνο το μικρό σύνολο τιμών του join attribute και να επιστρέψει μόνο τις σχετικές πλειάδες της \(R\). Έτσι μειώνεται το μέγεθος των ενδιάμεσων σχέσεων, αποφεύγονται περιττές μεταφορές πλειάδων που δεν θα συμμετείχαν στο τελικό join και μειώνεται το συνολικό κόστος της επερώτησης.

Θέμα 4

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

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

Θέμα 5

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

Το χρονοπρόγραμμα είναι: [ S_1: R_3(B);R_4(A);W_4(B);W_3(A);R_2(A);R_1(B);W_2(B);W_1(A) ]

Εξετάζουμε τις συγκρούσεις ανά στοιχείο.

Για το \(B\): [ R_3(B)\to W_4(B),\quad R_3(B)\to W_2(B),\quad W_4(B)\to R_1(B),\quad W_4(B)\to W_2(B),\quad R_1(B)\to W_2(B) ] άρα προκύπτουν ακμές: [ T_3\to T_4,\quad T_3\to T_2,\quad T_4\to T_1,\quad T_4\to T_2,\quad T_1\to T_2. ]

Για το \(A\): [ R_4(A)\to W_3(A),\quad R_4(A)\to W_1(A),\quad W_3(A)\to R_2(A),\quad W_3(A)\to W_1(A),\quad R_2(A)\to W_1(A) ] άρα: [ T_4\to T_3,\quad T_4\to T_1,\quad T_3\to T_2,\quad T_3\to T_1,\quad T_2\to T_1. ]

Στο γράφημα προτεραιοτήτων έχουμε κύκλο [ T_3\to T_4 \quad \text{και} \quad T_4\to T_3. ] Επίσης υπάρχει κύκλος \(T_1\leftrightarrow T_2\). Άρα το \(S_1\) δεν είναι σειριοποιήσιμο με βάση τη σειριοποιησιμότητα συγκρούσεων.

  1. Δεν είναι σειριοποιήσιμο, επειδή το γράφημα συγκρούσεων περιέχει κύκλο.

  2. Δεν ακολουθεί το πρωτόκολλο κλειδώματος δύο φάσεων (2PL). Κάθε χρονοπρόγραμμα που παράγεται από 2PL είναι σειριοποιήσιμο με βάση τις συγκρούσεις· αφού το \(S_1\) δεν είναι, δεν μπορεί να προέρχεται από 2PL. Επιπλέον, οι αμοιβαίες εξαρτήσεις \(T_3\to T_4\) και \(T_4\to T_3\) δείχνουν ότι δεν μπορεί να τηρηθεί μία μόνο αυξητική φάση απόκτησης κλειδαριών για όλες τις δοσοληψίες.

Θέμα 6

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

Θεωρώ πλήθος εγγραφών της \(ΚΑΤΑΘΕΤΗΣ\) ίσο με \(V(ID, ΚΑΤΑΘΕΤΗΣ)=8192\) (προφανώς εννοείται πλήθος εγγραφών/πρωτεύον κλειδί, αφού το πεδίο \(ID\) δεν εμφανίζεται στον πίνακα). Επίσης θεωρώ ομοιόμορφη κατανομή.

Α[10%]

Η σχέση \(ΚΑΤΑΘΕΤΗΣ\) έχει: [ n=8192,\qquad f=32\ \text{εγγραφές/block} ] άρα αριθμός blocks: [ b=\left\lceil \frac{8192}{32}\right\rceil=256. ]

  1. Για την επιλογή \(\sigma_{\text{Όνομα}='Κώστας'}(ΚΑΤΑΘΕΤΗΣ)\), η ακολουθιακή σάρωση διαβάζει όλα τα blocks: [ \boxed{256\ \text{block accesses}} ]

  2. Αν το αρχείο είναι διατεταγμένο ως προς το \(\text{Όνομα}\), μπορούμε να κάνουμε δυαδική αναζήτηση για την πρώτη εγγραφή με τιμή Κώστας και μετά να διαβάσουμε τις εγγραφές που ταιριάζουν. Η πληθικότητα επιλογής είναι: [ s=\frac{n}{V(\text{Όνομα},ΚΑΤΑΘΕΤΗΣ)} =\frac{8192}{1000}=8.192. ] Τα 8.192 records χωρούν σε [ \left\lceil \frac{8.192}{32}\right\rceil=1 ] block. Η δυαδική αναζήτηση σε 256 blocks κοστίζει [ \left\lceil \log_2 256\right\rceil=8 ] block accesses. Άρα: [ 8+1=9 ] και με τη συνήθη σύμβαση του βιβλίου: [ \boxed{9\ \text{block accesses}} ] (Αν η τελευταία προσπέλαση της δυαδικής αναζήτησης θεωρηθεί ότι είναι το ίδιο block με τις εγγραφές που ταιριάζουν, το κόστος μπορεί να μετρηθεί ως 8.)

Β[10%]

Για τη σχέση \(ΛΟΓΑΡΙΑΣΜΟΣ\): [ n=V(ID,ΛΟΓΑΡΙΑΣΜΟΣ)=16384,\qquad f=128. ] Άρα: [ b=\left\lceil \frac{16384}{128}\right\rceil=128\ \text{data blocks}. ]

Σε αραιό B-tree index πάνω στο \(ID\), έχουμε μία καταχώρηση ανά data block, άρα: [ N_{\text{index entries}}=128. ] Με fan-out \(p=64\), κάθε κόμβος μπορεί να έχει μέχρι \(p-1=63\) κλειδιά. Επειδή \(128>63\), χρειάζονται τουλάχιστον 2 επίπεδα: [ \left\lceil \log_{64}(128+1)\right\rceil=2. ] Δηλαδή το ευρετήριο έχει 2 επίπεδα: ρίζα και φύλλα.

Για αναζήτηση ισότητας στο μοναδικό κλειδί \(ID='1234'\), διαβάζουμε: - 2 blocks του ευρετηρίου, - 1 block δεδομένων.

Άρα: [ \boxed{3\ \text{block accesses}} ] (Αν η ρίζα είναι μόνιμα στη μνήμη, τότε 2.)

Γ[20%]

Θεωρώ ότι οι «αναλήψεις άνω των 5.000» αναπαρίστανται στη \(ΣΥΝΑΛΛΑΓΗ\) με συνθήκη \(\text{Ποσό}>5000\). Αν υπήρχε επιπλέον γνώρισμα τύπου συναλλαγής, θα προσέθετα και έλεγχο τύπου «ανάληψη».

Χρησιμοποιώ ψευδώνυμα: [ K=ΚΑΤΑΘΕΤΗΣ,\quad L=ΛΟΓΑΡΙΑΣΜΟΣ,\quad S=ΣΥΝΑΛΛΑΓΗ. ]

  1. Σε σχεσιακή άλγεβρα: [ \Pi_{K.\text{Όνομα}}\left( K \bowtie_{K.\text{ΑΦΜ}=L.\text{ΑΦΜ_καταθέτη}} \sigma_{\text{Υπόλοιπο}<2000}(L) \bowtie_{K.\text{ΑΦΜ}=S.\text{ΑΦΜ_καταθέτη}} \sigma_{\text{Ποσό}>5000}(S) \right) ] Το αποτέλεσμα δίνει τα ονόματα καταθετών για τους οποίους υπάρχει τουλάχιστον ένας λογαριασμός με υπόλοιπο μικρότερο των 2.000 και τουλάχιστον μία συναλλαγή/ανάληψη με ποσό μεγαλύτερο των 5.000. Δεν απαιτείται ο ίδιος λογαριασμός να ικανοποιεί και τις δύο συνθήκες.

Αν ζητείται η ανάληψη να γίνεται από τον ίδιο λογαριασμό με υπόλοιπο μικρότερο των 2.000, προσθέτουμε τη συνθήκη: [ L.ID=S.ID_λογαριασμού. ]

  1. Ένα δενδρικό πλάνο με ώθηση των επιλογών πριν από τα join είναι: 

                           Π_{K.Όνομα}
                            |
                 ⋈_{K.ΑΦΜ = S.ΑΦΜ_καταθέτη}
                      /                 \
       ⋈_{K.ΑΦΜ = L.ΑΦΜ_καταθέτη}      σ_{Ποσό>5000}(S)
              /              \
        K (ΚΑΤΑΘΕΤΗΣ)      σ_{Υπόλοιπο<2000}(L)

  2. Δύο ισοδύναμα πλάνα:

Πλάνο 2 — τομές συνόλων ΑΦΜ: [ P_1=\Pi_{\text{ΑΦΜ}}\left(\sigma_{\text{Υπόλοιπο}<2000}(L)\right) ] [ P_2=\Pi_{\text{ΑΦΜ_καταθέτη}}\left(\sigma_{\text{Ποσό}>5000}(S)\right) ] (μετονομάζουμε κατάλληλα ώστε και τα δύο να έχουν γνώρισμα ΑΦΜ), έπειτα: [ I=P_1\cap P_2 ] και τελικά: [ \Pi_{K.\text{Όνομα}}\left(K\bowtie_{K.\text{ΑΦΜ}=I.\text{ΑΦΜ}} I\right). ] Το πλάνο αυτό είναι συνήθως αποδοτικό όταν και οι δύο επιλογές είναι αρκετά εκλεκτικές, γιατί υπολογίζει πρώτα μικρά σύνολα ΑΦΜ που ικανοποιούν τις δύο συνθήκες και μετά κάνει αναζήτηση στη \(ΚΑΤΑΘΕΤΗΣ\) μόνο για αυτά.

Πλάνο 3 — διαδοχικές ημιενώσεις: [ \Pi_{K.\text{Όνομα}}\left( \left( K\ltimes_{K.\text{ΑΦΜ}=L.\text{ΑΦΜ_καταθέτη}} \sigma_{\text{Υπόλοιπο}<2000}(L) \right) \ltimes_{K.\text{ΑΦΜ}=S.\text{ΑΦΜ_καταθέτη}} \sigma_{\text{Ποσό}>5000}(S) \right). ] Εδώ φιλτράρονται σταδιακά οι καταθέτες, χωρίς να παραχθούν μεγάλα καρτεσιανά γινόμενα. Είναι καλό όταν μία από τις δύο συνθήκες είναι πολύ εκλεκτική. Αν καμία από τις δύο επιλογές δεν είναι εκλεκτική, τότε ένα πλάνο με hash join στη \(ΚΑΤΑΘΕΤΗΣ\) και στις φιλτραρισμένες σχέσεις μπορεί να είναι προτιμότερο, ανάλογα με τα διαθέσιμα ευρετήρια και το μέγεθος των ενδιάμεσων αποτελεσμάτων.

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

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