Minimal difference query and view matching
View Patent ↗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 view matching system comprising the following computer implemented components:
a computer memory having stored thereon the following components executable by a processor:
an input component that receives a query and a materialized view, wherein the materialized view only partially intersects with the query;
an intersection component that determines the intersection between the query and materialized view;
a view map component that generates an intersection query by rewriting the intersection between the query and materialized view in terms of the materialized view;
a constraint difference component that determines the difference between the query and materialized view to generate a difference query; and
a functional dependency component that modifies the query and materialized view to enable the constraint difference component to eliminate more queries based on functional dependencies, such that if V k functionally determines v, then all occurrences of v are renamed using the same variable, and generates 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.
2. The view matching system of claim 1 , further comprising a query writing component that generates a new query that is the union of the intersection query and difference query.
3. The view matching system of claim 1 , wherein the constraint difference component generates a minimal difference query representing the difference between the query and materialized view.
4. The view matching system of claim 3 , the constraint difference component includes a naïve difference component that generates a naïve representation of the difference between the query and materialized view.
5. The view matching system of claim 4 , the constraint 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.
6. The view matching system of claim 5 , the constraint difference component includes an analysis component that analyzes the plurality of queries to identity redundant or contradictory queries that can be removed.
7. The view matching system of claim 6 , the constraint difference component generates the minimal difference query from the naïve representation and eliminates identified redundant or contradictory queries.
8. The view matching system of claim 7 , further comprising an inclusion dependency component that eliminates one or more queries from the minimal difference query based on inclusion dependencies.
9. The view matching system of claim 3 , wherein the constraint difference component employs a bag difference algorithm to generate the minimal difference query.
10. A view matching method comprising:
employing a processor to execute computer executable instructions stored on a computer readable medium to perform the following acts:
receiving a query and a materialized view, wherein the materialized view only partially intersects with the query;
generating an intersection query by rewriting an intersection between the query and materialized view in terms of the materialized view;
generating a difference query representing the difference between the query and materialized view; and
simplifying the query difference based on functional dependencies, comprising:
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.
11. The view matching system of claim 10 , further comprising generating a new query that is the union of the intersection query and difference query.
12. The method of claim 10 , further comprising:
partitioning conjuncts in a naïve rewritten query representing the difference query;
analyzing the conjuncts for redundancy by identifying redundant constructs in one or more partitions; and
generating a minimal difference query from the naïve rewritten query with redundancies removed.
13. The method of claim 12 , partitioning comprising:
dividing each conjuncts into individual partition; and
merging partitions that share common free variables.
14. A view matching system, comprising:
a computer memory having stored thereon the following components executable by a processor:
means for receiving a query and a materialized view, wherein the materialized view only partially intersects with the query;
means for generating an intersection query by rewriting an intersection between the query and materialized view in terms of the materialized view;
means for generating a minimal difference query representing the difference between the query and materialized view; and
means for modifying the query and the materialized view to eliminate more queries based on functional dependencies, such that if V k functionally determines v, then all occurrences of v are renamed using the same variable and if all variables in V k are bound, then v is determined and is bound as well; and
means for 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.
15. The system of claim 14 , further comprising means for generating a new query that is the union of the intersection query and difference query.