The Databases Course

Exercise No. 8

Transitive Closure - Practical

Due on February 18th by midnight

The Example Database Schema: Animals participate in research projects, that may span several years and sites in many countries. The children table keeps parenthood relations between animals, by keeping the animal id of each parent and child.

Animal(aid, species, weight, birthyear)
Children(parent, child)

The aid attribute is a key to the animals table. You may assume that if an animal id appears in the children table, it appears in the animals table as well, and that there are no circles in the children relation. There are no null values in the children table or in the aid and species fields of the animals table, but the weight and birth years of some animals may be missing.

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

Compute the relation Dynasty(aid, avg_weight, avg_age). For every animal in the animals table, this relation should include its id, the average weight of all its ancestors including itself, and the average age in which its ancestors became parents. Ancestors include parents, parents of the parents, and so forth recursively. Create the new relation as a table, whose aid field is of type varchar(5) and whose two other fields are of type number(10). Your program should create the Dynasty 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 still appear in the output table, but the missing fields should be ignored when computing averages.

The input size of this problem is the total number of animals 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 immediately 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: