Computing probabilistic answers to queries
US7363299B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 17, 2005 |
| Grant date | Apr 22, 2008 |
| Priority date | — |
| Expiry date | Jun 26, 2026 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99933
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A system that supports arbitrarily complex SQL queries with “uncertain” predicates. The query semantics are based on a probabilistic model and the results are ranked, much like in Information Retrieval, based upon their probability. An optimization algorithm is employed that can efficiently compute most queries. The algorithm attempts to determine whether a proposed plan is a safe plan that can be used for correctly evaluating the query. Operators such as the project operator in the proposed plan are evaluated to determine if they are safe. If so, the proposed plan is safe and will produce correct answers in a result. Due to the data complexity of some queries, a safe plan may not exist for a query. For these queries, either a “least unsafe plan,” or a Monte-Carlo simulation algorithm can be employed to produce a result with answers that have an acceptable error.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.