Εικόνα 10.1 Αρχείο δεδομένων με πολλαπλούς καταλόγους

Το αρχείο δεδομένων μπορεί να οργανωθεί μ’ οποιοδήποτε από τις μεθόδους που αναφέρθηκαν (όπως σειριακά-χρονολογικά αρχεία, σχετικά, ταξινομημένα, άμεσης προσπέλασης). Οι βασικές διαδικασίες που θα πρέπει να λαμβάνονται υπόψη είναι η προσθήκη και η διαγραφή. Όπου χρειάζεται συχνά να γίνεται εξαντλητική ανάγνωση αρχείου με διάταξη ως προς κάποιο κλειδί, το ταξινομημένο σχετικό αρχείο χρειάζεται λιγότερες προσπελάσεις μια και πλεονεκτεί αυτή η οργάνωση λόγω του παράγοντα ομαδοποίησης.

Βέβαια τα αρχεία κατάλογοι μπορεί να είναι οποιουδήποτε τύπου. Παρ’ όλα αυτά το Β-δένδρο υπερτερεί έναντι όλων των άλλων τύπων για τις περισσότερες εφαρμογές. Κάθε κατάλογος μπορεί να υλοποιείται με διαφορετικό αρχείο ή όλοι οι κατάλογοι μπορεί να υλοποιούνται με ένα αρχείο. Όλα τα παραπάνω σχήματα μπορούν να χρησιμοποιούνται. Στη συνέχεια υποθέτουμε ότι κάθε κατάλογος καταλαμβάνει ξεχωριστό αρχείο.

Η επιλογή δεικτών που χρησιμοποιούνται για να συνδέουν κάθε στοιχείο του καταλόγου με στοιχείο του αρχείου δεδομένων είναι σημαντική. Αν ο τύπος του αρχείο δεδομένων είναι τέτοιος που οποιαδήποτε εγγραφή δεν θα επανατοποθετηθεί τότε προφανώς ο τύπος του δείκτη είναι ο αριθμός εγγραφής. Παρ’ όλα αυτά για κάποιους τύπους αρχείων, όπως τα αρχεία άμεσης προσπέλασης, είναι δυνατόν μια εγγραφή να επανατοποθετηθεί λόγω προσθήκης ή διαγραφής άλλης εγγραφής. Γι’ αυτές τις περιπτώσεις υπάρχουν 2 επιλογές:

Οι διαδικασίες που επανατοποθετούν μια εγγραφή πρέπει να φροντίζουν και για την ενημέρωση των τιμών των δεικτών όλων των καταλόγων όταν μια εγγραφή μετακινείται.

Ο τύπος του δείκτη θα επιλεγεί έτσι ώστε οι τιμές που λαμβάνει θα είναι ανυπερέαστες από την επανατοποθέτηση εγγραφής.

Π.χ. και τα ταξινομημένα σχετικά αρχεία άμεσης προσπέλασης χρησιμοποιώντας τη τεχνική διαχείρισης συνωνύμων με επανατοποθέτηση θα προκαλέσουν μετακινήσεις εγγραφών μετά από προσθήκες και διαγραφές.

Τα ταξινομημένα σχετικά αρχεία πρέπει να μετακινήσουν εγγραφές λόγω προσθήκης και διαγραφής ενώ η τεχνική διαχείρισης συνωνύμων με επανατοποθέτηση προκαλεί μετακίνηση εγγραφών σε αρκετές διαφορετικές καταστάσεις. Και οι 2 τύποι αρχείων χρησιμοποιούν πρωτεύον κλειδί για να εντοπίσουν κάθε εγγραφή. Αυτό το πρωτεύον κλειδί χρησιμοποιείται πάντα για τον εντοπισμό εγγραφής ανεξάρτητα της φυσικής της θέσης. Σ’ αυτές τις περιπτώσεις το αρχείο κατάλογος γίνεται το μέσον που μετατρέπει μια τιμή κλειδιού (δευτερεύον κλειδί) σε άλλη τιμή κλειδιού (πρωτεύον κλειδί) με βάση την οποία η εγγραφή είναι δυνατόν να εντοπισθεί.

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

