Post Solutions Here

'''Problem 3''' By Craig, Geordi, Kevin Vu

Define the following terms:

a) serial schedule: A schedule is said to be a serial schedule if all of its actions consist of all the actions of one transaction, followed by all the actions of another transaction, etc. without interleaving of transaction operations.

b) serializable schedule: A serializable schedule is a schedule whose effect on the database is the same as some serial schedule

c) conflict serializable schedule: A transaction is conflict-serializable if it is conflict equivalent to a serial schedule. Two schedules are conflict equivalent if they can be turned into each other by swapping non-conflicting transactions. We say a pair of operations O1,...,O2 in a schedule from two different transactions S and T do not conflict if any of the following hold: They are both reads. They are RS(X) and WT(Y) and X is not equal to Y. They are WS(X) and RT(Y) and X is not equal to Y. They are WS(X) and WT(Y) and and X is not equal to Y.

Give an example of a serializable schedule which is not conflict serializable.

W1(Y), W1(X), W2(Y), W2(X), W3(X) is a serial schedule which has the same effect on the database as W1(Y), W2(Y), W2(X), W1(X), W3(X), but this latter is not conflict serializable.

Problem 1

a)Undo logging is a type of logging that repairs the the database by undoing the effects of transactions that have not committed before the crash to restore the database to a consistent state.

b)2 Rules

 1.If transaction T modifies database element X , then the log record of the form <T,X,v> must be written to disk before the new value of X is written to disk.

 2.If a transaction commits, then its COMMIT log record must be written to disk only after all database elements changed by the transaction have been written to disk, but as soon thereafter as possible.

By: Austin Yam, Elton Vinh, Derek Ortega

Problem 9 By Craig, Geordi, Kevin Vu

Mediator Schema
ChairMediator(Color, Material, Type, Manufacturer)

Mediator Query
SELECT color, type FROM ChairMediator WHERE color = 'red';

Data Source 1 Wrapper Query From Manufacturer 1 SELECT color, type FROM Chairs WHERE color = 'red';

Data Source 2 Wrapper Query From Manufacturer 2 SELECT colour, type FROM ChairsData WHERE colour = 'red';

Problem 2 - Jay Lam, Alex Choy, Andrew Hon

Transaction T1 and T2 will be listed in the checkpoint because they were started before the checkpoint after <T1,A,4>. The earliest we can write an end checkpoint is after <COMMIT T2>

'''Problem 8''' - Casey Reyes, Joe Kanagawa, and Yanpeng Li

8a. Centralized Locking - Contains 'centralized' lock site that is responsible for keeping track of what transactions hold, in which logical database elements replicates/copies of logical elements are allowed.

8b. Lock Coordinator - Responsible for gathering all locks needed for a transaction, it does not require any messages on the same machine for locking, it requires messages for locking to a different machine, and it does not allow any replication of logical elements.

8c. Primary Copy Locking - Deals w/ the repicated data by designating one copy of each data item as a primary copy, which keeps track of whether or not it is locked.

8d. In a distributed setting, timeouts avoid deadlocks. To prevent the deadlock, a transaction waits for a certain period for the lock, and if it does not get the lock, the transaction aborts and rolls back. Other waiting transactions might now have a chance to complete before their timeouts.

Problem 10

a)Star Schema: A Star schema that consists of a schema for the fact table and schemas for other relations called dimension tables that are linked by foreign key relationship

b)slicing data: A particular partition bin by use of a WHERE clause.

Partition bins can be formed from using a GROUP BY clause.

c)Cube: A cube is an operator that creates an augmented table Cube (f) that adds to each dimension an additional value , is equivalent to ANY and that value for a tuple with * in a column is assumed to be aggregated amongst all values that it implies

By: Austin Yam, Elton Vinh, Derek Ortega

Problem 7 <br> By Sean Schlaefli, Michael Hyun, Leonard Thang <br> <br> a) Give the parallel algorithm from class for computing the join of two relations RS. <br>

1. Determine a hash function h(t) for the join operation. The hash function should only depend on the join attributes <br>
2. Compute h(t) for each tuple in R and S <br>
3. The output of h(t) should be a machine number i that maps to a machine Mi. <br>
4. For each i, send all tuples with h(t) = i to the machine Mi. <br>
5. After each machine receives all tuples they are expected to process, the machine computes the join and outputs the results.<br>

<br> b) Give its cost on N machines. <br> cost in disk I/Os = {{Fraction|5*(B(R) + B(S))|N}} <br> <br> c) Give the distributed algorithm from class for computing RS on two machines. <br> Assume R is smaller than S <br> M1 contains R and M2 contains S <br> M2 computes π<sub>Y</sub>(S) and sends the results to M1 <br> M1 computes R π<sub>Y</sub>(S) and sends the results to M2 <br> M2 uses R π<sub>Y</sub>(S) to compute R S <br> <br>

Question 5: Kim Pham, Stanley Plagata, Elena Pearson

Timestamp scheduling: give each transaction and database element a timestamp and compare these to determine if the schedule is equivalent to the serial schedule given by the transactions' timestamps.

In timestamp scheduling, the scheduler can grant, delay, or abort a transaction

Timestamp Scheduling:

1/ Read request:

• if timestamp > time write -> the read is realizable

- if committed -> grant the request & update timestamp
	else delay

• if timestamp < time write -> non realizable -> rollback

- abort 2/ Write request:

• if timestamp >= read time and timestamp >= write time, write is realizable

- write, reset write time = timestamp and commit to false

• if timestamp >= read time and timestamp < write time, write is realizable but there is a value in X

- if Committed -> ignore write, otherwise delay until transaction commit or abort

• if timestamp < read time -> roll back

Multiversion Scheduling:

• Write request create new versions of the database elements
• Read request: read from a version that is older from the current transaction timestamp
• Write time and read time are associated with versions of an element

Example: Timestamp scheduling: A transaction with a smaller timestamp attempt to read from a database element with a greater last write time, then the transaction would abort

Multiversion scheduling: Supposed there are 2 version of X: X_50 and X_100 When T1 read from X at time=80, it read X_50 Supposed a transaction T2 that started at time=60 attempted to change X at time=90, it would create an inconsistent (T1 should have read X_90) So T2 would have to abort

Question 6

Tim, Tyler, Gregory