Index support for next-generation database applications
Paul M. Aoki, Michael R Stonebraker · 1999
Conventional relational database management systems supporting the industry-standard query language, SQL, provide a fixed set of data types. Some applications (in, e.g., financial, multimedia and scientific domains) require additional data types. Extensible object-relational database management systems allow programmers to add these novel data types to the database system. However, in addition to the data types themselves, efficient implementation of these applications often requires additional database support in the form of specialized query processing operations. This dissertation examines the hypothesis that many of these specialized operations can be supported efficiently using a template storage structure that is based on extensions to the generalized search tree, or GiST, originally proposed by Hellerstein et al. The dissertation contains three main contributions. The first is a software framework that implements the proposed template storage structure. Among other things, this framework extends GiST in a way that allows programmers to specify customized methods of navigating the index. We then show how the framework supports a variety of different applications that have not previously been integrated into extensible systems. The second contribution concerns the exploitation of search tree structure to allow a kind of generalized density estimation. We describe algorithms which apply this basic notion to the core database problem of query selectivity estimation. The third contribution lies in the area of incremental query processing. We show how search trees might be used to support a probabilistic type of “best results first” or “top k” query result retrieval.