Πολλές φορές στην οργάνωση αρχείου με πολλαπλούς καταλόγους γίνεται διάκριση μεταξύ του πρωτεύοντος και του δευτερεύοντος κλειδιού. Όταν ακολουθείται αυτή η διάκριση τότε το αρχείο δεδομένων συνήθως οργανώνεται ως αρχείο άμεσης προσπέλασης, ταξινομημένο σχετικό αρχείο ή ακολουθείται μια παρόμοια δομή όπου το πρωτεύον κλειδί προσδιορίζει την φυσική θέση της εγγραφής στο αρχείο. Όταν το αρχείο οργανώνεται ως σειριακό-χρονολογικό αρχείο ή μ’ άλλη οργάνωση, όπου μέσω του κλειδιού δεν είναι δυνατός ο εντοπισμός της εγγραφής, τότε χρησιμοποιείται κατάλογος.

Σ’ ένα αρχείο χωρίς κατάλογο η τιμή του πρωτεύοντος κλειδιού χρησιμοποιείται για να βρεθούν και οι αντίστοιχες τιμές των άλλων πεδίων. Αυτό μπορεί να παρομοιασθεί με μια συνάρτηση όπου το πρωτεύον κλειδί είναι η παράμετρος και τα υπόλοιπα πεδία είναι οι τιμές της συνάρτησης. Στην περίπτωση που υπάρχουν κατάλογοι με δευτερεύοντα κλειδιά που επιστρέφουν την τιμή του πρωτεύοντος κλειδιού αυτό αντιστοιχεί με την αντιστροφή της συνάρτησης δηλαδή για δοσμένη τιμή της συνάρτησης επιστρέφεται η αντίστοιχη παράμετρος. Γι’ αυτό το λόγο τα αρχεία που όλα τα πεδία της δεικτοδοτούνται ονομάζονται ανεστραμμένα αρχεία (inverted files) ή πλήρως ανεστραμμένα (fully inverted). Στην αντίθετη περίπτωση μερικώς ανεστραμμένα (partially inverted files).

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

Θα πρέπει να σημειωθεί ότι είναι προτιμότερη η δυναμική δημιουργία και καταστροφή καταλόγων για πρόσκαιρη χρήση παρά η διατήρηση καταλόγων.

Συνήθως όταν ένας κατάλογος δημιουργείται με βάση το δευτερεύον κλειδί η τιμή του κλειδιού για κάθε εγγραφή εκπροσωπείται στον κατάλογο. Αν υπάρχουν Ν εγγραφές στο αρχείο τότε θα έχουμε και Ν στοιχεία σε κάθε κατάλογο. Όταν η ίδια τιμή κλειδιού εμφανίζεται σε διαφορετικές εγγραφές τότε είναι δυνατόν να μειώσουμε το μέγεθος του καταλόγου δεικτοδοτώντας κάθε τιμή κλειδιού μόνο μια φορά. Έτσι κάθε στοιχείο του καταλόγου δεικτοδοτεί μόνο μια εκ των πολλών εγγραφών που έχουν την ίδια τιμή κλειδιού. Άλλες εγγραφές που μοιράζονται την ίδια τιμή κλειδιού συνδέονται μεταξύ τους με διπλή συνδετική λίστα. Η λίστα είναι διπλή για να απλουστεύει τις διαδικασίες της προσθήκης και διαγραφής εγγραφών στην αλυσίδα. Μπορεί να είναι είτε γραμμική είτε κυκλική.

Μ’ αυτή τη μέθοδο διαφορετικά κλειδιά μπορούν να δεικτοδοτούν στο ίδιο αρχείο.

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

Βέβαια η οργάνωση αυτή συνοδεύεται κι από μειονεκτήματα.

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

Παράδειγμα: αν το αρχείο δεδομένων είναι ταξινομημένο σχετικό αρχείο και ο κατάλογος Β-δένδρο ο αλγόριθμος για τον εντοπισμό εγγραφής με βάση μη πρωτεύον κλειδί θα μπορούσε να γίνει με βάση τον αλγόριθμο 7_3 για να προσδιοριστεί στοιχείο του καταλόγου και στη συνέχεια να κληθεί ο αλγόριθμος 3_2 για να εφαρμόσουμε Binary Search στο αρχείο δεδομένων για τον προσδιορισμό της συγκεκριμένης εγγραφής.

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

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

Τα αρχεία πολλαπλών καταλόγων δεν είναι χρήσιμα μόνο για τον εντοπισμό εγγραφών με διαφορετικά κλειδιά αλλά και για αναζητήσεις που προσδιορίζονται με την χρήση πολλαπλών κλειδιών. Τέτοιες αναζητήσεις ονομάζονται συνδυασμένες ερωτήσεις.

