1. A method for generating a statistical summary of a database, the database having a plurality of base relations, the method comprising steps of: forming a sample-tuple set for at least one selected base relation of the plurality of base relations of the database, each sample-tuple set containing at least one sample tuple from a corresponding base relation; and forming a join synopsis set for each selected base relation, each join synopsis set containing a join synopsis for each sample tuple in a sample-tuple set, a join synopsis of a sample tuple being based on a join of the sample tuple and at least one descendent relation of the sample tuple, all join synopsis sets forming a statistical summary of the database.