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:
How can we model and build a general-purpose database in Java? Here are some crucial concepts:
The picture suggests that the database will operate the same, regardless of whether books, bank accounts, and so on, are saved. As long as the records---whatever they are---hold keys, the database can do its insertions, lookups, and deletions, by manipulating the records' keys and not the records themselves. This is strongly reminiscent of arrays, which can hold a variety of objects without manipulating the objects themselves.![]()
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,
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:
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(...);Then, the application might insert a record---call it r0---into db with a method invocation like this:
db.insert(r0);As stated earlier, each record possesses its own key. Say that record r0 holds object k0 as its key. To retrieve record r0 from the database, we use a command like this:
Record r = db.find(k0);This places the address of record r0 into variable r for later use. We can delete the record from the database by stating:
db.delete(k0);Notice that variable r still holds the address of the record, but the record no longer lives in the database.
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.
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===================================There is a new notation in the Figure's class diagram: The annotation, 1 --> *, on the arrow emphasizes that one Database collaborates with (or collects) multiple Records, suggesting that an array will be useful in the coding of class Database. As noted earlier, whatever a Record or Key might be, the methods getKey and equals are required. (The format of the equals method will be explained momentarily.)ENDFIGURE=============================================================
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=======================
Database | a container for data items, called Records |
Attribute | |
private Record[] base | Holds the records inserted into the database. |
Methods | |
insert(Record r): boolean | Attempts to insert the record, r, into the database. Returns true if the record is successfully added, false otherwise. |
find(Key k): Record | Attempts to locate the record whose key has value k. If successful, the address of the record is returned, otherwise, null is returned. |
delete(Key k): boolean | Deletes the record whose key has value k. If successful, true is returned; if no record has key k, false is returned. |
Record | a data item that can be stored in a database |
Methods | |
getKey(): Key | Returns the key that uniquely identifies the record. |
Key | an identification, or ``key,'' value |
Methods | |
equals(Key m): boolean | Compares itself to another key, m, for equality. If this key and m are same key value, then true is returned; if m is a different key value, then false is returned. |
ENDTABLE===========================================================Because we have provided partial (incomplete) specifications for Record and Key, many different classes might implement the two specifications. For example, we might write class Book to implement a Record so that we can build a database of books, or we might write class BankAccount to implement a database of bank accounts. Different classes of keys might also be written, if only because books use different keys than do bank accounts.
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.
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;The constructor method for the class will initialize the field to an array:
base = new Record[HOW_MANY_RECORDS];where all the array's elements have value null, because the array is empty. Records will be inserted into the database one by one. To do an insert(Record r), follow this algorithm:
/** 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)Then, Step 1 of the algorithm is merely,
if ( findLocation(r.getKey()) == -1 )because r.getKey() extracts the key held within record r, and a result of -1 from findLocation means that no record with the same key is already present.
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;The last assignment, base = temp, copies the address of the larger array into array variable base, meaning that base once again holds the address of an array of records.
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,
int index = findLocation(k); if ( index != -1 ) { base[index] = null; }See Figure 4 for the completed method.
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 }Note the conditional statement in the loop's body:
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 nextThe test expression first asks if there is a record stored in element, base[i], and if the answer is true, then the element's key (namely, base[i].getKey()) is compared for equality to the desired key, k.
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:
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);When a customer opens a new account, we might ask the customer to select an integer key for the account and make an initial deposit:
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);The fourth statement both constructs the new account and inserts it into the database.
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);As noted by the statement, Key lookup_key = new Key("QA", 76.8), we can manufacture keys as needed to perform lookups and deletions.
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.