Questions:

* 13.1, 13.2, 13.3, 13.4, 13.7, 13.9

* 14.2, 14.3, 14.4, 14.5, 14.6, 14.7, 14.8

* 15.1, 15.5, 15.6, 15.7, 15.8, 15.10

* 16.2, 16.3, 16.4, 16.5

* 17.5, 17.6

#13.1

Why is it not desirable to force users to make an explicit choice of a query-processing strategy? Are there cases in which it is desirable for users to be aware of the costs of competing query-processing strategies? Explain your answer.

Users don't have all the information about internal costs of different strategies. Naïve users may choose an inefficient strategy because of their lack of full information. They would not know how a relation is stored, or what indices are available to speed queries; as a result they might make poor choices of query-processing methods. Ease of use is a major objective of database query languages, so we cannot (and do not want to) force users to be aware of these details.

In theory it is possible that users who are aware of the internal implementation details could write very efficient queries, helping performance. In practice this would only occur in the case where experts were using the system.

#13.2

Consider the following SQL query:

Select T.branch-name

From branch T, branch S

Where T.assets > S.assets and S.branch-city = "Brooklyn"

Write an efficient relational-algebra expression that is equivalent to this query and justify your choice.

Answer:

P _{T.branch-name}( (P _{T.branch-name,T.assets}(T)) |X|_{T.assets>S.assets} (P _S.assets(s _{S.branch-city="Brooklyn"}(S))) )

Justification: the most expensive operation in this query is the theta-join on assets. To make that operation as fast as possible, we attempt to reduce both sides of the join to the smallest relations possible. We do this in two ways: first by cutting down S (computing the selection on Brooklyn first, to remove the majority of tuples from S before the join), and second by reducing the size of the individual tuples on both sides of the equation, keeping only the necessary attributes (branch-name and assets from T, assets only from S).

#13.3

What are the advantages and disadvantages of hash indices relative to B+-tree indices? How might the type of index available influence the choice of a query-processing strategy?

Hash indices allow us to compute single-value lookups based upon a search key very, very quickly. B+-tree indices are much better at range queries. If there is a range query and a hash index is the only available index, the best strategy for processing that query would be to perform a full scan of the file rather than using the index.

#13.4

Assume only one tuple fits in a block and memory holds at most 3 page frames. Show the runs created on each pass of the sort-merge algorithm when applied to sort the following tuples on the first attribute:

(kangaroo, 17) run 1: (emu, 1) (emu, 1) (baboon, 12)

(wallaby, 21) (kangaroo, 17) (kangaroo, 17) (emu, 1)

(emu, 1) (wallaby, 21) (lion, 8) (hornbill, 2)

(wombat, 13) (platypus, 3) (hyena, 9)

(platypus, 3) run 2: (lion, 8) (wallaby, 21) (kangaroo, 17)

(lion, 8) (platypus, 3) (wombat, 13) (lion, 8)

(warthog, 4) (wombat, 13) (meerkat, 6)

(zebra, 11) (baboon, 12) (platypus, 3)

(meerkat, 6) run 3: (meerkat, 6) (hornbill, 2) (wallaby, 21)

(hyena, 9) (warthog, 4) (hyena, 9) (warthog, 4)

(hornbill, 2) (zebra, 11) (meerkat, 6) (wombat, 13)

(baboon, 12) (warthog, 4) (zebra, 11)

run 4: (baboon, 12) (zebra, 11)

(hornbill, 2)

(hyena, 9)

#13.7

The indexed nested-loop join algorithm described in section 13.5.3 can be inefficient if the index is a secondary index, and there are multiple tuples with the same value for the join attributes. Why? Describe a way, using sorting, to reduce the cost of retrieving tuples of the inner relation. Under what conditions would this algorithm be more efficient than hybrid merge-join?

If there are many tuples with the same value for the join attribute, we may have to access many different blocks of the inner relation for each tuple of the outer relation -- very expensive.

