System and method for obtaining complete and correct answers from incomplete and/or incorrect databases

• US 5,987,450 A
• Filed: 08/14/1997
• Issued: 11/16/1999
• Est. Priority Date: 08/22/1996
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Levy, Alon Yitzchak
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): RONES, CHARLES
• Application Number:
  US08/911,015
• Time in Patent Office: 824 Days
• Field of Search: 707/1, 707/3, 707/4, 707/5, 707/2, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.