Παράδειγμα: έστω ότι δίνεται υποτροφία για τους sophomores από το Οhio και μέσο όρο βαθμολογίας ³ 3.0. Μια μέθοδος θα ήταν η εξέταση όλων των φοιτητών σειριακά και όσοι φοιτητές πληρούσαν τις 3 συνθήκες, αυτών τα ονόματα θα εκτυπώνονταν.

Αν π.χ. 10% των φοιτητών ήταν από το Ohio, 25% sophomores και 20% είχαν βαθμολογία ³ 3.0 τότε μόνο 1 φοιτητής στους 200 έχει τα προσόντα για την υποτροφία. Οι αναγνώσεις για το υπόλοιπο 99.5% των εγγραφών δεν είναι αναγκαίες.

Αν όμως τα πεδία που σχηματίζουν την ερώτηση δεικτοδοτούνται είναι δυνατόν να προσδιοριστούν οι εγγραφές που ικανοποιούν την ερώτηση χωρίς να χρειάζεται να αναγνωστεί όλο το αρχείο. Για το παράδειγμα με την υποτροφία σε κάθε ένα από τους 3 καταλόγους μπορεί να αναζητηθούν οι εγγραφές που ικανοποιούν ένα εκ των χαρακτηριστικών. Το αποτέλεσμα είναι 3 λίστες με περιεχόμενα τους με αριθμούς εγγραφών.

Εικόνα 10.3

Στη συνέχεια παρουσιάζεται ένας αλγόριθμος που βρίσκει την τομή ενός αριθμού λιστών. Ο αλγόριθμος 8_1 δέχεται j λίστες και επιστρέφει μια λίστα με δείκτες που αναφέρεται στη τομή τους. Οι συναρτήσεις READ-NEXT, WRITE-NEXT, APPEND χρησιμοποιούνται για ανάγνωση και εγγραφή στις λίστες. Η συνάρτηση SORT ταξινομεί τους δείκτες σε αύξουσα διάταξη. Οι συναρτήσεις MAX και MIN επιστρέφουν τον ΜΑΧ και ΜΙΝ των τιμών των δεικτών του πίνακα Ρ.

Συχνά ερωτήσεις ενώνονται με τον τελεστή AND. Σε περίπτωση που ερωτήσεις συνδέονται μ’ άλλον τελεστή εκτός του AND τότε χρειάζεται τροποποίηση ο αλγόριθμος 8.1. Έτσι αν οι προϋποθέσεις για να δοθεί υποτροφία είναι (state=’OH’ and class = ‘sophomores’ and GPA ³ 3.0 or city =’Akron’). Σ’ αυτή την περίπτωση ο αλγόριθμος 8_1 χρειάζεται μικρή τροποποίηση προσθέτοντας ένα ακόμη βήμα.

Οι 3 λίστες δημιουργούνται όπως και πριν από τους αντίστοιχους 3 καταλόγους (state, class, GPA). Η 4η λίστα δημιουργείται από τον κατάλογο CITY και περιλαμβάνει τις εγγραφές που έχουν τιμή ‘AKRON’. Η 4η λίστα έπειτα προστίθεται στην 3η που είναι και η τελική.

Μια και ο αλγόριθμος λειτουργεί με την λογική AND έτσι μπορεί να προστεθεί στην κατάλληλη λίστα πριν να γίνει συγχώνευση (merge).

