Method and system for using materialized views to evaluate queries involving aggregation

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 5897632
SERIAL NO

08895024

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

The present invention is a method and system for using materialized views to compute answers to SQL queries with grouping and aggregation. A query is evaluated a using a materialized view. The materialized view is semantically analyzed to determine whether the materialized view is usable in evaluating an input query. The semantic analysis includes determining that the materialized view does not project out any columns needed to evaluate the input query and determining that the view does not discard any tuple that satisfies a condition enforced in the input query. If the view is usable, the input query is rewritten to produce an output query that is multi-set equivalent to the input query and that specifies one or more occurrences of the materialized view as a source of information to be returned by the output query. The output query is then evaluated. The semantic analysis and rewriting may be iterated, with the output query of each iteration being the input query of the next iteration. The output query is evaluated after the last iteration.

Loading the Abstract Image... loading....

First Claim

See full text

Family

Loading Family data... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
LINKEDIN CORPORATIONPALO ALTO, CA1221

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Dar, Shaul Tel Aviv, IL 6 304
Jagadish, Hosagrahar Visvesvaraya Berkeley Heights, NJ 23 963
Levy, Alon Yitzchak Seattle, WA 7 717
Srivastava, Divesh Summit, NJ 125 2227

Cited Art Landscape

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (1)
* 5161225 Persistent stream for processing time consuming and reusable queries in an object oriented database management system 97 1989
 
HEWLETT-PACKARD COMPANY (1)
* 5276870 View composition in a data base management system 159 1990
 
SOUND VIEW INNOVATIONS, LLC (3)
* 5655116 Apparatus and methods for retrieving information 72 1994
* 5600831 Apparatus and methods for retrieving information by modifying query plan based on description of information sources 152 1994
* 5768578 User interface for information retrieval system 378 1995
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (14)
* 6275818 Cost based optimization of decision support queries using transient views 112 1998
* 6532470 Support for summary tables in a database system that does not otherwise support summary tables 7 1999
* 6636846 Method for providing a system maintained materialized functionally dependent column for a database management system 18 2000
* 2004/0122,814 Matching groupings, re-aggregation avoidance and comprehensive aggregate function derivation rules in query rewrites using materialized views 10 2002
6950823 Transparent edge-of-network data cache 34 2002
* 2004/0133,538 Transparent edge-of-network data cache 12 2002
7020649 System and method for incrementally maintaining non-distributive aggregate functions in a relational database 13 2002
* 2004/0128,289 System and method for incrementally maintaining non-distributive aggregate functions in a relational database 1 2002
* 8417680 System for improving access efficiency in database and method thereof 1 2006
* 2009/0307,275 SYSTEM FOR IMPROVING ACCESS EFFICIENCY IN DATABASE AND METHOD THEREOF 3 2006
* 8965912 Integrating databases 0 2007
* 2008/0306,904 SYSTEM, METHOD, AND PROGRAM PRODUCT FOR INTEGRATING DATABASES 12 2007
* 8620899 Generating materialized query table candidates 0 2010
* 2011/0196,857 Generating Materialized Query Table Candidates 5 2010
 
Other [Check patent profile for assignment information] (1)
* 2006/0206,468 RULE APPLICATION MANAGEMENT IN AN ABSTRACT DATABASE 5 2006
 
SYBASE, INC. (2)
* 6691101 Database system providing optimization of group by operator over a union all 47 2002
* 2002/0198,872 Database system providing optimization of group by operator over a union all 10 2002
 
WORKDAY, INC. (4)
* 6199063 System and method for rewriting relational database queries 97 1998
* 6594653 Server integrated system and methods for processing precomputed views 58 1999
* 6493699 Defining and characterizing an analysis space for precomputed views 46 1999
* 6629094 System and method for rewriting relational database queries 73 2000
 
