Applications of Range Query Theory to Relational Data Base Join and Selection Operations

AbstractThis article applies range query theory to develop join algorithms that run inO(IlogdI+U) time, whereIandUare the sizes of the input and output anddis usually a small constant. One advantage of these algorithms is that they do not require the storage of an index, and they also use a working memory space guaranteed to be proportional to the size of the input. If the memory space is expanded toO(NPolylogN), our formalism also leads to the development of very fast indices supportingO(PolylogN) selection operations