601. Query execution and index selection for relational data bases
- Author
-
Gilles Farley and Stewart A. Schuster
- Subjects
Set (abstract data type) ,Theoretical computer science ,Selection (relational algebra) ,Basis (linear algebra) ,Relation (database) ,Computer science ,Simple (abstract algebra) ,Relational database ,Function (mathematics) ,Data mining ,computer.software_genre ,computer ,Index selection - Abstract
An algorithm to evaluate primitive Boolean selections over single relations is presented. It will be argued that the algorithm is efficient with respect to the number of relational accesses and with respect to the merging of inverted lists. The algorithm's unique quality is its efficiency in evaluating selections over partially inverted relations. A simple cost function is used to drive the algorithm along the most efficient access paths. The cost function can also be used to predict its response time which then forms the basis of a procedure to suboptimize the selection of the domains to be inverted. The domains to be inverted are selected by analyzing, with respect to their costs, a sample of queries. Such a method does away with usual methods of updating usage counters for every domain and relation in the system. In this approach, the selection of a good set of inverted lists is based on the algorithm which uses those lists.
- Published
- 1975