To reduce this cost we can create a temporary relation by joining the tuples of the outer relation only with the secondary index leaf-node entries -- in other words, just with the values found in the secondary index (and the address of the page they point to), not with the actual tuples they point to. That avoids multiple references to the same block through the secondary index. After that step is complete we sort the resulting tuples of the temporary relation based upon the addresses of the secondary-index pointers. Finally we go through the sorted pointers systematically to create the full join desired. This method has the significant advantage of only requiring one page read per page with desired tuples in the inner relation, rather than one page read per tuple, because the addresses are now sorted when we pass through the inner relation.

As for the comparison with hybrid merge-join, it (hyb-m-j) requires the outer relation to be sorted, where our algorithm above doesn't have that requirement. On the other hand, our algorithm must do an index lookup on the inner relation for each tuple in the outer relation. If the outer relation is much larger than the inner relation, then sorting the outer relation will be more costly than the index lookup on the inner relation, so our algorithm will be more efficient.

#13.9

Let R and S be relations without indices, and unsorted. Assuming infinite memory, what is the lowest-cost way (in terms of I/O) to compute R |X| S? How much memory does it require?

The lowest cost method is simply to load all of R and S into memory at once, requiring one page read per page of R and S combined, and (once the result is computed) one page write per page of the resulting tuple.

The amount of memory required is the size of R, plus the size of S, plus one page for results. As the single page for results fills up it can be written to disk and cleared for new results.

#14.2

Consider R1, R2, R3 with 1000, 1500, and 750 tuples respectively as described in the problem. Estimate the size of R1 |X| R2 |X| R3 and give an efficient strategy for computing the join.

Because natural join is associative and commutative, the result will be the same size no matter what order the relations are joined. Consider joining R1 and R2 first. We have 1000 unique tuples of R1. The two relations join on attribute C, which is a key for R2, so the join of R1 and R2 on C cannot be larger than 1000 tuples. Similarly, joining the temporary result (which is no larger than 1000) on attribute E with relation R3 (where E is a key to R3) can give us no more than 1000 tuples, so the result is no larger than 1000 tuples.

An efficient strategy would be to create an index on C for R2 and on E for R3. Then for each tuple in R1 we use the (primary) index on C to look up (at most) one tuple in R2 that matches the C value; if we find one we use the index on E to find a match within R3 for the R2 tuple; if we find that we put the resulting joined tuple in the result queue.

#14.3

Relations as above. Assume there are no primary keys except the entire schema. Let V(C,R1) be 900, V(C,R2) be 1100, V(E,R2) be 50, and V(E,R3) be 100. Sizes as above (1000, 1500, 750 respectively). Estimate the size of the triple natural join and give an efficient strategy for computing the join.

We can estimate the size of the result by calculating the average number of tuples which would be joined with each tuple of the second relation. So for each tuple in R1, 1500 (the size of R2) divided by 1100 (the number of values of C in R2) = 15/11 tuples of R2 which would join with R1 on average. So the intermediate relation of R1 |X| R2 would have 15000/11 tuples. For each tuple in R2 (or in the temporary relation R1 |X| R2), 750 (size of R3) divided by 100 (number of values of E in R3) = 7.5 tuples will join from R3, on average. So the total size will be about 15000/11*7.5, or about 10227 tuples. Note that joining R1 and R2 first increases creates a temporary result that is very close to the size of either, whereas joining R2 with R3 first creates a much larger temporary file (7.5 times the size of R2). So it is more efficient to join R1 and R2 first, and then join the result to R3.

#14.4

B+-tree index on branch-city; no other index available; what is the best way to handle the following selections that involve negation?

a) select all the tuples where branch-city is not less than "Brooklyn"

Use the index to find "Brooklyn", then choose all the tuples with greater than or equal value for branch-city.

b) select all the tuples where branch-city is not "Brooklyn"

