Homework. All numbered homework problems are from the text.
Due Tuesday 1/13: Exercise 2.6 p 53.
Due Tuesday 1/20: Exercises 3.8 and 3.16 pp 96 and 97.
Due Tuesday 1/27. Exercise 4.4 p. 128. Also, using a schema that answers exercise 3.16 write relational algebra queries for the following.
Which airplane models are supported? (Build a table containing the names of the models.)
Which technicians are expert in which models? (Build a table containing the technician names and SSNs and the model names.)
Which technicians have ever tested a Boeing 747? (Build a table containing technician names.)
Which technicians have never tested a Boeing 747 (Build a table containing technician names.)
Which airplanes were tested by a technician who has not had a medical exam in the past 6 months. (Build a table containing airplane registration number, test FAA test number, and technician name.)
Let us say that technicians T1 and T2 are interchangeable if they are expert in the same models, i.e., that T1 is expert in all the models in which T2 is expert and vice versa. List all the pairs of interchangeable technicians. (Build a table containing the pairs of names.) Don't allows two rows that have the same pair but in the reverse order as another row. One way to accomplish this is to set up your query to require that T1's SSN be less than T2's SSN.
Due Tuesday 2/3. Exercise 5.2, p. 175, questions 1, 2, 3, 4, 7, 8, 9. In each case, write both SQL and relational algebra queries. Number 8 asks for suppliers who supply either a red part or a green part (or both). Number 9 asks for suppliers who supply both red and green parts.
Due Tuesday 2/10. Exercise 5.4. If possible construct both SQL and relational algebra answers. If you cannot construct relational algebra answers, explain why.
Due Tuesday 2/17. Exercise 8.2.
Due Tuesday 2/24. (This is a programming assignment. Please write and submit executable code.) Modify ExternalMergeSort.java in three ways.
Instead of a 2-way merge, make it a k-way merge, where k is an input parameter.
Implement replacement sort for pass 0 as described in Section 13.3.1 (p. 428). Assume that you have a two-page working area instead of a one-page working area. There are two approaches. In both approaches, start by reading the first two pages into the working area. Both cases involve a loop. The only difference is how you determine the next element to write out to the current run.
- Search through the working area for the smallest element. Write that element to the output run. Repeat until you have room for the next page in the working area. Read it in and continue until all the elements in the working area are smaller than the last element in the current run and there is insufficient room to read a new page. Then start a new run.
- Use Arrays.sort() to sort the working area. Find the smallest element in the working area that is larger than the last element in the current run. Write it and all following elements of the working area to the current run. Read in the next page if there is enough room. Repeat until there is insufficient room in the working area to read another page. Then start a new run.
- During the first (sorting) pass, work with multiple runs at once up to a limit of m--i.e., work with an array of m runs instead of just one run. Start with one active run in the array. Whenever an element appears in the working area that is smaller than the last element in all the active runs, start a new run. When writing an element out to a run, write it to the run that has the largest last element that is less than or equal to the element to be written. When all m runs are active and yet another new run is needed, close the run with the largest last element and replace it with a new run.
One way to implement this approach is to keep two arrays: an array of runs and an array of the last element in each run. For simplicity, you may assume that the "last" element in a non-active run is the smallest int value (Integer.MIN_VALUE in Java).
Due Tuesday 3/2. Exercises 16.2 parts 1 and 2 and 17.4 parts 1 - 5.
Due Tuesday 3/9.
- Exercise 19.6.
- Prove that Armstrong's Axioms imply Decomposition (p. 613).
- Exercise 19.18 parts 1 and 4.
- Exercises 19.8, 19.10, 19.12, and 19.24.