Process for performing logical combinations

• US 7,231,387 B2
• Filed: 10/03/2003
• Issued: 06/12/2007
• Est. Priority Date: 07/08/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Sauermann, Volker, Bergen, Axel Von, Schwarz, Arne
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Ahn; Sangwoo
• Application Number:
  US10/677,736
• Publication Number:
  US 20050021506A1
• Time in Patent Office: 1,348 Days
• Field of Search: 707 1- 10, 707100-1041
• US Class Current: 707/745
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/955 Object-oriented
• 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/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Techniques are described for performing logical operations, where the techniques generally involve the use of dynamic flags used as markers to build a result set in response to a search query. The dynamic flags within a result set may be guide elements linked to one another, and to their respective data records and attributes, via pointers. In this case, the groups of guide elements forming result sets may each also be linked to one another via pointers, and may each be associated with a counter for counting a number of guide elements within a corresponding result set. The dynamic flags also may be individual bits within a bitmap, where the bitmap is linked to a particular result set identifier via a pointer, and the individual bitmaps are linked to their corresponding data record(s) via a relative addressing scheme. In this case, a counter also may be used to determine a number of hits within a result set (bitmap), before, during, and after a particular logical operation.

Claims

1. A method for performing a logical OR operation, comprising:

building first and second result sets, further comprising;

identifying data records including first and second attributes from amongst first and second attribute sets stored in first and second tree structures, respectively,

assigning guide elements of the first result set to identified data records, and

assigning guide elements of the second result set to identified data records,

wherein the guide elements are each an instantiation of an object class in an object-oriented programming language, and linked to a data record via a pointer, and

wherein the first result set includes fewer guide elements than the second result set;

selecting the first result set;

iteratively checking whether each of the guide elements of the first result set also exists in the second result set;

renaming at least one of the guide elements of the first result set if the at least one of the guide elements of the first result set does not exist in the second result set;

deleting the at least one of the guide elements of the first result set if the at least one of the guide elements of the first result set exists in the second result set;

linking the renamed at least one of the guide elements of the first result set with the guide elements of the second result set, as the final result set; and

outputting the final result set.

2. The method of claim 1, wherein each of the guide elements are associated with a data record by changing a value of a first bit within a first bitmap.

3. The method of claim 2 wherein bits within the bitmap correspond in number to a total amount of data records available for searching.

4. The method of claim 2 further comprising:

linking a first result set identifier with the first bitmap via a first pointer; and

linking a second result set identifier with a second bitmap via a second pointer,

wherein the first result set identifier and the second result set identifier are linked together in a tree structure.

5. The method of claim 2 further comprising associating the first bit with the first record by calculating a bitmap memory address of the first bit relative to a data record memory address of the first record.

6. The method of claim 1,

wherein the first result set further comprises a counter, and

wherein the counter is decremented if the at least one of the guide elements of the first result set exists in the second result set.

7. A method for performing a logical AND operation, comprising:

building a result set, further comprising;

identifying data records including a first attribute from amongst a first attribute set stored in a first tree structure, and

assigning guide elements of the result set to the identified data records,

wherein the guide elements are each an instantiation of an object class in an object-oriented programming language, and linked to a data record via a pointer;

iteratively selecting each of the guide elements;

checking the record associated with each of the guide elements based upon a second attribute;

deleting at least one of the guide elements if the second attribute is not met by the at least one of the guide elements;

linking a predecessor of a deleted at least one of the guide elements with a successor of the deleted at least one of the guide elements; and

outputting the result set as the final result set.

8. The method of claim 7,

wherein the result set further comprises a counter;

and

wherein the counter is decremented if the second attribute is not met by the at least one of the guide elements.

9. A method for performing a logical AND operation, comprising:

building first and second result sets, further comprising;

identifying data records including first and second attributes from amongst first and second attribute sets stored in first and second tree structures, respectively,

assigning guide elements of the first result set to identified data records, and

assigning guide elements of the second result set to identified data records,

wherein the guide elements are each an instantiation of an object class in an object-oriented programming language, and linked to a data record via a pointer, and

wherein the first result set includes fewer guide elements than the second result set;

selecting the first result set;

iteratively checking whether each of the guide elements of the first result set also exists in the second result set;

deleting the at least one of the guide elements of the first result set if the at least one of the guide elements of the first result set does not exist in the second result set;

