Systems and methods for estimating functional relationships in a database
A system that facilitates estimating functional relationships associated with one or more columns in a database comprises a sampling component that receives a random sample of records within the database. An estimate generator component calculates an estimate of strength of functional relationships based at least in part upon the received samples. For example, the estimate generator component can calculate an estimate of strength of a column as a key column based at least in part upon the received samples.
1. A system that facilitates estimating functional relationships associated with one or more columns in a database, the system, comprising at least a processor executing the following components:
a sampling component that receives a random sample of records within the database;
an estimate generator component that calculates an estimate of strength of the functional relationships associated with the one or more columns based at least in part upon a subset of the received sample and a selected measure;
an estimate selector component that facilitates selection of a measure of strength to be calculated by the estimate generator component;
an overhead calculator component that estimates a measure of overhead associated with a column in the database by utilizing:
Estimated
Overhead
(
A
)
=
N
S
^
J
A
(
R
)
,
where
S
^
J
A
(
R
)
=
1
p
2
·
S
k
,
1
A
S
k
,
2
,
p is a sampling fraction
(
k
N
)
,
N is a number of rows that have a column A in a relation R, and S k,1 and S k,2 are two independent uniform random samples of size k drawn from the relation R;
a row strength computation component that estimates strength |{circumflex over (X)}| of a column comprising one or more default values as a key column based at least on a number of clean records within the column in the database by utilizing:
| {circumflex over (X)}|=|{circumflex over (X)} small |+|{circumflex over (X)} large |
wherein, X small is a set of “dirty” rows in a relation R that have either zero or one conflicting representative tuple pairs in a set of tuples S, and X large corresponds to a set of “dirty” rows that have more than one conflicting pair represented in S;
the estimate generator component calculates an estimate of strength of a column as a key column as a function of the received samples utilizing the overhead calculator component, or the row strength computation component based at least on the selection of a measure of strength.
2. The system of claim 1 , further comprising a randomization component that is employed to provide the sampling component with the random sample of records.
3. The system of claim 1 , wherein the overhead calculator component utilizes a self-join algorithm in connection with estimating the measure of overhead.
4. The system of claim 3 , further comprising an error threshold component that determines a number of sample records to provide to the sampling component based at least in part upon a threshold amount of error allowed for the estimate generator component.
5. The system of claim 1 , wherein the estimate generator component employs a row strength computation component that estimates a number of clean records within a column in the database.
6. The system of claim 1 , further comprising a monitoring component that determines a number of sample records to provide to the sampling component based at least in part upon size of the database.
7. The system of claim 1 , further comprising monitoring component that determines a number of sample records to provide to the sampling component based at least in part upon a threshold performance associated with the estimate generator component.
8. The system of claim 1 , wherein the estimate generator component utilizes the following algorithm in connection with calculating an estimate of strength of functional relationships:
X
^
small
=
z
2
·
N
2
k
(
k
-
1
)
,
where, N is a number of rows that have a column A in the relation R, z 2 is a number of conflicting groups of size two in the random sample, and k is a size of the random sample.
9. The system of claim 8 , wherein the estimate generator component utilizes the following algorithm in connection with calculating an estimate of strength of functional relationships:
X
^
large
=
z
1
N
k
,
where z 1 is a total number of “dirty” rows over all large groups in the sample.
10. The system of claim 1 , further comprising a machine-learning component that generates inferences regarding a type of measure of strength to be estimated by the estimate generator component by analyzing contextual data and historical data.
11. A method for estimating strength of key dependencies in a database, comprising the following executable by a processor:
receiving random samples from the database, the samples are associated with a column comprising one or more default values associated therewith;
selecting a measure of strength to be estimated for assessing strength of the column as a key column;
estimating a measure of overhead associated with the column in the database by utilizing:
Estimated
Overhead
(
A
)
=
N
S
^
J
A
(
R
)
,
where
S
^
J
A
(
R
)
=
1
p
2
·
S
k
,
1
A
S
k
,
2
,
p is a sampling fraction
(
k
N
)
,
N is a number of rows that have a column A in a relation R, and S k,1 and S k,2 are two independent uniform random samples of size k drawn from the relation R, if a overhead associated with the column is selected as the measure of strength;
estimating strength |{circumflex over (X)}| of the column comprising the one or more default values as a key column based at least on a number of clean records within the column in the database by utilizing:
| {circumflex over (X)}|=|{circumflex over (X)} small |+|{circumflex over (X)} large |
wherein, X small is a set of “dirty” rows in a relation R that have either zero or one conflicting representative tuple pairs in a set of tuples S, and X large corresponds to a set of “dirty” rows that have more than one conflicting pair represented in S, if a row strength computation is selected as the measure of strength;
calculating an estimate of strength of a column as a key column as a function of the received samples utilizing the overhead calculator component or the row strength computation component based at least on the selection.
12. The method of claim 11 , further comprising:
determining size of the database; and
determining one of a number and size of the samples based at least in part upon the determined size.
13. The method of claim 11 , further comprising:
computing a sampling fraction; and
estimating strength of the column as a key column based at least in part upon the computed sampling fraction.
14. The method of claim 11 , further comprising:
defining a threshold amount of error tolerance that can be associated with the estimated strength; and
determining one of a number and size of the samples based at least in part upon the defined threshold.