Method for efficient processing of multi-state attributes

• US 7,315,855 B2
• Filed: 05/12/2005
• Issued: 01/01/2008
• Est. Priority Date: 06/07/2002
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Kathmann, Kevin James, Carlson, David Glenn
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US11/127,647
• Publication Number:
  US 20050278316A1
• Time in Patent Office: 964 Days
• Field of Search: 707/2, 707/3, 707/4, 707/8, 707/10, 707/100, 707/103.R, 707/200, 707/101, 707/102, 717/109, 709/201, 709/208
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Methods, systems and articles of manufacture of processing a multi-state attribute field query. One embodiment provides a method of processing a multi-state attribute field query, comprising instantiating a plurality of live objects; performing, by each live object, an attribute operation, wherein at least one attribute operation is a comparison operation associated with attributes of the query. The plurality of live objects access a global status storage area only when an operand of the comparison operation is null or error. In any case, execution control is passed from each live object to an adjacent live object.

Claims

1. A computer-implemented method of processing a multi-state attribute field query, comprising:

a) structuring operator result states from a group comprising true, false, null, and error as intermediate multi-state operator input state results; and

b) using non-outcome determinative input-output logic operator properties to structure execution flow circumventing unproductive branches and yielding intermediate results from the group of true and false;

whereby the null and error intermediate multi-state operator results on the non-outcome determinative logic operator branches are pruned out rendering them ineffective in producing query results;

storing the intermediate results from attribute operations in a global status storage area and manipulating the global status storage area in the process of propagating execution flow; and

maintaining a logic operator value and operation object sub-tree height count in the global status storage area accessible by adjacent comparison operation objects when an operand of a comparison operation is null or error.

2. The computer-implemented method of claim 1, further comprising executing a plurality of instruction objects configured to perform attribute operations on associated attribute operands without the use of an intermediate evaluation stack by de-referencing and loading the associated attribute operands into registers for comparison operations.

3. The computer-implemented method of claim 1, further comprising allocating fields required by the query for a characteristic of an attribute and containing reference to a corresponding field attribute value.

4. The computer-implemented method of claim 1, further comprising instantiating an attribute descriptor vector data structure which comprises a set of individual attribute descriptor vectors required for the query.

5. The computer-implemented method of claim 4, further comprising instantiating a plurality of attribute operations on attribute fields defined by the attribute descriptor vector data structure.

6. The computer-implemented method of claim 1, further comprising accessing intermediate attribute operations on corresponding attributes by call foliation.

7. The computer-implemented method of claim 1, wherein the query is a structure query language (SQL) query.

8. The computer-implemented method of claim 1, further comprising accessing a global status stack only after a null or error status is encountered, the global status stack comprising:

a status field configured to hold values selected from a group comprising true, false, null and error; and

a behavior field configured to hold a logic operator.

9. A computer readable storage medium containing a program which, when executed, performs an operation for processing a multi-state attribute field query, the operation comprising:

a) structuring operator result states from a group comprising true, false, null, and error as intermediate multi-state operator input state results; and

b) using non-outcome determinative input-output logic operator properties to structure execution flow circumventing unproductive branches and yielding intermediate results from the group of true and false;

whereby the null and error intermediate multi-state operator results on the non-outcome determinative logic operator branches are pruned out rendering them ineffective in producing query results;

storing the intermediate results from attribute operations in a global status storage area and manipulating the global status storage area in the process of propagating execution flow; and

maintaining a logic operator value and operation object sub-tree height count in the global status storage area accessible by adjacent comparison operation objects when an operand of a comparison operation is null or error.

10. The computer-readable storage medium of claim 9, further comprising executing a plurality of instruction objects configured to perform attribute operations on associated attribute operands without the use of an intermediate evaluation stack by de-referencing and loading the associated attribute operands into registers for comparison operations.

11. The computer-readable storage medium of claim 9, further comprising allocating fields required by the query for a characteristic of an attribute and containing reference to a corresponding field attribute value.

12. The computer-readable storage medium of claim 9, further comprising accessing intermediate attribute operations on corresponding attributes by call foliation.

13. The computer-readable storage medium of claim 9, wherein the query is a structure query language (SQL) query.

14. The computer-readable storage medium of claim 9, further comprising accessing a global status stack data structure only after a null or error status is encountered, the global status stack comprising:

a status field configured to hold values selected from a group comprising true, false, null and error; and

a behavior field configured to hold a logic operator.

15. The computer-readable storage medium of claim 9, further comprising instantiating an attribute descriptor vector data structure which comprises a set of individual attribute descriptor vectors required for the query.

16. The computer-readable storage medium of claim 15, further comprising instantiating a plurality of attribute operations on attribute fields defined by the attribute descriptor vector data structure.