Method and mechanism for storing and accessing data

Details Method and mechanism for storing and accessing data Method and mechanism for storing and accessing data

2006-09-05

2006-09-05

Robinson, Greta (Department: 2167)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

07103608

ABSTRACT:
A method and mechanism is disclosed for implementing storage and retrieval of data in a computing system. Data compression is performed on stored data by reducing or eliminating duplicate values in a database block. Duplicated values are eliminated within the set of data that is to be stored within a particular data storage unit. Rather than writing the duplicated data values to the data storage unit, the on-disk data is configured to reference a symbol table a single copy of each duplicated data value. Column reordering may be performed in an embodiment to further improve compression efficiency. The column reordering may be performed to allow efficient removal of trailing NULL values from on-disk storage.

REFERENCES:
patent: 4862167 (1989-08-01), Copeland, III
patent: 5237460 (1993-08-01), Miller et al.
patent: 5357431 (1994-10-01), Nakada et al.
patent: 5414634 (1995-05-01), Alexander et al.
patent: 5426426 (1995-06-01), Hymel
patent: 5627995 (1997-05-01), Miller et al.
patent: 5787415 (1998-07-01), Jacobson et al.
patent: 5918225 (1999-06-01), White et al.
patent: 5936560 (1999-08-01), Higuchi
patent: 6006232 (1999-12-01), Lyons
patent: 6112209 (2000-08-01), Gusack
patent: 6199070 (2001-03-01), Polo-Wood et al.
patent: 6205453 (2001-03-01), Tucker et al.
patent: 6208273 (2001-03-01), Dye et al.
patent: 6360300 (2002-03-01), Corcoran et al.
patent: 6374266 (2002-04-01), Shnelvar
patent: 6427145 (2002-07-01), Hara et al.
patent: 6721751 (2004-04-01), Furusho
patent: 6760907 (2004-07-01), Shaylor
patent: 6823329 (2004-11-01), Kirk et al.
patent: 2002/0073298 (2002-06-01), Geiger et al.
patent: 2002/0107988 (2002-08-01), Jordan
patent: 2003/0009595 (2003-01-01), Collins
patent: 2003/0023536 (2003-01-01), Hollerman et al.
patent: 2003/0028509 (2003-02-01), Sah et al.
patent: 2003/0065662 (2003-04-01), Cosic
patent: 2003/0212694 (2003-11-01), Potapov et al.
patent: 2004/0034616 (2004-02-01), Witkowski et al.
patent: 0 079 465 (1983-05-01), None
DBA Certified Professional DBA Certification Exam Guide, by Jason S. Couchman, Osborne McGraw-Hill, 1998 (also an Oracle Press Edition).
Shannon, C.E., “A Mathematical Theory of Communication”, The Bell System Technical Journal, vol. 27, pp. 379-423, 623,656, Jul. Oct. 1948, Reprint pp. 1-55.
Westmann, Till et al., “The Implementation and Performance of Compressed Databases”, Reihe Informatik, Mar. 1998.
comp.compression Frequently Asked Questions (part 1/3), http://www.faqs.org/faqs/compression-faq/part1/, Last-modified: Sep. 5, 1999, pp. 1-65.
comp.compression Frequently Asked Questions (part 2.3), http://www.faqs.org/faqs/compression-faq/part2/, Last-modified Sep. 5, 1999, pp. 1-37.
comp.compression Frequently Asked Questions (part 3/3), http://www.faqs.org/faqs/compression-faq/part3/, Last-modified Feb. 7, 1996, pp. 1-13.
Bassiouni, M.A., “Data Compression in Scientific and Statistical Databases,”IEEE Transactions on Software Engineering, (1985), vol. SE-11, No. 10, pp. 1047-1058.
Bayer, R. et al., “Organization and Maintenance of Large Ordered Indexes,”Acta Informat., (1972) vol. 1, pp. 173-189.
Beckmann, N. et al., “The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles,”ACM SIGMOD(1992) pp. 322-331.
Berchtold, S. et al., “The X-Tree: An Index Structure for High-Dimensional Data,”VLDB(1996), pp. 28-39.
Eggers, S. J. et al., “A Compression Technique for Large Statistical Databases,”VLDB(1981), pp. 424-434.
Goldstein, J. et al., “Compressing Relations and Indexes,” Technical report No. 1355, CS Dept., University of Wisconsin-Madison (1997) pp. 1-23.
Guttman, Antonin, “R-Trees: A Dynamic Index Structure for Spatial Searching,”ACM SIGMOD(1984), pp. 47-57.
Leuteneger, S.T. et al., “STR: A Simple and Efficient Algorithm for R-Tree Packing,” Tech. Report, Mathematics and Computer Science Dept., University of Denver (1996) No. 96-02, pp. 1-29.
Lin, K.I. et al., The TV-Tree: An Index Structure for High-Dimensional Data,VLDB journal(1994), vol. 3, No. 4, pp. 517-542.
Ng, W. K. et al., “Relational Database Compression Using Augmented Vector Quantization,”IEEE 11thInternational Conference on Data Engineering(1995), pp. 540-549.
Nievergelt, J. et al, “The Grid File: An Adaptable, Symmetric Multikey File Structure,”Readings in Database Systems, (1988) Morgan Kaufmann, 582-598.
O'Neil, P. et al., “Improved Query Performance with Variant Indexes,”ACM SIGMOD(1977), pp. 38-49.
Roth, M.A. et al., “Database Compression,”SIGMOD Record, (1993) vol. 22, No. 3, pp. 31-39.
Seeger, B. et al., “The Buddy-Tree: An Efficient and Robust Method for Spatial Data Base Systems,”VLDB(1990), pp. 590-601.
Ziv, J., et al, “A Universal Algorithm for Sequential Data Compression,”IEEE Transactions on Information Theory, (1977) vol. 31, No. 3, pp. 337-343.
Benveniste et al. “Cache-memory interfaces in compressed memory systems” IEEE Transactions on Computers (Nov. 2001) 50(11):1106-1116.
de Castro et al. “Adaptive compressed caching: Design and Implementation” Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing (Nov. 2003) pp. 10-18.
Chen, W.T. et al. “Counter for Full Table Scan Control in Data Redistribution”,IBM Technical Disclosure Bulletin(Sep. 1992), vol. 35, No. 4B, pp. 3-4.
Chen, Z. and P. Seshadri “An Algebraic Compression Framework for Query Results” Data Engineering 2000, Proceedings of the 16thInternational Conference on San Diego, CA, USA, Feb. 29-Mar. 3, 2000,IEEE Comp. Soc.(Feb. 29, 2000) pp. 177-188.
Cockshott, W.P. et al. “Data Compression in Database Systems” Database and Expert Systems Applications 1998, Proceedings of the 9thInternational Workshop on Vienna, AT, Aug. 26-28, 1998IEEE Comp. Soc.(Aug. 26, 1998) pp. 981-990.
Goldstein, J. et al. “Compressing Relations and Indexes” Data Engineering 1998, Proceedings of the 14thInternational Conference on Orlando, FL, USA, Feb. 23-27, 1998,IEEE Comput. Soc.(Feb. 23, 1998) pp. 370-379.
Graefe, G. and L.D. Shapiro “Data Compression and Database Performance” Applied Computing 1991, Proceedings of the 1991 Symposium on Kansas City, MO, USA, Apr. 3-5, 1991IEEE Comp. Soc.(Apr. 3, 1991) pp. 22-27.
Haerder, T. et al. “Speicherungsstrukturen”Datenbanksysteme: Konzepte und Techniken der Implementierung(1999), Book excerpt, pp. 143-175.
Ng, W.K. and C.V. Ravishankar “Relational Database Compression Using Augmented Vector Quantization” Data Engineering 1995, Proceedings of the 11thInternational Conference on Taipei, TW, Mar. 6-10, 1995,IEEE Comp. Soc.(Mar. 6, 1995) pp. 540-549.
Olken, F. and D. Rotem “Rearranging Data to Maximize the Efficiency of Compression”J. Comp. Sys. Sci.(Apr. 1989) 38(2):405-430.
Segev, A. and A. Chatterjee “Supporting Statistics in Extensible Databases: A Case Study” Scientific and Statistical Database Management 1994, Proceedings of the 7thInternational Working Conference on Charlottesville, VA, USA, Sep. 28-30, 1994,IEEE Comput. Soc.(Sep. 28, 1994), pp. 54-63.
International Search Report dated May 24, 2004 (PCT/US2003/001484).
Written Opinion dated Jul. 29, 2004 (PCT/US2003/001484).

Affiliated with

Also associated with

Rating

Method and mechanism for storing and accessing data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and mechanism for storing and accessing data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and mechanism for storing and accessing data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3542025