• GRADES: check here after each exam.
• PROJECT GROUPS: your groups.
• Slides: Intro1, Chp7: internet application, Chp2: ER Diagram, Chp3: Relational Model, Chp4: Relational Algebra, Chp5: SQL, Chp8&9: Storage, Chp10: B+-tree, NEUStore, Query Evaluation, External Sort, Hash Index, Ch17: concurency control, Ch18: recovery,
• [1/28/2009] Homework 1: read chapters 1, 2, 3, 4, 5. Exercise 2.1, 2.2, 3.4, 3.6, 3.8, 4.3(1-4). All the problems on the relational algebra and SQL slides.
• Quiz 1 solution
• [2/11/2009] Homework 2:
  • If you are doing the game project, go through the Java game tutorial at here;
  • If you are doing the social network or the forum project, go through my chapter 3 located at here.
  • If you are doing the DBMS project, study the NEUStore package from here.
• [2/19/2009] Homework 3:
  • Read chapters 8, 9, 10 of the DBMS textbook.
  • Solve all the SQL problems on the slides that involves GROUPBY.
  • Book exercise 10.1.
  • Assume a harddrive has two platters, and each platter has 8 tracks, and each track has 8 sectors. So you can name each individual block on a disk such as (platter 1, track 1, sector 1), or (platter 2, track 8, sector 8). Suppose the first block of a file is stored at (platter 1, track 2, sector 1). And suppose the file occupies 30 blocks. Describe how you would store the file on disk so as to minimize sequential access of it. Suppose every seek time takes 5ms, every rotational delay takes 1ms, and every block transfer takes 0.2ms. How long does it take to sequentially access the file once (assuming the disk heads were on cylinder 7 initially)? answer
  • Do the LRU buffer exercise on page 21 of the B+-tree slides. (Note: within the same level, the orders of logical operators does not matter typically).
  • Suppose in a B+-tree with three levels, every index node can have up to 200 children (half full means 100 children), and every leaf node can store up to 20 records. What is the maximum and minimum number of records that the tree can hold? For an insertion (assume the record did not exist in the tree beforehand), what is the maximum and minimum number of logical I/O requests to the buffer manager? answer
  • Consider a sorted file. Let the smallest key in each page be: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200. Draw the intermediate result of bulkloading a B+-tree immediately (a) after processing 50; (b) after processing 100; (c) after processing 150; and (d) after bulk-loading has finished. Assume an index node can hold between 3 and 6 keys, and we desire a fill factor of 2/3. answer
• Quiz 2 Solution
• [3/12/2009] Homework 4:
  • Study the JPA/Spring/Hibernate tutorial of MyEclipse.
  • Do the exercises on the "Hash Index" slides. answer
  • Let there be a file with 10 pages. Let every page store two records. Let the 20 records stored in the file have keys 20 down to 1 (decreasing order). E.g. the second page stores keys 18 and 17. Let there be a 4-page memory buffer. Tell the content of the file after each pass of the external-memory merge-sort algorithm. How many I/Os are needed to sort the whole file? How many I/Os are needed if the sorted file does not need to be written to disk. answer
• [3/12/2009] Homework 5:
  • Let |E|=10,000, T(E)=100,000, |D|=200, T(D)=2,000.
  • Assume both the E table and the D table has a primary B+-tree index (on their primary keys SSN and did, respectively). Let both B+-trees have height 3. Assume for every B+-tree, the root page is pinned in memory but the other pages are not in memory.
  • Let memory buffer size be 51 pages (without counting the pinned B+-tree root pages).
  • Let V(E, SSN)=100,000. Let the range of SSN be from 000-00-0000 to 999-99-9999.
  • Let V(D, budget)=200.
  • Consider a SQL query:
    SELECT E.Name, D.Dname
    FROM Emp E, Dept D
    WHERE E.Did=D.Did
  • Draw the best logical query plan.
  • Estimate the cost of executing the SQL query using the following five physical query plans: BNL (let E be the outer table); BNL (let D be the outer table); merge join; hash join; index join.
  • answer.
