Patent ID: 7805447

Claim:
A computer-implemented method of forming a sample table from a base table for testing semantics of a query to be run on the base table, comprising: sampling the base table to form an initial sample table and forming an intermediate table of each operator from an operator tree of the query by passing the initial sample table through the operator tree; inserting suggestion records into the intermediate table based on incompleteness in the intermediate table to form an expanded sample table; passing the expanded sample table through the operator tree to form an expanded intermediate table; pruning the expanded sample table to form a final sample table, wherein said pruning comprises: grouping equivalence classes of equivalent records in the expanded intermediate table; retaining a set of expanded sample table records whose corresponding set of intermediate records includes at least one record from all equivalence classes while being as small as possible; and classifying expanded sample table records and expanded intermediate table records into lineage groups, wherein the lineage groups each correspond to a set of records that derive from each other as they flow through the operator tree.