Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-07-24
2007-07-24
Channavajjala, Srirama (Department: 2166)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
10608083
ABSTRACT:
By transforming a query into a product of conditional selectivity expressions, an existing set of statistics on query expressions can be used more effectively to estimate cardinality values. Conditional selectivity values are progressively separated according to rules of conditional probability to yield a set of non-separable decompositions that can be matched with the stored statistics on query expressions. The stored statistics are used to estimate the selectivity of the query and the estimated selectivity can be multiplied by the Cartesian product of referenced tables to yield a cardinality value.
REFERENCES:
patent: 4769772 (1988-09-01), Dwyer
patent: 5724570 (1998-03-01), Zeller et al.
patent: 5806061 (1998-09-01), Chaudhuri et al.
patent: 5950186 (1999-09-01), Chaudhuri et al.
patent: 6029163 (2000-02-01), Ziauddin
patent: 6061676 (2000-05-01), Srivastava et al.
patent: 6088691 (2000-07-01), Bhargava et al.
patent: 6272487 (2001-08-01), Beavin et al.
patent: 6311181 (2001-10-01), Lee et al.
patent: 6363371 (2002-03-01), Chaudhuri et al.
patent: 6438741 (2002-08-01), Al-omari et al.
patent: 6477534 (2002-11-01), Acharya et al.
patent: 6516310 (2003-02-01), Paulley
patent: 6529901 (2003-03-01), Chaudhuri et al.
patent: 6629095 (2003-09-01), Wagstaff et al.
patent: 6714938 (2004-03-01), Avadhanam et al.
patent: 6778976 (2004-08-01), Haas et al.
patent: 6915290 (2005-07-01), Bestgen et al.
patent: 6947927 (2005-09-01), Chaudhuri et al.
patent: 6961721 (2005-11-01), Chaudhuri et al.
patent: 6983275 (2006-01-01), Koo et al.
patent: 7010516 (2006-03-01), Leslie
patent: 2003/0018615 (2003-01-01), Chaudhuri et al.
patent: 2003/0120682 (2003-06-01), Bestgen et al.
patent: 2003/0229635 (2003-12-01), Chaudhuri et al.
patent: 2004/0249810 (2004-12-01), Das et al.
patent: 2004/0260675 (2004-12-01), Bruno et al.
patent: 2005/0071331 (2005-03-01), Gao et al.
patent: 2006/0294065 (2006-12-01), Dettinger et al.
patent: 2416368 (2003-10-01), None
patent: 0743607 (1996-11-01), None
patent: 1564620 (2005-08-01), None
patent: WO 92/15066 (1992-09-01), None
patent: WO 98/26360 (1998-06-01), None
patent: WO 02//41185 (2002-05-01), None
patent: WO 02/089009 (2002-11-01), None
Chiang Lee et al. “Optimizing Large join queries using a graph-based approach”, IEEE transactions on knowledge and data engineering, vol. 13, No. 2,Mar./Apr. 2001, pp. 298-315.
Dongwon Lee et al. “Conjuctive point predicate-based semantic caching for web databases”, UCLA-CS-TR-980030, last revised: Sep. 24, 1998, pp. 1-21.
Oliver M Duschka et al. “Query planning in infomaster”, Proceedings of the 1997 ACM symposium on applied computing, 1997, pp. 109-111.
Chun-Nan Hsu et al. “Semantic query optimization for query plans of heterogeneous multidatabase systems”, IEEE transactions on knowledge and data engineering, vol. 12, No. 6, Nov./Dec. 2000, pp. 959-978.
Nicolas Bruno, “Automatic management of statistics on Query expressions in relational databases”, Ph.D. Thesis Proposal, Dept of computer science, Columbia University, NY, Apr. 25, 200232 pages.
Stratis D Viglas et al. “Rate-based query optimization for streaming information sources”, ACM SIGMOD 2002.
Vijayshankar Raman et al. “partial results for online query processing”, ACM/SIGMOD,2002.
Jenk Ernst Blok et al. “A selectivity model for fragmented relations: applied in information retrieval”, IEEE transactions on knowledge and daa engineering, vol. 16,No. 5, 2004, pp. 635-639.
Yun-Wu Huang et al. “optimizing path query performance: graph clustering strategies”, Transportation research part C 8 (2000) pp. 381-408.
Faruk Polat et al. “semantic information-based alternative plan generation for multiple query optimization”, information sciences 137 (2001) pp. 103-133.
N. Bruno and S. Chaudhuri. Exploiting Statistics on Query Expressions for Optimization. InProceedings of the 2002 ACM International Conference on Management of Data(SIGMOND'2), 2002.
N. Bruno and S. Chaudhuri. Efficient Creation of Statistics over Query Expressions. InProceedings of the 19thInternational Conference on Data Engineering, 2003.
N. Bruno, S. Chaudhuri, and L. Gravano. STHoles: A Multidimensional Workload-Aware Histogram. InProceedings of the 2001 ACM International Conference on Management of Data(SIGMOND'01), 2001.
S. Chaudhurin et al. Optimizing Queries with Materialized Views. InProceedings of the 11thInternational Conference on Data Engineering, 1995.
J. Goldstein and P.-A. Larson. Optimizing Queries Using Materialized Views: A Practical, Scalable Solution. InProceedings of the 2001 ACM International Conference on Management of Data(SIGMOND'01), 2001.
G. Graefe. The Cascades Framework for Query Optimization.Data Engineering Bulletin, 18(3), 1995.
G. Graefe and W. McKenna. The Volcano Optimizer Generator: Extensibility and Efficient Search. InProceedings of the 9thInt. Conference on Data Engineering, 1993.
G. Graefe and W. McKenna. The Volcano Optimizer Generator: Extensibility and Efficient Search. InProceedings of the 9thInt. Conference on Data Engineering, 1993.
L. M. Haas, J. C. Freytag, G. M. Lohman, and H. Pirahesh. Extensible Query Processing in Starburst. InProceedings of the 1989 ACM International Conference on Management Data(SIGMOND'89), 1989.
M. Muralikrishna and D. J. DeWitt. Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. InProceedings of the 1988 ACM International Conference on Management of Data(SIGMOND'88), 1988.
V. Poosala and Y. E. Ioannidis. Selectivity Estimation Without the Attribute Value Independence Assumption. InProceedings of the Twenty-third International Conference on Very Large Databases(VLDB'97), Aug. 1997.
V. Poosala, Y. E. Ioannidis, P. J. Hass, and E. J. Shekita. Improved Histograms for Selectivity Estimation of Range Predicates. InProceedings of the 1996 ACM International Conference on Management of Data(SIGMOND'96), 1996.
M. Stillger, G. M. Lohman V. Markl, and M. Kandil. LEO—DB2's Learning Optimizer. InProceedings of the 27thInternational Conference on Very Large Databases, 2001.
Bruno Nicolas
Chaudhuri Surajit
LandOfFree
Method and apparatus for selecting candidate statistics to... 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 apparatus for selecting candidate statistics to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for selecting candidate statistics to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3798379