1. An a priori method of identifying dependencies and discovering correlations between column pairs from one or more relational databases and applying said discoveries in query optimization; said method comprising: a. selecting column pairs from said relational database or databases; b. collecting a random sample of value pairs from said selected column pairs; c. identifying functionally dependent column pairs; said column pairs identified by detection of soft functional dependencies between value pairs in said collected sample; d. preparing a set of value pairs using system catalog statistics for said relational database or databases; said set comprised of value pairs in said collected sample for which soft functional dependencies were not detected; and e. discovering correlated column pairs by testing for, using said test statistic, correlations between said sampled value pairs in prepared set; and f. recommending to said query optimizer, said functionally dependent and correlated column pairs.