1. A computer-implemented method for generating a cardinality estimate, comprising: identifying a predicate in a query, wherein the predicate is split into a plurality of equivalence classes; generating a plurality of undirected equivalence graphs from the plurality of equivalence classes, wherein the undirected equivalence graphs include a plurality of weighted edges representing a join predicate between two tables, and wherein the equivalence classes are determined based on sets of common attributes that are included in tables joined in the query; identifying spanning trees in the plurality of undirected equivalence graphs; determining a minimum spanning tree of the identified spanning trees; calculating a cardinality estimate based on the minimum spanning tree based on multiplying each predicate, in a set of identified predicates in the spanning tress, by a selectivity associated with each edge corresponding to the predicate, wherein a quality of the selectivity indicates a relationship between two tables joined in the query, and wherein the relationship indicates at least one of a key or attribute relationship between the two tables; and selecting a query plan corresponding to the cardinality estimate, wherein the cardinality estimate for the selected query plan is associated with a lower consumption of resources amongst a plurality of query plans in an execution of a query by a processor.