Due
2300 on Lessons 33 and 34
Duration
30–60 minutes
Points
10 points

Help Policy

Authorized Resources
Any, excluding classmates
Notes
Never copy another person’s work and submit it as your own

You must document all resources, including the instructor and instructor-provided course materials (such as the textbook)

Instructions

Respond to one of the following prompts, and reply to one of your classmates’ original posts. Unless otherwise indicated by the prompt, it is expected that responses should be no more than a paragraph (one paragraph ≈ 200 words).

  1. Many different types of indexes exist, including the following:
    • B-tree / B+ tree
    • R-tree / R+ tree
    • Hash
    • Inverted index
    • Bitmap
    • Reverse
    • Partial
    • Expression
    • Trie (i.e., prefix tree)

    Describe one type of index that was not previously covered (e.g., you cannot select B+ trees), and identify the index’s storage space complexity and algorithmic complexity for search, insertion, and deletion (e.g., a B+ tree requires \(O(n)\) storage space and requires \(O(\log_b n)\) operations for search, insertion, and deletion). List at least one application for this specific type of index.

    Responses to initial posts may identify additional applications for the type of index – i.e., under what circumstances should you use it.

    Note: While your description may look similar to the opening paragraph from Wikipedia, you should not use Wikipedia as your sole reference. For example, PostgreSQL implements many of these indexes, and its documentation contains a wealth of details about them.

  2. Although serializable schedule is generally the target isolation level for transactions, it can significantly reduce performance. Describe a use case where a serializable schedule is unnecessary and justify why its is not required.

    Responses to initial posts should analyze the use case and identify which ACID properties are being sacrificed. Do you agree with the justification that they are unnecessary?

  3. The traditional implementation of concurrency control is locking, but a number of alternatives exist. Such alternatives include
    • conflict checking
    • timestamp ordering
    • commit ordering
    • multiversion concurrency control (MVCC)
    • deferred updates

    to name a few. Briefly describe an alternative implementation to locking for concurrency control, including its trade-offs. Illustrate the use of this technique with a transaction schedule.

Submission

Submit your posts using the Blackboard discussion board for your section.

Due to the way that Blackboard is configured (i.e., one site per course instead of one site per section), the main “Discussion Board” is visible to all students. Thus, it might be difficult for those posting later to avoid rehashing the same content.

Consequently, each section has its own discussion forum, which is accessible only to students in that section. You can access the discussion forum for your section in the following ways:

  • Groups > Section ? > Group Tools > Group Discussion Board
  • My Groups > Section ? > Group Discussion Board

where ? is a placeholder for the section number (e.g., M3A).

Be sure to document any sources that you used when writing your posts.

Grading

Grading is largely based on completion, but posts should demonstrate effort commensurate with the expected duration for this activity. Citing multiple references, drawing connections among others’ posts, additional responses, etc. all demonstrate effort that is appropriate or even exceeds the expectation. Conversely, summarizing the first paragraph of a Wikipedia article, poor spelling and grammar, off-topic posts, etc. demonstrate lack of effort.

Posts that express simple (dis)agreement will be ignored for the purpose of grading. For example,

I agree.

may be appropriate in the context of a conversation but does not satisfy the requirements when responding to someone else’s post. (A good rule of thumb might be that fewer than 20 words does not qualify as a “post.”) Nevertheless, several short posts (e.g., 100 words) may collectively sum to the level of effort expected.

Rubric

The specific grading rubric is as follows:

Initial post
Exceeds standard (100%)
Fully addresses prompt and expands upon it
Meets standard (90%)
Fully addresses prompt
Nearly meets standard (75%)
Addresses most, but not all, of the prompt
Below standard (50%)
Post is obviously incomplete or off-topic
Missing (0%)
Post does not address the prompt or is missing entirely
Response
Exceeds standard (100%)
Contributes to the discussion in a meaningful way (e.g., adds new information to that previously presented)
Meets standard (90%)
Contributes to the discussion
Nearly meets standard (75%)
Response is on-topic but does not further the discussion
Below standard (50%)
Response is off-topic or inappropriate or may not be relevant to the larger discussion
Missing (0%)
Response is limited to simple (dis)agreement or missing entirely

As indicated by the rubric, earning all the points requires exceeding the standard. Simply addressing the prompt and contributing to the discussion will only earn 90% of the available points.