Patent ID: 7809713

Claim:
A computer implemented method, comprising transforming a base query that includes a plurality of base branches of a union operator in a base query; and wherein transforming the base query includes: generating a plurality of units that each correspond to a set of base branches of the plurality of base branches; wherein each unit of said plurality of units represents a factorization of a common table set involving a common table joined in each branch of the respective set of base branches; generating a certain plurality of states that conform to one or more criteria, wherein each state of said certain plurality of states corresponds to a combination of one or more units of said plurality of units, and a query transformation according to the one or more factorizations represented by the combination of one or more units; generating costs for at least a subset of states of said certain plurality of states; making a comparison of the costs of the subset of states to select a certain state of said certain plurality of states; and wherein said computer implemented method is performed by one or more computing devices.