Άσκηση 2 - K18 - Υλοποίηση Συστημάτων Βάσεων Δεδομένων Χειμερινό Εξάμηνο 2021 – 2022

Μέλη ομάδας:

Μουτσάτσος Αριστείδης - 1115200600110
Νικολάου Γεώργιος - 1115202000154
Δραβίλας Ιωάννης - 1115201900053

hash_file

Γενική Περιγραφή

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

Γενική Δομή

Η δομή των αρχείων επεκτατού κατακερματισμού που δημιουργούνται είναι η εξής:

Block_0: | HASH_ID | GLOBAL_DEPTH |
Block_1: | HASH_TABLE ........... |
Block_k: | .....END_OF_HASH_TABLE |
(k=2^i)
Block_{k+1}: | HEADER, RECORDS |
...
Block_n

__HASH_ID__: Αναγνωριστικό string που δηλώνει ότι το συγκεκριμένο αρχείο είναι ένα αρχείο επεκτατού κατακερματισμού που έχει δημιουργηθεί από το παρόν πρόγραμμα.

__HEADER__ = LOCAL_DEPTH, NUMBER_OF_RECORDS, INDEXES, PREFIX

__INDEX__: Μια σειρά από bits που σηματοδοτεί εάν η εγγραφή που αντιστοιχεί στο κάθε bit χρησιμοποιείται ή όχι, και άρα αποτελεί διαθέσιμο χώρο για νέα εγγραφή.

Κάθε INDEX έχει μέγεθος 8 bit και μπορούμε να έχουμε όσα indexes χρειάζονται ανάλογα με το μέγεθος των records, δηλαδή πόσα χωράνε στο block.
Π.χ.    για max 7 εγγραφές έχει 1 INDEX με μέγεθος 1 byte
        για max 8 εγγραφές έχει 1 INDEX με μέγεθος 1 byte
        για max 9 εγγραφές έχει 2 INDEX με μέγεθος 1 byte το καθένα και συνολικό μέγεθος 2 byte

__PREFIXES__: Ο συνδυασμός most significant bits (με πλήθος που δίνεται από το local depth), ο οποίος ορίζει κάθε φορά τα κλειδιά του ευρετηρίου τα οποία δείχνουν στο ίδιο bucket.

Τεχνικές Λεπτομέρειες

• Επιλέχθηκε τα blocks του ευρετηρίου να είναι συνεχόμενα στην αρχή του αρχείου μετά το block 0 προκειμένου να έχουμε όσο το δυνατόν γρηγορότερη αναζήτηση. Ως εκ τούτου, η διαδικασία του expand είναι πιο χρονοβόρα, καθώς αντιγράφονται όσα block χρειάζεται μετά το τέλος του αρχείου, προκειμένου το ευρετήριο να επεκταθεί. Αυτό, ωστόσο, δεν αποτελεί σημαντικό πρόβλημα, καθώς το expand είναι μια σπάνια διαδικασία.

• Κατά τη διαδικασία του split, όταν πραγματοποιείται το rehashing των εγγραφών του bucket και πρέπει η εγγραφή να εισαχθεί στο καινούριο bucket, δεν διαγράφεται από το παλιό, αλλά απλώς μηδενίζεται το bit που αντιστοιχεί σε αυτή στο index του αρχικού block. Επιλέχθηκε αυτή η προσέγγιση για γρηγορότερη απόδοση.

• Χρησιμοποείται hash function με την τεχνική most significant bit, η οποία αντιστρέφει τη σειρά των bit του αριθμού που δίνεται κι έπειτα επιστρέφει τα πρώτα k (k=global depth) bit του.

• Οι εγγραφές γράφονται ανά πεδίο συνεχόμενα μέσα στο block (όχι ολόκληρο το struct ταυτόχρονα), για να αποφευχθεί το padding του compiler.

• Το update γίνεται μέσω ενός struct UpdateRecordArray στο οποίο αποθηκεύονται όλες οι πληροφορίες που χρειάζονται ώστε να ενημερωθεί σωστά το δευτερεύον ευρετήριο. Η διαδικασία της insert στο πρωτεύον ευρετήριο, εφόσον υπάρχει δευτερεύον ευρετήριο ακολουθείται από update κι έπειτα insert στο δευτερεύον ευρετήριο. Μετά την insert πρέπει να ελευθερωθεί η μνήμη που έχει δεσμευτεί για το UpdateRecordArray.changed_tuples, ανεξαρτήτως αν υπάρχει δευτερεύον ευρετήριο ή όχι.

