Digital Symposium Collection 2000

High Level Indexing of User-Defined Types Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, and Yun Wang   View Paper (PDF)   Return to Extending SQL with User Defined Types Abstract To support emerging database applications, object-relational databases leverage the mature relational database technology and allow users to introduce application-specific types and methods. Tables in a database may now contain such objects as geographical shapes, images, and text documents. To realize the full potential of object-relational databases, efficient querying and searching of user-defined objects must be supported. This paper presents a high level framework for indexing of user-defined types with user-defined predicates. It is orthogonal to the low level access methods that are supported. It is unique in providing direct user control over the transformation from a user-defined type into an abstract domain of index values, the generation of search keys of a user-defined predicate with bound search arguments, and the execution of a user-defined predicate. The high level framework has been implemented in IBM DB2 Universal Database. Its generality, usability, and performance have been demonstrated in different application domains, where indices on user-defined objects can be fully integrated with SQL queries and exploited by the query compiler. References Note: References link to DBLP on the Web. [1] Paul M. Aoki : Generalizing ``Search'' in Generalized Search Trees (Extended Abstract). ICDE 1998 : 380-389 [2] Rudolf Bayer : The Universal B-Tree for Multidimensional Indexing: general Concepts. WWCA 1997 : 198-209 [3] Rudolf Bayer , Edward M. McCreight : Organization and Maintenance of Large Ordered Indices. Acta Informatica 1 : 173-189(1972) [4] Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel : The Pyramid-Tree: Breaking the Curse of Dimensionality. SIGMOD Conference 1998 : 142-153 [5] Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider : Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems. ICDE 1993 : 40-49 [6] Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger : Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994 : 197-208 [7] Surajit Chaudhuri , Kyuseok Shim : Optimization of Queries with User-defined Predicates. VLDB 1996 : 87-98 [8] Jyh-Herng Chow , Josephine M. Cheng , Daniel T. Chang , Jane Xu : Index Design for Structured Documents Based on Abstraction. DASFAA 1999 : 89-96 [9] Douglas Comer : The Ubiquitous B-Tree. Computing Surveys 11(2) : 121-137(1979) [10] ... [11] Christos Faloutsos , Ron Barber , Myron Flickner , Jim Hafner , Wayne Niblack , Dragutin Petkovic , William Equitz : Efficient and Effective Querying by Image Content. JIIS 3(3/4) : 231-262(1994) [12] Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos : Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994 : 419-429 [13] Volker Gaede , Oliver Günther : Multidimensional Access Methods. Computing Surveys 30(2) : 170-231(1998) [14] Roy Goldman , Jennifer Widom : DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997 : 436-445 [15] Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57 [16] Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer : Generalized Search Trees for Database Systems. VLDB 1995 : 562-573 [17] Joseph M. Hellerstein , Michael Stonebraker : Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993 : 267-276 [18] ... [19] H. V. Jagadish : Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990 : 332-342 [20] Clifford A. Lynch , Michael Stonebraker : Extended User-Defined Indexing with Application to Textual Databases. VLDB 1988 : 306-317 [21] Jack A. Orenstein , Frank Manola : PROBE Spatial Data Modeling and Query Processing in an Image Database Application. TSE 14(5) : 611-629(1988) [22] Nick Roussopoulos , Stephen Kelley , Frédéic Vincent : Nearest Neighbor Queries. SIGMOD Conference 1995 : 71-79 [23] Narayanan Shivakumar , Hector Garcia-Molina , Chandra Chekuri : Filtering with Approximate Predicates. VLDB 1998 : 263-274 [24] Michael Stonebraker : Inclusion of New Types in Relational Data Base Systems. ICDE 1986 : 262-269 [25] Michael Stonebraker , Paul Brown , Dorothy Moore: Object-Relational DBMSs, Second Edition. Morgan Kaufmann 1998, ISBN 1-55860-452-9 [26] ... [27] ... BIBTEX @inproceedings{DBLP:conf/vldb/ChenCFGJMTW99,   author    = {Weidong Chen and                 Jyh-Herng Chow and                 You-Chin Fuh and                 Jean Grandbois and                 Michelle Jou and                 Nelson Mendon\c{c}a Mattos and                 Brian T. Tran and                 Yun Wang},    editor    = {Malcolm P. Atkinson and                 Maria E. Orlowska and                 Patrick Valduriez and                 Stanley B. Zdonik and                 Michael L. Brodie},    title     = {High Level Indexing of User-Defined Types},    booktitle = {VLDB'99, Proceedings of 25th International Conference on Very                 Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,                 UK},    publisher = {Morgan Kaufmann},    year      = {1999},    isbn      = {1-55860-615-5},    pages     = {554-564},    crossref  = {DBLP:conf/vldb/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM