Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-13
G.21. Develop an algorithm to produce a report listing the IDs of students enrolled in each
class using the linked-list structure in Figure G-4.
/* This algorithm is in pseudocode. */
/* It would need to be re-coded for actual use. */
/* */
Call Procedure (Print-Header)
DO WHILE RRN > 0
IF Semester(RRN) = CurrentSemester
THEN
IF Class-Number(RRN) = CurrentClass
Call Procedure (Print-Header)
Call Procedure (Print-SN)
END IF
Set RRN = ClassLink(RRN)
END DO WHILE
New page
PROCEDURE PRINT-HEADER
new page
Print “Semester = “, CurrentSemester, “ “,
“Class = “, CurrentClass
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-14
OUTPUT:
Semester = 2015S Class = 20
100
——————————————-
Semester = 2014F Class = 20
300
G.22. Develop an algorithm to insert records into the structure in Figure G-4. The resulting
structure should resemble the one shown in Figure G-5.
/* This algorithm is in pseudocode. */
/* It would need to be re-coded for actual use. */
/* */
Set NewRecordRRN = NOR + 1
Set NewRecordSN = Student-Number(NewRecordRRN)
Set NewRecordCN = Class-Number(NewRecordRRN)
/* UPDATE Student Links. */
/* Case 1 – New Record RRN should replace StartOfStudentList. */
Set SRRN = StartOfStudentList
Set SFLAG = 1
IF NewRecordSN < Student-Number(SRRN)
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-15
/* Case 2 – New Record RRN does not replace StartOfStudentList.
*/
DO WHILE SFLAG=1
IF NewRecordSN >= Student-Number(SRRN)
THEN
/* Check for end of list */
ELSE
Set NewRecordStudentLink = SRRN
Set StudentLink(PreviousSRRN) = NewRecordRRN
SET SFLAG = 0
END IF
END DO WHILE
DO WHILE CFLAG=1
IF NewRecordCN >= Class-Number(CRRN)
THEN
/* Check for end of list */
IF StudentLink(SRRN) > 0
THEN
Set PreviousCRRN = CRRN
Set CRRN = ClassLink(CRRN)
ELSE
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-16
G.23. Develop an algorithm to produce a report listing the IDs of students enrolled in each
class using the index structure shown in Figures G-8(a), G-8(b), and G-8(c).
/* This algorithm is in pseudocode. */
/* It would need to be re-coded for actual use. */
/* */
Set CurrentSemester = Semester(RRN)
Set CurrentClass = Class-Number(RRN)
Call Procedure (Print-Header)
DO WHILE RRN <> EndOfIndex
IF Semester(RRN) = CurrentSemester
THEN
IF Class-Number(RRN) = CurrentClass
THEN
ELSE
Set CurrentSemester = Semester(RRN)
Set CurrentClass = Class-Number(RRN)
Call Procedure (Print-Header)
Call Procedure (Print-SN)
END IF
Set RRN = Next-Index-RRN
END DO WHILE
New page
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-17
OUTPUT:
Semester = 2014F Class = 20
300
G.24. Develop an algorithm to insert a record into the structure shown in Figure G-8(a). Be
sure to modify both associated indexes shown in Figure G-8(b) and G-8(c).
/* This algorithm is in pseudocode. */
/* It would need to be re-coded for actual use.
*/
/* */
/* INSERT DATA ROUTINE */
/* Now the links have to be updated. */
Set NewRecordRRN = NOR + 1
Set NewRecordSN = Student-Number(NewRecordRRN)
Set NewRecordCN = Class-Number(NewRecordRRN)
/* NOTE: We need to be able to track where we are in the indexes. */
/* Therefore, we will use an Index Record Number (IRN), */
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-18
/* UPDATE Student Index. */
Set SIRN = 1
DO WHILE Student-Number(SIRN) <= NewRecordSN
/* Check for end of index */
IF SIRN+1 <> EOF
THEN
Set SIRN = SIRN +1
ELSE
Set SIRN = EOF
G.25. Develop an algorithm to delete a record from the structure shown in Figure G-34, which
shows a secondary key represented with a linked list. If all records for one of the credit-
limit categories (say, $1000) are deleted, should the associated head pointer also be
deleted? Why or why not?
Whether or not the associated head pointer should be deleted depends on whether or not the limit
category itself has been eliminated. If it has, the head pointer should be deleted since it will not
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-19
DO WHILE AccountNumber(RRN) <> DeleteAN
SET PreviousRRN = RRN
SET RRN = Link(RRN)
G.26. Develop an algorithm to insert a record into the structure shown in Figure G-34.
Suppose that the new record has a credit-limit value different from those already
established. Should the record be inserted and a new linked list established? Or should
the record be rejected? Who should make that decision?
Assuming the new record credit-value limit is not an error, whether or not the record should be
inserted should be decided by the person who has authority to establish new credit-value limits.
If a new credit-limit is established, insert the record. If not, reject the record.
/* This algorithm is in pseudocode. */
/* It would need to be recoded for actual use. */
/* The data is appended at this time. */
APPEND NewRecord
/* Now the links have to be updated. */
Set NewRecordRRN = NOR + 1
Set NewRecordCL = Credit-Limit(NewRecordRRN)
Appendix G – Physical Database Design and Data Structures for Database Processing
THEN
CREATE HEAD for NewRecordCL
Set Link(NewRecordRRN) = 0
END IF
G.27. Why do most commercial DBMS products automatically create an index on a table’s
primary key?
A primary key is the primary means of accessing rows in a table. Thus we expect many queries to
G.28. What is an exact-match or equality query?
An exact-match or equality query is one in which the only comparisons are equality comparisons
G.29. What is a range query?
A range query is a query in which there is at least comparison involving > or <. These queries
G.30. How can an index speed up the processing of a query whose WHERE clause contains
the comparison “Salary = 50000”? What kind of index could help?
In this case the index can lead us directly to all rows with a Salary value of 50000. Without the
G.31. How can an index speed up the processing of a query whose WHERE clause contains
the comparison “Salary > 35000 AND Salary < 75000”? What kind of index could help?
An index can get us quickly to the first row with Salary > 35000. From there, we can scan
G.32. What is a clustered index? How many clustered indexes can a table have?
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-21
A clustered index is one in which the order of the table’s rows in secondary memory is based on
G.33. What kind of index can be most helpful in processing an ORDER BY query?
A clustered index is most helpful, as the data are already sorted in the appropriate way. As
G.34. Give an example of an index and a query, other than those presented in this appendix,
that would enable the query to be answered by examining only the index, not the actual
data.
If there is a multicolumn index on (CUSTOMER.AreaCode, CUSTOMER.PhoneNumber), then
G.35. What is the difference between an index on columns (LastName, ZIPCode) and an index
on columns (ZIPCode, LastName)? Give an example of a query that could benefit from
either index. Give an example of a query that could benefit from one index but not the
other.
The index on (LastName, ZIPCode) will have the search keys ordered first by LastName, then
G.36. In a table with two columns, how many different indexes can be created?
G.37. Why is it undesirable to create an index to speed up every possible query?
Not every possible query is equally likely, so many of these indexes will be a waste of time to
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-22
G.38. What is clustering? Give an example, other than those used in this appendix, of a query
and two or more tables for which clustering would be helpful.
Ordinarily, pages of data contain rows from a single relational table. Clustering is when rows of
G.39. Based on your answer to Review Question G.38, give an example of a query that will
now run slower than it would if clustering were not used.
The following query will now run slower, since it will have to examine a larger volume of data in
secondary memory:
G.40. What is vertical decomposition? What kind of SQL query can be used to reconstruct a
vertically decomposed table?
Vertical decomposition divides one logical table into two new physical relations by putting some
G.41. What is horizontal decomposition? What kind of SQL query can be used to reconstruct a
horizontally decomposed table?
Horizontal decomposition divides one logical table into two new physical relations by putting
G.42. What are the drawbacks with using vertical decomposition?
Any query that requires columns from both new decomposed relations will now require a join. In
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-23
G.43. What are the drawbacks with using horizontal decomposition?
Any query that requests rows from both new decomposed relations will now require a UNION in
G.44. What is a workload? Why is it important for a DBA to understand a database’s work–
load?
A workload is a description of the anticipated collection of queries and updates that will occur in