The Databases Course

Exercise No. 9

Transitive Closure - Practical

Due on January 25th by midnight

The Example Database Schema: A manufacturing firm buys basic parts and builds composite parts out of them. There is a cost to every basic part, and a cost to assembling a composite part out of all its basic parts (which doesn't include the cost of the basic components). Composite parts may be composed from other composite parts as well. The information about parts is stored in the Base_Parts and Composite_Parts tables, and the Made_From relation specifies which and how many basic parts each composite part needs. Made_from(car, wheel, 4) indicates that a car is made using four wheels.

Base_Parts (pno, cost)
Composite_Parts (pno, assembly_cost)
Made_From (pno1, pno2, qty)

Standard assumptions can be made about the database:

• No part number appears both in Base_Parts and Composite_Parts.
• 'pno' is a key for Base_Parts and for Composite_Parts.
• 'pno1' and 'pno2' together form a key for Made_From.
• All part numbers in Made_From appear in either Base_Parts or Composite_Parts.
• The graph corresponding to Made_From is acyclic, but it is not necessarily a tree. This means that we might have, for example:
  Made_From(car, wheel, 4), Made_From(bike, wheel, 2), Made_From(wheel, tire, 1), ...
• All basic parts have no children in the graph.
• All composite parts have at least one child in the graph.
• Some of the new parts (both base and composite) have been inserted into the database without a cost, because it is still under negotiation. Therefore, there may be null values in the cost field of these tables.
• No composite part is composed of basic or composite parts with null values.

Write a C program with embedded SQL statements to do the following:

You should compute the relation Costs(pno, total_cost), where total_cost is the total cost for making part pno - including the costs of all the base parts and the costs of assembling the composite parts. This relation should contain a record for every part (both basic and composite). The Costs table should be created as a new table - pno is of type varchar(15) and total_cost is of type number(10). These are also the types that are used by the existing tables. Your program should create and fill the Costs table, print it to the screen, and destroy it.

Your should use a reasonable amount of main memory space, since the above relations can be very large. You may use tables to store intermediate results. Tuples containing null values should be ignored - such parts needn't be used in your computations, and shouldn't appear in the final Costs table.

The input size of this problem is the total number of parts n. Your algorithm should use at most O(log n) queries. Every SELECT statement counts as one query; when using cursors, every time you OPEN the cursor it counts as one query.

When encountering any type of error you should print a detailed message to the standard error stream, and terminate the program emmidiately with an error code 1. If the program ends without an error, it should return an error code 0.

Your program should be superbly documented. Your README file, along with the usual information, must also include the pseudo-code for the algorithm you use, and an analysis of the number of queries it performs.

You should submit:

• Submit electronically (run ~db/bin/submit to submit ex4.tar) the following files:
  README - containing only your login on the first line, and your full name and relevant exercise documentation afterwards. Specifically, this include the pseudo-code and run-time analysis of the algorithm you use.
  Makefile - When running 'gmake', exactly one executable named 'ex4' should be created.
  ex4.out - An example output of your program, on the example Oracle database.
  ex4.pc - The program's source code.
  If you have more source files, specify their names in the README file.
• Submit printouts of everything, except the Makefile, to the course's submission box.