Query optimizer with schema conversion

Details Query optimizer with schema conversion Query optimizer with schema conversion

2009-02-06

2011-12-27

Lewis, Cheryl (Department: 2155)

Data processing: database and file management or data structures

Database and file access

Query optimization

C707S606000, C707S797000

Reexamination Certificate

active

08086598

ABSTRACT:
Methods, program products and systems for determining, for a database query that does not represent a snowflake schema, a graph comprising vertices each representing a table joined in the query, a directed edge between each pair of vertices of which a first vertex represents a first table and a second vertex represents a second table that is joined in the query with the first table, each of the edges representing one of an outer join and an inner join. Further determining, for the graph, a directed spanning tree that represents an ordering of joins in the query and includes all outer join edges in the graph.

REFERENCES:
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5423037 (1995-06-01), Hvasshovd
patent: 5701460 (1997-12-01), Kaplan et al.
patent: 5794228 (1998-08-01), French et al.
patent: 5794229 (1998-08-01), French et al.
patent: 5878409 (1999-03-01), Baru et al.
patent: 5918225 (1999-06-01), White et al.
patent: 5960423 (1999-09-01), Chaudhuri et al.
patent: 6009432 (1999-12-01), Tarin
patent: 6029163 (2000-02-01), Ziauddin
patent: 6105020 (2000-08-01), Lindsay
patent: 6421687 (2002-07-01), Klostermann
patent: 6801903 (2004-10-01), Brown et al.
patent: 6879984 (2005-04-01), Duddleson et al.
patent: 7024414 (2006-04-01), Sah et al.
patent: 7139783 (2006-11-01), Hinshaw et al.
patent: 7464247 (2008-12-01), Uppala
patent: 7483918 (2009-01-01), Chaudhuri et al.
patent: 7716167 (2010-05-01), Colossi et al.
patent: 2004/0260684 (2004-12-01), Agrawal et al.
patent: 2005/0065939 (2005-03-01), Miao
patent: 2005/0187917 (2005-08-01), Lawanade et al.
patent: 2005/0187977 (2005-08-01), Frost
patent: 2005/0203940 (2005-09-01), Farrar et al.
patent: 2005/0283658 (2005-12-01), Clark et al.
patent: 2006/0085484 (2006-04-01), Raizman et al.
patent: 2006/0184338 (2006-08-01), Lightstone et al.
patent: 2006/0253473 (2006-11-01), Agrawal et al.
patent: 2006/0282423 (2006-12-01), Al-Omari et al.
patent: 2007/0027904 (2007-02-01), Chow et al.
patent: 2007/0067261 (2007-03-01), Burger et al.
patent: 2008/0033914 (2008-02-01), Cherniack et al.
patent: 2008/0281784 (2008-11-01), Zane et al.
patent: 2010/0131490 (2010-05-01), Lamb et al.
patent: 2008016877 (2008-02-01), None
Steinbrunn et al., “Heuristic and Randomized Optimization for the Join Ordering Problem,” VLDB Journal, Spring Verlag, Berlin, DE LINKD—DOI: 10.1007/500778005040, vol. 6, No. 3, Aug. 1, 1997, pp. 191-208, XP000957755, ISSN: 1066-8888, the whole document.
Son J.H. et al.: “An Adaptable Vertical Partitioning Method In Distributed Systems”, Journal of Systems and Software, Elsevier North Holland, New York, NY, US LNKD-DOI: 10.1016/J.JSS.2003.04.002, vol. 73, No. 3, Nov. 1, 2004, pp. 551-561, XP004560798 ISSN: 0164-1212, 11 pages.
Supplementary European Search Report for EP Application No. EP 07799914, dated May 28, 2010, 63 pages.
International Search Report and Written Opinion for PCT Application No. PCT/US2010/023216, dated Aug. 3, 2010, 49 pages.
“ADABAS-RAPID Demonstration Databases,” Statistics Canada, Demonstration Databases, Jun. 1978, 38 pages.
Ailamaki et al., “Weaving Relations for Cache Performance,” Proceedings of the 27thVLDB Conference, Roma, Italy, 2001, 12 pages.
Alsberg, Peter A. ,“Space and Time Savings Through Large Data Base Compression and Dynamic Restructuring,” Proceedings of the IEEE vol. 63, No. 8, Aug. 1975, 9 pages.
“An Introduction to Multidimensional Database Technology,” Kenan Systems Corporation, 1993-1995, 29 pages.
Andersson, “A Study of Modified Interpolation Search in Compressed, Fully Transposed, Ordered Files,” Proceedings of the 4thInternational Conference on Statistical and Scientific Database Management, 1988, 13 pages.
Apache Cassandra “Data Model” [online], [retrieved on May 29, 2009]. Retrieved from the Internet <URL: http://cwiki.apache.org/confluence/display/CSDR/Pata+Model>, 2 pages.
Baker, Margaret, “User's Guide to the Berkeley Transposed File Statistical System,” Survey Research Center Technical Report No. One, Jan. 1974, 132 pages.
Batory, D. S., “On Searching Transposed Files,” ACM Transactions on Database Systems, vol. 4, No. 4, Dec. 1979, 14 pages.
Bleier et al., “File Organization in the SDC Time-Shared Data Management System (TSMS),” North-Holland Publishing Company, 1969, 8 pages.
Boral et al., “Prototyping Bubba, A Highly Parallel Database System,” IEEE Trans. on Knowledge and Data Engineering, Mar. 1990, 21 pages.
Brun et al., “Visualization of Scientific Data for High Energy Physics. PAW++, KUIP, PIAF: General-Purpose Portable Software Tools for Data Analysis and Presentation,” European Organization for Nuclear Research, 1993, 12 pages.
Burnett et al., “Data Management Support for Statistical Data Editing and Subset Selection,” Proceedings of the 1stLBL Workshop on Statistical Database Management, 1981, 15 pages.
Cochinwala et al., “A Multidatabase System for Tracking and Retrieval of Financial Data,” Proceedings of the 20thVLDB Conference Santiago, Chile, 1994, 8 pages.
Cohen et al., MAD Skills: New Analysis Practices for Big Data [online], [retrieved May 29, 2009]. Retrieved from the Internet <URL: http://db.cs.berkeley.edu/papers/vldb09-madskills.pdf>, 12 pages.
Cornell, “A Vertical Partitioning for Relational Databases,” IBM Thomas J. Watson Research Center, 1987, 8 pages.
Cornell et al., “An Effective Approach to Vertical Partitioning for Physical Design of Relational Databases,” IEEE Transactions on Software Engineering, vol. 16, No. 2, Feb. 1990, 11 pages.
Cressman, “Analysis of Data Compression in the DLT2000 Tape Drive,” Digital Technical Journal vol. 6, No. 2, 1994, 17 pages.
Date, C. J., “An Introduction to Database Systems, vol. 1,” Addison-Wesley Publishing Company, 1990, 400 pages.
DBMS2—The secret sauce to Clearpace's compression [online], [retrieved May 29, 2009]. Retrieved from the Internet <URL: http://www.dbms2.com/2009/05/14/the-secret-sauce-to-clearpaces-compression/>, 6 pages.
Elmasri et al., “Fundamentals of Database Systems.” The Benjamin/Cummings Publishing Company, Inc., 1989.
Farsi et al., “A Relational Database for Efficient Processing of Statistical Queries,” Proceedings of the Second International Workshop on Statistical Database Management, 1983, 9 pages.
Goil et al., “Sparse Data Storage of Multi-Dimensional Data for OLAP and Data Mining,” Department of Electrical & Computer Engineering Center for Parallel and Distributed Computing, 1994, 26 pages.
Goldstein, Andrew C. “Files-11 On-Disk Structure Specification,” Digital Equipment Corporation, Jan. 15, 1979, 104 pages.
Greenplum—Greenplum Database 3.3—Features [online], [retrieved Jul. 13, 2009]. Retrieved from the Internet <URL: http://www.greenplum.com/products/features/>, 6 pages.
Hammer et al., “A Heuristic Approach to Attribute Partitioning,” Laboratory for Computer Science, 1979, 9 pages.
Hawthorn, Paula, “Microprocessor Assisted Tuple Access, Decompression and Assembly for Statistical Database Systems,” Proceedings of the 8thVLDB, 1982, pp. 223-233.
Inmon et al., “The Dynamics of Data Base,” Prentice Hall, 1986.
Khoshafian et al., “Efficient Support of Statistical Operations,” IEEE Trans. On Software Engineering, vol. SE-11, No. 10, Oct. 1985, 13 pages.
Khoshafian et al., “A Query Processing Strategy for the Decomposed Storage Model,” Microelectronics and Computer Technology Corporation, 1987, pp. 636-643.
Kickfire “The First Analytic Appliance for the Mass Market, Blog comment,” [online], (retrieved on Aug. 6, 2009). Retrieved from the Internet: <URL: http://www.kickfire.com/blog/?p-392>, 4 pages.
Korth et al., “Database System Concepts,” Second Edition, McGraw-Hill, Inc., 1991.
March,

Affiliated with

Also associated with

Rating

Query optimizer with schema conversion does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Query optimizer with schema conversion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query optimizer with schema conversion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4260123