TY - GEN

T1 - An evaluation of TANE algorithm for functional dependency detection

AU - Bobrov, Nikita

AU - Chernishev, George

AU - Grigoriev, Dmitry

AU - Novikov, Boris

N1 - Bobrov N., Chernishev G., Grigoriev D., Novikov B. (2017) An Evaluation of TANE Algorithm for Functional Dependency Detection. In: Ouhammou Y., Ivanovic M., Abelló A., Bellatreche L. (eds) Model and Data Engineering. MEDI 2017. Lecture Notes in Computer Science, vol 10563. Springer, Cham. https://doi.org/10.1007/978-3-319-66854-3_16

PY - 2017

Y1 - 2017

N2 - Exploitation of logical schema information can allow producing better physical designs for a database. In order to exploit this information, one has to extract it from the data stored in the database. Extraction should be performed using some kind of an algorithm that provides an acceptable level of result quality. This quality has to be ensured, for example, in terms of precision.In this paper we consider a particular type of such information: functional dependencies. One of the well-known algorithms for extraction of functional dependencies is the TANE algorithm. We propose to study its precision-related properties which are relevant for its use in our automatic physical design tool. TANE, being an approximate algorithm, returns only a fraction of existing dependencies. It is also prone to false positives. In contrast with the previous research, which measured run times and memory consumption, we aim to evaluate the quality of this algorithm.Finally, we briefly describe the context of this study—constructing an alternative physical design tuning system that would use the output of the TANE algorithm. The system is an ordinary vertical partitioning tool, but which operates without workload knowledge, relying on data characteristics. Our plan is to employ TANE inside the functional dependency detection component. Thus, the purpose of evaluation is to study to what extent the properties of the algorithm affect our goals.

AB - Exploitation of logical schema information can allow producing better physical designs for a database. In order to exploit this information, one has to extract it from the data stored in the database. Extraction should be performed using some kind of an algorithm that provides an acceptable level of result quality. This quality has to be ensured, for example, in terms of precision.In this paper we consider a particular type of such information: functional dependencies. One of the well-known algorithms for extraction of functional dependencies is the TANE algorithm. We propose to study its precision-related properties which are relevant for its use in our automatic physical design tool. TANE, being an approximate algorithm, returns only a fraction of existing dependencies. It is also prone to false positives. In contrast with the previous research, which measured run times and memory consumption, we aim to evaluate the quality of this algorithm.Finally, we briefly describe the context of this study—constructing an alternative physical design tuning system that would use the output of the TANE algorithm. The system is an ordinary vertical partitioning tool, but which operates without workload knowledge, relying on data characteristics. Our plan is to employ TANE inside the functional dependency detection component. Thus, the purpose of evaluation is to study to what extent the properties of the algorithm affect our goals.

KW - Experimentati, Functional dependency, Functional dependency detection, Logical schema information, Physical design tuning, TANE, Von

KW - Functional dependency

KW - Functional dependency detection

KW - Logical schema information

KW - Physical design tuning

KW - TANE

KW - Vertical partitioning

KW - TANE

KW - Physical design tuning

KW - Vertical partitioning

KW - Logical schema information

KW - Functional dependency

KW - Functional dependency detection

KW - Experimentation

UR - https://link.springer.com/book/10.1007/978-3-319-66854-3

M3 - Conference contribution

SN - 978-3-319-66853-6

T3 - Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)

SP - 208

EP - 222

BT - Model and Data Engineering

PB - Springer Nature

T2 - Model and Data Engineering

Y2 - 4 October 2017 through 6 October 2017

ER -