Process for performing logical combinations

• US 20050021506A1
• Filed: 10/03/2003
• Published: 01/27/2005
• 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
• Granted Patent: US 7,231,387 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 comprising:

building a first result set; and

performing a logical operation based on the first result set,

wherein building the first result set includes;

identifying a first data record, the first data record including a first attribute from among a first attribute set, the first attribute set stored in a first tree structure; and

assigning a first marker to the first data record, wherein the first marker is included in the first result set.

2. The method of claim 1 further comprising building a second result set, wherein building the second result set includes identifying a second data record, the second data record including a second attribute from among the first attribute set.

3. The method of claim 2 wherein the first data record and the second data record are stored in a second tree structure.

4. The method of claim 2 wherein performing the logical operation comprises performing a logical AND combination between the first result set, based on the first marker, and the second result set, based on the second attribute.

5. The method of claim 2 further comprising assigning a second marker to the second attribute.

6. The method of claim 5 wherein performing the logical operation comprises performing a logical AND combination between the first result set, based on the first marker, and the second result set, based on the second marker.

7. The method of claim 5 wherein performing the logical operation comprises performing a logical OR combination between the first result set, based on the first marker, and the second result set, based on the second marker.

8. The method of claim 1 wherein performing the logical combination comprises performing a logical NOT combination on the first result set, based on the first marker, by de-selecting data records associated with the first result set and selecting remaining data records that include attributes from the first attribute set other than the first attribute.

9. The method of claim 1 wherein the first marker is an instantiation of an object class in an object-oriented programming language, and linked to the first data record via a pointer.

10. The method of claim 1 wherein identifying the first data record is in response to a first query.

11. The method of claim 10 wherein building the first result set comprises:

associating a second marker with a second data record including the first attribute, in response to the first query; and

grouping the first marker and the second marker into the first result set.

12. The method of claim 11 wherein grouping the first marker and the second marker comprises assigning a first pointer between the first marker and the second marker.

13. The method of claim 12 further comprising building a second result set, wherein building the second result set includes:

selecting a third data record, the third data record including a third attribute from among a second attribute set; and

associating a third marker with the third attribute.

14. The method of claim 13 wherein performing the logical operation comprises:

performing the logical operation between the first result set and the second result set to obtain a final result set;

determining that the first and third marker are included in the final result set;

determining that the second marker is not included in the final result set;

deleting the second marker from the final result set; and

re-directing the first pointer from the first marker to the third marker.

15. The method of claim 14, further comprising associating a counter with the third result set, the counter operable to indicate a number of markers within the third result set.

16. The method of claim 13 wherein the first result set and the second result set are linked to one another using pointers.

17. The method of claim 1 wherein assigning the first marker to the first data record includes changing a value of a first bit within a first bitmap.

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

19. The method of claim 17 further comprising building a second result set, wherein building the second result set includes selecting a second data record, the second data record including a second attribute from among a second attribute set.

20. The method of claim 19 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 second tree structure.

21. The method of claim 19 further comprising assigning a second marker to the second attribute by changing a value of a second bit within a second bitmap.

22. The method of claim 21 wherein performing the logical operation comprises performing a bitwise combination between the first bitmap and the second bitmap, to thereby obtain a third bitmap.

23. The method of claim 22 further comprising associating a counter with the third bitmap, the counter being operable to count a number of changed-value bits within the third bitmap.

24. The method of claim 17 wherein performing the logical operation comprises performing a bitwise logical operation using the first bitmap.

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

26. A system for searching data, the system comprising:

an interface operable to input data records, attributes associated with the data records, and queries, and further operable to output the data records, the attributes, and query responses;

a data storage device operable to store the attributes in a first tree structure, and further operable to store the data records in a second structure, the second structure relating a first data record to a first attribute; and

a search subsystem operable to build a first result set in response to a first query, the first result set including a first marker associated with the first data record, and further operable to perform a logical operation based on the first result set.

27. The system of claim 26 wherein the second structure is a second tree structure.

28. The system of claim 26 wherein the search subsystem is further operable to build a second result set in response to a second query, the second result set including a second marker associated with a second data record.

29. The system of claim 28 wherein the search subsystem is further operable to perform the logical operation based on the first marker and the second marker, to thereby build a third result set which includes at least one of the first marker and the second marker.

30. The system of claim 29 further comprising a counter associated with the third result set and operable to count a total number of markers within the third result set.

31. The method of claim 30 wherein the marker is an instantiation of an object class in an object-oriented programming language.

32. The system of claim 31 wherein markers within and between the first result set, the second result set, and the third result set are linked together using pointers.

33. The system of claim 30 wherein the first marker and the second marker are changed-value bits within a first bitmap and a second bitmap, respectively.

34. The system of claim 33 wherein the search subsystem performs the logical operation by performing a bitwise combination of the first bitmap and the second bitmap, to thereby obtain a third bitmap as the third result set.

35. The system of claim 34 wherein the search subsystem associates the first bit within the first bitmap with the first data record by calculating a bitmap memory address of the first bit relative to a data record memory address of the first data record.

36. The system of claim 35 wherein the search subsystem is further operable to link a first result set identifier with the first bitmap via a first pointer, and to link a second result set identifier with the second bitmap via a second pointer, wherein the first result set identifier and the second result set identifier are linked together in a second tree structure.

37. An apparatus comprising a storage medium having instructions stored thereon, the instructions including:

a first code segment for selecting a first marker within a first result set, the first marker associated with a first data record including a first attribute that is stored in an attribute tree structure;

a second code segment for performing a logical operation based on the first marker;

a third code segment for individually selecting remaining markers within the first result set, where the second code segment iteratively performs further logical operations based on the remaining markers; and

a fourth code segment for building a final result set based on the logical operations.

38. The apparatus of claim 37 wherein the second code segment includes:

a fifth code segment for deleting markers which are not included in the final result set; and

a sixth code segment for decreasing a counter associated with the first result set accordingly.

39. The apparatus of claim 37 wherein the first code segment includes a fifth code segment for selecting a second marker within a second result set, the second marker associated with a second data record including a second attribute that is stored in the attribute tree structure.

40. The apparatus of claim 39 wherein the second code segment includes a sixth code segment for performing the logical operations based on the first marker and the second marker, so that the final result set includes at least one of the first marker and the second marker.

41. The apparatus of claim 40 wherein the first marker is an instantiation of an object class in an object-oriented programming language.

42. The apparatus of claim 41 further comprising a seventh code segment for linking markers within and between the first result set and the second result set together using pointers.

43. The apparatus of claim 39 wherein the first marker and the second marker are changed-value bits within a first bitmap and a second bitmap, respectively.

44. The apparatus of claim 43 wherein the second code segment is for performing the logical operation by performing a bitwise combination of the first bitmap and the second bitmap, to thereby obtain a third bitmap as the third result set.

45. The system of claim 44 wherein the fourth code segment is further for associating the first bit within the first bitmap with the first data record by calculating a bitmap memory address of the first bit relative to a data record memory address of the first data record.

46. The apparatus of claim 44 further comprising a fifth code segment for linking a first result set identifier with the first bitmap via a first pointer, and also for linking a second result set identifier with the second bitmap via a second pointer, wherein the first result set identifier and the second result set identifier are linked together in a second tree structure.