procedure indersect(list, j); {list is an array of (j+1) lists, each of indefinite length. The first j lists contain pointers.

The intersection of the lists is returned in list(j+1)

local p(l..j); {array to hold one value at a time from each list}

FOR i:=1 to j DO APPEND(list(i), top); {top is a named constant of pointer type whose value is greater than that of any pointer.

It serves as an end-of-list sentinel}

FOR i:=1 TO j DO SORT(list(i));                     {order the pointers in all lists}

FOR i:=1 TO j DO READ_NEXT(list(i), p(i));         {read first pointer from each list}

WHILE MAX(p) < top DO BEGIN                          {loop until all mathes have been found}

IF MAX(p)=MIN(p) THEN BEGIN                 {match has been found}

WRITE_NEXT(list(j+1),p(l));                 {add match to output}

FOR i:=1 to j DO READ_NEXT(list(i),p(i));

{refill the pointrs array}

END

ELSE {replace entries less than MAX with next entries}

FOR i:=1 to j DO

IF p(i) < MAX(p) THEN

READ_NEXT(list(i),p(i));

END;

Σε περίπτωση που δεν έχουμε καταλόγους για όλα τα χαρακτηριστικά, οι συνδυαστικές ερωτήσεις μπορούν να υλοποιηθούν αποτελεσματικά με την χρήση της συγχώνευσης. Π.χ. έστω ότι ο κατάλογος GPA δεν είναι διαθέσιμος και είναι διαθέσιμοι οι κατάλογοι STATE και CLASS. Σ’ αυτή την περίπτωση η καλύτερη στρατηγική είναι με βάση τους διαθέσιμους καταλόγους να δημιουργηθούν οι λίστες των δεικτών και να εφαρμοσθεί συγχώνευση. Με βάση αυτή τη λίστα γίνεται προσπέλαση στια αντίστοιχες εγγραφές και ελέγχεται αν αυτές οι εγγραφές παρουσιάζουν GPA ³ 3.0. Έτσι η 3η λίστα (που δημιουργήθηκε από την συγχώνευση μερικώς ικανοποιεί την συνθήκη.

Περίληψη

Τα αρχεία με πολλαπλούς καταλόγους είναι αρχεία δεδομένων που σχετίζονται με ένα ή περισσότερα λογικά ξεχωριστά αρχεία καταλόγων. Τα κλειδιά των καταλόγων λέγονται δευτερεύοντα κλειδιά (secondary keys). Αρχεία με δεικτοδοτούμενα χαρακτηριστικά ονομάζονται ανεστραμμένα αρχεία (inverted files). Αρχεία που διατηρούν ένα κατάλογο για κάθε χαρακτηριστικό λέγονται πλήρως ανεστραμμένα αρχεία (fully inverted files) ενώ εκείνα που διατηρούν καταλόγους για κάποια από τα χαρακτηριστικά λέγονται μερικώς ανεστραμμένα αρχεία (partially inverted files).

Τα αρχεία με πολλαπλούς καταλόγους δεικτοδοτούν κάθε τιμή χαρακτηριστικού μόνο μια φορά. Εγγραφές που μοιράζονται την ίδια τιμή χαρακτηριστικού συνδέονται σε συνδετική λίστα. Μεταβαίνοντας από την μια συνδετική λίστα σε μια άλλη είναι δυνατόν να πλοηγούμαστε διαμέσου του αρχείου καταλόγου και να εντοπίσουμε τις εγγραφές που επιθυμούμε.

Access method είναι βιβλιοθήκες διαδικασιών και βοηθητικών προγραμμάτων που συνδυάζουν διαδικασίες προσπέλασης των αρχείων δεδομένων και των καταλόγων σ’ ένα αρχείο.

Συνδυαστικές ερωτήσεις είναι αυτές που προσδιορίζουν τα χαρακτηριστικά των εγγραφών που επιθυμούμε διαμέσου πολλαπλών κλειδιών. Αυτές τις ερωτήσεις μπορούμε να τις επεξεργαστούμε αποτελεσματικά χρησιμοποιώντας τα κλειδιά των καταλόγων και δημιουργώντας λίστες που προσδιορίζουν μερικώς τις εγγραφές (partially qualified records). Αυτές οι λίστες στη συνέχεια συγχωνεύονται για να οδηγήσουν σε μια που προσδιορίζει πλήρως τις εγγραφές (fully qualified records).

Χρησιμοποιώντας έναν αποτελεσματικό τύπο δομής καταλόγου και δημιουργώντας καταλόγους για διάφορα κλειδιά είναι δυνατόν να μειώσουμε τα στατιστικά μιας εφαρμογής σε τάξη NlogN. Για εφαρμογές που απαιτούν οποιοδήποτε είδος ταξινόμησης αυτή η τάξη στατιστικών είναι η καλύτερη.

Αυτή η δραματική βελτίωση δεν σημαίνει ότι δεν χρειάζεται να δίνεται προσοχή σε παράγοντες όπως ο παράγοντας ομαδοποίησης και στη δομή του αρχείου δεδομένων. Αυτά τα στοιχεία επηρεάζουν τις σταθερές των στατιστικών του συστήματος όπως συμβαίνει πάντα. Προσεκτικές επιλογές θα αυξήσουν την συνολική αποτελεσματικότητα του συστήματος.