Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-07-31
2007-07-31
Gaffin, Jeffrey (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
11352628
ABSTRACT:
The subject disclosure pertains to efficient computation of the difference between queries by exploiting commonality between them. A minimal difference query (MDQ) is generated that roughly corresponds to removal of as many joins as possible while still accurately representing the query difference. The minimal difference can be employed to further substantially the scope of view matching where a query is not wholly subsumed by a view. Additionally, the minimal difference query can be employed as an analytical tool in various contexts.
REFERENCES:
patent: 5768578 (1998-06-01), Kirk et al.
patent: 2004/0083204 (2004-04-01), Dettinger et al.
patent: 2005/0289100 (2005-12-01), Dettinger et al.
patent: 2006/0036580 (2006-02-01), Stata et al.
Afrati, F. et al., “Generating Efficient Plans for Queries Using Views,” in Proceedings of ACM SIGMOD Conference 2001, Santa Barbara, California, May 21-24, 2001, pp. 319-330.
AHO, A. et al., “Equivalence of Relational Expressions,” SIAM Journal of Computing, vol. 8, No. 2, May 1979, pp. 218-246.
Bello, R. et al., “Materialized Views in Oracle,” in Proceedings of the 24th VLDB Conference, New York, New York, 1998, pp. 659-664.
Chandra, A. and Merlin, P., “Optimal Implementation of Conjunctive Queries in Relational Databases,” in Proceedings of the Ninth Annual ACM Symposium on Theory of Computing (STOC), 1977, pp. 77-90.
Chaudhuri, S. et al., “Robust and Efficient Fuzzy Match for Online Data Cleaning,” in Proceedings of ACM SIGMOD Conference 2003, San Diego, California, Jun. 9-12, 2003, pp. 313-324.
Chaudhuri, S. et al., “Optimizing Queries with Materialized Views,” in Proceedings of the 11th International Conference on Data Engineering, Taipei, Taiwan, Mar. 6-10, 1995, pp. 190-200.
Cohen, W., “Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity,” in Proceedings of ACM SIGMOD Conference 1998, Seattle, Washington, Jun. 2-4, 1998, pp. 201-212.
Dar, S. et al., “Semantic Data Caching and Replacement,” in Proceedings of the 22nd VLDB Conference, Mumbai (Bombay), India, 1996, pp. 330-341.
Dayal, U., “Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers,” in Proceedings of the 13th VLDB Conference, Brighton, England, 1987, pp. 197-208.
Dehaan, D. et al., “Stacked Indexed Views in Microsoft SQL Server,” in Proceedings of the ACM SIGMOD Conference 2005, Baltimore, Maryland, Jun. 14-16, 2005, pp. 179-190.
Rundensteiner, E.A., Ed., Special Issue on Data Transformations, Bulletin of the Technical Committee on Data Engineering, vol. 22, No. 1, Mar. 1999, 54 pages.
Flesca, S. et al., “On the Minimization of Xpath Queries,” in Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003, 12 pages.
Ganski, R. and Wong, H., “Optimization of Nested SQL Queries Revisited,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1987, pp. 23-33.
Goldstein, J. and Larson, P., “Optimizing Queries Using Materialized Views: A Pratical, Scalable Solution,” in Proceedings of the ACM SIGMOD Conference 2001, Santa Barbara, California, May 21-24, 2001, pp. 331-342.
Graefe, G., “The Cascades Framework for Query Optimization,” Bulletin of the Technical Committee on Data Engineering, vol. 18, No. 3, Sep. 1995, pp. 19-28.
Gupta, A. et al., “Aggregate-Query Processing in Data Warehousing Environments,” in Proceedings of the 21st VLDB Conference, Zurich, Switzerland, Sep. 1995, pp. 358-369.
Dasu, T. et al., “Mining Database Structure; Or, How to Build a Data Quality Browser,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 2002, Madison, Wisconsin, Jun. 4-6, 2002, pp. 240-251.
Kim, W., “On Optimizing an SQL-like Nested Query,” ACM Transactions on Database Systems, vol. 7, No. 3, Sep. 1982, pp. 443-469.
Larson, P. et al., “Transparent Mid-Tier Database Caching in SQL Server,” in Proceedings of the ACM SIGMOD Conference 2003, San Diego, California, Jun. 9-12, 2003, p. 661.
Larson, P. and Yang, H., “Computing Queries from Derived Relations,” in Proceedings of the VLDB Conference, Stockholm, Sweden, 1985, pp. 259-269.
Larson, P. and Zhou, J., “View Matching for Outer-Join Views,” in Proceedings of the 31st VLDB Conference, Trondheim, Norway, Aug. 30-Sep. 2, 2005, pp. 445-456.
Levy, A. and Sagiv, Y., “Queries Independent of Updates,” in Proceedings of the 19th VLDB Conference, Dublin, Ireland, 1993, pp. 171-181.
Mandhani, B. and Suciu, D., “Query Caching and View Selection for XML Databases,” in Proceedings of the 31st VLDB Conference, Trondheim, Norway, Aug. 30-Sep. 2, 2005, pp. 469-480.
Minock, M. et al., “The Indentification of Missing Information Resources Through the Query Difference Operator,” in Proceedings of the 4th International Conference on Cooperative Information Systems (COOPIS '99), Edinburgh, Scotland, Sep. 2-4, 1999, 11 pages.
Muralikrishna, M., “Improved Unnesting Algorithms for Join Aggregate SQL Queries,” in Proceedings of the 18th VLDB Conference, Vancouver, B.C., Canada, 1992, pp. 91-102.
Park, C. et al., “Rewriting OLAP Queries Using Materialized Views and Dimension Hierarchies in Data Warehouses,” in Proceedings of the International Conference on Data Engineering, 2001, pp. 515-523.
Raman, V. and Hellerstein, J., “Potter's Wheel: An Interactive Data Cleaning System,” in Proceedings of the 27th VLDB Conference, Rome, Italy, 2001, pp. 381-390.
Sagiv, Y. and Yannakakis, M., “Equivalences Among Relational Expressions with the Union and Difference Operators,” Journal of the Association for Computing Machinery, vol. 27, No. 4, Oct. 1980, pp. 633-655.
Saraiya, Y., “Subtree-Elimination Algorithms in Deductive Databases,” Ph.D. Thesis, Stanford University, Stanford, California, 1991, University Microfilms International (UMI), 168 pages.
Srivastava, D. et al., “Answering Queries with Aggregation Using Views,” in Proceedings of the 22nd VLDB Conference, Mumbai (Bombay), India, 1996, pp. 318-329.
TPC Benchmark H, Decision Support, Standard Specification Revisions 2.3.0, Transaction Processing Performance Council (TPC), 145 pages. Available online at http://www.tpc.org/tpch/, last accessed on Mar. 15, 2006.
Van Der Meyden, R., “The Complexity of Querying Indefinite Data about Linearly Ordered Domains,” in Proceedings of the 11th Principles of Database Systems (PODS), San Diego, California, Jun. 1992, pp. 331-345.
Yan, L. et al., “Data-Driven Understanding and Refinement of Schema Mappings,” in Proceedings of the ACM SIGMOD Conference 2001, Santa Barbara, California, May 21-24, 2001, pp. 485-496.
Yang, H. and Larson, P., “Query Transformation for PSJ-Queries,” in Proceedings of the 13th VLDB Conference, Brighton, England, 1987, pp. 245-254.
Chang, J. and Lee, S., “Query Reformulation Using Materialized Views in Data Warehouse Environment,” in Proceedings of the First ACM International Workshop on Data Warehousing and OLAP, Washington, DC, 1998, pp. 54-59.
Zaharioudakis, M. et al., “Answering Complex SQL Queries Using Automatic Summary Tables,” in Proceedings of ACM SIGMOD Conference 2000, Dallas, Texas, pp. 105-116.
Dong Xin
Ganti Venkatesh
Shriraghav Kaushik
Gaffin Jeffrey
Ponikiewski Tomasz
LandOfFree
Minimal difference query and view matching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Minimal difference query and view matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal difference query and view matching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3812526