CSc 417

Assign 4 -

due by Monday, ideally Friday if you want it marked soon

See p. 732 and before. In all these exercises, assume that the relation S is small enough to fit in main memory [ ie. B(S) < M ]
Iterators for algorithms should call on iterators for the inputs. These could be table scans, or iterators for other algorithms. [e.g. R.GetNext() ]
  1. The algorithm for Set Intersection described on p. 729 seems to assume that R and S are sets. But there are many reasons why they might be bags (contain duplicates.)  Please describe a set intersection for bag inputs.
  2. Write an iterator of projection
  3. Write an iterator for bag intersection of R and S. Briefly describe the (augmented) search structure you need.
  4. Write an iterator for one-pass natural join.
  5. Are any of these iterators blocking? In other words, do you have to wait for one or both of the input relations to be completely read in before delivering any output?

Lab 1

Do this afternoon, submit by Friday

EXPLAIN will tell postgresql to reveal its chosen query plan. You should be able to determine what order of operations are performed, and approximately what algorithms are used. Please explain three queries regarding the ships database (make sure your queries actually work!) and comment on them regarding the query plan and algorithms. Please identify any "blocking" operations.

Use the "ships" database on cs-linux (see p.211)
  1. All the ships in the database (bag union of name from ships and ship from outcomes)
  2. Set union of the above (no duplicates)  Comments?
  3. Count the number of ships sunk in each battle.
If you were a database user in csc207, you still are. Otherwise, you are, your user name is same as your linux login, and your initial password is your student number. Please change it.

Submit the output of EXPLAIN, with comments written on it, on paper or by:
submit csc417 myfile.txt