D64 Assignment #2

Due Monday, January 31, 2000 at 4:00pm.

The assignment should be turned in before class on Monday. Remember, all assignments should be your individual work - group work is not permitted.

Problem Set

  1. (50 pts.) Consider a table with the following column definitions
    1. title CHAR(40) NOT NULL
    2. author CHAR(40) NOT NULL
    3. isbn CHAR(10) PRIMARY KEY NOT NULL
    4. hardcover BIT(1)
    5. numSold INTEGER DEFAULT 0
    6. description VARCHAR(255)
    7. price NUMERIC(5,2)
    8. averageRating FLOAT

    Part A: Devise a fixed length representation for records in this table subject to the following constraints:

    1. The first thing stored in a record is its header (if your scheme requires a header). After the header, each attribute should be stored in the order listed above.
    2. When records are loaded into memory, their fields should be properly aligned. The alignment of a field depends on its type (i.e. integers should be 4 bytes aligned, floats should be 8 byte aligned, characters do not need to be aligned, etc.).
    3. Fields should not overlap (i.e. do not try to put more than 1 bit field in the same byte).
    4. Records should be as small as is possible (and reasonable) given the above constraints.
    5. The code required to extract field values from the record and to change field values must be reasonable. This is just a sanity check - do not actually write the code.

      Turn in:

      1. A description of the representation you choose.

      2. The exact layout for the following record: ('See spot run','Dick & Jane','0123456789',0,35256,NULL,19.95,8.234)

      This question is underspecified on purpose - there is more than one way to answer it.

    Part B: Devise a variable length representation for records in this table subject to the following constraints:

    1. The first thing stored in a record is its header (if your scheme requires a header). After the header, each attribute should be stored in the order listed above.
    2. When records are loaded into memory, their fields should be properly aligned. The alignment of a field depends on its type (i.e. integers should be 4 bytes aligned, characters do not need to be aligned, etc.).
    3. Fields should not overlap (i.e. do not try to put more than 1 bit field in the same byte).
    4. Records should be as small as is possible (and reasonable) given the above constraints.
    5. The code required to extract field values from the record and to change field values must be reasonable. This is just a sanity check - do not actually write the code.

      Turn in:

      1. A description of the representation you choose.

      2. The exact layout for the following record: ('See spot run','Dick & Jane','0123456789',0,35256,NULL,19.95,8.234).

      This question is underspecified on purpose - there is more than one way to answer it.

  2. (30 pts.) Write the pseudocode to dereference a pointer in the following three cases:
    1. No swizzling
    2. Swizzling on demand
    3. Automatic swizzling

    Your code will have to be a bit vague since I'm not providing exact data structures or the interface to other components (like the buffer manager). The goal is to show me you understand swizzling in general and the differences between the above approaches in particular. Make reasonable assumptions.

  3. (20 pts.) Flesh out the details of the block packing scheme described in Section 3.2.3. Assume that we don't have a directory in the header since the records are fixed length, we simply store the records back to back after the header. What information will we need to store in the header? How do we delete a fixed length record from a block if we're using physical addressing? Are there any repercussions of this approach?