Patent ID: 8239406

Claim:
A method of representing a database query expression for use during execution of the query expression by a computer, wherein the database query expression includes a plurality of predicates related to one another by at least one logical relation, the method comprising: generating a plurality of operands from the database query expression, wherein each operand in the plurality of operands is representative of a predicate in the plurality of predicates; assigning each operand in the plurality of operands to a separate bit in a binary operand map, the number of bits in the binary operand map based upon the number of predicates in the expression; generating an expression tree data structure based upon the generated plurality of operands, wherein the expression tree includes a plurality of nodes, wherein each node includes an operand identifier comprising a binary value that includes a bit set for each operand identified by the operand identifier according to the binary operand map, wherein each node defines a first logical relation between those predicates in the database query expression that are represented by operands identified by the operand identifier for such node, and wherein the plurality of nodes are arranged relative to one another in the data structure to define at least a second logical relation among predicates in the database query expression, wherein the expression tree includes a header, the header including a number of predicates in the tree and whether the tree is a special type, wherein the expression tree further includes at least one set, at least one group, and at least one block, wherein the tree is hierarchical such that each set includes at least one node and is associated with exactly one group, and each group includes at least one set and is associated with exactly one block, and each block includes at least one group, and wherein the expression tree implicitly represents relations such that the elements in each node are implicitly represented by “AND” relation, the nodes in a set are implicitly represented by “OR” relation, and the sets in a group are implicitly represented by “AND” relation without data in the data structure explicitly conveying these relations, wherein the expression tree includes a directory with a plurality of directory entries, and wherein each directory entry describes one group or describes one set, wherein the expression tree further includes a data area wherein the operand identifiers of the nodes are stored, the directory entries identifying which set and which group are associated with each node, and wherein the expression tree is simplified by: sorting the expression tree according to relation-preserving rules such that the operands and operations of the expression are represented according to a well-defined and predictable order; and applying a set of rules to the sorted expression tree, the rules comprising a list of transformations that preserve the logical relationships represented by the expression tree.