Το σύστημα αρχείου αναλαμβάνει το έργο του υπολογισμού της διεύθυνσης του τομέα (sector), του block που περιέχει τη συγκεκριμένη εγγραφή, καθώς και να διαβάσει/γράψει το block. Όσον αφορά τον προγραμματιστή η διεύθυνση της εγγραφής είναι ο αριθμός της εγγραφής. M’ αυτή την έννοια τα σχετικά αρχεία μοιάζουν με πίνακα μιας διάστασης, όπου κάθε στοιχείο του πίνακα είναι μια εγγραφή και ο δείκτης της γραμμής του πίνακα είναι ο αριθμός εγγραφής.

Οι αριθμοί εγγραφής μπορούν να χρησιμοποιηθούν ως κλειδιά για τα δεδομένα του αρχείου. Π.χ. μια εταιρεία αντιστοιχεί τους αριθμούς εγγραφής στους υπαλλήλους της. Βέβαια υπάρχουν αρκετές συναρτήσεις που μπορούν να μετατρέψουν ένα εξωτερικό κλειδί, όπως το “όνομα” σε αριθμό εγγραφής.

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

SA=FA+(RN/B)SPB

SA= διεύθυνση τομέα

FA= διεύθυνση τομέα του πρώτου block του αρχείου

RN= αριθμός εγγραφής της επιθυμούμενης εγγραφής

B= εγγραφές ανά block

SPB= πλήθος τομέων ανά block

OPEN

CLOSE

READ-NEXT

READ-DIRECT

WRITE-DIRECT

EOF

VALID

Σε σχέση με τα σειριακά αρχεία μπορούν να εφαρμοσθούν οι ίδιες βασικές πράξεις εκτός από την Append. Αντί για την append μπορούμε να γράψουμε αλλά και να διαβάσουμε οποιαδήποτε εγγραφή του αρχείου.

Σημείωση

Η δυνατότητα να γράψουμε/διαβάσουμε σ’ οποιοδήποτε μέρος στο αρχείο έχει ως συνέπεια 2 περιορισμούς που πρέπει να λαμβάνονται υπόψη στα σχετικά αρχεία.

1. Μια εγγραφή δεν μπορεί να αναγνωσθεί αν δεν έχει πρώτα γραφεί. Πράγμα που είναι λογικό να συμβαίνει. Έτσι δημιουργείται μια ασυνήθης συνθήκη (exceptional condition) παρόμοια με τη συνθήκη λάθους (error condition) αν επιχειρήσουμε να διαβάσουμε μια εγγραφή που δεν υπάρχει. Έτσι όταν το αρχείο δημιουργείται το σύστημα αρχείου «σημειώνει» όλες τις θέσεις εγγραφών ή τις «σχισμές» (slots) ως ελεύθερες. Οταν μια εγγραφ’η αποθηκεύεται σε μια θέση, η θέση θεωρείται καταλυμένη και η εγγραφή στη συνέχεια μπορεί να αναγνωσθεί. όμοια, μια εγγραφή μπορεί να διαγραφεί σημειώνοντας την ως άδεια.

2. Ο αριθμός εγγραφής πρέπει να κυμαίνεται από 0 έως n-1(ή από 1 έως n), μια και εκτός αυτής της κλίμακας δεν υπάρχουν αριθμοί εγγραφής και έτσι αν επιχειρήσουμε να προσπελάσουμε εγγραφές με αριθμό εγγραφής μεγαλύτερο του n-1 (ή n) θα προκύψει λάθος.

Εγγραφές μπορούν να προστεθούν στο αρχείο οποιαδήποτε στιγμή. Χρησιμοποιείται η πράξη WRITE-DIRECT. Το πρόγραμμα θα πρέπει να ελέγχει αν επιχειρείται να προστεθεί εγγραφή σε θέση που έχει ήδη χρησιμοποιηθεί για την αποθήκευση κάποιας άλλης εγγραφής.

• Διαγραφή

Οι εγγραφές σημειώνονται ως διαγραμμένες. Χρησιμοποιείται η πράξη WRITE-DIRECT. Μια και οι διαγραμμένες εγγραφές μπορούν να ξαναχρησιμοποιηθούν δεν χρειάζεται να εφαρμόσουμε περιοδικά αναδιοργάνωση όπως χρειαζόταν στα σειριακά αρχεία.

