File Structures With Ada (Benjamin Cummings Series in Computer Science) - Hardcover

Miller, Nancy E.; Petersen, Charles G.

Hardcover

ISBN 10: 0805304401 ISBN 13: 9780805304404

Publisher: Benjamin-Cummings Pub Co, 1990

Synopsis

Provides an overview of file design and manipulation and discusses Ada records and files, blocking and buffering, secondary storage devices, search trees, and various types of file organization

About this title

About the Author

About Charles G. Petersen

Charles Petersen holds a bachelor's degree in Electrical Engineering and is a registered professional engineer. He worked for 10 years in industry before returning to graduate school to complete a master's degree in Computer Science. He received his Ph.D. from Iowa State University in Higher Education and has been teaching computer science at the university level since 1972. He is the author of three other computer science textbooks and several articles dealing with computer science topics and curriculum issues.

From the Back Cover

File Structures with Ada gives you all the tools you will need to design files in Ada that are more reliable and easy to maintain. Of the modern production languages, Ada provides the most comprehensive features for file design. This book shows you how to use Ada to implement abstract data types naturally and handle sequential and random access non-text files. Also, you will learn how to use Ada's encapsulation capability to build basic file structure packages that can be used again with only small modifications. Realistic case study examples are fully implemented and all the file structures are coded in validated Ada to eliminate portability problems. Features: Implements a realistic case study for each file structure discussed. Uses real Ada code in each case study. Provides abundant examples and illustrations, as well as detailed algorithims in Ada-like pseudocode. Inlcudes an optional overview of Ada. Provides a complete appendix to all Ada I/O package specifications from the Ada Reference Manual.

From the Inside Flap

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, such as Pascal, with less support for file organizations, would allow students to gain greater computer science knowledge concerning the implementation of data structures on external files. Pascal is an excellent pedagogical language, but it is not in widespread use by industry as a production language. Ada, on the other hand, provides more support for files than either Pascal or COBOL. An additional plus for Ada is that it is a bona fide production language whose use is appearing more and more in software applications inside and outside the Department of Defense. Among all the commonly used production languages, Ada has the most comprehensive features for file design. Ada features, such as packages, generics, and exceptions, aid for utilizing the software engineering concepts of data abstraction and information hiding. All these features allow for the design of files that are more reliable and more easily maintained. 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 textbook is to study the external data structures necessary for implementing different file organizations. Ada supports sequential and random access files. The Ada programming language can be used in a more practical pedagogical 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 an Ada-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 stacks, queues, linked lists, and trees are studied and analyzed for efficient use in the implementation of various file organizations. By using a superior pedagogical language such as Ada and analyzing key data structures, students will gain a better understanding of design analysis and the implementation of file organization. Level/Audience/Prerequisites A four-year college or university with a computer science curriculum is one of the intended audiences of this book. The prerequisites are two semesters of computer programming, namely CS1 and CS2, with at least one of those semesters being devoted to Ada programming. The primary audience is third-semester computer science majors. Many data processing applications are now being written in Ada. The professional data processor and systems analysts will find many of the concepts used in Ada to be superior to those of COBOL and PL/I. Other computing professionals involved in or interested in software contracts with the Department of Defense will find the information presented in this book to be invaluable. 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 record variants and for declaring and accessing test and sequential nontext files in the Ada programming language. The input-output subprograms and their associated exceptions are covered. This chapter may be omitted for those students with a good understanding of the Ada programming language. Chapter 3 deals with the topics of blocking and buffering of records in a file. The central theme of the chapter is the reduction in the number of 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 the Ada programming language. 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. 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 there are a variety of examples and algorithms accompanied by numerious figures and tables. Students have found these to be very helpful for independent study. Algorithms/Exercises: Throughout the book algorithms are presented in Ada-like pseudocode. Students learn best by working with a variety of file 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. Solutions to all exercises are provided in the Solutions Manual. 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 Ada Chapter 2 reviews the Ada syntax for declaring, using, and accessing Ada records and files. A review of Ada packages, test I/O, and exceptions is also included. This chapter can be omitted for those students with a good understanding of the Ada programming language. Chapter 3 introduces tasking as a tool for implementing double buffering. Chapter 5 introduces Package Sequential_IO for creating and accessing sequential files for Ada. Chapter 7 introduces Package Direct_IO for creating and maintaining randon-access files in Ada. Appendix A is from the Military Standard of the Ada Programming language (ANSI/MIL-STD-1815A). All case studies involving the car-rental agency are implemented in Ada and included as Appendix B. Software All the solutions to the programming problems at the end of each chapter along with the data sets used to test these Ada programs may be purchased by adopting instructors and nonacademic professionals from the authors for a fee of $35.00. The programs have been compiled and tested with the Meridian AdaVantage compiler version 2.2 that runs under MS-DOS or PC-DOS. Please make the check or purchase order payable to "NANCY E. MILLER." Upon receipt of the fee, the purchases will be mailed a diskette (either 5.25" (HD or DD) or 3.5") that contains all the solutions and data sets in ASCII text form. Please specify the size diskette required. Correspondence may be directed to:

Nancy E. Miller

Computer Science Department

P.O. Drawer CS

Mississippi State University

Mississippi State, MS 39762

phone: (601) 325-2756

E-MAIL: miller@cs.msstate.edu Solutions Manual The accompanying Solutions Manual includes: solutions to all exercises in the book guidelines for the special challenges teaching Ada assumes. Acknowledgements We are grateful to the numerous individuals that have helped us in preparing this book. We are indebted to Meridian Software Systems, Inc. for providing the AdaVantage compiler used in testing all Ada software accompanying the book. Our thanks also go to the reviewers: Grady Booch, Victor Meyer, Charlene Hayden, and Jaime Nino. We express our appreciation to our editor, Alan Apt, and to all those individuals at Benjamin/Cummings who have organized the reviewing and production of this book.

Edition details

• Publisher: Benjamin-Cummings Pub Co
• Publication date: 1990
• Language: English
• ISBN 10: 0805304401
• ISBN 13: 9780805304404
• Binding: Hardcover
• Edition number: 1
• Number of pages: 600