Multi-dimensional set object

1. A machine-implemented method of representing a collection of objects, the method comprising:

providing one or more data structure definitions, the one or more data structure definitions defining a set object to represent the collection of objects as being within a computer-representable universal set that is a subset of a universal set defined for the collection of objects, wherein the computer-representable universal set is limited to data types representable within a computer system; and

generating, with a computer-implemented constructor using the one or more data structure definitions, a set object representing the collection of objects, the set object being a one-dimensional set object comprising:

a first list of knot elements, each of the knot elements being a value;

a second list representing the knot elements that the one-dimensional set includes such that the second list represents the one-dimensional set includes values of corresponding knot elements; and

a third list representing elements, other than the knot elements, that are included in the one-dimensional set object such that the third list represents the one-dimensional set includes values between the values corresponding to the knot elements;

wherein the second and third lists are defined to be alternating elements of a one-dimensional bit vector, where bits of the second list are a one or zero to indicate an existence or non-existence of the knot elements, and the third list is defined to indicate whether the one-dimensional set includes a range that is bound by one or more knot elements based on bits that are a one or zero indicating an existence or non-existence of an element in a range.

2. A method in accordance with claim 1 , wherein the data structure definitions define the set object to be a one-dimensional set object comprising one or more ranges of elements.

3. A method in accordance with claim 1 , wherein the first list is a one-dimensional vector of values corresponding to the knot elements of a one-dimensional set.

4. A method in accordance with claim 1 , wherein the data structure definitions further define a multi-dimensional set object comprising a union of blocks of a partition, each block defining a disjoint collection of the objects.

5. A method in accordance with claim 4 , wherein the multi-dimensional set object is defined to comprise:

a first list of knot elements;

a second list representing blocks corresponding to the knot elements that the multi-dimensional set includes; and

a third list representing blocks corresponding to elements, other than the knot elements, that are included in the multi-dimensional set.

6. A method in accordance with claim 1 , wherein the data structure definitions further define a multi-dimensional set object comprising a Cartesian Product of two or more dimensions of a collection of the objects.

7. A method in accordance with claim 6 wherein the Cartesian Product is defined to comprise:

two references to set objects, a first reference corresponding to a first Cartesian Factor and a second reference corresponding to a second Cartesian Factor, wherein the references are ordered such that the references define a Cartesian Product of the collection of the objects.

8. A method in accordance with claim 1 , wherein the data structure definitions define a multi-dimensional set object comprising:

set objects nested within the multi-dimensional set object.

9. A method in accordance with claim 1 , wherein the data structure definitions define a multi-dimensional set object comprising:

a union set comprising blocks of a partition, each block defining a disjoint collection of the objects and being a reference referring to at least one of a one-dimensional set a union set, an empty set, a universal set, or a Cartesian Product set, wherein the Cartesian Product set comprises a Cartesian Product of a first Cartesian Factor being a one-dimensional set and a second Cartesian Factor being a reference referring to at least one of a union set, a Cartesian Product Set, or a one-dimensional set.

10. A method in accordance with claim 1 , wherein the data structure definitions define a multi-dimensional set object comprising:

a Cartesian Product set comprising a Cartesian Product of a first Cartesian Factor being a one-dimensional set and a second Cartesian Factor being a reference referring to at least one of a union set a Cartesian Product Set, or a one-dimensional set wherein the union set comprises blocks of a partition, each block defining a disjoint collection of objects and being a reference referring to at least one of a one-dimensional set, a union set, an empty set a universal set, or a Cartesian Product set.

11. A method in accordance with claim 1 , wherein the one or more data structure definitions define the set object as normalized sets.

12. A method in accordance with claim 1 , wherein the generated set object represents data on a storage medium, the method further comprising:receiving a query; and computing a result to the query, wherein computing the result to the query comprises determining whether to access the data in the storage medium based on the generated set object.

13. A method in accordance with claim 1 , wherein the one or more definitions define operations for set objects.

14. A method in accordance with claim 13 , wherein the operations for set objects comprise:

an operation to determine an intersection of two or more set objects;

an operation to determine a union of two or more set objects;

