Βάσεις Δεδομένων — Φεβρουάριος 2022 (Θέμα 4)¶
Μεταγραφή του Θέματος 4 από Screenshot_4.jpg.
Screenshot_4.jpg¶
Θέμα 4: Οργάνωση Αρχείων [30 μονάδες]
Ένα αρχείο έχει \(r=65536\) εγγραφές του τύπου Υπάλληλος με σταθερό μήκος. Κάθε εγγραφή έχει τα ακόλουθα πεδία: * ΑΦΜ (4 bytes) * ΟΝΟΜΑ (20 bytes) * ΕΠΩΝΥΜΟ (20 bytes ) * ΘΕΣΗ (15 bytes) * ΗΛΙΚΙΑ (2 bytes) * Ένα επιπλέον byte χρησιμοποιείται ως σημάδι διαγραφής
Το αρχείο είναι αποθηκευμένο σε δίσκο με τα εξής χαρακτηριστικά * Μέγεθος μπλοκ \(B=512\text{ byte}\)
Οι εγγραφές είναι ταξινομημένες στον δίσκο με βάση το πρωτεύον κλειδί.
Ερωτήσεις: 1. Υπολογίστε τον παράγοντα ομαδοποίησης bfr (blocking factor) για το συγκεκριμένο αρχείο. 2. Ποιος είναι ο απαιτούμενος αριθμός block προκειμένου να αποθηκευθεί το σύνολο των εγγραφών του αρχείου, υποθέτοντας μη εκτεινόμενη οργάνωση; 3. Ας υποθέσουμε ότι το αρχείο μας είναι διατεταγμένο και επιθυμούμε να πραγματοποιήσουμε κάποια αναζήτηση. Ποιος είναι ο απαιτούμενος αριθμός προσπελάσεων μπλοκ στον δίσκο για να βρεθεί η ζητούμενη εγγραφή για την μέση περίπτωση; 4. Εάν υποθέσουμε ότι δεικτοδοτούμε τα δεδομένα χρησιμοποιώντας ένα πολυεπίπεδο ευρετήριο με παράγοντα διακλάδωσης (fan-out) \(\text{bfr}_i\) (που θα πρέπει να υπολογίσετε), πόσα επίπεδα απαιτούνται ώστε να δεικτοδοτηθεί το σύνολο των εγγραφών με δεδομένο ότι το μήκος δείκτη block που θα χρησιμοποιηθεί είναι 4 bytes;
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2022-02¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 4¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη
Μέγεθος εγγραφής: \(R=4+20+20+15+2+1=62\) bytes. 1. \(bfr=\lfloor 512/62\rfloor=\lfloor 8{,}26\rfloor=\) 8. 2. \(b=\lceil 65536/8\rceil=\) 8192 μπλοκ. 3. Διατεταγμένο αρχείο, δυαδική αναζήτηση: \(\lceil\log_2 8192\rceil=\) 13 προσπελάσεις. 4. Εγγραφή ευρετηρίου = τιμή κλειδιού + δείκτης. Το κλειδί είναι ο ΑΦΜ (4 bytes), ο δείκτης 4 bytes ⇒ 8 bytes. Fan-out: \(bfr_i=\lfloor 512/8\rfloor=\) 64. - Πρωτεύον (αραιό) ευρετήριο, μία εγγραφή ανά μπλοκ δεδομένων: 1ο επίπεδο \(8192\) εγγραφές ⇒ \(\lceil 8192/64\rceil=128\) μπλοκ· 2ο επίπεδο: 128 εγγραφές ⇒ 2 μπλοκ· 3ο επίπεδο: 2 εγγραφές ⇒ 1 μπλοκ (ρίζα). - (Αν ήταν πυκνό: \(65536\to1024\to16\to1\), επίσης 3.)
Απαιτούνται 3 επίπεδα (τύπος: \(\lceil\log_{64}8192\rceil=3\)). Άρα μια αναζήτηση κοστίζει \(3+1=4\) προσπελάσεις.