CS 6890 Web-based Database Management Systems Homework Three

Homework Three - More Fun with Queries
CS 6890 - Web-based Database Management Systems
Utah State University


Home
Lectures
Homework
Syllabus
Resources
People

Due date: Monday, March 24 at the start of class (9:10AM).
Instructions: Please turn your homework in at the start of class.
Weight: The homework will count approximately 5% of your final grade.

Consider a supplier-parts example database (modified from an example in a book by C. J. Date). The database has the schema listed below (for Datalog, imagine a collection of ground facts, e.g., supplier(acme, paris)).
supplier (SupplierName, City)
part (PartName, Color, Weight)
subpart (PartName, SubPartName)
shipment (SupplierName, PartName, Date)

Formulate the following queries in Datalog.
1. What are the names of suppliers located in Paris that ship red parts?
2. Which parts have been shipped by at least two different suppliers?
3. What are all the subparts of an engine?
4. Which cities are related by the fact that they both ship an engine subpart?
Assume that there is an XML document with the following structure.
```
  <supplier name="ACME">
    <city>Paris</city>
    <part name="Engine">
      <color>red</color>
      <subpart name="...">
        <subpart name="...">...
            Could be many levels of subparts
        </subpart>
        ...
      </subpart>
    </part>
  </supplier>
```
Formulate the following queries in XQuery.
1. What are the names of suppliers located in Paris that ship red parts?
2. Which parts have been shipped by at least two different suppliers?
3. What are all the subparts of an engine?
4. Which cities are related by the fact that they both ship an engine subpart?
Exercise 12.3 part b) only
Exercise 12.20
Consider a disk with block size of 1024 bytes. Assume a block pointer is 8 bytes. Assume a record pointer is 10 bytes. Assume that a PERSON relation is stored in contigous blocks on disk with a fill percentage of 100%. PERSON has 1,000,000 tuples. Each column in a tuple is the following size: NAME(40 bytes), SSN(9 bytes), DOB(6 bytes), and PHONE(9 bytes). SSN is the key of the relation. Let SEEK be a disk read or write that re-positions the disk head, while NEXT is the read or write of the next block (i.e., without re-positioning the disk head).
For each of the following scenarios, state how many disk SEEKs and NEXTs for the given query. Also, if an index is involved, state how large the index is (in blocks).
1. How many blocks does the relation occupy?
2. Assume the file is ordered sequentially on SSN. How many disk SEEKs and NEXTs will be needed to find the PERSON with SSN = 1234123?
3. Assume the file is ordered sequentially on SSN. Assume one hundred people on avarage share the same name. How many disk SEEKs and NEXTs will be needed to find all of the people with NAME = 'Joe'?
4. Assume the file is sequentially ordered on NAME (a non-unique column). Assume one hundred people on avarage share the same name. How many disk SEEKs and NEXTs will be needed to find the PERSON with NAME = 'Joe'?
5. Assume that a primary, sparse index is created. How large is the index? How many disk SEEKs and NEXTs will be needed to find the PERSON with SSN = 1234123?
6. Assume that a secondary, dense index is created for SSN (SSN is a unique column). In the dense index, record pointers are used. How large is the index? How many disk SEEKs and NEXTs will be needed to find the PERSON with SSN = 1234123?
7. Assume a sparse, multi-level, primary index on SSN. How many disk SEEKs and NEXTs will be needed to find the PERSON with SSN = 1123233?
8. Assume a clustering B+-tree index on NAME. Assume one hundred people on avarage share the same name. Assume that the index is 69% full. How many disk SEEKs and NEXTs will be needed to find the PERSON with NAME = 'Joe'?

E-mail questions or comments to Curtis.Dyreson at usu dot edu