linking a predecessor of a deleted at least one of the guide elements with a successor of the deleted at least one of the guide elements; and

outputting the first result set as the final result set.

10. The method of claim 9,

wherein the first result set further comprises a counter, and

wherein the counter is decremented if the at least one of the guide elements of the first result set exists in the second result set.

11. A method for performing a logical NOT operation, comprising:

building a result set, further comprising;

identifying data records including a first attribute from amongst a first attribute set stored in a first tree structure, and

assigning guide elements of the result set to the identified data records,

wherein the guide elements are each an instantiation of an object class in an object-oriented programming language, and linked to a data record via a pointer;

iteratively checking each of the data records for a guide element of the first result set associated with the each of the data records;

instantiating a guide element in a second result set associated with each of the data records not associated with a guide element of the first result set;

linking guide elements of the second result set;

deleting the first result set; and

outputting the second result set as the final result set.

12. The method of claim 11,

wherein the second result set further comprises a counter;

and

wherein the counter is incremented for each instantiated guide element.

13. A computer program product, tangibly stored on a computer-readable medium, for performing a logical OR operation, the product comprising instructions operable to cause a programmable processor to:

build first and second result sets, wherein building a result set further comprises;

identifying data records including first and second attributes from amongst first and second attribute sets stored in first and second tree structures, respectively,

assigning guide elements of the first result set to identified data records, and

assigning guide elements of the second result set to identified data records,

wherein the guide elements are each an instantiation of an object class in an object-oriented programming language, and linked to a data record via a pointer, and

wherein the first result set includes fewer guide elements than the second result set;

select the first result set;

iteratively check whether each of the guide elements of the first result set also exists in the second result set;

rename at least one of the guide elements of the first result set if the at least one of the guide elements of the first result set does not exist in the second result set;

delete the at least one of the guide elements of the first result set if the at least one of the guide elements of the first result set exists in the second result set;

link the renamed at least one of the guide elements of the first result set with the guide elements of the second result set, as the final result set; and

output the final result set.

14. A computer program product, tangibly stored on a computer-readable medium, for performing a logical AND operation, the product comprising instructions operable to cause a programmable processor to:

build a result set, wherein building a result set further comprises;

identifying data records including a first attribute from amongst a first attribute set stored in a first tree structure, and

assigning guide elements of the result set to the identified data records,

wherein the guide elements are each an instantiation of an object class in an object-oriented programming language, and linked to a data record via a pointer;

iteratively select each of the guide elements;

check the record associated with each of the guide elements based upon a second attribute;

delete at least one of the guide elements if the second attribute is not met by the at least one of the guide elements;

link a predecessor of a deleted at least one of the guide elements with a successor of the deleted at least one of the guide elements; and

output the result set as the final result set.

15. A computer program product, tangibly stored on a computer-readable medium, for performing a logical AND operation, the product comprising instructions operable to cause a programmable processor to:

build first and second result sets, wherein building a result set further comprises;

identifying data records including first and second attributes from amongst first and second attribute sets stored in first and second tree structures, respectively,

assigning guide elements of the first result set to identified data records, and

assigning guide elements of the second result set to identified data records,

wherein the guide elements are each an instantiation of an object class in an object-oriented programming language, and linked to a data record via a pointer, and

wherein the first result set includes fewer guide elements than the second result set;

select the first result set;

iteratively check whether each of the guide elements of the first result set also exists in the second result set;

delete the at least one of the guide elements of the first result set if the at least one of the guide elements of the first result set does not exist in the second result set;

link a predecessor of a deleted at least one of the guide elements with a successor of the deleted at least one of the guide elements; and

output the first result set as the final result set.

16. A computer program product, tangibly stored on a computer-readable medium, for performing a logical NOT operation, the product comprising instructions operable to cause a programmable processor to:

build a result set, wherein building a result set further comprises;

identifying data records including a first attribute from amongst a first attribute set stored in a first tree structure, and

assigning guide elements of the result set to the identified data records,

wherein the guide elements are each an instantiation of an object class in an object-oriented programming language, and linked to a data record via a pointer;

iteratively check each of the data records for a guide element of the first result set associated with the each of the data records;

instantiate a guide element in a second result set associated with each of the data records not associated with a guide element of the first result set;

link guide elements of the second result set;

delete the first result set; and

output the second result set as the final result set.