HW5 Solutions Page

Return to homework page.

18.5

We are to answer the following questions with respect to Figure 18.8 out of the book when we append four additional log records for recovery attempts followed by crashes. Lets say these records are:

100 CLR: Undo T1 LSN 80 undoNextLSN 20
110 CLR: Undo T3 LSN 60 undoNextLSN 40
crash
120 CLR: Undo T3 LSN 40 undoNextLSN null
130 T3 end

1. What is the value of the LSN stored in the master log record?

00, the LSN of the begin_checkpoint of the last completed checkpoint.

2. What is done during Analysis?

Initialize the dirty page table and the transaction table. As we don't know what went on before LSN 00, we assume these are both empty. Analysis then scans forward. Entries for T1, T2 and T3 are added to the Transaction table. Also, each of these transactions has some redoable operations, so the pages they redoably affect are added to the dirty page table. Namely, P1 with recLSN 20, P2 with recLSN 30, P3 with recLSN 40, and P5 with recLSN 80. The end of T2 is then seen so it is removed from transaction table. Similarly, the end of T3 is seen and removed from the transaction table. lastLSNs of T1 are initially set to 120. The status of T1 is set to C.

3. What is done during Redo?

The redo phase begins at LSN 20 (the smallest recLSN in dirty page table). It then reapplies the operations in LSNs 20, 30. The operations 40, 60, and 80 are not reapplied because the pageLSN for these pages will be larger then the log record LSN.

4. What is done during Undo?

The und phase would produce the additional records:

140 CLR: Undo T1 LSN 20 undoNextLSN null
150 T1 end

5. Show the log when recovery is complete, including all non-null prevLSN and undonenextLSN values in log records.

The complete log will be figure 18.8 from the book, followed by LSNs 100-130 listed above, followed by 140 and 140 list in part 4.

20.4

1. List the FDs that are given to hold over G.

Chapters keep moving to new locations and a new president is elected when and only the chapter moves. This implies the dependencies (a) P-->L, (b) CL--> P. I don't say L--> P. Because maybe Chapter X1 moves away from location P1 and then Chapter X2 moves to location P1. We are also told a president of a chapter can never serve as a president of any other chapter. this implies (c) P-->C. Each chapter gives its president some salary. My guess as to why they would mention this is because they want the dependency: (d) C --> S.

2. What are candidate keys for relation G?

From P using the above depencies we can derive back all the columns. Also, from CL we can derive back all the columns.

3. What normal form is the schema G in?

It is in first normal form only, the dependency C --> S, is a partial dependency on a candidate key ruling out second normal form.

4. Design a good database schema for the club.

We could split G into two tables G'(PCL) and G''(CS).

5. What normal form is your schema in? Give an example of a query that is likely to run slower on this schema than on the relation G.

My schema is in BCNF since in dependencies (a) and (c), P is a key and hence superkey. In dependency (b), CL is a superkey. A slow query might be: find all presidents who recieved a give salary.

6. Is there a lossless-join, dependency preserving decomposition of G into BCNF?

Our schema above is in BCNF and preserve dependencies, so the question is whether it has the lossless join property. To see this look at Theorem 3 of Chapter 19. R1 intersect R2 is in this case G' intersect G'' = {C}. Then we note C-->CS by (d) and since C--> C.

7. Is there ever a good reason to accept something less than 3NF when designing a schema for a relational database?

A possible situation where is might be useful is if there were an extremely frequent query that involved all attributes of our original table G and if there were no other operations that would be slowed by the weaker normal form.

20.6

1. Describe the physical design you would choose for this relation. That is, what kind of a file structure would you choose for these relations, and what indexes would you create?

The frequent queries are to find the location where an employee works and whether the budget of a department is greater thatn the salary of each of it employees. Our tables are Emp(eid*, sal, did) and Dept(did*, location, budget). We could evaluate this first query by doing a look-up of the `did' of the employee and then use this `did' to find the location of the department. Both of these are equality selections. The second query involves summing all the salaries in Emp with a given `did' value. Then the sum for this `did' is compared with the budget for this same `did' in Dept. So again an equality selection is needed. For the first query, it makes sense to have hash indexes on `eid' of Emp and `did' of Dept. For the second query, it might make sense to cluster the data of Emp by `did' and then index it as well.

2. Explain how you would try to obtain better performance by describing the schema for the relation(s) that you would use and your choice of file organizations and indexes on these relations if you were allowed to redesign the schema.

You could try and create a new table Emp_loc(eid*, location) or change Emp to Emp(eid, sal, did, location) and put an index on both of eid and location.

3. Suppose that your database system has very inefficient implementations of index structures. What kind of design would you try in this case?

Could cluster Emp by `did' and Dept by `did' then maybe create a separate table with attributes eid and location.

Grant experiment:

First, I created a new account:

C:\Documents and Settings\cpollett>sqlplus me/password@ep

SQL*Plus: Release 9.0.1.3.0 - Production on Thu Dec 11 14:17:23 2003

(c) Copyright 2001 Oracle Corporation.  All rights reserved.


Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production

