(10278 mod 411) + 1 = 3 + 1 = 4 (09222 mod 411) + 1 = 2 + 1 = 3 (20553 mod 411) + 1 = 3 + 1 = 4 (17256 mod 411) + 1 = 405 + 1 = 406
. . .
09222 10278 20553
CHAPTER 13
File Structures
(Solutions to Practice Set)
Review Questions
1. The two access methods are sequential and random. 2. The old master file is the file that should be updated; the new master file contains the current data (the data from the old master file including any changes that were made during the update process). 3. The transaction file contains changes that should be made to the old master file. 4. To access a record in a file randomly, we need to know the address of the record. 5. The index is a table that relates the keys of the data items to the addresses in the file where the data are stored. 6. In direct hashing, the key is the address of the record in the file. 7. In modulo division hashing, the key is divided by the file size. The remainder plus 1 is used as the address of the record in the file. 8. In digit extraction hashing, certain digits are removed from the key and used as the address of the record. 9. A collision occurs when two hashed record have the same address. The three collision methods are open addressing, linked list resolution, and bucket hashing. In open addressing, the prime area is searched for an unoccupied address. In linked list resolution, the first record is stored in the home address, but it contains a pointer to the second record. In bucket hashing, a group of records are stored in a buckets which are locations that can accommodate more than one record. 10. A text file is a file of characters while a binary file is a collection of data stored in the internal format of the computer.
. . .
406
17256
36. The result of linked list resolution is shown in Figure S13.36. Figure S13.36 Exercise 36
Address Key Link
(10278 mod 411) + 1 = 3 + 1 = 4 (09222 mod 411) + 1 = 2 + 1 = 3 (20553 mod 411) + 1 = 3 + 1 = 4 (17256 mod 411) + 1 = 405 + 1 = 406
TR OR
Read TF Read OF
Stop
For simplicity, we assume that there is no discrepancy between OF and TF, which means that there is no need to create an error file. The routine follows the logic in the solution to Exercise 37. The loop will terminate when both files have reached their dummy records. The process, however, needs three decision branches. If the there is no transaction for a record (OR.k < TR.k), the record in the old master file is copied to the new transaction file. If there is a new record in the transaction file to be inserted into the new master file (OR.k > TR.k), then the routine simply writes that record. If (OR.k = TR.k), it means that a record needs to be either partially changed or totally deleted. In the case of deletion, no action is needed. In the case of change, the record in the old master file is updated and written to the new master file. Note that the routine works correctly if the transaction file is empty (having only one dummy record). This may happen, if at the end of the updating period, there is no changes to the old master file. The old master file is simply copied to the new master file. The routine also works correctly if the old master file is empty (creation of a new file).
New Master File Key 14 16 17 26 31 89 90 92 Name John Wu George Brown Duc Lee Ted White Joanne King Mark Black Orva Gilbert Betsy Yellow Pay Rate 17.00 18.00 11.00 23.00 28.00 19.00 20.00 14.00 Action A Key 17 Error File Name Martha Kent
Stop
38. Algorithm S13.38 shows the routine in pseudocode. Algorithm S13.38 Exercise 38
Algorithm: MergeFile (F1, F2, Sentinel) Purpose: It merges two sequential files Pre: Given F1 and F2 and the Sentinel Post: Return: A new File (NF) { R1 ← Read F1 R2 ← Read F2 while ((R1.k < Sentinel) OR (R2.k < Sentinel)) { if (R1.k < R2.k) { Write R1 to NF R1 ← Read F1 } else { Write R2 to NF R2 ← Read F2 } } return NF }
Address 003 004 005 Key
1422 = 20164 → 16 1252 = 15625 → 62 1342 = 17956 → 95 1532 = 23408 → 40 14 + 22 = 36 12 + 57 = 69 13 + 49 = 62 15 + 32 = 47 41 + 22 + 43 = 106 21 + 57 + 11 = 89 31 + 49 + 91 = 171 51 + 32 + 31 = 114
1
2
Multiple-Choice Questions
11. d 17. a 23. a 12. a 18. c 24. c 13. a 19. d 25. a 14. d 20. a 26. d 15. c 21. d 27. d 16. a 22. b 28. a