2. 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 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, 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 comprised of value pairs in said collected sample 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 implemented as computer readable program code stored in computer storage of a computer, said functionally dependent column pairs and said correlated column pairs, said query optimizer utilizing said functionally dependent column pairs and said correlated column pairs in query optimization.
2. 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 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, 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 comprised of value pairs in said collected sample 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 implemented as computer readable program code stored in computer storage of a computer, said functionally dependent column pairs and said correlated column pairs, said query optimizer utilizing said functionally dependent column pairs and said correlated column pairs in query optimization. 3. The a priori method of claim 2 , wherein said selected column pairs are selected based on: a. generating candidate column pairs from said relational databases; b. pruning said generated candidate column pairs with respect to a set of heuristic constraints; and c. eliminating trivial instances of correlation in said generated candidate column pairs; said trivial instances of correlation identified by system catalog statistics for said relational databases.