Informative Armstrong Relations: Application to Database Analysis

National audienceGiven a set F of functional dependencies (FDs), Armstrong relations for F are example relations satisfying exactly F. Instead of starting from F, an interesting issue is to consider an existing relation, say r, and compute Armstrong relations for dep(r), the set of FDs satisfied in r. In this setting, the main contribution of this paper is to define so ­called Infor­mative Armstrong Relations (IAR), say s, for r such that s is a subset of r and s is an Armstrong relation for dep(r). Such a relation always exists since r itself is obviously an IAR for dep(r), but the challenge is to compute IAR whose size is as small as possible. First, we proof that generating the smallest IAR is NP­complete. Then, we give an heuristic to construct small IARs for a given relation. Some expe­riments have been performed on relations available in the KDD archive; they point out the interest of IARs to sample existing relations