Data processing: database and file management or data structures – Database design – Data structure types
Patent
1995-06-07
1998-07-07
Amsbury, Wayne
Data processing: database and file management or data structures
Database design
Data structure types
707 3, 39518202, 39520003, 395709, 395705, G06F 1730
Patent
active
057783543
ABSTRACT:
A database management system (DBMS) provided with a multi-dimensional improved indexed accessing capability using keyed index searching. Individual search keys are constructed from general expression statements created in the DBMS compiler from search queries supplied to the DBMS. Each key column represents another dimension, and both ranges and IN lists can be specified in the search query and used as the predicate values in multiple columns. Missing predicate values in the search query are interpreted as a specification of the minimum and maximum values for the associated search key column. During compile time, the DBMS compiler produces general expressions to be used by the DBMS executor during run time to create the search keys. The DBMS compiler evaluates search queries by associating predicates with clusters and disjunct numbers assigned to each individual disjunct in the search query expression. The DBMS executor uses the general expression from the compiler and eliminates any conflicts among same column predicates, removes redundancies in predicate values and disjuncts and reduces the number of records to be accessed to the minimum required to complete the search query. The individual search keys are generated in the same order as the index to which the search pertains (i.e., increasing or decreasing order).
REFERENCES:
patent: 4497039 (1985-01-01), Kitakami et al.
patent: 4506326 (1985-03-01), Shaw et al.
patent: 4967341 (1990-10-01), Yamamoto et al.
patent: 5043872 (1991-08-01), Cheng et al.
patent: 5519859 (1996-05-01), Grace
patent: 5551031 (1996-08-01), Cheng et al.
patent: 5557791 (1996-09-01), Cheng et al.
patent: 5559948 (1996-09-01), Bloomfield et al.
patent: 5560006 (1996-09-01), Layden et al.
patent: 5560007 (1996-09-01), Thai
Sartori et al. "Partial Indexing for Nonuniform Data Distributions in Relational DBMS's", IEEE Transaction vol. 6, No. 3, pp. 420-429, Jun. 1994.
IBM Corp., technical Disclosure Bulletin, "Query optimization for relational accessing language", vol. 28, No. 8, pp. 3471-3471, Jan. 1986.
Pang et al., "An effiencient semantic query optimization algorithm," Proceeding of the Interl conf on Data Engineering, Kobe, JP, No. 7, IEEE, pp. 326-335, Apr. 1991.
Bayer, R. and Schkolnick, M. "Concurrency of Operations of B-Trees" Acta.Inf. 9 1 (1977).
Bayer, R. and Unterauer, K. "Prefix B-Trees" ACM-TODS, vol. 2, No. 1, Mar. 1977.
Beckmann, N. and Kreigel, H.P. and Schneider, R. and Seeger, "The R*-tree: an Efficient and Robust Access Method for Points and Rectangles". ACM-SIGMOD 1990.
Bentley J. L. "Multidimensional Binary Search Trees Used for Associative Searching" Comm. ACM, vol. 18, No. 9, 1975.
Chang J. M. and Fu K. S. "A Dynamic Clustering Technique for Physical Database Design" ACM-SIGMOD 1980.
Comer, D. "The ubiquitous B-tree" ACM Computing Surveys vol. 11, No. 2, 1979.
Guttmann, A. "R-trees: a dynamic index structure for spatial searching" Proceedings ACM-SIGMOD Conf., 1984.
Held, G and Stonebraker, M "B-Trees Re-examined" Electronics Research Laboratory, University of California, 1975.
Knuth, D.E. "The Art of Computer Programming" vol. 3, Sorting and Searching. Addison-Wesley, Reading, Mass., 1973.
Lomet, D.B. and Salzberg, B. "The hB-tree: a Robust Multi-Attribute Indexing Method" ACM Trans. on Database Systems, vol. 15, No. 4 1989.
Nievergelt, J and Hinterberger, H "The Grid File: An Adaptable, Symmetric Multikey File Structure" Trends in Information Processing Systems, Proc 3rd ECI Conference 1981.
Robinson, J.T. "The K-D-B-Tree: A Search Structure for Large Multi-dimensional Dynamic Indexes" Proc. ACM SIGMOD Conf. 1981.
Rothnie, J. B. and Lozano, T. "Attribute Based File Organization in a Paged Memory Environment" comm ACM, vol. 17, No. 2, Nov. 1974.
Seeger, B. and Kriegel, H. P. "The Buddy-tree: an Efficient and Robust Access Method for Spatial Data Base Systems" Proc. 16th Int. Conf. on Very Large Data Bases, 1990.
Sellis, T. and Rossopoulous, N. and Faloutsos, C. "The R+ Tree: a Dynamic Index for Multidimensional Objects" Proc. 13th Int. Conf. on Very Large Data Bases, 1987.
Snodgrass, R. "Temporal Databases" Computer, pp. 35-42, Computer Sep. 1986.
IBM Corp., IBM Technical Disclosure Bulletin, "Optimization of Like Predicate in an SQL Query", vol. 35, No. 4A, Sep. 1992, pp. 314-317.
IBM Corp., IBM Technical Disclosure Bulletin, "Query Optimization for Relational Accessing Language", vol. 28, No. 8, Jan. 1986, pp. 3471-3472.
Proceedings of the International Conference on Data Engineering, KOBE, JP, Apr. 8-12, 1991, No. 7, IEEE, Hwee Hwa Pang et al., "An Efficient Semantic Query Optimization Algorithm," pp. 326-335.
Birdsall David W.
Jain Rohit N.
Leslie Harry A.
Yaghmai Hedieh
Amsbury Wayne
Corrielus Jean M.
Tandem Computers Incorporated
LandOfFree
Database management system with improved indexed accessing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Database management system with improved indexed accessing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database management system with improved indexed accessing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1217816