Visit the Author's Support Pages for Files Structures Using Pascal. 080537082XB04062001
Motivation After teaching file processing courses for years using COBOL
as the vehicle language, I concluded that the students do learn to use COBOL for a variety of file organizations (sequential, indexed sequential, and relative) but do not gain an understanding of the data structures involved in implementing the more complex file structures such as direct files and indexed sequential files. A programming language with less support for file organizations than COBOL allows the students to gain greater in-depth knowledge about the implementation of routines that access data structures on external files. Pascal, with its support for relative files, fills this need. Goal This textbook meets the requirements for The Association for Computing Machinery (ACM) course CS5 as defined in the ACM curriculum guidelines. The goal of the book is to study the external data structures necessary for implementing different file organizations. Most texts currently available present file processing by using languages such as COBOL or PL/1, which have built-in support for direct access and indexed sequential access. Pascal does not have this built-in support. Instead, this language can be used in a more practical, prdagogical way by allowing students to gain more in-depth file implementation experience as they analyze data structures for efficiency and write their own access routines. The algorithms in this book are presented in a Pascal-like pseudocode, which provides students with a familiar environment in which to study the key concepts and structures necessary to implement a variety of file organizations. Data structures such as trees, linked lists, stacks and queues are studied and analyzed for efficient use in the implementation of various file organizations. By using a superior pedagogical language such as Pascal and analyzing key data structures, students will gain a better understanding of design analysis and the implementation of file organization. Level/Audience/Prerequisites The prerequisites for the course addressed by this book, CS5, are two semesters of Pascal; in other words students should already have taken ACM CS1 and CS2 courses. Third-semester Computer Science majors constitute the primary audience for this book. Organization and Coverage Chapter 1 presents a conceptual overview of the file-processing environment, including discussions of common file organizations, file types and characteristics, and different ways of manipulating files as factors that affect file design. Several of the examples of file applications in this chapter are referenced in later chapters. Chapter 2 reviews the syntax for declaring and using records and for declaring and accessing files in Pascal. This chapter may be omitted for those students with a good understanding of Pascal records and files. Chapter 3 deals with the topics of blocking and buffering of records in a file. The central theme of the chapter is the fewer I/O operations required for a program that accesses a blocked file and the reduction of the time that the CPU waits for an I/O operation to be completed when using a buffered file. Interfacing algorithms for record blocking and deblocking are also presented. Quantitative measures of the effects of blocking and buffering effects are given solely in terms of the number of I/O accesses. Chapter 4 describes external storage devices as a background for understanding the impact of storage devices on file design and manipulation. Quantitative measures of the effects of blocking and buffering (similar to those in Chapter 3) are repeated in terms of physical access time of the devices using various blocking factors and different numbers of buffers. Chapter 5 deals with the design and maintenance of sequential files on both sequential and random-access storage devices. Algorithms for maintenance of sequential files stored on sequential devices are contrasted with algorithms for maintenance of sequential files stored on random-access devices. Sample data for a car-rental agency are used for implementating a sequential file. Quantitative measures of access times are given. Chapter 6 describes external sort/merge techniques, which are necessary for sorting very large sequential files. Sorting is a common file-processing task, especially for manipulating sequential files. Sorting methods discussed at length are the two-way merge, the balanced k-way merge, and the polyphase merge. These methods are compared in terms of the number of merge cycles and external storage devices needed for several example data sets. Chapter 7 begins with a discussion of the basic structures of direct files. A variety of techniques are presented for obtaining random access to data files, including the use of hashing. Examples are used to illustrate several methods for handling hashing collisions. Also included are some algorithms for creating and maintaining random-access files in versions of Pascal with the random-access files extension. In order to compare random and sequential access, the car-rental agency data used in Chapter 5 are stored in a random-access file and quantitative measures of access times are computed. Chapter 8 describes several types of tree structures that are useed to accessing random-access files sequentially. The most important tree structure is the B-Tree, and ways of representing and manipulating the B-tree are discussed along with accompanying algorithms. The chapter also discusses the application of trees that allow sequential and random access to the car-rental agency data file created in Chapter 7. Chapter 9 describes common implementations of indexed sequential organization, including implementations that use a tree structure, such as a B+-Tree, for the indexes. The chapter studies Scope Indexed Sequential files used on CDC computers, cylinder-and-surface-indexed sequential files (ISAM) used on IBM computers, and VSAM file organization used on IBM computers. Also included are algorithms for implementing indexed sequential files using a variety of data structures. Applications include the car- rental agency data, and access times for sequential, random, and indexed sequential files are compared. Chapter 10 investigates other types of file organization that use linked lists or tree structures to provide multiple-key access to random-access data files. Included in this chapter is a discussion of inverted files and multilist files along with creation and manipulation algorithms. The car-rental agency data are implemented as an inverted file and multilist files to provide access by several keys. Quantitative measures of access times are given by comparing these file organizations with others discussed previously. Outstanding Features Pedagogy Case Studies: Chapter 5 introduces a case study based on an actual car-rental agency, and this case study is used throughout the book as an on-going example illustrating practical file concepts and issues. Additional practical, real-world case studies are presented in Chapter 2. They include discussions of an inventory of products, student class schedules, and the assignment of course grades for a class. Examples/Illustrations: Throughout the book algorithms are presented in Pascal-like pseudocode. Students learn best by working with files of varying organizations rather than just reading about them. A variety of exercises and programming projects have been provided that illustrate the creation and manipulation of files for each type of organization. Students can implement the algorithms from the book in a hands-on, file organization programming environment, thus gaining experience and greater knowledge of all key concepts. The program solutions for these exercises are available from the author. Solutions to odd- numbered exercises are provided at the back of the book while the solutions to even-numbered exercises are provided in the Instructor's Guide. Glossary/Key Terms: Key terms are highlighted and defined as they occur in the test, and are also included in the glossary in the end of the book. Class Tested: This book was thoroughly class tested for six semesters in a sophomore-level file structures course. The readability of the book was greatly enhanced because of student and reviewer feedback over the course of several drafts. The Use of Pascal Chapter 2 reviews the Pascal syntax for declaring, using, and accessing Pascal records and files. This chapter can be omitted for those students with a good understanding of Pascal. The Pascal syntax for records, linked lists and trees is included in corresponding sections. The first two sections of the book (I and II) reference the ISO standard Pascal, while sections III and IV require random-access files, which are not included in the ISO standard. Most versions of Pascal have been extended to allow random access (OMSI Pascal, TURBO Pascal, UCSD P-System Pascal, and VAX-11 Pascal, to name a few). Appendix A includes a sequential simulation of random access using arrays in intern
