1. An article of manufacture comprising computer storage medium having computer readable program code embodied therein which, implements an a priori identification of dependencies and discovery of correlations between column pairs from one or more relational databases and applying said discoveries in query optimization, said medium comprising computer readable program code for: a. selecting column pairs from said relational databases; b. collecting a random sample of value pairs from said selected column pairs to produce a reduced table S; c. identifying functionally dependent column pairs in said selected column pairs by detecting soft functional dependencies between value pairs in said collected random sample of value pairs in said reduced table S, said soft functional dependency between a first column C 1 and a second column C 2 defined as |C 1 | S /|C 1 ,C 2 | S ≈1, said |C 1 | S denoting number of distinct values in column C 1 of reduced table S, said |C 1 ,C 2 | S denoting number of distinct values in a concatenation of columns C 1 and C 2 of reduced table S; d. preparing a set of value pairs using system catalog statistics for said relational databases; said set of value pairs comprising value pairs from said collected random sample of value pairs for which soft functional dependencies are not detected; e. identifying correlated column pairs in said selected column pairs by testing for correlations between value pairs in said prepared set of value pairs using a chi-squared test; and f. outputting to a query optimizer, said functionally dependent column pairs and said correlated column pairs, said query optimizer utilizing said functionally dependent column pairs identified and said correlated column pairs in query optimization.