Summer '95 Final Exam

Overview

Your task is to design a system that allows reservation agents to book passengers on flights operated by Air NoFrills or any of its partners. The system must keep track of seat availability, meal selection, and of course, the passenger roster. When making a reservation, passengers may specify flights by:

flight numbers, departure date, return date
item origin city, destination city, departure date, return date

Given a flight specification in the second format (by origin and destination city for a particular set of dates), your program should be able to provide a reservation agent with a list of flights with available seating, and the available fares. Once a booking is made in a passenger's name, a unique reservation number is assigned. Passengers may then make changes to their booking using this number. Unfortunately, many passengers misplace or forget their reservation numbers so your system must also be able to retrieve reservations based on:

passenger name, originating flight number, originating date
passenger name, origin city, destination city

Note that passengers may hold multiple reservations at any one time.

Queries

Air NoFrills has enormous external storage availability to deal with approximately 10^6 (one million) active reservations at any one time. Their concern is for speed, not size. Therefore, your design should provide quick access to information for most typical requests:

availability by flight number and date
availability by origin and destination city, and date
roster by flight and date
information by passenger name
information by reservation number

Reservations agents may also request more complicated searches, either in response to passenger or management requests. For example:

find all the flights from Toronto to Vancouver, departing in the first week of September and returning the following week, with at least five available seats at fares of less than $600
find a reservation based on passenger name, origin and destination city (no date specified)
find all the flights from Calgary to Edmonton, on October 13, that have less than half of the available seats booked

While your system is not expected to answer these requests very quickly, it should be able to do so reasonably efficiently. You may assume that the available main memory on the client machines used by reservation agents is at least 1 Mbyte and that the central data base disks provide data in blocks of 1024 bytes.

What to do

Describe your design of this system. Discuss what file organizations you will use, and explain your rationale for selecting each. Provide rough calculations of expected record sizes and numbers of file accesses for all of the queries listed above, as well for two non-trivial queries of your own design. Finally, re-write the three complicated queries in relational algebra. Illustrating with parse trees where appropriate, explain how these queries would be answered by your system. For full marks, you must organize your reply sensibly, and write or print neatly. If the marker finds anything difficult to read, that section will be ignored.