SQL> create user bob identified by "hello"
  2  default tablespace users
  3  temporary tablespace temp;

User created.

SQL> grant connect, resource to bob;

Grant succeeded.

SQL>

Now we create a table and add some rows and revoke bob's privileges on it:

SQL> create table employee(
  2  fname varchar(20),
  3  lname varchar(20),
  4  salary int,
  5  address varchar(30));

Table created.

SQL> insert into employee values(
  2  'grace',
  3  'jones',
  4  300000,
  5  'mars');

1 row created.

SQL> insert into employee values(
  2  'Joe',
  3  'Black',
  4  100000,
  5  'Obscure');

1 row created.

SQL> revoke select on employee from bob;

Revoke succeeded.

SQL>

Note by default bob shouldn't have select privileges but we are making really sure. Now let's connect to bob and see if bob can see anything.

C:\Documents and Settings\cpollett>sqlplus bob/hello@ep

SQL*Plus: Release 9.0.1.3.0 - Production on Thu Dec 11 14:47:54 2003

(c) Copyright 2001 Oracle Corporation.  All rights reserved.


Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production

SQL> select * from me.employee;
select * from me.employee
                       *
ERROR at line 1:
ORA-00942: table or view does not exist


SQL>

Okay, so let's give bob select privileges:

SQL> grant select on employee to bob;

Grant succeeded.

SQL>

Now what does bob see?

SQL> select * from me.employee;

FNAME                LNAME                    SALARY
-------------------- -------------------- ----------
ADDRESS
------------------------------
grace                jones                    300000
mars

Joe                  Black                    100000
Obscure


SQL>

OO/XML Experiment

First, we create a type address. This works in both in 9i and 8i.

SQL> create or replace type address as object
  2   (city varchar(10),
  3   state char(2),
  4   zip number(5)) not final;
  5  /

Type created.

This was not part of the assignment, but in 9i we could have created a subtype of address using:

SQL> create type rural_address under address
  2  ( routeno number);
  3  /

Type created.

Doing something like the above was the alternative version of the XMLTYPE part of this assignment if you were working at school and did not have access to 9i. For now, we create a table using our address type and insert some rows into it:

SQL> create table employee (
  2  fname varchar(20),
  3  lname varchar(20),
  4  salary int,
  5  address address);

Table created.

SQL> insert into employee values ('bob', 'the builder', 200,
  2  address('somewhere','ca',95000));

1 row created.

SQL> insert into employee values ('sam', 'the sailor', 300,
  2  address('not here','mo',12000))
  3  /

1 row created.

SQL> select * from employee;

FNAME                LNAME                    SALARY
-------------------- -------------------- ----------
ADDRESS(CITY, STATE, ZIP)
--------------------------------------------------------------------------------
bob                  the builder                 200
ADDRESS('somewhere', 'ca', 95000)

sam                  the sailor                  300
ADDRESS('not here', 'mo', 12000)

For the second part of the OO experiment we first create a DTD for addresses:

<?xml version="1.0" encoding="UTF-8"?>
<!-- created  by Chris Pollett (SJSU) -->

<!ELEMENT address (city, state, zip)>
<!ELEMENT city (#PCDATA)>
<!ELEMENT state (#PCDATA)>
<!ELEMENT zip (#PCDATA)>

Now we create a new version of Employee that could make use of this type and insert some stuff into it:

SQL> create table employee2 (
  2  fname varchar(20),
  3  lname varchar(20),
  4  salary int,
  5  address2 xmltype)
  6  /


SQL> insert into employee2 values
  2  ('Paul', 'Bunyan', 20000,
  3  xmltype.createxml('<?xml version="1.0"
encoding="UTF-8"?><address><city>Cowville</city><state>IN</state>
  4  <zip>20200</zip></address>'))
  5  /

1 row created.

SQL>  insert into employee2 values
  2  ('Samuel', 'Adams', 2000000,
  3  xmltype.createxml('<?xml version="1.0"
encoding="UTF-8"?><address><city>Boston</city><state>MA</state>
  4  <zip>02600</zip></address>'))
  5  /

1 row created.


SQL> select * from employee2;

FNAME                LNAME                    SALARY
-------------------- -------------------- ----------
ADDRESS2
--------------------------------------------------------------------------------
Paul                 Bunyan                    20000
<address>
  <city>Cowville</city>
  <state>IN</state>
  <zip>20200</zip>
</addre

Samuel               Adams                   2000000
<address>

FNAME                LNAME                    SALARY
-------------------- -------------------- ----------
ADDRESS2
--------------------------------------------------------------------------------
  <city>Boston</city>
  <state>MA</state>
  <zip>02600</zip>
</address

SQL>

If you were doing everything at school using 8i then the XMLTYPE stuff won't work. Instead, I said in class you should try to look up on the web how to create subtypes in Oracle 8i. About the only way to do this is to fake it with nested tables. For example:

SQL> create or replace type address_table as table of address
  2  /

Type created.

SQL> create type rural_address as object (
  2  routno number(2), address address_table);
  3  /

Type created.

Note: when you create type address as given earlier in the 8i version forget the words not final.

Return to homework page.