• quiz 3 solution
• [4/10/2009] Homework 6:
  • Let there be two tables: R1(A,B,C) and R2(C,D).
  • Let T(R1)=2000, V(R1,A)=2000, V(R1,B)=500, V(R1,C)=80.
  • Let T(R2)=100, V(R2,C)=100, V(R2,D)=20.
  • Let X = R1 natural joins with R2.
  • Let Y = σ_B=100R1.
  • Estimate T(X), V(X,A), V(X,B), V(X,C), V(X,D).
  • Estimate T(Y), V(Y,A), V(Y,B), V(Y,C).
  • If the table R1 fits in 200 disk pages, and if you have a memory buffer of 5 pages, what's the I/O cost to sort R1?
  • For answers, click here.
• [4/10/2009] Homework 7:
  • What's the cost to hash-join two tables, with 2000 pages and 20,000 pages, respectively, with a memory buffer of 11 pages, assuming perfect hashing? here.
• [4/10/2009] Homework 8
  • Let |E|=10,000, T(E)=100,000, |D|=200, T(D)=2,000.
  • Assume both the E table and the D table has a primary B+-tree index (on their primary keys SSN and did, respectively). Let both B+-trees have height 3. Assume for every B+-tree, the root page is pinned in memory but the other pages are not in memory.
  • Let memory buffer size be 51 pages (without counting the pinned B+-tree root pages).
  • Let V(E, SSN)=100,000. Let the range of SSN be from 000-00-0000 to 999-99-9999.
  • Let V(D, budget)=200.
  • Consider a SQL query:
    SELECT E.Name, D.Dname
    FROM Emp E, Dept D
    WHERE E.Did=D.Did AND E.ssn>"600-00-0000" AND E.ssn<"900-00-0000" AND D.budget=8556
  • Draw the best logical query plan.
  • Estimate the cost of executing the SQL query using the following five physical query plans: BNL (let E be the outer table); BNL (let D be the outer table); merge join; hash join; index join.
  • For answers, click here.
• [4/10/2009] Homework 9:
  • Explain the ACID properties of transactions.
  • What is a serial schedule?
  • Does the following schedule conform with 2PL? What about strict 2PL? S(1), R(1), X(2), W(2), S(3), R(3), U(1), R(2), U(2), U(3), C.
  • Is it true that 2PL only allows serializable schedules? What about strict 2PL?
  • Explain Wait-Die and Wound-Wait protocols for deadline prevention.
  • In multi-granularity locking, the locks a transaction can apply for are: IS, IX, S, X, SIX. What does each of the lock conflict with? For instance, IS conflicts with X.
  • An alternative way of asking this question can be: suppose transaction T1 is holding an IX lock on a table. Can another transaction T2 get an S lock on the table?
  • The four tree-locking problem in concurrency slides.
  • The Read and Write algorithms in Timestamp CC.

Instructor

Office Hours: W 2:30-5:30pm.
Office: 478WVH
Phone: x2177
Email: donghui AT ccs.neu.edu

Lecture: W 6-9pm, 429 Ryder.

TA

Overview

Grading

• Quizzes: 30%
• Project: 35%
• Final 35%

Textbook

Project

• You can either do the projects alone, or be part of a group of at most four people. Doing the project alone will not be weighted more in grading. In any group, every group member will receive exactly the same project score regardless of how much contribution each individual has.
• The project should be submitted to the TA (not me).
• Advice: start doing the project early!
• Overall picture: we will collectively build a database-backed J2EE web site.
• You can choose among:
  • Build a multi-user game.
  • Build a forum.
  • Build a social networking site.
  • Build a DBMS. Note: this choice is provided for those who really want to understand what's in the black box. Description is here.
• For the first three project options, you have more flexibility to choose what to implement. But for all of them you should go through the first three chapters of my java web game book.

Tentative Schedule

Academic Honesty