SAP SE (5)
7464083 Combining multi-dimensional data sources using database operations 6 2005
* 8924384 Upgrading column-based databases 6 2010
* 2012/0036,165 UPGRADING COLUMN-BASED DATABASES 14 2010
* 9460176 In-memory database for multi-tenancy 0 2010
* 2012/0173,589 In-Memory Database For Multi-Tenancy 11 2010
 
EXCALIBUR IP, LLC (1)
* 7921103 Adaptive materialized view selection for databases 4 2008
 
HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP (1)
* 6134545 Method and system for processing a query 3 1998
 
LUCENT TECHNOLOGIES INC. (2)
* 6353835 Technique for effectively maintaining materialized views in a data warehouse 38 1998
6721735 Method and apparatus for synchronizing databases in a network management system 11 2000
 
Savera Systems, Inc. (1)
* 6484159 Method and system for incremental database maintenance 31 1999
 
TERADATA US, INC. (2)
* 7092951 Auxiliary relation for materialized view 11 2001
7761477 Auxiliary relation for materialized view 3 2004
 
HUAWEI TECHNOLOGIES CO., LTD. (1)
* 6339769 Query optimization by transparently altering properties of relational tables using materialized views 73 1998
 
AT&T INTELLECTUAL PROPERTY II, L.P. (2)
* 5987450 System and method for obtaining complete and correct answers from incomplete and/or incorrect databases 6 1997
8312099 Pseudo proxy server 1 2005
 
AT&T INTELLECTUAL PROPERTY I, L.P. (4)
8161048 Database analysis using clusters 20 2009
* 2010/0274,785 Database Analysis Using Clusters 62 2009
8595194 Forward decay temporal data analysis 0 2009
* 2011/0066,600 FORWARD DECAY TEMPORAL DATA ANALYSIS 7 2009
 
TWITTER, INC. (2)
7711692 Method, system and program product for rewriting view statements in structured query language (SQL) statements 0 2004
* 2006/0106,765 Method, system and program product for rewriting view statements in structured query language (SQL) statements 3 2004
 
ORACLE INTERNATIONAL CORPORATION (38)
6439783 Range-based query optimizer 87 1997
6496819 Rewriting a query in terms of a summary based on functional dependencies and join backs, and based on join derivability 104 1998
* 6477525 Rewriting a query in terms of a summary based on one-to-one and one-to-many losslessness of joins 47 1998
6449605 Using a materialized view to process a related query containing a one to many lossless join 21 1998
6449606 Using a materialized view to process a related query containing an antijoin 12 1998
6449609 Using materialized view to process a related query containing a one to many lossless join 26 1998
6334128 Method and apparatus for efficiently refreshing sets of summary tables and materialized views in a database management system 59 1998
* 6345272 Rewriting queries to access materialized views that group along an ordered dimension 26 1999
6546382 Finding the TOP N values through the execution of a query 18 1999
6622138 Method and apparatus for optimizing computation of OLAP ranking functions 66 2000
6389410 Method for minimizing the number of sorts required for a query block containing window functions 13 2000
7158994 Object-oriented materialized views 31 2001
* 7379933 Union all rewrite for aggregate queries with grouping sets 9 2002
7930277 Cost-based optimizer for an XML data repository within a database 4 2004
7814067 Asynchronous actions using flashback 9 2005
* 2005/0125,430 Asynchronous actions using flashback 41 2005
8478742 Using estimated cost to refresh a set of materialized views (MVS) 3 2005
7890497 Using estimated cost to schedule an order for refreshing a set of materialized views (MVS) 12 2005
7734602 Choosing whether to use a delayed index maintenance depending on the portion of the materialized view (MV) changed 11 2005
* 2005/0235,004 Using estimated cost to schedule an order for refreshing a set of materialized views (MVS) 5 2005
* 2005/0234,971 Using estimated cost to refresh a set of materialized views (MVS) 8 2005
7814065 Affinity-based recovery/failover in a cluster environment 18 2005
* 2007/0043,726 Affinity-based recovery/failover in a cluster environment 11 2005
7685150 Optimization of queries over XML views that are based on union all operators 2 2005
* 2006/0235,840 Optimization of queries over XML views that are based on union all operators 52 2005
8073841 Optimizing correlated XML extracts 3 2005
* 2007/0083,809 Optimizing correlated XML extracts 3 2005
* 2007/0239,659 Query generator 1 2006
7912834 Rewrite of queries containing rank or rownumber or Min/Max aggregate functions using a materialized view 5 2006
* 2006/0212,436 Rewrite of queries containing rank or rownumber or Min/Max aggregate functions using a materialized view 11 2006
* 7730080 Techniques of rewriting descendant and wildcard XPath using one or more of SQL OR, UNION ALL, and XMLConcat() construct 3 2006
* 2007/0299,834 Techniques of rewriting descendant and wildcard XPath using combination of SQL OR, UNION ALL, and XMLConcat() construct 14 2006
7797310 Technique to estimate the cost of streaming evaluation of XPaths 1 2007
* 2008/0091,623 Technique to estimate the cost of streaming evaluation of XPaths 11 2007
7958112 Interleaving query transformations for XML indexes 0 2008
* 2010/0036,825 Interleaving Query Transformations For XML Indexes 3 2008
8103689 Rewrite of queries containing rank or rownumber or min/max aggregate functions using a materialized view 4 2011
* 2011/0106,790 Rewrite of Queries Containing Rank or Rownumber or Min/Max Aggregate Functions Using a Materialized View 2 2011
 
