Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-07-11
2006-07-11
Alam, Shahid (Department: 2162)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S201000
Reexamination Certificate
active
07076507
ABSTRACT:
A computer-implemented database and method providing an efficient, ordered reduced space representation of multi-dimensional data. The data values for each attribute are stored in a manner that provides an advantage in, for example, space usage and/or speed of access, such as in condensed form and/or sort order. Instances of each data value for an attribute are identified by instance elements, each of which is associated with one data value. Connectivity information is provided for each instance element that uniquely associates each instance element with a specific instance of a data value for another attribute. Low cardinality fields may be combined into a single field having values representing the various combinations of the original fields. In one embodiment, the “combined field” contains only instantiated combinations. In another embodiment, the combined field contains all values in the Cartesian product of the original fields, preferably in nested sort order. In yet another embodiment, the original fields are padded with dummy values so that their cardinalities are a power of two, causing each subfield in the combined field to fall on a bit boundary. In still another embodiment, containerization techniques are used to reduce the space required for representing the complete set of all possible values in the Cartesian product of the original fields.
REFERENCES:
patent: 4468732 (1984-08-01), Raver
patent: 4479196 (1984-10-01), Ferrer et al.
patent: 4858146 (1989-08-01), Shebini
patent: 5010478 (1991-04-01), Deran
patent: 5201046 (1993-04-01), Goldberg et al.
patent: 5276868 (1994-01-01), Poole
patent: 5379422 (1995-01-01), Antoshenkov
patent: 5388259 (1995-02-01), Fleischman et al.
patent: 5412797 (1995-05-01), Rubin
patent: 5414834 (1995-05-01), Alexander et al.
patent: 5495608 (1996-02-01), Antoshenkov
patent: 5504885 (1996-04-01), Alashqur
patent: 5542073 (1996-07-01), Schiefer et al.
patent: 5546575 (1996-08-01), Potter et al.
patent: 5555388 (1996-09-01), Shaughnessy
patent: 5560006 (1996-09-01), Layden et al.
patent: 5592667 (1997-01-01), Bugajski
patent: 5611076 (1997-03-01), Durflinger et al.
patent: 5649181 (1997-07-01), French et al.
patent: 5675779 (1997-10-01), Doktor
patent: 5692178 (1997-11-01), Shaughnessy
patent: 5701461 (1997-12-01), Dalal et al.
patent: 5713014 (1998-01-01), Durflinger et al.
patent: 5734887 (1998-03-01), Kingberg et al.
patent: 5761652 (1998-06-01), Wu et al.
patent: 5787279 (1998-07-01), Rigoutsos
patent: 5794229 (1998-08-01), French et al.
patent: 5797000 (1998-08-01), Bhattacharya et al.
patent: 5797136 (1998-08-01), Boyer et al.
patent: 5799312 (1998-08-01), Rigoutsos
patent: 5802525 (1998-09-01), Rigoutsos
patent: 5838965 (1998-11-01), Kavanagh et al.
patent: 5855019 (1998-12-01), Bhargava et al.
patent: 5918225 (1999-06-01), White et al.
patent: 5956706 (1999-09-01), Carey et al.
patent: 5963936 (1999-10-01), Cochrane et al.
patent: 5966709 (1999-10-01), Zhang et al.
patent: 5983232 (1999-11-01), Zhang
patent: 5999933 (1999-12-01), Mehta
patent: 6006219 (1999-12-01), Rothschild
patent: 6018734 (2000-01-01), Zhang et al.
patent: 6088691 (2000-07-01), Bhargava et al.
patent: 6138111 (2000-10-01), Krishna
patent: 6199099 (2001-03-01), Gershman et al.
patent: 6330554 (2001-12-01), Altschuler et al.
patent: 6374263 (2002-04-01), Bunger et al.
patent: 6484179 (2002-11-01), Roccaforte
“ERDB Entity-Relation Database,” Website and ERDB Manual, www.ataindy.com, copyright 1998, Automated Technology Associates.
“Monet Source Code,” dated Jan. 8, 1996, as appears on www.cwi.nl/˜monet/srcdoc.html as of Feb. 5, 1999.
“Monet Performance,” www.cwi.nl/˜monet/performance.html, last modified Sep. 20, 1995.
Boncz et al., “The Drill Down Benchmark,” www.cwi.nl/˜monet/papers.html, appears in Proceedings of the 24thVLDB Conference New York, USA, 1998.
Boncz et al., “Flattening an Object Algebra to Provide Performance,” www.cwi.nl/˜monet/papers.html, appears in 14thInternational Conference on Data Engineering, Feb. 23-27, 1998, Orlando, Florida, USA.
Boncz et al., “Monet and Its Geographic Extensions: a Novel Approach to High Performance GIS Processing,” as appears on www.cwi.nl/˜monet/papers.html as of Feb. 5, 1999.
Boncz et al., “Monet An Impressionist Sketch of An Advanced Database System,” www.cwi.nl/˜monet/papers.html, appears in Basque International Workshop on Information Technology, Data Management Systems, San Sebastian, Spain, Jul. 19-21, 1995.
van den Berg et al., “Monet Meets 007,” Nov. 3, 1995, as appears on www.cwi.nl/˜monet/papers.html as of Feb. 5, 1999.
Kersten et al., “A Data Cube Algebra Engine for Data Mining,” as appears on www.cwi.nl/˜monet/papers.html as of Feb. 5, 1999.
van den Berg, “Dynamic Query Processing in a Parallel Object-Oriented Databae System,” Ph.D. Thesis, published at CWI, 1994, as appears on www.cwi.nl/˜monet/papers.html as of Feb. 5, 1999.
van den Berg et al., “Analysis of a Dynamic Query Optimization Technique for Multi-Join Queries,” as appears on www.cwi.nl/˜monet/papers.html as of Feb. 5, 1999.
Angara website, www.angara.com, copyright 1998, Angara Database Systems, Inc.
Cache website, www.intersys.com, copyright 1996, 1997, 1998, InterSystems Corporation.
“The Dali Main-Memory Storage Manager,” Dali website, www.bell-labs.com/project/dali, copyright 1996, as appears on the website as of Feb. 5, 1999.
Jagadish et al., “Dali: A High Performance Main Memory Storage Manager,” www.bell-labs.com/project/dali, appears in Proceedings of the 20thVLDB Conference Santiago, Chile, 1994.
Bohannon et al., “Recoverable User-Level Mutual Exclusion,” as appears on www.bell-labs.com/project/dali as of Feb. 5, 1999.
Bohannon et al., “Logical and Physical Versioning in Main Memory Databases,” www.bell-labs.com/project/dali, appears in Proceedings of the Conference on Very Large Database, 1997.
“Times Ten Performance Software,” Times Ten website, www.timesten.com, copyright 1997, 1998.
“Titanum Database Engine Technical Synopsis” copyright 1998, Micro Data Base Systems, Inc..
Herrin et al., “Schema and Tuple Trees: An Intuitive Structure for Representing Relational Data,” www.hsdi.com/qddb/article2, appears in Computing Systems, vol. 9, No. 2, copyright 1996 by the USENIX Association.
Herrin et al., “An ASCII Database for Fast Queries of Relatively Stable Data,” www.hsdi.com/qddb/article2, appears in Computing Systems, vol. 4, No. 2, copyright 1991 by the Regents of the University of California.
Date, C. J., “An Introduction to Database Systems,” 3rdEd., pp. 33-61, Addison-Wesley Publishing Company.
Date, C. J., Aug., 1995, “An Introduction to Database Systems,” 6thEd., pp. 1-51, 710-760, Addison-Wesley Publishing Company.
Batory, D.S., “On Searching Transposed Files,” ACM Transactions on Database Systems, vol. 4, No. 4, Dec. 1979, pp. 531-544.
Batory et al., “A Unifying Model of Physical Databases,” ACM Transactions on Database Systems, vol. 7, No. 4, Dec. 1982, pp. 509-539.
Eggers et al., “Efficient Access of Compressed Data,” IEEE, 1980, pp. 205-211.
Eggers et al., “A Compression Technique for Large Statistical Databases,” IEEE, 1981, pp. 424-434.
Valduriez, P., “Join Indices,” ACM Transactions on Database Systems, vol. 12, No. 2, Jun. 1987, pp. 218-246.
Olken et al., “Rearranging Data to Maximize the Efficiency of Compression,” ACM, 1986, pp. 78-90.
Alam Shahid
Required Technologies, Inc.
LandOfFree
Value-instance-connectivity computer-implemented database does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Value-instance-connectivity computer-implemented database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Value-instance-connectivity computer-implemented database will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3593879