Method and apparatus for querying a database containing disjunctive information

Abstract

A method and apparatus for querying a disjunctive database is disclosed. An annotated object, which defines a complete object which is a unique element of the normal form of the database, is stored and maintained in memory. A complete object is created using the annotated object, and is stored in memory. A query is run against the complete object. If continued processing is required, a next function produces a next annotated object, which represents another unique element of the normal form of the database. The next annotated object is stored in memory, overwriting the previous annotated object. A complete object is then created using the next annotated object and is stored in memory, overwriting the previous complete object. The query is then applied to the complete object stored in memory. By processing the elements of the normal form one at a time and reusing memory spaces, the present invention has a polynomial space requirement. The invention also allows processing to begin from a pre-defined annotated object, either user defined or random. A user defined annotated object may define certain sub-objects which are not to be processed. Further, processing may terminate with the last processed, annotated object as an output.

I claim: 
     
       1. A method for operation of a computer system for querying a database containing disjunctive information comprising the steps in the sequence set forth of: producing a first element of the normal form of the database;   applying a query against the first element of the normal form;   producing a second element of the normal form of the database; and   applying the query against the second element of the normal form.   
     
     
       2. The method of claim 1 wherein: said step of producing a first element of the normal form of the database further comprises the steps of: producing an initial annotated object, and   picking the first element of the normal form using the initial annotated object;     said step of producing a second element of the normal form of the database further comprises the steps of: producing a next annotated object using the initial annotated object, and   picking the second element of the normal form using the next annotated object.     
     
     
       3. The method of claim 1 further comprising the steps of: storing the first element of the normal form in a memory space; and   replacing the first element of the normal form with the second element of the normal form in the memory space.   
     
     
       4. The method of claim 2 further comprising the steps of: storing the initial annotated object in a memory space; and   replacing the initial annotated object with the next annotated object in the memory space.   
     
     
       5. The method of claim 1 wherein: said step of producing a first element of the normal form of the database further comprises the steps of: producing a random annotated object, and   picking the first element of the normal form using the random annotated object;     said step of producing a second element of the normal form of the database further comprises the steps of: producing a next annotated object using the random annotated object, and   picking the second element of the normal form using the next annotated object.     
     
     
       6. A method for operation of a computer system for querying a database containing disjunctive information comprising the steps of: (a) producing a unique element of the normal form of the database;   (b) applying a query to the unique element of the normal form; and   (c) conditionally repeating steps (a) and (b) in response to step (b).   
     
     
       7. The method of claim 6 wherein the first iteration of step (a) further comprises the steps of: receiving as input a starting annotated object; and   picking a unique element of the normal form using the starting annotated object.   
     
     
       8. The method of claim 7 wherein the received annotated object contains user specified type indicia, wherein step (a) further comprises the step of: excluding the production of certain unique elements of the normal form of the database in response to the user specified type indicia.   
     
     
       9. A method for operation of a computer system for processing a query on a database containing disjunctive information, the method comprising the steps of: (a) producing a unique element of the normal form of the database;   (b) applying a query to the element of the normal form produced in step (a); and   (c) repeating steps (a) and (b) until a stop condition has been satisfied.   
     
     
       10. The method of claim 9 wherein said stop condition is a predetermined time limit, said method further comprising the step of: terminating the processing and outputting results when the predetermined time limit has been reached.   
     
     
       11. The method of claim 9 wherein: the first iteration of step (a) further comprises the steps of: creating an initial annotated object, and   picking a complete object using the annotated object;     each iteration of step (a) after the first iteration further comprises the steps of: creating a next annotated object, and   picking a complete object using the next annotated object.     
     
     
       12. The method of claim 11 further comprising the step of: terminating the processing and outputting an annotated object when the stop condition is satisfied.   
     
     
       13. The method of claim 12 further comprising the step of: continuing the processing using the outputted annotated object.   
     
     
       14. The method of claim 9 wherein the first iteration of step (a) further comprises the steps of: receiving a user defined annotated object, and   picking a complete object using the annotated object.   
     
     
       15. The method of claim 9 wherein the first iteration of step (a) further comprises the steps of: receiving a random annotated object; and   picking a complete object using the random annotated object.   
     
     
       16. An apparatus for querying a database containing disjunctive information comprising: a computer processor;   a memory unit connected to the computer processor;   an annotated object stored in the memory unit;   means responsive to the annotated object for creating an element of the normal form of the database; and   query means for querying the element of the normal form.   
     
     
       17. The apparatus of claim 16 further comprising: means for producing a next annotated object from a current annotated object.   
     
     
       18. The apparatus of claim 17 wherein said means for producing a next annotated object from a current annotated object further comprises: means for replacing the current annotated object with the next annotated object in the memory unit.   
     
     
       19. The apparatus of claim 17 wherein said means responsive to the annotated object for creating an element of the normal form of the database further comprises: means for storing each created element of the normal form in the same memory space in the memory unit.   
     
     
       20. The apparatus of claim 16 further comprising: means for producing a random annotated object.   
     
     
       21. A method for operation of a computer system for generating elements of the normal form of a disjunctive database, the method comprising the steps of: creating a first annotated object which represents a first unique element of the normal form;   storing the first annotated object in a first memory space;   creating the first element of the normal form using the first annotated object; and   storing the first element of the normal form in a second memory space.   
     
     
       22. The method of claim 21 further comprising the step of: applying a query to the first element of the normal form.   
     
     
       23. The method of claim 21 further comprising the steps of: creating a second annotated object which represents a second unique element of the normal form;   storing the second annotated object in the first memory space;   creating the second element of the normal form using the second annotated object; and   storing the second element of the normal form in the second memory space.   
     
     
       24. The method of claim 23 further comprising the step of: applying a query to the second element of the normal form.   
     
     
       25. The method of claim 23 further comprising the steps of: applying a query to the first element of the normal form; and   applying a query to the second element of the normal form.