COMPSCI 186 Study Guide - Midterm Guide: Good Luck!!, Ibm System R, Redone

88 views9 pages

turquoisegnu128

8 Jan 2019

School

Department

Course

Professor

For unlimited access to Study Guides, a Grade+ subscription is required.

University of California, Berkeley

College of Engineering

Spring 2011 Prof. Michael J. Franklin

MIDTERM II

CS 186 Introduction to Database Systems

NAME: ____________________________ STUDENT ID:__________________

IMPORTANT: Circle the last two letters of your class account:

cs186 a b c d e f g h i j k l m n o p q r s t u v w x y z

a b c d e f g h i j k l m n o p q r s t u v w x y z

DISCUSSION SECTION DAY & TIME:____________ TA NAME: ___________

This is a closed book examination – but you are allowed one 8.5” x 11” sheets of notes (double

sided). You should answer as many questions as possible. Partial credit will be given where

appropriate. There are 100 points in all. You should read all of the questions before starting the

exam, as some of the questions are substantially more time-consuming than others.

Write all of your answers directly on this paper. Be sure to clearly indicate your final answer

for each question. Also, be sure to state any assumptions that you are making in your answers.

GOOD LUCK!!!

Problem

Possible

Score

1. Recovery

2. SQL

3. Relational Algebra

4. Query Evaluation and Optimization

TOTAL

100

Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

Already have an account? Log in

SID:____________________

CS 186 Midterm II April 7, 2011 Page 2 of 9

Question 1 – Recovery [7 parts, 31 points total]

Consider the following content of a log produced using Write-Ahead Logging. Assume that the

log contains all operations since the start of the DBMS. Note that at this point, no system crash

has occurred:

LSN

Transaction ID

Content

prevLSN

update P5

null

update P3

null

update P5

commit

Now consider four statements:

A. P5 appears in the dirty page table with recLSN 10

B. P5 appears in the dirty page table with recLSN 30

C. P5 appears in the dirty page table, but we don’t have enough information to know what

the recLSN would be.

D. None of the above

a) [3 points] Consider the state of the system during normal operation after the log record with

LSN 40 is written. If the buffer manager uses a “STEAL” / NO FORCE” policy, which one of

the above statements is guaranteed to be true? Why?

D. In steal/no-force, P5 and P3 can be flushed to disk anytime.

b) [3 points] Consider the state of the system during normal operation after the log record with

LSN 40 is written. If the buffer manager uses a “NO STEAL” / “NO FORCE” policy, which

one of the above statements is guaranteed to be true? Why?

A. In no-steal, P5 must not be flushed before T1 commits.

c) [3 points] Consider the state of the system during normal operation after the log record with

LSN 40 is written. If the buffer manager uses a “NO STEAL” / “FORCE” policy, which one of

the above statements is guaranteed to be true? Why?

A. In no-steal, P5 must not be flushed before T1 commits.

Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

Already have an account? Log in

SID:____________________

CS 186 Midterm II April 7, 2011 Page 3 of 9

Question 1 – Recovery (continued)

Below is the state of the log after a system crash has occurred. Assume STEAL/NO FORCE

buffer management and that the log contains all operations since the start of the DBMS.

LSN

XactId

Content

prevLSN

update P5

null

update P5

update P4

null

update P1

null

Commit

End

begin_checkpoint

end checkpoint

update P3

null

100

update P2

110

Abort

100

120

update P4

130

CLR: undo LSN 100, undoNextLSN = 20

110

d) [5 points] Assuming that no dirty pages were written to disk prior to the crash, What are

contents of the transaction table contained in the checkpoint ending at LSN 80?

XactID

LastLSN

Status

running

PageID

RecLSN

Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

Already have an account? Log in

Document Summary