There is no need to use the index -- just scan the file sequentially and copy all values not equalt to "Brooklyn" to the result

c) select all the tuples NOT fulfilling (branch-city < "Brooklyn" or assets < 5000)

This query is equivalent to the query: select branch-city>="Brooklyn" and assets>5000, which is a much easier query to compute. Use the B+-tree to find all the Brooklyn branches, then traverse them to find which tuples fulfill the assets>=5000 requirement.

#14.5

Suppose that we have a B+-tree index on (branch-name, branch-city) available on our branch relation. What would be the best way to handle the following selection?

With the index as described we follow the B+-tree to find the first tuple with branch-name = "Downtown", then we follow the pointers retrieving successive tuples as long as branch-city < "Brooklyn". When we hit the first tuple with branch-city >="Brooklyn" we have seen all the relevant tuples and we may stop. With the set of tuples generated, check each one as it comes in to see if it satisfies the condition on assets.

#14.6

show that each of the following equivalencies hold. Explain how that could be used to increase the efficiency of queries.

a) E₁|X|q (E₂ - E₃) == E₁|X|q E₂ - E₁|X|q E₃

On the left side, if a tuple belongs to the result then it must be a member of E₁|X|q Y, where Y is all the tuples in E₂ that are not in E₃. So every such tuple is in E₁|X|q E₂ and every such tuple may not be in E₁|X|q E₃. Since that is the right side of the equation, the two sides are equivalent.

Queries that are phrased in the format shown on the right side could be more efficiently computed by converting them to the left-side equivalence -- first a temporary result is computed by taking the difference between E2 and E3 (which will be no larger than E2), and then the theta-join of the temporary result and E1 is computed. That is one join and one difference. The right hand side, on the other hand, will be a much more costly operation with an additional join to a possibly very large relation (E3).

b)

Ignore this one -- assigned by mistake.

c)

s q (E1 left-outer-join E2) = (s q (E1)) left-outer-join E2

where theta uses only attributes from E1

Theta uses only attributes from E1. Examine (E1 left-outer-join E2) -- for any tuple t in that join to be filtered out by the selection of the left hand side, we must have that theta is false for that tuple. Since no attributes of the result tuples from E2 will be involved in the selection filtering, theta will be false for the tuple from E1 that was joined with some tuple in E2. All such tuples (where theta is false for a tuple in E1) will be eliminated by the selection on the right hand side. A similar proof will show that any tuple selected-out in the right hand side will also be selected-out in the left hand side, which suffices to prove that the two are equivalent.

This equivalence is useful because it allows us to use the right hand side by preference without affecting the results. Since the selection on theta is applied to E1 immediately, the join (an expensive operation) will be applied on a smaller (already-reduced) relation, and so will be cheaper.

#14.7 Show how to derive the following equivalences by a sequence of transformations (equivalence rules) in section 14.3.1

a)s q _{1 Ù q 2 Ù q 3}(E) = s q ₁ (s q ₂(s q ₃(E)))

by rule (1), we get

s q _{1 Ù q 2 Ù q 3}(E) = s q ₁ (s q _{2 Ù q 3}(E))

applying rule (1) again, we get

s q ₁ (s q _{2 Ù q 3}(E)) = s q ₁ (s q ₂(s q ₃(E)))

which is what we wanted to prove.

b) s q _{1 Ù q 2} (E1 |X|q ₃ E2) = s q ₁ (E1 |X|q ₃ (s q ₂ (E2))) where q 2 involves only attributes from E2.

By rule (1) we get

s q _{1 Ù q 2} (E1 |X|q ₃ E2) = s q ₁ (s q ₂ (E1 |X|q ₃ E2))

applying rule 7.a we get

s q ₁ (s q ₂ (E1 |X|q ₃ E2)) = s q ₁ (E1 |X|q ₃ (s q ₂ (E2)))

which is what we wanted to prove.

#14.8

