Patent ID: 8296289

Claim:
An article of manufacture including a non-transitory computer readable storage medium to tangibly store instructions, which when executed by a computer, cause the computer to: receive a join query, a materialization graph representing a join part of the join query, and a plurality of matching sets; configure a tuple construction counter, which value indicates progression in an overall length of constructing a join tuple and an iterator that traverses a matching set from the plurality of matching sets; upon determining that the value of the tuple construction counter is a positive integer: (a) compute a partial specialization of an operator tree, wherein the operator tree represents a non-join part of the join query; (b) when the computed partial specialization satisfies the non-join part of the join query and the value of the tuple construction counter is less than the overall length of the join tuple to be constructed, recompute a subset of the plurality of matching sets; (c) when no empty matching set is encountered during recomputation, increase the value of the tuple construction counter by one count; (d) when the value of the tuple construction counter is equal to the overall length of the join tuple, identify a first join tuple satisfying the join part and the non-join part of the join query; and (e) when the computed partial specialization does not satisfy the non-join part of the join query or an empty matching set is encountered, decrease the value of the tuple construction counter by one or more counts; and continue steps (a) to (e) until the value of the tuple construction counter is equal to zero, wherein all join tuples satisfying the join part and the non-join part of the join query are identified when the value of the tuple construction counter is equal to zero.