辅导B+ tree、R程序语言昨天他说、辅导R设计、data留学生讲解 讲解SPSS|辅导R语言编程
- 首页 >> 其他 Assignment 3
Please make sure that you always use notations consistent with lecture notes.
Different notations will not be accepted. The deadline for assignment 3 is:
Mon 29 Apr, 10:00 am
Question 1 (8 marks)
Consider the B+ tree shown in the following as an original tree.
Answer the following questions:
1) (2 marks) There are currently 18 records in this tree. How many additional records could
be added to this tree without changing its height (give the maximum possible number)?
2) (3 marks) Show the B+ tree after inserting a data entry with key 3 into the original tree.
3) (3 marks) Show the B+ tree after deleting the data entry with key 91 from the original
tree.
Question 2 (4 marks)
Consider a relation R(a,b,c,d,e,f,g,h) containing 10,000,000 records, where each data page of
the relation holds 10 records. R is organised as a sorted file with the search key R.a. Assume
that R.a is a candidate key of R, with values lying in the range 0 to 9,999,999. For the
relational algebra , state which of the following
approaches (or combination thereof) is the most likely to be the cheapest:
1. Access the sorted file for R directly.
2. Use a clustered B+ tree index on attribute R.a.
3. Use a clustered B+ tree index on attribute R.b.
4. Use a linear hashed index on attribute R.a.
5. Use a clustered B+ tree index on attributes (R.a, R.b).
6. Use a linear hashed index on attribute s (R.a, R.b).
We assume that the database considers index-only plans. Index-only plans allow an index to
contain all columns required to answer the query. It means that by using index-only plans,
you will not have to access the data records in the file that contain the queried relations.
π{a,b}(σ(a>2,000,000 and a<8,000,000)
(R))Question 3 (8 marks)
Consider the schedule below. Here, R(*) and W(*) stand for ‘Read’ and ‘Write’, respectively.
, , and represent four transactions and represents a time slot.
Each transaction begins at the time slot of its first Read, and commits right after its last Write
(same time slot).
Regarding the following questions, give and justify your answers.
1) Assume a checkpoint is made between and , what should be done to the four
transactions when the crash happens between and . (2 marks)
2) Is the transaction schedule conflict serialisable? Give the precedence graph to justify your
answer. (2 marks)
3) Construct a schedule (which is different from above) of these four transactions which
causes deadlock when using two-phase locking protocol. If no such schedule exists,
explain why. (2 marks)
4) Construct a schedule (which is different from above) of these four transactions which
does not cause deadlock when using two-phase locking protocol. If no such schedule
exists, explain why. (2 marks)
T1 T2 T3 T4 ti
Time
R(B) R(A) W(B) W(A)
R(A) W(A)
R(B) W(B)
R(A) W(A) R(B) W(B)
t7 t8Assignment Submission
We accept electronic submissions only. Please submit your assignments as follows:
The file name should be ass3.pdf.
Ensure that you are in the directory containing the file to be submitted. (note: we
only accept files with .pdf extension)
Type “give cs9311 ass3 ass3.pdf” to submit.
You can also use the web give system to submit.
Please keep a screen capture (including timestamp and the size of the submitted file)
for your submissions as proof in case that the system is not working properly. If you
are not sure how, please have a look at the FAQ.
Note:
1. If the size of your pdf file is larger than 2MB, the system will not accept the
submission. If you face this problem, try converting to compress pdf.
2. If you have any problems in submissions,
3. We do not accept e-mail submissions, and the submission system will be immediately
closed after the deadline.
Late Submission Penalty
Zero mark
Please make sure that you always use notations consistent with lecture notes.
Different notations will not be accepted. The deadline for assignment 3 is:
Mon 29 Apr, 10:00 am
Question 1 (8 marks)
Consider the B+ tree shown in the following as an original tree.
Answer the following questions:
1) (2 marks) There are currently 18 records in this tree. How many additional records could
be added to this tree without changing its height (give the maximum possible number)?
2) (3 marks) Show the B+ tree after inserting a data entry with key 3 into the original tree.
3) (3 marks) Show the B+ tree after deleting the data entry with key 91 from the original
tree.
Question 2 (4 marks)
Consider a relation R(a,b,c,d,e,f,g,h) containing 10,000,000 records, where each data page of
the relation holds 10 records. R is organised as a sorted file with the search key R.a. Assume
that R.a is a candidate key of R, with values lying in the range 0 to 9,999,999. For the
relational algebra , state which of the following
approaches (or combination thereof) is the most likely to be the cheapest:
1. Access the sorted file for R directly.
2. Use a clustered B+ tree index on attribute R.a.
3. Use a clustered B+ tree index on attribute R.b.
4. Use a linear hashed index on attribute R.a.
5. Use a clustered B+ tree index on attributes (R.a, R.b).
6. Use a linear hashed index on attribute s (R.a, R.b).
We assume that the database considers index-only plans. Index-only plans allow an index to
contain all columns required to answer the query. It means that by using index-only plans,
you will not have to access the data records in the file that contain the queried relations.
π{a,b}(σ(a>2,000,000 and a<8,000,000)
(R))Question 3 (8 marks)
Consider the schedule below. Here, R(*) and W(*) stand for ‘Read’ and ‘Write’, respectively.
, , and represent four transactions and represents a time slot.
Each transaction begins at the time slot of its first Read, and commits right after its last Write
(same time slot).
Regarding the following questions, give and justify your answers.
1) Assume a checkpoint is made between and , what should be done to the four
transactions when the crash happens between and . (2 marks)
2) Is the transaction schedule conflict serialisable? Give the precedence graph to justify your
answer. (2 marks)
3) Construct a schedule (which is different from above) of these four transactions which
causes deadlock when using two-phase locking protocol. If no such schedule exists,
explain why. (2 marks)
4) Construct a schedule (which is different from above) of these four transactions which
does not cause deadlock when using two-phase locking protocol. If no such schedule
exists, explain why. (2 marks)
T1 T2 T3 T4 ti
Time
R(B) R(A) W(B) W(A)
R(A) W(A)
R(B) W(B)
R(A) W(A) R(B) W(B)
t7 t8Assignment Submission
We accept electronic submissions only. Please submit your assignments as follows:
The file name should be ass3.pdf.
Ensure that you are in the directory containing the file to be submitted. (note: we
only accept files with .pdf extension)
Type “give cs9311 ass3 ass3.pdf” to submit.
You can also use the web give system to submit.
Please keep a screen capture (including timestamp and the size of the submitted file)
for your submissions as proof in case that the system is not working properly. If you
are not sure how, please have a look at the FAQ.
Note:
1. If the size of your pdf file is larger than 2MB, the system will not accept the
submission. If you face this problem, try converting to compress pdf.
2. If you have any problems in submissions,
3. We do not accept e-mail submissions, and the submission system will be immediately
closed after the deadline.
Late Submission Penalty
Zero mark