For each of the following pairs of expressions, give instances of relations that show the expressions are not equivalent

a)

R={ (1,X) }

S={ (1,Y) }

The result of the left-hand side expression is {(1)}, while the right hand side is empty.

b)

R={ (1,2), (1,5) }

The result of the left-hand side is empty; the right hand side result is {(1,2)}

c)

Yes, if "max" is replaced by "min" the two sides become equivalent.

d)

R={(1,2)}

S={(2,3)}

T={(1,4)}

With these tuples (and the schema described in the hint) the left-hand result would be {(1, 2, null, 4)} and the right-hand result would be {(1, 2, 3, null)}

e)

Let R be on the schema (A,B) and S on (A,C).

Let R be {(1,2)} and S be {(2,3)} and let theta be the expression C=1.

The left-hand result is empty (none of the tuples fulfill theta) and the right hand side results in {(1, 2, null)}

#15.1

List the ACID properties and give the usefulness of each

C: Consistency. Execution of a transaction preserves the consistency of the database. This is typically the responsibility of the application programmer who codes the transactions.

A: Atomicity. Either all sub-operations that are part of the transaction become part of the database, or none do. Lack of Atomicity quickly leads to consistency problems.

I: Isolation. When multiple transactions operate concurrently, the results upon the database are the same as if they had operated one at a time (non-concurrently). This is important because it useful to run multiple transactions at the same time to maximize throughput and resource utilization, but non-serializability leads to consistency errors.

D: Durability. Changes made to the database persist, even if there are system failures. This is important for a wide variety of reasons -- we don't want to lose the results of transactions due to system faults.

#15.5

Possible sequences are:

• Active -- partially committed -- committed. This is the sequence for successful transactions.
• Active -- partially committed -- aborted. This is the sequence where the transaction finishes its internal calculations, but a fault occurs during its final writes of the results to disk, so the transaction must abort.
• Active -- failed -- aborted. This is the sequence where a fault occurs somewhere in the internal processing of the transaction, so the transaction fails and then aborts.

#15.6

Justify: "Concurrent execution of transactions is more important when data must be fetched from (slow) disk or when transactions are long, and is less important when data is in memory and transactions are very short"

Concurrent execution of transactions occurs when a number of transactions are running at the same time. If the number of transactions (overall) is fairly constant, the number that are running at any given moment will be larger if transactions are very long (have a lot of operations) and smaller if the transactions are very short. So concurrent execution is more important when transactions are long, because more of them will be running at the same time.

Similarly, if data must be fetched from disk then transactions will be running for longer periods of time than if the data is held in memory. If they run for longer periods of time then more of them will overlap (run at the same time) and concurrent execution will be more important.

#15.7

Explain the difference between the terms serial schedule and serializable schedule

A serial schedule is when all the operations of one transactions appear together (not mixed with the operations of any other transactions on the schedule).

A serializable schedule is a weaker term -- it is a schedule where the operations of different transactions may be mixed together on the schedule, so long as they are conflict-equivalent to some serial schedule.

#15.8

a) show that every serial execution of these two transactions preserves the consistency of the database:

The two possible serial executions are T1 and then T2; or T2 and then T1.

T1 and then T2:

Initially: A=0, B=0

After T1: A=0, B=1

After T2: A=0, B=1

Consistency Requirement is still valid.

T2 and then T1:

Initially: A=0, B=0

After T2: A=1, B=0

After T1: A=1, B=0

Consistency Requirement is still valid.

So after every serial execution of T1 and T2 the consistency is preserved.

b) Show a concurrent execution of T1 and T2 that produces a nonserializable schedule

Any interleaving of T1 and T2 produces a nonserializable schedule. Here is one example:

T1 T2

Read(A)

Read(B)

Read(B)

Read(A)

If B=0 then A=A+1

Write(A)

If A=0 then B=B+1

Write(B).

