Describe analysis of access paths
To describe analysis of access paths, consider an example of the design of a company's employee skills database. A part of the object model from analysis phase is shown in Figure. The operation Company:: find-skill returns a group of persons in company with a given skill. Like, we may ask for data of all employees who speak Japanese.
Figure: Chain of associations between objects
For this example, suppose that company has 1000 employees, each of one has 10 skills on average. A simple nested loop will traverse Employs 1000 times and has-skill 10,000 times. If only 5 employees in fact speak Japanese, then test-to-hit ratio is 2000.
Now, let us check whether this figure can be improved or not. Actually, we could make many possible improvements in this Figure. First, Has-skill need not to be implemented as an unordered list a hashed set. The hashing can be performed during fixed interval of time so that cost of testing whether a person speaks Japanese is constant or not, provided a unique skill object represents speaks Japanese. This rearrangement decreases number of tests from 10,000 to 1,000, or one per employee.
For those cases where number of hits from a query is less (since only a fraction of objects satisfy test) we can build the index to improve access to objects which must be frequently retrieved. For instance, we can add a qualified association Speaks language from Company to Employee, where qualifier is the language spoken. This permits us to straight away access all employees who speak particular language with no wasted accesses. But there is a cost to index: "It requires extra memory and it must be updated every time base associations are updated". The object designer should select that when it is useful to build the indexes. Here, we have to consider case where most queries return all of objects in search path, then an index really does not save much since test-to-hit ratio in this case is very close to 1.
Figure: Index for personal skills database