Επιπλέον Συναρτήσεις

Έχουν υλοποιηθεί επιπλέον 6 βοηθητικές συναρτήσεις:

• memcpy_rec(): Γράφει ένα record στο κομμάτι data ενός block
• memcpy_to_rec(): Γράφει από το κομμάτι data ενός block σε ένα record
• expand_dir(): Επεκτείνει το ευρετήριο (hash table)
• split_bucket(): Χωρίζει το bucket
• find_prefixes(): Βρίσκει το διάστημα των buddy buckets
• print_record(): Εκτυπώνει μια εγγραφή
• significant_hash(): Η hash function που χρησιμοποιείται για τη δομή

Παραδοχές

• μέγεθος κάθε bucket = μέγεθος 1 block -(μείον) μέγεθος header του block που περιέχει το bucket
• Η δομή μπορεί να διαχειριστεί διπλότυπα (σε πλήθος το πολύ με τη max χωρητικότητα ενός bucket), όπως περιγράφηκε σχετικά στο eclass, συνεπώς δεν υπάρχει έλεγχος αν εισαχθούν περισσότερα διπλότυπα. Σε αυτήν την περίπτωση θα συνεχίζεται το expand μέχρι να γεμίσει η στοίβα, οπότε το πρόγραμμα δεν θα λειτουργήσει σωστά.

Επιπλέον λειτουργικότητες

• Η παρούσα δομή μπορεί να διαχειριστεί οποιουδήποτε μεγέθους εγγραφές με τα ίδια πεδία με την αρχική εγγραφή, με την προϋπόθεση ότι χωρά τουλάχιστον μια εγγραφή σε 1 bucket.

secondary_hash_file

Γενική Περιγραφή

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

Γενική Δομή

Η δομή των αρχείων επεκτατού κατακερματισμού που δημιουργούνται είναι η εξής:

Block_0: | SECONDARY_HASH_ID | GLOBAL_DEPTH | ATTRIBUTE_LENGTH | ATTRIBUTE_NAME | PRIMARY_FILENAME | Block_1: | HASH_TABLE ........... | Block_k: | .....END_OF_HASH_TABLE | (k=2^i) Block_{k+1}: | HEADER, RECORDS | ... Block_n

__SECONDARY_HASH_ID__: Αναγνωριστικό string που δηλώνει ότι το συγκεκριμένο αρχείο είναι ένα αρχείο επεκτατού κατακερματισμού που έχει δημιουργηθεί από το παρόν πρόγραμμα.

__ATTRIBUTE_LENGTH__: Έχει υλοποιηθεί, αλλά δεν χρησιμοποιείται καθώς γίνεται χρήση macro.

__ATTRIBUTE_NAME__: Το όνομα του πεδίου πάνω στο οποίο έχει δημιουργηθεί το δευτερεύον ευρετήριο. Επιτρέπονται μόνο "surname" και "city", όπως περιγράφεται στην εκφώνηση.

__PRIMARY_FILENAME__: Το πρωτεύον ευρετήριο στο οποίο ανήκει το δευτερεύον.

__HEADER__ = LOCAL_DEPTH, NUMBER_OF_RECORDS, INDEXES, PREFIX

__INDEX__: Μια σειρά από bits που σηματοδοτεί εάν η εγγραφή που αντιστοιχεί στο κάθε bit χρησιμοποιείται ή όχι, και άρα αποτελεί διαθέσιμο χώρο για νέα εγγραφή.

Κάθε INDEX έχει μέγεθος 8 bit και μπορούμε να έχουμε όσα indexes χρειάζονται ανάλογα με το μέγεθος των records, δηλαδή πόσα χωράνε στο block.
Π.χ.    για max 7 εγγραφές έχει 1 INDEX με μέγεθος 1 byte
        για max 8 εγγραφές έχει 1 INDEX με μέγεθος 1 byte
        για max 9 εγγραφές έχει 2 INDEX με μέγεθος 1 byte το καθένα και συνολικό μέγεθος 2 byte

__PREFIXES__: Ο συνδυασμός most significant bits (με πλήθος που δίνεται από το local depth), ο οποίος ορίζει κάθε φορά τα κλειδιά του ευρετηρίου τα οποία δείχνουν στο ίδιο bucket.

Τεχνικές Λεπτομέρειες

• Επιλέχθηκε τα blocks του ευρετηρίου να είναι συνεχόμενα στην αρχή του αρχείου μετά το block 0 προκειμένου να έχουμε όσο το δυνατόν γρηγορότερη αναζήτηση. Ως εκ τούτου, η διαδικασία του expand είναι πιο χρονοβόρα, καθώς αντιγράφονται όσα block χρειάζεται μετά το τέλος του αρχείου, προκειμένου το ευρετήριο να επεκταθεί. Αυτό, ωστόσο, δεν αποτελεί σημαντικό πρόβλημα, καθώς το expand είναι μια σπάνια διαδικασία.

• Κατά τη διαδικασία του split, όταν πραγματοποιείται το rehashing των εγγραφών του bucket και πρέπει η εγγραφή να εισαχθεί στο καινούριο bucket, δεν διαγράφεται από το παλιό, αλλά απλώς μηδενίζεται το bit που αντιστοιχεί σε αυτή στο index του αρχικού block. Επιλέχθηκε αυτή η προσέγγιση για γρηγορότερη απόδοση.

• Χρησιμοποείται hash function με την τεχνική most significant bit, η οποία αντιστρέφει τη σειρά των bit του αριθμού που δίνεται κι έπειτα επιστρέφει τα πρώτα k (k=global depth) bit του.

• Οι εγγραφές γράφονται ανά πεδίο συνεχόμενα μέσα στο block (όχι ολόκληρο το struct ταυτόχρονα), για να αποφευχθεί το padding του compiler.

• Στη συνάρτηση SHT_SecondaryUpdateEntry() για κάθε εγγραφή που άλλαξε στο πρωτεύον ευρετήριο, βρίσκεται η εγγραφή που αντιστοιχεί στο δευτερεύον του, και αλλάζει το tupleId κατάλληλα.

• Στη συνάρτηση SHT_InnerJoin() το αποτέλεσμα εκτυπώνεται ως εξής:

  • Πρώτα εκτυπώνεται το κοινό κλειδί από το πρωτεύον 1, μετά το κοινό κλειδί από το πρωτεύον 2
  • Έπειτα τα 3 υπόλοιπα πεδία του πρωτεύοντος 1
  • Στο τέλος τα 3 υπόλοιπα πεδία του πρωτεύοντος 2

Επιπλέον Συναρτήσεις

Έχουν υλοποιηθεί επιπλέον βοηθητικές συναρτήσεις, εκτός από τις ζητούμενες, οι οποίες είναι μέσα στο sht_file.c:

Παραδοχές

• μέγεθος κάθε bucket = μέγεθος 1 block -(μείον) μέγεθος header του block που περιέχει το bucket
• Η δομή μπορεί να διαχειριστεί διπλότυπα (σε πλήθος το πολύ με τη max χωρητικότητα ενός bucket), όπως περιγράφηκε σχετικά στο eclass, συνεπώς δεν υπάρχει έλεγχος αν εισαχθούν περισσότερα διπλότυπα. Σε αυτήν την περίπτωση θα συνεχίζεται το expand μέχρι να γεμίσει η στοίβα, οπότε το πρόγραμμα δεν θα λειτουργήσει σωστά.
• To FILENAME και το ATTRIBUTE_NAME, όταν δίνονται, σε συνδυασμό με τα υπόλοιπα στοιχεία του block0, δεν θα ξεπεράσουν τη χωρητικότητα του block (=512).

Επιπλέον λειτουργικότητες

• Η παρούσα δομή μπορεί να διαχειριστεί οποιουδήποτε μεγέθους εγγραφές με τα ίδια πεδία με την αρχική εγγραφή, με την προϋπόθεση ότι χωρά τουλάχιστον μια εγγραφή σε 1 bucket.

• Η συνάρτηση SHT_InnerJoin() μπορεί να εκτελεστεί και σε διαφορετικές στήλες του πρωτεύοντος 1 και του πρωτεύοντος 2, π.χ. πρωτεύον1.surname = πρωτεύον2.city.

Μεταγλώττιση και εκτέλεση των τεστ που υλοποιήσαμε

cd examples/test_cases
make tests

Μεταγλώττιση και εκτέλεση της sht_main που υλοποιήσαμε

make run

στο αρχικό directory.