Discussion section day & time:____________ ta name: ___________ This is a closed book examination but you are allowed one 8. 5 x 11 sheets of notes (double sided). You should answer as many questions as possible. You should read all of the questions before starting the exam, as some of the questions are substantially more time-consuming than others. Write all of your answers directly on this paper. Be sure to clearly indicate your final answer for each question. Also, be sure to state any assumptions that you are making in your answers. Score: recovery, sql, relational algebra, query evaluation and optimization. Question 1 recovery [7 parts, 31 points total] Consider the following content of a log produced using write-ahead logging. Assume that the log contains all operations since the start of the dbms. Note that at this point, no system crash has occurred: T2 update p5 update p3 update p5 commit.

Related Questions

1.Write a function encipher(s, n) that takes as inputs an arbitrary string s and a non-negative integer n between 0 and 25, and that returns a new string in which the letters in s have been "rotated" by n characters forward in the alphabet, wrapping around as needed. For example:

>>> encipher('hello', 1) result: 'ifmmp'

>>> encipher('hello', 2) result: 'jgnnq'

>>> encipher('hello', 4) result: 'lipps'

Upper-case letters should be "rotated" to upper-case letters, even if you need to wrap around. For example:

>>> encipher('XYZ', 3)

result: 'ABC'

Lower-case letters should be "rotated" to lower-case letters:

>>> encipher('xyz', 3)

result: 'abc'

Non-alphabetic characters should be left unchanged:

>>> encipher('#caesar!', 2)

result: '#ecguct!'

Hints/reminders:

You can use the built-in functions ord and chr convert from single-character strings to integers and back:

>>> ord('a')

result: 97

>>> chr(97)

result: 'a'

You can use the following test to determine if a character is between 'a' and 'z' in the alphabet:

if 'a' <= c <= 'z':

A similar test will work for upper-case letters.

We recommend writing a helper function rot(c, n) that rotates a single character c forward by n spots in the alphabet. We have given you a template for this helper function in ps3pr3.py that checks to ensure that c is a single-character string. We wrote rot13(c) in lecture; rot(c, n) will be very close to rot13(c)! You can test your rot(c, n) as follows:

>>> rot('a', 1)

result: 'b'

>>> rot('y', 2)

result: 'a'

>>> rot('A', 3)

result: 'D'

>>> rot('Y', 3)

result: 'B'

>>> rot('!', 4)

result: '!'

Once you have rot(c, n), you can write a recursive encipher function.

Once you think you have everything working, here are three more examples to try:

>>> encipher('xyza', 1)

result: 'yzab'

>>> encipher('Z A', 2)

result: 'B C'

>>> encipher('Caesar cipher? I prefer Caesar salad.', 25)

result: 'Bzdrzq bhogdq? H oqdedq Bzdrzq rzkzc.'

2.Write a function decipher(s) that takes as input an arbitrary string s that has already been enciphered by having its characters "rotated" by some amount (possibly 0). decipher should return, to the best of its ability, the original English string, which will be some rotation (possibly 0) of the input string s. For example:

>>> decipher('Bzdrzq bhogdq? H oqdedq Bzdrzq rzkzc.')

result: 'Caesar cipher? I prefer Caesar salad.'

Here are two more examples:

>>> decipher('Hu lkbjhapvu pz doha ylthpuz hmaly dl mvynla lclyfaopun dl ohcl slhyulk.')

result: 'An education is what remains after we forget everything we have learned.'

>>> decipher('python')

result: 'eniwdc'

------------------------------------

def rot(c, n):
""" your docstring goes here """
# check to ensure that c is a single character
assert(type(c) == str and len(c) == 1)

def letter_prob(c):
""" if c is the space character (' ') or an alphabetic character,
returns c's monogram probability (for English);
returns 1.0 for any other character.
adapted from:

"""
# check to ensure that c is a single character
assert(type(c) == str and len(c) == 1)

