Discovery and Maintenance of Functional Dependencies by Independencies

All Contents

For semantic query optimization one needs detailed knowledge about the contents of the database. Traditional techniques use static knowledge about all possible states of the database which is already given. New techniques use knowledge only about the current state of the database which can be found by methods of knowledge discovery in databases. Databases are often very large and permanently in use. Therefore, methods of knowledge discovery are only allowed to take a small amount of the capacity of the database system. So database access has to be reduced to a minimum during the process of discovery and obviously if the database changes during the process of maintenance of the discovered knowledge. In this paper, the main effort has been put into minimizing the number of database accesses, w.r.t. discovery and maintenance. This is exemplified by the discovery of functional dependencies. We improve the inference of functional dependencies by using independencies and cardinality dependencies. First we give an axiomatization. Then we describe the three parts of our system: the initialization by cardinality dependencies, the exclusion of hypothetical dependencies by entailment, and the verification of hypothetical dependencies by SQL queries. Moreover, we investigate the complexity of each subsystem. In addition, we describe the maintenance of discovered dependencies and finally draw some conclusions.