Oracle Corporation
Optimal Index Selection in Polynomial Time

Abstract:

A method may use a minimal set of indices for an input query including identifying the input query including primitive searches that are accelerated using indices, and computing a minimal set of indices for the input query using a polynomial-time algorithm by constructing a bi-partite graph comprising a first and a second vertex set. The first and the second vertex set may be a set of searches in both partitions of the bi-partite graph. Each edge of the edge set may connect a vertex in the first vertex set and a vertex in the second vertex set. The method may further include identifying an edge set as a strict subset relation between at least two searches of the set of searches showing up in the first and second vertex set of the bi-partite graph, and performing relational data analysis using the minimal set of indices for input queries.