Karima Ennaoui - Hybrid algorithms for candidate keys enumeration for a relational schema
Channel: ISAE-ENSMA officiel
Date: 12/01/2017

This paper investigates the problem of candidate keys enumeration of a relational database schema. The notion of candidate keys is also known as minimal generators in lattice or FCA terminologies. We consider the case where the input is a relation schema, composed of pairs of attribute subsets representing the interrelationship among attributes, i.e. a set of functional dependencies. Lucchesi and Osborn gave in [5] a polynomial incremental algorithm with an exponential space to enumerate all candidate keys of a relation schema. Saiedian and Spencer, introduce the notion of attribute graph of a set of functional dependencies and bring enumerating candidate keys of the relational schema to enumerating those of strongly connected components of its attribute graph. In this paper we exploit presence of unary functional dependencies that form a partial order over the set of attributes. We show a bijection between key-ideal sets (ideal associated to a key) and candidate keys. We show that the
number of key-ideal sets can be exponential in the number of minimal key-ideal sets. Moreover, if there is a polynomial delay algorithm to enumerate minimal key-ideal sets then there is one for all candidate keys. We also give an incremental polynomial algorithm to enumerate all minimal key-ideal sets. As a consequence, if the number of minimal key-ideal sets is polynomial in the size of the relational schema, then there is a polynomial delay algorithm to enumerate minimal key-ideal sets.