• Ανάγνωση όλων των εγγραφών του αρχείο χωρίς μια συγκεκριμένη σειρά

Αυτή η λειτουργία δεν διαφέρει σημαντικά από την αντίστοιχη διαδικασία για τα σειριακά αρχεία (Αλγόριθμος 1_2). Βέβαια μπορεί να χρησιμοποιηθεί και η READ-DIRECT και να αυξάνουμε τον αριθμό εγγραφής κατά 1. Θα πρέπει να ελέγχεται η περίπτωση των άδειων σχισμών (empty slots) για να μην διαβάζονται και οδηγηθούμε σε exceptional condition.

• Ανάγνωση όλων των εγγραφών με βάση κάποιο συγκεκριμένο κλειδί

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

Αυτή η μέθοδος έχει 2 μειονεκτήματα.

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

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

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

Παράδειγμα: αν ο manager μιας εταιρείας αυτοκινήτων αντικαθιστά κάθε χρόνο όλα τα αυτοκίνητα. Έτσι κάθε φορά αντιστοιχεί έναν αριθμό σε κάθε όχημα. Αυτός ο αριθμός προκύπτει από το έτος του μοντέλου και έναν τριψήφιο αριθμό. Μια εγγραφή σχηματίζεται για κάθε όχημα έτσι ώστε τα 3 τελευταία ψηφία του αριθμού να ισούνται με τον αριθμό εγγραφής. Έτσι η σειριακή ανάγνωση του αρχείου θα έχει ως αποτέλεσμα μια λίστα με τον αριθμό κάθε αυτοκινήτου σε αύξουσα σειρά.

Αν βέβαια το αρχείο πρέπει να αναγνωσθεί με βάση κάποιο άλλο κλειδί τότε πρέπει να εφαρμοσθεί ο αλγόριθμος 1_5 με συνέπεια την αναποτελεσματικότητά του από άποψη χρόνου.

• Ανάγνωση μιας εγγραφής με βάση την τιμή κάποιου συγκεκριμένου κλειδιού

Όπως και με τα σειριακά αρχεία είναι δυνατόν να οδηγηθούμε σε 3 καταστάσεις:

• Υπάρχει ακριβώς μια εγγραφή που ταιριάζει με τη τιμή του κλειδιού.

• Υπάρχουν περισσότερες από μια εγγραφές που ταιριάζουν στη τιμή του κλειδιού.

• Δεν υπάρχει καμία εγγραφή που να ταιριάζει με τη τιμή του κλειδιού.

Οι αλγόριθμοι 1_3 και 1_5 μπορούν να χρησιμοποιηθούν αλλά μια και είναι σειριακοί είναι χρονοβόροι. Όταν όμως το κλειδί είναι ο αριθμός εγγραφής τότε μπορεί να χρησιμοποιηθεί αποτελεσματικότερος αλγόριθμος. Απλώς χρειάζεται μια READ-DIRECT πράξη.

Περίληψη

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

Υπάρχουν διάφορες τροποποιημένες εκδόσεις των σχετικών αρχείων όπως τα ταξινομημένα σχετικά αρχεία (ordered relative files) και τα άμεσης προσπέλασης αρχεία (direct access files).

Η Συμπύκνωση χώρου (storage compunction) επιτρέπει τη δημιουργία μικρότερων αρχείων μια και αναζητείται αν υπάρχει χώρος στο αρχείο που δεν περιέχει δεδομένα ώστε να ξανακαλύψουν με αυτό το χώρο με δεδομένα. Οι κενοί χώροι συνήθως δημιουργούνται στα αρχεία όταν διαγράφονται εγγραφές.

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

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

Ένας τρόπος, όπως αναφέραμε για να “σώσουμε” χώρο στο αρχείο είναι η αναδιοργάνωση του. Υπάρχουν όμως εφαρμογές που είναι χρήσιμη μια άμεση επαναχρησιμοποίηση του χώρου που καταλαμβάνουν οι διαγραμμένες εγγραφές. Έτσι αναζητείται μια δυναμική επαναχρησιμοποίηση του χώρου. Γενικά για να επαναχρησιμοποιήσουμε το χώρο που καταλαμβάνουν οι διαγραμμένες εγγραφές θα πρέπει να αναπτύξουμε ένα μηχανισμό που πραγματοποιεί τα εξής:

1. Οι διαγραμμένες εγγραφές να μαρκάρονται με ειδικό τρόπο

2. Να μπορούμε να εντοπίσουμε το χώρο που καταλαμβάνουν οι διαγραμμένες εγγραφές

Η πρώτη απαίτηση μπορεί να ικανοποιηθεί αν χρησιμοποιήσουμε ένα πεδίο με τη τιμή “*” που θα δηλώνει ότι η εγγραφή είναι διαγραμμένη.

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

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

1. Να γνωρίσουμε αμέσως αν υπάρχουν διαγραμμένες εγγραφές (empty slots)

2. Ένα τρόπο να έχουμε άμεση πρόσβαση σ’ αυτές τις άδειες “σχισμές”.

• Συνδετικές λίστες

Η χρήση συνδετικής λίστας (ΣΛ) μπορεί να ικανοποιήσει και τις 2 παραπάνω απαιτήσεις. Όπως γνωρίζουμε η συνδετική λίστα είναι μια δομή δεδομένων όπου κάθε στοιχείο της (κόμβος της ) περιλαμβάνει και την πληροφορία για το ποιο είναι το επόμενο στοιχείο της ΣΛ. Έτσι αν γνωρίζουμε την διεύθυνση του 1ου στοιχείου της ΣΛ τότε μπορούμε να προσπελάσουμε όλα τα στοιχεία της. Το τέλος της ΣΛ συμβολίζεται με ιδιαίτερη τιμή στο πεδίο που κρατάμε την πληροφορία για το ποιο είναι το επόμενο στοιχείο της ΣΛ.

Έτσι μπορούμε να διατηρήσουμε μια ΣΛ με τις διαγραμμένες εγγραφές και συνήθως αυτή τη ΣΛ την ονομάζουμε διαθέσιμη Λίστα (Avail list) και το χώρο που καταλαμβάνουν οι διαγραμμένες εγγραφές διαθέσιμο χώρο (available space). Τέλος θα πρέπει να αναφέρουμε ότι δεν υπάρχει ιδιαίτερος λόγος για να προτιμηθεί ένα στοιχείο της ΣΛ από ένα άλλο και έτσι δεν χρειάζεται να διατάξουμε τα στοιχεία της ΣΛ με κάποιο συγκεκριμένο τρόπο.

• Στοίβα

Αν διαγραφεί και η εγγραφή με αριθμό εγγραφής =3 τότε θα εισαχθεί στη κορυφή της στοίβας το στοιχείο με RN=3 και θα έχει ως επόμενο στοιχείο εκείνο με RN = 2.

Αν πάλι χρειασθεί να προσθέσουμε νέα εγγραφή αυτή θα καταλάβει την εγγραφή με RN=3.

• Συνδέοντας και στοιβάζοντας διαγραμμένες εγγραφές

Όπως ήδη είπαμε η χρήση της στοίβας εξασφαλίζει

1. ότι γνωρίζουμε αμέσως αν υπάρχουν διαγραμμένες εγγραφές

2. άμεση πρόσβαση στις άδειες σχισμές.

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

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

Ας υποθέσουμε ότι έχουμε ένα αρχείο με 7 εγγραφές (αριθμοί εγγραφής (ΑΕ) από 0-6) και ότι οι εγγραφές με ΑΕ 3 και 5 διαγράφτηκαν και οι διαγραμμένες εγγραφές σημειώνονται τοποθετώντας ένα “*” αντικαθιστώντας την τιμή του 1ου πεδίου. Στη συνέχεια μπορούμε να χρησιμοποιήσουμε το 2ο πεδίο της διαγραμμένης εγγραφής για να αποθηκεύσουμε το δείκτη της επόμενης εγγραφής της διαθέσιμης λίστας. Έτσι:

α) μετά τη διαγραφή των εγγραφών 3 και 5

β) μετά τη διαγραφή των εγγραφών 3, 5 και 1

γ) μετά την εισαγωγή 3 νέων εγγραφών

• Υλοποίηση της διαθέσιμης λίστας