The authors report on an investigation of average processing times for various database structures. The purpose of the tests was to identify structures that are robust, in the sense that a robust structure performs competitively, with the optimum structure for a particular query. Using robust structures can be beneficial in practice because the pattern of queries is not known precisely, and it may vary with time, so the optimum structure cannot be determined.

The strategy of the investigation was to test each possible structure with each query type, to identify candidates for further testing; in the example given, the top five performers used significantly shorter processing time than the rest. Then these top performers, the candidates, were tested comprehensively to determine which were robust. The tests consist of random arrivals of queries with different complexity. The various database structures tested were created from a basic structure, containing seven tables, by joining tables. In a business situation, the search for top performers would need to be done only once.

The approach presented can be called “pre-theory,” creating the knowledge upon which a theory can be developed. The approach appears promising, although it will only be useful if robust structures exist for many combinations of database structures and query patterns; more experimentation is needed.