COMP2211-WE01

Section A    Databases

Question 1

(a) Consider the XML document below.

     <?XML VERSION = "1.0" STANDALONE = "yes"?>

     <schoolclass>

     <student hobby = "cycling" sex = "M" YOB = "2001">

     <name> John Richardson </name>

     <topic> Math </topic>

     <topic> Physics </topic>

     <tutor> Mrs. Marton </tutor>

     </student>

     <student hobby = "movies" sex = "F" YOB = "2000">

     <name> Maria Clothier </name>

     <topic> Chemistry </topic>

     <tutor> Mrs. Hall </tutor>

     </student>

     <student hobby = "cycling" sex = "F" YOB = "2005">

     <name> Gina Heyen </name>

     <topic> Engineering </topic>

     <topic> Math </topic>

     <tutor> Mrs. Marton </tutor>

     </student>

     </schoolclass>

i. Draw the Hierarchical Tree Model of the above XML file. Please ensure that you include in your tree all the necessary labels.

Hint: If you do not have enough space, you can write the names of the nodes next to the nodes (instead of inside the nodes). [24 Marks]

In what follows, assume that the above XML code is stored in the file ”school.xml”.

ii. Write an XPath query for the following:

‘Select all different tutors of students who were born after year 2000.’ 

Provide also the output of your query. [4 Marks]

iii. Write a query in XQuery for the following:

‘Find the hobbies that correspond to more than one student.’ 

Provide also the output of your query. [6 Marks]

(b) Produce the wait-for-graph for the following transaction scenario and de-termine whether a deadlock exists. 

[16 Marks]

Section B    Distributed Systems

Question 2

Beatrix has implemented an efficient distributed system, which contains two back-end servers to offer auction services to all Durham CS students. The system supports three main functions: 1) auction item submission and bidding, 2) item browsing, and 3) item payment, where the item payment function is done by an external web service. Assume that 70% of user activities in the system are item browsing.

In the system, for each auction item, the seller is required to set a base price, which is visible to all users. Each participating bidder for the item can only submit one single bid price, which must be higher than or equal to the item’s base price. A bidder will win an auction item if he/she has submitted the highest bid price or was the first bidder who submitted that highest bid price.

(a) Draw a block diagram to depict the required distributed system, fulfilling both Beatrix’s system design requirement and suitable transparency prop-erties. Justify your answer. Explain how the three main system functions are handled by the servers inside the system. [14 Marks]

(b) After running the distributed system for three months, there has been a 300% increase in the auction item submission and bidding activities. Beatrix has proposed to use five dedicated servers to handle such activities based on active replication. To enforce system robustness while improving system performance, each transaction of the activities will be processed by two selected servers out of the five.

i. Analyse the practicality of Beatrix’s proposal. Explain how it improves or fails to enforce system performance and robustness. [6 Marks]

ii. Based on your finding in (b)(i), write an algorithm to illustrate how the required servers can be selected for handling each bidding transac-tion and return the result to a user. Assume that each server provides a remote function bid processing() to process a bidding transac-tion and return the server-dependent processed result. [12 Marks]

iii. On every Friday after 5pm, the system typically receives many brows-ing or bidding activities, making some servers overloaded. Suggest an efficient and robust load distributing algorithm to solve this problem. Justify your answer. [8 Marks]

(c) To enhance user experience, the system is modified to allow a bidder sub-mitting bid prices multiple times for an item. The base price of an item will be increased accordingly when the item receives new bid price(s). Note that concurrent bid price submission for an item by multiple bidders is allowed.

Suggest what control mechanism can be implemented to support the sys-tem modification, ensuring efficient and robust base price updating. Justify your answer. [10 Marks]

END OF PAPER