Database Design

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

Scheme Design

Two important principles guide scheme design

1. Two pieces of information that are independent should reside in two different relations.

2. Two pieces of information that are related should reside in the same relation.

Violations of principle 1 result in a database full of redundant information.

• 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 the database.

• 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

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?