A database designer must define
- the database scheme
- the keys for each relation
- primary index structures for each relation
- (optional) secondary index structures for each relation
These decisions depend on
- the information to be supported
- the relationships between pieces of information
- the expected size of the relations
- the types of queries expected
Two important principles guide scheme design
- Two pieces of information that
are independent should reside in two different relations.
- Two pieces of information that are related should reside
in the same relation.
Violations of principle 1 result in a database full of
- Course prerequisite information is independent of the
time and day the course is offered.
- A server's status is independent of the users it serves
- Company information is independent of the mutual fund
that owns shares in the company.
Violations of principle 2 result in a loss of information in
- A Course-Day-Hour relation cannot be split into Course-Day
and Course-Hour relations without losing track of the meeting
time of a course on a particular day.
Key selection is important, as it usually dictates the choice
of primary index structure
- You can't identify keys simply by looking at the values
of a relation; only the database designer knows for sure
- The best choice of keys depends on knowledge of the data
in the relations, and the expected pattern of queries
Primary Index Structures
The choice of domain for the primary index structure determines
- the location of the tuples
- the type of queries that will be most efficient
A typical choice is to use a hash table as the primary index structure
- use a key as the domain of the hash function
- use the remaining attributes as the range (bucket entries)
of the hash function
If the common queries don't use a key (eg. User Name in the Users relation),
you can still use a hash table based on this domain, but the distribution
of entries in hash buckets may be less even than if you used a key (such
as user login).
Secondary Index Structures
A secondary index
- speeds up queries based on the index
- slows down every change to the relation
How do we evaluate this tradeoff?
Given a relation with M entries, how many queries on the index
must we perform to justify creating a secondary index?
- What other information might you want to know before deciding?