CS 561   Spring 2003.

CS561 HOMEWORK : View Maintenance in Distributed Environments

Assigned: Wednesday, March 26, 2003

Due: Wednesday, April 2, 2003 (at start of class in hardcopy)

Maximum: 100pts.

Collaboration: This homework should be done individually.

Note:

The questions below are based on the paper we have covered last week in class entitled VIEW MAINTENANCE IN A WAREHOUSING ENVIRONMENT.

• 1. List at least 6 assumptions that the ECA algorithm is making about the environment and/or the problem it is tackling.
• 2. Explain briefly in a few sentences what the main problem is that this ECA algorithm is trying to solve, including the cause of this problem.
• 3. Explain briefly in a few sentences what the key ideas and the intuition is of the ECA algorithm solution.
• 4. Below, this problem contains several exercises to make sure you deeply understand the basics of view maintenance in distributed environments, and in particular the BASIC view maintenance algorithm and the ECA algorithm.

  Show your detailed steps, queries, intermediate data structures, messages, view content, and so on after each step. Describe when and how often the view is actually being refreshed and if the view content is correct or not.

  Initial database states:
  
     R1 (W , X)        R2 (X , Y)       R3(Y , Z)
         1   2             2   3           -   -
  
  
  Updates:
  U1 =  insert(2,2) into R1
  U2 =  insert(3,4) into R3
  U3 =  insert(3,2) into R1
  

  • 4(a). Show a detailed walk-through of what the BASIC ALGORITHM given as algorithm 5.1 in section 5.1 of the ECA paper would compute for the above. Do show the queries, the view, and when it is being refreshed. Make all the same assumptions as in the paper. In addition, assume the three updates U1, U2, and U3 all happen very rapidly in time, and all are committed at the data source before the first maintenance query ever arrives back to the view manager.
  • 4(b). Now show a detailed walk-through of what the ECA ALGORITHM given as algorithm 5.2 in section 5.1 of the ECA paper would compute for the above. Make all the same assumptions as in the paper. In addition, assume here at the three updates U1, U2, and U3 all happen very rapidly, and all are committed at the data source before the first maintenance query ever arrives.
  • 4(c). Now, repeat problem 4(a) above for the BASIC algorithm. However, assume that first U1, U2 are committed at the source close in time. After hearing about these two updates, the view manager receives the query answer to the first maintenance query Q1. And, only thereafter she gets notified that a third update, U3, happened at the source.
  • 4(d). Now, repeat problem 4(a) above for the ECS ALGORITHM. However, assume that first U1, U2 are committed at the source close in time. After hearing about these two updates, the view manager receives the query answer to the first maintenance query Q1. And, only thereafter she gets notified that a third update, U3, happened at the source.