Discovering Functional Dependencies From Possibilistic Data

Abstract

Functional dependencies can express important relationships in data. They can therefore help enforce the semantics of an application domain within a database system. This has applications in many database tasks, including database design, data consistency, update and query processing. Traditional functional dependencies (FDs) were introduced for applications in which data occurs with full certainty. An important problem, that has been studied over the last three decades, concerns the discovery of those functional dependencies that hold on a given data set. In modern applications, such as information extractions, financial risk assessment, or sensor management, data is inherently uncertain. Recently, a new notion of possibilistic functional dependency (pFD) has been introduced. In this data model, each tuple is assigned one of finitely many available degrees of possibility with which it is perceived to occur in the data. Each FD is assigned one of finitely many available degrees of certainty that says to which tuples the FD applies. The new notion of pFD has been shown to have important applications in the schema design of databases. In this thesis, we study the problem of discovering those pFDs that hold on a given possibilistic data set. For this purpose, we review several FD discovery algorithms. We then describe how to extend these algorithms to the discovery problem of pFDs. The extended algorithms have been implemented and their performance in terms of time and memory usage have been tested on real-world benchmark data sets whose tuples have been augmented by randomly assigned degrees of possibility. In addition, we apply canonical cover algorithms to reduce the size of the output of the discovery algorithms, showing that little time is necessary to significantly reduce the size of the output's representation. Given particular features of the input, such as the number of rows, number of columns and number of available possibility degrees, we identify those algorithms that perform the fastest on data sets with these features. This provides guidelines for practitioners to choose the most suitable algorithm for a given data set at hand. Our results support and extend recent findings for the performance of algorithms that address the traditional FD discovery problem.