US5987450A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for obtaining complete and correct answers from incomplete and/or incorrect databases
Assignee: Google LLC
•
Filing: 1997-08-14
•
Granted: 1999-11-16
•
Expires: 2017-08-14
Abstract
Abstract A system and method for obtaining complete and correct answers from incomplete and/or partially incorrect databases determine if the answer to a query will be complete by determining whether the answer to the query is independent of an insertion update to the database. If the answer to the query is independent of an insertion update, the system and the method determine that the answer to the query will be complete. In the case of databases that may be incorrect, the system and the method determine if the answer to a given query will be correct by determining if the answer to the query is independent of a deletion update to the database. If the answer to the query is independent of a deletion update, the system and the method determine that the answer to the query will be correct.
Inventors
- 👤 Alon Yitzchak Levy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 23:39
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/23; G06F16/2365; G06F16/24; G06F16/245; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
64 words
A method for determining whether a database that is partially correct will provide a correct answer to a query, comprising: determining whether an answer to the query is independent of a deletion update to the database; and determining that the database will provide a correct answer to the query when the answer to the query is independent of a deletion update to the database.
Claim 2
Independent Claim
64 words
A method for determining whether a database that is partially correct will provide a correct answer to a query, comprising: determining whether an answer to the query is independent of a deletion update to the database; and determining that the database will provide a correct answer to the query when the answer to the query is independent of a deletion update to the database.
Claim 3
Dependent Claim
31 words
The method of claim 1, wherein determining whether the database will provide a correct answer to the query comprises determining whether the database will provide a complete answer to the query.
Claim 4
Dependent Claim
37 words
The method of claim 1, wherein determining whether the answer to the query is independent of a deletion update to the database comprises determining whether tuples affected by the deletion update and the query are mutually unsatisfiable.
Claim 5
Dependent Claim
111 words
The method of claim 1, wherein the query has a conjunctive constraint that uses only built-in atoms, each of the built-in atoms having one constant, the step of determining whether the answer to the query is independent of a deletion update to the data comprising, for every occurrence of the relation in a conjuct of the query, the steps of: mapping the constraint to the occurrence; adding the mapping of the constraint to the query to form a test query; determining whether the test query is satisfiable; and determining that the answer to the query is independent of a deletion update to the database when no satisfiable test query is found.
Claim 6
Independent Claim
64 words
A method for determining whether a database that is partially complete will provide a complete answer to a query, comprising: determining whether an answer to the query is independent of an insertion update to the database; and determining that the database will provide a complete answer to the query when the answer to the query is independent of an insertion update to the database.
Claim 7
Independent Claim
64 words
A method for determining whether a database that is partially complete will provide a complete answer to a query, comprising: determining whether an answer to the query is independent of an insertion update to the database; and determining that the database will provide a complete answer to the query when the answer to the query is independent of an insertion update to the database.
Claim 8
Dependent Claim
37 words
The method of claim 5, wherein determining whether the answer to the query is independent of an insertion update to the database comprises determining whether tuples affected by the insertion update and the query are mutually unsatisfiable.
Claim 9
Dependent Claim
111 words
The method of claim 5, wherein the query has a conjunctive constraint that uses only built-in atoms, each of the built-in atoms having one constant, the step of determining whether the answer to the query is independent of an insertion update to the database comprising, for every occurrence of the relation in a conjunct of the query, the steps of: mapping the constraint to the occurrence; forming a test query by adding the mapping of the constraint to the query; determining whether the test query is satisfiable; and determining that the answer to the query is independent of an insertion update to the database when no satisfiable test query is found.
Claim 10
Dependent Claim
115 words
An information retrieval system for retrieving information from a relational database, comprising: a device that sends a first query to the database; and a completeness/correctness determiner that receives the first query from the device and that determines if an answer to the first query from the database will be complete and correct, the completeness/correctness determiner comprising: a completeness analyzer that determines whether the answer to the first query is independent of an insertion update to the database; a correctness analyzer that determines if the answer to the first query is independent of a deletion update to the database; and a controller that communicates with and controls operations of the completeness analyzer and the correctness analyzer.
Claim 11
Dependent Claim
115 words
An information retrieval system for retrieving information from a relational database, comprising: a device that sends a first query to the database; and a completeness/correctness determiner that receives the first query from the device and that determines if an answer to the first query from the database will be complete and correct, the completeness/correctness determiner comprising: a completeness analyzer that determines whether the answer to the first query is independent of an insertion update to the database; a correctness analyzer that determines if the answer to the first query is independent of a deletion update to the database; and a controller that communicates with and controls operations of the completeness analyzer and the correctness analyzer.
Claim 12
Independent Claim
187 words
A method for determining whether a database whose current state is partially complete will provide a complete answer to a query, comprising: determining a first subset of subgoals of the query, the subgoals of the first subset having a first set of variables that functionally determine distinguished variables of the query, where an answer to the subgoals of the first subset is complete for the current database state; determining a minimal subset of a second set of variables that appear both in the first subset of subgoals and a second subset of subgoals that are not included the first subset, the variables in the minimal subset functionally determining all of the other variables in the second set of variables; determining whether an answer to the second subset of subgoals for the minimal subset of variables is a superset of the answer to the first subset of subgoals for the minimal subset of variables; and determining that the database will provide a complete answer to the query if the answer to the second subset of subgoals is a superset of the answer to the first subset of subgoals.
Claim 13
Independent Claim
187 words
A method for determining whether a database whose current state is partially complete will provide a complete answer to a query, comprising: determining a first subset of subgoals of the query, the subgoals of the first subset having a first set of variables that functionally determine distinguished variables of the query, where an answer to the subgoals of the first subset is complete for the current database state; determining a minimal subset of a second set of variables that appear both in the first subset of subgoals and a second subset of subgoals that are not included the first subset, the variables in the minimal subset functionally determining all of the other variables in the second set of variables; determining whether an answer to the second subset of subgoals for the minimal subset of variables is a superset of the answer to the first subset of subgoals for the minimal subset of variables; and determining that the database will provide a complete answer to the query if the answer to the second subset of subgoals is a superset of the answer to the first subset of subgoals.
References Cited (Backward Citations)
US5418943A
Cited
US5590322A
Cited
US5600831A
Cited
US5655116A
Cited
US5768578A
Cited
US5584024A
Cited
US5628012A
Cited
US5535385A
Cited
US5897632A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-15 | 2003-05-17 | 2003-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-15 | 2007-05-17 | 2007-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-15 | 2011-05-17 | 2011-11-16 | $7700.00 | Window Closed / Lapsed |