Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-10-17
2006-10-17
Al-Hashemi, Sana (Department: 2164)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
07124146
ABSTRACT:
A technique is provided for incrementally maintaining column cardinality estimates in database management systems. The system catalog table containing a cardinality estimate for a column is extended to include an appropriate data structure. A modified linear counting technique is used in a first embodiment of a method for column cardinality estimation. Moreover, a modified logarithmic counting technique is used in a second, preferred embodiment of a column cardinality estimation method to reduce storage requirements for the data structure. The cardinality estimate is produced by an initial scan of the data but is then further maintained without requiring a full scan of the data. Data changes are reflected incrementally in modifications to the initial cardinality estimate, keeping the cardinality statistics more current with respect to the database condition. The technique of the invention typically provides a capability for a database management system to produce more efficient search plans providing more effective responses to user queries through the use of improved cardinality statistics.
REFERENCES:
patent: 5542089 (1996-07-01), Lindsay et al.
patent: 5761653 (1998-06-01), Schiefer et al.
patent: 5802521 (1998-09-01), Ziauddin et al.
patent: 5956706 (1999-09-01), Carey et al.
patent: 5995957 (1999-11-01), Beavin et al.
patent: 6282541 (2001-08-01), Hoa et al.
patent: 6606638 (2003-08-01), Tarin
patent: 2002/0026438 (2002-02-01), Rjaibi et al.
patent: 2002/0046301 (2002-04-01), Shannon et al.
patent: 2002/0065704 (2002-05-01), Dunn
Schiefer, Swami A. “On the Estimation of Join Result Sizes,” Advances in Database Technology Proceedings, Published: Berlin, Germany, 1994, pp. 287-300.
Bell, Colin; Nerode, Anil; NG, Raymond T.; Subrahmanian, V.S. “Implementing Deductive Databases by Mixed Integer Programming,”ACM Transactions on Database Systems,vol. 21, No. 2, Jun. 1996, pp. 238-269.
Emiris, Ioannis; Canny, John. “A Practical Method for the Sparse Resultant,” 1993 ACM 0-89791-604-2/93/0007/0183.
Haas Peter Jay
Rjaibi Walid
Al-Hashemi Sana
Sawyer Law Group LLP
LandOfFree
Incremental cardinality estimation for a set of data values does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Incremental cardinality estimation for a set of data values, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental cardinality estimation for a set of data values will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3633768