1.Consider the following relation:
Emp(eid: integer, sal: integer, age: real, did: integer)
There is a clustered index on eid and an unclustered index on age.
1. How would you use the indexes to enforce the constraint that eid is a key?
2. Give an example of an update that is definitely speeded up because of the available indexes. (English description is suficient.)
3. Give an example of an update that is definitely slowed down because of the indexes. (English description is suficient.)
4. Can you give an example of an update that is neither speeded up nor slowed down by the indexes?
2.Consider a delete specified using an equality condition. For each of the five file organizations, what is the cost if no record qualifies? What is the cost if the condition is not on a key?
3.(Due to Jeff Derstadt) TechnoBooks.com is in the process of reorganiz-ing its website. A major issue is how to effciently handle a large number of search results. In a human interaction study, it found that modem users typically like to view 20 search results at a time, and it would like to program this logic into the system. Queries that return batches of sorted results are called top N queries. (See Section 23 for a discussion of database support for top N queries.) For example, results 1-20 are returned, then results 21-40, then 41-60, and so on. Different techniques are used for performing top N queries and TechnoBooks.com would like you to implement two of them.
Infrastructure: Create a database with a table called Books and populate it with some books, using the format that follows. This gives you 111 books in your database with a title of AAA, BBB, CCC, DDD, or EEE, but the keys are not sequential for books with the same title.
Books(bookid: INTEGER, title: CHAR(80), author: CHAR(80), price: REAL)
For i = 1 to 111 {
Insert the tuple (i, “AAA”, “AAA Author”, 5.99) i = i + 1
Insert the tuple (i, “BBB”, “BBB Author”, 5.99) i = i + 1
Insert the tuple (i, “CCC”, “CCC Author”, 5.99) i = i + 1
Insert the tuple (i, “DDD”, “DDD Author”, 5.99) i = i + 1
Insert the tuple (i, “EEE”, “EEE Author”, 5.99) }
Placeholder Technique:The simplest approach to top N queries is to store a placeholder for the ?rst and last result tuples, and then perform the same query. When the new query results are returned, you can iterate to the placeholders and return the previous or next 20 results.
Tuples Shown Lower Placeholder Previous Set Upper Placeholder Next Set
1-20 1 None 20 21-40
21-40 21 1-20 40 41-60
41-60 41 21-40 60 61-80
Write a webpage in JSP that displays the contents of the Books table, sorted by the Title and BookId, and showing the results 20 at a time. There should be a link (where appropriate) to get the previous 20 results or the next 20 results. To do this, you can encode the placeholders in the Previous or Next Links as follows. Assume that you are displaying records 21–40. Then the previous link is display.jsp?lower=21 and the next link is display.jsp?upper=40.
You should not display a previous link when there are no previous results; nor should you show a Next link if there are no more results. When your page is called again to get another batch of results, you can perform the same query to get all the records, iterate through the result set until you are at the proper starting point, then display 20 more results.
What are the advantages and disadvantages of this technique?
.Query Constraints Technique: A second technique for performing top N queries is to push boundary constraints into the query (in the WHERE clause) so that the query returns only results that have not yet been displayed. Although this changes the query, fewer results are returned and it saves the cost of iterating up to the boundary. For example, consider the following table, sorted by (title, primary key).
Batch Result Number Title Primary Key
1 1 AAA 105
1 2 BBB 13
1 3 CCC 48
1 4 DDD 52
1 5 DDD 101
2 6 ddd 121
2 7 EEE 19
2 8 EEE 68
2 9 FFF 2
2 10 FFF 33
3 11 FFF 58
3 12 FFF 59
3 13 GGG 93
3 14 HHH 132
3 15 HHH 135
In batch 1, rows 1 through 5 are displayed, in batch 2 rows 6 through 10 are displayed, and so on. Using the placeholder technique, all 15 results would be returned for each batch. Using the constraint technique, batch 1 displays results 1-5 but returns results 1-15, batch 2 will display results 6-10 but returns only results 6-15, and batch 3 will display results 11-15 but return only results 11-15.
The constraint can be pushed into the query because of the sorting of this table. Consider the following query for batch 2 (displaying results 6-10):
EXEC SQL SELECT B.Title FROM Books B
WHERE (B.Title = ’DDD’ AND B.BookId > 101) OR (B.Title > ’DDD’) ORDER BY B.Title, B.BookId
This query ?rst selects all books with the title ‘DDD,’ but with a primary key that is greater than that of record 5 (record 5 has a primary key of 101). This returns record 6. Also, any book that has a title after ‘DDD’ alphabetically is returned. You can then display the ?rst ?ve results.
The following information needs to be retained to have Previous and Next buttons that return more results:
Previous: The title of the ?rst record in the previous set, and the primary key of the ?rst record in the previous set.
Next: The title of the ?rst record in the next set; the primary key of the ?rst record in the next set.
These four pieces of information can be encoded into the Previous and Next buttons as in the previous part. Using your database table from the ?rst part, write a JavaServer Page that displays the book information 20 records at a time. The page should include Previous and Next buttons to show the previous or next record set if there is one. Use the constraint query to get the Previous and Next record sets.
Exercise 8.6 Fill in the I/O costs in Figure.
File Type scan Equality Search Range Search Insert Delete
Heap file
Sorted file
Clustered file
Unclustered tree index
Unclustered hash index
figure:I/O Cost Comparison