if c == ' ': return 0.1904
if c == 'e' or c == 'E': return 0.1017
if c == 't' or c == 'T': return 0.0737
if c == 'a' or c == 'A': return 0.0661
if c == 'o' or c == 'O': return 0.0610
if c == 'i' or c == 'I': return 0.0562
if c == 'n' or c == 'N': return 0.0557
if c == 'h' or c == 'H': return 0.0542
if c == 's' or c == 'S': return 0.0508
if c == 'r' or c == 'R': return 0.0458
if c == 'd' or c == 'D': return 0.0369
if c == 'l' or c == 'L': return 0.0325
if c == 'u' or c == 'U': return 0.0228
if c == 'm' or c == 'M': return 0.0205
if c == 'c' or c == 'C': return 0.0192
if c == 'w' or c == 'W': return 0.0190
if c == 'f' or c == 'F': return 0.0175
if c == 'y' or c == 'Y': return 0.0165
if c == 'g' or c == 'G': return 0.0161
if c == 'p' or c == 'P': return 0.0131
if c == 'b' or c == 'B': return 0.0115
if c == 'v' or c == 'V': return 0.0088
if c == 'k' or c == 'K': return 0.0066
if c == 'x' or c == 'X': return 0.0014
if c == 'j' or c == 'J': return 0.0008
if c == 'q' or c == 'Q': return 0.0008
if c == 'z' or c == 'Z': return 0.0005
return 1.0

olivemink636

9. Finally, you should write a program MontrealMaps which will suggest a path to go along the metro to get from one place to another. The only required method for MontrealMaps is a main method but of course you are allowed to write others. Your program should do the following. For any library methods that you use, make sure that you are properly importing things and handling any exceptions they may throw. (10 points) • Using an appropriate library method, you should create a Subway System object. If this method fails to initialize, you should print the message Error, not enough funding. • Use a Scanner and print statements to read the current x and y position of the user. • Use a Scanner and print statements to read the x and y position that the user wants to go to. . Find the nearest Metro Station to both the start position of the user and his final destination. • If the 2 metro stations have the same name (i.e. are the same metro station) then print It is fastest to walk there. • Otherwise, call the method findPath from the previous part to find a path from these 2 metro stations. . If the method returns null, then print Sorry, there is no path on the metro, you'll have to walk • Otherwise, print the path using the metro using the method printPath defined in the MapUtilities class in the appendix. SUMMARY OF JAVA STANDARD LIBRARY METHODS POR SELECTED CLASSES • String package java.lang) Methods - public boolean gist and e rs is stingeancoject - puble boolean grease Sering another ca t ering String paint i th Stre C h eshilly before the Stripe with striert w Single weiter water N ENE fusha -publish tohy Casting de . File( p age java.io) Methods r eate - publie Yiling path : C • Scanner (package java.ut 1) Method -ple S ule - double Double Sc - le bon when : S Scanner tal de fethede h able othebean - puble String Best Mus eethe u s tepal -pulle haalean haxtLine: Check the hea ther in left PrintStream( p age java.io) Methods pul vaid pri Pribonaat - puli wid pride d oble vile. - pille vaid print Print vei. -pulle vaid printject o: Prints Object -puli vaid printString : Prints String .. - vaid primi The theme line by writing the li n e tie id print in bool bl. Prise n value the - public void platinabled Prints double ved and then the line - public void printit Prints Ent value and then tomis the - Pull vaid pri l l be t he minime publie wild prin t ing with String in the terminates the line • ArrayLiat package java.util) Methods - public boolean Arraybettype was a new ArrayList

COMPSCI 186 Study Guide - Midterm Guide: Good Luck!!, Ibm System R, Redone

Document Summary

Get access

Related Documents

COMPSCI 186 Study Guide - Midterm Guide: Good Luck!!, Hard Disk Drive, Binary Search Algorithm

COMPSCI 186 Study Guide - Midterm Guide: Query Optimization, Functional Dependency, Good Luck!!

COMPSCI 186 Midterm: cs186-fa2004-mt2-Franklin-soln

Related Questions