ΑΡΧΕΙΑ ΜΕ ΚΑΤΑΛΟΓΟ -ΓΡΑΜΜΙΚΟΙ ΚΑΤΑΛΟΓΟΙ
6.1 Η έννοια του καταλόγου
Στις τελευταίες σελίδες κάθε βιβλίου υπάρχει ένας κατάλογος που περιλαμβάνει μια λίστα από θέματα (κλειδιά - keys) και τους αριθμούς των σελίδων που αναφέρονται αυτά τα θέματα (πεδία αναφοράς -reference fields).
Όλοι οι κατάλογοι βασίζονται στην ίδια λογική. Θα ξεκινήσουμε με τον απλούστερο τύπο αρχείου κατάλογου, τον απλό κατάλογο (simple index) ή γραμμικό κατάλογο (linear index) που είναι και η απλούστερη οργάνωση αρχείου με κατάλογο. Ξεκινάμε αυτή την οργάνωση αρχείου καταλόγου για να δείξουμε ότι αν και βασίζεται σε απλή έννοια εντούτοις αποτελεί ένα πολύ ισχυρό εργαλείο.
Ας ξαναγυρίσουμε στο παράδειγμα με τον κατάλογο σ’ ένα βιβλίο. Μέσω του καταλόγου ενός βιβλίου μπορούμε να εντοπίσουμε εύκολα ένα θέμα. Αν επιχειρήσουμε να αναζητήσουμε ένα θέμα χωρίς κατάλογο το πιθανότερο είναι ότι δεν θα το εντοπίσουμε ή δεν θα εντοπίσουμε όλες τις αναφορές γι’ αυτό το θέμα.
Ας φαντασθούμε τι θα συνέβαινε αν εφαρμόζαμε την οργάνωση “ταξινομημένου αρχείου” του προηγούμενου κεφαλαίου. Θα διαθέταμε ένα αρχείο όπου οι λέξεις ενός βιβλίου θα εμφανίζονταν σε αλφαβητική σειρά κι έτσι εφαρμόζοντας τη μέθοδο BS θα μπορούσαμε να βρούμε οποιοδήποτε θέμα ευκολότερα, αλλά αυτό θα ήταν καταστροφικό για το νόημα του βιβλίου. Βέβαια αυτό είναι ένα θέμα με εμφανή δόση υπερβολής αλλά μέσω αυτού γίνεται αντιληπτή η δύναμη και η σημασία του καταλόγου. Έτσι θα μπορούσαμε να πούμε ότι μέσω του αρχείου καταλόγου επιτυγχάνουμε τη διάταξη των εγγραφών ενός αρχείου χωρίς να χρειάζεται να αναδιατάξουμε πραγματικά τις εγγραφές του αρχείου.
Ας θεωρήσουμε ένα άλλο παράδειγμα. Αφορά στην αναζήτηση βιβλίων στη βιβλιοθήκη. Συχνά αναζητούμε ένα βιβλίο με διάφορους τρόπους, π.χ. με βάση τον συγγραφέα, τον τίτλο ή με βάση τη θεματική περιοχή. Ένας τρόπος είναι να έχουμε 3 αντίγραφα του βιβλίου τοποθετημένα σε 3 διαφορετικές βιβλιοθήκες. Στην 1η τοποθετούνται με βάση τον συγγραφέα, στη 2η με βάση το τίτλο και στη 3η με βάση το θέμα. Βεβαίως και σ’ αυτό το παράδειγμα υπάρχει η δόση της υποβολής αλλά και πάλι γίνεται φανερό πόσο πλεονεκτεί η ύπαρξη του αρχείου καταλόγου.
6.2 Απλός κατάλογος με σειριακό - χρονολογικό αρχείο
Ας υποθέσουμε ότι διαθέτουμε μια συλλογή δίσκων μουσικής και επιθυμούμε να διατηρήσουμε σ’ ένα αρχείο τα στοιχεία των δίσκων. Οι οντότητες που αφορούν σ’ ένα δίσκο φαίνονται στην εικόνα 6.1.
Εικόνα 6.1
Στην εικόνα 6.2. φαίνεται πως είναι το αρχείο στο οποίο θα αποθηκεύσουμε πληροφορίες που αναφέρονται σε δίσκους μουσικής. Το αρχείο θα το ονομάσουμε datafile.
Eικόνα 6.2 : Περιεχόμενα του αρχείου datafile
Ας υποθέσουμε ότι επιλέγουμε ως πρωτεύον κλειδί ένα συνδυασμό της “εταιρείας παραγωγής” (Label) και του “αριθμού ταυτότητας” (id). Αυτός ο συνδυασμός προφανώς είναι μια καλή επιλογή πρωτεύοντος κλειδιού μια και σίγουρα δημιουργεί ένα μοναδικό κλειδί. Ονομάζουμε αυτό το κλειδί “ετικέτα-ταυτότητα” (Label_id).
Ποια μέθοδος θα μπορούσε να χρησιμοποιηθεί για να έχουμε γρήγορη προσπέλαση σε οποιαδήποτε εγγραφή. Θα μπορούσε να χρησιμοποιηθεί η οργάνωση ταξινομημένου αρχείου και η εφαρμογή της μεθόδου BS. Μια λύση θα ήταν αυτή. Μια όμως άλλη εναλλακτική λύση προς αυτή θα ήταν η χρήση αρχείου καταλόγου. Εκτός από το αρχείο δεδομένων, datafile, που θα περιλαμβάνει εγγραφές με τα παραπάνω 5 πεδία, παράλληλα θα διατηρούμε και το αρχείο κατάλογος, indexfile. Κάθε εγγραφή του αρχείου καταλόγου θα περιλαμβάνει το πρωτεύον κλειδί και το πεδίο αναφορά (reference key) που δίνει τη διεύθυνση δηλαδή τον αριθμό εγγραφής στο αρχείο δεδομένων. Στην εικόνα 6.3 μπορούμε να δούμε το αρχείο δεδομένων με ένα αρχείο κατάλογο.
Eικόνα 6.3 Αρχείο κατάλογος (indexfile) μαζί με το αρχείο δεδομένων(datafile)
Ετσι στο παράδειγμά μας, στο αρχείο κατάλογο Indexfile η εγγραφή με τιμή κλειδιού ANG3797 έχει αντίστοιχα τιμή πεδίου αναφοράς 3, που σημαίνει ότι η εγγραφή με αριθμό εγγραφής 3 στο αρχείο δεδομένων, Datafile, περιέχει την πλήρη περιγραφή κάθε δίσκου μουσικής.
Θα πρέπει να σημειώσουμε ότι το αρχείο κατάλογος είναι ταξινομημένο ως προς το κλειδί, ενώ το αρχείο δεδομένων δεν είναι. Ακόμη ότι σε κάθε εγγραφή του αρχείου καταλόγου αντιστοιχεί και μια εγγραφή του αρχείου δεδομένων. Το αρχείο δεδομένων οργανώνεται ως σειριακό-χρονολογικό αρχείο. Έτσι με βάση το παραπάνω παράδειγμα μπορούμε να πούμε ότι το αρχείο κατάλογος (index) είναι μια δομή δεδομένων η οποία περιέχει μια συνάρτηση της οποίας η παράμετρος είναι το κλειδί και η τιμή της συνάρτησης είναι ο αριθμός εγγραφής στο αρχείο δεδομένων.
Επανερχόμενοι στην οργάνωση αρχείου με κατάλογο έχουμε να εντοπίσουμε τα εξής:
Στην οργάνωση αυτή χρειαζόμαστε 2 αρχεία, το αρχείο δεδομένων και το αρχείο κατάλογος. Η επεξεργασία του αρχείου κατάλογος είναι ευκολότερη αφού είναι ταξινομημένο και μικρότερο σε μέγεθος.
Το αρχείο κατάλογος προσπαθούμε να το διατηρήσουμε όσο γίνεται μικρότερο.
OPEN
READ_NEXT
READ_DIRECT
APPEND (WRITE_DIRECT)
UPDATE
CLOSE
EOF
VALID
Η εφαρμογή του B.S. απαιτεί το αρχείο να είναι ταξινομημένο. Η ταξινόμηση όμως αρχείου είναι πολυέξοδη διαδικασία ακόμη κι αν η ταξινόμηση γίνει στη RAM και μετά αντιγράφεται στο δίσκο.
Ένα πλεονέκτημα του αρχείου καταλόγου είναι ότι η προσθήκη εγγραφής μπορεί να γίνει ταχύτερα σε σχέση με τα ταξινομημένα αρχεία. Βέβαια όσο το αρχείο κατάλογος είναι μικρό μπορούμε να το κρατάμε ολόκληρο στη μνήμη. Υποθέτοντας ότι το αρχείο κατάλογος μπορεί να αποθηκευθεί στη μνήμη θεωρούμε τον πίνακα INDEX όπου μεταφέρουμε το αρχείο κατάλογο από το δίσκο στη μνήμη.
Διατηρώντας το αρχείο κατάλογο στη μνήμη είναι ταχύτερη η αναζήτηση μιας συγκεκριμένης εγγραφής με το BS και μετά απαιτείται μόνο μια εφαρμογή της READ_DIRECT. Σε αντίθεση όταν εφαρμόζουμε BS σε ταξινομημένο αρχείο τότε χρειάζεται σε κάθε βήμα του BS να εφαρμόσουμε και μια πράξη READ_DIRECT. Εκτός των 6 βασικών διαδικασιών που αναφέραμε στις προηγούμενες οργανώσεις θα αναφέρουμε και 2 επιπλέον διαδικασίες.
μεταφορά του αρχείου καταλόγου από το δίσκο στη μνήμη (πριν τη χρήση του)
αντιγραφή του αρχείου καταλόγου από τη μνήμη στο δίσκο (μετά τη χρήση του).
Mεταφορά του αρχείου καταλόγου από το δίσκο στη μνήμη (πριν τη χρήση του)
Θεωρούμε ότι το αρχείο κατάλογος είναι μικρό και χωρά στη μνήμη έτσι ορίζουμε τον πίνακα INDEX. Κάθε στοιχείο του πίνακα έχει τη δομή της εγγραφής του αρχείου καταλόγου. Εκείνο που χρειάζεται είναι η σειριακή ανάγνωση των εγγραφών του αρχείου καταλόγου και αποθήκευση κάθε εγγραφής σε κάθε στοιχείο του πίνακα.
procedure Copy _indexfile_to_memory(indexfile, n, index);
OPEN(indexfile);
i := 0;
WHILE not EOF(indexfile) DO BEGIN
READ_NEXT(indexfile, indexbuffer);
i:=i+1;
index[i]:=indexbuffer;
END;
CLOSE(indexfile);
Αντιγραφή του αρχείου καταλόγου από τη μνήμη στο δίσκο μετά τη χρήση του
Όταν ολοκληρωθεί η επεξεργασία του αρχείου κατάλογου μεταφέρουμε τα περιεχόμενα του πίνακα INDEX στο αρχείο κατάλογο. Αν μεν έχει μεταβληθεί ο πίνακας INDEX τότε αποθηκεύουμε σε νέο αρχείο κατάλογο αλλιώς δεν χρειάζεται να γίνει καμία ενημέρωση.
procedure Copy _from_memory_to_indexfile(indexfile, n, index);
OPEN(indexfile);
FOR i := 1 to n DO BEGIN
indexbuffer := index[i];
WRITE_NEXT(indexfile, indexbuffer);
END;
CLOSE(indexfile);
Είναι σημαντικό να αναφερθεί τι θα συμβεί αν δεν ολοκληρωθεί η μεταφορά του πίνακα INDEX στο αρχείο κατάλογο ή αν δεν γίνει σωστά. Η διαδικασία που εκτελεί τη μεταφορά του πίνακα στο αρχείο θα πρέπει να εγγυάται την ορθή μεταφορά αλλά και σε περίπτωση που δεν ολοκληρωθεί (διακοπή ρεύματος κτλ) να δηλώνεται με κάποιο τρόπο. Έτσι ο σχετικός αλγόριθμος θα πρέπει να περιλαμβάνει τα εξής:
Να υπάρχει ένας μηχανισμός που θα επιτρέπει στο πρόγραμμα να γνωρίζει αν το αρχείο κατάλογος είναι εκτός ημερομηνίας. Ένας τρόπος είναι να χρησιμοποιείται μια σημαία κατάστασης η οποία θα αλλάζει τιμή, πχ 1, όταν το αρχείο κατάλογος που βρίσκεται στη μνήμη άλλαξε. Η σημαία μπορεί να αποθηκεύεται στη επικεφαλίδα του αρχείου. Όταν ολοκληρωθεί η αντιγραφή του INDEX πίνακα στο δίσκο τότε η τιμή της σημαίας θα ξαναλλάζει σε 0. Έτσι όλες οι διαδικασίες που χρησιμοποιεί το αρχείο κατάλογος θα ελέγχουν τη τιμή της σημαίας πριν χρησιμοποιήσουν το αρχείο αυτό. Αν η τιμή είναι 1 τότε αυτό θα δηλώνει ότι το αρχείο δεν είναι στη σωστή κατάσταση, είναι όπως λέμε out of date.
Αν μια διαδικασία διαπιστώσει ότι το αρχείο κατάλογος είναι εκτός ημερομηνίας τότε θα πρέπει να καλεί τη διαδικασία που θα ξαναδημιουργήσει (reconstruction) το αρχείο κατάλογος από το αρχείο δεδομένων. Αυτό πρέπει να γίνεται αυτόματα πριν να χρησιμοποιηθεί το αρχείο κατάλογος.
Προσθήκη
Η προσθήκη νέας εγγραφής στο αρχείο δεδομένων απαιτεί τη προσθήκη αντίστοιχης εγγραφής στο αρχείο κατάλογο. Η προσθήκη εγγραφής στο αρχείο δεδομένων είναι απλή αφού χρειάζεται να προστεθεί εγγραφή στο τέλος του αρχείου.
Η προσθήκη εγγραφής στον πίνακα INDEX θα απαιτήσει πιθανώς αναδιοργάνωση του πίνακα αφού απαιτείται να παραμείνει ταξινομημένος.
Add (Algorithm 4_1)
procedure Add(file, buffer, indexfile, n, index);
OPEN(file);
APPEND(file, buffer);
COPY_INDEXFILE_TO_MEMORY(indexfile, n index);
SORT_INDEX(index, key(buffer), n);
COPY_FROM_MEMORY_TO_INDEXFILE(index, n, indexfile);
CLOSE(file);
Διαγραφή
Στο κεφάλαιο που αναφέρονταν στα σχετικά αρχεία αναφέραμε μια μέθοδο που μας επιτρέπει την επαναχρησιμοποίηση διαγραμμένων εγγραφών. Αυτή η μέθοδος μπορεί να εφαρμοσθεί και για το αρχείο δεδομένων, μια και το αρχείο δεν μεταβάλλεται, π.χ. δεν ταξινομείται για να έχουμε μετακίνηση εγγραφών. Βέβαια όταν διαγράφουμε εγγραφές από το αρχείο δεδομένων πρέπει επίσης να διαγραφούν οι αντίστοιχες εγγραφές από το αρχείο κατάλογο.
Μια και το αρχείο κατάλογος περιλαμβάνεται σε πίνακα κατά τη διάρκεια εκτέλεσης του προγράμματος, η διαγραφή εγγραφής του αρχείου καταλόγου σημαίνει τη διαγραφή στοιχείου του πίνακα, πράγμα που συνεπάγεται τη μετακίνηση στοιχείων του πίνακα που τελικά δεν είναι και τόσο χρονοβόρα διαδικασία. Βέβαια εναλλακτικά θα μπορούσαμε απλώς να μαρκάρουμε την αντίστοιχη εγγραφή στον πίνακα ως διαγραμμένη.
Ανάγνωση όλων των εγγραφών του αρχείο χωρίς μια συγκεκριμένη σειρά
Όπως και στις άλλες οργανώσεις αρχείου η διαδικασία αυτή επιτυγχάνεται με σειριακή ανάγνωση του αρχείου δεδομένων.
Read all records in any order (Algorithm 1_2)
Ανάγνωση όλων των εγγραφών με βάση κάποιο συγκεκριμένο κλειδί
Read all records in key value (Algorithm 4_2)
procedure Algor4_2(indexfile, n, index, file);
OPEN(file);
COPY_ INDEXFILE_TO_MEMORY(indexfile, n, index);
FOR i := 1 to n DO BEGIN
r := loc(index[i]);
READ_DIRECT(file, buffer, r);
process buffer;
END;
CLOSE(file);
Ανάγνωση μιας εγγραφής με βάση την τιμή κάποιου συγκεκριμένου κλειδιού
Αν πρόκειται για το πρωτεύον κλειδί τότε εφαρμόζεται η μέθοδος BS στο αρχείο κατάλογο (πίνακα INDEX) εντοπίζεται ο αριθμός εγγραφής στο αρχείο δεδομένων και απαιτείται μόνο η πράξη READ_DIRECT.
Αν όμως η ανάγνωση χρειάζεται να γίνει με βάση κάποιο άλλο κλειδί, τότε ή θα αναγνωσθεί σειριακά το αρχείο δεδομένων ή θα δημιουργηθεί άλλο κλειδί (δευτερεύον κλειδί).
Read a record with specific key value (Algorithm 4_3)
procedure Algor4_3(Indexfile, n, index, givenkey, file, buffer);
OPEN(FILE);
COPY _INDEXFILE_TO_MEMORY(indexfile, n, index);
BINSHR(index,n, givenkey, indexbuffer);
r := loc(buffer);
READ_DIRECT(file, buffer, r);
CLOSE(file);
6.5 Πρόσβαση στο αρχείο δεδομένων με πολλαπλά κλειδιά.
Ας ξαναγυρίσουμε στο παράδειγμα με το αρχείο δίσκων μουσικής. Όπως είπαμε θεωρούμε το αρχείο κατάλογο που αποτελείται από το σύνθετο πρωτεύον κλειδί LABEL_ID και τον αριθμό εγγραφής. Ένα εύλογο ερώτημα που μπορεί να τεθεί είναι αν θα μπορούσε να αναζητήσει κανείς ένα δίσκο με βάση ένα κλειδί που έχει τιμή DG18807, ή τη συμφωνία 9 του Beethoven. Ας πάμε ακόμη πιο πίσω στη βιβλιοθήκη και στη καρτέλα καταλογογράφησης. Το πρωτεύον κλειδί στην περίπτωσή μας είναι το LABEL_ID, δηλαδή ένα είδος αριθμού καταλόγου. Όπως σε κάθε βιβλίο αντιστοιχίζεται και ένας αριθμός καταλόγου έτσι και για μας το LABEL_ID είναι μοναδικό. Βέβαια σε μια βιβλιοθήκη είναι ασυνήθιστο να αναζητούμε ένα βιβλίο με βάση τον αριθμό καταλόγου, π.χ. ένα βιβλίο με αριθμό καταλόγου : QA… , αντίθετα συνήθως ζητάμε ένα βιβλίο με βάση το θέμα ή τον συγγραφέα ή τον τίτλο. Ετσι για κάποιο συγκεκριμένο θέμα ή τίτλο αναζητούμε τον αριθμό καταλόγου και έτσι έχουμε στη διάθεσή μας τον διάθεσή μας το βιβλίο.
Όμοια λοιπόν μπορούμε να δημιουργήσουμε αρχεία καταλόγων με βάση τον τίτλο του δίσκου, τον συνθέτη κτλ. Αυτά τα πεδία ονομάζονται δευτερεύοντα κλειδιά (secondary keys). Όπως λοιπόν ένας κατάλογος βιβλιοθήκης συσχετίζει ένα συγγραφέα (secondary key) με τον αριθμό καταλόγου (primary key) έτσι και εμείς μπορούμε να κατασκευάσουμε ένα αρχείο κατάλογο (Composer Index) που συσχετίζει έναν συνθέτη με το LABEL_ID. Tα παραπάνω φαίνονται στην εικόνα 6.4.
Composer Index
Eικόνα 6.4 : Αρχείο κατάλογος βασισμένο σε δευτερεύον κλειδί: Composer
Βέβαια αν και υπάρχουν ομοιότητες μεταξύ της βιβλιοθήκης και του αρχείου δίσκων μουσικής υπάρχουν και διαφορές. Σε μια βιβλιοθήκη, όταν γνωρίζουμε τον αριθμό καταλόγου μπορούμε να βρούμε το βιβλίο μια και τοποθετούνται τα βιβλία με βάση τον αριθμό καταλόγου. Μ’ άλλα λόγια τα βιβλία ταξινομούνται με βάση το πρωτεύον κλειδί.
Οι δίσκοι στο αρχείο δεδομένων είσαγονται με βάση το χρόνο άφιξης στο αρχείο. Έτσι όταν γνωρίζουμε το πρωτεύον κλειδί που αντιστοιχεί σε συγκεκριμένο συνθέτη κτλ., χρειάζεται να προσπελάσουμε και το αρχείο κατάλογο για να εντοπίσουμε σε ποιά εγγραφή του αρχείου δεδομένων βρίσκεται ο συγκεκριμένος συνθέτης.
Βέβαια θα μπορούσε το αρχείο κατάλογο συνθέτη (Composer Index) να δομηθεί διαφορετικά, δηλαδή με ένα πεδίο το δευτερεύον κλειδί (συνθέτη) και δεύτερο πεδίο τον αριθμό εγγραφής που αντιστοιχεί ο συγκεκριμένος συνθέτης στο αρχείο δεδομένων Υπάρχουν όμως συγκεκριμένοι λόγοι που επιλέγεται η πρώτη δομή οργάνωσης του δευτερεύοντος αρχείου καταλόγου.
Προσθήκη
Η προσθήκη εγγραφής στο αρχείο δεδομένων θα σημάνει και προσθήκη εγγραφής στο πρωτεύον αρχείο κατάλογο αλλά και στο δευτερεύον αρχείο κατάλογο. Όπως και με ένα αρχείο κατάλογο (πρωτεύον) θα χρειασθεί η αναδόμηση του αρχείου καταλόγου. Βέβαια όπως ήδη αναφέρθηκε αν το δευτερεύον αρχείο κατάλογο χωράει στη μνήμη, τότε το κόστος της προσθήκης εγγραφής δεν είναι σημαντικό.
Θα πρέπει να επισημάνουμε ότι το μεν δευτερεύον αρχείο κατάλογος (secondary index) επιτρέπει την ύπαρξη διπλού κλειδιού, ενώ το πρωτεύον αρχείο κατάλογος όχι. Προφανώς οι διπλοεγγραφές είναι ομαδοποιημένες αφού το αρχείο κατάλογος είναι ταξινομημένο ως προς το δευτερεύον κλειδί που έχει ορισθεί.
Διαγραφή
Διαγραφή μιας εγγραφής συνεπάγεται προφανώς την διακοπή κάθε αναφοράς σ’ αυτή την εγγραφή. Έτσι η διαγραφή εγγραφής από το αρχείο δεδομένων συνεπάγεται τη διαγραφή της αντίστοιχης εγγραφής από το πρωτεύον αρχείο κατάλογο και από το δευτερεύον αρχείο κατάλογο. Το πρόβλημα τόσο με το δευτερεύον αρχείο κατάλογο όσο και με το πρωτεύον είναι ότι και τα 2 αρχεία είναι ταξινομημένα. Έτσι η διαγραφή μιας εγγραφής οδηγεί σε αναδιάταξη του αρχείου προκειμένου να “καλυφθεί” ο χώρος που έμεινε κενός από τη διαγραφή εγγραφής.
Η διαγραφή όλων των αντίστοιχων εγγραφών και από τα 2 αρχεία καταλόγους είναι επιβεβλημένη αν το δευτερεύον αρχείο κατάλογος αναφέρεται κατ’ ευθεία στο αρχείο δεδομένων. Αν δεν διαγραφεί η εγγραφή από το δευτερεύον αρχείο κατάλογο και το δευτερεύον αρχείο κατάλογος αναφέρεται κατ’ ευθείαν στο αχρείο δεδομένων θα είναι δύσκολο να αποφανθούμε αν ο αριθμός εγγραφής στην οποία αναφέρεται η διαγραμμένη εγγραφή είναι νόμιμη ή όχι. Τα πεδία αναφοράς που σχετίζονται με τα δευτερεύοντα κλειδιά μπορεί να διευθυνσιοδοτούν σε εγγραφές, μετά τη διαγραφή και την επαναχρησιμοποίηση της εγγραφής στο αρχείο δεδομένων, που συσχετίζονται με διαφορετικές εγγραφές στο αρχείο δεδομένων. Γι’ αυτό το λόγο αποφύγαμε να έχουμε κατ’ ευθείαν αναφορά στο αρχείο δεδομένων από το δευτερεύον αρχείο κατάλογο. Έτσι μετά την αναζήτηση στο δευτερεύον αρχείο κατάλογο αναζητούμε και στο πρωτεύον αρχείο κατάλογο. Η αναζήτηση στο πρωτεύον αρχείο κατάλογο θα έχει ως αποτέλεσμα εγγραφή ανύπαρκτη. Συνεπώς η ενημέρωση μόνο του πρωτεύοντος αρχείου καταλόγου μας προστατεύει από αναζήτηση ανύπαρκτων εγγραφών.
Άρα η διαγραφή εγγραφής στο αρχείο δεδομένων μπορεί να συνεπάγεται τη διαγραφή της αντίστοιχης εγγραφής μόνο στο πρωτεύον αρχείο κατάλογο και να μην επέμβουμε στο δευτερεύον αρχείο κατάλογο. Η αναζήτηση που θα ξεκινήσει από το δευτερεύον αρχείο δεν θα συνεχισθεί αφού η αναζήτηση και στο πρωτεύον αρχείο κατάλογο θα δώσει ως αποτέλεσμα ανύπαρκτη εγγραφή.
Αν έχουμε περισσότερα από ένα δευτερεύοντα αρχεία τότε η μη ενημέρωσή τους κατά τη διαγραφή εγγραφών σημαίνει ένα όχι ευκαταφρόνητο κόστος το οποίο είναι ακόμη σημαντικότερο όταν η επεξεργασία αρχείων καταλόγων υλοποιείται στη δευτερεύουσα μνήμη. Είναι επίσης σημαντικό για τις διαλογικές εφαρμογές (interactive) όπου ο χρήστης περιμένει αρκετό χρόνο για να ολοκληρωθεί η διαδικασία της διαγραφής.
Βέβαια το κέρδος που προκύπτει από την μη ενημέρωση των δευτερευόντων αρχείων καταλόγων συνεπάγεται απώλεια σε χώρο. Αν η εφαρμογή μας είναι ευμετάβλητη, δηλαδή προβλέπεται μεγάλος αριθμός αλλαγών στο μέγεθος του αρχείου με προσθήκες και διαγραφές, τότε πρέπει να υπάρχει σχετική διαδικασία που θα απομακρύνει από τα δευτερεύοντα αρχεία καταλόγους τις διαγραμμένες εγγραφές. Μια άλλη λύση είναι η χρήση άλλης δομής αρχείου, όπως η μέθοδος B-tree που επιτρέπει διαγραφές χωρίς να απαιτείται αναδιοργάνωση αρχείου.
Ενημέρωση εγγραφής
Διακρίνουμε 3 περιπτώσεις
Ενημέρωση - αλλαγή δευτερεύοντος κλειδιού
Αν αλλάζει τιμή το δευτερεύον κλειδί τότε πρέπει να ενημερώσουμε και το δευτερεύον αρχείο κατάλογο ώστε να παραμείνει ταξινομημένο. Διαδικασία χρονοβόρα.
Ενημέρωση - αλλαγή πρωτεύοντος κλειδιού
Αλλαγή του πρωτεύοντος κλειδιού προφανώς έχει επίδραση στο πρωτεύον αρχείο κατάλογο. Αλλά συνήθως απαιτείται μόνο η ενημέρωση του πεδίου αναφοράς (στο παράδειγμά μας το πεδίο LABEL_ID) σ΄ όλα τα δευτερεύοντα αρχεία καταλόγους. Στα δευτερεύοντα αρχεία καταλόγους απαιτούνται σχετικά εύκολες αλλαγές, μια και χρειάζεται να λάβει τη νέα τιμή το πεδίο αναφοράς. Αυτό σημαίνει αναζήτηση στα δευτερεύοντα αρχεία και ενημέρωση του πεδίου αναφοράς. Αν όμως υπάρχουν περισσότερες από μια εγγραφές με την ίδια τιμή του δευτερεύοντος κλειδιού, τότε χρειάζεται τοπική αναδιάταξη των εγγραφών, αφού εγγραφές με την ίδια τιμή δευτερεύοντος κλειδιού διατάσσονται σύμφωνα με την τιμή του πεδίου αναφοράς.
Αλλαγή άλλων πεδίων
Αλλαγή στις τιμές άλλων πεδίων δεν συνεπάγονται αλλαγές στα αρχεία καταλόγων.
6.6 Αναζήτηση χρησιμοποιώντας συνδυασμό δευτερευόντων κλειδιών
Μια από τις πλέον σημαντικές εφαρμογές των δευτερευόντων κλειδιών είναι αυτές που αναφέρονται σε αναζητήσεις προκειμένου να προσδιορισθεί ένα συγκεκριμένο υποσύνολο εγγραφών του αρχείου δεδομένων. Για να γίνει αντιληπτό θα χρησιμοποιήσουμε ένα παράδειγμα. Κατ’ αρχήν θεωρούμε ένα ακόμη ένα δευτερεύοντα αρχείο κατάλογο χρησιμοποιώντας ως κλειδί τον τίτλο. Ετσι έχουμε το αρχείο κατάλογο Title Index, (εικόνα 6.5).
Title Index
Εικόνα 6.5: Αρχείο κατάλογος βασισμένος σε δευτερεύον κλειδί : title
Ας υποθέσουμε ότι τίθενται ερωτήσεις όπως:
να προσδιορισθεί η εγγραφή με LABEL_ID COL38358 (προσπέλαση με βάση το πρωτεύον κλειδί)
να προσδιοριστούν όλοι οι δίσκοι του BEETHOVEN (προσπέλαση με βάση το δευτερεύον κλειδί -composer)
να προσδιοριστούν όλοι οι δίσκοι με τίτλο “Violin concerto” (προσπέλαση με βάση το δευτερεύον κλειδί title)
Σε πολλές περιπτώσεις όμως επιθυμείται να προσδιοριστούν εγγραφές με βάση π.χ. τον συνθέτη και τον τίτλο.
Παράδειγμα: να προσδιοριστούν όλοι οι δίσκοι του “Beethoven Symphony No 9”
Χωρίς τη χρήση δευτερευόντων αρχείων καταλόγων θα έπρεπε να προσπελάσουμε το αρχείο σειριακά, εργασία αρκετά χρονοβόρα σε αρχείο με μεγάλο πλήθος εγγραφών.
Η παραπάνω ερώτηση μπορεί να διατυπωθεί ως εξής:
Να προσδιοριστούν όλες οι εγγραφές με
composer=”BEETHOVEN” AND title =“SYMPHONY No 9”
Η διαδικασία που ακολουθείται είναι:
α) αναζητούμε στο αρχείο κατάλογο “συνθέτη” (Composer Index) για εγγραφές με τιμή δευτερεύοντος κλειδιού = BEETHOVEN και έχουμε την παρακάτω λίστα από LABEL_ID.
ANG3795
DG139201
DG18807
RCA2626
β) αναζητούμε στο αρχείο κατάλογο “τίτλος” (Title Index) για εγγραφές με τιμή δευτερεύοντος κλειδιού = “SYMPHONY No 9” και έχουμε την παρακάτω λίστα από LABEL_ID:
ANG3795
COL31809
DG18807
Εφαρμόζοντας την λογική πράξη AND μεταξύ των πεδίων αναφοράς των δυο παραπάνω λιστών έχουμε:
ANG3705
DG18807
Η διαδικασία που εφαρμόζεται για τον προσδιορισμό του συνόλου που προκύπτει από τη τομή των δυο συνόλων είναι η εξής: Κατ’ αρχήν όταν έχουμε περισσότερες από μια ίσες τιμές του δευτερεύοντος κλειδιού, τότε τις ταξινομούμε ως προς το πεδίο αναφοράς. Έτσι προκύπτει το σύνολο τομής με βάση το πεδίο αναφοράς (LABEL_ID). Με βάση τους αριθμούς εγγραφής που αντιστοιχούν σ’ αυτά τα πεδία αναφοράς στο πρωτεύον αρχείο εντοπίζουμε τις εγγραφές στο αρχείο δεδομένων.
Μέσω αυτής της επεξεργασίας φαίνεται η δύναμη των αρχείων καταλόγων. Διαθέτοντας μόνο ένα αντίγραφο του αρχείου δεδομένων μπορούμε να επεξεργαστούμε τα δεδομένα ή να τα δούμε από διαφορετικές απόψεις. Ετσι με τη χρήση δευτερευόντων αρχείων καταλόγων μπορούμε να έχουμε τα δεδομένα διατεταγμένα ως προς τον συνθέτη ή τον τίτλο ή οποιοδήποτε άλλο πεδίο μας ενδιαφέρει. Βέβαια μπορούμε να εφαρμόσουμε κι οποιαδήποτε άλλη λογική πράξη όπως OR, AND - OR κτλ.
6.7 Βελτιώνοντας τη δευτερεύουσα δομή καταλόγου : Ανεστραμμένες λίστες
Η διαχείριση των δευτερευόντων αρχείων καταλόγων έχει ως συνέπεια 2 δυσκολίες.
Πρέπει να επαναδιατάξουμε το αρχείο κατάλογο κάθε φορά που μια νέα εγγραφή προστίθεται στο αρχείο δεδομένων, ακόμη κι αν αυτή η νέα εγγραφή αναφέρεται σε υπάρχον δευτερεύον κλειδί π.χ. η προσθήκη εγγραφής με συνθέτη τον BEETHOVEN και SYMPHONY Νο 9 θα οδηγήσει σε επαναδιάταξη των δευτερευόντων αρχείων καταλόγων, Composer Index και Title Index, αν και υπάρχουν εγγραφές σ’ αυτά με τιμές BEETHOVEN και SYMPHONY Νο 9
Αν υπάρχουν εγγραφές περισσότερες από μια με την ίδια τιμή του δευτερεύοντος κλειδιού, τότε το πεδίο που αντιστοιχεί στο δευτερεύον κλειδί επαναλαμβάνεται. Αυτό οδηγεί σε σπατάλη χώρου που με τη σειρά της μπορεί να έχει ως συνέπεια το δευτερεύον αρχείο κατάλογος να μην χωράει στη μνήμη.
Μια πρώτη προσπάθεια για λύση
Ένας τρόπος για να ξεπεραστούν οι δυσκολίες είναι η αλλαγή της δομής του δευτερεύοντος αρχείου καταλόγου. Έτσι αντιστοιχούμε σε κάθε δευτερεύον κλειδί ένα πίνακα αναφορών. Για παράδειγμα χρησιμοποιώντας μια δομή εγγραφής που θα μας επιτρέψει να αντιστοιχίσουμε σε κάθε δευτερεύον κλειδί 4 αναφορές του LABEL_ID, δηλαδή,
Η εικόνα 6.6 μας δίνει μια σχηματική παράσταση ενός τέτοιου αρχείου καταλόγου που αναφέρεται στα δεδομένα του αρχείου δεδομένων, datafile.
Tροποποιημένο το αρχείο κατάλογος Composer Index
Εικόνα 6.6 : Δευτερεύον αρχείο κατάλογος με αποθήκευση πολλαπλών αναφορών για κάθε δευτερεύον κλειδί
Μ’ αυτό το τρόπο δεν χρειάζεται η ταξινόμηση του δευτερεύοντος αρχείου καταλόγου κάθε φορά που προστίθενται ένα νέο έργο π.χ. αν προστεθεί στο αρχείο δεδομένων ένα έργο του Prokofiev, δεν απαιτείται η προσθήκη νέας εγγραφής στο αρχείο κατάλογο. Ετσι αν προστεθεί η παρακάτω εγγραφή στο αρχείο δεδομένων, έχουμε :
Εκείνο που απαιτείται είναι να εισάγουμε στο δευτερεύοντα αρχείο κατάλογο (Composer Index) μια δεύτερη LABEL_ID, δηλαδή:
Έτσι δεν χρειάζεται επαναδιάταξη του δευτερεύοντος αρχείου καταλόγου αφού δεν προστίθεται νέα εγγραφή απλώς χρειάζεται αναδιάταξη των πεδίων αναφοράς (LABEL_ID) εντός της υπάρχουσας εγγραφής με τιμή δευτερεύοντος κλειδιού = PROCOFIEV.
Αν κι αυτή η δομή βοηθάει με το να μη χρειάζεται επαναδιάταξη του αρχείου καταλόγου παρ’ όλα αυτά έχει προβλήματα. Είμαστε αναγκασμένοι να ορίσουμε ένα καθορισμένο αριθμό πεδίων για να αποθηκεύσουμε τα πεδία αναφοράς. Έτσι κάποια στιγμή θα οδηγηθούμε να μη διαθέτουμε επαρκή χώρο για να αποθηκεύσουμε πεδία αναφοράς ή σε άλλες εγγραφές θα σπαταλιέται χώρος αφού αυτά τα πεδία θα μένουν κενά.
Έτσι θα αναζητήσουμε μια δομή που θα ικανοποιεί και τις 3 παρακάτω απαιτήσεις.
δεν θα χρειάζεται αναδιάταξη του δευτερεύοντος αρχείου καταλόγου με κάθε προσθήκη νέας εγγραφής στο αρχείο δεδομένων.
θα επιτρέπει την αποθήκευση περισσοτέρων από 4 πεδίων αναφοράς
δεν θα γίνεται σπατάλη χώρου
Μια καλλίτερη λύση : Συνδετική λίστα για τα πεδία αναφοράς
Αρχεία όπου το δευτερεύον κλειδί οδηγεί σε ένα σύνολο ενός ή περισσοτέρων πρωτευόντων κλειδιών, ονομάζονται ανεστραμμένες λίστες (inverted lists). Οι λίστες θεωρούνται ανεστραμμένες μια και εργαζόμαστε με αντίστροφο τρόπο, δηλαδή από το δευτερεύον κλειδί προς το πρωτεύον κλειδί για να εντοπίσουμε την εγγραφή στο αρχείο δεδομένων.
H δεύτερη λέξη στον όρο Inverted lists - ανεστραμένες λίστες, μας λέει κάτι σημαντικό, δηλαδή, ότι αναφερόμαστε σε λίστα αναφορών πρωτεύοντος κλειδιού. Ετσι το τροποποιημένο δευτερεύον αρχείο κατάλογος θα συγκεντρώνει ένα αριθμό από LABEL_ID για κάθε δευτερεύον κλειδί. Στην εικόνα 6.7 δίνεται σχηματικά η έννοια της αναστραμμένης λίστας.
Εικόνα 6.7: Εννοιολογική άποψη πρωτευόντων πεδίων αναφοράς σαν μια ακολουθία από λίστες
Έτσι κάθε δευτερεύον κλειδί θα δείχνει σε διαφορετική λίστα από πρωτεύοντα κλειδιά αναφοράς. Κάθε μια από αυτές τις λίστες θα έχει μήκος όσο χρειάζεται και θα μεγαλώνει όσο χρειάζεται.
Ετσι αν προσθέσουμε μια νέα εγγραφή που αναφέρεται στον PROKOFIEV, τότε η λίστα που αναφέρεται στον PROKOFIEV, θα είναι :
Ομοίως αν προστεθούν 2 νέες εγγραφές για τον Beethoven το μόνο που θα χρεισθεί είναι να προστεθούν 2 επιπλέον στοιχεία στη λίστα αναφορών που σχετίζεται με το κλειδί Beethoven. Ετσι σε αντίθεση με την αρχική τεχνική που δεσμεύαμε χώρο για να αποθηκεύσουμε τις 4 τιμές του πεδίου LABEL_ID, οι λίστες μπορούν να περιέχουν εκατοντάδες αναφορών και μόνο μια τιμή του δευτερεύοντος κλειδιού. Απ’ την άλλη αν η λίστα έχει μόνο ένα στοιχείο τότε δεν θα σπαταλιέται χώρος και το σημαντικότερο θα χρειαστεί αναδιάταξη του δευτερεύοντος αρχείου καταλόγου μόνο αν προστεθεί νέος συνθέτης στο αρχείο δεδομένων (datafile).
Το ερώτημα που τίθεται είναι να που θα αποθηκεύσουμε αυτές τις μικρές λίστες διαφορετικού μεγέθους η κάθε μια. Σε διαφορετικά αρχεία; Ο απλούστερος τρόπος είναι η χρήση συνδετικής λίστας.
Τροποποιούμε τη δομή του δευτερεύοντος αρχείου καταλόγου έτσι που να περιλαμβάνει 2 πεδία, ένα με το πρωτεύον κλειδί και το δεύτερο τον αριθμό εγγραφής στην ανεστραμμένη λίστα που αντιστοιχεί στο πρωτεύον κλειδί.
Τα πρωτεύοντα κλειδιά θα αποθηκεύονται σε διαφορετικό αρχείο με δομή σειριακού-χρονολογικού αρχείου.Σύμφωνα λοιπόν με τα δεδομένα του παραδείγματος αυτή η νέα τεχνική θα οδηγήσει σ’ ένα δευτερεύον αρχείο λίστα (LABEL_ID αρχείο) που οργανώνεται όπως φαίνεται παρακάτω. Έτσι το αρχείο κατάλογος συνθέτης (Composer Index) τροποποιείται ως εξής :
Secondary Index file LABEL_ID file
Εικόνα 6.8 : Βελτιωμένη οργάνωση του αρχείου Composer Index
Έτσι αν αναζητούμε με δευτερεύον κλειδί τον συνθέτη π.χ. BEETHOVEN, τότε από το δευτερεύον αρχείο κατάλογο (Composer index) βρίσκουμε ότι οι αναφορές για τον Beethoven ξεκινούν από την 3η εγγραφή του αρχείου λίστα (Label_id αρχείο λίστα). Από κει και πέρα εργαζόμαστε με το αρχείο λίστα, Label_id. Αρχίζοντας λοιπόν από την εγγραφή με αριθμό εγγραφής 3, μετά θα πάμε στην 8η, 5η, 1η και μετά σταματάμε.
Στη συνέχεια θα δούμε πως η προσθήκη νέας εγγραφής θα επηρρεάσει τον δευτερεύοντα αρχείο κατάλογο και το αρχείο λίστα Lable_id. Ας υποθέσουμε ότι προσθέσαμε μια εγγραφή που αναφέρεται στον PROKOFIEV, όπως ήδη αναφέρθηκε παραπάνω, με τα εξής στοιχεία:
Στην εικόνα 6.8 φαίνεται ότι αυτή η εγγραφή είναι η τελευταία του αρχείου λίστα Label_id μια και το αρχείο label_id οργανώνεται ως σειριακό-χρονολογικό αρχείο. Πριν τη προσθήκη αυτής της εγγραφής υπήρχε μόνο ένας δίσκος μουσικής που αναφέρονταν στον Prokofiev και είχε ως Label_id την τιμή LON2312. Επειδή θέλουμε να διατηρήσουμε τις λίστες ταξινομημένες (αλφαριθμητική διάταξη), ο νέος δίσκος εισέρχεται στη λίστα που αφορά στον PROKOFIEV και προηγείται λογικά του δίσκου με label_id ίσο με LON2312. Ετσι οι αναφορές για τον PROKOFIEV θα ξεκινήσουν από το αρχείο λίστα Label_id από την εγγραφή με αριθμό εγγραφής ίσο με 10 και μετά θα πάμε στην εγγραφή με αριθμό εγγρφαής ίσο με 0. Ετσι θα έχουμε ως αναφορές για τον PROKOFIEV αυτές με label_id ίσο με ANG36193 και LON2312.
Έτσι αντιστοιχίζοντας σε κάθε δευτερεύον αρχείο κατάλογο ένα αρχείο λίστα έχουμε τα εξής:
Δεν χρειάζεται ταξινόμηση του δευτερεύοντος αρχείου καταλόγου με κάθε νέα προσθήκη εγγραφής στο αρχείο δεδομένων. Η μόνη περίπτωση που θα χρειασθεί επαναδιάταξη του δευτερεύοντος αρχείου καταλόγου είναι όταν προστεθεί νέος συνθέτης. Η διαγραφή ή η προσθήκη δίσκου υπάρχοντος συνθέτη δεν απαιτεί αναδιάταξη του δευτερεύοντος αρχείου καταλόγου αλλά μόνο του αρχείου λίστα. Τη διαγραφή όλων των δίσκων συνθέτη καταχωρημένου στο δευτερεύον αρχείο μπορούμε να τη διαχειριστούμε ως εξής: να αφήσουμε την εγγραφή στο δευτερεύον αρχείο και στο πεδίο αναφορά να βάλουμε τη τιμή -1 που σημαίνει ότι αυτή η εγγραφή του δευτερεύοντος αρχείου καταλόγου δεν οδηγεί σε λίστα.
Σε περίπτωση που χρειαστεί να αναδιαταχθεί το δευτερεύον αρχείο τότε η διαδικασία αυτή είναι ευκολότερη αφού χρειάζεται λιγότερες εγγραφές να μετακινήσουμε και κάθε εγγραφή είναι μικρότερη.
Μια και δεν έχουμε συχνά ταξινομήσεις και το δευτερεύον αρχείο μ’ αυτή τη δομή είναι μικρότερο, έτσι αφήνουμε μεγαλύτερο χώρο RAM για άλλες δομές δεδομένων.
Το αρχείο LABEL_ID list file είναι entry sequenced που σημαίνει ότι δεν θα χρειασθεί ποτέ να το ταξινομήσουμε.
Μπορούμε τέλος διαγραμμένες εγγραφές του αρχείου LABEL_ID list να χρησιμοποιηθούν εκ νέου έτσι όπως περιγράφτηκε στο προηγούμενο κεφάλαιο.
Βέβαια η δομή αυτή έχει και ένα μειονέκτημα. Οι εγγραφές με τα Label id’s δεν είναι πλέον “φυσικά” ομαδοποιημένες. Π.χ. για τον BEETHOVEN θα επισκεφθούμε την 3η, 8η, 5η, 1η. Αυτή η έλλειψη “τοπικότητας” (locality) μπορεί να οδηγήσει σε πολλές αναζητήσεις (seeks) σε περίπτωση που έχουμε μεγάλη λίστα αναφορών.
Ένας τρόπος για να ξεπεραστεί ο μεγάλος αριθμός αναζητήσεων είναι να διατηρήσουμε το αρχείο λίστα Label_id στη μνήμη. Βέβαια αυτό μπορεί να είναι πολυέξοδο και μη πρακτικό αν έχουμε μεγάλο αριθμό δευτερευόντων αρχείων καταλόγων, εκτός βέβαια κι αν μοιράζονται το ίδιο αρχείο λίστα. Βέβαια ακόμη κι αν το αρχείο λίστα είναι πολύ μεγάλο και δεν χωρά στη μνήμη είναι δυνατόν να επιτύχουμε βελτίωση της αποτελεσματικότητας, κρατώντας έστω και μέρος του αρχείου στη μνήμη, μεταφέροντας από το δίσκο στη μνήμη και αντίστροφα τμήματα του αρχείου.