In the schedule above the result in the database is A=1, B=1, which is not consistent.

c) No. If the first step of T1 occurs after the last step of T2 (or vice versa) then the schedule is serial, by definition. In any other case we get a R/W conflict between T1 and T2. So there is no possible parallel execution that results from a serializable schedule.

#15.10

Consider figure 15.18. Is the corresponding schedule conflict serializable? Explain your answer.

Yes. There is no cycle in the precedence graph, so the schedule is serializable. A possible schedule can be obtained by doing a topological sort to get: T1, T2, T3, T4, T5. The other legal schedule is T1, T2, T4, T3, T5.

#16.2

Add lock and unlock instructions to T31 and T32 so that they observe the two-phase locking protocol

T31: lock-S(A)

Read(A)

Lock-X(B)

Read(B)

If A=0 then B=B+1

Write(B)

Unlock(A)

Unlock(B)

T32: lock-S(B)

Read(B)

Lock-X(A)

Read(A)

If B=0 then A=A+1

Write(A)

Unlock(A)

Unlock(B)

Can the result of these transactions result in a deadlock?

Yes. If both transactions execute their first lock statement before either of them executes their second lock statement then both will be holding a lock on one of the two data items A and B, and they will both be waiting for the other transaction to release the lock on the second item. Deadlock results.

#16.3

Strict two-phase locking produces only cascadeless schedules, so recovery is very easy. The disadvantage is that it is more restrictive -- a number of possible serializable schedules are not permitted compared to plain two-phase locking. This reduces the potential for concurrency.

#16.4

Rigorous two-phase locking gives the property that transactions can be serialized in the order in which they commit. It also has the advantages of strict two-phase locking.

#16.5

Most database systems use strict two-phase locking. Suggest three reasons for the popularity of this protocol.

• It is relatively easy to implement
• Cascadeless schedules impose a low rollback overhead -- in other words, when we are forced to roll back some transactions, the lack of cascading rollback means the burden is manageable (not too severe)
• The level of concurrency allowed is acceptable. More restrictive schemes don't allow as much concurrency; less restrictive schemes create the problems of implementation difficulty or possible cascading rollback.

#17.5

Explain the purpose of the checkpoint mechanism. How often should checkpoints be performed? How does the frequency of checkpoints affect

• System performance when no failure occurs
• Time it takes to recover from a system crash
• Time it takes to recover from a disk crash

Checkpointing is done on log-based recovery schemes to reduce the time required for recovery after a crash. Without checkpointing the entire log must be searched after a crash, and all transactions on the log must be redone/undone as appropriate. This can be an enormous amount of work. With checkpointing, it is only necessary to examine the log for transactions to redo/undo up to the point of the checkpoint; most of the other log records can be ignored (and the checkpoint can hold the locations or information of the few that cannot be ignored, so we don't need to search the whole log for them).

Performing checkpoints will slow the system down during their execution, so when failures are rare it will not be useful to checkpoint frequently. The tradeoff is whether it is more work (load on the system) to make checkpoints frequently, or whether it is worth the additional effort of longer recovery time after a crash to avoid slowing the whole system down with constant, frequent, checkpoints. If fast recovery is a high priority then we should increase the frequency of checkpoints.

Checkpoints reduce the time it takes to recover from a system crash. They have no affect upon the time it takes to recover from a disk crash; that is affected by the frequency of backups (archival data dumps).

#17.6

The first phase of recovery is to undo the changes done by the failed transactions, so that all data items which have been modified by them get back the values that they would have had if the failed transactions had never occurred. If several transactions modified the same data item, the undo operations must all be done in a reverse direction so that the final value left in the data item is the one before the FIRST of the failed transactions started its work.

The second phase of recovery is to redo the changes made by successful (completed) transactions. For this phase, the most recently written value is the one we want to remain in the data item, so we must process the redo operations in a forward direction (from farthest back to most recent) to ensure that occurs correctly.