8.6 Case Study: Databases

A large collection of information, such as a company's sales records or its customer accounts or its payroll information, is called a database. An important programming challenge is determining the proper structure for a database.

In simplest terms, a database is a ``container'' into which objects are inserted, located, and removed; the objects that are stored in a database are called records. An important feature about a record is that it is uniquely identified by its key, which is held within the record itself. Here are some examples of records:

• A bank's database holds records of accounts. Each account record is uniquely identified by a multi-letter-and-digit account number. A typical record would contain information such as
  1. its key, the multi-digit integer, which identifies the account
  2. the name (or some other identification) of the account's owner
  3. the amount of money held in the account
• A library's database holds records of books. Each record has for its key the book's catalog number. For example, the U.S. Library of Congress catalog number is a pair: an alphabetic string and a fractional number, such as QA 76.8. The records held in a library's database would have these attributes:
  1. the key, which is the book's catalog number
  2. the book's title, author, publisher, and publication date
  3. whether or not the book is borrowed, and if so, by which patron
• The U.S. Internal Revenue Service database hold records of taxpayers. Each record is identified by a nine-digit social-security number. The record holds the number as its key and also holds the taxpayer's name, address, and copies of the person's tax reports for the past five years.

How can we model and build a general-purpose database in Java? Here are some crucial concepts:

1. keys are objects
2. records are objects, and a record holds as one of its attributes (the address of) its key object
3. a database is a kind of ``array'' of record objects; it must have methods for inserting a record, finding a record, and deleting a record
4. when the database's user wishes to insert a record into the database, she calls the databases' insert method, supplying the record as the argument; when she wishes to find a record, she calls the find method, supplying a key object as an argument; when she wishes to delete a record, the calls the delete method, supplying a key object as an argument

So, how does a database manipulate a key? Regardless of whether keys are numbers or strings or pairs of items, keys are manipulated by comparing them for equality. Consider a lookup operation: The database receives a key object, and the database searches its collection of records, asking each record to tell its key, so that each key can be compared for equality to the desired key. When an equality is found true, the corresponding record is returned. This algorithm operates the same whether integers, strings, or whatever else is used for keys.

In summary,

1. The Database holds a collection of Record objects, where each Record holds a Key object. The remaining structure of the Records is unimportant and unknown to the database.
2. The Database will possess insert, find, and delete methods.
3. Records, regardless of their internal structure, will possess a getKey method that returns the Record's Key object when asked.
4. Key objects, regardless of their internal structure, will have an equals method that compares two Keys for equality and returns true or false as the answer.

We are now ready to design and build a database subassembly in Java. We will build a subassembly---not an entire program---such that the subassembly can be inserted as the model into a complete application. We follow the usual stages for design and construction:

1. State the subassembly's desired behaviors.
2. Select an architecture for the subassembly.
3. For each of the architecture's components, specify classes with appropriate attributes and methods.
4. Write and test the individual classes.
5. Integrate the classes into a complete subassembly.

8.6.1 Behaviors

Regardless of whether a database holds bank accounts, tax records, or payroll information, its behaviors are the same: a database must be able to insert, locate, and delete records based on the records' keys. We plan to write a class Database so that an application can construct a database object by stating,

Database db = new Database(...);

db.insert(r0);

Record r = db.find(k0);

db.delete(k0);

The above behaviors imply nothing about the techniques that the database uses to store and retrieve records; these activities are internal to class Database and are best left unknown to the database's users.

8.6.2 Architecture

The previous examples suggest there are at least three components to the database's design: the Database itself, the Records that are inserted into it, and the Keys that are kept within records and are used to do insertions, lookups, and deletions. The class diagram in Figure 2 lists these components and their dependencies.

FIGURE 2: architecture for a database===================================



ENDFIGURE=============================================================

8.6.3 Specifications

To keep its design as general as possible, we will not commit class Database to saving any particular form of Record---the only requirement that a database will make of a record is that a record can be asked for its key. Similarly, the only requirement a database will make of a key is that the key can be compared to another key for an equality check.

Since class Database must hold multiple records, its primary attribute will be an array of records, and the database will have at least the three methods listed in Figure 2.

The specification for Record is kept as minimal as possible: whatever a record object might be, it has a function, getKey, that returns the key that uniquely identifies the record. Similarly, it is unimportant whether a key is a number or a string or whatever else; therefore, we require only that a key possesses a method, equals, that checks the equality of itself to another key.

Table 3 presents the specifications that summarize our assumptions about databases, records, and keys.

TABLE 3: specifications for database building=======================

ENDTABLE===========================================================

Key's specification deserves a close look: the specification is written as if keys are objects (and not mere ints). For this reason, given two Key objects, K1 and K2, we must write K1.equals(K2) to ask if the two keys have the same value. (This is similar to writing S1.equals(s2) when comparing two strings, S1 and S2, for equality.) We exploit this generality in the next section.

8.6.4 Implementation

The specifications for Record and Key make it possible to write a complete coding for class Database without knowing any details about the codings for the records and keys. Let's consider the implementation of class Database.

The database's primary attribute is an array that will hold the inserted records. class Database must contain this field declaration:

private Record[] base;

base = new Record[HOW_MANY_RECORDS];

1. Search array base to see if r is present. (More precisely, search base to see if a record with the same key as r's key is already present.)
2. If r is not in base, then search for the first element in base that is empty (that is, holds value null).
3. Insert r into the empty element.

/** findLocation  is a helper method that searches  base  for a record
  *  whose key is  k.   If found, the array index of the record within
  *  base  is returned, else  -1  is returned.  */
private int findLocation(Key k)

if ( findLocation(r.getKey()) == -1 )

Step 2 of the algorithm is clearly a searching loop, and we use the techniques from Chapter 7 to write this loop, which searches for the first empty element in base where a new record can be inserted:

boolean found_empty_place = false;
int i = 0;
while ( !found_empty_place  &&  i != base.length )
      // so far, all of  base[0]..base[i-1]  are occupied
      { if ( base[i] == null )   // is this element empty?
             { found_empty_place = true; }
        else { i = i + 1; }
      }

When this loop completes, i holds the index of the first empty element in base, meaning that Step 3 is just base[i] = r, unless array base is completely filled with records and there is no available space. What should we do in the latter situation?

Because Java arrays are objects, it is possible to construct a new array object that is larger than the current array and copy all the elements from the current array to the new array. Here is a standard technique for doing so:

// This constructs a new array twice as large as base:
Record[] temp = new Record[base.length * 2];
// Copy  elements in array named by  base   into  temp:
for ( int j = 0;  j != base.length;  j = j + 1 )
    { temp[j] = base[j]; }
// Change  base  to hold address of  temp:
base = temp;

BeginFootnote: If you have studied the Java libraries, perhaps you discovered class Vector, which behaves like an array but automatically expands to a greater length when full. The technique that a Java Vector uses to expand is exactly the one presented above. EndFootnote.

Figure 4 displays the completed version of insert.

Next, we consider how to delete an element from the database: The algorithm for method, delete(Key k), would go,

1. Search array base to see if if a record with the key, k, is present.
2. If such a record is located, say, at element index, then delete it by assigning, base[index] = null.

int index = findLocation(k);
if ( index != -1 )
   { base[index] = null; }

We can write the lookup method so that it merely asks findLocation to find the desired record in the array. Again, see Figure 4.

To finish, we must write the findLocation method, which finds the record in array base whose key is k. The algorithm is a standard searching loop, but there is a small complication, because array base might have null values appearing in arbitrary places, due to deletions of previously inserted records:

private int locationOf(Key k)
{ int result = -1;  // recall that  -1  means  ``not found''
  boolean found = false;
  int i = 0;
  while ( !found  &&  i != base.length )
        { if ( base[i] != null   // is this element occupied?
               &&  base[i].getKey().equals(k) )  // is it the desired record?
               { found = true;
                 result = i;
               }
          else { i = i + 1; }
        }
  return result;  // return array index of the record found
}

if ( base[i] != null    // is this array element occupied?
               &&  base[i].getKey().equals(k) )  // is it the desired record?
               { ... }  // we found the record at array element,  i
else { i = i + 1; }     // the record is not yet found;  try  i + 1  next

The completed Database class appears in Figure 4. In addition to attribute base, we define the variable, NOT_FOUND, as a memorable name for the -1 answer used to denote when a search for a record failed.

FIGURE 4: class Database============================================

/** Database  implements a database of records */
public class Database
{ private Record[] base;   // the collection of records
  private int NOT_FOUND = -1;  // int used to denote when a record not found

  /** Constructor  Database  initializes the database
    * @param initial_size - the size of the database */
  public Database(int initial_size)
  { if ( initial_size > 0 )
         { base = new Record[initial_size]; }
    else { base = new Record[1]; }
  }

  /** findLocation  is a helper method that searches  base  for a record
    *  whose key is  k.   If found, the index of the record is returned,
    *  else  NOT_FOUND  is returned.  */
  private int findLocation(Key k)
  { int result = NOT_FOUND;
    boolean found = false;
    int i = 0;
    while ( !found  &&  i != base.length )
          { if ( base[i] != null  &&  base[i].getKey().equals(k) )
                 { found = true;
                   result = i;
                 }
            else { i = i + 1; }
          }
    return result;
  }

  /** find  locates a record in the database based on a key
    * @param key - the key of the desired record
    * @return (the address of) the desired record;
    *  return  null if record not found.  */
  public Record find(Key k)
  { Record answer = null;
    int index = findLocation(k);
    if ( index != NOT_FOUND )
       { answer = base[index]; }
    return answer;
  }
 ...

ENDFIGURE======================================================

FIGURECONT 4: class Database (concl.)=============================

  /** insert inserts a new record into the database.
    * @param r - the record
    * @return true, if record added; return false if record not added because
    *   another record with the same key already exists in the database */
  public boolean insert(Record r)
  { boolean success = false;
    if ( findLocation(r.getKey()) == NOT_FOUND )  // r  not already in  base?
       { // find an empty element in  base  for insertion of  r:
         boolean found_empty_place = false;
         int i = 0;
         while ( !found_empty_place  &&  i != base.length )
               // so far, all of  base[0]..base[i-1]  are occupied
               { if ( base[i] == null )   // is this element empty?
                      { found_empty_place = true; }
                 else { i = i + 1; }
               }
         if ( found_empty_place )
              { base[i] = r; }
         else { // array is full!  So, create a new one to hold more records:
                Record[] temp = new Record[base.length * 2];
                for ( int j = 0;  j != base.length;  j = j + 1 )
                    { temp[j] = base[j]; } // copy  base  into  temp
                temp[base.length] = r;   // insert  r  in first free element
                base = temp;   // change  base  to hold address of  temp
              }
         success = true;
       }
    return success;
  }

  /** delete removes a record in the database based on a key
    * @param key - the record's key (identification)
    * @return true, if record is found and deleted; return false otherwise  */
  public boolean delete(Key k)
  { boolean result = false;
    int index = findLocation(k);
    if ( index != NOT_FOUND )
       { base[index] = null;
         result = true;
       }
    return result;
  }
}

ENDFIGURE===============================================================

The coding presents several lessons:

• Although class Database appears to store records based on their keys, a more primitive structure, an array, is used inside the class to hold the records. The helper method, findLocation, does the hard work of using records' keys as if there were ``indices.''
• Aside from the getKey and equals methods, nothing is known about the records and keys saved in the database. This makes class Database usable in a variety of applications, we see momentarily.
• Because the array of records can be filled, we use a standard technique within the insert method to build a new, larger array when needed.

8.6.5 Forms of Records and Keys

FIGURE 5: BankAccount Record and AccountKey==============================

/** Record models a bank account with an identification key */
public class Record
{ private int balance;  // the account's balance
  private Key id;       // the identification key

  /** Constructor Record initializes the account
    * @param initial_amount - the starting account balance, a nonnegative.
    * @param id - the account's identification key  */
  public Record(int initial_amount, Key id)
  { balance = initial_amount;
    key = id;
  }

  /** deposit adds money to the account.
    * @param amount - the amount of money to be added, a nonnegative int */
  public void deposit(int amount)
  { balance = balance + amount; }

  /** getBalance reports the current account balance
    * @return the balance */
  public int getBalance() { return balance; }

  /** getKey returns the account's key
    * @return the key */
  public int getKey() { return key; }
}


/** Key models an integer key */
public class Key
{ private int k;  // the integer key

  /** Constructor  Key  constructs the Key 
    * @param i - the integer that uniquely defines the key */
  public Key(int i) {  k = i; }

  /** equals  compares this Key to another for equality
    * @param c - the other key
    * @return true, if this key equals k's; return false, otherwise */
  public boolean equals(Key c)
  { return  ( k == c.getInt() ); }

  /** getInt returns the integer value held within this key */
  public int getInt() { return k; }
}

ENDFIGURE==============================================================

The Record in Figure 5 has additional methods that let us do deposits and check balances of a bank account, but the all-important getKey method is present, meaning that the record can be used with class Database of Figure 4.

In order to conform to the requirements demanded by class Database, the integer key must be embedded within a class Key. This means the integer is saved as a private field within class Key and that the equals method must be written so that it asks another key for its integer attribute, by means of an extra method, getInt.

Here is how we might use the classes in Figure 5 in combination with Figure 4. Perhaps we are modelling a bank, and we require this database:

Database bank = new Database(1000);

int i = ...some integer selected by the customer...;
int start_balance = ...some initial deposit by the customer...;
Key k1 = new Key(i);
boolean success = bank.insert( new Record(start_balance, k1) );
System.out.println("account inserted = " + success);

Later, if the account must be fetched so that its balance can be checked, we can find it and print its balance like this:

Record r = bank.find(k1);  // recall that  k1  is the account's key
if ( r != null )  // did we successfully fetch the account?
   { System.out.println(r.getBalance()); }

To show that the database can be used in a completely different application, we find in Figure 6 a new coding of record and key, this time for library books. Now, class Record holds attributes for a book's title, author, publication date, and catalog number; the catalog number serves as the book's key.

FIGURE 6: Book Record and CatalogNumber Key=============================

/** Record models a Library Book */
public class Record
{ // the names of the fields describe their contents:
  private Key catalog_number;
  private String title;
  private String author;
  private int publication_date;

  /** Constructor Record constructs the book.
    * @param num - the book's catalog number
    * @param a - the book's author
    * @param t - the book's title   */
  public Record(Key num, String a, String t, int date)
  { catalog_number = num;
    title = t;
    author = a;
    publication_date = date;
  }

  /** getkey  returns the key that identifies the record
    * @return the key  */
  public Key getKey() { return catalog_number; }

  /** getTitle returns the book's title 
    * @return the title */
  public String getTitle() { return title; }

  /** getAuthor returns the book's author 
    * @return the author */
  public String getAuthor() { return author; }

  /** getDate returns the book's publication date
    * @return the date */
  public int getDate() { return publication_date; }
}

ENDFIGURE======================================================

FIGURECONT 6: CatalogNumber Key (concl.)=============================

/** Key models a Library-of-Congress-style id number,
  *  consisting of a letter code concatenated to a decimal number */
public class Key
{ private String letter_code;  // the letter code, e.g.,  "QA"
  private double number_code;  // the number code, e.g.,  76.884

  /** Constructor Key constructs a catalog number
    * @param letters - the letter code, e.g.,  "QA"
    * @param num - the decimal number code, e.g.,  76.884 */
  public Key(String letters, double num)
  { letter_code = letters;
    number_code = num;
  }

  /** equals returns whether the catalog number held within this object
    *  is identical to the catalog number held within  c
    * @param c - the other catalog number
    * @return true, if this catalog number equals  c; return false, otherwise */
  public boolean equals(Key c)
  { String s = c.getLetterCode();
    double d = c.getNumberCode();
    return ( s.equals(letter_code)  &&  d == number_code );
  }

  /** getLetterCode returns the letter code part of this catalog number
    * @return the letter code, e.g.,  "QA"  */
  public String getLetterCode() { return letter_code; }
  
  /** getNumberCode returns the number code part of this catalog number
    * @return the number code, e.g.,  "76.884"  */
  public double getNumberCode() { return number_code; }
}

ENDFIGURE=================================================================

The structure of the catalog number is more complex: Its class Key holds a string and a double, because we are using the U.S. Library of Congress coding for catalog numbers, which requires a string and a fractional number. The class's equals method compares the strings and fractional numbers of two keys.

Here is a short code fragment that constructs a database for a library and inserts a book into it:

Database library = new Database(50000);

Record book = new Book( new Key("QA", 76.8), "Charles Dickens",
                        "Great Expectations", 1860 );
library.insert(book);

// We might locate the book this way:
Key lookup_key = new Key("QA", 76.8);
book = library.find(lookup_key);

// We can delete the book, if necessary:
boolean deleted = library.delete(lookup_key);

It is a bit unfortunate that the bank account record in Figure 5 was named class Record and that the book record in Figure 6 was also named class Record; more descriptive names, like class BankAccount and class Book would be far more appropriate and would let us include both classes in the same application if necessary. (Perhaps a database must store both bank accounts and books together, or perhaps one single application must construct one database for books and another for bank accounts.)

Of course, we were forced to use the name, class Record, for both records because of the coding for class Database demanded it. The Java language lets us repair this naming problem with a new construction, called a Java interface. We will return to the database example in the next chapter and show how to use a Java interface with class Database to resolve this difficulty.

Exercise