Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

School of Computer Science

Distributed Databases and Data Mining

Assignment 2

● Introduction

Assignment 2 has four questions. Both UG and PG students need to finish all four questions. The first two questions are the same for UG and PG students, while the last two questions have different requirements for UG and PG students.

Given the following relations:

STUDENT (SID, SNAME, SAGE, SSEX)

COURSE (CID, CNAME, CCONTEXT)

MARK (SID, CID, SCORE)

Please answer the questions in the format of descriptions, equations, query graphs and the operator trees in question 1-4. Only the query graph and the operator tree can be handwritten; others such as descriptions and equations must be in electronic version. For the handwritten parts, you could save them as jpg. or png., and insert them into office word. Please submit the electronic version and do not submit the handwritten version of descriptions and equations. Handwritten descriptions and equations will not be marked.

You are expected to provide your answers for the all four questions in one pdf and submit the pdf in MyUni, Assignment 2.

If you have any questions about assignment 2, please feel free to post the questions on the discussion board or contact Congbo Ma ([email protected]).

● Questions

Question 1 (4 marks):

Given three relations STUDENT, COURSE and MARK, a user query is: “Find the student name and Course name of students whose scores are more than 85 points.”

(1) Please give the claculus query (SQL) (1 mark);

(2) Please give the corresponging query graph (2 mark);

(3) Please map the SQL query into an original operator tree (Not optimized) (1 mark).

Question 2 (4 marks):

For the following query:

(1) Please simplify the query (2 mark);

(2) Please transform the SQL expression into an optimized operator tree using the restructuring algorithm where select and project operations are applied as soon as possible to reduce the size of intermediate relations (2 mark).

Question 3 (5 marks):

Assume that relation STUDENT of the sample database is horizontally fragmented:

relation MARK is indirectly fragmented as：

and relation COURSE is vertically fragmented as：

Please describe the detailed processes of how to transform the following query into a reduced query on fragments:

For undergraduate students, the query is (5 marks):

For postgraduate students, the query is (5 marks):

Question 4 (7 marks):

The first table shows the placement of the copies of the 4 relations at the 4 sites and the site loads:

Please describe the detailed processes of how to extend the SQAllocation algorithm to the following bushy join trees using the data placement and site loads shown in the table.

For undergraduate students, you only need to provide one solution (7 marks).

For postgraduate students, you need to provide two solutions (4 marks for the first solution and 3 marks for the second solution).