CS511 Assignment #1:
Study Guide Problems
(due Sept 29, 2006, Fri, 11:59PM CST)
In this assignment, you will need to create one "study guide problem" (SGP) for at least five of
the following nine classic DB papers covered in the class:
- E.F. Codd: A Relational Model of
Data for Large Shared Data Banks
- Chamberlin et al.: A History and Evaluation of System R
- Michael Stonebraker: Retrospection on a Database System
- Stonebraker: OS Support for Database Management
- Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching
- Hellerstein et al.: Generalized Search Trees for
Database Systems
- Selinger et al.: Access Path Selection in a
Relational Database Management System
- Gray et al.: Granularity of Locks and Degrees of
Consistency in a Shared Data Base
- Anon et al.: A Measure of Transaction Processing Power
A study-guide problem (SGP) is an open-book exam type problem
with sample answers. The goal of writing study-guide problems is two-fold: 1) Students will read papers carefully to write good problems, demonstrating their understanding and digesting of materials. 2) Students will benefit by using problems written by their peers as study guides for reviewing.
How to write good study-guide problems?
Study-guide assignment is designed for two purposes: First, making problems
encourages you to read a paper more carefully and critically.
Second, problems made by your peers will benefit you as study guides.
In order to better serve these two purposes, we recommend the following
guidelines for making good study guide problems:
When you encounter a new problem or solution from the paper,
try to ask yourself critical questions: Is the problem real?
What are real-world applications you can think of? How is the
new solution different from other solutions that you know?
A good study guide problem will encourage such critical thinking,
while a bad one requires only straightforward reciting of concepts
and facts in papers, as contrasted below with examples:
- bad example: Explain the access path dependency problem.
- good example: Give a simple example (of a small database) to illustrate the difference, i.e,
1. How the network model requires access path be explicitly programmed
2. How the relational model (of the same data) makes access path transparent.
For concrete understanding of the solution proposed, try to make working examples
and operate them yourself. It will help you ensure your understanding of the
solution and discover the underlying intuition. Again, to illustrate,
we contrast a good problem that requires to demonstrate concrete understanding
of the solution from a bad one that only requires straightforward citation:
- bad example: What is the cost formula for estimating the join size?
- good example: Assume that we have the following "statistics" of the relations:
NCARD(R)=1000, V(R.A)=100, NCARD(S)=300, V(S.A)=20
Estimate the size of the join, i.e., NCARD(R join S on A).
How to submit your study-guide problems?
Study-guide problems and the corresponding solutions are to be submitted by Sept. 29, Friday, 11:59PM CST, through the
CS511 wiki
space. Late submissions will not be accepted. Use the place holders created in the wiki space to insert
your SGPs and solutions. More detailed instructions will be posted later.
Grading
You are required to make 5 SGPs, but you are encouraged to submit more, in which case, we will choose
the best 5 for grading. Each SGP is worth 20 points, summing to a total of 100 points for this assignment.
A SGP is graded based on (1) clarity of the problem (no ambiguity, well defined) [30%];
(2) correctness of the solution [40%]; (3) usefulness for understanding the key point(s) of the paper [20%];
and (4) novelty of the problem [10%].
To encourage writing high quality problems, at least 30% of the midterm exam problems will be created by
adapting the best SGPs submitted by you. It is thus advantageous to you if you submit high quality SGPs
and also study SGPs submitted by others.