Java Reference
In-Depth Information
to account balances and updates such as deposits and withdrawals. Spe-
cial service representatives are typically provided (during restricted hours)
to handle opening and closing accounts. Teller and ATM transactions are
expected to take little time. Opening or closing an account can take much
longer (perhaps up to an hour from the customer's perspective).
From a database perspective, we see that ATM transactions do not mod-
ify the database significantly. For simplicity, assume that if money is added
or removed, this transaction simply changes the value stored in an account
record. Adding a new account to the database is allowed to take several
minutes. Deleting an account need have no time constraint, because from
the customer's point of view all that matters is that all the money be re-
turned (equivalent to a withdrawal). From the bank's point of view, the
account record might be removed from the database system after business
hours, or at the end of the monthly account cycle.
When considering the choice of data structure to use in the database
system that manages customer accounts, we see that a data structure that
has little concern for the cost of deletion, but is highly efficient for search
and moderately efficient for insertion, should meet the resource constraints
imposed by this problem. Records are accessible by unique account number
(sometimes called an exact-match query). One data structure that meets
these requirements is the hash table described in Chapter 9.4. Hash tables
allow for extremely fast exact-match search. A record can be modified
quickly when the modification does not affect its space requirements. Hash
tables also support efficient insertion of new records. While deletions can
also be supported efficiently, too many deletions lead to some degradation
in performance for the remaining operations. However, the hash table can
be reorganized periodically to restore the system to peak efficiency. Such
reorganization can occur offline so as not to affect ATM transactions.
Example1.2
A company is developing a database system containing in-
formation about cities and towns in the United States. There are many
thousands of cities and towns, and the database program should allow users
to find information about a particular place by name (another example of
an exact-match query). Users should also be able to find all places that
match a particular value or range of values for attributes such as location or
population size. This is known as a range query.
A reasonable database system must answer queries quickly enough to
satisfy the patience of a typical user. For an exact-match query, a few sec-
onds is satisfactory. If the database is meant to support range queries that
can return many cities that match the query specification, the entire opera-
