School of Computing and Information Technology Session: Spring 2020 University of Wollongong Lecturer: Janusz R. Getta CSCI235/CSCI835 Database Systems Assignment 2 14 September 2020 Scope This assignment includes the tasks related to database normalization, indexing of relational tables, and using cursors to search a database. The outcomes of the laboratory work are due by Saturday 17 October, 2020, 7.00 pm (sharp). Please read very carefully information listed below. This assignment contributes to 20% of the total evaluation in a subject CSCI235 and it contributes to 17% of the total evaluation in a subject CSCI835. A submission procedure is explained at the end of specification. This assignment consists of 4 tasks and specification of each task starts from a new page. It is recommended to solve the problems before attending the laboratory classes in order to efficiently use supervised laboratory time. A submission marked by Moodle as “late” is treated as a late submission no matter how many seconds it is late. A policy regarding late submissions is included in the subject outline. A submission of compressed files (zipped, gzipped, rared, tared, 7-zipped, lhzed, … etc) is not allowed. The compressed files will not be evaluated. All files left on Moodle in a state “Draft(not submitted)” will not be evaluated. An implementation that does not compile due to one or more syntactical and/or run time errors scores no marks. It is expected that all tasks included within Assignment 2 will be solved individually without any cooperation with the other students. If you have any doubts, questions, etc. please consult your lecturer or tutor during lab classes or office hours. Plagiarism will result in a FAIL grade being recorded for the assessment task. Task 1 (6 marks) Concurrent executions of database transactions Consider the database transactions listed below. T1 T2 T3 read(x) read(y) read(z) write(y,x+1) write(x,y+1) write(x,z+1) commit commit write(y,z+2) commit Assume that the initial values of the persistent data items x, y, and z are the following. x = 1, y = 2, and z= 3. (1) ( 2 marks) Show a sample concurrent execution of the transactions T1, T2, and T3 that is nonconflict serializable and that is view serializable. Prove, that the execution is nonconflict serializable and that it is view serializable. When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 10 Introduction to Transaction Processing (1), slide 9. (2) (2 marks) Show a sample concurrent execution of the transactions T1, T2, and T3 that is conflict serializable and that is not order-preserving conflict serializable. Prove, that the execution is conflict serializable and that it is not order-preserving conflict serializable. When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 10 Introduction to Transaction Processing (1), slide 9. (3) (2 marks) Show a sample concurrent execution of the transactions T1, T2, and T3 that is recoverable and that is not strict. Prove, that the execution is recoverable and that it is not strict. When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 10 Introduction to Transaction Processing (1), slide 9. Deliverables A file solution1.pdf with: (1) a visualization of a sample concurrent execution of the transactions T1, T2, and T3 that is nonconflict serializable and that is view serializable and a proof that the execution is nonconflict serializable and that it is view serializable. (2) visualization of a sample concurrent execution of the transactions T1, T2, and T3 that is conflict serializable and that is not order-preserving conflict serializable and a proof that the execution is conflict serializable and that it is not order-preserving conflict serializable. (3) visualization of a sample concurrent execution of the transactions T1, T2, and T3 that is recoverable and that is not strict and a proof that the execution is recoverable and that it is not strict. Task 2 (6 marks) Serialization graph testing, 2PL, and Timestamp ordering scheduler Consider a concurrent execution of database transactions T1, T2, and T3 such that the execution is not controlled by any scheduler. T1 T2 T3 read(x) write(x,x+1) read(y) write(x,y+1) read(z) write(x,z+1) read(z) write(z,x+2) (1) (2 marks) Assume, that the transactions attempt to interleave their operations in the same way as in the execution above. Show a sample concurrent execution of the transactions T1, T2, and T3 that is controlled by serialization graph testing scheduler. Draw a conflict serialization graph. When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 10 Introduction to Transaction Processing (1), slide 9. (2) (2 marks) Assume, that the transactions attempt to interleave their operations in the same way as in the execution above. Show a sample concurrent execution of the transactions T1, T2, and T3 that is controlled by 2PL scheduler. Assume, that to simplify the problem we use only a general concept of a lock and we do not distinguish between shared locks and exclusive locks. When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 10 Introduction to Transaction Processing (1), slide 9. (3) (2 marks) Assume, that the transactions attempt to interleave their operations in the same way as in the execution above. Show a sample concurrent execution of the transactions T1, T2, and T3 that is controlled by timestamp ordering scheduler. When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 10 Introduction to Transaction Processing (1), slide 9. Show the data items accessed by the transactions together with the timestamps left by the transactions on the data items. Deliverables A file solution2.pdf with: (1) visualization of a sample concurrent execution of the transactions T1, T2, and T3 that is controlled by serialization graph testing scheduler and a conflict serialization graph, (2) visualization of a sample concurrent execution of the transactions T1, T2, and T3 that is controlled by 2PL scheduler, (3) visualization of a sample concurrent execution of the transactions T1, T2, and T3 that is controlled by timestamp ordering scheduler. Task 3 (6 marks) Processing transactions at READ COMMITTED level by a snapshot isolation scheduler Consider a stored PL/SQL function MAX_MIN given below. CREATE OR REPLACE FUNCTION MAX_MIN ( orderkey IN NUMBER ) RETURN NUMBER IS max_value NUMBER(12); min_value NUMBER(12); BEGIN SELECT MAX(L_QUANTITY * L_EXTENDEDPRICE) INTO max_value FROM LINEITEM WHERE L_ORDERKEY = orderkey; SELECT MIN(L_QUANTITY * L_EXTENDEDPRICE) INTO min_value FROM LINEITEM WHERE L_ORDERKEY = orderkey; RETURN max_value-min_value; END MAX_MIN; / (1) (4 marks) Show a sample concurrent execution of the function at READ COMMITTED level that interleaves the operations with another transaction and such that a result returned by the function is incorrect. The operations performed by another transaction are up to you. When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 14 Transaction Processing in Oracle DBMS slide 16. (2) (2 marks) Rewrite a stored function such that it can be processed at READ COMMITTED level and show how the improved function interleaves the operations with another transaction and such that a result returned by the function is always correct. When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 14 Transaction Processing in Oracle DBMS slide 16. Deliverables A file solution3.pdf with: (1) visualization of a sample concurrent execution of the function at READ COMMITTED level that interleaves the operations with another transaction and such that a result returned by the function is incorrect, (2) visualization of a sample concurrent execution of an improved function at READ COMMITTED level that interleaves the operations with another transaction and such that a result returned by the function is always correct. Task 4 (2 marks) Deadlocks Consider a stored PL/SQL function SWAP given below. CREATE OR REPLACE PROCEDURE SWAP( order_key1 IN NUMBER, order_key2 In NUMBER ) IS total_price1 ORDERS.O_TOTALPRICE%TYPE; total_price2 ORDERS.O_TOTALPRICE%TYPE; BEGIN SELECT O_TOTALPRICE INTO total_price1 FROM ORDERS WHERE O_ORDERKEY = order_key1; SELECT O_TOTALPRICE INTO total_price2 FROM ORDERS WHERE O_ORDERKEY = order_key2; UPDATE ORDERS SET O_TOTALPRICE = total_price1 WHERE O_ORDERKEY = order_key2; UPDATE ORDERS SET O_TOTALPRICE = total_price2 WHERE O_ORDERKEY = order_key1; END SWAP; / Show a sample concurrent execution of two transactions both processing a function SWAP, both running at READ COMMITTED level, and such that the execution leads to a deadlock. When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 14 Transaction Processing in Oracle DBMS slide 16. Deliverables A file solution4.pdf with visualization of a sample concurrent execution of two transactions both processing a function SWAP, both running at READ COMMITTED level, and such that the execution leads to a deadlock. Submission Submit the files solution1.pdf, solution2.pdf, solution3.pdf, and solution4.pdf through Moodle in the following way: (1) Access Moodle at http://moodle.uowplatform.edu.au/ (2) To login use a Login link located in the right upper corner the Web page or in the middle of the bottom of the Web page (3) When logged select a site CSCI835/CSCI235 (S220) Database Systems (4) Scroll down to a section SUBMISSIONS (5) Click at a link In this place you can submit the outcomes of Assignment 2 (6) Click at a button Add Submission (7) Move a file solution1.pdf into an area You can drag and drop files here to add them. You can also use a link Add… (8) Repeat a step (7) for the files solution2.pdf, solution3.pdf, and solution4.pdf. (9) Click at a button Save changes (10) Click at a button Submit assignment (11) Click at the checkbox with a text attached: By checking this box, I confirm that this submission is my own work, … in order to confirm the authorship of your submission. (12) Click at a button Continue End of specification
