Minimal difference query and view matching

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.

1 . A query difference system comprising the following computer-implemented components:
 a receiver component that receives a first and second query; and   a difference component that generates a minimal difference query representing the difference between the first and the second query.   
   
   
       2 . The system of  claim 1 , the difference component includes a naïve difference component that generates a naïve representation of the difference between the first and second query. 
   
   
       3 . The system of  claim 2 , the difference component includes a partition component that partitions the naïve representation into a plurality of queries the union of which is equivalent to the naïve representation. 
   
   
       4 . The system of  claim 3 , the difference component includes an analysis component that analyzes the plurality of queries to identity redundant or contradictory queries that can be removed. 
   
   
       5 . The system of  claim 4 , the difference component generates the minimal difference query from the naïve representation and eliminates identified redundant or contradictory queries. 
   
   
       6 . The system of  claim 5 , further comprising a functional dependency component that modifies the first and second query prior to receipt by the difference component to enable the difference component to eliminate more queries based on functional dependencies. 
   
   
       7 . The system of  claim 6 , further comprising an inclusion dependency component that eliminates one or more queries from the minimal difference query based on inclusion dependencies. 
   
   
       8 . The system of  claim 1 , further comprising a transformation component that associates unique identity attributes to data sets to enable bag semantic based minimal difference query generation. 
   
   
       9 . The system of  claim 1 , further comprising:
 an intersection component that generates an intersection query that identifies an intersection between the first and second query; and   a query writing component that generates a query based on the minimal difference query and the intersection query that efficiently queries a portion of a materialized view and a database, the first query corresponds to a query and the second query corresponds to the view.   
   
   
       10 . The system of  claim 1 , the components form part of one of an analytical tool and a query optimizer. 
   
   
       11 . A method of determining the difference between two queries comprising the following computer-implemented acts:
 partitioning conjuncts in a naïve rewritten query representing a difference between two queries;   analyzing the conjuncts for redundancy; and   generating a minimal difference query from the naïve rewritten query with redundancies removed.   
   
   
       12 . The method of  claim 11 , partitioning comprising:
 dividing each conjuncts into individual partition; and   merging partitions that share common free variables.   
   
   
       13 . The method of  claim 12 , analyzing conjuncts for redundancy comprises identifying redundant constructs in one or more partitions. 
   
   
       14 . The method of  claim 11 , further comprising simplifying the difference query based on functional dependencies. 
   
   
       15 . The method of  claim 14 , simplifying the query difference comprises:
 renaming variables in queries in accordance with functional dependencies such that if V k  functionally determines v, then all occurrences of v are renamed using the same variable; and   generating new bound variables V Q   d    ⊂ V Q   f , where for each v ε V Q   d , there exists a set of variables V K    ⊂  V that functionally determines v.   
   
   
       16 . The method of  claim 11 , further comprising removing conjuncts from the minimum difference query based on one or more inclusion dependencies. 
   
   
       17 . The method of  claim 11 , further comprising adding identity attributes to conjunct data sets prior to analyzing and removing the attributes after the minimal difference query is generated. 
   
   
       18 . A system for determining the difference between two queries comprising:
 means for partitioning conjuncts in a naive rewritten query representing a difference between two queries;   means for analyzing the conjuncts for redundancy; and   means for generating a minimal difference query from the naïve rewritten query with redundancies removed.   
   
   
       19 . The system of  claim 18 , partitioning comprising:
 means for dividing each conjuncts into individual partition; and   means for merging partitions that share common free variables.   
   
   
       20 . The method of  claim 19 , analyzing conjuncts for redundancy comprises identifying redundant constructs in one or more partitions.