ug_ch4b.htm

db.* (pronounced dee-be star) is an advanced, high performance, small footprint embedded database fo

   Type: data
   Size of record slots : 90
   Record slots per page: 5
   Unused page space    : 58

FILE: chkg.k01
   Id  : 1
   Type: key
   Size of record slots : 16
   Record slots per page: 63
   Unused page space    : 6

FILE: chkg.k02
   Id  : 2
   Type: key
   Size of record slots : 14
   Record slots per page: 145
   Unused page space    : 8

RECORD: BUDGET
   Id  : 0
   File: chkg.dat [0]
   Total set pointers   : 1
   Total member pointers: 0
   Offset to data       : 26
   Size of record       : 90
   Unused slot space    : 0

RECORD: CHECK
   Id  : 1
   File: chkg.dat [0]
   Total set pointers   : 0
   Total member pointers: 1
   Offset to data       : 18
   Size of record       : 78
   Unused slot space    : 12
</font>
</pre>
<p><font size="2">The summary for each data and key file includes
the following:</font></p>
<ul>
<li>File name</li>
<li>File id number</li>
<li>File type: data or key</li>
<li>Size of each record or key slot in bytes</li>
<li>Total number of slots per page</li>
<li>Total amount of unused page space</li>
</ul>
<p>The information most significant to database design is the
number of slots per page and the amount of unused page space in a
data file. The unused page space occurs because the slot size
multiplied by the number of slots per page does not always exactly
equal the size of the database page. Much of this unused space can
be reserved by adding an extra (unused) data field to the largest
record on the file. The length of the field is computed as
follows:</p>
<div style="margin-left: 4em">
<p>length = (unused page space) / (slots per page)</p>
</div>
<p>The unused space is contained in a record so that if additional
data needs to be stored in that record, space will be available. If
the reserved space is large enough, the new field can be added
without restructuring the database.</p>
<p>The record summary contains the following information.</p>
<ul>
<li>Record name</li>
<li>Record number</li>
<li>File in which record is contained</li>
<li>Total number of set pointers (sets owned by record)</li>
<li>Total number of member pointers (sets in which record is
member)</li>
<li>Offset to start of data from start of record</li>
<li>Total size of record in bytes</li>
<li>Amount of unused slot space</li>
</ul>
<p>The design-related information in this report is the unused slot
space. This space can easily be converted into a usable form by
adding an extra field the length of the unused slot space to the
record. Then, as explained above, the space is available for
additional data to be stored in the record at a later date, without
requiring a restructure of the database.</p>
<p>Also important in calculating the size of the records is the
ordering and size of the data types used in the record. Most
systems require numeric data to start on word boundaries. This
means that if the field preceding a numeric field does not end on a
word boundary, unseen and unusable padding is inserted to force the
numeric data to the word boundary. When character and numeric data
are not carefully mixed, wasted space can be generated.</p>
<h4><a name="Sizes" id="Sizes"></a>File Page Sizes</h4>
<p><font size="2">To optimize file access performance, the page
sizes for data and key files should be a multiple of the file block
size used by your operating system. Many systems have a block size
of 512 bytes. In these systems block sizes of 512, 1024, 1536, etc.
would be acceptable.</font></p>
<p>The best page size for a given file is not always easily
determined, and will be based on application implementation
details. Key file pages should be large enough to hold a reasonable
number of keys, so that the number of levels in the resulting
B-tree are kept as small as possible (less than or equal to four).
Data file page sizes should be based on the number of records you
want to store on each page. For example, if all members of a set
are stored together, then they will likely be stored in contiguous
record slots. If they will usually be accessed together as well,
then you may decide that the page size should be large enough to
hold the average number of set members in order to minimize the
actual disk accesses necessary to read each member.</p>
<p>The initial <b><i>db.*</i></b> runtime page buffers are sized
based upon the largest page size specified in the DDL. For example,
if you have specified four files with a 1024-byte page size and one
file with a 4096-byte page size, <b><i>db.*</i></b> will allocate
4096 bytes for each page in the cache. You need to be aware of your
memory requirements in deciding on page sizes.</p>
<h2><a name="DesignExample" id="DesignExample"></a>4.5 Database
Design Example</h2>
<h3><a name="DesignIntroduction" id="DesignIntroduction"></a>4.5.1
Introduction</h3>
<p><font size="2">The example to be presented in this section is an
elaboration of the <b>tims</b> database introduced in Chapter 3. It
will be used in examples throughout the remainder of this document.
A solid understanding of this example design is
necessary.</font></p>
<p>The requirements for the <b>tims</b> application are given
first, followed by a description of the schema with explanations of
how the design will be used to satisfy the stated requirements.</p>
<h3><a name="Requirements" id="Requirements"></a>4.5.2
Requirements</h3>
<p><font size="2">The system is to be used to maintain a database
of technical information contained in books, technical journals or
magazines, and articles. In the following discussion, a single
book, journal issue, or article will be generally referred to as an
info item.</font></p>
<p>The following data is to be stored for each book, journal, or
article:</p>
<div style="margin-left: 4em">
<p>author's name</p>
<p>information id code</p>
<p>title</p>
<p>publisher</p>
<p>date published</p>
<p>abstract</p>
<p>topical key words</p>
</div>
<p>The id code will be a unique Dewey-Decimal library code assigned
by the user. The abstract will be a brief description (up to
several paragraphs) of the info item. Each info item may have
several key words associated with it that identify topics discussed
in it.</p>
<p>Functions are to be provided to allow info item entry and
deletion.</p>
<p>The info item data is to be retrieved as follows:</p>
<ul>
<li>By author name, where all info items for a given author are
reported</li>
<li>By id code, through which individual occurrences can be found
or all occurrences can be retrieved in id code order</li>
<li>By key word, where all info items for a given key word are
reported</li>
</ul>
<p>The ability to keep track of loaned books and magazines is also
to be provided, where the borrower's name, the date borrowed, and
the date returned are stored for each item loaned. A loan history
is to be maintained for each info item. In addition, the ability to
report all unreturned info items is to be provided.</p>
<h3><a name="DatabaseDesign" id="DatabaseDesign"></a>4.5.3 Database
Design</h3>
<p><font size="2">The schema diagram for the database design is
shown in Figure 4-5 below.</font></p>
<p align="center">&nbsp;</p>
<p align="center"><img alt="dbstar_4-5.gif - 5346 Bytes" border="0"
height="366" src="dbstar_4-5.gif" width="396"></p>
<p align="center">Fig. 4-5. tims Database Schema</p>
<p>The principal data for each info item is stored in a record
called <b>info</b>. This includes the id code, title, publisher,
and publication date. Also included is a coded-value field for
storing the type of info, where 0 = book, 1 = journal or magazine
and 2 = article. The id code will be a key in order to quickly find
specific <b>info</b> occurrences.</p>
<p>Because there may be many books or articles written by a single
author, storing the author name in the <b>info</b> record would
replicate multiple occurrences of the same author. This is often
referred to as redundant data. So, the author is stored in a
separate record with a set, <b>has_published</b>, connecting an
author to that author's <b>info</b> records.</p>
<p>Since the <b>info</b> records for a given author are to be
retrievable by author name, a set, ordered by author name, called
<b>author_list,</b> has been defined with the system record as the
owner. To find a specified author, this set is searched. This is
sufficient for a small personal library where there would be
relatively few authors (less than 100) and the system is only used
by a single user. In a large library with many authors, access
would be faster if we used the author name as a key field and did
not use a set. Here (mainly for instructional purposes), the
assumption is that the system is for a small, personal library.</p>
<p>A simple variable-length text structure is used for storing the
abstract. A record type called <b>text</b> is defined that stores a
text string of up to 80 characters, including a sentinel null byte.
A set called <b>abstract</b> with order <b>last</b> is defined with
<b>info</b> as owner and <b>text</b> as member, forming a
one-to-many set between an <b>info</b> record and each line of
abstract text.</p>
<p>The relationship between key words and item <b>info</b> records
is many-to-many. A key word is stored in a record type named
<b>key_word</b>. The key word is a string field that is keyed to
allow rapid retrieval of individual key word occurrences and to
allow alphabetized key word perusal. The many-to-many relationship
is implemented through the use of two sets, as described in section
4.4.1, "Logical Design Considerations." <b>Key_word</b> records and
<b>info</b> records are connected to an intersection record called
<b>intersect</b>. Set <b>key_to_info</b> is used to find the
<b>info</b> records corresponding to a particular key word. Set
<b>info_to_key</b> is used to find the key words associated with a
given <b>info</b> record. The <b>intersect</b> record has one field
to hold a copy of the <b>info</b> type from its <b>info</b> owner
through the <b>info_to_key</b> set. By eliminating an extra disk
read of the <b>info</b> record for non-books, this facilitates the
kind of key word searches where, for example, you're only
interested in finding the books covering a specific topic.
Redundant data is sometimes incorporated into a database design in
order to improve data access performance.</p>
<p>A record type named <b>borrower</b> will contain the name of the
borrower, the date loaned, and the date returned. The borrower's
name will be a key field, in order to be able to quickly find all
of the items borrowed by a particular person. Dates will be stored
as a long integer of the form YYMMDD (for example, 870709 is July
9, 1987). A date of zero indicates that the loaned item has not yet
been returned. When an item is loaned, a new borrower record is
created and is connected to two sets. A set called
<b>loaned_books</b> connects the <b>borrower</b> record to the
<b>info</b> record for the loaned item. These records will normally
remain members of this set even after the item is returned, to
maintain a loan history for each item in the library. The
<b>borrower</b> record is also connected to a set called
<b>loan_history</b>, which is owned by the system record. This set
is scanned when a list of all unreturned books is desired. Both
sets are in <b>last</b> order so the records will be connected in
chronological order (without having to specify ascending order by
date loaned).</p>
<p>One final set has been included. The set named <b>articles</b>
has <b>info</b> records participating as both owner and member of
the same set (which is legal in <b><i>db.*</i></b>). Here, the set
is intended to connect article <b>info</b> records to the
<b>info</b> record of the journal or magazine in which it is
published.</p>
<p>The <b><i>db.*</i></b> DDL that implements the <b>tims</b>
database design is presented on the next page. Two data files and
two key files have been defined. Data file <b>tims.d01</b> contains
the <b>system</b> record (of which there is only one occurrence and
is small because it has no fields), <b>key_word</b> records and
<b>intersect</b> records. Data file <b>tims.d02</b> contains the
occurrences of record types <b>author</b>, <b>borrower</b>,
<b>info</b>, and <b>text</b>. This organization is arbitrary in
this case since the database is not large.</p>
<p>Key field <b>id_code</b> is much smaller than keys <b>friend</b>
and <b>word</b> and is therefore stored in a separate key file, as
is shown in the example below.</p>
<pre>
<font color=
"#0000FF">/*--------------------------------------------------------------------
Technical Information Management System (TIMS) Database
--------------------------------------------------------------------*/
database tims
{
   data file "tims.d01" contains system, key_word, intersect;
   data file "tims.d02" contains author, borrower, info, text;
   key  file "tims.k01" contains id_code;
   key  file "tims.k02" contains friend, word;
   
   record author {
      char name[32];               /* author's name: "last, first" */
   }                               /* or editor's name */
   record info {
      unique key char id_code[16]; /* dewey dec. code */
      char info_title[80];         /* title of book, article, mag. */
      char publisher[32];          /* name of publisher */
      char pub_date[12];           /* date of publication */
      short info_type;             /* 0=book, 1=mag, 2=art */
   }
   record borrower {
      key char friend[32];         /* name of borrower */
      long date_borrowed;          /* dates are stored initially */
      long date_returned;          /* numeric YYMMDD */
   }
   record text {
      char line[80];               /* line of abstract text */
   }
   record key_word {
      unique key char word[32];    /* subject key words */
   }
   record intersect {
      short int_type;              /* copy of info_type */
   }
   set author_list {
      order ascending;
      owner system;
      member author by name;
   }
   set has_published {
      order ascending;
      owner author;
      member info by info_title;
   }
   set articles {
      order last;
      owner info;
      member info;
   }
   set loaned_books {
      order last;
      owner info;
      member borrower;
   }
   set abstract {
      order last;
      owner info;
      member text;
   }
   set key_to_info {
      order last;
      owner key_word;
      member intersect;
   }
   set info_to_key {
      order last;
      owner info;
      member intersect;
   }
   set loan_history {
      order last;
      owner system;
      member borrower;
   }
}
</font>
</pre>
<p><a href="UG_Ch5a.htm">Next Page</a></p>
</body>
</html>