-------------------------------------------------------------------------------- LAB 3 | Schedule types and properties. -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- PRACTICE EXERCISES -------------------------------------------------------------------------------- (1) Get familiar with the terms: - transaction schedule, - serial schedule, - serializable schedule, - conflict serializable schedule, - precedence graph, - conflict equivalent schedule, - recoverable schedule, - cascadeless schedule, by attending the lecture and reading chapters 14.5, 14.6, 14.7 from the textbook. (2) Is the following schedule conflict serializable? Draw a precedence graph to verify. T1: T2: T3: write(X) write(Y) read(Y) write(Z) read(Z) COMMIT COMMIT COMMIT (3) Is the following schedule conflict serializable? Draw a precedence graph to verify. T1: T2: T3: write(X) read(X) write(X) write(X) COMMIT read(X) COMMIT COMMIT (4) Draw the precedence graph of the following schedule and show whether the schedule is conflict serializable or not. T1: T2: T3: read(Z) read(Y) write(Y) read(Y) read(Z) read(X) write(X) write(Y) write(Z) read(X) read(Y) write(Y) write(X) (5) Consider the following schedule. T1: T2: T3: read(X) read(Y) read(Z) read(Y) write(X) write(Z) write(Y) write(Y) (a) Draw the precedence graph of the schedule. (b) Give all possible serializability orders of the schedule. Explain why the list is complete. (6) Consider the following schedule. T1: T2: T3: T4: read(X) write(X) read(X) read(Y) write(Y) read(Z) write(Z) read(Z) write(Z) (a) Is the following schedule conflict serializable? Explain why. (b) If it is serializable, give an equivalent serial schedule. (7) Consider the following schedule. T1: T2: read(X) write(Y) read(Y) (c) Is this schedule cascadeless? If no, where to place the commits in order to make it cascadeless? (8) Show the commit order for the following schedule such that the schedule is recoverable. Is it possible to insert COMMIT instructions into the schedule such that the schedule avoids cascading aborts? T1: T2: T3: T4: write(X) read(X) read(X) write(X) read(X) read(X) (9) Consider the following schedule. T1: T2: T3: read(Z) read(X) read(Z) write(Z) read(X) read(Y) write(X) read(X) read(Y) (a) Draw the precedence graph of the schedule. (b) Give all possible serializability orders of the schedule. Explain why the list is complete. (c) Add two COMMIT and one ROLLBACK commands such that the resulting schedule is not recoverable. (10) Consider the following schedule. T1: T2: read(X) write(X) read(X) read(Y) read(Y) write(Y) (a) Is the schedule conflict serializable? (b) Is the schedule recoverable if: - T1 commits after write(Y), - T2 commits after read(Y) and before T1:read(Y))? (c) Is the schedule cascadeless? (11) FURTHER READING: - 'Concurrency control', 'Concurency control manager' from Encyclopedia of Database Systems [1]. (12) CHECK-LIST: - I can explain what is a serializable shcedule and why ensuring serializability is important. - I can explain what are the properties of conflict serializable, recoverable, and cascadeless schedules. - I can analyse a transaction schedule and identify its properties (conflict serializable, recoverable, cascadeless). -------------------------------------------------------------------------------- HOMEWORK -------------------------------------------------------------------------------- DEADLINE: 24.11.2016, 21:59 This is the first Python exercise. It introduces you with the concepts and technologies we will use later on. We call this exercise "Cookie Jar". Your task is to implement a Python script that immitates monsters eating cookies from a cookie jar. We need a few items to start implementing. Make sure you have all of them installed and working. PostgreSQL[2] - Will store a table that represents our cookie jar. Python3 [3] - Will be used to implement everything. Psycopg2[4,5] - Is a PostgreSQL adapter for Python3. It will help us to connect to PostgreSQL from Python3. argparse [6] - Is a Python3 module for parsing command-line options and arguments. We will use it for convenient execution of our Python3 script. NOTE: Use the package manager of your system to install Python3 (apt-get, macports, etc.). NOTE: Use pip [7] to install Psycopg2 (you may need to install pip first). IMPORTANT: The sript will be automatically executed and evaluated so make sure that everything works as it should. The following command will be used to execute your script. "--connection-string" is an argument that lets us specify a custom connection string to the database. Use argparse for processing command line arguments. python cookie_jar.py --connection-string "My database connection string." The script has to perform the following tasks: (1) Connect to a database in PostgreSQL using Psycopg2. (2) Execute a statement that creates a table "cookie_jar" with two columns: "cookie_id" of type "int" and "is_eaten" of type "int". (3) Fills in the cookie jar with 10 cookies (with ids 0...9) and sets their "is_eaten" value to "0" which means that a cookie has not been eaten yet. (4) Implement three monsters as a list of two-elements-lists: monsters = [[1,0],[2,0],[3,0]] Each inner list stores a monster id and the number of cookies it ate. (5) Implement a function "is_cookie_left()" that returns "True" if there are cookies in the cookie jar, and "False" if there are no cookies left. (6) Implement a function "eat_cookie(monster)" that, in a single transaction, chooses the first not-eaten cookie in the cookie jar and eats it. In particular it: (a) Sets "is_eaten" value of the eaten cookie to "1". (b) Increments the number of cookies that the monster ate. (7) Implement monsters eating cookies as a loop that lets the monsters eat the cookies until there are no more left. At each step, a monster to eat a cookie is chosen randomly (use random module [8], for example, random.choice(monsters)). (8) Print the monsters list using "print(monsters)". An example result should look like this "[[1, X], [2, Y], [3, Z]]" where X,Y,Z are the numbers of cookies eaten by the corresponding monsters. -------------------------------------------------------------------------------- REFERENCES -------------------------------------------------------------------------------- [1] (Access from university network.) https://link.springer.com/referencework/10.1007%2F978-0-387-39940-9 [2] PostgreSQL (downloads) https://www.postgresql.org/download/ [3] Python3 https://www.python.org/ [4] Psycopg2 (documentation) http://initd.org/psycopg/docs/index.html [5] Psycopg2 (basic usage) http://initd.org/psycopg/docs/usage.html [6] argparse (documentation) https://docs.python.org/3/library/argparse.html [7] pip - tool for installing Python packages. https://pypi.python.org/pypi/pip [8] random (documentation) https://docs.python.org/3/library/random.html