an operation to determine whether a set object includes a range; and

an operation to determine a complement of a set object.

15. A method in accordance with claim 1 , wherein

the first list of the knot elements represents elements;

each item in the second list corresponding to one of the knot elements of the first list; and

each item in the third list represents elements above, below, or between knot elements.

16. A computer program product, the computer program product tangibly embodied in a machine-readable storage device, the computer program product comprising:

one or more data structure definitions, the one or more data structure definitions comprising:

a constructor method for generating a set object, wherein the set object represents sets in a computer system the set object being a one-dimensional set object comprising:

a first list of knot elements, each of the knot elements being a value;

a second list representing the knot elements that the one-dimensional set includes such that the second list represents the one-dimensional set includes values of corresponding knot elements; and

a third list representing elements, other than the knot elements, that are included in the one-dimensional set object such that the third list represents the one-dimensional set includes values between the values corresponding to the knot elements;

wherein the second and third lists are defined to be alternating elements of a one-dimensional bit vector, where bits of the second list are a one or zero to indicate an existence or non-existence of the knot elements, and the third list is defined to indicate whether the one-dimensional set includes a range that is bound by one or more knot elements based on bits that are a one or zero indicating an existence or non-existence of an element in a range.

17. A computer program product in accordance with claim 16 , wherein the data structure definitions define a one-dimensional set object as one or more ranges of elements.

18. A computer program product in accordance with claim 16 , wherein the data structure definitions further define a multi-dimensional set object comprising a union of blocks of a partition, each block defining a disjoint collection of objects.

19. A computer program product in accordance with claim 18 , wherein the multi-dimensional set object is defined to comprise:

a first list of knot elements;

a second list representing blocks corresponding to the knot elements that the multi-dimensional set includes; and

a third list representing blocks corresponding to elements, other than the knot elements, that are included in the multi-dimensional set.

20. A computer program product in accordance with claim 16 , wherein the data structure definitions further define a multi-dimensional set object comprising a Cartesian Product of two or more dimensions of a collection of objects.

21. A computer program product in accordance with claim 20 , wherein the multi-dimensional set object is defined to comprise:

two references to set objects, a first reference corresponding to a first Cartesian Factor and a second reference corresponding to a second Cartesian Factor, wherein the references are ordered such that the references define a Cartesian Product of the collection of the objects.

22. A computer program product in accordance with claim 16 , wherein the generated set object represents data on a storage medium, the computer program product comprising instruction to cause data processing apparatus to perform operations comprising: receiving a query; and computing a result to the query, wherein computing the result to the query comprises determining whether to access the data in the storage medium based on the generated set object.

23. A computer program product in accordance with claim 16 , wherein the one or more data structure definitions define operations for the set object to comprise:

an operation to determine an intersection of two or more set objects;

an operation to determine a union of two or more set objects;

an operation to determine whether the set object includes a range; and

an operation to determine a complement of the set object.

24. A computer program product in accordance with claim 16 , wherein the data structure definitions define a multi-dimensional set object comprising:

set objects nested within the multi-dimensional set object.

25. A computer program product in accordance with claim 16 , wherein the data structure definitions further define a multi-dimensional set object comprising:

a union set comprising blocks of a partition, each block defining a disjoint collection of objects and being a reference referring to at least one of a one-dimensional set, a union set, an empty set, a universal set, or a Cartesian Product set, wherein the Cartesian Product set comprises a Cartesian Product of a first Cartesian Factor being a one-dimensional set and a second Cartesian Factor being a reference referring to at least one of a union set, a Cartesian Product Set, or a one-dimensional set.

26. A computer program product in accordance with claim 16 , wherein the data structure definitions further define a multi-dimensional set object comprising:

a Cartesian Product set comprising a Cartesian Product of a first Cartesian Factor being a one-dimensional set and a second Cartesian Factor being a reference referring to at least one of a union set, a Cartesian Product Set, or a one-dimensional set, wherein the union set comprises blocks of a partition, each block defining a disjoint collection of objects and being a reference referring to at least one of a one-dimensional set, a union set, an empty set, a universal set, or a Cartesian Product set.