Minimal difference query and view matching
AssigneeMicrosoft Corporation
InventorsKaushik Shriraghav, Venkatesh Ganti, Xin Dong
Life of this patent
Estimating the term…
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.
Claims18
A query difference system on comprising the following computer-implemented components:
- a receiver component that receives a first and second query;
- a functional dependency component that modifies the first and second query prior to receipt by the difference component by renaming variables in queries in accordance with functional dependencies, when Vk functionally determines v, then all occurrences of v are renamed using the same variable, and generating new bound variables VQd⊂VQf, where for each vεVQd, there exists a set of variables VK⊂V that functionally determines v.
- a difference component that generates a minimal difference query based on the first and the second query;
- and
- at least one of a display device that displays the minimal difference query or a computer readable storage medium that stores the minimal difference query.
(canceled)
A method of determining the difference between two queries comprising the following computer-implemented acts:
- partitioning conjuncts in a naïve rewriting of query difference between the two queries;
- simplifying the query difference by renaming variables in queries in accordance with functional dependencies such that if Vk functionally determines v, then all occurrences of v are renamed using the same variable, and generating new bound variables VQd⊂VQf, where for each vεVQd, there exists a set of variables VK⊂V that functionally determines v.
- analyzing the conjuncts for redundancy;
- and
- generating a minimal difference query from the naïve rewriting with redundancies removed;
- and
- at least one of displaying the minimal difference query on a display device or storing the minimal difference query on a computer readable storage medium.
(canceled)
(canceled)
18-20. (canceled)
Dependencies are inferred from the claim text.