Please read the following instructions before starting the homework:

This homework must be completed individually and should be submitted on Gradescope.

No late days for homework! If you miss the due date, you get 0 points. If your PDF gets modified after the due date, you get 0 points. No exceptions on this.

Honor Code:

By submitting this homework, you are agreeing to abide by the Honor Code:

I have neither given nor received unauthorized aid on this assignment, nor have I concealed any violations of the Honor Code.

Question 1 Transactions (34 points)

Check what kinds of conflicts exist in the following schedules. Determine if the following schedules are: serializable, and/or conflict serializable.

1.1 Schedule A [8 points]

1.  [2 points] What conflicts exist between T1 and T3?

2.  [3 points] Is the schedule conflict serializable?

3.  [3 points] Is the schedule serializable?

1.2 Schedule B [8 points]

1.  [2 points] What conflicts exist between T1 and T2?

2.  [3 points] Is the schedule conflict serializable?

3.  [3 points] Is the schedule serializable?

1.3 Schedule C [8 points]

1.  [2 points] What conflicts exist between T1 and T2?

2.  [3 points] Is the schedule conflict serializable?

3.  [3 points] Is the schedule serializable?

1.4 Schedule D [10 points]

1.  [2 points] What conflicts exist between T1 and T4?

2.  [2 points] What conflicts exist between T3 and T4?

3.  [3 points] Is the schedule conflict serializable?

4.  [3 points] Is the schedule serializable?

Question 2. Left-Deep Plan (36 points)

Consider the following schemas:

Team(tid, tname, sport,

ranking) Game(tid, vid, date,

result) Venue(vid, vname)

Consider the following query for question 1:

SELECT T.tname

FROM Team T, Game G, Venue V

WHERE T.tid = G.tid AND

G.vid = V.vid AND

T.sport = ‘football’

AND

V.vname = ‘Michigan Stadium’;

Q2.1 [3 points] Given the above schema and no information on data sizes, select the plans that are valid left-deep plans for the query (avoid plans that cause a join to degenerate into a cross-product) from the plans given below.

Q2.2 [33 points] Consider the following plan for the questions that follow later in this problem. This plan only shows the join operators. Assume that selections and projections are applied on the edges as appropriate so that they are moved inside to reduce table sizes as much as possible prior to any joins.

For example, between relation T and the join operator, you would want to do a selection on T.sport = 'football'and also a projection to remove columns that are not going to be used. You can assume that projections and selections can be done together as tuplesof T are being read into the buffer. Similarly, you will want to insertselections and projection operators along other edges as needed.

Consider the following information.

Team Table: 600 data pages

● There are 5 types of sports, one of which is football. All teams play a sport and each sport has the same number of teams that play it.

● Index on Team Table: Clustered B+ tree index on attribute sport. The entire tree, including the leaves, lives in memory.

Venue Table: 300 data pages

● There are 4 uniquely named venues, the best of which is “Michigan Stadium”. Every venue has the same number of records. (Note that each uniquely named venue can have multiple vids)

● No indexes are available on Venue.

Game Table: 1200 data pages

● Every team has the same number of venues where it participated in a game as any other team.

● Every venue has the same number of teams that played in it as any other venue. ● No indexes are available on Game.

System Info:

● Page size = 512 bytes

● Each attribute is 64 bytes