LingoMotors, Inc. (1)
* 2002/0147,578 Method and system for query reformulation for searching of information 61 2001
 
THE TRUSTEES OF COLUMBIA UNIVERSITY IN THE CITY OF NEW YORK (1)
* 6026390 Cost-based maintenance of materialized views 63 1997
 
MICROSOFT TECHNOLOGY LICENSING, LLC (13)
* 6366903 Index and materialized view selection for a given workload 85 2000
* 6356890 Merging materialized view pairs for database workload materialized view selection 32 2000
* 6356891 Identifying indexes on materialized views for database workload 42 2000
* 6510422 Cost based materialized view selection for query optimization 34 2000
* 6850933 System and method for optimizing queries using materialized views and fast view matching 27 2001
* 2003/0093,415 System and method for optimizing queries using materialized views and fast view matching 11 2001
* 7383256 System and method for optimizing queries using materialized views and fast view matching 4 2004
* 2005/0091,208 System and method for optimizing queries using materialized views and fast view matching 3 2004
7406468 View matching for materialized outer-join views 4 2005
* 2006/0282,424 View matching for materialized outer-join views 4 2005
7769755 Efficient execution of aggregation queries 0 2006
* 2008/0133,492 EFFICIENT EXECUTION OF AGGREGATION QUERIES 1 2006
* 2009/0064,160 Transparent lazy maintenance of indexes and materialized views 13 2007
 
RED HAT, INC. (3)
* 7890491 Query optimization technique for obtaining improved cardinality estimates using statistics on automatic summary tables 23 2000
* 8386450 Query optimization technique for obtaining improved cardinality estimates using statistics on pre-defined queries 11 2004
* 2004/0181,521 Query optimization technique for obtaining improved cardinality estimates using statistics on pre-defined queries 34 2004
 
GOOGLE INC. (3)
* 6847962 Analyzing, optimizing and rewriting queries using matching and compensation between query and automatic summary tables 29 2000
7167853 Matching and compensation tests for optimizing correlated subqueries within query using automatic summary tables 8 2002
* 2003/0088,558 Optimizing correlated queries using automatic summary tables 11 2002
 
SIEBEL SYSTEMS, INC. (1)
* 2002/0072,951 MARKETING SUPPORT DATABASE MANAGEMENT METHOD, SYSTEM AND PROGRAM PRODUCT 687 1999
* Cited By Examiner